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

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