Commented Zelda III 02/FEBB decompression routine by Assassin (http://assassin17.brinkster.net/) 2005-10-24 and 2016-06-14 ================================================================================= (Output a number of bytes from a compressed input block, whose 24-bit address is held in Variable $C8, to an output block, whose 24-bit address is held in Variable $00. There are several types of compression supported. Basically, the sequence is: read a control byte (which holds the compression type and [part of] the quantity of bytes to output), output a sequence of bytes based on reading one or more input data bytes, then rinse and repeat until we get FFh as a control byte. Normally, the quantity of bytes to output (which I'll call N) MINUS 1 is held in bits 0-4 of the control byte, and the compression type is held in bits 5-7. The decompression scenarios are: Bits 5-7 of | control byte | Method --------------------+----------------------------------------------------------- 000b | No compression. Just copy N bytes from our input block | to our output block. --------------------+----------------------------------------------------------- 001b | Normal 1-byte RLE. Read a data byte from the input | block, and output it to the output block N times. --------------------+----------------------------------------------------------- 010b | 2-byte RLE. Read a 16-bit data word from the input | block, and output it to the output block N/2 times (as | N is still the BYTE count). Yes, this means we might | output the entire word 4 times, then just its bottom byte | 1 more time. --------------------+----------------------------------------------------------- 011b | Ascending 1-byte RLE. Read a data byte from the input | block, copy it to the output block. Then output it N-1 | more times to the output block, but incrementing it once | before each time. Ex: If N is 4 and the value in the | input block is 10, we'll output: 10, 11, 12, 13. Also, | note that the input value will wrap to 0 if it's | incremented when 255. --------------------+----------------------------------------------------------- 1JKb (where either | Clever stuff. Copy a sequence of bytes found elsewhere J or K or | (i.e. earlier) in our output block to the current both is zero) | position in that block. We read the next two bytes from | the input block, and use them as a 16-bit pointer to | earlier in our output block: the first one read is the | top half, and the second the bottom half. N is once | again the number of bytes to copy. --------------------+----------------------------------------------------------- 111b | Special case. Get our new compression type from bits 2-4 | of the control byte. Also, N-1 is no longer 5 bits, but | 10. Its bottom 8 bits are held in the next byte of the | input block, and its top 2 are held in bits 0-1 of the | control byte. Then proceed as normal, starting the input | stream or pointer thereto with the next read byte. What | if the new compression type's bits are also 111b? It'll | just go with the 1JKb method. :) -------------------------------------------------------------------------------- ) 02/FEBB: C2 10 REP #$10 (set 16-bit X and Y) 02/FEBD: A0 00 00 LDY #$0000 (start out pointing to beginning of output block) 02/FEC0: 20 5F FF JSR $FF5F (read value from input block, and advance input block pointer. the read value acts as our control byte.) 02/FEC3: C9 FF CMP #$FF (termination character?) 02/FEC5: D0 03 BNE $FECA (branch if we haven't reached end of block. otherwise, we'll exit.) 02/FEC7: E2 10 SEP #$10 (set 8-bit X and Y) 02/FEC9: 60 RTS 02/FECA: 85 CD STA $CD (save our control byte. it holds [part of] the # of data bytes to output, as well as our compression type.) 02/FECC: 29 E0 AND #$E0 02/FECE: C9 E0 CMP #$E0 02/FED0: F0 0A BEQ $FEDC (branch if top 3 bits are all set) 02/FED2: 48 PHA (save top 3 bits) 02/FED3: A5 CD LDA $CD 02/FED5: C2 20 REP #$20 02/FED7: 29 1F 00 AND #$001F (isolate quantity of bytes to output minus 1) 02/FEDA: 80 12 BRA $FEEE (Type 111b. This is a bit of a special case. Our "compression type" is in bits 2-4 rather than the typical bits 5-7. Our quantity of bytes to output minus 1 isn't a 5-bit value in bits 0-4 of $CD, but rather a 10-bit value. The bottom 8 bits are found in the next byte in the input block, and the top 2 bits are bits 0-1 of $CD.) 02/FEDC: A5 CD LDA $CD 02/FEDE: 0A ASL 02/FEDF: 0A ASL 02/FEE0: 0A ASL 02/FEE1: 29 E0 AND #$E0 (our "compression type" is in bits 2-4 rather than the typical bits 5-7) 02/FEE3: 48 PHA (save bits 2-4) 02/FEE4: A5 CD LDA $CD 02/FEE6: 29 03 AND #$03 (get top two bits of (output byte quantity - 1).) 02/FEE8: EB XBA (put it in top half of A) 02/FEE9: 20 5F FF JSR $FF5F (read value from input block; it's the bottom 8 bits of (output byte quantity - 1). advance input block pointer.) 02/FEEC: C2 20 REP #$20 (set 16-bit Accumulator) 02/FEEE: 1A INC (make quantity one higher than read value, since we'd never need to output zero bytes.) 02/FEEF: 85 CB STA $CB (save # of bytes to output.) 02/FEF1: E2 20 SEP #$20 02/FEF3: 68 PLA (restore top 3 bits, or bits 2-4. these bits are our compression type.) 02/FEF4: F0 16 BEQ $FF0C (branch if none of bits are set) 02/FEF6: 30 4A BMI $FF42 (branch if top bit is set) 02/FEF8: 0A ASL 02/FEF9: 10 20 BPL $FF1B (branch if second highest bit isn't set and third highest is) 02/FEFB: 0A ASL 02/FEFC: 10 2A BPL $FF28 (branch if third highest bit isn't set and second highest is) (Type 011b. This means we'll be outputting a sequence of ascending values, where $CB is length of that sequence.) 02/FEFE: 20 5F FF JSR $FF5F (read data value from input block, and advance input block pointer) 02/FF01: A6 CB LDX $CB (X = desired byte quantity to output) 02/FF03: 97 00 STA [$00],Y (save data value to output block) 02/FF05: 1A INC (add 1 to data value, as we're ascending) 02/FF06: C8 INY (advance to next position in output block) 02/FF07: CA DEX 02/FF08: D0 F9 BNE $FF03 (loop if we haven't output desired quantity yet) 02/FF0A: 80 B4 BRA $FEC0 (start over and do it all again, reading our next control byte) (Type 000b. $CB holds the # of plain old data bytes to output. There's no compression in this instance; we're just copying bytes.) 02/FF0C: 20 5F FF JSR $FF5F (read data value from input block, and advance input block pointer) 02/FF0F: 97 00 STA [$00],Y (copy data value to output block) 02/FF11: C8 INY (advance to next position in output block) 02/FF12: A6 CB LDX $CB (X = desired quantity of bytes to output) 02/FF14: CA DEX 02/FF15: 86 CB STX $CB (decrement # of bytes to output. why not replace these 3 instructions with "DEC $CB" ? $CB is a 16-bit value, but our accumulator is in 8-bit mode. so we must favor our 16-bit index registers.) 02/FF17: D0 F3 BNE $FF0C (loop if we haven't output the desired quantity yet) 02/FF19: 80 A5 BRA $FEC0 (start over and do it all again, reading our next control byte) (Type 001b. Basic RLE. Just output one data byte a # of times, where that quantity is held in $CB.) 02/FF1B: 20 5F FF JSR $FF5F (read data value from input block, and advance input block pointer) 02/FF1E: A6 CB LDX $CB (X = desired byte quantity to output) 02/FF20: 97 00 STA [$00],Y (save data value to output block) 02/FF22: C8 INY (advance to next position in output block) 02/FF23: CA DEX 02/FF24: D0 FA BNE $FF20 (loop if we haven't output this byte the desired # of times yet) 02/FF26: 80 98 BRA $FEC0 (start over and do it all again, reading our next control byte) (Type 010b. Word-sized RLE. Output one 16-bit data word a # of times, though $CB still holds the _byte_ count. This means we may end up outputting the word 4 times, then outputting its bottom byte an extra time.) 02/FF28: 20 5F FF JSR $FF5F (read data value [low byte] from input block, and advance input block pointer) 02/FF2B: EB XBA 02/FF2C: 20 5F FF JSR $FF5F (read data value [high byte] from input block, and advance input block pointer) 02/FF2F: A6 CB LDX $CB (read # of bytes to output) 02/FF31: EB XBA 02/FF32: 97 00 STA [$00],Y (output low byte of data word) 02/FF34: C8 INY (advance to next position in output block) 02/FF35: CA DEX (decrement # of bytes to output) 02/FF36: F0 07 BEQ $FF3F (if we've output the desired quantity, exit the loop.) 02/FF38: EB XBA (get high byte of data word) 02/FF39: 97 00 STA [$00],Y (output high byte of data word) 02/FF3B: C8 INY (advance to next position in output block) 02/FF3C: CA DEX (decrement # of bytes to output) 02/FF3D: D0 F2 BNE $FF31 (loop if we haven't output the desired quantity yet) 02/FF3F: 4C C0 FE JMP $FEC0 (start over and do it all again, reading our next control byte) (Type 1JKb [where either J or K or both is zero]. This isn't RLE, but instead we're outputting a sequence already found elsewhere [i.e. earlier] in our output block. $CB holds the byte size of that sequence.) 02/FF42: 20 5F FF JSR $FF5F (read value from input block; it's the high byte of a pointer to somewhere in our output block. advance input block pointer.) 02/FF45: EB XBA 02/FF46: 20 5F FF JSR $FF5F (read value from input block; it's the low byte of a pointer to somewhere in our output block. advance input block pointer.) 02/FF49: AA TAX (X = 16-bit pointer to elsewhere [i.e. earlier] in output block) 02/FF4A: 5A PHY (save Y, which is our current writing position in the output block) 02/FF4B: 9B TXY 02/FF4C: B7 00 LDA [$00],Y (load data byte from earlier in output block) 02/FF4E: BB TYX (X = X? brilliant.) 02/FF4F: 7A PLY (restore pointer to current position in output block) 02/FF50: 97 00 STA [$00],Y (now save the data byte there) 02/FF52: C8 INY (advance Y to next writing position in output block) 02/FF53: E8 INX (advance X to next reading position in output block) 02/FF54: C2 20 REP #$20 02/FF56: C6 CB DEC $CB (decrement # of bytes to output) 02/FF58: E2 20 SEP #$20 02/FF5A: D0 EE BNE $FF4A (loop if we haven't output the desired quantity yet) 02/FF5C: 4C C0 FE JMP $FEC0 (start over and do it all again, reading our next control byte) (Read value from input block, and advance input block pointer) 02/FF5F: A7 C8 LDA [$C8] (read value from input block. $CA holds the bank to read from, and $C8 - $C9 hold the offset) 02/FF61: A6 C8 LDX $C8 (get input block pointer) 02/FF63: E8 INX (increment it) 02/FF64: D0 05 BNE $FF6B (branch if we haven't reached end of input block) 02/FF66: A2 00 80 LDX #$8000 (if we have, move our 3-byte pointer to the start...) 02/FF69: E6 CA INC $CA (...of the next ROM bank) 02/FF6B: 86 C8 STX $C8 (save new input block pointer) 02/FF6D: 60 RTS