git.sur5r.net Git - cc65/blob - libsrc/zlib/inflatemem.s

   1 ;
   2 ; 2003-09-21, Piotr Fusik
   3 ; 2016-07-19, Greg King
   4 ;
   5 ; unsigned __fastcall__ inflatemem (char* dest, const char* source);
   6 ;
   7
   8         .export         _inflatemem
   9
  10         .import         incsp2
  11         .importzp       sp, sreg, ptr1, ptr2, ptr3, ptr4, tmp1
  12
  13         .macpack        cpu
  14
  15 ; --------------------------------------------------------------------------
  16 ;
  17 ; Constants
  18 ;
  19
  20 ; Maximum length of a Huffman code.
  21 MAX_BITS      = 15
  22
  23 ; All Huffman trees are stored in the bitsCount, bitsPointer_l
  24 ; and bitsPointer_h arrays.  There may be two trees: the literal/length tree
  25 ; and the distance tree, or just one - the temporary tree.
  26
  27 ; Index in the mentioned arrays for the beginning of the literal/length tree
  28 ; or the temporary tree.
  29 PRIMARY_TREE  = 0
  30
  31 ; Index in the mentioned arrays for the beginning of the distance tree.
  32 DISTANCE_TREE = MAX_BITS
  33
  34 ; Size of each array.
  35 TREES_SIZE    = 2*MAX_BITS
  36
  37
  38 ; --------------------------------------------------------------------------
  39 ;
  40 ; Page zero
  41 ;
  42
  43 ; Pointer to the compressed data.
  44 inputPointer            :=      ptr1    ; 2 bytes
  45
  46 ; Pointer to the uncompressed data.
  47 outputPointer           :=      ptr2    ; 2 bytes
  48
  49 ; Local variables.
  50 ; As far as there is no conflict, same memory locations are used
  51 ; for different variables.
  52
  53 inflateDynamicBlock_cnt :=      ptr3    ; 1 byte
  54 inflateCodes_src        :=      ptr3    ; 2 bytes
  55 buildHuffmanTree_src    :=      ptr3    ; 2 bytes
  56 getNextLength_last      :=      ptr3    ; 1 byte
  57 getNextLength_index     :=      ptr3+1  ; 1 byte
  58
  59 buildHuffmanTree_ptr    :=      ptr4    ; 2 bytes
  60 fetchCode_ptr           :=      ptr4    ; 2 bytes
  61 getBits_tmp             :=      ptr4    ; 1 byte
  62
  63 moveBlock_len           :=      sreg    ; 2 bytes
  64 inflateDynamicBlock_np  :=      sreg    ; 1 byte
  65 inflateDynamicBlock_nd  :=      sreg+1  ; 1 byte
  66
  67 getBit_hold             :=      tmp1    ; 1 byte
  68
  69
  70 ; --------------------------------------------------------------------------
  71 ;
  72 ; Code
  73 ;
  74
  75 _inflatemem:
  76
  77 ; inputPointer = source
  78         sta     inputPointer
  79         stx     inputPointer+1
  80 ; outputPointer = dest
  81 .if (.cpu & CPU_ISET_65SC02)
  82         lda     (sp)
  83         ldy     #1
  84 .else
  85         ldy     #0
  86         lda     (sp),y
  87         iny
  88 .endif
  89         sta     outputPointer
  90         lda     (sp),y
  91         sta     outputPointer+1
  92
  93 ;       ldy     #1
  94         sty     getBit_hold
  95 inflatemem_1:
  96 ; Get a bit of EOF and two bits of block type
  97         ldx     #3
  98         lda     #0
  99         jsr     getBits
 100         lsr     a
 101 ; A and Z contain block type, C contains EOF flag
 102 ; Save EOF flag
 103         php
 104 ; Go to the routine decompressing this block
 105         jsr     callExtr
 106         plp
 107         bcc     inflatemem_1
 108 ; C flag is set!
 109
 110 ; return outputPointer - dest;
 111         lda     outputPointer
 112 .if (.cpu & CPU_ISET_65SC02)
 113         sbc     (sp)            ; C flag is set
 114         ldy     #1
 115 .else
 116         ldy     #0
 117         sbc     (sp),y          ; C flag is set
 118         iny
 119 .endif
 120         pha
 121         lda     outputPointer+1
 122         sbc     (sp),y
 123         tax
 124         pla
 125 ; pop dest
 126         jmp     incsp2
 127
 128 ; --------------------------------------------------------------------------
 129 ; Go to proper block decoding routine.
 130
 131 callExtr:
 132         bne     inflateCompressedBlock
 133
 134 ; --------------------------------------------------------------------------
 135 ; Decompress a 'stored' data block.
 136
 137 inflateCopyBlock:
 138 ; Ignore bits until byte boundary
 139         ldy     #1
 140         sty     getBit_hold
 141 ; Get 16-bit length
 142         ldx     #0
 143         lda     (inputPointer,x)
 144         sta     moveBlock_len
 145         lda     (inputPointer),y
 146         sta     moveBlock_len+1
 147 ; Skip the length and one's complement of it
 148         lda     #4
 149         clc
 150         adc     inputPointer
 151         sta     inputPointer
 152         bcc     moveBlock
 153         inc     inputPointer+1
 154 ;       jmp     moveBlock
 155
 156 ; --------------------------------------------------------------------------
 157 ; Copy block of length moveBlock_len from (0,x) to the output.
 158
 159 moveBlock:
 160         ldy     moveBlock_len
 161         beq     moveBlock_1
 162 .if (.cpu & CPU_ISET_65SC02)
 163 .else
 164         ldy     #0
 165 .endif
 166         inc     moveBlock_len+1
 167 moveBlock_1:
 168         lda     (inputPointer,x)
 169 .if (.cpu & CPU_ISET_65SC02)
 170         sta     (outputPointer)
 171 .else
 172         sta     (outputPointer),y
 173 .endif
 174         inc     inputPointer
 175         bne     moveBlock_2
 176         inc     inputPointer+1
 177 moveBlock_2:
 178         inc     outputPointer
 179         bne     moveBlock_3
 180         inc     outputPointer+1
 181 moveBlock_3:
 182 .if (.cpu & CPU_ISET_65SC02)
 183         dey
 184 .else
 185         dec     moveBlock_len
 186 .endif
 187         bne     moveBlock_1
 188         dec     moveBlock_len+1
 189         bne     moveBlock_1
 190         rts
 191
 192 ; --------------------------------------------------------------------------
 193 ; Decompress a Huffman-coded data block
 194 ; (A = 1: fixed, A = 2: dynamic).
 195
 196 inflateCompressedBlock:
 197         lsr     a
 198         bne     inflateDynamicBlock
 199 ; Note: inflateDynamicBlock may assume that A = 1
 200
 201 ; --------------------------------------------------------------------------
 202 ; Decompress a Huffman-coded data block with default Huffman trees
 203 ; (defined by the DEFLATE format):
 204 ; literalCodeLength:  144 times 8, 112 times 9
 205 ; endCodeLength:      7
 206 ; lengthCodeLength:   23 times 7, 6 times 8
 207 ; distanceCodeLength: 30 times 5+DISTANCE_TREE, 2 times 8
 208 ;                     (two 8-bit codes from the primary tree are not used).
 209
 210 inflateFixedBlock:
 211         ldx     #159
 212         stx     distanceCodeLength+32
 213         lda     #8
 214 inflateFixedBlock_1:
 215         sta     literalCodeLength-1,x
 216         sta     literalCodeLength+159-1,x
 217         dex
 218         bne     inflateFixedBlock_1
 219         ldx     #112
 220 ;       lda     #9
 221 inflateFixedBlock_2:
 222         inc     literalCodeLength+144-1,x       ; sta
 223         dex
 224         bne     inflateFixedBlock_2
 225         ldx     #24
 226 ;       lda     #7
 227 inflateFixedBlock_3:
 228         dec     endCodeLength-1,x       ; sta
 229         dex
 230         bne     inflateFixedBlock_3
 231         ldx     #30
 232         lda     #5+DISTANCE_TREE
 233 inflateFixedBlock_4:
 234         sta     distanceCodeLength-1,x
 235         dex
 236         bne     inflateFixedBlock_4
 237         beq     inflateCodes            ; branch always
 238
 239 ; --------------------------------------------------------------------------
 240 ; Decompress a Huffman-coded data block, reading Huffman trees first.
 241
 242 inflateDynamicBlock:
 243 ; numberOfPrimaryCodes = 257 + getBits(5)
 244         ldx     #5
 245 ;       lda     #1
 246         jsr     getBits
 247         sta     inflateDynamicBlock_np
 248 ; numberOfDistanceCodes = 1 + getBits(5)
 249         ldx     #5
 250         lda     #1+29+1
 251         jsr     getBits
 252         sta     inflateDynamicBlock_nd
 253 ; numberOfTemporaryCodes = 4 + getBits(4)
 254         lda     #4
 255         tax
 256         jsr     getBits
 257         sta     inflateDynamicBlock_cnt
 258 ; Get lengths of temporary codes in the order stored in tempCodeLengthOrder
 259         txa                     ; lda #0
 260         tay
 261 inflateDynamicBlock_1:
 262         ldx     #3              ; A = 0
 263         jsr     getBits         ; does not change Y
 264 inflateDynamicBlock_2:
 265         ldx     tempCodeLengthOrder,y
 266         sta     literalCodeLength,x
 267         lda     #0
 268         iny
 269         cpy     inflateDynamicBlock_cnt
 270         bcc     inflateDynamicBlock_1
 271         cpy     #19
 272         bcc     inflateDynamicBlock_2
 273         ror     literalCodeLength+19    ; C flag is set, so this will set b7
 274 ; Build the tree for temporary codes
 275         jsr     buildHuffmanTree
 276
 277 ; Use temporary codes to get lengths of literal/length and distance codes
 278         ldx     #0
 279         ldy     #1
 280         stx     getNextLength_last
 281 inflateDynamicBlock_3:
 282         jsr     getNextLength
 283         sta     literalCodeLength,x
 284         inx
 285         bne     inflateDynamicBlock_3
 286 inflateDynamicBlock_4:
 287         jsr     getNextLength
 288 inflateDynamicBlock_5:
 289         sta     endCodeLength,x
 290         inx
 291         cpx     inflateDynamicBlock_np
 292         bcc     inflateDynamicBlock_4
 293         lda     #0
 294         cpx     #1+29
 295         bcc     inflateDynamicBlock_5
 296 inflateDynamicBlock_6:
 297         jsr     getNextLength
 298         cmp     #0
 299         beq     inflateDynamicBlock_7
 300         adc     #DISTANCE_TREE-1        ; C flag is set
 301 inflateDynamicBlock_7:
 302         sta     endCodeLength,x
 303         inx
 304         cpx     inflateDynamicBlock_nd
 305         bcc     inflateDynamicBlock_6
 306         ror     endCodeLength,x         ; C flag is set, so this will set b7
 307 ;       jmp     inflateCodes
 308
 309 ; --------------------------------------------------------------------------
 310 ; Decompress a data block basing on given Huffman trees.
 311
 312 inflateCodes:
 313         jsr     buildHuffmanTree
 314 inflateCodes_1:
 315         jsr     fetchPrimaryCode
 316         bcs     inflateCodes_2
 317 ; Literal code
 318 .if (.cpu & CPU_ISET_65SC02)
 319         sta     (outputPointer)
 320 .else
 321         ldy     #0
 322         sta     (outputPointer),y
 323 .endif
 324         inc     outputPointer
 325         bne     inflateCodes_1
 326         inc     outputPointer+1
 327         bcc     inflateCodes_1  ; branch always
 328 ; End of block
 329 inflateCodes_ret:
 330         rts
 331 inflateCodes_2:
 332         beq     inflateCodes_ret
 333 ; Restore a block from the look-behind buffer
 334         jsr     getValue
 335         sta     moveBlock_len
 336         tya
 337         jsr     getBits
 338         sta     moveBlock_len+1
 339         ldx     #DISTANCE_TREE
 340         jsr     fetchCode
 341         jsr     getValue
 342         sec
 343         eor     #$ff
 344         adc     outputPointer
 345         sta     inflateCodes_src
 346         php
 347         tya
 348         jsr     getBits
 349         plp
 350         eor     #$ff
 351         adc     outputPointer+1
 352         sta     inflateCodes_src+1
 353         ldx     #inflateCodes_src
 354         jsr     moveBlock
 355         beq     inflateCodes_1  ; branch always
 356
 357 ; --------------------------------------------------------------------------
 358 ; Build Huffman trees basing on code lengths (in bits).
 359 ; stored in the *CodeLength arrays.
 360 ; A byte with its highest bit set marks the end.
 361
 362 buildHuffmanTree:
 363         lda     #<literalCodeLength
 364         sta     buildHuffmanTree_src
 365         lda     #>literalCodeLength
 366         sta     buildHuffmanTree_src+1
 367 ; Clear bitsCount and bitsPointer_l
 368         ldy     #2*TREES_SIZE+1
 369         lda     #0
 370 buildHuffmanTree_1:
 371         sta     bitsCount-1,y
 372         dey
 373         bne     buildHuffmanTree_1
 374         beq     buildHuffmanTree_3      ; branch always
 375 ; Count number of codes of each length
 376 buildHuffmanTree_2:
 377         tax
 378         inc     bitsPointer_l,x
 379         iny
 380         bne     buildHuffmanTree_3
 381         inc     buildHuffmanTree_src+1
 382 buildHuffmanTree_3:
 383         lda     (buildHuffmanTree_src),y
 384         bpl     buildHuffmanTree_2
 385 ; Calculate a pointer for each length
 386         ldx     #0
 387         lda     #<sortedCodes
 388         ldy     #>sortedCodes
 389         clc
 390 buildHuffmanTree_4:
 391         sta     bitsPointer_l,x
 392         tya
 393         sta     bitsPointer_h,x
 394         lda     bitsPointer_l+1,x
 395         adc     bitsPointer_l,x         ; C flag is zero
 396         bcc     buildHuffmanTree_5
 397         iny
 398 buildHuffmanTree_5:
 399         inx
 400         cpx     #TREES_SIZE
 401         bcc     buildHuffmanTree_4
 402         lda     #>literalCodeLength
 403         sta     buildHuffmanTree_src+1
 404         ldy     #0
 405         bcs     buildHuffmanTree_9      ; branch always
 406 ; Put codes into their place in sorted table
 407 buildHuffmanTree_6:
 408         beq     buildHuffmanTree_7
 409         tax
 410         lda     bitsPointer_l-1,x
 411         sta     buildHuffmanTree_ptr
 412         lda     bitsPointer_h-1,x
 413         sta     buildHuffmanTree_ptr+1
 414         tya
 415         ldy     bitsCount-1,x
 416         inc     bitsCount-1,x
 417         sta     (buildHuffmanTree_ptr),y
 418         tay
 419 buildHuffmanTree_7:
 420         iny
 421         bne     buildHuffmanTree_9
 422         inc     buildHuffmanTree_src+1
 423         ldx     #MAX_BITS-1
 424 buildHuffmanTree_8:
 425         lda     bitsCount,x
 426         sta     literalCount,x
 427         dex
 428         bpl     buildHuffmanTree_8
 429 buildHuffmanTree_9:
 430         lda     (buildHuffmanTree_src),y
 431         bpl     buildHuffmanTree_6
 432         rts
 433
 434 ; --------------------------------------------------------------------------
 435 ; Decode next code length using temporary codes.
 436
 437 getNextLength:
 438         stx     getNextLength_index
 439         dey
 440         bne     getNextLength_1
 441 ; Fetch a temporary code
 442         jsr     fetchPrimaryCode
 443 ; Temporary code 0..15: put this length
 444         ldy     #1
 445         cmp     #16
 446         bcc     getNextLength_2
 447 ; Temporary code 16: repeat last length 3 + getBits(2) times
 448 ; Temporary code 17: put zero length 3 + getBits(3) times
 449 ; Temporary code 18: put zero length 11 + getBits(7) times
 450         tay
 451         ldx     tempExtraBits-16,y
 452         lda     tempBaseValue-16,y
 453         jsr     getBits
 454         cpy     #17
 455         tay
 456         txa                     ; lda #0
 457         bcs     getNextLength_2
 458 getNextLength_1:
 459         lda     getNextLength_last
 460 getNextLength_2:
 461         sta     getNextLength_last
 462         ldx     getNextLength_index
 463         rts
 464
 465 ; --------------------------------------------------------------------------
 466 ; Read a code basing on the primary tree.
 467
 468 fetchPrimaryCode:
 469         ldx     #PRIMARY_TREE
 470 ;       jmp     fetchCode
 471
 472 ; --------------------------------------------------------------------------
 473 ; Read a code from input basing on the tree specified in X.
 474 ; Return low byte of this code in A.
 475 ; For the literal/length tree, the C flag is set if the code is non-literal.
 476
 477 fetchCode:
 478         lda     #0
 479 fetchCode_1:
 480         jsr     getBit
 481         rol     a
 482         inx
 483         sec
 484         sbc     bitsCount-1,x
 485         bcs     fetchCode_1
 486         adc     bitsCount-1,x   ; C flag is zero
 487         cmp     literalCount-1,x
 488         sta     fetchCode_ptr
 489         ldy     bitsPointer_l-1,x
 490         lda     bitsPointer_h-1,x
 491         sta     fetchCode_ptr+1
 492         lda     (fetchCode_ptr),y
 493         rts
 494
 495 ; --------------------------------------------------------------------------
 496 ; Decode low byte of a value (length or distance), basing on the code in A.
 497 ; The result is the base value for this code plus some bits read from input.
 498
 499 getValue:
 500         tay
 501         ldx     lengthExtraBits-1,y
 502         lda     lengthBaseValue_l-1,y
 503         pha
 504         lda     lengthBaseValue_h-1,y
 505         tay
 506         pla
 507 ;       jmp     getBits
 508
 509 ; --------------------------------------------------------------------------
 510 ; Read X-bit number from the input and add it to A.
 511 ; Increment Y if overflow.
 512 ; If X > 8, read only 8 bits.
 513 ; On return X holds number of unread bits: X = (X > 8 ? X - 8 : 0);
 514
 515 getBits:
 516         cpx     #0
 517         beq     getBits_ret
 518 .if (.cpu & CPU_ISET_65SC02)
 519         stz     getBits_tmp
 520         dec     getBits_tmp
 521 .else
 522         pha
 523         lda     #$ff
 524         sta     getBits_tmp
 525         pla
 526 .endif
 527 getBits_1:
 528         jsr     getBit
 529         bcc     getBits_2
 530         sbc     getBits_tmp     ; C flag is set
 531         bcc     getBits_2
 532         iny
 533 getBits_2:
 534         dex
 535         beq     getBits_ret
 536         asl     getBits_tmp
 537         bmi     getBits_1
 538 getBits_ret:
 539         rts
 540
 541 ; --------------------------------------------------------------------------
 542 ; Read a single bit from input, return it in the C flag.
 543
 544 getBit:
 545         lsr     getBit_hold
 546         bne     getBit_ret
 547         pha
 548 .if (.cpu & CPU_ISET_65SC02)
 549         lda     (inputPointer)
 550 .else
 551         sty     getBit_hold
 552         ldy     #0
 553         lda     (inputPointer),y
 554         ldy     getBit_hold
 555 .endif
 556         inc     inputPointer
 557         bne     getBit_1
 558         inc     inputPointer+1
 559 getBit_1:
 560         ror     a               ; (C flag was set)
 561         sta     getBit_hold
 562         pla
 563 getBit_ret:
 564         rts
 565
 566
 567 ; --------------------------------------------------------------------------
 568 ;
 569 ; Constant data
 570 ;
 571
 572         .rodata
 573 ; --------------------------------------------------------------------------
 574 ; Arrays for the temporary codes.
 575
 576 ; Order, in which lengths of the temporary codes are stored.
 577 tempCodeLengthOrder:
 578         .byte   16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
 579
 580 ; Base values.
 581 tempBaseValue:
 582         .byte   3,3,11
 583
 584 ; Number of extra bits to read.
 585 tempExtraBits:
 586         .byte   2,3,7
 587
 588 ; --------------------------------------------------------------------------
 589 ; Arrays for the length and distance codes.
 590
 591 ; Base values.
 592 lengthBaseValue_l:
 593         .byte   <3,<4,<5,<6,<7,<8,<9,<10
 594         .byte   <11,<13,<15,<17,<19,<23,<27,<31
 595         .byte   <35,<43,<51,<59,<67,<83,<99,<115
 596         .byte   <131,<163,<195,<227,<258
 597 distanceBaseValue_l:
 598         .byte   <1,<2,<3,<4,<5,<7,<9,<13
 599         .byte   <17,<25,<33,<49,<65,<97,<129,<193
 600         .byte   <257,<385,<513,<769,<1025,<1537,<2049,<3073
 601         .byte   <4097,<6145,<8193,<12289,<16385,<24577
 602 lengthBaseValue_h:
 603         .byte   >3,>4,>5,>6,>7,>8,>9,>10
 604         .byte   >11,>13,>15,>17,>19,>23,>27,>31
 605         .byte   >35,>43,>51,>59,>67,>83,>99,>115
 606         .byte   >131,>163,>195,>227,>258
 607 distanceBaseValue_h:
 608         .byte   >1,>2,>3,>4,>5,>7,>9,>13
 609         .byte   >17,>25,>33,>49,>65,>97,>129,>193
 610         .byte   >257,>385,>513,>769,>1025,>1537,>2049,>3073
 611         .byte   >4097,>6145,>8193,>12289,>16385,>24577
 612
 613 ; Number of extra bits to read.
 614 lengthExtraBits:
 615         .byte   0,0,0,0,0,0,0,0
 616         .byte   1,1,1,1,2,2,2,2
 617         .byte   3,3,3,3,4,4,4,4
 618         .byte   5,5,5,5,0
 619 distanceExtraBits:
 620         .byte   0,0,0,0,1,1,2,2
 621         .byte   3,3,4,4,5,5,6,6
 622         .byte   7,7,8,8,9,9,10,10
 623         .byte   11,11,12,12,13,13
 624
 625
 626 ; --------------------------------------------------------------------------
 627 ;
 628 ; Uninitialised data
 629 ;
 630
 631         .bss
 632
 633 ; Number of literal codes of each length in the primary tree
 634 ; (MAX_BITS bytes, overlap with literalCodeLength).
 635 literalCount:
 636
 637 ; --------------------------------------------------------------------------
 638 ; Data for building the primary tree.
 639
 640 ; Lengths of literal codes.
 641 literalCodeLength:
 642         .res    256
 643 ; Length of the end code.
 644 endCodeLength:
 645         .res    1
 646 ; Lengths of length codes.
 647 lengthCodeLength:
 648         .res    29
 649
 650 ; --------------------------------------------------------------------------
 651 ; Data for building the distance tree.
 652
 653 ; Lengths of distance codes.
 654 distanceCodeLength:
 655         .res    30
 656 ; For two unused codes in the fixed trees and an 'end' mark.
 657         .res    3
 658
 659 ; --------------------------------------------------------------------------
 660 ; The Huffman trees.
 661
 662 ; Number of codes of each length.
 663 bitsCount:
 664         .res    TREES_SIZE
 665 ; Pointers to sorted codes of each length.
 666 bitsPointer_l:
 667         .res    TREES_SIZE+1
 668 bitsPointer_h:
 669         .res    TREES_SIZE
 670
 671 ; Sorted codes.
 672 sortedCodes:
 673         .res    256+1+29+30+2