2 ; Piotr Fusik, 21.09.2003
4 ; unsigned __fastcall__ inflatemem (char* dest, const char* source);
10 .importzp sp, sreg, ptr1, ptr2, ptr3, ptr4, tmp1
12 ; --------------------------------------------------------------------------
17 ; Maximum length of a Huffman code.
20 ; All Huffman trees are stored in the bitsCount, bitsPointer_l
21 ; and bitsPointer_h arrays. There may be two trees: the literal/length tree
22 ; and the distance tree, or just one - the temporary tree.
24 ; Index in the mentioned arrays for the beginning of the literal/length tree
25 ; or the temporary tree.
28 ; Index in the mentioned arrays for the beginning of the distance tree.
29 DISTANCE_TREE = MAX_BITS
32 TREES_SIZE = 2*MAX_BITS
35 ; --------------------------------------------------------------------------
40 ; Pointer to the compressed data.
41 inputPointer = ptr1 ; 2 bytes
43 ; Pointer to the uncompressed data.
44 outputPointer = ptr2 ; 2 bytes
47 ; As far as there is no conflict, same memory locations are used
48 ; for different variables.
50 inflateDynamicBlock_cnt = ptr3 ; 1 byte
51 inflateCodes_src = ptr3 ; 2 bytes
52 buildHuffmanTree_src = ptr3 ; 2 bytes
53 getNextLength_last = ptr3 ; 1 byte
54 getNextLength_index = ptr3+1 ; 1 byte
56 buildHuffmanTree_ptr = ptr4 ; 2 bytes
57 fetchCode_ptr = ptr4 ; 2 bytes
58 getBits_tmp = ptr4 ; 1 byte
60 moveBlock_len = sreg ; 2 bytes
61 inflateDynamicBlock_np = sreg ; 1 byte
62 inflateDynamicBlock_nd = sreg+1 ; 1 byte
64 getBit_hold = tmp1 ; 1 byte
67 ; --------------------------------------------------------------------------
74 ; inputPointer = source
77 ; outputPointer = dest
93 ; Get a bit of EOF and two bits of block type
98 ; A and Z contain block type, C contains EOF flag
101 ; Go to the routine decompressing this block
107 ; return outputPointer - dest;
110 sbc (sp) ; C flag is set
114 sbc (sp),y ; C flag is set
125 ; --------------------------------------------------------------------------
126 ; Go to proper block decoding routine.
129 bne inflateCompressedBlock
131 ; --------------------------------------------------------------------------
132 ; Decompress a 'stored' data block.
135 ; Ignore bits until byte boundary
144 ; Skip the length and one's complement of it
153 ; --------------------------------------------------------------------------
154 ; Copy block of length moveBlock_len from (0,x) to the output.
169 sta (outputPointer),y
189 ; --------------------------------------------------------------------------
190 ; Decompress a Huffman-coded data block
191 ; (A = 1: fixed, A = 2: dynamic).
193 inflateCompressedBlock:
195 bne inflateDynamicBlock
196 ; Note: inflateDynamicBlock may assume that A = 1
198 ; --------------------------------------------------------------------------
199 ; Decompress a Huffman-coded data block with default Huffman trees
200 ; (defined by the DEFLATE format):
201 ; literalCodeLength: 144 times 8, 112 times 9
203 ; lengthCodeLength: 23 times 7, 6 times 8
204 ; distanceCodeLength: 30 times 5+DISTANCE_TREE, 2 times 8
205 ; (two 8-bit codes from the primary tree are not used).
209 stx distanceCodeLength+32
212 sta literalCodeLength-1,x
213 sta literalCodeLength+159-1,x
215 bne inflateFixedBlock_1
219 inc literalCodeLength+144-1,x ; sta
221 bne inflateFixedBlock_2
225 dec endCodeLength-1,x ; sta
227 bne inflateFixedBlock_3
231 sta distanceCodeLength-1,x
233 bne inflateFixedBlock_4
234 beq inflateCodes ; branch always
236 ; --------------------------------------------------------------------------
237 ; Decompress a Huffman-coded data block, reading Huffman trees first.
240 ; numberOfPrimaryCodes = 257 + getBits(5)
244 sta inflateDynamicBlock_np
245 ; numberOfDistanceCodes = 1 + getBits(5)
249 sta inflateDynamicBlock_nd
250 ; numberOfTemporaryCodes = 4 + getBits(4)
254 sta inflateDynamicBlock_cnt
255 ; Get lengths of temporary codes in the order stored in tempCodeLengthOrder
258 inflateDynamicBlock_1:
260 jsr getBits ; does not change Y
261 inflateDynamicBlock_2:
262 ldx tempCodeLengthOrder,y
263 sta literalCodeLength,x
266 cpy inflateDynamicBlock_cnt
267 bcc inflateDynamicBlock_1
269 bcc inflateDynamicBlock_2
270 ror literalCodeLength+19 ; C flag is set, so this will set b7
271 ; Build the tree for temporary codes
274 ; Use temporary codes to get lengths of literal/length and distance codes
277 stx getNextLength_last
278 inflateDynamicBlock_3:
280 sta literalCodeLength,x
282 bne inflateDynamicBlock_3
283 inflateDynamicBlock_4:
285 inflateDynamicBlock_5:
288 cpx inflateDynamicBlock_np
289 bcc inflateDynamicBlock_4
292 bcc inflateDynamicBlock_5
293 inflateDynamicBlock_6:
296 beq inflateDynamicBlock_7
297 adc #DISTANCE_TREE-1 ; C flag is set
298 inflateDynamicBlock_7:
301 cpx inflateDynamicBlock_nd
302 bcc inflateDynamicBlock_6
303 ror endCodeLength,x ; C flag is set, so this will set b7
306 ; --------------------------------------------------------------------------
307 ; Decompress a data block basing on given Huffman trees.
319 sta (outputPointer),y
324 bcc inflateCodes_1 ; branch always
330 ; Restore a block from the look-behind buffer
349 sta inflateCodes_src+1
350 ldx #inflateCodes_src
352 beq inflateCodes_1 ; branch always
354 ; --------------------------------------------------------------------------
355 ; Build Huffman trees basing on code lengths (in bits).
356 ; stored in the *CodeLength arrays.
357 ; A byte with its highest bit set marks the end.
360 lda #<literalCodeLength
361 sta buildHuffmanTree_src
362 lda #>literalCodeLength
363 sta buildHuffmanTree_src+1
364 ; Clear bitsCount and bitsPointer_l
370 bne buildHuffmanTree_1
371 beq buildHuffmanTree_3 ; branch always
372 ; Count number of codes of each length
377 bne buildHuffmanTree_3
378 inc buildHuffmanTree_src+1
380 lda (buildHuffmanTree_src),y
381 bpl buildHuffmanTree_2
382 ; Calculate a pointer for each length
391 lda bitsPointer_l+1,x
392 adc bitsPointer_l,x ; C flag is zero
393 bcc buildHuffmanTree_5
398 bcc buildHuffmanTree_4
399 lda #>literalCodeLength
400 sta buildHuffmanTree_src+1
402 bcs buildHuffmanTree_9 ; branch always
403 ; Put codes into their place in sorted table
405 beq buildHuffmanTree_7
407 lda bitsPointer_l-1,x
408 sta buildHuffmanTree_ptr
409 lda bitsPointer_h-1,x
410 sta buildHuffmanTree_ptr+1
414 sta (buildHuffmanTree_ptr),y
418 bne buildHuffmanTree_9
419 inc buildHuffmanTree_src+1
425 bpl buildHuffmanTree_8
427 lda (buildHuffmanTree_src),y
428 bpl buildHuffmanTree_6
431 ; --------------------------------------------------------------------------
432 ; Decode next code length using temporary codes.
435 stx getNextLength_index
438 ; Fetch a temporary code
440 ; Temporary code 0..15: put this length
444 ; Temporary code 16: repeat last length 3 + getBits(2) times
445 ; Temporary code 17: put zero length 3 + getBits(3) times
446 ; Temporary code 18: put zero length 11 + getBits(7) times
448 ldx tempExtraBits-16,y
449 lda tempBaseValue-16,y
456 lda getNextLength_last
458 sta getNextLength_last
459 ldx getNextLength_index
462 ; --------------------------------------------------------------------------
463 ; Read a code basing on the primary tree.
469 ; --------------------------------------------------------------------------
470 ; Read a code from input basing on the tree specified in X.
471 ; Return low byte of this code in A.
472 ; For the literal/length tree, the C flag is set if the code is non-literal.
483 adc bitsCount-1,x ; C flag is zero
486 ldy bitsPointer_l-1,x
487 lda bitsPointer_h-1,x
489 lda (fetchCode_ptr),y
492 ; --------------------------------------------------------------------------
493 ; Decode low byte of a value (length or distance), basing on the code in A.
494 ; The result is the base value for this code plus some bits read from input.
498 ldx lengthExtraBits-1,y
499 lda lengthBaseValue_l-1,y
501 lda lengthBaseValue_h-1,y
506 ; --------------------------------------------------------------------------
507 ; Read X-bit number from the input and add it to A.
508 ; Increment Y if overflow.
509 ; If X > 8, read only 8 bits.
510 ; On return X holds number of unread bits: X = (X > 8 ? X - 8 : 0);
527 sbc getBits_tmp ; C flag is set
538 ; --------------------------------------------------------------------------
539 ; Read a single bit from input, return it in the C flag.
557 ror a ; C flag is set
564 ; --------------------------------------------------------------------------
570 ; --------------------------------------------------------------------------
571 ; Arrays for the temporary codes.
573 ; Order, in which lengths of the temporary codes are stored.
575 .byte 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
581 ; Number of extra bits to read.
585 ; --------------------------------------------------------------------------
586 ; Arrays for the length and distance codes.
590 .byte <3,<4,<5,<6,<7,<8,<9,<10
591 .byte <11,<13,<15,<17,<19,<23,<27,<31
592 .byte <35,<43,<51,<59,<67,<83,<99,<115
593 .byte <131,<163,<195,<227,<258
595 .byte <1,<2,<3,<4,<5,<7,<9,<13
596 .byte <17,<25,<33,<49,<65,<97,<129,<193
597 .byte <257,<385,<513,<769,<1025,<1537,<2049,<3073
598 .byte <4097,<6145,<8193,<12289,<16385,<24577
600 .byte >3,>4,>5,>6,>7,>8,>9,>10
601 .byte >11,>13,>15,>17,>19,>23,>27,>31
602 .byte >35,>43,>51,>59,>67,>83,>99,>115
603 .byte >131,>163,>195,>227,>258
605 .byte >1,>2,>3,>4,>5,>7,>9,>13
606 .byte >17,>25,>33,>49,>65,>97,>129,>193
607 .byte >257,>385,>513,>769,>1025,>1537,>2049,>3073
608 .byte >4097,>6145,>8193,>12289,>16385,>24577
610 ; Number of extra bits to read.
612 .byte 0,0,0,0,0,0,0,0
613 .byte 1,1,1,1,2,2,2,2
614 .byte 3,3,3,3,4,4,4,4
617 .byte 0,0,0,0,1,1,2,2
618 .byte 3,3,4,4,5,5,6,6
619 .byte 7,7,8,8,9,9,10,10
620 .byte 11,11,12,12,13,13
623 ; --------------------------------------------------------------------------
630 ; Number of literal codes of each length in the primary tree
631 ; (MAX_BITS bytes, overlap with literalCodeLength).
634 ; --------------------------------------------------------------------------
635 ; Data for building the primary tree.
637 ; Lengths of literal codes.
640 ; Length of the end code.
643 ; Lengths of length codes.
647 ; --------------------------------------------------------------------------
648 ; Data for building the distance tree.
650 ; Lengths of distance codes.
653 ; For two unused codes in the fixed trees and an 'end' mark.
656 ; --------------------------------------------------------------------------
659 ; Number of codes of each length.
662 ; Pointers to sorted codes of each length.