* GenComp - General fast LZW decompressor
* Copyright (C) 1992 Bryan Ford
*
* This file is part of BLZW, Bryan's LZW compressor.
*
* BLZW is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* BLZW is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.



* Register usage:
* d0.hw = Initial code countdown
* d0.w = Bit position in current longword
* d1.w = Code countdown
* d2.l = Code size mask
* d3.l = Next code number
* d4.l = Old_code * 4
* d5.l = Current code
* d6.l = Current character
* d7 = Various
* a0 = Compressed stream pointer
* a1 = Decompressed stream pointer
* a2 = Current code size
* a3 = Scratch
* a4 = String stack pointer
* a5 = String table: suffix character 0(a5,dn), prefix code * 2 2(a5,dn)
* a6 = Pointer to next entry in string table to fill

*** GenDecompress - Generic decompression routine - decompress any stream compressed with gencompress
* a0 = Pointer to compressed source stream
* a1 = Pointer to destination data
* a2 = Pointer to an area for the hash tables, of size found with GenDecompTableSize
* Returns:
* a0 = End of compressed input data
* a1 = End of uncompressed data (subtract start pointer to get final length)
GenDecompress
        movem.l d2-d7/a2-a6,-(sp)

        move.w  (a0)+,d1                ; Number of codes we can fill (d0.hw)
        moveq   #0,d0
        bset    d1,d0
        sub.w   #1<<SOURCEBITS+3,d0
        swap    d0

        move.w  #32,d0                  ; Initial bit offset (d0.w)

        add.w   (a0)+,a2                ; Top of string stack =
        move.l  a2,a5                   ; String table (a5)

        move.w  #$ff00,d4               ; Initialize first 256 table entries
        move.w  #256-1,d7

.tabinit
        move.w  d4,(a2)
        addq.w  #1,d4
        addq.w  #4,a2
        dbra    d7,.tabinit

        move.w  #$8000,(a2)             ; Initialize the special entries
        move.w  #$8001,4(a2)
        move.w  #$8002,8(a2)

        move.l  a5,a4                   ; Initialize string stack pointer

        moveq   #0,d2                   ; Zero out some upper words
        moveq   #0,d4
        moveq   #0,d6
        moveq   #0,d7

        bra     .resetloop

.storeloop
        move.w  d6,(a6)+                ; Store character in table
        move.w  d4,(a6)+                ; Store old_code * 2

.nostoreloop
        move.w  d5,d4                   ; Shift new_code * 2 to old_code * 2

.loop
        sub.w   a2,d0                   ; Find the next code
        bpl.b   .one
        addq.w  #2,a0
        addq.w  #8,d0
        addq.w  #8,d0
.one
        move.l  (a0),d5                 ; Grab the code * 2
        lsr.l   d0,d5
        and.l   d2,d5
        add.w   d5,d5

        lea     (a5,d5.l),a3            ; Check "for special case"
        add.l   d5,a3
        cmp.l   a6,a3
        blt.b   .notspecialcase
        move.b  d6,-(a4)                ; Push last character
        lea     (a5,d4.l),a3            ; Use old_code as new_code
        add.l   d4,a3
.notspecialcase

        move.w  (a3)+,d7                ; Get first suffix character
        bmi.b   .outsing
.traverse
        move.b  d7,-(a4)
        move.w  (a3),d7                 ; Get prefix code * 2
        lea     (a5,d7.l),a3
        add.l   d7,a3
        move.w  (a3)+,d7
        bpl.b   .traverse

.outmult
        move.b  d7,(a1)+                ; Stash the last character
        move.b  d7,d6

.unstack
        move.b  (a4)+,(a1)+             ; Copy the rest of the string
        cmp.l   a4,a5
        bne.b   .unstack

        dbra    d1,.storeloop            ; Make sure we're not overflowing

        moveq   #0,d1                   ; Stop filling until the next reset
        bra     .nostoreloop

.outsing
        subq.w  #3,d7                   ; Check for special codes
        bvs.b   .special
        addq.w  #3,d7

        move.b  d7,(a1)+                ; Output the character we got
        move.b  d7,d6

        cmp.l   a4,a5
        beq.b   .singnospecialcase
        move.b  (a4)+,(a1)+             ; Only the "special case" can cause this
.singnospecialcase

        dbra    d1,.storeloop            ; Make sure we're not overflowing

        moveq   #0,d1                   ; Stop filling until the next reset
        bra     .nostoreloop

.special
        addq.w  #1,d7                   ; What kind of special code?
        bvc.b   .notincsize

.incsize                                 ; $102 = Increase code size
        addq.w  #1,a2                   ; Add another bit
        add.w   d2,d2
        addq.w  #1,d2
        bra.b   .loop

.notincsize
        addq.w  #1,d7
        bvc.b   .out

.resetloop                               ; $101 = Reset table
        move.w  #STARTBITS,a2           ; Initial Number of bits per code (a2)

        move.w  #(1<<STARTBITS)-1,d2    ; Initial codemask (d2)

        lea     (1<<SOURCEBITS+3)*4(a5),a6 ; Initial table fill pointer (a6)

        swap    d0                      ; Start code countdown over (d1)
        move.w  d0,d1
        swap    d0

        sub.w   a2,d0                   ; Find the first code
        bpl.b   .two
        addq.w  #2,a0
        addq.w  #8,d0
        addq.w  #8,d0
.two
        move.l  (a0),d5                 ; Grab the code * 2
        lsr.l   d0,d5
        and.l   d2,d5

        move.w  d5,d4                   ; Initial old_code * 2 (d4)
        add.w   d4,d4
        move.w  d5,d6                   ; Initial character (d6)
        move.b  d5,(a1)+                ; Store first byte

        bra     .loop

.out                                     ; $100 = End marker
        movem.l (sp)+,d2-d7/a2-a6
        rts

*** GenDecompTableSize - Find the compression table size required for a particular compressed stream
* a0 = Pointer to compressed data stream
* Returns: d0 = Size in bytes of required hash tables
GenDecompTableSize
        moveq   #BYTESPERTABENT,d0	; Calculate the table size necessary
        move.w  (a0)+,d1
        lsl.l   d1,d0
        move.w  (a0),a0
        add.l   a0,d0
        rts