UPDATE 1: I no longer think it is run-length-encoding and I now have no idea what it could possibly be.
I'm currently working on a project that involves dissecting the assembly code of the SNES game Jurassic Park. Specifically, I'm focusing on a decompression routine that seems to use a form of run length encoding. I have been able to understand and add comments to most of it. However, I'm having difficulty understanding the exact decompression format and the role of certain memory addresses and operations.
Here's the relevant portion of the assembly code:
; The y regsiter contains the address of the decompressed data
; What are memory addresses $44, $48 used for
; Memory address $46 seems to be used to hold how many bytes to transfer in the MVN opperation
; Memory address $48 seems to be used to hold how far away the source address is from the destination address
; I am still trying to figure out what the bit shifts and rotates are for
CODE_81B18B:
STX.b $40 ; Address of the compressed data
STA.b $42 ; Bank of the compressed data
; Figured out what it does. It sets the data bank to 7F without chaning the processor status
; The reason this is done is because of the MVN opperation that is done later
; The exact same thing can be done with
; SEP.b #$20
; PHB
; LDA #$7F
; PHA
; PLB
; REP #$20
PHB
LDA.w #$7F7F
PHA
PLB
PLB
; Intialize the loop condition
LDA.w #$8000 ; Why 0x8000?
BRA CODE_81B1B6 ; Branch always. This litteraly just jumps to CODE_81B1B6
CODE_81B19B:
LDX.w #$0100
STX.b $44
CODE_81B1A0:
ASL
BNE.b CODE_81B1AA ; Loop 1.1.1
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B1AA:
ROL.b $44
BCC.b CODE_81B1A0 ; Loop 1.1.2 Exit the loop when rotating the data to the left causes a carry
; Store the decompressed byte to the output
TAX
LDA.b $44
STA.w $0000,y ; Store decompressed data
INY
TXA
CODE_81B1B6: ; Start of the first part of the decompression loop
ASL
; This detects when the data has been decompressed
BNE.b CODE_81B1C0
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B1C0:
BCC.b CODE_81B19B
ASL
BNE.b CODE_81B1CC
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B1CC:
BCS.b CODE_81B1D5
LDX.w #$0000
STX.b $46 ; Set the number of bytes to transfer to 0
BRA.b CODE_81B208
; The below code figures out how many bytes to repeat
; And the range of bytes to repeat
CODE_81B1D5: ; Start of the second part of the decompression if certain conditions are met
LDX.w #$2000
STX.b $46 ; Set the number of bytes to transfer to 0x2000
CODE_81B1DA:
ASL
BNE.b CODE_81B1E4 ; Once a is 0 or 46 is 0 then do the following instructions: Loop 2.1.1
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B1E4: ; Start of the second part of the decompression loop
ROL.b $46
BCC.b CODE_81B1DA ; Repeat until $46 is 0: Loop 2.1.2
BNE.b CODE_81B208 ; Decompress the encoded data
LDX.w #$0100
STX.b $46
CODE_81B1EF:
ASL
BNE.b CODE_81B1F9 ; Once a is 0 or 46 is 0 then do the following instructions: Loop 2.2.1
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B1F9:
ROL.b $46
BCC.b CODE_81B1EF ; Repeat until $46 is 0: Loop 2.2.2
BEQ.b CODE_81B22A ; If a is 0 then we have successfully decompressed the data and we can exit the routine
; If not then we got ahead and Decompress the encoded data
TAX
LDA.w #$0006 ; Add 6 to the number of bytes to transfer ????
ADC.b $46
STA.b $46
TXA
CODE_81B208:
LDX.w #$0040
STX.b $48
CODE_81B20D:
ASL
BNE.b CODE_81B217 ; Not sure what this does
LDA.b [$40] ; Load compressed data
INC.b $40
INC.b $40
ROL
CODE_81B217:
; This is the core of the decompression routine.
; It uses the MVN data to repeat data
; $46 contains the number of bytes to transfer.
; X contains the high and low bytes of the source address
; Y contains the high and low bytes of the destination address
ROL.b $48
BCC.b CODE_81B20D
PHA ; Save the a register
TYA ; Put the destination address in the a register
SBC.b $48
DEC
TAX ; Calculate the source address
LDA.b $46
INC ; Add one to the number of bytes to transfer
MVN $7F,$7F
PLA ; Restore the a register to its original value
BRA.b CODE_81B1B6 ; Enter another loop of the decompression routine
CODE_81B22A:
PLB
RTL
My main questions are:
Any insights or guidance would be greatly appreciated. Thank you in advance!
Here is some compressed and uncompressed data.
What I can glean from the code is that it is an LZ77 compressor, where the compressed data starts with a bit indicating a literal (0) or a match (1).
If it's a literal, then get eight bits for that literal and write it out.
If it's a match, then get one more bit to indicate a length of 2 (0), or more than 2 (1). If it's not length 2, then get three bits for the length. If that's zero, then get eight more bits. If that's zero as well, then the compressed data has terminated. Add 2 to the three-bit length or 9 to the eight-bit length. That's the length of the match, in the range 2..264.
Now get 10 bits for the distance, to which one is added. The distance is then in the range 1..1024.
Finally copy length bytes from distance back. Then start over with one bit to indicate a literal or a match. Note that the source and destination may overlap, i.e., the length may be greater than the distance. The copy must be made with increasing indices, which in the case of an overlap will replicate sequences of bytes whose length is distance. For example, the specific case of a distance of 1 and length greater than 1 is a run of the same byte with the given length — a run-length encoding.
(Side note for C/C++ programmers: you cannot use memmove() or memcpy() for this. memmove() is guaranteed to not do it this way, and memcpy() may or may not. Just write a loop and the optimizer will take care of it for you.)
The 16-bit values at $44, $46, and $48 are the literal, length, and distance as they are being constructed, bit by bit. The rotates and shifts are the extractions of sequences of 1, 8, 3, or 10 bits from the input.
The bits are pulled starting from the most significant bit of each little-endian 16-bit value from the input. Note that then the first bit of input comes from the high bit of the second byte!