2 ; Piotr Fusik, 23.11.2001
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
19 ; Index in bitsCount, bitsPointer_l and bitsPointer_h
20 ; for temporary tree or literal/length tree
22 ; Index in bitsCount, bitsPointer_l and bitsPointer_h for distance tree
23 DISTANCE_TREE = MAX_BITS
24 ; Size of each of bitsCount, bitsPointer_l and bitsPointer_h
25 TREES_SIZE = 2*MAX_BITS
27 ; --------------------------------------------------------------------------
32 ; Pointer to compressed data
33 inputPointer = ptr1 ; 2 bytes
34 ; Pointer to uncompressed data
35 outputPointer = ptr2 ; 2 bytes
38 getBit_hold = tmp1 ; 1 byte
40 inflateDynamicBlock_cnt = ptr3 ; 1 byte
41 inflateCodes_src = ptr3 ; 2 bytes
42 buildHuffmanTree_src = ptr3 ; 2 bytes
43 getNextLength_last = ptr3 ; 1 byte
44 getNextLength_index = ptr3+1 ; 1 byte
46 buildHuffmanTree_ptr = ptr4 ; 2 bytes
47 fetchCode_ptr = ptr4 ; 2 bytes
48 getBits_tmp = ptr4 ; 1 byte
50 moveBlock_len = sreg ; 2 bytes
51 inflateDynamicBlock_np = sreg ; 1 byte
52 inflateDynamicBlock_nd = sreg+1 ; 1 byte
54 ; --------------------------------------------------------------------------
61 ; inputPointer = source
64 ; outputPointer = dest
80 ; Get a bit of EOF and two bits of block type
86 ; X contains block type, C contains EOF flag
89 ; Go to the routine decompressing this block
95 ; return outputPointer - dest;
98 sbc (sp) ; C flag is set
102 sbc (sp),y ; C flag is set
113 ; --------------------------------------------------------------------------
114 ; Go to the routine decompressing block type X
123 ; --------------------------------------------------------------------------
124 ; Decompress 'stored' data block
127 ; Ignore bits until byte boundary
136 ; Skip length and one's complement of it
145 ; --------------------------------------------------------------------------
146 ; Copy block of length moveBlock_len from (0,x) to output
161 sta (outputPointer),y
181 ; --------------------------------------------------------------------------
182 ; Decompress Huffman-coded data block with default Huffman trees:
183 ; literalCodeLength: 144 times 8, 112 times 9
184 ; endCodeLength: 24 times 7, 6 times 8
185 ; distanceCodeLength: 30 times 5+DISTANCE_TREE, 2 times 8
186 ; (two 8-bit codes from primary tree are not used)
190 stx distanceCodeLength+32
193 sta literalCodeLength-1,x
194 sta literalCodeLength+159-1,x
196 bne inflateFixedBlock_1
200 inc literalCodeLength+144-1,x ; sta
202 bne inflateFixedBlock_2
206 dec endCodeLength-1,x ; sta
208 bne inflateFixedBlock_3
212 sta distanceCodeLength-1,x
214 bne inflateFixedBlock_4
217 ; --------------------------------------------------------------------------
218 ; Decompress Huffman-coded data block, reading Huffman trees first
221 ; numberOfPrimaryCodes = 257 + getBits(5)
225 sta inflateDynamicBlock_np
226 ; numberOfDistanceCodes = 1 + getBits(5)
230 sta inflateDynamicBlock_nd
231 ; numberOfTemporaryCodes = 4 + getBits(4)
235 sta inflateDynamicBlock_cnt
236 ; Get lengths of temporary codes in order stored in tempCodeLengthOrder
238 inflateDynamicBlock_1:
241 jsr getBits ; does not change Y
242 inflateDynamicBlock_2:
243 ldx tempCodeLengthOrder,y
244 sta literalCodeLength,x
246 cpy inflateDynamicBlock_cnt
247 bcc inflateDynamicBlock_1
250 bcc inflateDynamicBlock_2
251 ror literalCodeLength+19 ; C flag is set, so it will set b7
252 ; Build tree for temporary codes
255 ; Use temporary codes to get lengths for literal/length and distance codes
258 stx getNextLength_last
259 inflateDynamicBlock_3:
261 sta literalCodeLength,x
263 bne inflateDynamicBlock_3
264 inflateDynamicBlock_4:
268 cpx inflateDynamicBlock_np
269 bcc inflateDynamicBlock_4
271 bcs inflateDynamicBlock_6 ; branch always
272 inflateDynamicBlock_5:
276 bcs inflateDynamicBlock_6 ; branch always
277 inflateDynamicBlock_5:
281 inflateDynamicBlock_6:
283 bcc inflateDynamicBlock_5
284 inflateDynamicBlock_7:
287 beq inflateDynamicBlock_8
288 adc #DISTANCE_TREE-1 ; C flag is set
289 inflateDynamicBlock_8:
292 cpx inflateDynamicBlock_nd
293 bcc inflateDynamicBlock_7
294 ror endCodeLength,x ; C flag is set, so it will set b7
297 ; --------------------------------------------------------------------------
298 ; Decompress data block basing on given Huffman trees
310 sta (outputPointer),y
315 bcc inflateCodes_1 ; branch always
340 sta inflateCodes_src+1
341 ldx #inflateCodes_src
343 beq inflateCodes_1 ; branch always
345 ; --------------------------------------------------------------------------
346 ; Build Huffman trees basing on code lengths.
347 ; Lengths (in bits) are stored in *CodeLength tables.
348 ; A byte with highest bit set marks end of length table.
351 lda #<literalCodeLength
352 sta buildHuffmanTree_src
353 lda #>literalCodeLength
354 sta buildHuffmanTree_src+1
355 ; Clear bitsCount and bitsPointer_l
361 bne buildHuffmanTree_1
362 beq buildHuffmanTree_3 ; branch always
363 ; Count number of codes of each length
368 bne buildHuffmanTree_3
369 inc buildHuffmanTree_src+1
371 lda (buildHuffmanTree_src),y
372 bpl buildHuffmanTree_2
373 ; Calculate pointer for each length
382 lda bitsPointer_l+1,x
383 adc bitsPointer_l,x ; C flag is zero
384 bcc buildHuffmanTree_5
389 bcc buildHuffmanTree_4
390 lda #>literalCodeLength
391 sta buildHuffmanTree_src+1
393 bcs buildHuffmanTree_9 ; branch always
394 ; Put codes into their place in sorted table
396 beq buildHuffmanTree_7
398 lda bitsPointer_l-1,x
399 sta buildHuffmanTree_ptr
400 lda bitsPointer_h-1,x
401 sta buildHuffmanTree_ptr+1
405 sta (buildHuffmanTree_ptr),y
409 bne buildHuffmanTree_9
410 inc buildHuffmanTree_src+1
416 bpl buildHuffmanTree_8
418 lda (buildHuffmanTree_src),y
419 bpl buildHuffmanTree_6
422 ; --------------------------------------------------------------------------
423 ; Get next code length basing on temporary codes
426 stx getNextLength_index
429 ; Fetch a temporary code
431 ; Temporary code 0..15: put this length
435 ; Temporary code 16: repeat last length 3 + getBits(2) times
436 ; Temporary code 17: put zero length 3 + getBits(3) times
437 ; Temporary code 18: put zero length 11 + getBits(7) times
439 ldx tempExtraBits-16,y
440 lda tempBaseValue-16,y
447 lda getNextLength_last
449 sta getNextLength_last
450 ldx getNextLength_index
453 ; --------------------------------------------------------------------------
454 ; Read code basing on primary tree
460 ; --------------------------------------------------------------------------
461 ; Read code from input stream basing on tree given in X.
462 ; Return low byte of code in A.
463 ; For literal/length tree, C is: 0 if literal code, 1 if end or length code.
472 sbc bitsCount,x ; C flag is set
474 bcs fetchCode_1 ; branch always
481 lda (fetchCode_ptr),y
484 ; --------------------------------------------------------------------------
485 ; Read low byte of value (length or distance), basing on code A
489 ldx lengthExtraBits-1,y
490 lda lengthBaseValue_l-1,y
492 lda lengthBaseValue_h-1,y
497 ; --------------------------------------------------------------------------
498 ; Read X-bit number from input stream and add it to A.
499 ; In case of carry, Y is incremented.
500 ; If X > 8, only 8 bits are read.
501 ; On return X holds number of unread bits: X = (X > 8 ? X - 8 : 0);
525 ; --------------------------------------------------------------------------
526 ; Read single bit from input stream, return it in C flag
544 ror a ; C flag is set
555 ; --------------------------------------------------------------------------
561 ; --------------------------------------------------------------------------
562 ; Addresses of functions extracting different blocks
564 .byte <(inflateCopyBlock-1)
565 .byte <(inflateFixedBlock-1)
566 .byte <(inflateDynamicBlock-1)
568 .byte >(inflateCopyBlock-1)
569 .byte >(inflateFixedBlock-1)
570 .byte >(inflateDynamicBlock-1)
572 ; --------------------------------------------------------------------------
573 ; Tables for temporary codes
574 ; Value is BaseValue + getBits(ExtraBits)
576 ; Order, in which lengths of temporary codes are stored
578 .byte 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
584 ; Number of extra bits to read
588 ; --------------------------------------------------------------------------
589 ; Tables for length and distance codes
590 ; Value is BaseValue + getBits(ExtraBits)
594 .byte <3,<4,<5,<6,<7,<8,<9,<10
595 .byte <11,<13,<15,<17,<19,<23,<27,<31
596 .byte <35,<43,<51,<59,<67,<83,<99,<115
597 .byte <131,<163,<195,<227,<258
599 .byte <1,<2,<3,<4,<5,<7,<9,<13
600 .byte <17,<25,<33,<49,<65,<97,<129,<193
601 .byte <257,<385,<513,<769,<1025,<1537,<2049,<3073
602 .byte <4097,<6145,<8193,<12289,<16385,<24577
604 .byte >3,>4,>5,>6,>7,>8,>9,>10
605 .byte >11,>13,>15,>17,>19,>23,>27,>31
606 .byte >35,>43,>51,>59,>67,>83,>99,>115
607 .byte >131,>163,>195,>227,>258
609 .byte >1,>2,>3,>4,>5,>7,>9,>13
610 .byte >17,>25,>33,>49,>65,>97,>129,>193
611 .byte >257,>385,>513,>769,>1025,>1537,>2049,>3073
612 .byte >4097,>6145,>8193,>12289,>16385,>24577
614 ; Number of extra bits to read
616 .byte 0,0,0,0,0,0,0,0
617 .byte 1,1,1,1,2,2,2,2
618 .byte 3,3,3,3,4,4,4,4
621 .byte 0,0,0,0,1,1,2,2
622 .byte 3,3,4,4,5,5,6,6
623 .byte 7,7,8,8,9,9,10,10
624 .byte 11,11,12,12,13,13
626 ; --------------------------------------------------------------------------
633 ; Number of literal codes of each length in primary tree
634 ; (MAX_BITS bytes, overlap with literalCodeLength)
637 ; --------------------------------------------------------------------------
638 ; Data for building primary tree
640 ; Lengths of literal codes
646 ; Lengths of length codes
650 ; --------------------------------------------------------------------------
651 ; Data for building distance tree
653 ; Lengths of distance codes
656 ; For two unused codes in fixed trees and end-of-table flag
659 ; --------------------------------------------------------------------------
660 ; Huffman tree structure
662 ; Number of codes of each length
665 ; Pointer to sorted codes of each length