Understanding the Decompression Routine from a SNES Game

Question

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:

1. What is the specific format of the decompression? How is the data structured and how does it get decompressed?
2. What is the role of memory address 44?
3. What are the purposes of the bit shifts and rotates in this routine?

Any insights or guidance would be greatly appreciated. Thank you in advance!

Here is some compressed and uncompressed data.

Answer 1

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!