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