home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 65 / arclzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-07-13  |  26.9 KB  |  820 lines
  1. static char *RCSid = "$Header: arclzw.c,v 1.2 86/07/15 07:53:20 turner Exp $";
  2.  
  3. /*
  4.  * $Log:    arclzw.c,v $
  5.  * Hack-attack 1.3  86/12/20  01:23:45  wilhite@usceast.uucp
  6.  *     Bludgeoned into submission for VAX 11/780 BSD4.2
  7.  *    (ugly code, but fewer core dumps)
  8.  *
  9.  * Revision 1.2  86/07/15  07:53:20  turner
  10.  * 
  11.  * Revision 1.1  86/06/26  15:00:26  turner
  12.  * initial version
  13.  * 
  14.  */
  15.  
  16. /*  ARC - Archive utility - ARCLZW
  17.  
  18. $define(tag,$$segment(@1,$$index(@1,=)+1))#
  19. $define(version,Version $tag(
  20. TED_VERSION DB =1.88), created on $tag(
  21. TED_DATE DB =01/20/86) at $tag(
  22. TED_TIME DB =16:47:04))#
  23. $undefine(tag)#
  24.     $version
  25.  
  26. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  27.  
  28.     By:  Thom Henderson
  29.  
  30.     Description:
  31.          This file contains the routines used to implement Lempel-Zev
  32.          data compression, which calls for building a coding table on
  33.          the fly.  This form of compression is especially good for encoding
  34.          files which contain repeated strings, and can often give dramatic
  35.          improvements over traditional Huffman SQueezing.
  36.  
  37.     Language:
  38.          Computer Innovations Optimizing C86
  39.  
  40.     Programming notes:
  41.          In this section I am drawing heavily on the COMPRESS program
  42.          from UNIX.  The basic method is taken from "A Technique for High
  43.          Performance Data Compression", Terry A. Welch, IEEE Computer
  44.          Vol 17, No 6 (June 1984), pp 8-19.  Also see "Knuth's Fundamental
  45.          Algorithms", Donald Knuth, Vol 3, Section 6.4.
  46.  
  47.          As best as I can tell, this method works by tracing down a hash
  48.          table of code strings where each entry has the property:
  49.  
  50.               if <string> <char> is in the table
  51.               then <string> is in the table.
  52. */
  53. #include <stdio.h>
  54. #include "arc.h"
  55.  
  56. /* definitions for older style crunching */
  57.  
  58. #define FALSE    0
  59. #define TRUE     !FALSE
  60. #define TABSIZE  4096
  61. #define NO_PRED  0xFFFF
  62. #define EMPTY    0xFFFF
  63. #define NOT_FND  0xFFFF
  64.  
  65. static unsigned INT inbuf;             /* partial input code storage */
  66. static INT sp;                         /* current stack pointer */
  67.  
  68. static struct entry                    /* string table entry format */
  69. {   char used;                         /* true when this entry is in use */
  70.     unsigned INT next;                 /* ptr to next in collision list */
  71.     unsigned INT predecessor;          /* code for preceeding string */
  72.     unsigned char follower;            /* char following string */
  73. }   string_tab[TABSIZE];               /* the code string table */
  74.  
  75. /* definitions for the new dynamic Lempel-Zev crunching */
  76.  
  77. #define BITS   12                      /* maximum bits per code */
  78. #define HSIZE  5003                    /* 80% occupancy */
  79. #define INIT_BITS 9                    /* initial number of bits/code */
  80.  
  81. static INT n_bits;                     /* number of bits/code */
  82. static INT maxcode;                    /* maximum code, given n_bits */
  83. #define MAXCODE(n)      ((1<<(n)) - 1) /* maximum code calculation */
  84. static INT maxcodemax =  1 << BITS;    /* largest possible code (+1) */
  85.  
  86. static unsigned char buf[BITS];        /* input/output buffer */
  87.  
  88. static unsigned char lmask[9] =        /* left side masks */
  89. {   0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00 };
  90. static unsigned char rmask[9] =        /* right side masks */
  91. {   0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  92.  
  93. static INT offset;                     /* byte offset for code output */
  94. static long in_count;                  /* length of input */
  95. static long bytes_out;                 /* length of compressed output */
  96. static unsigned INT ent;
  97.  
  98. /* To save much memory (which we badly need at this point), we overlay
  99.  * the table used by the previous version of Lempel-Zev with those used
  100.  * by the new version.  Since no two of these routines will be used
  101.  * together, we can safely do this.  Note that the tables used for Huffman
  102.  * squeezing may NOT overlay these, since squeezing and crunching are done
  103.  * in parallel.
  104.  */
  105.  
  106. #if MSDOS
  107. static long *htab = string_tab;        /* hash code table   (crunch) */
  108. #endif
  109. #if BSD | ST
  110. static long htab[HSIZE];               /* hash code table   (crunch) */
  111. #endif
  112. static unsigned INT codetab[HSIZE];    /* string code table (crunch) */
  113.  
  114. static unsigned INT *prefix = codetab; /* prefix code table (uncrunch) */
  115.  
  116. #if MSDOS
  117. static unsigned char *suffix = string_tab;  /* suffix table (uncrunch) */
  118. #endif
  119. #if BSD | ST
  120. static unsigned char suffix[HSIZE];    /* suffix table (uncrunch) */
  121. #endif
  122. static INT free_ent;                   /* first unused entry */
  123. static INT firstcmp;                   /* true at start of compression */
  124. static unsigned char stack[HSIZE];     /* local push/pop stack */
  125.  
  126. /*
  127.  * block compression parameters -- after all codes are used up,
  128.  * and compression rate changes, start over.
  129.  */
  130.  
  131. static INT clear_flg;
  132. static long ratio;
  133. #define CHECK_GAP 10000                /* ratio check interval */
  134. static long checkpoint;
  135.  
  136. /*
  137.  * the next two codes should not be changed lightly, as they must not
  138.  * lie within the contiguous general code space.
  139.  */
  140. #define FIRST   257                    /* first free entry */
  141. #define CLEAR   256                    /* table clear output code */
  142.  
  143. static INT cl_block(t)                     /* table clear for block compress */
  144. FILE *t;                               /* our output file */
  145. {
  146.     long rat;
  147.     INT putcode();
  148.  
  149.     checkpoint = in_count + CHECK_GAP;
  150.  
  151.     if(in_count > 0x007fffff)          /* shift will overflow */
  152.     {    rat = bytes_out >> 8;
  153.          if(rat == 0)                  /* Don't divide by zero */
  154.               rat = 0x7fffffff;
  155.          else rat = in_count / rat;
  156.     }
  157.     else rat = (in_count<<8)/bytes_out;/* 8 fractional bits */
  158.  
  159.     if(rat > ratio)
  160.          ratio = rat;
  161.     else
  162.     {    ratio = 0;
  163.          setmem    (htab,HSIZE*sizeof(long),0xff);
  164.          free_ent = FIRST;
  165.          clear_flg = 1;
  166.          putcode(CLEAR,t);
  167.     }
  168. }
  169.  
  170. /*****************************************************************
  171.  *
  172.  * Output a given code.
  173.  * Inputs:
  174.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  175.  *              that n_bits =< (long)wordsize - 1.
  176.  * Outputs:
  177.  *      Outputs code to the file.
  178.  * Assumptions:
  179.  *      Chars are 8 bits long.
  180.  * Algorithm:
  181.  *      Maintain a BITS character long buffer (so that 8 codes will
  182.  * fit in it exactly).  When the buffer fills up empty it and start over.
  183.  */
  184.  
  185. static INT putcode(code,t)                 /* output a code */
  186. INT code;                              /* code to output */
  187. FILE *t;                               /* where to put it */
  188. {
  189.  INT r_off = offset;                /* right offset */
  190.  INT bits = n_bits;                 /* bits to go */
  191.  unsigned char *bp = buf;           /* buffer pointer */
  192.  INT n;                             /* index */
  193.  
  194.     if(code >= 0)                      /* if a real code */
  195.     {    /*
  196.           * Get to the first byte.
  197.           */
  198.          bp += (r_off >> 3);
  199.          r_off &= 7;
  200.  
  201.          /*
  202.           * Since code is always >= 8 bits, only need to mask the first
  203.           * hunk on the left.
  204.           */
  205.          *bp = (*bp&rmask[r_off]) | (code<<r_off) & lmask[r_off];
  206.          bp++;
  207.          bits -= (8 - r_off);
  208.          code >>= (8 - r_off);
  209.  
  210.          /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  211.          if(bits >= 8)
  212.          {    *bp++ = code;
  213.               code >>= 8;
  214.               bits -= 8;
  215.          }
  216.  
  217.          /* Last bits. */
  218.          if(bits)
  219.               *bp = code;
  220.  
  221.          offset += n_bits;
  222.  
  223.          if(offset == (n_bits << 3))
  224.          {    bp = buf;
  225.               bits = n_bits;
  226.               bytes_out += bits;
  227.               do
  228.                    putc_pak(*bp++,t);
  229.               while(--bits);
  230.               offset = 0;
  231.          }
  232.  
  233.          /*
  234.           * If the next entry is going to be too big for the code size,
  235.           * then increase it, if possible.
  236.           */
  237.          if(free_ent>maxcode || clear_flg>0)
  238.          {    /*
  239.                * Write the whole buffer, because the input side won't
  240.                * discover the size increase until after it has read it.
  241.                */
  242.               if(offset > 0)
  243.               {    bp = buf;           /* reset pointer for writing */
  244.                    bytes_out += n = n_bits;
  245.                    while(n--)
  246.                         putc_pak(*bp++,t);
  247.               }
  248.               offset = 0;
  249.  
  250.               if(clear_flg)            /* reset if clearing */
  251.               {    maxcode = MAXCODE(n_bits = INIT_BITS);
  252.                    clear_flg = 0;
  253.               }
  254.               else                     /* else use more bits */
  255.               {    n_bits++;
  256.                    if(n_bits == BITS)
  257.                         maxcode = maxcodemax;
  258.                    else
  259.                         maxcode = MAXCODE(n_bits);
  260.               }
  261.          }
  262.     }
  263.  
  264.     else                               /* dump the buffer on EOF */
  265.     {    bytes_out += n = (offset+7) / 8;
  266.  
  267.          if(offset > 0)
  268.               while(n--)
  269.                    putc_pak(*bp++,t);
  270.          offset = 0;
  271.     }
  272. }
  273.  
  274. /*****************************************************************
  275.  *
  276.  * Read one code from the standard input.  If EOF, return -1.
  277.  * Inputs:
  278.  *      cmpin
  279.  * Outputs:
  280.  *      code or -1 is returned.
  281.  */
  282.  
  283. static INT getcode(f)                  /* get a code */
  284. FILE *f;                               /* file to get from */
  285. {
  286.  INT code;
  287.     static INT offset = 0, size = 0;
  288.  INT r_off, bits;
  289.     unsigned char *bp = buf;
  290.  
  291.     if(clear_flg > 0 || offset >= size || free_ent > maxcode)
  292.     {    /*
  293.           * If the next entry will be too big for the current code
  294.           * size, then we must increase the size.  This implies reading
  295.           * a new buffer full, too.
  296.           */
  297.          if(free_ent > maxcode)
  298.          {    n_bits++;
  299.               if(n_bits == BITS)
  300.                    maxcode = maxcodemax;    /* won't get any bigger now */
  301.               else maxcode = MAXCODE(n_bits);
  302.          }
  303.          if(clear_flg > 0)
  304.          {    maxcode = MAXCODE(n_bits = INIT_BITS);
  305.               clear_flg = 0;
  306.          }
  307.  
  308.          for(size=0; size<n_bits; size++)
  309.          {    if((code=getc_unp(f))==EOF)
  310.                    break;
  311.               else buf[size] = code;
  312.          }
  313.          if(size <= 0)
  314.               return -1;               /* end of file */
  315.  
  316.          offset = 0;
  317.          /* Round size down to integral number of codes */
  318.          size = (size << 3)-(n_bits - 1);
  319.     }
  320.     r_off = offset;
  321.     bits = n_bits;
  322.  
  323.     /*
  324.      * Get to the first byte.
  325.      */
  326.     bp +=(r_off >> 3);
  327.     r_off &= 7;
  328.  
  329.     /* Get first part (low order bits) */
  330.     code = (*bp++ >> r_off);
  331.     bits -= 8 - r_off;
  332.     r_off = 8 - r_off;                 /* now, offset into code word */
  333.  
  334.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  335.     if(bits >= 8)
  336.     {    code |= *bp++ << r_off;
  337.          r_off += 8;
  338.          bits -= 8;
  339.     }
  340.     /* high order bits. */
  341.     code |= (*bp & rmask[bits]) << r_off;
  342.     offset += n_bits;
  343.  
  344.     return code;
  345. }
  346.  
  347. /*
  348.  * compress a file
  349.  *
  350.  * Algorithm:  use open addressing double hashing (no chaining) on the
  351.  * prefix code / next character combination.  We do a variant of Knuth's
  352.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  353.  * secondary probe.  Here, the modular division first probe is gives way
  354.  * to a faster exclusive-or manipulation.  Also do block compression with
  355.  * an adaptive reset, where the code table is cleared when the compression
  356.  * ratio decreases, but after the table fills.  The variable-length output
  357.  * codes are re-sized at this point, and a special CLEAR code is generated
  358.  * for the decompressor.
  359.  */
  360.  
  361. INT init_cm(f,t)                           /* initialize for compression */
  362. FILE *f;                               /* file we will be compressing */
  363. FILE *t;                               /* where we will put it */
  364. {
  365.     offset = 0;
  366.     bytes_out = 1;
  367.     clear_flg = 0;
  368.     ratio = 0;
  369.     in_count = 1;
  370.     checkpoint = CHECK_GAP;
  371.     maxcode = MAXCODE(n_bits = INIT_BITS);
  372.     free_ent = FIRST;
  373.     setmem(htab,HSIZE*sizeof(long),0xff);
  374.     n_bits = INIT_BITS;                /* set starting code size */
  375.  
  376.     putc_pak(BITS,t);                  /* note our max code length */
  377.  
  378.     firstcmp = 1;                      /* next byte will be first */
  379. }
  380.  
  381. INT putc_cm(c,t)                           /* compress a character */
  382. unsigned char c;                       /* character to compress */
  383. FILE *t;                               /* where to put it */
  384. {
  385.     static long fcode;
  386.     static INT hshift;
  387.  INT i;
  388.  INT disp;
  389.  
  390.     if(firstcmp)                       /* special case for first byte */
  391.     {    ent = c;                      /* remember first byte */
  392.  
  393.          hshift = 0;
  394.          for(fcode=(long)HSIZE;  fcode<65536L; fcode*=2L)
  395.               hshift++;
  396.          hshift = 8 - hshift;          /* set hash code range bund */
  397.  
  398.          firstcmp = 0;                 /* no longer first */
  399.          return;
  400.     }
  401.  
  402.     in_count++;
  403.     fcode =(long)(((long)c << BITS)+ent);
  404.     i = (c<<hshift)^ent;               /* xor hashing */
  405.  
  406.     if(htab[i]==fcode)
  407.     {    ent = codetab[i];
  408.          return;
  409.     }
  410.     else if(htab[i]<0)                 /* empty slot */
  411.          goto nomatch;
  412.     disp = HSIZE - i;                  /* secondary hash (after G.Knott) */
  413.     if(i == 0)
  414.          disp = 1;
  415.  
  416. probe:
  417.     if((i -= disp) < 0)
  418.          i += HSIZE;
  419.  
  420.     if(htab[i] == fcode)
  421.     {    ent = codetab[i];
  422.          return;
  423.     }
  424.     if(htab[i] > 0)
  425.          goto probe;
  426.  
  427. nomatch:
  428.     putcode(ent,t);
  429.     ent = c;
  430.     if(free_ent < maxcodemax)
  431.     {    codetab[i] = free_ent++;      /* code -> hashtable */
  432.          htab[i] = fcode;
  433.     }
  434.     else if((long)in_count >= checkpoint)
  435.          cl_block(t);
  436. }
  437.  
  438. long pred_cm(t)                        /* finish compressing a file */
  439. FILE *t;                               /* where to put it */
  440. {
  441.     putcode(ent,t);                    /* put out the final code */
  442.     putcode(-1,t);                     /* tell output we are done */
  443.  
  444.     return bytes_out;                  /* say how big it got */
  445. }
  446.  
  447. /*
  448.  * Decompress a file.  This routine adapts to the codes in the file
  449.  * building the string table on-the-fly; requiring no table to be stored
  450.  * in the compressed file.  The tables used herein are shared with those of
  451.  * the compress() routine.  See the definitions above.
  452.  */
  453.  
  454. INT decomp(f,t)                            /* decompress a file */
  455. FILE *f;                               /* file to read codes from */
  456. FILE *t;                               /* file to write text to */
  457. {
  458.     unsigned char *stackp;
  459.  INT finchar;
  460.  INT code, oldcode, incode;
  461.  
  462.     if((code=getc_unp(f))!=BITS)
  463.          abort("File packed with %d bits, I can only handle %d",code,BITS);
  464.  
  465.     n_bits = INIT_BITS;                /* set starting code size */
  466.     clear_flg = 0;
  467.  
  468.     /*
  469.      * As above, initialize the first 256 entries in the table.
  470.      */
  471.     maxcode = MAXCODE(n_bits=INIT_BITS);
  472.     for(code = 255; code >= 0; code--)
  473.     {    prefix[code] = 0;
  474.          suffix[code] = (unsigned char)code;
  475.     }
  476.     free_ent = FIRST;
  477.  
  478.     finchar = oldcode = getcode(f);
  479.     if(oldcode == -1)                  /* EOF already? */
  480.          return;                       /* Get out of here */
  481.     putc_ncr((char)finchar,t);         /* first code must be 8 bits=char */
  482.     stackp = stack;
  483.  
  484.     while((code = getcode(f))> -1)
  485.     {    if(code==CLEAR)
  486.          {    for(code = 255; code >= 0; code--)
  487.                    prefix[code] = 0;
  488.               clear_flg = 1;
  489.               free_ent = FIRST - 1;
  490.               if((code=getcode(f))==-1)/* O, untimely death! */
  491.                    break;
  492.          }
  493.          incode = code;
  494.          /*
  495.           * Special case for KwKwK string.
  496.           */
  497.          if(code >= free_ent)
  498.          {    *stackp++ = finchar;
  499.               code = oldcode;
  500.          }
  501.  
  502.          /*
  503.           * Generate output characters in reverse order
  504.           */
  505.          while(code >= 256)
  506.          {    *stackp++ = suffix[code];
  507.               code = prefix[code];
  508.          }
  509.          *stackp++ = finchar = suffix[code];
  510.  
  511.          /*
  512.           * And put them out in forward order
  513.           */
  514.          do
  515.               putc_ncr(*--stackp,t);
  516.          while(stackp > stack);
  517.  
  518.          /*
  519.           * Generate the new entry.
  520.           */
  521.          if((code=free_ent) < maxcodemax)
  522.          {    prefix[code] = (unsigned short)oldcode;
  523.               suffix[code] = finchar;
  524.               free_ent = code+1;
  525.          }
  526.          /*
  527.           * Remember previous code.
  528.           */
  529.          oldcode = incode;
  530.     }
  531. }
  532.  
  533. /*************************************************************************
  534.  * Please note how much trouble it can be to maintain upwards            *
  535.  * compatibility.  All that follows is for the sole purpose of unpacking *
  536.  * files which were packed using an older method.                        *
  537.  *************************************************************************/
  538.  
  539. /*  The h() pointer points to the routine to use for calculating a hash
  540.     value.  It is set in the init routines to point to either of oldh()
  541.     or newh().
  542.  
  543.     oldh() calculates a hash value by taking the middle twelve bits
  544.     of the square of the key.
  545.  
  546.     newh() works somewhat differently, and was tried because it makes
  547.     ARC about 23% faster.  This approach was abandoned because dynamic
  548.     Lempel-Zev (above) works as well, and packs smaller also.  However,
  549.     inadvertent release of a developmental copy forces us to leave this in.
  550. */
  551.  
  552. static unsigned INT (*h)();                /* pointer to hash function */
  553.  
  554. static unsigned INT oldh(pred,foll)        /* old hash function */
  555. unsigned INT pred;                     /* code for preceeding string */
  556. unsigned char foll;                    /* value of following char */
  557. {
  558.     long local;                        /* local hash value */
  559.  
  560.     local = ((pred + foll) | 0x0800) & 0xffff;    /* create the hash key */
  561.     /*local = (pred + foll) | 0x0800;    /* create the hash key */
  562.     local *= local;                    /* square it */
  563.     return (local >> 6) & 0x0FFF;      /* return the middle 12 bits */
  564. }
  565.  
  566. static unsigned INT newh(pred,foll)        /* new hash function */
  567. unsigned INT pred;                     /* code for preceeding string */
  568. unsigned char foll;                    /* value of following char */
  569. {
  570.     return (((pred+foll)&0xffff)*15073)&0xFFF;  /* faster hash */
  571.     /*return ((pred+foll)*15073)&0xFFF;  /* faster hash */
  572. }
  573.  
  574. /*  The eolist() function is used to trace down a list of entries with
  575.     duplicate keys until the last duplicate is found.
  576. */
  577.  
  578. static unsigned INT eolist(index)          /* find last duplicate */
  579. unsigned INT index;
  580. {
  581.  INT temp;
  582.  
  583.     while(temp=string_tab[index].next) /* while more duplicates */
  584.          index = temp;
  585.  
  586.     return index;
  587. }
  588.  
  589. /*  The hash() routine is used to find a spot in the hash table for a new
  590.     entry.  It performs a "hash and linear probe" lookup, using h() to
  591.     calculate the starting hash value and eolist() to perform the linear
  592.     probe.  This routine DOES NOT detect a table full condition.  That
  593.     MUST be checked for elsewhere.
  594. */
  595.  
  596. static unsigned INT hash(pred,foll)        /* find spot in the string table */
  597. unsigned INT pred;                     /* code for preceeding string */
  598. unsigned char foll;                    /* char following string */
  599. {
  600.     unsigned INT local, tempnext;      /* scratch storage */
  601.     struct entry *ep;                  /* allows faster table handling */
  602.  
  603.     local = (*h)(pred,foll);           /* get initial hash value */
  604.  
  605.     if(!string_tab[local].used)        /* if that spot is free */
  606.          return local;                 /* then that's all we need */
  607.  
  608.     else                               /* else a collision has occured */
  609.     {    local = eolist(local);        /* move to last duplicate */
  610.  
  611.          /*   We must find an empty spot. We start looking 101 places
  612.               down the table from the last duplicate.
  613.          */
  614.  
  615.          tempnext = (local+101) & 0x0FFF;
  616.          ep = &string_tab[tempnext];   /* initialize pointer */
  617.  
  618.          while(ep->used)               /* while empty spot not found */
  619.          {    if(++tempnext==TABSIZE)  /* if we are at the end */
  620.               {    tempnext = 0;       /* wrap to beginning of table*/
  621.                    ep = string_tab;
  622.               }
  623.               else ++ep;               /* point to next element in table */
  624.          }
  625.  
  626.          /*   local still has the pointer to the last duplicate, while
  627.               tempnext has the pointer to the spot we found.  We use
  628.               this to maintain the chain of pointers to duplicates.
  629.          */
  630.  
  631.          string_tab[local].next = tempnext;
  632.  
  633.          return tempnext;
  634.     }
  635. }
  636.  
  637. /*  The unhash() function is used to search the hash table for a given key.
  638.     Like hash(), it performs a hash and linear probe search.  It returns
  639.     either the number of the entry (if found) or NOT_FND (if not found).
  640. */
  641.  
  642. static unsigned INT unhash(pred,foll)      /* search string table for a key */
  643. unsigned INT pred;                     /* code of preceeding string */
  644. unsigned char foll;                    /* character following string */
  645. {
  646.     unsigned INT local, offset;        /* scratch storage */
  647.     struct entry *ep;                  /* this speeds up access */
  648.  
  649.     local = (*h)(pred,foll);           /* initial hash */
  650.  
  651.     while(1)
  652.     {    ep = &string_tab[local];      /* speed up table access */
  653.  
  654.          if((ep->predecessor==pred) && (ep->follower==foll))
  655.               return local;            /* we have a match */
  656.  
  657.          if(!ep->next)                 /* if no more duplicates */
  658.               return NOT_FND;          /* then key is not listed */
  659.  
  660.          local = ep->next;             /* move on to next duplicate */
  661.     }
  662. }
  663.  
  664. /*  The init_tab() routine is used to initialize our hash table.
  665.     You realize, of course, that "initialize" is a complete misnomer.
  666. */
  667.  
  668. static INT init_tab()                      /* set ground state in hash table */
  669. {
  670.     unsigned INT i;                    /* table index */
  671.     INT upd_tab();
  672.  
  673.     setmem((char *)string_tab,sizeof(string_tab),0);
  674.  
  675.     for(i=0; i<256; i++)               /* list all single byte strings */
  676.          upd_tab(NO_PRED,i);
  677.  
  678.     inbuf = EMPTY;                     /* nothing is in our buffer */
  679. }
  680.  
  681. /*  The upd_tab routine is used to add a new entry to the string table.
  682.     As previously stated, no checks are made to ensure that the table
  683.     has any room.  This must be done elsewhere.
  684. */
  685.  
  686. INT upd_tab(pred,foll)                     /* add an entry to the table */
  687. unsigned INT pred;                     /* code for preceeding string */
  688. unsigned INT foll;                     /* character which follows string */
  689. {
  690.     struct entry *ep;                  /* pointer to current entry */
  691.  
  692.     /* calculate offset just once */
  693.  
  694.     ep = &string_tab[hash(pred,foll)];
  695.  
  696.     ep->used = TRUE;                   /* this spot is now in use */
  697.     ep->next = 0;                      /* no duplicates after this yet */
  698.     ep->predecessor = pred;            /* note code of preceeding string */
  699.     ep->follower = foll;               /* note char after string */
  700. }
  701.  
  702. /*  This algorithm encoded a file into twelve bit strings (three nybbles).
  703.     The gocode() routine is used to read these strings a byte (or two)
  704.     at a time.
  705. */
  706.  
  707. static INT gocode(fd)                      /* read in a twelve bit code */
  708. FILE *fd;                              /* file to get code from */
  709. {
  710.     unsigned INT localbuf, returnval;
  711.  
  712.     if(inbuf==EMPTY)                   /* if on a code boundary */
  713.     {    if((localbuf=getc_unp(fd))==EOF)   /* get start of next code */
  714.               return EOF;              /* pass back end of file status */
  715.          localbuf &= 0xFF;             /* mask down to true byte value */
  716.          if((inbuf=getc_unp(fd))==EOF) /* get end of code, start of next */
  717.               return EOF;              /* this should never happen */
  718.          inbuf &= 0xFF;                /* mask down to true byte value */
  719.  
  720.          returnval = ((localbuf<<4)&0xFF0) + ((inbuf>>4)&0x00F);
  721.          inbuf &= 0x000F;              /* leave partial code pending */
  722.     }
  723.  
  724.     else                               /* buffer contains first nybble */
  725.     {    if((localbuf=getc_unp(fd))==EOF)
  726.               return EOF;
  727.          localbuf &= 0xFF;
  728.  
  729.          returnval = localbuf + ((inbuf<<8)&0xF00);
  730.          inbuf = EMPTY;                /* note no hanging nybbles */
  731.     }
  732.     return returnval;                  /* pass back assembled code */
  733. }
  734.  
  735. static INT push(c)                         /* push char onto stack */
  736. INT c;                                 /* character to push */
  737. {
  738.     stack[sp] = ((char) c);            /* coerce integer into a char */
  739.  
  740.     if(++sp >= TABSIZE)
  741.          abort("Stack overflow\n");
  742. }
  743.  
  744. static INT pop()                       /* pop character from stack */
  745. {
  746.     if(sp>0)
  747.          return ((INT) stack[--sp]);   /* leave ptr at next empty slot */
  748.  
  749.     else return EMPTY;
  750. }
  751.  
  752. /***** LEMPEL-ZEV DECOMPRESSION *****/
  753.  
  754. static INT code_count;                 /* needed to detect table full */
  755. static unsigned INT code;                  /* where we are so far */
  756. static INT firstc;                     /* true only on first character */
  757.  
  758. INT init_ucr(new)                          /* get set for uncrunching */
  759. INT new;                               /* true to use new hash function */
  760. {
  761.     if(new)                            /* set proper hash function */
  762.          h = newh;
  763.     else h = oldh;
  764.  
  765.     sp = 0;                            /* clear out the stack */
  766.     init_tab();                        /* set up atomic code definitions */
  767.     code_count = TABSIZE - 256;        /* note space left in table */
  768.     firstc = 1;                        /* true only on first code */
  769. }
  770.  
  771. INT getc_ucr(f)                        /* get next uncrunched byte */
  772. FILE *f;                               /* file containing crunched data */
  773. {
  774.     unsigned INT c;                    /* a character of input */
  775.  INT code, newcode;
  776.     static INT oldcode, finchar;
  777.     struct entry *ep;                  /* allows faster table handling */
  778.  
  779.     if(firstc)                         /* first code is always known */
  780.     {    firstc = FALSE;               /* but next will not be first */
  781.          oldcode = gocode(f);
  782.          return finchar = string_tab[oldcode].follower;
  783.     }
  784.  
  785.     if(!sp)                            /* if stack is empty */
  786.     {    if((code=newcode=gocode(f))==EOF)
  787.               return EOF;
  788.  
  789.          ep = &string_tab[code];       /* initialize pointer */
  790.  
  791.          if(!ep->used)                 /* if code isn't known */
  792.          {    code = oldcode;
  793.               ep = &string_tab[code];  /* re-initialize pointer */
  794.               push(finchar);
  795.          }
  796.  
  797.          while(ep->predecessor!=NO_PRED)
  798.          {    push(ep->follower);      /* decode string backwards */
  799.               code = ep->predecessor;
  800.               ep = &string_tab[code];
  801.          }
  802.  
  803.          push(finchar=ep->follower);   /* save first character also */
  804.  
  805.          /*   The above loop will terminate, one way or another,
  806.               with string_tab[code].follower equal to the first
  807.               character in the string.
  808.          */
  809.  
  810.          if(code_count)                /* if room left in string table */
  811.          {    upd_tab(oldcode,finchar);
  812.               --code_count;
  813.          }
  814.  
  815.          oldcode = newcode;
  816.     }
  817.  
  818.     return pop();                      /* return saved character */
  819. }
  820.