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

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