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