The title screen uses a crude form of compression, which I'll call ZRLE (zero-run length encoding). It's a special-purpose compression scheme I came up with, to meet the following requirements: - Must be able to compress the Taipan title screen by at least 33% (66% compression ratio, where the decompress code is counted as part of the compressed file size). - Must be able to decompress in less than 250 bytes of 6502 asm code (2 single-density sectors on disk). - Must decompress title screen in less than 1/4 sec on the Atari. All 3 requirements are exceeded slightly: the screen is compressed at a 60% ratio, the decompressor is around 160 bytes of object code, and it runs in approximately 1/5 of a second. Things that are NOT requirements: it doesn't need to compress anything else well, just the title screen. It turns out that it works pretty well for bitmapped graphics like the Atari uses, or any kind of file that's likely to have large areas of all 0 bytes, but e.g. it can't compress an ASCII or ATASCII text file at all (because there are pretty much never any null bytes in a human-readable text file). Apologia: --------- I'm aware that cc65 has a zlib implementation, but it doesn't quite meet the requirements: it's slow, large (linking it adds 781 bytes to the executable size), and the best DEFLATE compression I could manage for my title screen was 2806 bytes (using 7z). Add to that the 781 bytes of zlib code and the other required libs for a C program, and I end up with something like a 65% compression ratio (since I'm counting the code size as part of the file size), and it takes 2/3 of a second to decompress. So, it meets one of my requirements, but not all of them. Which should not be taken as a criticism of cc65's zlib implementation: It's amazingly small, efficient, and easy to use. It's just that deflate is a general-purpose compression algorithm, and I thought I could do a better job with a purpose-built one... which I think I've done. I didn't know exomizer existed, before I started on my compression scheme. If I'd known, and if I'd tried it out, I probably would have just used it instead. It has a better compression ratio (55% for my title screen, including decomp code) and decompresses fast enough. Theory of operation: -------------------- Unlike real RLE, ZRLE only compresses runs of 0-bytes. Non-zero bytes are stored as-is, not compressed at all. Also unlike real RLE, ZRLE won't work on arbitrary input data. Why? ZRLE relies on some byte values being unused in the input. In other words, if the file contains every byte value 0 to 255, it can't be compressed with ZRLE. There needs to be at least one unused value per length of null run found in the file, because the unused values are used as markers telling the decoder how long each run of 0-bytes is. There is no "escape" byte in ZRLE, or any sort of block structure. Each byte is either a byte of pixels, or a marker indicating a run of 0-bytes. In other words, if the input looks like: 01 00 00 02 00 00 03 00 00 00 04 ...there are 2 lengths of zero-run: 2 and 3. The fact that there are two runs of length 2 doesn't affect the algorithm (in fact it helps the compression ratio). Here are the runs, illustrated in glorious ASCII art: 01 00 00 02 00 00 03 00 00 00 04 \___/ \___/ \______/ run of run of run of 2 zeroes 2 zeroes 3 zeroes For each length of zero-run found in the file, an otherwise-unused byte is assigned as a marker for that length. The above input might be encoded as: 01 05 02 05 03 06 04 ...where 05 represents a run of two zeroes, and 06 represents a run of three zeroes. This means there are no escape bytes, markers, or counts stored in the file. Each run of zero-bytes collapses into one byte of data, which we'll call a code value. All bytes that aren't code values, are just uncompressed data bytes, used as-is. If there aren't enough unused values, the encoder will fail, saying it's out of codes. But how can this be decoded? The encoder creates a table for the decoder to use, of course. The table is written to the file comptitle.s, along with the rest of the decoder code from comptitle.s.in. This means the decoder is specific to the encoded file, not general-purpose. If we weren't on such a limited system as the Atari 800, the table would be part of the output file, not the code (like the "dictionary" in a gzipped file, etc). Each byte value in the compressed data either represents itself (is a plain data value) or some number of consecutive zero bytes (is a code value). The table has an entry for each byte value 0-255 (conceptually anyway; see below), and if the byte value represents itself, the table entry will be zero. If it represents a zero-run, the table entry will be non-zero, and will be the number of bytes in the run. For a "run" of one zero-byte, the encoder doesn't bother to encode it as a run: a plain zero is stored in the output file instead. This doesn't affect the file size, but does save one encoded value. Here's the above example again: 01 00 00 02 00 00 03 00 00 00 04 It encoded to: 01 05 02 05 03 06 04 The table built into the decoder will look like: byte value | definition -----------+----------- 01 | 0 02 | 0 03 | 0 04 | 0 05 | 2 06 | 3 This tells the decoder that 01, 02, 03 represent themselves (they're copied from compressed input to decompressed output as-is)... the value 05 represents a run of 2 consecutive zeroes, and 06 represents a run of 3 zeroes. The decoder will look at the input (the compressed data), one byte at a time, and consult the table to decide what to do with each byte. "Output" here is the decompressed data, which you can think of as a list of bytes, which starts out empty. input| table lookup | | data | result | action | output after action is taken -----+--------------+-----------------+--------------------------------- 01 | 0 | append 01 | 01 | | | 05 | 2 | append 2 zeroes | 01 00 00 | | | 02 | 0 | append 02 | 01 00 00 02 | | | 05 | 2 | append 2 zeroes | 01 00 00 02 00 00 | | | 03 | 0 | append 03 | 01 00 00 02 00 00 03 | | | 06 | 3 | append 3 zeroes | 01 00 00 02 00 00 03 00 00 00 | | | 04 | 0 | append 04 | 01 00 00 02 00 00 03 00 00 00 04 As you can see, the final output after the last byte of data is read, matches the original input exactly. In this dumb example, it's pretty obvious that the encoded data plus the table size is bigger than the original input, so the "compression" is actually making it bigger. But it serves to illustrate, I hope. The table lookup values are stored as one byte, so a run of up to 255 consecutive zeroes can be stored as a single byte. A run of more than that could be stored as 2 or more runs in a row, but the current encoder just aborts if it encounters a run of 256 zeroes (Taipan doesn't need it so I didn't implement it). The astute reader will have noticed a that a table lookup result of 1, meaning a zero-run of length 1, is possible to encode, but useless (might as well just store the single zero as plain data), and including an entry in the table for 1 makes the table larger by one entry for no purpose. The actual encoder (see below) doesn't encode zero-runs of length 1, it just stores a 0 as-is. For Taipan, the title screen (newtitle.png) contains large black areas. A black pixel is a 0 bit. The title screen data ends up packed 8 pixels per byte (1 bit per pixel), so those black areas are represented by runs of consecutive zero bytes. Each row of pixels in the image has 256 bits, or 32 bytes. The bytes are arranged in consecutive order: the leftmost 8 visible pixels are the first byte of the first row... after enough bytes to fill up the row, the next byte in the file is the leftmost 8 pixels of the 2nd line, etc etc. The algorithm treats the input as a stream of bytes, and doesn't know nor care how they're arranged on the screen, but if you know how they're stored you can see that a black area at the right-hand end of one line is "joined" with a black area at the left-hand end of the next line, as far as the compression is concerned. Specifics: ---------- The original image newtitle.png is the authoritative source for the title screen that ends up being built into the game binary. Its resolution is 256x184 pixels. If this image is ever modified, the Makefile will cause all the stuff mentioned below to be rebuilt. First, a script called newtitle.pl reads the PNG image and creates an Atari loadable file called titledata.xex. It contains a 6-byte Atari header followed by the pixel data, one bit per pixel. The pixel data is 5888 bytes. Formerly, before the compression scheme was invented, titledata.xex was used as-is in creating the game binary taipan.xex. The compression code is written in Perl, in the file titlecomp.pl. It reads titledata.xex, applies the compression, and writes a file called comptitle.dat, containing the raw compressed data (minus the table definition). It also creates an assembly source file comptitle.s, containing the table definition and the rest of the decoding code. If you look at titlecomp.pl, you'll see it takes an optional argument, forcing it to use a particular byte value as the first code value. This number is determined by running the script repeatedly with different arguments, to find the one with the smallest table size. Wait, what do I mean by smallest table size? Well, I said the table contains one entry for each byte value 0 to 255... This isn't really true. Byte values less than 128 *always* represent themselves, so I don't bother storing them in the table. Also, the perl script knows the lowest and highest numbered code values, so it only emits the portion of the table between these two numbers (and modifies the code to not do a table lookup, if it's outside the range). If you can read 6502 assembly, looking at the code will make this much clearer. comptitle.s is then assembled, to create comptitle.xex. When comptitle.s is assembled, it includes the contents of comptitle.dat with an ".incbin", so the data ends up in comptitle.xex along with the table and decoder. This file contains 2 Atari binary load segments: the data + table + decoder, and an initialization segment telling the Atari to run the decoder subroutine immediately after loading. comptitle.xex ends up being the first part of the complete taipan.xex game binary, so after its init routine exits, the rest of the game continues to load. In particular, the next segment is another init routine that tells the Atari to actually display the decoded title screen data. Compression Ratio: ------------------ If we want to calculate the compression ratio, the size of comptitle.xex is the compressed file size, and the size of titledata.xex is the original file size: $ ls -l comptitle.xex titledata.xex -rw-r--r-- 1 urchlay users 3602 Jan 6 02:08 comptitle.xex -rw-r--r-- 1 urchlay users 5894 Jan 6 01:55 titledata.xex The percentage is: $ perl -e 'printf "%.1f\n", 3602/5894*100' 61.1 Actually, we have to do the calculations in disk sectors. A standard Atari floppy disk holds 125 data bytes per sector (or less, but we assume full sectors because that's how taipan.xex is generated). It's impossible to read less than a full sector from the drive. So titledata.xex is 48 sectors, and comptitle.xex is 29. What we really care about is loading time, not disk space: the title screen should be visible as soon as possible after the program starts loading (to give the user something to look at, while the huge bloated game code loads). Standard 810 or 1050 drives load around 10 sectors per second, we saved 19 sectors or around 2 seconds. The decompression takes 1/5 of a second, so it's a net gain.