Bload Compressor/3

 BBS: Inland Empire Archive
Date: 12-27-92 (06:21)             Number: 244
From: RICH GELDREICH               Refer#: NONE
  To: ALL                           Recvd: NO  
Subj: Bload Compressor/3             Conf: (2) Quik_Bas

'Page 3 of ENCODE13.BAS begins here.
                    MakeString R
                END IF

                'Limit  match  length  because the look ahead buffer
                'is growing smaller.   This is another little oddity
                'I've seen amoung the LZSS compressors,  they all do
                'this check outside this  loop  before they output a
                'character/match token...    There's  no  reason  to
                'check  outside  the  loop because the string search
                'function always  limits  the  match  length  to the
                'look ahead buffer's size.   We only check when  the
                'look ahead buffer starts to get smaller.

                IF Match.Length > LookAheadLength THEN
                    Match.Length = LookAheadLength
                END IF
            END IF
        NEXT
    LOOP WHILE LookAheadLength 'loop while still more chars to encode
    OutputEOF
    WriteFlush
    'get (compressed size)-header
    a& = LOF(1) - 7: SCREEN 0: WIDTH 80
    IF a& > 64000 THEN
        PRINT "Image could not be compressed."
        CLOSE #1: KILL F$
    ELSE
        PRINT "Image compressed to"; a&; "bytes."
        IF a& > 32767 THEN a& = a& - 65536
        'store the compressed size so BLOAD loads everything in
        a = a&: PUT #1, 6, a: CLOSE #1
    END IF
END SUB

'Deletes the string at S from the linked list pool.
SUB DeleteString (BYVAL S)
    NextCell = NextCell(S): LastCell = LastCell(S)
    NextCell(LastCell) = NextCell: LastCell(NextCell) = LastCell
    NextCell(S) = Null
END SUB

'Attempts to find a match at R+1 that is larger than the match found
'at R, to get rid of some of the encoder's "greedy" characteristics.
FUNCTION FindAlternate (BYVAL R, BYVAL MatchLength)
    B1 = RingBuffer(R): B2 = RingBuffer(R + 1): B3 = RingBuffer(R + 2)
    'hash out the first three characters of the string to locate
    P = (BufferSize + 1) + ((B1 * 14096& XOR B2 * 77 XOR B3) MOD _
HashSize)
    MatchChar = RingBuffer(R + MatchLength)
    FOR x = 1 TO MaxCompares
        P = NextCell(P) 'traverse linked list P for a match
        'if we struck bottom then search failed
        IF P = Null THEN FindAlternate = False: EXIT FUNCTION
        'compare string P to string R
        IF RingBuffer(P) = B1 AND RingBuffer(P + 1) = B2 AND RingBuffer_
(P + 2) = B3 AND RingBuffer(P + MatchLength) = MatchChar THEN
            FOR SearchLength = 3 TO (MaxMatch - 1) - 1
                IF RingBuffer(R + SearchLength) <> RingBuffer(P + _
SearchLength) THEN EXIT FOR
            NEXT
            'if we find a longer match then exit with success
            IF SearchLength > MatchLength THEN FindAlternate = True: _
EXIT FUNCTION
        END IF
    NEXT
    FindAlternate = False
END FUNCTION

'Attempts  to  locate  a  match  in the linked list pool for  R. Most
'other LZ77/LZSS  implementations  I've  seen  use  a  binary tree to
'locate string matches.   In this implementation,  I use  a  pool  of
'linked  lists to locate strings.   Each linked list contains strings
'which all  start  with the  same 3 characters. (Well, usually. Since
'hash collisions can occur,  sometimes  a linked list contains two or
'more different strings.   This isn't cool,  and can't be  eliminated
'unless  another approach to collision handling is used.)
'
'    To locate a string,  its linked list is located through a simple
'hashing formula(which was home brewed,  BTW,   so it may not be that
'optimal),  and then each string in the list is compared against  our
'target  string until we either find a string which matches perfectly
'or the "bombout" variable is decremented to zero.   The bombout rate
'defines the number of string  compares  which may be performed until

'the algorithm stops searching and settles with what it  has.    This
'decreases  compression  slightly,  but greatly increases compression
'speed,  especially when  the  input  stream  contains  large runs of
'repeated data.   (ARJ adjusts its bombout  rate  with  command  line
'options:   options  -m4  to  -m0 vary the number of compares it does
'against its string directionary,  therefore "dialing" in compression
'speed  vs.    compression  ratio.    PKZIP  1.93a  does  this  also.
'Normally, PKZIP 1.93a will set its bombout rate to 50 compares.  The
'Continued on page 4

--- MsgToss 2.0b
 * Origin: Computer Co-Op - Voorhees, NJ | Ted Hare (1:266/29)