I've explained how to decode the compressed screen data of the screens of a level. What I didn't mention back then was how the game itself actually decompresses that data. That's what this update is all about and I have to admit that the decompression code of the original game is better than the one I wrote. To my defence I want to mention that the original code uses nice tricks with the carry flag which wouldn't have been easy to use in my C++ code.
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.
CODE:
<br />$D1F6-> C9 FF: CMP #$FF ; If A is $FF ...
<br />$D1F8-> F0 F1: BEQ $D1EB ; ... call the third part
<br />$D1FA-> A: ASL A
<br />$D1FB-> A8: TAY
<br />$D1FC-> B1 7A: LDA ($7A),Y ; Lower byte of screen pointer
<br />$D1FE-> 85 8: STA $8
<br />$D200-> C8: INY
<br />$D201-> B1 7A: LDA ($7A),Y ; Upper byte of screen pointer
<br />$D203-> 18: CLC
<br />$D204-> 69 80: ADC #$80 ; Adjust address
<br />
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.
CODE:
<br />$D206-> 85 9: STA $9
<br />$D208-> A9 0: LDA #$0
<br />$D20A-> 85 5E: STA $5E ; $5E = Current byte
<br />$D20C-> 85 5D: STA $5D ; $5D = Current block
<br />$D20E-> 85 5F: STA $5F ; $5F = Current bit
<br />
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.
CODE:
<br />$D210-> A9 0: LDA #$0
<br />$D212-> 85 5C: STA $5C ; $5C = Bit buffer
<br />$D214-> 20 58 D2: JSR $D258 ; Load next bit
<br />$D217-> 26 5C: ROL $5C ; Add bit to bit buffer
<br />$D219-> 20 58 D2: JSR $D258 ; Load next bit
<br />$D21C-> 26 5C: ROL $5C ; Add bit to bit buffer
<br />$D21E-> A5 5C: LDA $5C
<br />$D220-> 29 3: AND #$3
<br />$D222-> AA: TAX
<br />$D223-> E0 3: CPX #$3 ; If the buffer is 3
<br />$D225-> F0 D: BEQ $D234 ; A new block was found
<br />$D227-> A5 5D: LDA $5D ; Load current block index
<br />$D229-> 18: CLC
<br />$D22A-> 7D 73 D2: ADC $D273,X ; Address block to copy
<br />$D22D-> AA: TAX
<br />$D22E-> BD 0 6: LDA $600,X ; Value of block to copy
<br />$D231-> 4C 44 D2: JMP $D244 ; Store block
<br />
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.
CODE:
<br />$D234-> A2 8: LDX #$8 ; Bit counter
<br />$D236-> A9 0: LDA #$0
<br />$D238-> 85 5C: STA $5C ; Reset bit buffer
<br />$D23A-> 20 58 D2: JSR $D258 ; Load next bit
<br />$D23D-> 26 5C: ROL $5C ; Add bit to bit buffer
<br />$D23F-> CA: DEX ; Decrease bit counter
<br />$D240-> D0 F8: BNE $D23A
<br />$D242-> A5 5C: LDA $5C ; Load value of new block
<br />
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.
CODE:
<br />$D244-> A6 5D: LDX $5D ; Block index
<br />$D246-> 9D 0 6: STA $600,X ; Write to array
<br />$D249-> E6 5D: INC $5D ; Next block
<br />$D24B-> D0 C3: BNE $D210 ; More blocks to decompress
<br />
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.
CODE:
<br />$D24D-> A2 F0: LDX #$F0
<br />$D24F-> A9 0: LDA #$0
<br />
<br />$D251-> 9D 0 6: STA $600,X
<br />$D254-> E8: INX
<br />$D255-> D0 FA: BNE $D251
<br />$D257-> 60: RTS
<br />
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.
CODE:
<br />$9258-> A5 5F: LDA $5F ; Load bit index
<br />$925A-> D0 6: BNE $9262 ; Bits left in current byte
<br />$925C-> A4 5E: LDY $5E ; Load next byte
<br />$925E-> B1 8: LDA ($8 ),Y ; Load value of next byte
<br />$9260-> 85 60: STA $60 ; Value of current byte
<br />$9262-> 6 60: ASL $60 ; Get the next bit
<br />$9264-> 8: PHP ; Store flags
<br />$9265-> E6 5F: INC $5F ; Next bit
<br />$9267-> A5 5F: LDA $5F
<br />$9269-> 29 7: AND #$7 ; Enforce values 0 - 7
<br />$926B-> D0 4: BNE $9271 ; 8 bits not yet read
<br />$926D-> 85 5F: STA $5F ; Reset bit index to 0
<br />$926F-> E6 5E: INC $5E ; Next byte
<br />$9271-> 28: PLP ; Load flags
<br />$9272-> 60: RTS
<br />