NEWS, EDITORIALS, REFERENCE

Subscribe to C64OS.com with your favorite RSS Reader
September 18, 2017#42 Programming Theory

Organizing a Big Module

Post Archive Icon

Let's start with a description of the Toolkit drawing system.

As should be evident from my last post, Toolkit Introduction, I've been hard at work (during whatever spare time I can manage) designing and building out the Toolkit module of C64 OS. I spent the weekend (re)implementing two of the biggest components of the view drawing system which I haven't even had a chance to discuss yet here. To be honest, I've been avoiding discussing it, because it's been so in flux. But, given that this is a blog about my progress, maybe I should be talking more regularly about the thoughts I've been having and the dead ends I've hit and the things I've tried. Drawing, in general, is a complex topic. So it's really hard to cover in a single post. I will eventually dedicate an entire post just to talking about how the drawing system works.

In brief, there is a global structure, maintained by the screen module, called the draw context. It defines the screen and color memory origins (2 byte pointers each), the width and height, 1 byte each because they're in character cells, and these define a rectangular region on the screen. The draw rect is always an on-screen area measured in character cells, so width and height don't need to be 16-bit. 40 columns and 25 rows is well below needing 16-bits. Additionally, the draw context has two more values, offset top and offset left. These are both 16-bit and represent the scroll offsets of the draw context.

The scroll offsets are what make things particularly complex, but as far as I can tell they're necessary. They are what allow the hierarchy of nested views to be scrolled. And they have to be 16-bit otherwise nothing would be able to scroll more than just a few screens.

Every view has the ability to draw itself, and when it does it uses the details in the current draw context to know how much space is available, where it starts in memory, and how offset its origin is from the virtual origin of the view itself (those are the scroll offsets). Typically a view like a button, a label, a checkbox or whatever just have to draw themselves. Views do have the ability to have children, of course, but the leaf views don't have children. A button, for example, even though it inherits node properties (including a child pointer) will never actually have children. In fact if you instantiate a view and assign it as the child of a button, that child will never be drawn, because button's draw routine does not attempt to pass drawing control to any children, because it assumes it doesn't have any.

The View view, aka the root class from which all the other views descend, implements a draw routine which on its own doesn't need to do much except clear the rectangle defined by the draw context. But View is also the main container for laying out children. So, if you want to have a UI that puts two scroll views side by side (or one above the other) for a sort of two-up dual pane, those two scroll views are siblings of each other, and they share a parent. That parent is most likely View. View has a special feature of its draw routine that recursively calls draw on each of its child views. This logic is quite complex, so one wouldn't want to implement it twice, as you'll see very shortly.

There are two other container views, Scroll view and Split view. Scroll view is effectively just View but with scrollbars that can be interacted with to change the offset top and offset left properties of its own draw context. And split view maintains two children and an interactable control for changing the draw context's height of its two children (if horizontal split) or width (if vertical split). But these two container views do not reimplement View's draw logic. They just set the draw context in a custom way, set a couple of custom pointers, and then call View's own draw routines. And that is a big benefit of object oriented code.

When View is recursively walking through its children there are actually three steps it needs to go through. And two of these are what I was working on finishing up this weekend. They are:

  • Resize Node
  • Bounds Check
  • Recontext

A resize occurs when the width or height metrics of a view changes. A global resize flag is set and a view's size is recomputed. This has down stream effects, because views can be anchored in such a way that their size changes as a result of their parent changing size. A resize is usually caused by interaction with a split view but view metrics can also be changed programmatically. If they are one simply has to set the global resize flag manually. There are some efficiencies baked into how this works so that not every view has to have its size recomputed, and one of the flags of the view_rsmask is used to help determine if the view needs to be resized.

Next a bounds check is performed. The containing view, before recursing to its next child uses the metrics of the child and compares against the draw context to determine if any part of the child will be visible on screen. If the scroll offsets are set in such a way that the child is scrolled out of view, then the parent simply skips over this child and moves on to the next.

Recontext is a step that will take me a moment to unpack. Each view, when it draws itself, is drawing itself into a global 10-byte draw context, as described earlier. However, that global draw context changes as the system recursively moves through the view hierarchy. Later on, let's say you mouse down on a button, or you type a character when an input view is in focus, in such a case only that one singular view is updated and needs to redraw itself, (to highlight the button, or insert a character, etc.) But the global draw context is no longer relevant to the view that needs to redraw. We could redraw the entire screen but that would be much too slow. Instead, each view maintains a copy of the draw context, as it was when the view last drew itself.

Those contexts become out-of-date, however, if there is a scroll or resize. So another global flag indicates if a recontext needs to happen. The recontext routine takes the current draw context, for the parent or containing view, and modifies it (it always either stays the same or gets smaller, it cannot ever become bigger) according to the offset and size metrics of the child. The child then backs up that new context onto itself. And lastly it draws itself. When the recontext flag is not set, each time a view is to be drawn the global context is set from the copy of the context on the view, which is much less computationally expensive than the recontext logic. In the event that a single view has to be redrawn, the context is simply copied from that view to the global context and then its draw routine is called as normal. It has no idea it isn't being called as part of an entire screen refresh.

This is very cool stuff. I'm having lots of fun. This is easily my favorite type of code to work on.


The devil in the details, the problem of complex code

So the above was as quick an overview as I can give about how drawing works without getting into the nitty gritty technical details. But I feel it was necessary to give at least this level of detail on how it works to understand the level of complexity being worked with.

Last night, after midnight, as I was getting tired and ready to wrap up, I got the dreaded error message:

LABELNAME OVERFLOW!

The last time I went through this and I asked about it on IRC, everyone seemed to nod in agreement that the time is now right for me to switch to cross assembly. As opposed to the coding native on a C64 (actually a C128) that I've been doing up to this point. A C64's limited memory and computational capacity puts limitations not just on what can be run, but also what can be coded. There is a limit to how many labels can be used. Assembly programming labels stand in for constants, and for memory addresses that will only resolved at assemble-time.

When I first started learning 65021 (coming up on a year ago next month) I was so wet behind the ears that I just started coding everything into one big file. It didn't take me more than a couple of months before I encountered my first Labelname Overflow. I resisted then the temptation and near universal advice to switch to cross assembly, by coming up with an ability to break the project into more manageable modules. This solution and its subsequent refinements to make it more workable are well documented across several posts:

Now I've hit this problem again. Except instead of the entire C64 OS project being too big and unwieldy, just the Toolkit module itself has become too big and unwieldy! It's a similar situation but I think it needs a different solution. And I don't yet know what that's going to be.

Here are some stats. The main source file, toolkit.a, is 56 blocks. A block is 256 bytes, minus the two byte link pointer. So a rough measurement in kilobytes is to divide block count by 4. Toolkit is therefore about 14 kilobytes. But that's the source code, which is full of comments so I don't forget how all this stuff is supposed to work. Assembled, last I assembled it, was about 7 blocks. Or, less than 2K. Less than 2 kilobytes, on a machine with 64 kilobytes of ram. Toolkit's code is under 3% of total available memory and I'm already overflowing the labels! How does anyone write a game that fills or nearly fills the C64's memory?

I think the answer to that question is that they either cross assemble, or huge regions of memory are dedicated to sprites, graphics, music and level data, leaving a much smaller area of memory for the game's engine code in the first place. Or the parts of the game are divided up manually into areas of memory where the connections between the parts can be hardcoded.

As an operating system, C64 OS obviously should try to take up as little memory as it can, leaving as much free memory for the application and its data as possible. This should be on my side for not running into label overflows. But I've also got at least two things working against me.

Toolkit is without a doubt the largest and most complex module of the bunch. But furthermore, because it is object oriented, it is also the most label heavy. I mean, the definition of the view class is effectively just a long list of all the labels that represent offsets to its properties. This problem is exacerbated by another interesting limitation.

Macros are super handy for not having to type everything out long form. They're particularly useful when you're doing lots of 16-bit math and pointer manipulation. But when you call a macro, all of its arguments have to fit on one 40 column line. The macro name automatically gets indented 8 spaces. So, after a macro name that's 8 or so characters, plus spaces, commas and the # symbol, you end up with only 22 or so characters for the names of the arguments. If any one of the names of the arguments exceeds 7 characters, there is suddenly not enough room on the line for just 3 arguments.

I've yet to write a macro that needed 4 arguments, but 3 is a common pattern. Many of the label names for properties are like this: view_draw, view_kcmd, view_kprnt etc. Even short names like this are 9 characters! Now imagine a macro call like this (the preceding white space is part of the line length!):

        #setobj16 this,view_kprnt,view_kprnt_

That is a 45 character line. Aka, it's impossible to type out. And macros (in Turbo Macro Pro+reu) cannot have their arguments spill onto a second line. One way to get around this is to define some temporary labels: vkp = view_kprnt and vkp_ = view_kprnt_. If you do this on the line above the macro call it's close enough in the code that the call remains legible... but you've just blown two more labels on nothing but making a macro call possible.

Another problem that Toolkit faces is that it seems to be the one module that leans most heavily on the resources of almost every other module. It needs math, string, memory, screen, service and input. (Math for 16bit divides and multiplies plus 16-bit macros, String for character conversion and length measurements, Memory for allocating and freeing space for new objects, Screen for the draw context system, Service for environment variables for system colors, Input for reading event objects.) Toolkit is a monster that seems to need to depend on bits and pieces of at least 6 out of only 9 or 10 modules total. Reading in header files and constants files bumps up the label count some more.

It's a tough problem.

But I'm not giving up. And I'm not caving in and switching to cross assembly. The first time I hit this problem I worked out a great solution. And I'll find a solution to this problem too. I have a few ideas in mind that will ease the pressure:

  • Move some big and label-heavy routines (boundschk, resizenode, recontext) out of Toolkit and into a smaller but related module (like Screen).
  • Shorten object property labels: view_... to vw_... or even v_...
  • Reduce the number of property labels by joining some properties conceptually. width and height could be a 4-byte dimension property, accessed as v_dim+2 etc.
  • Split some long external includes into multiple include files so one can be included without including and incorporating the labels from the others.
  • Unmacro a few things that really don't need to be macro'd.
  • Use hardcoded offsets for short-distance branches, rather than highly localized labels like next, skip or loop.

If I do all of the above, I should be back in business for some time to come, and may even be able to get most of Toolkit completed within the remaining constraints. If the above is not enough and I encounter Labelname Overflow again, I could try to split the Toolkit classes into separate files. I would like to avoid that, however, because there is definitely overhead, both memory, execution and organizational.

Thanks for reading. Until next post.

UPDATE: September 19, 2017

Last night I got to work implementing my remediation plan above. But first I decided to do a manual count of how many unique labels are in use by Toolkit. My rough counting came very close to 256, so I'm going to guess that's the key number, for obvious reasons.

On the one hand it feels like quite a few labels, but considering I'm able to use 30 or so in just one single routine, it feels like a cripplingly small number. Fortunately, to my discovery, recontext, resizenode, and boundschk are all called, conditionally, but only one other routine, drawchildren. I am going to move all 4 routines, lock, stock and barrel, to the screen module. And I only have to expose one new jumptable entry. drawchildren. Draw Children was actually something I'd already factored out of View's main draw routine, so it can be called easily by other container views.

  1. I dabbled with 6502 ASM over the course of my long history as a Commodore user. But I never made anything of any substantial complexity. Whatever I knew I forgot and had to completely relearn. When I was programming apps for WiNGs, it was 99.9% in C. []