home *** CD-ROM | disk | FTP | other *** search
/ BBS 1 / BBS#1.iso / document / compress.arj / SQUO.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-23  |  16.5 KB  |  931 lines
  1.  
  2. /*
  3.     Yet Another LZ-compression algorithm
  4. */
  5.  
  6.  
  7. #include <stdio.h>
  8.  
  9.  
  10. #include "style.h"
  11. #include "squo.h"
  12.  
  13.  
  14. char    SquoVersion [] = "1.5";
  15.  
  16.  
  17. #define    dptr    _ds *
  18.  
  19.  
  20. /*    Conditional compilation symbols
  21.     =============================== */
  22.  
  23. #define    BIGTREE        /* use bigger buffer and trees */
  24. #define    PARTSH        /* perform only partial shift */
  25. #define    SHLEN    0    /* length of partial shift (0 = none) */
  26.  
  27. #if    defined(PARTSH) && (SHLEN == 0)
  28. #define    STATICTREE    /* fast tree with no rearrangement at all */
  29. #endif
  30.  
  31.  
  32. /* !!! don't mix HASH and NEWHASH */
  33. #define    noHASH        /* hash second byte for speed search */
  34. #define    NEWHASH        /* hash 2-, 3- and 4-byte sequences */
  35.  
  36.  
  37. #define    FASTPACK    /* skip repeating series to prevent slowdowns */
  38.  
  39.  
  40. #define    UNPACKER    /* include Unpacker code */
  41.  
  42.  
  43. #define    noSTATS        /* collect full statistics */
  44. #define    noDBGSTR        /* generate five not-encoded byte streams */
  45. #define    noDEBUG        /* do diagnostics printouts */
  46.  
  47.  
  48. /*    Constants and macros
  49.     ==================== */
  50.  
  51. #ifdef    BIGTREE
  52. #define MT    16
  53. #define    MD    (4096)
  54. #else
  55. #define MT    8
  56. #define    MD    (2048)
  57. #endif
  58.  
  59. #define    ML    (254+MT)    /* 254 'cause 255 is EOF mark */
  60.  
  61. #ifdef    HASH
  62. #define    MH        (1 << 3)
  63. #define    Hash(ch)    ((ch) & MH - 1)
  64. #endif
  65.  
  66.  
  67. #ifdef    DBGSTR
  68. FILE    * len1Stream,
  69.     * len2Stream,
  70.     * dist1Stream,
  71.     * dist2Stream,
  72.     * charStream;
  73. #endif
  74.  
  75.  
  76. /*    Statistical variables
  77.     ===================== */
  78.  
  79. #ifdef    STATS
  80.  
  81. int    ProgressInd = 1;
  82.  
  83. struct    {
  84. long    Reads,
  85.     Chars,
  86.     Refs,
  87.     LenBits,
  88.     DistBits,
  89.     LenBytes,
  90.     DistBytes,
  91.     BitsOut,
  92.     BytesOut;
  93. }    Total;
  94.  
  95. long    RefLen  [ML];
  96. long    RefDist [MD / 256];
  97.  
  98. #endif
  99.  
  100.  
  101. /*    File i/o functions
  102.     ================== */
  103.  
  104. /* they are copies of parameters passed to SquoPack() or SquoUnpack () */
  105.  
  106. ReadFunc    * p_reader;
  107. WriteFunc    * p_writer;
  108.  
  109.  
  110. /*    BitBuf variables
  111.     ================ */
  112.  
  113. #define    BITS    16
  114.  
  115. struct  {
  116.     UWORD    bits;
  117.     UBYTE    bytes [BITS];    /* bits in field 'bits' */
  118.  
  119.     UBYTE    freeBits,
  120.         dptr freeBytePtr;
  121. }    BitBuf;
  122.  
  123.  
  124. /*    Tree variables
  125.     ============== */
  126.  
  127. typedef    struct    {
  128.     UBYTE    codeLen, codeVal;
  129.     }    treeEl;
  130.  
  131. treeEl    LenTree [MT] = {
  132. #ifdef    BIGTREE
  133.         /* experimental tree-16 for lengths
  134.             01,    10,    11,    0000,
  135.             00100,    00101,    00110,    001110,
  136.             001111,    000111,    0001000,0001001,
  137.             0001010,0001011,0001100,0001101
  138.         */
  139.             {2, 2},    {2, 1},    {2, 3},    {4, 0},
  140.             {5, 4},    {5,20},    {5,12},    {6,28},
  141.             {6,60},    {6,56},    {7, 8},    {7,72},
  142.             {7,40},{7,104},    {7,24},    {7,88}
  143. #else
  144.         /* self-computed tree-8; !!! no codes */
  145.             {1}, {3}, {3}, {4},
  146.             {4}, {4}, {5}, {5}
  147. #endif
  148.     };
  149.  
  150. treeEl    DistTree [MT] = {
  151. #ifdef    BIGTREE
  152.         /* experimental tree-16 for distances
  153.             11,    100,    101,    0000,
  154.             0001,    0010,    00110,    00111,
  155.             01000,    01001,    01010,    01011,
  156.             01100,    01101,    01110,    01111
  157.  
  158.         */
  159.             {2, 3},    {3, 1},    {3, 5},    {4, 0},
  160.             {4, 8},    {4, 4},    {5,12},    {5,28},
  161.             {5, 2},    {5,18},    {5,10},    {5,26},
  162.             {5, 6},    {5,22},    {5,14},    {5,30}
  163. #else
  164.         /* self-computed tree-8; !!! no codes */
  165.             {1}, {3}, {3}, {4},
  166.             {4}, {4}, {5}, {5}
  167. #endif
  168.     };
  169.  
  170.     /*     pointers to corresponding Tree:
  171.         *LenStack [x] is current Huffman code for 'x' */
  172.  
  173. treeEl    dptr LenStack [MT],
  174.     dptr DistStack [MT];
  175.  
  176.  
  177. /*    BitBuf functions
  178.     ================ */
  179.  
  180. /*
  181. tree path:    1011        reversed in table
  182. put code:    1101->CF    shr    al, 1
  183.         CF->databyte    rcr    bx, 1
  184. byte:        xxxx1101->CF    shr    bp, 1
  185. get code:    yy<-CF        rcl    bl, 1
  186. result:        1011        used as index
  187. */
  188.  
  189. void    _PutCode (treeEl dptr t);
  190. void    PutCode (treeEl dptr t)    {
  191.  
  192.     #ifdef    STATS
  193.     Total.BitsOut += t -> codeLen;
  194.     #endif
  195.     #ifdef    DEBUG
  196.     printf ("    %sTree [%d] codeLen: %d codeVal: %d\n",
  197.         t >= DistTree ? "Dist" : "Len",
  198.         t >= DistTree ? t - DistTree : t - LenTree,
  199.         t -> codeLen, t -> codeVal);
  200.     #endif
  201.  
  202.     _PutCode (t);
  203. }
  204.  
  205. void    PutByte (UBYTE b)    {
  206.  
  207.     #ifdef    STATS
  208.     Total.BytesOut ++;
  209.     #endif
  210.     #ifdef    DEBUG
  211.     printf ("    byte: %d [%c]\n", b, b);
  212.     #endif
  213.  
  214.     * (BitBuf.freeBytePtr ++) = b;
  215. }
  216.  
  217. void    InitBitBuf (void)    {
  218.     BitBuf.bits = 0;
  219.     BitBuf.freeBits = BITS;
  220.     BitBuf.freeBytePtr = & (BitBuf.bytes [0]);
  221. }
  222.  
  223. void    FlushBitBuf (void)    {
  224.     p_writer (& BitBuf.bits, sizeof (BitBuf.bits));
  225.     p_writer (& BitBuf.bytes, BitBuf.freeBytePtr - BitBuf.bytes);
  226.     InitBitBuf ();
  227. }
  228.  
  229. void    DoneBitBuf (void)    {
  230.     BitBuf.bits >>= BitBuf.freeBits;
  231.     FlushBitBuf ();
  232. }
  233.  
  234.  
  235. /*    Tree functions
  236.     ============== */
  237.  
  238. void    InitTrees (void)    {
  239.     UWORD    i;
  240.  
  241.     for (i = 0; i < MT; i ++)    {
  242.         LenStack [i] = & (LenTree [i]);
  243.         DistStack [i] = & (DistTree [i]);
  244.     }
  245. }
  246.  
  247. void    PutLen (UWORD len)    {
  248.     UWORD    l;
  249.  
  250.     #ifdef    STATS
  251.         RefLen [len - 1] ++;
  252.     #endif
  253.  
  254.     l = ( (len >= MT) ? MT : len) - 1;
  255.  
  256.     PutCode (LenStack [l]);
  257.     #ifdef    STATS
  258.         Total.LenBits += LenStack [l] -> codeLen;
  259.     #endif
  260.     #ifdef    DBGSTR
  261.         fwrite (&l, 1, 1, len1Stream);
  262.     #endif
  263.  
  264.     if (len >= MT)    {
  265.         PutByte (len - MT);
  266.         #ifdef    STATS
  267.             Total.LenBytes ++;
  268.         #endif
  269.         #ifdef    DBGSTR
  270.             {
  271.                 UBYTE    b = len - MT;
  272.                 fwrite (&b, 1, 1, len2Stream);
  273.             }
  274.         #endif
  275.     }
  276.  
  277.     #ifndef    STATICTREE
  278.     {
  279.     UWORD    i;
  280.  
  281.     for (i = 0; i < MT; i ++)    {
  282.         if (LenStack [i] < LenStack [l]
  283.         #ifdef    PARTSH
  284.             && LenStack [i] + SHLEN >= LenStack [l]
  285.         #endif
  286.         )
  287.             LenStack [i] ++;
  288.     }
  289.     #ifndef    PARTSH
  290.     LenStack [l] = & (LenTree [0]);
  291.     #else
  292.     if (LenStack [l] - LenTree >= SHLEN)
  293.         LenStack [l] -= SHLEN;
  294.     else
  295.         LenStack [l] = LenTree;
  296.     #endif
  297.     }
  298.     #endif
  299. }
  300.  
  301. void    PutDist (UWORD dist)    {
  302.     UWORD    d;
  303.  
  304.     #ifdef    STATS
  305.         RefDist [dist / 256] ++;
  306.     #endif
  307.  
  308.     d = dist >> 8;
  309.  
  310.     PutCode (DistStack [d]);
  311.     #ifdef    DBGSTR
  312.         fwrite (&d, 1, 1, dist1Stream);
  313.     #endif
  314.  
  315.     PutByte (dist & 0xFF);
  316.     #ifdef    STATS
  317.         Total.DistBits += DistStack [d] -> codeLen;
  318.         Total.DistBytes ++;
  319.     #endif
  320.     #ifdef    DBGSTR
  321.         {
  322.             UBYTE    b = dist & 0xFF;
  323.             fwrite (&b, 1, 1, dist2Stream);
  324.         }
  325.     #endif
  326.  
  327.     #ifndef    STATICTREE
  328.     {
  329.     UWORD    i;
  330.  
  331.     for (i = 0; i < MT; i ++)    {
  332.         if (DistStack [i] < DistStack [d]
  333.         #ifdef    PARTSH
  334.             && DistStack [i] + SHLEN >= DistStack [d]
  335.         #endif
  336.         )
  337.             DistStack [i] ++;
  338.     }
  339.     #ifndef    PARTSH
  340.     DistStack [d] = & (DistTree [0]);
  341.     #else
  342.     if (DistStack [d] - DistTree >= SHLEN)
  343.         DistStack [d] -= SHLEN;
  344.     else
  345.         DistStack [d] = DistTree;
  346.     #endif
  347.     }
  348.     #endif
  349. }
  350.  
  351. void    DoneTrees (void)    {
  352.     /* nothing there */
  353. }
  354.  
  355.  
  356. /*    Buffer variables
  357.     ================ */
  358.  
  359. typedef    struct    bufferEl {
  360.     char            c;
  361.  
  362.     #ifndef    NEWHASH
  363.     struct    bufferEl    dptr next;
  364.     #ifdef    HASH
  365.     struct    bufferEl    dptr next2;
  366.     #endif
  367.  
  368.     #else
  369.     struct    bufferEl    dptr next_2,
  370.                 dptr next_3,
  371.                 dptr next_4;
  372.     #endif
  373. } bufferEl;
  374.  
  375. #ifndef    NEWHASH
  376. typedef    struct    {
  377.     bufferEl    dptr first, dptr last;
  378.     #ifdef    HASH
  379.     struct    hashList    {
  380.         bufferEl    dptr first2, dptr last2;
  381.     }    list2 [MH];
  382.     #endif
  383. } cacheEl;
  384.  
  385. #define        CacheSize    256
  386. cacheEl        Cache [CacheSize];
  387.  
  388. #else
  389.  
  390. typedef    struct    {
  391.     bufferEl    dptr first, dptr last;
  392. }    hashList;
  393.  
  394.  
  395. hashList    Hash_2 [512],
  396.         Hash_3 [1024],
  397.         Hash_4 [2048];
  398. #endif
  399.  
  400. #define    BufferSize    (MD + ML)
  401. bufferEl    Buffer [BufferSize];
  402.  
  403. bufferEl    dptr BufStart,    /* start of dictionary */
  404.         dptr BufPtr;    /* end of dictionary, start of match */
  405.  
  406. UWORD        InBuffer;    /* size of dictionary */
  407. UWORD        CharsPastEof;    /* count of garbage chars in Buffer */
  408.  
  409.  
  410. /*    Buffer functions
  411.     ================ */
  412.  
  413. #define    Next(p)    ( (++p >= & Buffer [BufferSize]) ? (p = Buffer) : p)
  414.  
  415. #ifndef    NEWHASH
  416. #define    FirstChar    (BufPtr -> c)
  417. #define    SecondChar    (BufPtr < (Buffer + BufferSize - 1) ?    \
  418.             (BufPtr + 1) -> c :            \
  419.             Buffer -> c)
  420. #endif
  421.  
  422.  
  423. char    ReadChar (void)    {
  424.     char    ch;
  425.  
  426.     int    status = p_reader (&ch, 1);
  427.  
  428.     if (status == 0)    {
  429.         CharsPastEof ++;
  430.                 ch = 0;
  431.     }
  432.  
  433.     #ifdef    STATS
  434.     if (status != 0)    {
  435.         Total.Reads ++;
  436.         if (ProgressInd && (Total.Reads % 1024 == 0))    {
  437.             fprintf (stderr, "@");
  438.         }
  439.     }
  440.     #endif
  441.  
  442.     return    ch;
  443. }
  444.  
  445.  
  446. void    InitBuffer (void)    {
  447.     UWORD    i;
  448.     #ifdef    HASH
  449.     UWORD    j;
  450.     #endif
  451.  
  452.     #ifndef    NEWHASH
  453.     for (i = 0; i < CacheSize; i ++)    {
  454.         Cache [i].first = Cache [i].last = NULL;
  455.  
  456.         #ifdef    HASH
  457.         for (j = 0; j < MH; j ++)    {
  458.             Cache [i].list2 [j].first2 =
  459.             Cache [i].list2 [j].last2 = NULL;
  460.         }
  461.         #endif
  462.     }
  463.  
  464.     #else
  465.     for (i = 0; i < arraySize (Hash_2); i ++)    {
  466.         Hash_2 [i].first = Hash_2 [i].last = NULL;
  467.     }
  468.     for (i = 0; i < arraySize (Hash_3); i ++)    {
  469.         Hash_3 [i].first = Hash_3 [i].last = NULL;
  470.     }
  471.     for (i = 0; i < arraySize (Hash_4); i ++)    {
  472.         Hash_4 [i].first = Hash_4 [i].last = NULL;
  473.     }
  474.     #endif
  475.  
  476.     CharsPastEof = 0;
  477.     for (i = 0; i < ML; i ++)    {
  478.         Buffer [i].c = ReadChar ();
  479.     }
  480.  
  481.     BufStart = BufPtr = Buffer;
  482.     InBuffer = 0;
  483. }
  484.  
  485. void    DoneBuffer (void)    {
  486.     /* write EOF mark */
  487.     PutLen (ML + 1);
  488. }
  489.  
  490.  
  491. #ifdef    NEWHASH
  492. typedef    UWORD    HashValue;
  493.  
  494. #define    UpdateHash(hashVal, ch)    ( ((HashValue) (hashVal) << 1) ^ (ch) )
  495. #endif
  496.  
  497. void    MoveBuf (UWORD len)    {
  498.     for ( ; len > 0; len --)    {
  499.         if (InBuffer >= MD)    {
  500.             /* delete first char from dictionary */
  501.  
  502.             #ifndef    NEWHASH
  503.             register cacheEl    dptr cp;
  504.  
  505.             cp = & Cache [BufStart -> c];
  506.             if ( (cp -> first = BufStart -> next) == NULL)
  507.                 cp -> last = NULL;
  508.  
  509.             Next (BufStart);
  510.  
  511.             #ifdef    HASH
  512.             {
  513.             register struct hashList    dptr lp;
  514.  
  515.             lp = & ( cp -> list2 [Hash (BufStart -> c)] );
  516.             if ( (lp -> first2 = BufStart -> next2) == NULL)
  517.                 lp -> last2 = NULL;
  518.             }
  519.             #endif
  520.  
  521.             #else
  522.             HashValue    hashVal = 0;
  523.             bufferEl    dptr bp = BufStart;
  524.             hashList    dptr hp;
  525.  
  526.             hashVal = UpdateHash (hashVal, bp -> c);
  527.             Next (bp);
  528.  
  529.             hashVal = UpdateHash (hashVal, bp -> c);
  530.             Next (bp);
  531.             hp = & Hash_2 [hashVal];
  532.             if ( (hp -> first = BufStart -> next_2) == NULL)
  533.                 hp -> last = NULL;
  534.  
  535.             hashVal = UpdateHash (hashVal, bp -> c);
  536.             Next (bp);
  537.             hp = & Hash_3 [hashVal];
  538.             if ( (hp -> first = BufStart -> next_3) == NULL)
  539.                 hp -> last = NULL;
  540.  
  541.             hashVal = UpdateHash (hashVal, bp -> c);
  542.             /* extra Next (bp); */
  543.             hp = & Hash_4 [hashVal];
  544.             if ( (hp -> first = BufStart -> next_4) == NULL)
  545.                 hp -> last = NULL;
  546.  
  547.             Next (BufStart);
  548.  
  549.             #endif
  550.         } else {
  551.             InBuffer ++;
  552.         }
  553.  
  554.         {
  555.             /* add one new char to dictionary */
  556.  
  557.             #ifndef    NEWHASH
  558.             register cacheEl    dptr cp;
  559.  
  560.             cp = & Cache [BufPtr -> c];
  561.             if (cp -> last == NULL)    {
  562.                 cp -> first = cp -> last = BufPtr;
  563.             } else {
  564.                 cp -> last = cp -> last -> next = BufPtr;
  565.             }
  566.             BufPtr -> next = NULL;
  567.  
  568.             #else
  569.  
  570.             bufferEl        dptr bp = BufPtr;
  571.             HashValue    hashVal = 0;
  572.             hashList    dptr hp;
  573.  
  574.             hashVal = UpdateHash (hashVal, bp -> c);
  575.             Next (bp);
  576.  
  577.             hashVal = UpdateHash (hashVal, bp -> c);
  578.             Next (bp);
  579.             hp = & Hash_2 [hashVal];
  580.             if (hp -> last == NULL)    {
  581.                 hp -> first = hp -> last = BufPtr;
  582.             } else {
  583.                 hp -> last = hp -> last -> next_2 = BufPtr;
  584.             }
  585.             BufPtr -> next_2 = NULL;
  586.  
  587.             hashVal = UpdateHash (hashVal, bp -> c);
  588.             Next (bp);
  589.             hp = & Hash_3 [hashVal];
  590.             if (hp -> last == NULL)    {
  591.                 hp -> first = hp -> last = BufPtr;
  592.             } else {
  593.                 hp -> last = hp -> last -> next_3 = BufPtr;
  594.             }
  595.             BufPtr -> next_3 = NULL;
  596.  
  597.             hashVal = UpdateHash (hashVal, bp -> c);
  598.             /* extra Next (bp); */
  599.             hp = & Hash_4 [hashVal];
  600.             if (hp -> last == NULL)    {
  601.                 hp -> first = hp -> last = BufPtr;
  602.             } else {
  603.                 hp -> last = hp -> last -> next_4 = BufPtr;
  604.             }
  605.             BufPtr -> next_4 = NULL;
  606.  
  607.             #endif
  608.  
  609.             /* read next char into buffer's gap */
  610.             {
  611.                 bufferEl    dptr bp;
  612.  
  613.                 bp = BufPtr + ML;
  614.                 if (bp >= Buffer + BufferSize)    {
  615.                     bp -= BufferSize;
  616.                 }
  617.                 bp -> c = ReadChar ();
  618.             }
  619.  
  620.             Next (BufPtr);
  621.  
  622.             #ifndef    NEWHASH
  623.             #ifdef    HASH
  624.             {
  625.             register struct hashList    dptr lp;
  626.  
  627.             lp = & ( cp -> list2 [Hash (BufPtr -> c)] );
  628.             if (lp -> last2 == NULL)    {
  629.                 lp -> first2 = lp -> last2 = BufPtr;
  630.             } else {
  631.                 lp -> last2 = lp -> last2 -> next2 = BufPtr;
  632.             }
  633.             BufPtr -> next2 = NULL;
  634.             }
  635.             #endif
  636.             #endif
  637.         }
  638.     }    /* for (len) */
  639. }
  640.  
  641.  
  642. #ifdef    STATS
  643. void    PrintWeightedAvg (char * text, long * data, size_t size)    {
  644.     size_t    i;
  645.     long    total;        /* weighted sum of data [size] */
  646.     long    weight;        /* simple sum of -"-*/
  647.  
  648.     for (total = 0, weight = 0, i = 0; i < size; i ++)    {
  649.         total += i * data [i];
  650.         weight += data [i];
  651.     }
  652.     printf ("%s%ld.%02ld", text,
  653.         total / weight, (total % weight) * 100 / weight);
  654. }
  655.  
  656. void    PrintStats (void)    {
  657.     UWORD    i;
  658.  
  659.     printf ("\nTotal:\n"
  660.         "    reads: %07ld"
  661.         "    chars: %07ld"
  662.         "    refs:  %07ld\n"
  663.         "    len: bits: %07ld, bytes: %07ld\n"
  664.         "    dist: bits: %07ld, bytes: %07ld\n"
  665.         "    total: bits: %07ld, bytes: %07ld == %07ld bytes"
  666.             "; %d%% bits left\n",
  667.         Total.Reads,
  668.         Total.Chars,
  669.         Total.Refs,
  670.         Total.LenBits, Total.LenBytes,
  671.         Total.DistBits, Total.DistBytes,
  672.         Total.BitsOut, Total.BytesOut,
  673.         (Total.BitsOut >> 3) + Total.BytesOut,
  674.         100 * (Total.BitsOut + (Total.BytesOut << 3))
  675.             / (Total.Reads << 3)
  676.         );
  677.  
  678.     PrintWeightedAvg ("Mean (Dist) = ", RefDist, arraySize (RefDist));
  679.     PrintWeightedAvg ("\tMean (Len - 1) = ", RefLen, arraySize (RefLen));
  680.     printf ("\nRef distances: \n");
  681.     for (i = 0; i < MD / 256; i ++)
  682.         printf (" %05ld%s", RefDist [i], (i + 1) % 8 ? "" : "\n");
  683.     printf ("\nRef lengths: \n");
  684.     for (i = 0; i < ML / 4; i ++)    {
  685.         /* only first quarter -- last are nearly all 0's */
  686.         printf (" %04ld%s", RefLen [i], (i + 1) % 10 ? "" : "\n");
  687.     }
  688.     printf ("\n");
  689. }
  690. #endif
  691.  
  692.  
  693. /*    The Packer
  694.     ========== */
  695.  
  696. int    SquoPack (ReadFunc *reader, WriteFunc *writer)    {
  697.     UWORD        len, bestLen;
  698.     bufferEl    dptr start,  dptr bestStart;
  699.     register        bufferEl    dptr p,  dptr bestP;
  700.     #ifdef    HASH
  701.     cacheEl        dptr cp;
  702.     #endif
  703.  
  704.     #ifdef    DBGSTR
  705.         len1Stream  = fopen ("_l1.lz", "wb");
  706.         len2Stream  = fopen ("_l2.lz", "wb");
  707.         dist1Stream = fopen ("_d1.lz", "wb");
  708.         dist2Stream = fopen ("_d2.lz", "wb");
  709.     charStream  = fopen ("_c.lz", "wb");
  710.     #endif
  711.  
  712.     p_reader = reader;
  713.     p_writer = writer;
  714.  
  715.     InitBitBuf ();
  716.     InitTrees ();
  717.     InitBuffer ();
  718.  
  719.     while (CharsPastEof < ML)    {
  720.         /* the Buffer always contains ML chars in the gap */
  721.  
  722.         bestLen = 0;
  723.         bestStart = BufStart;    /* the value doesn't matter actually,
  724.                     but I want to have it initialized */
  725.  
  726.         #ifndef    NEWHASH
  727.         #ifndef    HASH
  728.         if ( (start = Cache [FirstChar].first) != NULL)    {
  729.         #else
  730.         if ( (cp = Cache + FirstChar) -> first != NULL
  731.          && (start = cp -> list2 [Hash (SecondChar)].first2) != NULL) {
  732.         #endif
  733.             do    {
  734.  
  735.                 p = start;
  736.                 #ifndef    HASH
  737.                 Next (p);
  738.                 #endif
  739.  
  740.                 bestP = BufPtr;
  741.                 Next (bestP);
  742.  
  743.                 for (len = 1; (++ len) <= ML; )    {
  744.                     if (p -> c != bestP -> c)
  745.                         break;
  746.                     Next (p); Next (bestP);
  747.                 }
  748.                 len --;
  749.                 if (len >= bestLen)    {
  750.                     bestLen = len;
  751.                     bestStart = start;
  752.                 }
  753.  
  754.             #ifndef    HASH
  755.             } while ( (start = start -> next) != NULL);
  756.             #else
  757.             } while ( (start = start -> next2) != NULL);
  758.             #endif
  759.         }
  760.  
  761.         #else
  762.         {
  763.         HashValue    hv_2, hv_3, hv_4;
  764.  
  765.         hv_2 = 0;                p = BufPtr;
  766.         hv_2 = UpdateHash (hv_2, p -> c);    Next (p);
  767.         hv_2 = UpdateHash (hv_2, p -> c);    Next (p);
  768.         hv_3 = hv_2;
  769.         hv_3 = UpdateHash (hv_3, p -> c);    Next (p);
  770.         hv_4 = hv_3;
  771.         hv_4 = UpdateHash (hv_4, p -> c);    /* extra Next (p); */
  772.  
  773.         if ( (start = Hash_4 [hv_4].first) != NULL)    {
  774.             do    {
  775.  
  776.                 #ifdef    FASTPACK
  777.                 /* kludge: skip over repeating series */
  778.                 {
  779.                 int    step = start - bestStart;
  780.  
  781.                 if (step < 0)
  782.                     step += BufferSize;
  783.  
  784.                 if (step < bestLen)
  785.                     continue;
  786.                 }
  787.                 #endif
  788.  
  789.                 p = start;
  790.                 bestP = BufPtr;
  791.  
  792.                 for (len = 0; (++ len) <= ML; )    {
  793.                     if (p -> c != bestP -> c)
  794.                         break;
  795.                     Next (p); Next (bestP);
  796.                 }
  797.                 len --;
  798.                 if (len >= bestLen)    {
  799.                     bestLen = len;
  800.                     bestStart = start;
  801.                 }
  802.  
  803.             } while ( (start = start -> next_4) != NULL);
  804.  
  805.             if (bestLen < 4)
  806.                 bestLen = 0;
  807.         }
  808.  
  809.         if (bestLen == 0)    {
  810.             if ( (start = Hash_3 [hv_3].first) != NULL)    {
  811.                 do    {
  812.                     p = start;
  813.                     bestP = BufPtr;
  814.  
  815.                     if (p -> c != bestP -> c)
  816.                         continue;
  817.                     Next (p); Next (bestP);
  818.                     if (p -> c != bestP -> c)
  819.                         continue;
  820.  
  821.                     bestLen = 3;
  822.                     bestStart = start;
  823.                 } while ( (start = start -> next_3) != NULL);
  824.             }
  825.         }
  826.  
  827.         if (bestLen == 0)    {
  828.             if ( (start = Hash_2 [hv_2].first) != NULL)    {
  829.                 do    {
  830.                     p = start;
  831.                     bestP = BufPtr;
  832.  
  833.                     if (p -> c != bestP -> c)
  834.                         continue;
  835.  
  836.                     bestLen = 2;
  837.                     bestStart = start;
  838.                 } while ( (start = start -> next_2) != NULL);
  839.             }
  840.         }
  841.  
  842.         }
  843.         #endif
  844.  
  845.         if (bestLen > ML - CharsPastEof)    {
  846.             bestLen = ML - CharsPastEof;
  847.         }
  848.  
  849.         if (bestLen <= 1)    {
  850.             bestLen = 1;
  851.  
  852.             #ifdef    DEBUG
  853.                 fprintf (stdout, "char %c [%x]\n",
  854.                 BufPtr -> c, BufPtr -> c);
  855.             #endif
  856.  
  857.             PutLen (1);
  858.             PutByte (BufPtr -> c);
  859.             #ifdef    DBGSTR
  860.                 {
  861.                 char    ch = BufPtr -> c;
  862.                 fwrite (&ch, 1, 1, charStream);
  863.                 }
  864.             #endif
  865.  
  866.             #ifdef    STATS
  867.             Total.Chars ++;
  868.             #endif
  869.         } else {
  870.             WORD    dist;
  871.  
  872.             dist = BufPtr - bestStart;
  873.             if (dist < 0)  dist += BufferSize;
  874.             #ifndef    HASH
  875.             dist --;
  876.             #endif
  877.  
  878.             #ifdef    DEBUG
  879.                 fprintf (stdout, "ref (%d) <-%d\n",
  880.                 bestLen, dist + 1);
  881.             #endif
  882.  
  883.             PutLen    (bestLen);
  884.             PutDist (dist);
  885.  
  886.             #ifdef    STATS
  887.             Total.Refs ++;
  888.             #endif
  889.                 }
  890.         MoveBuf (bestLen);
  891.     } /* while (! eof ()) */
  892.  
  893.     DoneBuffer ();
  894.     DoneTrees ();
  895.     DoneBitBuf ();
  896.  
  897.     #ifdef    DBGSTR
  898.         fclose (len1Stream);
  899.         fclose (len2Stream);
  900.         fclose (dist1Stream);
  901.         fclose (dist2Stream);
  902.     fclose (charStream);
  903.     #endif
  904.  
  905.     #ifdef    STATS
  906.     PrintStats ();
  907.     #endif
  908.  
  909.     return    0;
  910. }
  911.  
  912.  
  913. /*    The Unpacker
  914.     ============ */
  915.  
  916. extern    void    _SquoUnpack (void);
  917.  
  918. int    SquoUnpack (ReadFunc *reader, WriteFunc *writer)    {
  919.  
  920. #ifndef    UNPACKER
  921.     printf ("SquoUnpack() not included.\n");
  922.     return    1;
  923. #else
  924.     p_reader = reader;
  925.     p_writer = writer;
  926.     _SquoUnpack ();
  927.     return    0;
  928. #endif
  929. }
  930.  
  931.