2 ; 2017-11-07, Piotr Fusik
4 ; unsigned __fastcall__ inflatemem (char* dest, const char* source);
6 ; NOTE: Be extremely careful with modifications, because this code is heavily
7 ; optimized for size (for example assumes certain register and flag values
8 ; when its internal routines return). Test with the gunzip65 sample.
14 .importzp sp, sreg, ptr1, ptr2, ptr3, ptr4
16 ; --------------------------------------------------------------------------
21 ; Argument values for getBits.
33 DISTANCE_TREE = TREE_SIZE
36 LENGTH_SYMBOLS = 1+29+2 ; EOF, 29 length symbols, two unused symbols
38 CONTROL_SYMBOLS = LENGTH_SYMBOLS+DISTANCE_SYMBOLS
41 ; --------------------------------------------------------------------------
46 ; Pointer to the compressed data.
47 inputPointer := ptr1 ; 2 bytes
49 ; Pointer to the uncompressed data.
50 outputPointer := ptr2 ; 2 bytes
53 ; As far as there is no conflict, same memory locations are used
54 ; for different variables.
56 inflateStored_pageCounter := ptr3 ; 1 byte
57 inflateDynamic_symbol := ptr3 ; 1 byte
58 inflateDynamic_lastLength := ptr3+1 ; 1 byte
59 .assert ptr4 = ptr3 + 2, error, "Need three bytes for inflateDynamic_tempCodes"
60 inflateDynamic_tempCodes := ptr3+1 ; 3 bytes
61 inflateDynamic_allCodes := inflateDynamic_tempCodes+1 ; 1 byte
62 inflateDynamic_primaryCodes := inflateDynamic_tempCodes+2 ; 1 byte
63 inflateCodes_sourcePointer := ptr3 ; 2 bytes
64 inflateCodes_lengthMinus2 := ptr4 ; 1 byte
65 getBits_base := sreg ; 1 byte
66 getBit_buffer := sreg+1 ; 1 byte
69 ; --------------------------------------------------------------------------
76 ; inputPointer = source
79 ; outputPointer = dest
91 ; Get a bit of EOF and two bits of block type
97 ; A and Z contain block type, C contains EOF flag
100 bne inflateCompressed
102 ; Decompress a 'stored' data block.
104 sty getBit_buffer ; ignore bits until byte boundary
105 jsr getWord ; skip the length we don't need
106 jsr getWord ; get the one's complement length
107 sta inflateStored_pageCounter
108 bcs inflateStored_firstByte ; jmp
109 inflateStored_copyByte:
114 bcc inflateCodes_loop
115 inflateStored_firstByte:
117 bne inflateStored_copyByte
118 inc inflateStored_pageCounter
119 bne inflateStored_copyByte
121 ; Block decompressed.
124 bcc inflate_blockLoop
126 ; Decompression complete.
127 ; return outputPointer - dest
142 ; Decompress a Huffman-coded data block
143 ; A=1: fixed block, initialize with fixed codes
144 ; A=2: dynamic block, start by clearing all code lengths
145 ; A=3: invalid compressed data, not handled in this routine
149 inflateCompressed_setCodeLengths:
151 beq inflateCompressed_setLiteralCodeLength
152 ; fixed Huffman literal codes:
158 inflateCompressed_setLiteralCodeLength:
159 sta literalSymbolCodeLength,y
160 beq inflateCompressed_setControlCodeLength
161 ; fixed Huffman control codes:
164 ; 2 meaningless 8-bit codes
165 ; 30 5-bit distance codes
168 bcs inflateCompressed_setControlCodeLength
170 adc #$100+2-DISTANCE_TREE
171 inflateCompressed_setControlCodeLength:
173 bcs inflateCompressed_noControlSymbol
174 sta controlSymbolCodeLength,y
175 inflateCompressed_noControlSymbol:
177 bne inflateCompressed_setCodeLengths
188 beq inflate_nextBlock
189 ; Copy sequence from look-behind buffer
193 bcc inflateCodes_setSequenceLength
197 bcs inflateCodes_setSequenceLength
205 jsr getAMinus1BitsMax8
208 inflateCodes_setSequenceLength:
209 sta inflateCodes_lengthMinus2
213 bcc inflateCodes_setOffsetLowByte
216 jsr getAMinus1BitsMax8
217 inflateCodes_setOffsetLowByte:
219 sta inflateCodes_sourcePointer
222 bcc inflateCodes_setOffsetHighByte
223 lda getNPlus1Bits_mask-10,x
226 inflateCodes_setOffsetHighByte:
230 sta inflateCodes_sourcePointer+1
233 inflateCodes_copyByte:
235 dec inflateCodes_lengthMinus2
236 bne inflateCodes_copyByte
237 beq inflateCodes_loop ; jmp
240 ; Decompress a block reading Huffman trees first
242 ; numberOfPrimaryCodes = 257 + getBits(5)
243 ; numberOfDistanceCodes = 1 + getBits(5)
244 ; numberOfTemporaryCodes = 4 + getBits(4)
246 inflateDynamic_getHeader:
247 lda inflateDynamic_headerBits-1,x
250 adc inflateDynamic_headerBase-1,x
251 sta inflateDynamic_tempCodes-1,x
253 bne inflateDynamic_getHeader
255 ; Get lengths of temporary codes in the order stored in inflateDynamic_tempSymbols
257 inflateDynamic_getTempCodeLengths:
260 ldy inflateDynamic_tempSymbols,x
261 sta literalSymbolCodeLength,y
264 cpx inflateDynamic_tempCodes
265 bcc inflateDynamic_getTempCodeLengths
267 ; Build the tree for temporary codes
270 ; Use temporary codes to get lengths of literal/length and distance codes
273 inflateDynamic_decodeLength:
276 stx inflateDynamic_symbol
278 ; Fetch a temporary code
280 ; Temporary code 0..15: put this length
281 bpl inflateDynamic_storeLengths
282 ; Temporary code 16: repeat last length 3 + getBits(2) times
283 ; Temporary code 17: put zero length 3 + getBits(3) times
284 ; Temporary code 18: put zero length 11 + getBits(7) times
288 bcc inflateDynamic_code16
289 beq inflateDynamic_code17
292 inflateDynamic_code17:
294 sty inflateDynamic_lastLength
295 inflateDynamic_code16:
297 lda inflateDynamic_lastLength
300 inflateDynamic_storeLengths:
303 ldx inflateDynamic_symbol
304 inflateDynamic_storeLength:
305 bcc inflateDynamic_controlSymbolCodeLength
306 sta literalSymbolCodeLength,x
309 inflateDynamic_storeNext:
311 bne inflateDynamic_storeLength
312 sta inflateDynamic_lastLength
313 beq inflateDynamic_decodeLength ; jmp
314 inflateDynamic_controlSymbolCodeLength:
315 cpx inflateDynamic_primaryCodes
316 bcc inflateDynamic_storeControl
317 ; the code lengths we skip here were zero-initialized
318 ; in inflateCompressed_setControlCodeLength
319 bne inflateDynamic_noStartDistanceTree
321 inflateDynamic_noStartDistanceTree:
323 inflateDynamic_storeControl:
324 sta controlSymbolCodeLength,x
326 cpx inflateDynamic_allCodes
327 bcc inflateDynamic_storeNext
332 ; Build Huffman trees basing on code lengths (in bits)
333 ; stored in the *SymbolCodeLength arrays
335 ; Clear nBitCode_literalCount, nBitCode_controlCount
338 buildHuffmanTree_clear:
339 sta nBitCode_clearFrom,y
341 bne buildHuffmanTree_clear
342 ; Count number of codes of each length
344 buildHuffmanTree_countCodeLengths:
345 ldx literalSymbolCodeLength,y
346 inc nBitCode_literalCount,x
347 bne buildHuffmanTree_notAllLiterals
348 stx allLiteralsCodeLength
349 buildHuffmanTree_notAllLiterals:
351 bcs buildHuffmanTree_noControlSymbol
352 ldx controlSymbolCodeLength,y
353 inc nBitCode_controlCount,x
354 buildHuffmanTree_noControlSymbol:
356 bne buildHuffmanTree_countCodeLengths
357 ; Calculate offsets of symbols sorted by code length
359 ldx #$100-4*TREE_SIZE
360 buildHuffmanTree_calculateOffsets:
361 sta nBitCode_literalOffset+4*TREE_SIZE-$100,x
363 adc nBitCode_literalCount+4*TREE_SIZE-$100,x
365 bne buildHuffmanTree_calculateOffsets
366 ; Put symbols in their place in the sorted array
368 buildHuffmanTree_assignCode:
370 ldx literalSymbolCodeLength,y
371 ldy nBitCode_literalOffset,x
372 inc nBitCode_literalOffset,x
373 sta codeToLiteralSymbol,y
376 bcs buildHuffmanTree_noControlSymbol2
377 ldx controlSymbolCodeLength,y
378 ldy nBitCode_controlOffset,x
379 inc nBitCode_controlOffset,x
380 sta codeToControlSymbol,y
382 buildHuffmanTree_noControlSymbol2:
384 bne buildHuffmanTree_assignCode
387 ; Read Huffman code using the primary tree
390 ; Read a code from input using the tree specified in X.
391 ; Return low byte of this code in A.
392 ; Return C flag reset for literal code, set for length code.
401 ; are all 256 literal codes of this length?
402 cpx allLiteralsCodeLength
403 beq fetchCode_allLiterals
404 ; is it literal code of length X?
406 sbc nBitCode_literalCount,x
407 bcs fetchCode_notLiteral
410 adc nBitCode_literalOffset,x
412 lda codeToLiteralSymbol,x
413 fetchCode_allLiterals:
416 ; code >= 256, must be control
419 sbc nBitCode_literalCount,x
421 ; is it control code of length X?
422 fetchCode_notLiteral:
424 sbc nBitCode_controlCount,x
425 bcs fetchCode_nextBit
428 adc nBitCode_controlOffset,x
430 lda codeToControlSymbol,x
431 and #$1f ; make distance symbols zero-based
436 ; Read A minus 1 bits, but no more than 8
442 lda getNPlus1Bits_mask-2,x
445 getBits_normalizeLoop:
448 bcc getBits_normalizeLoop
464 ; Read one bit, return in the C flag
482 ; Copy a previously written byte
485 lda (inflateCodes_sourcePointer),y
490 sta (outputPointer),y
494 inc inflateCodes_sourcePointer+1
499 ; --------------------------------------------------------------------------
507 .byte GET_1_BIT,GET_2_BITS,GET_3_BITS,GET_4_BITS,GET_5_BITS,GET_6_BITS,GET_7_BITS
509 inflateDynamic_tempSymbols:
510 .byte GET_2_BITS,GET_3_BITS,GET_7_BITS,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
512 inflateDynamic_headerBits:
513 .byte GET_4_BITS,GET_5_BITS,GET_5_BITS
514 inflateDynamic_headerBase:
515 .byte 3,LENGTH_SYMBOLS,0
518 ; --------------------------------------------------------------------------
525 ; Data for building trees.
527 literalSymbolCodeLength:
529 controlSymbolCodeLength:
535 nBitCode_literalCount:
537 nBitCode_controlCount:
539 nBitCode_literalOffset:
541 nBitCode_controlOffset:
543 allLiteralsCodeLength: