Now that we’ve worked through the basic principles, let’s go through a worked example. I don’t work in BASIC much, but the largest program I’ve written that’s pure BASIC is a directory-editing program for disk images, weighing in at about 120 lines of code. It should serve to demonstrate the core principles.
When I was organizing some of my projects and other programs into disk images, I kept running into a host of minor irritations endemic to disk work on the C64. My initial list of goals was:
- The ability to reorder directory entries, including entries that didn’t refer to any files. You see, instead of storing directory entries as a linked list, CBM DOS stored as an array and when a file is created the first “empty” entry is used. That means that if you’ve deleted files, your newly created files appear seemingly randomly in the middle of the listing, instead of at the end. That’s super-annoying so I wanted to be able to move those gaps down to the end of the list.
- Undelete files.
- Hide files so that they existed on the disk but didn’t show up in directory listings.
- Create unloadable delimiter files that did exist in the directory listing, as dividers or headings.
Deletion and renaming were easily managed with ordinary disk commands, so I wasn’t as interested in those. I didn’t need a DOS shell or directory commander—I needed a program that would let me do things to the directory structure that the DOS didn’t provide as commands.
Now, as it turns out, that whole list can be boiled down to three operations:
- Exchange two entries in the directory listing.
- Alter the file type of a file in the directory listing.
- Optionally scan the directory structure and adjust the block allocation map to match it.
This gives us all the operations I want to perform. Any permutation can be built out of an exchange primitive. Deletion and undeletion involve changing the file type to or from “not a file” and then performing the scan for the block structure. Hiding files is accomplished by changing the file type to “not a file” and then not performing the scan, leaving its blocks protected and inaccessible. And delimiter files can be created from any other file by setting their file type to the special delimiter type.
The Initial Drafts
The basic implementation strategy falls out of the considerations above. To do reordering and file type manipulation, I would load all the disk blocks that hold the directory into memory, edit them in place, and then write them all back out at the end. The DOS provides a special “validate” command that does the directory structure scan and block allocation reconciliation. I would also add a “move slot A to slot B” command that performed repeated exchanges, to simplify moving gaps in the directory to the end of the list.
My first draft stored the directory blocks in a two-dimensional array of integers. One array dimension was the disk blocks, and the other was the bytes within them. This worked, and it was relatively simple to implement, working much like our sector-dumper program from last time did. However, it was impossibly slow; exchanging directory entries involved multiple loops that would copy values around, each executing dozens of times. If I wanted to get decent performance out, I’d need to write it in machine code, or create a completely external tool to handle it. Neither of these options appealed to me much.
I then set about trying to implement the core operations more efficiently, which in turn meant changing the data structures. The alterations were pretty drastic.
First, instead of reading and writing every single sector in track 18 (where the directories and allocation maps were stored), I would only read entries in the directory listing itself. These are arranged as a singly linked list. I created an array SN% that stored the order of tracks to write back and a variable NS for the actual number of sectors we read. I then created a parallel array D% to hold “dirty bits”—these all started as zeroes and got a 1 written to them if I ever altered anything in that relevant sector. At the end of the program, I would only need to write out those sectors that I actually changed. In the extreme this could result in me doing seventeen times less work.
That leaves the contents of the directory entries themselves. These were 30-byte data structures that my exchange-directory-entries routine would be copying back and forth as blocks. Instead of copying blocks of array entries back and forth, I kept each directory entry as a string and simply edited them or swapped references around as needed. These entries were stored in an array named DE$.
Finally, to keep myself honest, I added a couple of variables to check to see if I’d ever deleted or undeleted any files to remind me whether or not I should validate the disk.
All of these changes were a fairly significant rewrite. I did the implementation in C64List (which was also the initial import into Github, and while I made some basic efforts to make the code look nice when LISTed, I was pretty lackadaisical about it. Code flow jumped all over the place, modules were huge and all had differently-sized ranges of lines assigned to them. You couldn’t ever really type LIST with a line range and have any idea of what you would get.
So as written, in the modern era, with modern cross-development tools, this draft was basically fine. It would not have been fine in the 1980s. It would have been extremely difficult to understand or modify without printing out the entire source code and studying it as hardcopy.
So, before I do a walkthrough of the program itself, let’s fix that.
For the purposes of this project, I set the strictest set constraints that I’d commonly seen used in programs published with the intent of being typed in by the end user:
- The code will be organized into blocks, each of which is assigned one hundred line numbers. Block 0 is lines 0-99, block 1 is lines 100-199, and so on.
- Line 0 of each block (the line that is an even multiple of 100) will be a comment explaining what the block does.
- GOTO statements will only ever target locations within the same block.
- GOSUB statements will always target the beginning of a block and nowhere else.
- Blocks will be self-contained: any block you enter with GOSUB will be exited with RETURN. (The main program is a special case, and we’ll cover that below.)
- A reader should be able to type the code verbatim into a C64 without using input abbreviations or tricks. (The C64 line editor had a limit of 80 characters, but BASIC lines could be up to 255 characters long, and this limit wasn’t enforced until after all the keywords had been compressed to a single byte. Clever users could use special keyboard abbreviations to make lines that were over 80 bytes long when LISTed, or use program generators to produce lines that were much longer. This constraint demands that we structure the code so that this is never necessary.)
- A block will fit on the screen when LISTed. There needs to be room for both the intial comment and the reiterated BASIC prompt after the LIST completes.
I then added some additional structure that made sense for this program.
- Blocks would be further grouped into megablocks of ten blocks each. These would comprise related blocks that cooperated to perform some task.
- Megablock 0 would hold the main program and general utilities. Any GOSUB statement that called into a routine would either be calling a block in megablock 0, a block within their own megablock, or the first block in some other megablock (that is, an even multiple of 1000).
- Block 0 would be the entire main program. The only things it would do would be initialize globals and call into the other megablocks, and the last line in the block would be END. Blocks 1 through 9 would be reserved for general-purpose routines. (This was uncommon. Generally, 9 blocks wouldn’t be enough for your general purpose routines, and so a set of megablocks near the end of the program would be used for them. Likewise the main program would be kept near the end instead of the beginning. Extremely low-numbered blocks would hold routines that needed to run very quickly, taking advantage of the way backwards branches are faster at lower line numbers. Our directory editor is I/O bound basically all the time and doesn’t care about this.)
Of all of these restrictions, only the requirement that each block fit on a C64 screen when LISTed made my task harder. The others provided a structure that made the outlining and implementation simpler.
Structure is your friend. That’s not unique to BASIC, either.
Let’s take a walk through the final program.