* GenComp - General fast LZW compressor
* 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.l = Number of bytes remaining in source
* d1.w = Number of characters in current string
* d2.w = Current output bit position
* d3.w = Nextcode - Next code slot to fill, -1 if table full
* d4.l = Last code
* d5.l = Current character
* d6 = Scratch
* d7 = Scratch
* a0 = Source pointer
* a1 = Destination pointer
* a2 = ss_TabSize*6
* a3 = outbits - Number of bits per output code
* a4 = Scratch
* a5 = Append char (0,a5,Dn*6), prefix code (2,a5,Dn*6), code value (4,a5,Dn*6)
* a6 = Character shift for hashing

                rsreset
ss_IncCode      rs.w    1       ; Last code before incrementing table size
ss_PrevRatio    rs.w    1       ; Revious compression ratio
ss_MaxDest      rs.l    1       ; Pointer past end of destination
ss_Dest         rs.l    1       ; Pointer to destination stream
ss_TabSize      rs.w    1       ; Compression table size
ss_MaxString    rs.w    1       ; Max string size
ss_MaxBits      rs.w    1       ; Max number of compression bits
ss_pad          rs.w    1
ss_SMarker      rs.l    1       ; Source marker for compression ratio checking
ss_DMarker      rs.l    1       ; Dest marker
ss_Size         rs.b    0

*** GenCompress - General LZW compression routine - compress any byte stream
* d0.l = Length of source
* d1.l = Maximum number of bits to compress with
* a0 = Pointer to source byte stream
* a1 = Pointer to destination area (at least as big as source)
* a2 = Pointer to an area for the hash tables, of size found with gentablesize
* Returns: d0 = Total byte size of compressed data, null if the data did not compress
GenCompress
        movem.l d2-d7/a2-a6,-(sp)
        lea     (-ss_Size,sp),sp

        moveq   #$7f,d2                 ; Refuse to compress insultingly small streams...
        cmp.l   d2,d0
        bls     outerr

        move.l  a1,(ss_Dest,sp)         ; Save original dest to find final length later

        move.l  d0,d2                   ; Find max destination address
        andi.w  #$ffe0,d2
        add.l   d2,a1
        lea     -8(a1),a3               ; Safety margin
        move.l  a3,(ss_MaxDest,sp)

        lsr.l   #5,d2                   ; Clear entire destination
        subq.l  #1,d2
        move.l  d2,d3
        swap    d3
        moveq   #0,d4
        moveq   #0,d5
        moveq   #0,d6
        moveq   #0,d7
        move.l  d4,a3
        move.l  d5,a4
        move.l  d6,a5
        move.l  d7,a6
1$      movem.l d4-d7/a3-a6,-(a1)
        dbra    d2,1$
        dbra    d3,1$

        move.l  a2,a5                   ; Hash table pointer (a5)

        lea     (hashentstab,pc),a3     ; Find the hash table size (d2)
        move.l  d1,d2
        add.w   d2,d2
        move.w  (-MINBITS*2,a3,d2.w),d2
        move.w  d2,(ss_TabSize,sp)      ; Save a copy of the table size

        add.l   d2,d2                   ; table size * 6 (a2)
        move.l  d2,a2
        add.l   d2,a2
        add.l   d2,a2

        move.w  d1,(ss_MaxBits,sp)      ; Save MaxBits

        subq.w  #SOURCEBITS,d1          ; Calculate HashCharShift (a6)
        move.w  d1,a6

        addq.w  #4,a1                   ; Room for max bits and max string length

        moveq   #32,d2                  ; Initial bitcount (d2)

        clr.w   (ss_MaxString,sp)       ; Clear MaxString

        moveq   #0,d5                   ; Clear high bits of d5

resetloop
        move.l  a5,a3                   ; Invalidate the append_char entries
        moveq   #-1,d7
        move.w  (ss_TabSize,sp),d6
        subq.w  #1,d6
.clr
        move.w  d7,(a3)
        addq    #6,a3
        dbra    d6,.clr

        move.w  #1<<SOURCEBITS+3,d3     ; Initial nextcode (d3.w)
        move.w  #STARTBITS,a3           ; Initial outbits (a3)
        move.w  #1<<STARTBITS,(ss_IncCode,sp) ; Initial inccode

        moveq   #0,d4                   ; Initial string_code (d4)
        move.b  (a0)+,d4
        subq.l  #1,d0                   ; One less byte to munch

        moveq   #4,d1                   ; Init string size (with safety margin)
        bra.b   loop

bounceout
        bra     out

found                                   ; String found
        move.w  (4,a5,d6.l),d4
        addq.w  #1,d1

loop
        subq.l  #1,d0                   ; One less byte to munch
        bmi.b   bounceout

        move.b  (a0)+,d5                ; Get next character (d5)

findmatch
        move.l  d5,d6                   ; Find the hash table entry (d6)
        move.w  a6,d7
        asl.w   d7,d6
        eor.w   d4,d6
        add.l   d6,d6                   ; Offset (d6) = index * 6
        move.l  d6,d7
        add.l   d6,d6
        add.l   d7,d6

        move.l  0(a5,d6.l),d7           ; See if this entry is unused
        bmi.b   notfound
        cmp.w   d7,d4                   ; See if it contains the right code
        bne.b   1$
        swap    d7
        cmp.w   d7,d5
        beq.b   found
1$
        move.l  d6,a4                   ; Find negative index (a4)
        sub.l   a2,a4
        addq.w  #6,a4

        add.l   a4,d6                   ; Find the next appropriate entry
        bpl.b   .hunt
        add.l   a2,d6

.hunt
        move.l  (0,a5,d6.l),d7          ; See if this entry is unused
        bmi.b   notfound
        cmp.w   d7,d4                   ; See if it contains the right code
        bne.b   .notthis
        swap    d7
        cmp.w   d7,d5
        beq.b   found
.notthis
        add.l   a4,d6                   ; Find the next appropriate entry
        bpl.b   .hunt
        add.l   a2,d6
        bra.b   .hunt

notfound:
        cmp.w   (ss_MaxString,sp),d1    ; See if we've set a new record
        bls.b   2$
        move.w  d1,(ss_MaxString,sp)
2$
        lea     (4,a5,d6.l),a4          ; Add a new hash table entry
        move.w  d3,(a4)
        bmi.b   tabfull
        move.w  d4,-(a4)
        move.w  d5,-(a4)

        addq.w  #1,d3                   ; Find the next code

        cmp.w   (ss_IncCode,sp),d3      ; See if we've passed a boundary
        bhs.b   pastbound

outnew:
        move.l  d4,d7                   ; Output a new code
        move.l  d5,d4

        sub.w   a3,d2                   ; Find the bit position
        bpl.b   1$
        addq.w  #2,a1
        cmpa.l  (ss_MaxDest,sp),a1
        bge.b   outerrbounce
        addq.w  #8,d2
        addq.w  #8,d2
1$
        asl.l   d2,d7                   ; Insert the code into the bit stream
        or.l    d7,(a1)

        moveq   #4,d1                   ; Reset string size
        bra     loop

outerrbouncepop
        addq    #4,sp
outerrbounce
        bra     outerr

outcode:
        sub.w   a3,d2                   ; Find the bit position
        bpl.b   1$
        addq.w  #2,a1
        cmpa.l  (4+ss_MaxDest,sp),a1
        bge.b   outerrbouncepop
        addq.w  #8,d2
        addq.w  #8,d2
1$
        asl.l   d2,d7                   ; Insert the code into the bit stream
        or.l    d7,(a1)
        rts

pastbound:
        cmpa.w  (ss_MaxBits,sp),a3      ; Check for entire table full
        beq.b   settabfull

outcheck:
        cmp.w   (ss_IncCode,sp),d4      ; See if we're about to output a too-big code
        blo.b   outnew

        move.l  #1<<SOURCEBITS+2,d7     ; Output an increment-code-size code
        bsr.b   outcode

        addq.w  #1,a3                   ; Increase code size
        asl.w   (ss_IncCode,sp)

        bra.b   outnew                  ; Now output the new code

settabfull:
        move.l  (ss_Dest,sp),a4         ; Set the header to maximum number of bits
        move.w  (ss_MaxBits,sp),(a4)

        moveq   #-1,d3                  ; Flag that the table is full

        move.l  a0,(ss_SMarker,sp)      ; Set the markers
        move.l  a1,(ss_DMarker,sp)
        clr.w   (ss_PrevRatio,sp)

        bra.b   outnew

tabfull:
        subq.b  #1,d3                   ; Count out 256 codes
        bne.b   outnew

        ; FIXME: Try just using DMarker
        move.l  a0,d6                   ; Compute the compression ratio
        sub.l   (ss_SMarker,sp),d6
        asl.l   #8,d6
        move.l  a1,d7
        sub.l   (ss_DMarker,sp),d7
        divu.w  d7,d6
        cmp.w   (ss_PrevRatio,sp),d6    ; See if it dropped
        blo.b   cleartab

        move.l  a0,(ss_SMarker,sp)      ; Reset the markers
        move.l  a1,(ss_DMarker,sp)
        move.w  d6,(ss_PrevRatio,sp)
        bra     outnew

cleartab
        moveq   #$7f,d6                 ; Don't clear the table if there's only a little more
        cmp.l   d6,d0
        bls     outnew

        move.l  d4,d7                   ; Finish up the last two codes
        bsr     outcode
        move.l  d5,d7
        bsr     outcode

        move.l  #1<<SOURCEBITS+1,d7     ; Output a clear code
        pea     (resetloop,pc)
        bra     outcode

out
        cmp.w   (ss_IncCode,sp),d4      ; See if the last code is too big
        blo.b   .nottoobig

        move.l  #1<<SOURCEBITS+2,d7     ; Output an increment-code-size code
        bsr     outcode

        addq.w  #1,a3                   ; Increase the code size one last time
.nottoobig

        move.l  d4,d7                   ; Send out the last code
        bsr     outcode

        move.l  #1<<SOURCEBITS,d7       ; Send the end-of-file code
        bsr     outcode

        addq.w  #4,a1                   ; "Flush" the output buffer

        move.l  (ss_Dest,sp),a0         ; Find original destination

        move.w  (ss_MaxString,sp),d7    ; Save the maximum string length
        andi.w  #$fffc,d7
        move.w  d7,2(a0)

        tst.w   (a0)                    ; Record the largest number of bits used
        bne.s   1$
        move.w  a3,(a0)
1$
        suba.l  a0,a1                   ; Find the compressed size
        move.l  a1,d0

outt
        lea     (ss_Size,sp),sp         ; Pop the junk off the stack
        movem.l (sp)+,d2-d7/a2-a6
        rts

outerr
        moveq   #0,d0                   ; Return an error
        bra.b   outt

hashentstab
        dc.w    641     ; 9 bits
        dc.w    1283    ; 10 bits
        dc.w    2579    ; 11 bits
        dc.w    5147    ; 12 bits
        dc.w    10243   ; 13 bits
        dc.w    20483   ; 14 bits
        dc.w    40961   ; 15 bits

*** GenCompTableSize - Find the compression table size required for a particular number of bits
* d0.l = Maximum number of bits of compression
* Returns: d0 = Size in bytes of required hash tables, zero if unsupported number of bits
GenCompTableSize:
        sub.b   #MINBITS,d0             ; Check the range
        blo.b   .err
        moveq   #MAXBITS-MINBITS,d1
        cmp.l   d1,d0
        bhi.b   .err

        add.w   d0,d0                   ; Find the required number of entries
;        move.w  (hashentstab,pc,d0.w),d0
  lea     (hashentstab,pc),a0
  move.w  0(a0,d0.w),d0

        add.l   d0,d0                   ; Table size = entries * 6
        move.l  d0,d1
        add.l   d0,d0
        add.l   d1,d0

        rts

.err
        moveq   #0,d0
        rts