Crazy Disk Encoding Schemes
Wow. I expected the details of the Macintosh floppy data encoding to be a bit complex, but this is worse than I expected. I think I finally understand it well enough to duplicate it, but I can’t explain why it does what it does. Maybe whoever extended Woz’s code from the Apple II was just in a bad mood.
I’ve been focusing my attention on how a single sector’s data is represented on the disk. Most of it is fairly easy to understand, once you’ve found a reference. Each sector consists of an address block and a data block. Between the blocks are $FF sync bytes. The address block begins with a specific header ($D5AA96, a sort of secret password for old Apple II hackers), then five encoded bytes containing the disk format, track number, sector number, and a checksum, and ends with a specific trailer sequence. The data block begins with a different header, then the sector number, the encoded sector data, and a trailer sequence.
It’s the “encoded data” step where things start to get tricky. Logical data bytes must be encoded into disk data bytes before being written to disk. This is due to physical limitations of the magnetic disk media: bytes with too many consecutive zero bits can not be stored reliably. Of the 256 possible bytes values, only 64 (or is it 67?) values can be stored on disk reliably, so the Mac encodes six bits of logical data at a time into one of the 64 “safe” disk byte values, in a process called 6-and-2 GCR encoding. There’s a 64-entry table in the Macintosh ROM for converting six bits of logical data into the corresponding disk byte, which was often called a nibble (even though it’s not 4 bits). When reading a sector, the process is applied in reverse.
All of this I more-or-less already knew before I began. I expected to find a routine somewhere in ROM that grabs three logical data bytes at a time (24 bits), and shifts out six bits at a time, using the GCR lookup table to produce four disk bytes. Once I found the disk sector write routine, it became clear it does more than that. My first hint was this French page about Apple II DOS 3.3, whose low-level disk format is very similar to the Mac’s. According to this page, data values aren’t used directly as indexes into the GCR table. Instead, each data byte is XOR’d with the previous byte, and the result is used as the index into the GCR table. Why? This is where I fail, because I have no idea why. It seems somehow related to checksumming the data, but it would be easier to use the data values as direct GCR table indexes, and then use the sum of all data values as a checksum.
An unexplained running XOR-based index is strange, but I could live with that if it were the only unexplained part. Unfortunately it seems that either the French page is incomplete, or else the Mac encoding method is more complex than Apple DOS 3.3 encoding. I’ve stared at the 68000 assembly code in the ROM routine for quite a while, as well as C re-implementations from MESS and from Ben Herrenschmidt, trying to grasp some kind of high-level purpose in it, but it just seems arbitrary to me.
Instead of XOR-ing each value with the previous one, it XOR’s each value with the sum of all previous values back to the beginning with a stride of three. For example, the 10th value is XOR’d with the sum of the 9th, 6th, 3rd, and 0th values. To facilitate this, three running sums are maintained for the values on the 0th, 1st, and 2nd stride. But wait, it’s more complicated than that. After every 3 logical bytes, the sum for stride 2 is rotated left one bit position, and the bit that’s rotated out is added into the 0th stride sum, and any overflow there is added into the 1st stride sum, whose overflow is added to the second. Or something like that. It’s all a little crazy.
Read 12 comments and join the conversation12 Comments so far
Leave a reply. For customer support issues, please use the Customer Support link instead of writing comments.
There’s a good description of the A2 GCR routines in “beneath apple dos” which can be found in PDF form online (I am on my phone with weak signal so unable to supply a good link but giyf)
That’s a good book, and the link is http://www.scribd.com/doc/200679/Beneath-Apple-DOS-By-Don-Worth-and-Pieter-Lechner. It contains similar info to the French web site. It does give a hint for the purpose of the XOR operation on the Apple II (it was necessary for computing the checksum efficiently while keeping up with the disk?), but not why the method was retained and extended to greater complexity on the Mac. I’ll just copy the logic, even if I don’t really understand why its done that way.
[…] the progress of the Plus Too project in detail, covering topics such as the classic Mac’s Crazy Disk Encoding Schemes, the 680000 CPU’s interleaved memory design, various Mac Toolbox Mysteries, an SD Card Floppy […]
The Copy II Plus book is also very good. I’m going to go see if I can find some samples of the Mac GCR code to compare to the Apple II since I don’t have any working physical disks to compare anymore yet I still have my old .NIB files from back in the day. I could have sworn that it was pretty simple with the exception of that God-awful table-building and checksum for each sector. The code looks awful because it’s made for real time and a tiny ROM. I also could have sworn that the Apple II used the same format! Maybe not… I don’t have the assembler source to an IIgs/IIe/IIc 3.5″ firmware handy. There was a world of difference between the 800K and 1.4M drives, though?
It was logical that they kept the same standards simply because a lot of the hardware in the early Macs was essentially stolen/shared/loaned to/from the Apple II family. And yes, Wozniak’s 5&3 encoding was a great hack from a hardware perspective. It prevented them needing another $600 in parts(and labor!!)!
First, kudos to your work – this is just amazing, and at the same time long overdue…
WRT the “interesting” iwm checksum algorithm, I felt your pain, and still remember it, when writing http://nxr.netbsd.org/source/xref/src/sys/arch/mac68k/obio/iwm.s – I ended up copying what .Sony does without getting why it does it like that. Since .Sony is very obviously hand-coded, you’d have to pick the author’s brain, I guess.
I recently got interested in the disk encoding also. I found two other resources: the first is the companion to Beneath Apple DOS, being called Beneath Apple PRODOS by the same authors. I found a link for it at http://www.apple-iigs.info/doc/fichiers/beneathprodos.pdf
The second, although in French, is helpful especially if you can run it through a web translator, at http://www.hackzapple.com/DISKII/DISKIITECH06E.HTM
Using these resources I wrote an Excel program that encodes the 256 bytes of data to the 343 bytes (342 plus 1 checksum), and then back again. You just need to get the data into one of three forms; either straight code without spaces/tabs/etc, or code with spaces, or code with commas. The spreadsheet will process any of the three.
If anyone is interested let me know via this forum since I’d prefer not to publish my email for spam fears. Or perhaps the moderator can figure a way…
Hi Frank,
it’s already 2 years ago you publish in this blog.
You spoke abou an exec-sheet that encodes the 256 bytes of data to the 343 bytes (342 plus 1 checksum), and then back again.
Is it possible to get this sheet?
Thank you so much
Regards
Boris
Hi Boris,
Well I’m over the spam fears I suppose! Email me at FandR76@aol.com
-Frank
Dusting off an old thread. Frank – I’ve enjoyed reading your blog and about the development of the FloppyEMU. Your description of the MAC’s “Crazy Encoding Routine” and the question regarding why it looks so bizarre intrigued me.
Thanks to a mention you made on a different post, I located the MAME emulator project on GitHub and studied the routine sony_nibblize35(…) from ap_dsk35.cpp and have come up with some guesses about why the MAC routine is the way it is.
Executive summary: It’s done for performance and to have processing times (clock cycles) for each data byte that are independent of the data value.
If you implement a simple ‘multi-precision’ 24-bit checksum using three 8-bit fields, you need to handle the carry. Depending on the value you’re adding in, sometimes there is no carry, sometimes one, sometimes two. Thus, the processing time is data dependent. Summing all 0s goes faster than all FFs. Unless you add delays to make all the processing equally slow…
Instead, a pseudo-checksum is created where only one add and one handling of carry is required for each input byte. This is done by adding the input bytes to different fields of the checksum (c3,c2,c1) in rotation, plus any carry that resulted from the previous field. If you look at the code, it shows three sets of nearly identical code.
What about the weird rotate of the ms-byte of the checksum? The processing for the c2 and c3 fields checks for a carry by simply seeing if the previous addition resulted in a value > FF and incrementing if true, but the processing for c1 uses a ROL of c3 (leaving c3 rotated) and then checks for CY set to decide to increment. Why the difference?
The rotate occurs at the top of the loop, which also means it temporally follows the jump that occurs at the bottom of the loop. My guess is that the writer originally planned to use the same carry handling as for the other fields of the checksum, but wound up using the rotate (and leaving the value rotated) as a somewhat desperate workaround to compensate for clock cycles used up by the jump.
At least that’s how it looks to me. Once you get a handle on the crazy checksum, the rest of the data and nibblization processing is pretty logical. I have a more detailed explanation and a commented version of the sony_nibbliz35(…) routine if interested.
Regards,
Tom S
mea culpa. Wrote “Frank” meant Steve!
@Tom S; I’d love to see that if possible, or indeed really any other low-level documentation on the Mac disk encoding. I’m fully au fait with the Apple II GCR, but clearly this is another set of non-obvious decisions again.
I’ve just added Woz GCR support to DiskBrowser. If you want to see a java version of the denibblizing routine, try https://github.com/dmolony/DiskBrowser/blob/master/src/com/bytezone/diskbrowser/nib/DiskReaderGCR.java