Yazwh0_BitMagic_Legacy/Libraries/Compression/DecompressToMemory.csasm
namespace Compression;

public static partial class Inflator 
{
    public static void InflateToRamCode()
    {
        ; inflate taken from https://github.com/pfusik/zlib6502/blob/master/inflate.asx

        .scope Inflate

        .proc inflate_to_ram
            .const inputPointer                    = @(Source)
            .const outputPointer                   = @(Source+2)
            .const getBit_buffer                   = @(Source+4)

            .const getBits_base                    = @(Source+5)  ; 1 byte
            .const inflateStored_pageCounter       = @(Source+5)  ; 1 byte

            .const inflateCodes_sourcePointer      = @(Source+6)  ; 2 bytes

            .const inflateDynamic_symbol           = @(Source+6)  ;6 1 byte
            .const inflateDynamic_lastLength       = @(Source+7)  ;7 1 byte
            .const inflateDynamic_tempCodes        = @(Source+7)  ;7 1 byte

            .const inflateCodes_lengthMinus2       = @(Source+8)  ; 1 byte
            .const inflateDynamic_allCodes         = @(Source+8)  ; 1 byte

            .const inflateDynamic_primaryCodes     = @(Source+9)  ; 1 byte

            .const GET_1_BIT                       =	$81
            .const GET_2_BITS                      =	$82
            .const GET_3_BITS                      =	$84
            .const GET_4_BITS                      =	$88
            .const GET_5_BITS                      =	$90
            .const GET_6_BITS                      =	$a0
            .const GET_7_BITS                      =	$c0   

            .const TREE_SIZE                       =	16
            .const PRIMARY_TREE                    =	0
            .const DISTANCE_TREE                   =	16

            .const LENGTH_SYMBOLS                  =	@(1+29+2)
            .const DISTANCE_SYMBOLS                =	30
            .const CONTROL_SYMBOLS                 =	@(1+29+2 + 30) ;LENGTH_SYMBOLS+DISTANCE_SYMBOLS

; Uncompress DEFLATE stream starting from the address stored in inputPointer
; to the memory starting from the address stored in outputPointer
            ldy #0
            sty getBit_buffer

; Get a bit of EOF and two bits of block type
            .inflate_blockLoop:
            sty	getBits_base
            lda	#GET_3_BITS
            jsr	getBits
            lsr
            php
            bne	inflateCompressed

        ; Copy uncompressed block
            sty	getBit_buffer  ; ignore bits until byte boundary
            jsr	getWord        ; skip the length we don't need
            jsr	getWord        ; get the one's complement length
            sta	inflateStored_pageCounter
            bcs	inflateStored_firstByte

        .inflateStored_copyByte:
            jsr	getByte
            jsr	storeByte
            
        .inflateStored_firstByte:
            inx
            bne	inflateStored_copyByte
            inc	inflateStored_pageCounter
            bne	inflateStored_copyByte

        .inflate_nextBlock:
            plp
            bcc	inflate_blockLoop
            rts

        .inflateCompressed:
        ; A=1: fixed block, initialize with fixed codes
        ; A=2: dynamic block, start by clearing all code lengths
        ; A=3: invalid compressed data, not handled in this routine
            eor	#2

        ;	ldy	#0
        .inflateCompressed_setCodeLengths:
            tax
            beq	inflateCompressed_setLiteralCodeLength
        ; fixed Huffman literal codes:
        ; :144 dta 8
        ; :112 dta 9
            lda	#4
            cpy	#144
            rol	

        .inflateCompressed_setLiteralCodeLength:
            sta	literalSymbolCodeLength,y
            beq	inflateCompressed_setControlCodeLength
        ; fixed Huffman control codes:
        ; :24  dta 7
        ; :6   dta 8
        ; :2   dta 8 ; meaningless codes
        ; :30  dta 5+DISTANCE_TREE
            lda	#5+DISTANCE_TREE
            cpy	#LENGTH_SYMBOLS
            bcs	inflateCompressed_setControlCodeLength
            cpy	#24
            adc	#2-DISTANCE_TREE

        .inflateCompressed_setControlCodeLength:
            cpy	#CONTROL_SYMBOLS

            ;scs:sta	controlSymbolCodeLength,y
            bcs skip_5
            sta	controlSymbolCodeLength,y
        .skip_5:
            iny
            bne	inflateCompressed_setCodeLengths

            tax
            bne	inflateCodes

        ; Decompress a block reading Huffman trees first

        ; Build the tree for temporary codes
            jsr	buildTempHuffmanTree

        ; Use temporary codes to get lengths of literal/length and distance codes
        ;	ldx	#0
        ;	sec
        .inflateDynamic_decodeLength:
        ; C=1: literal codes
        ; C=0: control codes
            stx	inflateDynamic_symbol
            php
        ; Fetch a temporary code
            jsr	fetchPrimaryCode
        ; Temporary code 0..15: put this length
            bpl	inflateDynamic_verbatimLength
        ; Temporary code 16: repeat last length 3 + getBits(2) times
        ; Temporary code 17: put zero length 3 + getBits(3) times
        ; Temporary code 18: put zero length 11 + getBits(7) times
            tax
            jsr	getBits
            cpx	#GET_3_BITS
            bcc	inflateDynamic_repeatLast

            beq skip_1
            ;seq:adc	#7
            adc	#7
        .skip_1:
        ;	ldy	#0
            sty	inflateDynamic_lastLength

        .inflateDynamic_repeatLast:
            tay
            lda	inflateDynamic_lastLength
            ; iny:iny
            iny
            iny

        .inflateDynamic_verbatimLength:
            iny
            plp
            ldx	inflateDynamic_symbol

        .inflateDynamic_storeLength:
            bcc	inflateDynamic_controlSymbolCodeLength
            sta	literalSymbolCodeLength,x ; +
            inx
            cpx	#1

        .inflateDynamic_storeNext:
            dey
            bne	inflateDynamic_storeLength
            sta	inflateDynamic_lastLength
            beq	inflateDynamic_decodeLength

        .inflateDynamic_controlSymbolCodeLength:
            cpx	inflateDynamic_primaryCodes
            bcc	inflateDynamic_storeControl
        ; the code lengths we skip here were zero-initialized
        ; in inflateCompressed_setControlCodeLength
            ;sne:ldx	#LENGTH_SYMBOLS
            bne skip_2
            ldx	#LENGTH_SYMBOLS
        .skip_2:
            ora	#DISTANCE_TREE

        .inflateDynamic_storeControl:
            sta	controlSymbolCodeLength,x ; +
            inx
            cpx	inflateDynamic_allCodes
            bcc	inflateDynamic_storeNext
            dey

        ; Decompress a block
        .inflateCodes:
            jsr	buildHuffmanTree
        ;	jmp	inflateCodes_loop
            beq	inflateCodes_loop

        .inflateCodes_literal:
            stp
            jsr	storeByte

        .inflateCodes_loop:
            jsr	fetchPrimaryCode
            bcc	inflateCodes_literal
            beq	inflate_nextBlock
        ; Copy sequence from look-behind buffer

            sty	getBits_base
            cmp	#9
            bcc	inflateCodes_setSequenceLength
            tya

            cpx	#1+28
            bcs	inflateCodes_setSequenceLength
            dex
            txa
            lsr	
            ror	getBits_base
            inc	getBits_base
            lsr	
            rol	getBits_base
            jsr	getAMinus1BitsMax8
        ;	sec
            adc	#0

        .inflateCodes_setSequenceLength:
            sta	inflateCodes_lengthMinus2 ; -2 as the length is always greater than 3.
            ldx	#DISTANCE_TREE
            jsr	fetchCode
            cmp	#4
            bcc	inflateCodes_setOffsetLowByte
            inc	getBits_base
            lsr	
            jsr	getAMinus1BitsMax8

        .inflateCodes_setOffsetLowByte:
        stp ; at this point a is the low number of bytes to look back
            eor	#$ff
            sta	inflateCodes_sourcePointer
            lda	getBits_base
            cpx	#10
            bcc	inflateCodes_setOffsetHighByte
            lda	getNPlus1Bits_mask-10,x
            jsr	getBits
            clc

        .inflateCodes_setOffsetHighByte:
        stp ; at this point a is the hig number of bytes to look back
            eor	#$ff
        ;	clc
        ;   invert and add output pointer to get a address relative to the output pointer?
            adc	outputPointer+1
            sta	inflateCodes_sourcePointer+1
            jsr	copyByte
            jsr	copyByte

        .inflateCodes_copyByte:
            jsr	copyByte
            dec	inflateCodes_lengthMinus2
            bne	inflateCodes_copyByte
        ;	jmp	inflateCodes_loop
            beq	inflateCodes_loop

        ; Get dynamic block header and use it to build the temporary tree
        .buildTempHuffmanTree:
        ;	ldy	#0
        ; numberOfPrimaryCodes = 257 + getBits(5)
        ; numberOfDistanceCodes = 1 + getBits(5)
        ; numberOfTemporaryCodes = 4 + getBits(4)
            ldx	#3
        .inflateDynamic_getHeader:
            lda	inflateDynamic_headerBits-1,x
            jsr	getBits
        ;	sec
            adc	inflateDynamic_headerBase-1,x
            sta	inflateDynamic_tempCodes-1,x
            dex
            bne	inflateDynamic_getHeader

        ; Get lengths of temporary codes in the order stored in inflateDynamic_tempSymbols
        ;	ldx	#0
        .inflateDynamic_getTempCodeLengths:
            lda	#GET_3_BITS
            jsr	getBits
            ldy	inflateDynamic_tempSymbols,x
            sta	literalSymbolCodeLength,y
            ldy	#0
            inx
            cpx	inflateDynamic_tempCodes
            bcc	inflateDynamic_getTempCodeLengths

        ; Build Huffman trees basing on code lengths (in bits)
        ; stored in the *SymbolCodeLength arrays
        .buildHuffmanTree:
        ; Clear nBitCode_literalCount, nBitCode_controlCount
            tya
        ;	lda	#0
            ;sta:rne	nBitCode_clearFrom,y+
        .loop_1:
            sta nBitCode_clearFrom,y
            iny
            bne loop_1
        ; Count number of codes of each length
        ;	ldy	#0

        .buildHuffmanTree_countCodeLengths:
            ldx	literalSymbolCodeLength,y
            inc	nBitCode_literalCount,x

            bne skip_4
            ;sne:stx	allLiteralsCodeLength
            stx	allLiteralsCodeLength
            .skip_4:

            cpy	#CONTROL_SYMBOLS
            bcs	buildHuffmanTree_noControlSymbol
            ldx	controlSymbolCodeLength,y
            inc	nBitCode_controlCount,x

        .buildHuffmanTree_noControlSymbol:
            iny
            bne	buildHuffmanTree_countCodeLengths
        ; Calculate offsets of symbols sorted by code length
        ;	lda	#0
            ldx	#-4*TREE_SIZE

        .buildHuffmanTree_calculateOffsets:
        ; !problem!
            sta	nBitCode_literalOffset+64-$100,x
            ;add	nBitCode_literalCount+4*TREE_SIZE-$100,x
            clc
            adc	nBitCode_literalCount+64-$100,x
            inx
            bne	buildHuffmanTree_calculateOffsets
        ; Put symbols in their place in the sorted array
        ;	ldy	#0

        .buildHuffmanTree_assignCode:
            tya
            ldx	literalSymbolCodeLength,y
            ;ldy:inc	nBitCode_literalOffset,x
            ldy	nBitCode_literalOffset,x
            inc	nBitCode_literalOffset,x
            sta	codeToLiteralSymbol,y
            tay
            cpy	#CONTROL_SYMBOLS
            bcs	buildHuffmanTree_noControlSymbol2
            ldx	controlSymbolCodeLength,y
            ;ldy:inc	nBitCode_controlOffset,x
            ldy nBitCode_controlOffset,x
            inc	nBitCode_controlOffset,x
            sta	codeToControlSymbol,y
            tay

        .buildHuffmanTree_noControlSymbol2:
            iny
            bne	buildHuffmanTree_assignCode
            rts

        ; Read Huffman code using the primary tree
        .fetchPrimaryCode:
            ldx	#PRIMARY_TREE

        ; Read a code from input using the tree specified in X,
        ; return low byte of this code in A,
        ; return C flag reset for literal code, set for length code
        .fetchCode:
        ;	ldy	#0
            tya

        .fetchCode_nextBit:
            jsr	getBit
            rol	
            inx
            bcs	fetchCode_ge256
        ; are all 256 literal codes of this length?
            cpx	allLiteralsCodeLength
            beq	fetchCode_allLiterals
        ; is it literal code of length X?
            ;sub	nBitCode_literalCount,x
            sec
            sbc	nBitCode_literalCount,x

            bcs	fetchCode_notLiteral
        ; literal code
        ;	clc
            adc	nBitCode_literalOffset,x
            tax
            lda	codeToLiteralSymbol,x

        .fetchCode_allLiterals:
            clc
            rts

        ; code >= 256, must be control
        .fetchCode_ge256:
        ;	sec
            sbc	nBitCode_literalCount,x
            sec

        ; is it control code of length X?
        .fetchCode_notLiteral:
        ;	sec
            sbc	nBitCode_controlCount,x
            bcs	fetchCode_nextBit
        ; control code
        ;	clc
            adc	nBitCode_controlOffset,x
            tax
            lda	codeToControlSymbol,x
            and	#$1f	; make distance symbols zero-based
            tax
        ;	sec
            rts

        ; Read A minus 1 bits, but no more than 8
        .getAMinus1BitsMax8:
            rol	getBits_base
            tax
            cmp	#9
            bcs	getByte
            lda	getNPlus1Bits_mask-2,x

        .getBits:
            jsr	getBits_loop

        .getBits_normalizeLoop:
            lsr	getBits_base
            ror	
            bcc	getBits_normalizeLoop
            rts

        ; Read 16 bits
        .getWord:
            jsr	getByte
            tax

        ; Read 8 bits
        .getByte:
            lda	#$80

        .getBits_loop:
            jsr	getBit
            ror	
            bcc	getBits_loop
            rts

        ; Read one bit, return in the C flag
        .getBit:
            lsr	getBit_buffer
            bne	getBit_return
            pha
        ;	ldy	#0
            lda	(inputPointer),y

            ;inw	inputPointer
            inc	inputPointer
            bne skip_3
            inc inputPointer+1
        .skip_3:
        
            sec
            ror
            sta	getBit_buffer
            pla

        .getBit_return:
            rts

        ; Copy a previously written byte
        .copyByte:
            ldy	outputPointer
            lda	(inflateCodes_sourcePointer),y
            ldy	#0

        ; Write a byte
        .storeByte:
        ;	ldy	#0
            sta	(outputPointer),y
            inc	outputPointer
            bne	storeByte_return
            inc	outputPointer+1
            inc	inflateCodes_sourcePointer+1

        .storeByte_return:
            rts            

        .getNPlus1Bits_mask:
            .byte $81, $82, $84, $88, $90, $a0, $c0

        .inflateDynamic_tempSymbols:
	        .byte $82,$84,$c0,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15

        .inflateDynamic_headerBits:
            .byte $88, $90, $90
        .inflateDynamic_headerBase:
	        .byte	3,@(1+29+2),0
        
        .endproc        
        .endscope
    }

}