Faxanadu internals - The screen data decompression algorithm

The decompression code from the original game comes in three parts. The first part ($D1F6 - $D257) is the actual decompression code that translates the compressed data into an array of block values. The second part ($D258 - $D272) is a helper function to extract the next bit from the compressed data. The third part ($D1EB - $D1F5) overwrites the entire uncompressed block array with bytes of value $00. Due to it's simplicity I'm not going to discuss the third part.

Let's start with the first part, the actual decompression function.

In the first few lines of code the position of the compressed data is looked up from the chunk data of the current level. As the position is stored relative to the beginning of the chunk data, $80 is added to convert the relative address to an absolute address.



After the compressed data was found, the buffers used for decompression are initialized. Let's recall that the decompressed data is read bit for bit. $5E serves as an index into the compressed data to the byte the next bit will be extracted from. $5F keeps track of how many bits were already read from the current byte. $5D is an index into the decompressed data, it counts how many blocks were already decompressed succesfully.



Then the actual decompression begins. The next two bits of the compressed data are read into the bit buffer and depending on their value the value of an earlier block is copied ($00, $01 or $02) or an entirely new block is extracted from the compressed data ($03). The array at offset $D273 which is used to address the block to copy contains the three values $FF (-1), $F0 (-16) and $EF (-17). These values are added to the index of the current block to find the index of the block to copy.



If the value of the first two bits is three a new block needs to be extracted from the compressed data. The next eight bits in the compressed data hold the value of this block.



No matter if the value of the next block was copied from an earlier block or if the new block was extracted from the compressed data, at this point the value of the next block is known and it can be written to the correct position in the array that contains the uncompressed data.



The very last part of the function overwrites the last line of the uncompressed data with bytes of value $00 because that last line is not used when displaying screens.



Let's have a look at the second part now, the function which extracts a single bit from the compressed data. Depending on the value of the bit index a new byte is loaded or not. Afterwards the next bit is shifted out of the current byte and into the carry flag. At the end the byte index is incremented if necessary.