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