Subscribe to with your favorite RSS Reader
August 15, 2017#40 Programming Theory

Organizing Module Layout

Post Archive Icon

At the beginning of the year I wrote a post, Organizaing a Big Project. At that time, I had just split apart what had been a monolithic code file into a series of more managable modules. At the time of this writing they're documented in the C64 OS technical documentation as:

  1. memory
  2. petscii
  3. input
  4. string
  5. screen
  6. menu
  7. service
  8. file
  9. toolkit, and
  10. network

However, this list is in such flux that even though that documentation was updated just 2 weeks ago, this list of modules has already changed. I've merged petscii, (which only had 3 exports: asc2pet, pet2asc and pet2scr) into the string module which is likely to gain far more functionality in the coming months. Plus, I added a math module, 16-bit division and multiplication routines that started their life in toolkit due to their usefulness there, have been moved to their own module so they can be reused by other modules and by C64 OS applications. And lastly, the system jump table has been extricated from memory and made into its own module, thus making the memory module more of a peer to the others.

Suffice to say, the modules are in a state of flux. As I add new routines, optimize old routines and move routines from one module to another, the assembled object sizes of the modules keeps changing. However, they have to be packed together in memory, such that the end of one module is followed by the start of another module. If they overlap the module lower in memory will overwrite the first part of the module higher in memory that's already loaded in. Thus corrupting it and leading to instant and hair-pulling crashes. If there is space left between the modules, well, then that's just wasted memory that can never be allocated, found or utilized.

In addition to the problem of packing the modules together in memory, the main system jump table also has to know where each module starts, so that it knows where to find the module's table of vectors through which to jump. If that weren't enough, there is also the issue that the jump table itself is in a state of flux. With the addition of the math module, I just added mul16 and div16 to the middle to the jump table. Thus, the modules that consume the exports from other modules have to know where in the jump table to find the routine.

Each of these issues has a solution that I worked out at the beginning of the year. But how these solutions work has proven to be quite laborious for me to upkeep.

In order to pack the modules, I have to know how big each is. So I start with the first, the one highest in memory, and assemble it to somewhere arbitrary. The assembler tells me the start and end address of the object code. (And hopefully I don't get any phase errors, which seem to be fairly easy to produce if you use a label prior to defining it.) I write down that size. Then I go to the next module, load it up, assemble it and record its size. I do this for all 10 (or so) modules.

Then I pull out my calculator, a hex/oct/bin/dec converting Casio my brother helpfully gave me for christmas many moons ago. And I start with the last address plus one, so $CFFF+1, or $D000. And subtract the size of the first module to find where it should start, and I write that down. From that address I subtract the size of the next module, and write down its start address. Repeat this for all the modules. Eventually I end up with a table like this:

Module size and start address table

You can see in the image of my notebook that as I work on the code, I have to recompute the sizes and start addresses when it comes time to test my work. Sometimes, such as in the top middle column (second set of size/start columns), I've only worked on a few modules, so I can leave the others alone and just recompute the offsets for the few I worked on. Still, this process is painstaking and boring, and prone to mistakes leading to nasty bugs.

After I've calculated and written down this table of start addresses, I have to go back to each module, open its main file and manually set the initial start address. (*= $ce34) for memory, for example. Then I have to reassemble this module to an object file.

The system Jump Table is another issue. The Jump Table needs to know where each of these modules starts, so I open that module and update a set of labels with these new start addresses. Each jmp is an indirect jump through a vector found at the start of the module + the offset to the routine. If the module exports 5 routines, then it starts with a 10-byte table of five 2-byte vectors. And the Jump Table correspondingly has 5 entries.

  JMP (input+0)
  JMP (input+2)
  JMP (input+4)
  JMP (input+6)
  JMP (input+8)

That sort of thing. So every time a module grows in size, not only does it have to be reassembled, but every module lower in memory shifts down and has to be reassembled too. And then the jump table has to be reassembled also.

This is a big pain. But, let's not forget about how a module that wants to call an exported routine from another module finds the entry in the jump table. Each module has a .h header file that defines labels for each routine, and sets them to the position within the jump table for the module's block of jumps, plus the 3-byte offset. Such as:

  readmouse = inputbase+0
  mouserc   = inputbase+3
  deqmouse  = inputbase+6
  readkcmd  = inputbase+9
  deqkcmd   = inputbase+12
  readkprnt = inputbase+15
  deqkprnt  = inputbase+18


Thus we have another file that needs to be updated. If a routine is added to a module that needs an entry in the system Jump Table, it will offset the jump table base address for preceding modules. They then need to have their header files updated… and any module that includes that .h file and calls one of those routines needs to be reassembled so they have the right jump table offsets.

Needless to say, it's easy to forget any of these many places that need to be updated. And it's hard to remember exactly which modules depend on which other modules. I end up having load the source code for each module and look through their includes to see if they include an affected header file.

I need a better way to work this, because the burden is so heavy that its discouraging me from wanting to work on the project. And it gets worse the more code I write and the more modules I add.

Finally, it occurred to me that all those calculations of offsets that I'm doing could actually be done by the assembler, if only it had some basic information:

  • How big is each module, and
  • How many routines does the module export

Instead of writing these numbers down on paper, I could put them all together into a header file to be included by everything that needs one of these numbers. Here's what it ended up looking like:

The modules.h header file, top The modules.h header file, bottom

The top half of the file declares all the variable data I need to provide, in one place. One label for each module (prefixed with x for exports), for how many routines are exported by the module. One label for each module (prefixed with y, because it's close to x), for the size of the assembled module. Unfortunately I still have to manually determine the size of a module, however this only needs to be calculated for the modules I'm working on, which need to be reassembled anyway.

The bottom half of the file is where all the magic happens. First, the highest thing in memory is the Jump Table. And as of just a few nights ago, this is no longer part of the memory module but is its own stand alone file. One label is defined for each module (prefixed with j for jump table). The start of the jump table entries for memory are $d000 (hardcoded as the last address + 1), minus the number of exports for this module times 3. Three because each jmp() takes three bytes.

This gives us a label jmemory that indicates where the jump table entries for memory begin. But this also becomes the relative start address for where the next module's jump table entries begin. Thus jinput starts at jmemory minus xinput*3. And so on, all the way through all the modules. These offset labels are computing automatically simply by adjusting the number of exports each module offers at the top of the file.

The memory module is now just a standard module, structurally the same as any of the others, with its own table of vectors to its exported routines. It's start address is going to be offset from the final (lowest in memory) jump table block. There is one label per module (prefixed with s for start address). The Jump Table itself is first module, but its start address is the same as whatever was the address the final jump table block. In this case it's jtoolkit simply because toolkit is the last module. Thus there is a label, sjumptbl that is set equal to jtoolkit. smemory, the start address for the memory module therefore is sjumptbl minus the size ymemory, the size of the memory module. And the next module starts from smemory minus its own size, and so on through the modules. Thus, modules.h is a central place where all the variable data goes, the size of each module and the count of its exports, and it produces a set of labels that are j- prefixed and s- prefixed for the start addresses of each module's jump table block and code, respectively.

How can this be used, now?

Each module includes modules.h. Then sets is own assemble address to its s-prefixed label. Toolkit for example includes modules.h and positions itself by declaring *= stoolkit.

Each module's .h header file declares the labels for its jump table entries as offsets from the start of its j- prefixed label. These declarations are always right and so the header files themselves don't need to be touched.

  readmouse = jinput+0
  mouserc   = jinput+3
  deqmouse  = jinput+6
  readkcmd  = jinput+9
  deqkcmd   = jinput+12
  readkprnt = jinput+15
  deqkprnt  = jinput+18


And lastly, you have the jump table itself. The actual jmp() instructions still need to be written, because Turbo Macro Pro (the native version) doesn't support the code generating pseudo labels that TMPx provides. But where those JMPs jump to is computed dynamically by the s- prefixed labels simply by including modules.h. Thus:

  JMP (sinput+0)
  JMP (sinput+2)
  JMP (sinput+4)
  JMP (sinput+6)
  JMP (sinput+8)
Module size and export count table

I still need to keep track of some things on paper. My table now looks like what is shown in the image above. But I don't have to make any of the intermediate calculations. And I don't have to enter any of those intermediate values manually across a myriad of files. I just update the modules.h file with the new modules' sizes and export counts. Then I update the jump table itself with the additional entries. And reassemble to object files everything that would be affected by the changes.

It's still quite a bit of work if I make changes to a module up high in memory that pushes the others below it to new start addresses. But, like my recursive backup script it saves a huge amount of effort and takes a big burden off my shoulders, so I can spend more time coding and less time worrying about how to fit things into memory.

There is one last interesting benefit that has popped up. If I decide I'm going to start working on the string module a lot, because I'm building out the set of routines for string editing and manipulation, ordinarily I'd be in a bit of a tough spot. string is 3rd highest in memory, with six or more modules below it. I'd hate to have to reassemble 7 modules(!) every time I make string a bit bigger.

Well, actually I don't have to. It's easy peasy in the modules.h file simply to move the string module to the bottom of the pile. Its jump table entries can stay where they are, although it would be handy to build out the entries in the jump table, even with placeholders for routines I know will be there soon. There is nothing inherently special about having string be the 3rd module instead of the 9th. It was just bothersome having to redo all the math.

Now that modules.h does all that math, it becomes trivial to rearrange the modules. If I know I'm going to work on a specific couple for a few days, I can just move them to the bottom of the pile at the start of my session, and all of a sudden the cycle time for testing them becomes very short again.

Just a quick update on toolkit. It has been the primary focus of the last month or so of work. I've put a lot of thought and a lot of code into it. However, it's still so in flux in my head that I haven't wanted to commit to writing anything about it yet. But soon. I've just recently worked out what I think will be a big score in making the drawing of views and clipping them to the insides of their bounds rect much more efficient and easier to program. As soon as I get a slightly better handle on how well that's going to work out, I plan to write my first blog post discussing the general architecture of the toolkit. Stay tuned.