I ended my last entry by saying “Now I just need to write the data back out to a new disk image and make sure it’s the same as the original.” Well, it turns out the support for writing to disks in my little .d64 library was not as complete as I remembered it being. Luckily I had a quiet, rainy weekend to round out this month’s Retrochallenge, so I had plenty of time to work through the missing bits.
I suppose this looks like a lot of NIH (Not Invented Here) waste of effort, and it probably is, but I find this kind of coding really relaxing – there’s just something calming about it that I can’t quite put my finger on.
My references for this work, by the way, start with the Commodore 1541-II Disk Drive User’s Guide, which gives a very terse description of the disk format. Why the 1541-II? It was just the copy I had most readily at hand; I don’t think the content’s meaningfully different from earlier versions. When I needed more detail or context than the User’s Guide provided, I’ve been using Inside Commodore DOS, by Richard Immers and Gerald Neufeld. It’s a very thorough description of the inner workings along with disassembly of the 1541 ROMs, and describes many of the shortcomings in the 1541 code (even if they were wrong about the @-replace bug).
Since my original use case for this code was reading, analyzing, and modifying data, apparently I never actually added a way to create a new, blank disk image. I actually thought about just copying a blank .d64 created somewhere else and embedding it in my executable, but that seemed kind of lazy even for something I’m only coding for my own use.
Instead, I tried to do it right, though I am making some simplifying assumptions. For example, we only create new disks in the standard 1541 35-track format, even though the .d64 spec mentions some alternative formats with additional tracks.
A freshly-formatted C64 disk is pretty simple. Each of the 35 tracks has a predefined number of sectors, and most of those are empty. The exceptions happen on track 18. Track 18, sector 0, contains the Block Allocation Map (BAM). Each track has a four-byte entry: the number of available blocks, followed by a 3-byte bitmap of the available sectors. Sectors that are available are set to 1, and sectors that are in use (or that don’t exist on a particular track) are set to 0. Not too difficult, but a little bit-twiddly.
The BAM is followed by a directory header, and the important things there are just filling in the disk name and a 2-byte “disk id”. Oh, and remembering to pad out the name with the correct character. You’re supposed to use “shift spaces” – ASCII 160 – to pad out the disk name (and file names, when we get to that).
The actual directory entries begin in track 18, sector 1. Of course, a freshly-formatted disk won’t have any files on it, so the block is mostly zeroes. However, Inside Commodore DOS suggests that the first two bytes should be 0x00 0xff, to correctly signal that there are no further blocks.
I already had code for allocating specific blocks, but if you’re writing regular files, what you actually need is code that’ll just find however many available blocks you need. That’s also pretty simple, of course – you can just loop through the BAM until you find a free block. The implementation isn’t the interesting part here; the interesting part is the policy.
When a 1541 is allocating blocks for a file, it does so in particular ways. For example, it doesn’t just give you adjacent blocks. It spaces them out a bit, with the idea that if the gap is just right it’ll be able to stream out one block just in time for the next one to be under the read-write heads, or something like that. Apparently, the behavior is to skip 10 blocks when writing files. However, when writing directory blocks, it only skips three blocks instead. I’m not entirely sure why.
There’s probably some additional trickery in there too – some tracks have an even number of blocks, so there must be some adjustment so the algorithm doesn’t get stuck in a loop where it isn’t seeing half the blocks on a track.
There’s also some policy regarding track selection. Track 18 is reserved for the directory, but there isn’t anything stopping my code from putting file data in a block on track 18, and no reason that wouldn’t work. Similarly, when choosing which tracks to put files on, it seems like the DOS works its way outward from track 18.
Since I’m writing the allocator, I can arrange things however I want. There’s an opportunity here for experimentation. If I really wanted to, I could test different layouts and find the ones that are optimal to reduce load times for my data. Honestly, that sounds pretty tedious (and I wrote my MS thesis on performance monitoring!) but it’s good to know the possibility is there if I need it.
Wrapping it up
So that’s that for Retrochallenge 2018/09. I spent the first half of the month working on assembly language optimization of my program’s draw routine. Then I got distracted and played video games for a few days – well, it happens. But in the end I did make some progress on tools to help build the game and update my data structures, and in the course of that I learned a bit more about how the 1541 disk drive worked. So, not a complete waste.
That said, there’s lots I didn’t get around to doing, and much much more that needs to be done. Who knows? Maybe some more progress will happen before the next Retrochallenge rolls around and I get a new chance to set goals and fall short of them 😉