Help with a tilemap decompression routine

[Pennywise]

This is too big to post, so I'll do a link. The game and data in question is the title screen of Jesus for the NES, so if more context is needed you can easily fire up the game and check it out. Anyway the game uses some weird form of RLE that completely boggles my mind and I find the code to be really hard to follow. I might end up coding another routine that just loads the data uncompressed, but I'd love to figure out this routine and possibly recompress the new data back in. If anything, it would be smaller in size than the original. Then there's the issue of the actual tiles which seem to be stored in some weird format or are compressed as well, but it's been a while since I've looked at that and will check it out later again. Anyhow, I made a few comments, but the majority of this stuff seems convoluted to me.

http://yojimbo.eludevisibility.org/Stuff/title%20screen%20tilemap%20decomp.txt

[rveach]

From what I see:

FA88 to FAA1, is the main decompression. the subroutine FBAC seems like your main controller of the routine. $15 seems like a constant that comes from 0xE9D1 in the ROM. So it does 13h passes at a time.
FAA6 to FAC6, sets up your memory transfer. $27/$28 is your source address, $29/$2A is your stop memory address.
FE85 to FE9C, is the copy routine to ppu.

Here is all your code to the controller:

Code Select Expand

FBAC A6 4C LDX $4C x = $4C
FBAE D0 10 BNE $FBC0 BRANCH IF NOT 0
FBB0 20 D8 FB    JSR $FBD8
FBB3 90 15 BCC $FBCA
FBB5 20 CA FB    JSR $FBCA
FBB8 85 4B STA $4B
FBBA 20 C6 FB    JSR $FBC6
FBBD AA TAX
FBBE E8 INX
FBBF E8 INX
FBC0 CA DEX x--
FBC1 86 4C STX $4C $4C = X
FBC3 A5 4B LDA $4B A = $4B
FBC5 60 RTS

FBC6 A0 03 LDY #$03
FBC8 D0 02 BNE $FBCC always jump to FBCC
FBCA A0 08 LDY #$08
FBCC A9 00 LDA #$00
FBCE 48 PHA
FBCF 20 D8 FB    JSR $FBD8
FBD2 68 PLA
FBD3 2A ROL A
FBD4 88 DEY
FBD5 D0 F7 BNE $FBCE
FBD7 60 RTS

FBD8 AD 4A 00    LDA $004A
FBDB D0 12 BNE $FBEF
FBDD A2 47 LDX #$47
FBDF A1 00 LDA ($00,X)
FBE1 F6 00 INC $00,X
FBE3 D0 02 BNE $FBE7
FBE5 F6 01 INC $01,X
FBE7 8D 49 00    STA $0049
FBEA A9 08 LDA #$08
FBEC 8D 4A 00    STA $004A
FBEF CE 4A 00    DEC $004A
FBF2 0E 49 00    ASL $0049
FBF5 60 RTS = $FBB3

Its late, so I'm not going to look at it right now, but it may not be too complex.

Edit:
It seems FBDF is your ROM read address, which is stored in memory $47/$48 which is populated in execution from CA0E to CA17.  So that is where your tiles are stored.

Code Select Expand

CA0E BD 00 80    LDA $8000,X @ $800E = #BF
CA11 8D 47 00    STA $0047
CA14 BD 01 80    LDA $8001,X @ $800F = #A9
CA17 8D 48 00    STA $0048

[KingMike]

Code Select Expand

FBAC A6 4C LDX $4C x = $4C
FBAE D0 10 BNE $FBC0 BRANCH IF NOT 0
FBB0 20 D8 FB    JSR $FBD8    depends on value at $4A.
                                              If 0, it will read a byte from data at pointer $47
FBB3 90 15 BCC $FBCA   if the high bit was 0, read 8 bits from input stream and quit
FBB5 20 CA FB    JSR $FBCA     read 8 bits from the ROM input stream
FBB8 85 4B STA $4B        and store to $4B
FBBA 20 C6 FB    JSR $FBC6      read 3 bits from the ROM input stream
FBBD AA TAX             gives 1-8 range
FBBE E8 INX
FBBF E8 INX
FBC0 CA DEX not sure what the point of this is,
                                         these last two statements cancel each other
FBC1 86 4C STX $4C $4C = X
FBC3 A5 4B LDA $4B A = $4B
FBC5 60 RTS

FBC6 A0 03 LDY #$03       data size: 3 bits compressed per 8 uncompressed
FBC8 D0 02 BNE $FBCC     branch to routine at FBCC
FBCA A0 08 LDY #$08       set data size to 8
FBCC A9 00 LDA #$00       initialize result
FBCE 48 PHA
FBCF 20 D8 FB    JSR $FBD8           read next bit of ROM data, out to Carry
FBD2 68 PLA
FBD3 2A ROL A             shift that bit of data we read from the ROM
                                              from the Carry bit into the low bit of the result
FBD4 88 DEY
FBD5 D0 F7 BNE $FBCE
FBD7 60 RTS

FBD8 AD 4A 00    LDA $004A          ;check if all 8 bits of a byte have been read?
FBDB D0 12 BNE $FBEF
FBDD A2 47 LDX #$47
FBDF A1 00 LDA ($00,X)             read pointer at $47
FBE1 F6 00 INC $00,X             increment pointer low byte
FBE3 D0 02 BNE $FBE7            check for wraparound of the high byte
FBE5 F6 01 INC $01,X
FBE7 8D 49 00    STA $0049          store data read from pointer
FBEA A9 08 LDA #$08           set bit counter to 8
FBEC 8D 4A 00    STA $004A
FBEF CE 4A 00    DEC $004A         decrement bit counter
FBF2 0E 49 00    ASL $0049         shift next highest bit of data out to Carry
FBF5 60 RTS = $FBB3

[rveach]

$17 = temporary location of where to output uncompressed data to

$1D = some value to append to $4B afterwards if $4B isn't 0.
$48:$47 = input data pointer (starting value seems to be B0F3, even though we read in A9BF. Some other routine must read in the other bytes)
$49 = current byte of input data
$4A = the input data bits left to read
$4B = 8 bits of data that are outputted
$4C = 3 bits (contains values 0 to 7) of data that say how many times $4B is repeated. Note we add 2 to the value read in. So if we read 0, $4B is repeated only 2 times.

Its a good thing to notice, that when it reads a bit, it reads the TOP bit first, not the lowest like most routines do.

Also note, that before we read in the next $4B, we read 1 bit. If it is 0, then we don't read in $4C, we skip it and go right to $4B. So this is a way to save 3 bits when we want to repeat $4B only once.


here is a condensed, c++ like view of the code:

Code Select Expand

void FA88() {
     x = -1

     do {
          x++
          $17 = X
          a = getNextUncompressedByte()

          if (a != 0) {
               a += $1D
          }
          $626[$17] = a
     } while (x != $15)
}

byte getNextUncompressedByte() { //FBAC
     x = $4C
     if ($4C == 0) {
          carry = loadBit()
          if (carry == 0)
          {
               a = loadByte(8);
               return a;
          }
          $4b = loadByte(8)
          a = loadByte(3)
          x = a+2
     }
     x--
     $4C = x

     return $4B
}

byte loadByte(y) { //FBC6
     a = 0
     do {
          carry = loadBit()
          a = (a << 1) | carry
          y--
     } while (y != 0)

     return a
}

byte loadBit() { //FBD8
     if ($4A == 0) {
          a = ($47) (tile data)
          $48:$47 += 1 (increase input data pointer by 1)
          $49 = a
          $4A = #8
     }
     $4A--
     carry = ($49 & #80); $49 <<= 1;

     return carry
}


Edit:
as I pointed out that some other routine must read in the data before we get to the routine you specified.
It seems to read 5 bytes directly after it gets the pointer, and then switches in to reading the rest of the data as our compressed version.

Code Select Expand

F9D9 A0 00 LDY #$00
F9DB A2 47 LDX #$47
F9DD A1 00 LDA ($00,X) @ $A9BF = #06 <--- read data
F9DF F6 00 INC $00,X @ $0047 = #BF
F9E1 D0 02 BNE $F9E5
F9E3 F6 01 INC $01,X @ $0048 = #A9
F9E5 99 13 00    STA $0013,Y @ $0013 = #06
F9E8 C8 INY
F9E9 C0 04 CPY #$04 <---
F9EB D0 EE BNE $F9DB <--- loop 4 times
F9ED A2 47 LDX #$47
F9EF A1 00 LDA ($00,X) @ $A9C3 = #80 <--- read data
F9F1 F6 00 INC $00,X @ $0047 = #C3
F9F3 D0 02 BNE $F9F7
F9F5 F6 01 INC $01,X @ $0048 = #A9

............

FA32 20 A5 FB    JSR $FBA5 <--- compression reset routine

............

FA3F 20 5D FB    JSR $FB5D
FB5D 20 AC FB    JSR $FBAC A = getNextUncompressedByte()