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