home *** CD-ROM | disk | FTP | other *** search
/ Syzygy Magazine 8 / Syzygy_Magazine_8_2002___pl_beta_Side_B.atr / inflate.asm < prev    next >
Assembly Source File  |  2023-02-26  |  11KB  |  470 lines
  1. zpage    equ    $f0    ; 11 bytes
  2. inflate equ    $b600
  3.  
  4. * 'Inflate'
  5. ; Written by Piotr Fusik (a.k.a. Fox/Taquart)
  6. ; Purpose: to uncompress Deflate format compressed data on 6502-based system.
  7.  
  8. * const
  9. ; Maximum length of a Huffman code
  10. MAX_BITS      equ    15
  11. ; Index in bitsCount, bitsPointer_l and bitsPointer_h
  12. ; for temporary tree and literal/length tree
  13. PRIMARY_TREE  equ    0
  14. ; Index in bitsCount, bitsPointer_l and bitsPointer_h for distance tree
  15. DISTANCE_TREE equ    MAX_BITS
  16. ; Size of each of bitsCount, bitsPointer_l and bitsPointer_h
  17. TREES_SIZE    equ    2*MAX_BITS
  18.  
  19. * page zero
  20. ; (public) Pointer to compressed data
  21. inputPointer            equ    zpage    ; 2 bytes
  22. ; (public) Pointer to uncompressed data
  23. outputPointer           equ    zpage+2  ; 2 bytes
  24. ; Local variables
  25. getBit_hold             equ    zpage+10 ; 1 byte
  26.  
  27. inflateDynamicBlock_cnt equ    zpage+4  ; 1 byte
  28. inflateCodes_src        equ    zpage+4  ; 2 bytes
  29. buildHuffmanTree_src    equ    zpage+4  ; 2 bytes
  30. getNextLength_last      equ    zpage+4  ; 1 byte
  31. getNextLength_index     equ    zpage+5  ; 1 byte
  32.  
  33. buildHuffmanTree_ptr    equ    zpage+6  ; 2 bytes
  34. fetchCode_ptr           equ    zpage+6  ; 2 bytes
  35. getBits_tmp             equ    zpage+6  ; 1 byte
  36.  
  37. moveBlock_len           equ    zpage+8  ; 2 bytes
  38. inflateDynamicBlock_np  equ    zpage+8  ; 1 byte
  39. inflateDynamicBlock_nd  equ    zpage+9  ; 1 byte
  40.  
  41. * code
  42.     org    inflate
  43. * (public) inflate
  44. ; Decompress Deflate data pointed by inputPointer
  45. ; to memory at outputPointer
  46.     mvy    #1    getBit_hold
  47.     bne    inflate_2    !
  48. inflate_1
  49.     jsr    inflate_3
  50. inflate_2
  51. ; Get a bit of EOF and two bits of block type
  52.     ldx    #3
  53.     lda    #0
  54.     jsr    getBits
  55.     lsr    @
  56.     bcc    inflate_1
  57. inflate_3
  58.     bne    inflateCompressedBlock
  59.  
  60. * inflateCopyBlock
  61. ; Decompress 'stored' data block
  62. inflateCopyBlock
  63. ; Ignore bits until byte boundary
  64.     mvy    #1    getBit_hold
  65. ; Get 16-bit length
  66.     ldx    #inputPointer
  67.     mva    (0,x)    moveBlock_len
  68.     mva    (inputPointer),y    moveBlock_len+1
  69. ; Skip length and one's complement length
  70.     lda    #4
  71.     add:sta    inputPointer
  72.     scc:inc    inputPointer+1
  73.  
  74. * moveBlock
  75. ; Copy block of length moveBlock_len from (0,x) to output
  76. moveBlock
  77.     ldy    moveBlock_len
  78.     beq    moveBlock_1
  79.     ldy    #0
  80.     inc    moveBlock_len+1
  81. moveBlock_1
  82.     mva    (0,x)    (outputPointer),y
  83.     inw    0,x
  84.     inw    outputPointer
  85.     dec    moveBlock_len
  86.     bne    moveBlock_1
  87.     dec    moveBlock_len+1
  88.     bne    moveBlock_1
  89.     rts
  90.  
  91. * inflateCompressedBlock
  92. ; Decompress Huffman-coded data block
  93. ; A = 1: fixed, A = 2: dynamic
  94. inflateCompressedBlock
  95.     lsr    @
  96.     bne    inflateDynamicBlock
  97.  
  98. * inflateFixedBlock
  99. ; Decompress Huffman-coded data block with default Huffman trees:
  100. ; literalCodeLength    :144    dta 8
  101. ;            :112    dta 9
  102. ; endCodeLength        :24    dta 7
  103. ;            :6    dta 8
  104. ; distanceCodeLength    :30    dta 5+DISTANCE_TREE
  105. ;            :2    dta 8
  106. ; (two 8-bit codes from primary tree are not used)
  107. inflateFixedBlock
  108.     ldx    #159
  109.     stx    distanceCodeLength+32
  110.     lda    #8
  111. inflateFixedBlock_1
  112.     sta    literalCodeLength-1,x
  113.     sta    literalCodeLength+159-1,x-
  114.     bne    inflateFixedBlock_1
  115.     ldx    #112
  116.     inc:rne    literalCodeLength+144-1,x-
  117.     ldx    #24
  118.     dec:rne    endCodeLength-1,x-
  119.     ldx    #30
  120.     lda    #5+DISTANCE_TREE
  121.     sta:rne    distanceCodeLength-1,x-
  122.     beq    inflateCodes    !
  123.  
  124. * inflateDynamicBlock
  125. ; Decompress Huffman-coded data block, reading Huffman trees first
  126. inflateDynamicBlock
  127. ; numberOfPrimaryCodes = 257 + getBits(5)
  128.     ldx    #5
  129. ;    lda    #1
  130.     jsr    getBits
  131.     sta    inflateDynamicBlock_np
  132. ; numberOfDistanceCodes = 1 + getBits(5)
  133.     ldx    #5
  134.     lda    #1+29+1
  135.     jsr    getBits
  136.     sta    inflateDynamicBlock_nd
  137. ; numberOfTemporaryCodes = 4 + getBits(4)
  138.     lda:tax    #4
  139.     jsr    getBits
  140.     sta    inflateDynamicBlock_cnt
  141. ; Get lengths of temporary codes in order stored in tempCodeLengthOrder
  142.     lda:tay    #0
  143. inflateDynamicBlock_1
  144.     ldx    #3        ; A = 0
  145.     jsr    getBits        ; does not change Y
  146. inflateDynamicBlock_2
  147.     ldx    tempCodeLengthOrder,y
  148.     sta    literalCodeLength,x
  149.     lda    #0
  150.     iny
  151.     cpy    inflateDynamicBlock_cnt
  152.     bcc    inflateDynamicBlock_1
  153.     cpy    #19
  154.     bcc    inflateDynamicBlock_2
  155.     ror    literalCodeLength+19    +
  156. ; Build tree for temporary codes
  157.     jsr    buildHuffmanTree
  158.  
  159. ; Use temporary codes to get lengths for literal/length and distance codes
  160.     ldx    #0
  161.     ldy    #1
  162.     stx    getNextLength_last
  163. inflateDynamicBlock_3
  164.     jsr    getNextLength
  165.     sta    literalCodeLength,x+
  166.     bne    inflateDynamicBlock_3
  167. inflateDynamicBlock_4
  168.     jsr    getNextLength
  169.     sta    endCodeLength,x+
  170.     cpx    inflateDynamicBlock_np
  171.     bcc    inflateDynamicBlock_4
  172.     lda    #0
  173.     bcs    inflateDynamicBlock_6    !
  174. inflateDynamicBlock_5
  175.     sta    endCodeLength,x+
  176. inflateDynamicBlock_6
  177.     cpx    #1+29
  178.     bcc    inflateDynamicBlock_5
  179. inflateDynamicBlock_7
  180.     jsr    getNextLength
  181.     cmp    #0
  182.     seq:adc    #DISTANCE_TREE-1    +
  183.     sta    endCodeLength,x+
  184.     cpx    inflateDynamicBlock_nd
  185.     bcc    inflateDynamicBlock_7
  186.     ror    endCodeLength,x    +
  187.  
  188. * inflateCodes
  189. ; Decompress data block basing on given Huffman trees
  190. inflateCodes
  191.     jsr    buildHuffmanTree
  192. inflateCodes_1
  193.     jsr    fetchPrimaryCode
  194.     bcs    inflateCodes_2
  195. ; Literal code
  196.     sta    (outputPointer),0
  197.     inc    outputPointer
  198.     bne    inflateCodes_1
  199.     inc    outputPointer+1
  200.     bcc    inflateCodes_1    !
  201. ; End of block
  202. inflateCodes_ret
  203.     rts
  204. inflateCodes_2
  205.     beq    inflateCodes_ret
  206. ; Repeat block
  207.     jsr    getValue
  208.     sta    moveBlock_len
  209.     tya
  210.     jsr    getBits
  211.     sta    moveBlock_len+1
  212.     ldx    #DISTANCE_TREE
  213.     jsr    fetchCode
  214.     jsr    getValue
  215.     sec
  216.     eor    #$ff
  217.     adc    outputPointer
  218.     sta    inflateCodes_src
  219.     php
  220.     tya
  221.     jsr    getBits
  222.     plp
  223.     eor    #$ff
  224.     adc    outputPointer+1
  225.     sta    inflateCodes_src+1
  226.     ldx    #inflateCodes_src
  227.     jsr    moveBlock
  228.     beq    inflateCodes_1    !
  229.  
  230. * buildHuffmanTree
  231. ; Build Huffman trees basing on code lengths.
  232. ; Lengths (in bits) are stored in *CodeLength tables.
  233. ; A byte with highest bit set marks end of length table.
  234. buildHuffmanTree
  235.     mwa    #literalCodeLength    buildHuffmanTree_src
  236. ; Clear bitsCount and bitsPointer_l
  237.     ldy    #2*TREES_SIZE+1
  238.     lda    #0
  239.     sta:rne    bitsCount-1,y-
  240.     beq    buildHuffmanTree_3    !
  241. ; Count number of codes of each length
  242. buildHuffmanTree_2
  243.     tax
  244.     inc    bitsPointer_l,x
  245.     iny
  246.     bne    buildHuffmanTree_3
  247.     inc    buildHuffmanTree_src+1
  248. buildHuffmanTree_3
  249.     lda    (buildHuffmanTree_src),y
  250.     bpl    buildHuffmanTree_2
  251. ; Calculate pointer for each length
  252.     ldx    #0
  253.     lda    #<sortedCodes
  254.     ldy    #>sortedCodes
  255.     clc
  256. buildHuffmanTree_4
  257.     sta    bitsPointer_l,x
  258.     tya:sta    bitsPointer_h,x
  259.     lda    bitsPointer_l+1,x
  260.     adc    bitsPointer_l,x    -
  261.     scc:iny
  262.     inx
  263.     cpx    #TREES_SIZE
  264.     bcc    buildHuffmanTree_4
  265.     mva    #>literalCodeLength    buildHuffmanTree_src+1
  266.     ldy    #0
  267.     bcs    buildHuffmanTree_9    !
  268. ; Put codes into their place in sorted table
  269. buildHuffmanTree_6
  270.     beq    buildHuffmanTree_7
  271.     tax
  272.     mva    bitsPointer_l-1,x    buildHuffmanTree_ptr
  273.     mva    bitsPointer_h-1,x    buildHuffmanTree_ptr+1
  274.     tya
  275.     ldy:inc    bitsCount-1,x
  276.     sta    (buildHuffmanTree_ptr),y
  277.     tay
  278. buildHuffmanTree_7
  279.     iny
  280.     bne    buildHuffmanTree_9
  281.     inc    buildHuffmanTree_src+1
  282.     ldx    #MAX_BITS-1
  283.     mva:rpl    bitsCount,x    literalCount,x-
  284. buildHuffmanTree_9
  285.     lda    (buildHuffmanTree_src),y
  286.     bpl    buildHuffmanTree_6
  287.     rts
  288.  
  289. * getNextLength
  290. ; Get next code length basing on temporary codes
  291. getNextLength
  292.     stx    getNextLength_index
  293.     dey
  294.     bne    getNextLength_1
  295. ; Fetch a temporary code
  296.     jsr    fetchPrimaryCode
  297. ; Temporary code 0..15: put this length
  298.     ldy    #1
  299.     cmp    #16
  300.     bcc    getNextLength_2
  301. ; Temporary code 16: repeat last length 3 + getBits(2) times
  302. ; Temporary code 17: put zero length 3 + getBits(3) times
  303. ; Temporary code 18: put zero length 11 + getBits(7) times
  304.     tay
  305.     ldx    tempExtraBits-16,y
  306.     lda    tempBaseValue-16,y
  307.     jsr    getBits
  308.     cpy    #17
  309.     tay
  310.     lda    #0
  311.     bcs    getNextLength_2
  312. getNextLength_1
  313.     lda    getNextLength_last
  314. getNextLength_2
  315.     sta    getNextLength_last
  316.     ldx    getNextLength_index
  317.     rts
  318.  
  319. * fetchPrimaryCode
  320. ; Read code basing on primary tree
  321. fetchPrimaryCode
  322.     ldx    #PRIMARY_TREE
  323.  
  324. * fetchCode
  325. ; Read code from input stream basing on tree given in X.
  326. ; Return low byte of code in A.
  327. ; For literal/length tree C is set if non-literal code.
  328. fetchCode
  329.     lda    #0
  330. fetchCode_1
  331.     jsr    getBit
  332.     rol    @
  333.     inx
  334.     sub    bitsCount-1,x
  335.     bcs    fetchCode_1
  336.     adc    bitsCount-1,x    -
  337.     cmp    literalCount-1,x
  338.     sta    fetchCode_ptr
  339.     ldy    bitsPointer_l-1,x
  340.     mva    bitsPointer_h-1,x    fetchCode_ptr+1
  341.     lda    (fetchCode_ptr),y
  342.     rts
  343.  
  344. * getValue
  345. ; Read low byte of value (length or distance), basing on code A
  346. getValue
  347.     tay
  348.     ldx    lengthExtraBits-1,y
  349.     lda:pha    lengthBaseValue_l-1,y
  350.     lda:tay    lengthBaseValue_h-1,y
  351.     pla
  352.  
  353. * getBits
  354. ; Read X-bit number from input stream and add it to A.
  355. ; In case of carry, Y is incremented.
  356. ; If X > 8, only 8 bits are read.
  357. ; On return X holds number of unread bits: X = (X > 8 ? X - 8 : 0);
  358. getBits
  359.     cpx    #0
  360.     beq    getBits_ret
  361.     pha
  362.     mva    #1    getBits_tmp
  363.     pla
  364. getBits_1
  365.     jsr    getBit
  366.     bcc    getBits_2
  367.     add    getBits_tmp
  368.     scc:iny
  369. getBits_2
  370.     dex
  371.     beq    getBits_ret
  372.     asl    getBits_tmp
  373.     bcc    getBits_1
  374. getBits_ret
  375.     rts
  376.  
  377. * getBit
  378. ; Read single bit from input stream, returns it in C flag
  379. getBit
  380.     lsr    getBit_hold
  381.     bne    getBit_ret
  382.     pha
  383.     tya:pha
  384.     lda    (inputPointer),0
  385.     inw    inputPointer
  386.     ror    @    +
  387.     sta    getBit_hold
  388.     pla:tay
  389.     pla
  390. getBit_ret
  391.     rts
  392.  
  393. * Tables for temporary codes
  394. ; Value is BaseValue + getBits(ExtraBits)
  395.  
  396. ; Order, in which lengths of temporary codes are stored
  397. tempCodeLengthOrder
  398.     dta    b(16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15)
  399.  
  400. ; Base values
  401. tempBaseValue
  402.     dta    b(3,3,11)
  403.  
  404. ; Number of extra bits to read
  405. tempExtraBits
  406.     dta    b(2,3,7)
  407.  
  408. * Tables for length and distance codes
  409. ; Value is BaseValue + getBits(ExtraBits)
  410.  
  411. ; Base values
  412. lengthBaseValue_l
  413.     dta    l(3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43)
  414.     dta    l(51,59,67,83,99,115,131,163,195,227,258)
  415. distanceBaseValue_l
  416.     dta    l(1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385)
  417.     dta    l(513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577)
  418. lengthBaseValue_h
  419.     dta    h(3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43)
  420.     dta    h(51,59,67,83,99,115,131,163,195,227,258)
  421. distanceBaseValue_h
  422.     dta    h(1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385)
  423.     dta    h(513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577)
  424.  
  425. ; Number of extra bits to read
  426. lengthExtraBits
  427.     dta    b(0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4)
  428.     dta    b(4,4,5,5,5,5,0)
  429. distanceExtraBits
  430.     dta    b(0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10)
  431.     dta    b(11,11,12,12,13,13)
  432.  
  433. ; Number of literal codes of each length in primary tree
  434. ; (MAX_BITS bytes, overlap with literalCodeLength)
  435. literalCount
  436.  
  437. * Data for building primary tree
  438. ; Lengths of literal codes
  439. literalCodeLength
  440.     org    *+256
  441. ; Length of end code
  442. endCodeLength
  443.     org    *+1
  444. ; Lengths of length codes
  445. lengthCodeLength
  446.     org    *+29
  447.  
  448. * Data for building distance tree
  449. ; Lengths of distance codes
  450. distanceCodeLength
  451.     org    *+30
  452. ; For two unused codes in fixed trees and end-of-table flag
  453.     org    *+3
  454.  
  455. * Huffman tree structure
  456.  
  457. ; Number of codes of each length
  458. bitsCount
  459.     org    *+TREES_SIZE
  460. ; Pointer to sorted codes of each length
  461. bitsPointer_l
  462.     org    *+TREES_SIZE+1
  463. bitsPointer_h
  464.     org    *+TREES_SIZE
  465.  
  466. ; Sorted codes
  467. sortedCodes
  468.     org    *+256+1+29+30+2
  469.  
  470.     end