NEWS, EDITORIALS, REFERENCE

Pointers in Practice, Menus

Believe it or not, I've just gotten to the point in my development, maybe a week or two ago, where I am able to load in and parse the menu description files. I wrote this code a few months ago and even wrote a whole post series here about recursion and pointers. The primary examples for describing recursion and pointers was the ability to parse and build a set of linked menu structures.

I found a few small bugs in the sample code I included in those posts. But nothing too egregious. I used the wrong pointer variable at one critical spot which failed to null terminate the menu's string label properly. Then searching for its length and setting the pointer to its code bytes was out of whack. But besides that, the actual process of recursion works remarkably as it was intended to. It's my guilty pleasure to write a whole bunch of code without testing it much and then later test it out and find it has almost no bugs.

Seeing the data sitting there correctly laid out in my machine language monitor is a real rush. I'm actually doing it! If I can write a recursive file parser in 6502, it means I can actually write code in 6502. Feels good.

The Data Structures

Just as a quick recap, the data structure for a menu node was very simple. Each struct is 8 bytes, made up of four 16-bit pointers. The first pointer is to the next sibling node, the second pointer is to this node's first child (or $0000 aka "null" if this node has no children.) The third pointer is to the null terminated string label. And the fourth pointer is to a struct for "codes." Depending on which type of node this is, the code struct has a slightly varying format. However, those code structs contain just single bytes. For example, a key modifier flags byte, a petscii value to activate with a keyboard command, an "action" byte which is sent to the application's action dispatch routine for processing. Etc. You can read back into those previous posts for a more full description of these.

The goal of the menu description file to be parsed is that it be, A) Human readable / human editable. B) Almost an exact byte layout for what gets loaded into memory. C) Easily parsable while supporting unlimited menu nesting. Here's what the file looks like that these examples are parsing.

Excuse the quality of the screencaptures. I got them by taking photographs of a my actual CRT monitor. It's hard to avoid capturing those diagonal refresh stripes. Here you can see that I'm in the root (or boot) folder of C64 OS. And I've used the JiffyDos @t command to preview a SEQ text file. Also kinda neat here is that I'm using a relative path from the current folder into the "services" folder and then into the "app launcher" folder. And finally, the file name following the colon is menu.m.

Each row starts with the menu label. The label terminates either with ":" or ";" (colon or semi-colon.) The semi-colon indicates this row is a menu header which will have child rows. The full colon means this is a leaf node. The first byte after the header node's semi-colon indicates how many immediate children this header contains. The recursion depends on this to parse the file correctly.

After loading and parsing this file (or a slight variant of it,) and inspecting memory with my trusty machine language monitor1, we get the following very exciting pattern pop up in memory starting at at $ad00.

I tried hard to get my menu structs to be a nice round number that would divide evenly into a 256-byte memory page. 8 bytes worked brilliantly. 4 pointers, and exactly 32 structs fit in a page. What I wasn't anticipating was how great it would look in a standard ML monitor. As it happens the monitor has enough horizontal space to show the address in the first column, then a row of 8 bytes, and then on the right the Petscii version of those 8 bytes of data.

What that means is that you get exactly one menu struct per row! Two examples of which you see outlined above in red. Note that this data starts at $ad00. That's because the paged memory manager asked for a page into which to load the text source itself, and was assigned $ae00-$aeff. The page requested for the menu structs got $ad00-$adff. So, it seems the memory manager is also working as expected, yay!

The next neat effect of each struct fitting in a row is that vertically, the offsets of the struct pointers are aligned. Each two byte pair makes up a pointer, in little endian byte order remember, so the hi byte comes second. Each set of pointers, in four columns, I've circled in yellow. The first and second columns are for "next sibling" and "first child" respectively. And you can see very easily that the hi bytes of all the pointers in these first two columns are always $ad. That's because they always point to nodes that exist elsewhere inside this page ($adXX) allocated specifically for these menu structs. If the menu file had contained more than 32 menu nodes, then more than one page would have been allocated and somewhere along the way these pointers might point to somewhere outside $ad, but in this small example they do not. Which is cool, because it makes it easier to see what's going on.

Similarly, you can see very easily that the hi byte (second byte) in all the pairs in the last two columns is always $ae. That's because these two pointers point back into the original source file to strings and code bytes, respectively.

This next screenshot shows how the sibling and child pointers link the menu structs together in a recursive hierarchy.

There is something beautiful about structured data. The red boxes outline a "next sibling" pointer with an arrow leading to another red box that is the address pointed to. So, the struct at $ad00 has a next sibling at $ad30, which has a next sibling at $ad58. But you'll notice that the first two bytes at $ad58 are 00 00. That's a null pointer, and that indicates that this node has no next sibling. $ad58 is the last menu entry in this menu level (the top menu bar, in this case.)

The green boxes outline the "first child" pointer. And then the green arrow leads from that pointer to the address it points to. Once you're at an entry, such as the one at $ad08, it is structured the same as any other. Its first two bytes point to its next sibling, but it itself has no children. There was a limit to how many boxes and arrows I could draw on the screenshot without making it too complex. But if you follow the pointers with your eyes you can see how they are arranged. Pretty cool!

The next screenshots show how the menu structs use their label and code pointers to refer into the (slightly modified at parse-time) source data.

Once again, there are only so many boxes with pointing arrows I can draw on the screenshots before it would get completely crazy. I've taken 3 samples at random but you can use your eyes to see for yourself how they line up. The red boxes from the screenshot on the left (within $adXX) point to the menu label string in $aeXX on the right. The green boxes on the left outline the code struct pointers, and point to where that data begins within $aeXX on the right.

If you look at where any code struct begins (the green boxes on the right), you'll notice that the byte to its immediate left is always $00. That's the null terminating byte of the label string that precedes the menu entry's codes. A keen reader may have noticed that those null bytes appear in the middle of where the source file was loaded. But the source file itself, on disk, does not contain any $00 bytes. That's because $00 is not human typable into a text editor. During the parsing stage, when the parser encounters either a ";" or ":" at the end of a label, it uses that to determine if the row represents a header or a regular menu entry. But before it proceeds with processing that row appropriately for its type, it replaces that byte with a $00 in memory which serves to null terminate the label string. From the pointer to the start of the label, which gets put into the structs in $adXX seen on the right side screenshot, the code can later run a strlen to get the width of the menu label. That works because strlen expects that the string stops when it finds a $00 byte.

Lastly, I decided to take a picture of the hierarchy of pointers that I drew out by hand on paper to confirm that the topography of the graph is correct and matches the intentions of the source menu description file.

The sibling nodes belonging to a single menu "level" are shown going across with arrows going to the next sibling. The start addresses of each of these is written out in full. The down arrows point from a node to its first child, if it has one. Beneath each $adXX address are two little subscript numbers. These are the lo bytes only for the pointers into $aeXX. I confirmed for myself that all of these pointers are correct. From this drawing, you can see the intention of this menu description file is for a top level menu with three entries. Under the first menu is a submenu with three entries. Under the second top level menu is a submenu with 4 entries. Under the third top level menu is another submenu with 4 entries.

You may notice that in some of the subscripts instead of a number there is a little dash. For example, the second entries in the first and second submenus. And the 3rd entry in the 3rd submenu. Those are null code pointers. That's because, if you look back at the original source file, those entries were just an asterisk (*). These don't have "codes" as they are just spacers, dividers that will get rendered in the menus onscreen to help the visual layout.

But is it recursive?

That pretty much sums up what I wanted to show and talk about in this post. I'm pretty pleased with it so far. I can't wait to get into the rendering code, it's gonna be fun!

The only other thing I wanted to say is that with a menu that is just two levels deep, one top menu bar where each drops down one submenu, do you really need recursion at all? Well, that was just the depth I'd used on my sample input file. To prove to myself (and to you) that it really is recursive, and how easy it is to add more depth to the source file, I quickly whacked out an extra line or two in the source file to create a 3rd menu level.

I took a screenshot of the menu struct hierarchy in $adXX after parsing this file. But I will leave it as an exercise to the curious and adventuresome reader to follow the links shown below to see how the hierarchy has been extended to a third level of menu depth. In practice the C64 would run out of memory before hitting any other limitation on how deeply the menus can be nested. That's pretty damn cool!

Thanks everyone. Stay tuned. My next post will be a bit different for this site. I'm going to be posting my review of the excellent C64 Fanzine Freeze64.

1. Supermon+64, by Jim Butterfield. But the version I use has been explicitly assembled to load in at like $8000 or $9000 so it doesn't interfere with C64 OS's KERNAL, nor with the first several pages the memory manager hands out. [↩]