Maximizing Compression of Apple II Hi-Res Images

Summary

Maximizing Compression of Apple II Hi-res Images I have the somewhat niche problem of trying to fit as many Apple II hi-res images into RAM (and disk) at a time. Uncompressed these images are 8k (well, you can get away with 8184 bytes without any trouble for reasons we'll discuss later). Background I won't go too much into the wacky world of Apple II hi-res graphics, you can read more on that here. For our purposes the important part is that you can think of it as a 280x192 monochrome image with 7-bits per byte that typically is used to generate NTSC artifact color (the top bit shifts the pixel slightly to essentially choose another palette, blue/orange vs purple/green). You might think 280x192 at 7bpp should result in a 40 byte by 192 image fitting nicely in a linear 7.5k. Alas, no, and you can probably blame Woz for this. The graphics avoid crossing page boundaries so there are "holes" in the memory map. After each three rows (120 bytes) 8 bytes are left unused to pad things out to a nice power of 2. The final issue is that complex interleaving goes on so rows are not contiguous in memory. This is for various reasons, possibly to save a few chips on the motherboard. (In addition the addresses are all over the place on the actual RAM chips to make for "free" DRAM refreshes but you can only see that if you're logic-probing the address lines). A brief summary of the interlacing, in PAGE1 of hi-res memory starting at $2000 (on 6502 processors you use $ to indicate hexadecimal) you have something like this: $2000: Row 0, Row 64, Row 128, 8-bytes padding $2080: Row 8, Row 72, Row 136, 8 bytes padding ... and after 1k of this, you then start over with $2400: Row 1, Row 65, Row 129, 8 bytes padding ... $3F80: Row 63, Row 127, Row 191, 8 bytes padding This leads to the "Venetian blind" effect often seen when loading HGR graphics linearly. Compression I won't go into too many details here, there are a lot of 6502 compression algorithms that have various tradeoffs between co...