Bload Compressor/4

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

'Page 4 of ENCODE13.BAS begins here.
'-s option brings this down to 10-7 compares(can't remember exactly),
'and  the -ex option increases the  bombout  rate  to  500  compares.
'Obviously, the -ex option slows down PKZIP 1.93a  because it can  do
'up to ten times more string compares than usual.)
'
'    One optimization that I have not seen anywhere yet speeds up the
'string  search  by  skipping  strings which can't possibly be larger
'than the largest string found up to that point...
'
'    For  instance,   let's  say we are searching for the string "the
'president eats peanuts".   Let's  also  say  the largest match we've
'found so far is "the president ", or 14 characters.  The next string
'to  compare  against  our target is "the president finds coolness in
'compression".  Since the whole point of searching is to look for the
'largest match, there's no use in doing a whole string compare if the
'match will be smaller/equal to  our current match.   A quick compare
'of the character that must match for the match length to  be  larger
'will  tell  us  if  the  string  *may* be larger.   If the character
'matches,  we must do the compare.   If it doesn't,  then there is no
'use in doing the string compare because the match cannot possibly be
'longer.   Since the 15th character of our target string is "e",  and
'the 15th character of our search string is "f",  it can instantly be
'discarded because the  match  cannot  possibly  be  larger  than  14
'characters.   This especially speeds up the search when large string
'matches  are found in the input stream(such as in text files).   And
'since the optimization is relatively trivial, it shouldn't slow down
'the string search loop much  at  all  when  input stream is not very
'compressable.
'
'   Finally,  using the linked list pool to find string matches makes
'finding the  closest  AND  longest  match  very  simple(finding  the
'closest  match  aids  entropy encoding in attaining more compression
'because it can  favor  close  matches  over  far  ones).   Since new
'strings are always inserted as the first string in its  pool,    the
'entire  list is already sorted in order of distance from our current
'position in the ring buffer.
SUB FindString (BYVAL R)
    B1 = RingBuffer(R): B2 = RingBuffer(R + 1): B3 = RingBuffer(R + 2)
    'hash the first 3 characters of the string to find
    LinkHead = (BufferSize + 1) + ((B1 * 14096& XOR B2 * 77 XOR B3) _
MOD HashSize)
    Match.Length = 0: MatchChar = B1: P = LinkHead
    FOR x = 1 TO MaxCompares 'MaxCompares is the bombout rate
        'traverse linked list P for match
        P = NextCell(P): IF P = Null THEN EXIT FOR
        'If first 3 characters match, and the character at
        'P+MatchLength=R+MatchLength, then compare strings.
        IF RingBuffer(P) = B1 AND RingBuffer(P + 1) = B2 AND RingBuffer_
(P + 2) = B3 AND RingBuffer(P + Match.Length) = MatchChar THEN
            FOR SearchLength = 3 TO (MaxMatch - 1) - 1
                IF RingBuffer(R + SearchLength) <> RingBuffer(P + _
SearchLength) THEN EXIT FOR
            NEXT
            'if matchsize=maxmatch then take it and run
            '(MaxMatch-1) because our look ahead buffer is one
            'character longer than the maximum match length.
            IF SearchLength >= (MaxMatch - 1) THEN
                Match.Length = (MaxMatch - 1)
                Match.Position = P
                EXIT FOR
            END IF
            'if we find a longer match then take it
            IF SearchLength > Match.Length THEN
                Match.Length = SearchLength
                Match.Position = P
                MatchChar = RingBuffer(R + Match.Length)
            END IF
        END IF
    NEXT
    'make the new string the first entry in its linked list pool
    'so we always find the closest match
    a = NextCell(LinkHead): NextCell(LinkHead) = R
    LastCell(a) = R: LastCell(R) = LinkHead: NextCell(R) = a
    'Attempt to find a longer match at R+1. If there is a longer
    'match, then set the match length to zero so the current match
    'is ignored.
    IF (Match.Length <> 0) AND (Match.Length <> (MaxMatch - 1)) THEN
        IF FindAlternate(R + 1, Match.Length) THEN Match.Length = 0
    END IF
END SUB

'Returns one pixel from the display.
FUNCTION GetPixel
    GetPixel = POINT(xp, yp): xp = xp + 1
    IF xp > xh THEN
        LINE (xl, yp)-(xh, yp), 0
        xp = xl: yp = yp + 1: DoneFlag = yp > yh
    END IF
END FUNCTION

'Initializes the linked list pool arrays
'Continued on page 5

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