;Simple Huffman Decompressor for SNES ;(C) 1998, 1999, 2000 Realtime Simulations and Roleplaying Games ;By BattleQueen ;Cleanup for 2000 release by Grog ;Data structure of scratchpad variables DataStart EQU 0 ;24-bit pointer to source data TreeTable EQU 3 ;24-bit pointer to huffman tree data DataLength EQU 6 ;16-bit length of uncompressed block DestPointer EQU 8 ;16-bit pointer to destination buffer FreeNode EQU 11 ;16-bit pointer to next free Node position DataBit EQU 13 ;current input bit position DataByte EQU 14 ;current input byte TreeByte EQU 15 ;Decode space for tree bytes ; DecodeHuffman -- Macro that simplifies decoding huffman compressed data ;---------------------------------------------------------------------------- ; In: TREEBANK -- bank containing tree data ; TREEPTR -- offset of tree into TREEBANK ; SRCBANK -- bank containing the compressed data ; SRCPTR -- offset of compressed data into SRCBANK ; SIZE -- Size of uncomrpessed block (multiples of 256 for speed) ; RAMBANK -- Bank to write to ; DESTPTR -- Offset into RAMBANK to hold the data (page align for speed) ;---------------------------------------------------------------------------- ; Out: None ;---------------------------------------------------------------------------- ; Modifies: X, Y, 16 bytes of Scratchpad RAM at D+$00 ;---------------------------------------------------------------------------- DecodeHuffman .macro (TREEBANK,TREEPTR,SRCBANK,SRCPTR,SIZE,RAMBANK,DESTPTR) PHP PHB REP #$30 SEP #$20 .mem 8 .index 16 LDX #TREEPTR STX TreeTable LDA #TREEBANK STA TreeTable+2 LDX #SRCPTR STX DataStart LDA #SRCBANK STA DataStart+2 LDX #SIZE STX DataLength LDA #RAMBANK PHA PLB ;Point Data Bank at RAM bank REP #$30 .mem 16 LDA #DESTPTR STA DestPointer CLC ADC #SIZE STA FreeNode SEP #$20 .mem 8 JSR DecompressDataSub PLB PLP .endm ;Assumes Direct Page register has been pointed at empty Scratchpad RAM ;Assumes Direct Bank register has been pointed at a RAM bank ;Needs 16 bytes of RAM ;DecompressDataSub -- Decompresses a block of Huffman coded data ; In: ; DataStart -- points at source data (24-bit) ; TreeTable -- points at Huffman tree data (24-bit) ; DataLength -- holds # of bytes in block (16-bit) ; DestPointer -- points to where to decode to (24-bit) ; FreeNode -- points to a local (intrabank) RAM address to hold temp data ; Not that the worst case Node space is 256*2+255*5=1767 bytes ; Out: DestPointer data block will contain decompressed data ; Modifes: X,Y,A,P DecompressDataSub: ;Assumes 8b mem, 16b index .mem 8 .index 16 LDA #$07 STA DataBit ;Initialize bit position count JSR BuildTree ;Decode the huffman tree and build nodes LDX DataLength ;Get the # of bytes in decompressed data LDA #$07 STA DataBit ;Initialize bit position count DecodeLoop: PHX ;Preserve byte count LDX DataLength ;Initialize X to first tree node JSR Decode ;Decode the next byte PLX ;Restore byte count DEX ;Decrement byte count BNE DecodeLoop ;While Byte count != 0, keep decoding RTS ;Otherwise we're done ;GetNextBit -- returns the next data bit in Carry ; In: DataStart -- pointer to raw compressed data ; DataBit -- holds current shift position ; DataByte -- holds current shifted data byte GetNextBit: LDA DataBit ;Load data bit position INC A ;Increment position count AND #$07 ;Mask to 8 bits STA DataBit ;Save new data bit position BNE + ;If its nonzero, skip byte load LDA [DataStart] ;Load new data byte when bit position=0 LDY DataStart INY ;Increment input pointer STY DataStart STA DataByte ;Preserve data byte + LSR DataByte ;Shift data byte right (Carry = LSB) RTS ;GetTreeBit -- returns the next tree bit in Carry ; In: TreeTable -- pointer to raw huffman tree data ; DataBit -- holds current shift position ; DataByte -- holds current shifted data byte ; Out: Carry = bit ; Modifies: A GetTreeBit: LDA DataBit ;Load data bit position INC A ;Increment position count AND #$07 ;Mask to 8 bits STA DataBit ;Save new data bit position BNE + ;If its nonzero, skip byte load LDA [TreeTable] ;Load new data byte when bit position=0 LDY TreeTable INY ;Increment input pointer STY TreeTable STA DataByte ;Preserve data byte + LSR DataByte ;Shift data byte right (Carry = LSB) RTS ; GetTreeByte -- returns a whole byte from input tree data ; In: TreeTable -- pointer to raw huffman tree data ; DataBit -- holds current shift position ; DataByte -- holds current shifted data byte ; Out: A -- Byte from tree ; Modifies: A, P GetTreeByte: JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte JSR GetTreeBit ROL TreeByte LDA TreeByte RTS ;Decode -- Read the next byte from compressed data ;In: X - Points to first node of Huffman tree ;Out: Data written to DestPointer++ ;Modifies: X, Y, A, P Decode: ;Assumes 8b mem, 16b index LDA !$0000,X ;Get node type (0=leaf 1=internal) BEQ LeafNode JSR GetNextBit ;Get next input bit BCS RightChild ;if bit is 1, take right child LeftChild: LDY !$0001,X ;Otherwise load left child's pointer TYX ;into X BRA Decode ;Decode next bit RightChild: LDY !$0003,X ;Load right child's pointer TYX ;into X BRA Decode ;Decode next bit LeafNode: LDA !$0001,X STA (DestPointer) LDY DestPointer INY STY DestPointer RTS ;BuildTree -- Construct a useable Huffman Tree structure from a table ;In: FreeNode -- points to RAM to hold huffman tree ; TreeTable -- points to source data for tree ;Out: Y -- holds pointer of new node (for parent) ;Modifies: A, X, P BuildTree: ;Assumes 8bit mem, 16bit index LDX FreeNode JSR GetTreeBit ;Retrieve next Structure bit from tree table BCS MakeInternal MakeLeafNode: LDA #$00 ;0 indicates leaf node STA !$0000,X ;Set node's type JSR GetTreeByte ;Retrieve leaf node's data byte into A STA !$0001,X ;Set leaf data TXY ;Save this node's pointer for parent INX INX ;Move node pointer to next empty spot STX FreeNode ;Set next free node pointer RTS MakeInternal: LDA #$01 ;1 indicates internal node STA !$0000,X ;Set node's type PHX ;Preserve pointer to this node INX INX INX INX INX ;Skip this node STX FreeNode ;Set next free node pointer JSR BuildTree ;Recursively create the Left child PLX PHY ;Push returned node pointer onto stack PLA ;Low byte of left child's node pointer STA !$0001,X ;Write low pointer byte PLA ;High byte of left child's node pointer STA !$0002,X ;Write high pointer byte PHX JSR BuildTree ;Recursively create the Right child PLX PHY ;Push returned node pointer onto stack PLA ;Low byte of right child's node pointer STA !$0003,X ;Write low pointer byte PLA ;High byte of right child's node pointer STA !$0004,X ;Write high pointer byte TXY ;Save this node's pointer for parent RTS