home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 28 / amigaformatcd28.iso / -seriously_amiga- / archivers / arcppc / src / rcs / arclzw.c,v < prev    next >
Text File  |  1998-04-23  |  30KB  |  1,209 lines
  1. head     1.6;
  2. branch   ;
  3. access   ;
  4. symbols  patch1:1.6;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.6
  10. date     88.07.31.18.49.49;  author hyc;  state Exp;
  11. branches ;
  12. next     1.5;
  13.  
  14. 1.5
  15. date     88.07.01.15.57.14;  author hyc;  state Exp;
  16. branches ;
  17. next     1.4;
  18.  
  19. 1.4
  20. date     88.06.01.16.27.59;  author hyc;  state Exp;
  21. branches ;
  22. next     1.3;
  23.  
  24. 1.3
  25. date     88.06.01.15.50.26;  author hyc;  state Exp;
  26. branches ;
  27. next     1.2;
  28.  
  29. 1.2
  30. date     88.06.01.14.44.34;  author hyc;  state Exp;
  31. branches ;
  32. next     1.1;
  33.  
  34. 1.1
  35. date     88.04.11.18.12.18;  author hyc;  state Exp;
  36. branches ;
  37. next     ;
  38.  
  39.  
  40. desc
  41. @fix bugs in old style crunching caused by word size problems,
  42. re-synch with MTS...
  43. @
  44.  
  45.  
  46. 1.6
  47. log
  48. @Get rid of "nested" comment.
  49. @
  50. text
  51. @/*
  52.  * $Header: arclzw.c,v 1.5 88/07/01 15:57:14 hyc Locked $
  53.  */
  54.  
  55. /*
  56.  * ARC - Archive utility - ARCLZW
  57.  * 
  58.  * Version 2.03, created on 10/24/86 at 11:46:22
  59.  * 
  60.  * (C) COPYRIGHT 1985,86 by System Enhancement Associates; ALL RIGHTS RESERVED
  61.  * 
  62.  * By:  Thom Henderson
  63.  * 
  64.  * Description: This file contains the routines used to implement Lempel-Zev
  65.  * data compression, which calls for building a coding table on the fly.
  66.  * This form of compression is especially good for encoding files which
  67.  * contain repeated strings, and can often give dramatic improvements over
  68.  * traditional Huffman SQueezing.
  69.  * 
  70.  * Language: Computer Innovations Optimizing C86
  71.  * 
  72.  * Programming notes: In this section I am drawing heavily on the COMPRESS
  73.  * program from UNIX.  The basic method is taken from "A Technique for High
  74.  * Performance Data Compression", Terry A. Welch, IEEE Computer Vol 17, No 6
  75.  * (June 1984), pp 8-19.  Also see "Knuth's Fundamental Algorithms", Donald
  76.  * Knuth, Vol 3, Section 6.4.
  77.  * 
  78.  * As best as I can tell, this method works by tracing down a hash table of code
  79.  * strings where each entry has the property:
  80.  * 
  81.  * if <string> <char> is in the table then <string> is in the table.
  82.  */
  83. #include <stdio.h>
  84. #include "arc.h"
  85.  
  86. void    putc_pak(), abort(), putc_ncr();
  87. int    getc_unp();
  88. #if    MSDOS
  89. char    *setmem();
  90. #else
  91. char    *memset();
  92. #endif
  93.  
  94. static void    putcode();
  95. /* definitions for older style crunching */
  96.  
  97. #define FALSE    0
  98. #define TRUE     !FALSE
  99. #define TABSIZE  4096
  100. #define NO_PRED  0xFFFF
  101. #define EMPTY    0xFFFF
  102. #define NOT_FND  0xFFFF
  103.  
  104. static unsigned short inbuf;    /* partial input code storage */
  105. static int      sp;        /* current stack pointer */
  106.  
  107. struct entry {        /* string table entry format */
  108.     char            used;    /* true when this entry is in use */
  109.     unsigned char   follower;    /* char following string */
  110.     unsigned short  next;    /* ptr to next in collision list */
  111.     unsigned short  predecessor;    /* code for preceeding string */
  112. };            /* string_tab[TABSIZE];       the code string table */
  113.  
  114.  
  115. /* definitions for the new dynamic Lempel-Zev crunching */
  116.  
  117. #define BITS   12        /* maximum bits per code */
  118. #define HSIZE  5003        /* 80% occupancy */
  119. #define INIT_BITS 9        /* initial number of bits/code */
  120.  
  121. static int      n_bits;        /* number of bits/code */
  122. static int      maxcode;    /* maximum code, given n_bits */
  123. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  124. static int      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  125.  
  126. static char     buf[BITS];    /* input/output buffer */
  127.  
  128. static unsigned char lmask[9] =    /* left side masks */
  129. {
  130.  0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00
  131. };
  132. static unsigned char rmask[9] =    /* right side masks */
  133. {
  134.  0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff
  135. };
  136.  
  137. static int      offset;        /* byte offset for code output */
  138. static long     in_count;    /* length of input */
  139. static long     bytes_out;    /* length of compressed output */
  140. static long     bytes_ref;    /* output quality reference */
  141. static long     bytes_last;    /* output size at last checkpoint */
  142. static unsigned short ent;
  143.  
  144. /*
  145.  * To save much memory (which we badly need at this point), we overlay the
  146.  * table used by the previous version of Lempel-Zev with those used by the
  147.  * new version.  Since no two of these routines will be used together, we can
  148.  * safely do this.
  149.  */
  150.  
  151. extern long     htab[HSIZE];        /* hash code table   (crunch) */
  152. extern unsigned short codetab[HSIZE];    /* string code table (crunch) */
  153. static struct    entry *string_tab=(struct entry *)htab;    /* old crunch string table */
  154.  
  155. static unsigned short *prefix=codetab;    /* prefix code table (uncrunch) */
  156. static unsigned char *suffix=(unsigned char *)htab;    /* suffix table (uncrunch) */
  157.  
  158. static int      free_ent;    /* first unused entry */
  159. static int      firstcmp;    /* true at start of compression */
  160. extern unsigned char stack[HSIZE];    /* local push/pop stack */
  161.  
  162. /*
  163.  * block compression parameters -- after all codes are used up, and
  164.  * compression rate changes, start over.
  165.  */
  166.  
  167. static int      clear_flg;
  168. #define CHECK_GAP 2048        /* ratio check interval */
  169. static long     checkpoint;
  170. void            upd_tab();
  171.  
  172. /*
  173.  * the next two codes should not be changed lightly, as they must not lie
  174.  * within the contiguous general code space.
  175.  */
  176. #define FIRST   257        /* first free entry */
  177. #define CLEAR   256        /* table clear output code */
  178.  
  179. /*
  180.  * The cl_block() routine is called at each checkpoint to determine if
  181.  * compression would likely improve by resetting the code table.  The method
  182.  * chosen to determine this is based on empirical observation that, in
  183.  * general, every 2k of input data should compress at least as well as the
  184.  * first 2k of input.
  185.  */
  186.  
  187. static          void
  188. cl_block(t)            /* table clear for block compress */
  189.     FILE           *t;    /* our output file */
  190. {
  191.     checkpoint = in_count + CHECK_GAP;
  192.  
  193.     if (bytes_ref) {
  194.         if (bytes_out - bytes_last > bytes_ref) {
  195.             setmem(htab, HSIZE * sizeof(long), 0xff);
  196.             free_ent = FIRST;
  197.             clear_flg = 1;
  198.             putcode(CLEAR, t);
  199.             bytes_ref = 0;
  200.         }
  201.     } else
  202.         bytes_ref = bytes_out - bytes_last;
  203.  
  204.     bytes_last = bytes_out;    /* remember where we were */
  205. }
  206.  
  207. /*****************************************************************
  208.  *
  209.  * Output a given code.
  210.  * Inputs:
  211.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  212.  *              that n_bits =< (LONG)wordsize - 1.
  213.  * Outputs:
  214.  *      Outputs code to the file.
  215.  * Assumptions:
  216.  *      Chars are 8 bits long.
  217.  * Algorithm:
  218.  *      Maintain a BITS character long buffer (so that 8 codes will
  219.  * fit in it exactly).  When the buffer fills up empty it and start over.
  220.  */
  221.  
  222. static          void
  223. putcode(code, t)        /* output a code */
  224.     int             code;    /* code to output */
  225.     FILE           *t;    /* where to put it */
  226. {
  227.     int             r_off = offset;    /* right offset */
  228.     int             bits = n_bits;    /* bits to go */
  229.     char           *bp = buf;    /* buffer pointer */
  230.     int             n;    /* index */
  231.  
  232.     register int    ztmp;
  233.  
  234.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  235.         bp += (r_off >> 3);
  236.         r_off &= 7;
  237.  
  238.         /*
  239.          * Since code is always >= 8 bits, only need to mask the
  240.          * first hunk on the left. 
  241.          */
  242.         ztmp = (code << r_off) & lmask[r_off];
  243.         *bp = (*bp & rmask[r_off]) | ztmp;
  244.         bp++;
  245.         bits -= (8 - r_off);
  246.         code >>= (8 - r_off);
  247.  
  248.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  249.         if (bits >= 8) {
  250.             *bp++ = code;
  251.             code >>= 8;
  252.             bits -= 8;
  253.         }
  254.         /* Last bits. */
  255.         if (bits)
  256.             *bp = code;
  257.         offset += n_bits;
  258.  
  259.         if (offset == (n_bits << 3)) {
  260.             bp = buf;
  261.             bits = n_bits;
  262.             bytes_out += bits;
  263.             do
  264.                 putc_pak(*bp++, t);
  265.             while (--bits);
  266.             offset = 0;
  267.         }
  268.         /*
  269.          * If the next entry is going to be too big for the code
  270.          * size, then increase it, if possible. 
  271.          */
  272.         if (free_ent > maxcode || clear_flg > 0) {
  273.             /*
  274.              * Write the whole buffer, because the input side
  275.              * won't discover the size increase until after
  276.              * it has read it. 
  277.              */
  278.             if (offset > 0) {
  279.                 bp = buf;    /* reset pointer for writing */
  280.                 bytes_out += n = n_bits;
  281.                 while (n--)
  282.                     putc_pak(*bp++, t);
  283.             }
  284.             offset = 0;
  285.  
  286.             if (clear_flg) {    /* reset if clearing */
  287.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  288.                 clear_flg = 0;
  289.             } else {/* else use more bits */
  290.                 n_bits++;
  291.                 if (n_bits == BITS)
  292.                     maxcode = maxcodemax;
  293.                 else
  294.                     maxcode = MAXCODE(n_bits);
  295.             }
  296.         }
  297.     } else {        /* dump the buffer on EOF */
  298.         bytes_out += n = (offset + 7) / 8;
  299.  
  300.         if (offset > 0)
  301.             while (n--)
  302.                 putc_pak(*bp++, t);
  303.         offset = 0;
  304.     }
  305. }
  306.  
  307. /*****************************************************************
  308.  *
  309.  * Read one code from the standard input.  If EOF, return -1.
  310.  * Inputs:
  311.  *      cmpin
  312.  * Outputs:
  313.  *      code or -1 is returned.
  314.  */
  315.  
  316. static          int
  317. getcode(f)            /* get a code */
  318.     FILE           *f;    /* file to get from */
  319. {
  320.     int             code;
  321.     static int      offset = 0, size = 0;
  322.     int             r_off, bits;
  323.     unsigned char  *bp = (unsigned char *) buf;
  324.  
  325.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  326.         /*
  327.          * If the next entry will be too big for the current code
  328.          * size, then we must increase the size. This implies
  329.          * reading a new buffer full, too. 
  330.          */
  331.         if (free_ent > maxcode) {
  332.             n_bits++;
  333.             if (n_bits == BITS)
  334.                 maxcode = maxcodemax;    /* won't get any bigger
  335.                              * now */
  336.             else
  337.                 maxcode = MAXCODE(n_bits);
  338.         }
  339.         if (clear_flg > 0) {
  340.             maxcode = MAXCODE(n_bits = INIT_BITS);
  341.             clear_flg = 0;
  342.         }
  343.         for (size = 0; size < n_bits; size++) {
  344.             if ((code = getc_unp(f)) == EOF)
  345.                 break;
  346.             else
  347.                 buf[size] = (char) code;
  348.         }
  349.         if (size <= 0)
  350.             return -1;    /* end of file */
  351.  
  352.         offset = 0;
  353.         /* Round size down to integral number of codes */
  354.         size = (size << 3) - (n_bits - 1);
  355.     }
  356.     r_off = offset;
  357.     bits = n_bits;
  358.  
  359.     /*
  360.      * Get to the first byte. 
  361.      */
  362.     bp += (r_off >> 3);
  363.     r_off &= 7;
  364.  
  365.     /* Get first part (low order bits) */
  366.     code = (*bp++ >> r_off);
  367.     bits -= 8 - r_off;
  368.     r_off = 8 - r_off;    /* now, offset into code word */
  369.  
  370.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  371.     if (bits >= 8) {
  372.         code |= *bp++ << r_off;
  373.         r_off += 8;
  374.         bits -= 8;
  375.     }
  376.     /* high order bits. */
  377.     code |= (*bp & rmask[bits]) << r_off;
  378.     offset += n_bits;
  379.  
  380.     return code & MAXCODE(BITS);
  381. }
  382.  
  383. /*
  384.  * compress a file
  385.  * 
  386.  * Algorithm:  use open addressing double hashing (no chaining) on the prefix
  387.  * code / next character combination.  We do a variant of Knuth's algorithm D
  388.  * (vol. 3, sec. 6.4) along with G. Knott's relatively-prime secondary probe.
  389.  * Here, the modular division first probe is gives way to a faster
  390.  * exclusive-or manipulation.  Also do block compression with an adaptive
  391.  * reset, where the code table is cleared when the compression ratio
  392.  * decreases, but after the table fills.  The variable-length output codes
  393.  * are re-sized at this point, and a special CLEAR code is generated for the
  394.  * decompressor.
  395.  */
  396.  
  397. void
  398. init_cm(t)            /* initialize for compression */
  399.     FILE           *t;    /* where compressed file goes */
  400. {
  401.     offset = 0;
  402.     bytes_out = bytes_last = 1;
  403.     bytes_ref = 0;
  404.     clear_flg = 0;
  405.     in_count = 1;
  406.     checkpoint = CHECK_GAP;
  407.     maxcode = MAXCODE(n_bits = INIT_BITS);
  408.     free_ent = FIRST;
  409.     setmem(htab, HSIZE * sizeof(long), 0xff);
  410.     n_bits = INIT_BITS;    /* set starting code size */
  411.  
  412.     putc_pak(BITS, t);    /* note our max code length */
  413.  
  414.     firstcmp = 1;        /* next byte will be first */
  415. }
  416.  
  417. void
  418. putc_cm(c, t)            /* compress a character */
  419.     unsigned char   c;    /* character to compress */
  420.     FILE           *t;    /* where to put it */
  421. {
  422.     static long     fcode;
  423.     static int      hshift;
  424.     int             i;
  425.     int             disp;
  426.  
  427.     if (firstcmp) {        /* special case for first byte */
  428.         ent = c;    /* remember first byte */
  429.  
  430.         hshift = 0;
  431.         for (fcode = (long) HSIZE; fcode < 65536L; fcode *= 2L)
  432.             hshift++;
  433.         hshift = 8 - hshift;    /* set hash code range bound */
  434.  
  435.         firstcmp = 0;    /* no longer first */
  436.         return;
  437.     }
  438.     in_count++;
  439.  
  440.     fcode = (long) (((long) c << BITS) + ent);
  441.     i = (c << hshift) ^ ent;/* xor hashing */
  442.  
  443.     if (htab[i] == fcode) {
  444.         ent = codetab[i];
  445.         return;
  446.     } else if (htab[i] < 0)    /* empty slot */
  447.         goto nomatch;
  448.     disp = HSIZE - i;    /* secondary hash (after G.Knott) */
  449.     if (i == 0)
  450.         disp = 1;
  451.  
  452. probe:
  453.     if ((i -= disp) < 0)
  454.         i += HSIZE;
  455.  
  456.     if (htab[i] == fcode) {
  457.         ent = codetab[i];
  458.         return;
  459.     }
  460.     if (htab[i] > 0)
  461.         goto probe;
  462.  
  463. nomatch:
  464.     putcode(ent, t);
  465.     ent = c;
  466.     if (free_ent < maxcodemax) {
  467.         codetab[i] = free_ent++;    /* code -> hashtable */
  468.         htab[i] = fcode;
  469.     }
  470.     if (in_count >= checkpoint)
  471.         cl_block(t);    /* check for adaptive reset */
  472. }
  473.  
  474. long
  475. pred_cm(t)            /* finish compressing a file */
  476.     FILE           *t;    /* where to put it */
  477. {
  478.     putcode(ent, t);    /* put out the final code */
  479.     putcode(-1, t);        /* tell output we are done */
  480.  
  481.     return bytes_out;    /* say how big it got */
  482. }
  483.  
  484. /*
  485.  * Decompress a file.  This routine adapts to the codes in the file building
  486.  * the string table on-the-fly; requiring no table to be stored in the
  487.  * compressed file.  The tables used herein are shared with those of the
  488.  * compress() routine.  See the definitions above.
  489.  */
  490.  
  491. void
  492. decomp(f, t)            /* decompress a file */
  493.     FILE           *f;    /* file to read codes from */
  494.     FILE           *t;    /* file to write text to */
  495. {
  496.     unsigned char  *stackp;
  497.     int             finchar;
  498.     int             code, oldcode, incode;
  499.  
  500.     if ((code = getc_unp(f)) != BITS)
  501.         abort("File packed with %d bits, I can only handle %d", code, BITS);
  502.  
  503.     n_bits = INIT_BITS;    /* set starting code size */
  504.     clear_flg = 0;
  505.  
  506.     /*
  507.      * As above, initialize the first 256 entries in the table. 
  508.      */
  509.     maxcode = MAXCODE(n_bits = INIT_BITS);
  510.     setmem(prefix, 256 * sizeof(short), 0);    /* reset decode string table */
  511.     for (code = 255; code >= 0; code--)
  512.         suffix[code] = (unsigned char) code;
  513.  
  514.     free_ent = FIRST;
  515.  
  516.     finchar = oldcode = getcode(f);
  517.     if (oldcode == -1)    /* EOF already? */
  518.         return;        /* Get out of here */
  519.     putc_ncr((unsigned char) finchar, t);    /* first code must be 8 bits=char */
  520.     stackp = stack;
  521.  
  522.     while ((code = getcode(f)) > -1) {
  523.         if (code == CLEAR) {    /* reset string table */
  524.             setmem(prefix, 256 * sizeof(short), 0);
  525.             clear_flg = 1;
  526.             free_ent = FIRST - 1;
  527.             if ((code = getcode(f)) == -1)    /* O, untimely death! */
  528.                 break;
  529.         }
  530.         incode = code;
  531.         /*
  532.          * Special case for KwKwK string. 
  533.          */
  534.         if (code >= free_ent) {
  535.             if (code > free_ent) {
  536.                 if (warn) {
  537.                     printf("Corrupted compressed file.\n");
  538.                     printf("Invalid code %d when max is %d.\n",
  539.                         code, free_ent);
  540.                 }
  541.                 nerrs++;
  542.                 return;
  543.             }
  544.             *stackp++ = finchar;
  545.             code = oldcode;
  546.         }
  547.         /*
  548.          * Generate output characters in reverse order 
  549.          */
  550.         while (code >= 256) {
  551.             *stackp++ = suffix[code];
  552.             code = prefix[code];
  553.         }
  554.         *stackp++ = finchar = suffix[code];
  555.  
  556.         /*
  557.          * And put them out in forward order 
  558.          */
  559.         do
  560.             putc_ncr(*--stackp, t);
  561.         while (stackp > stack);
  562.  
  563.         /*
  564.          * Generate the new entry. 
  565.          */
  566.         if ((code = free_ent) < maxcodemax) {
  567.             prefix[code] = (unsigned short) oldcode;
  568.             suffix[code] = finchar;
  569.             free_ent = code + 1;
  570.         }
  571.         /*
  572.          * Remember previous code. 
  573.          */
  574.         oldcode = incode;
  575.     }
  576. }
  577.  
  578.  
  579. /*************************************************************************
  580.  * Please note how much trouble it can be to maintain upwards            *
  581.  * compatibility.  All that follows is for the sole purpose of unpacking *
  582.  * files which were packed using an older method.                        *
  583.  *************************************************************************/
  584.  
  585.  
  586. /*
  587.  * The h() pointer points to the routine to use for calculating a hash value.
  588.  * It is set in the init routines to point to either of oldh() or newh().
  589.  * 
  590.  * oldh() calculates a hash value by taking the middle twelve bits of the square
  591.  * of the key.
  592.  * 
  593.  * newh() works somewhat differently, and was tried because it makes ARC about
  594.  * 23% faster.  This approach was abandoned because dynamic Lempel-Zev
  595.  * (above) works as well, and packs smaller also.  However, inadvertent
  596.  * release of a developmental copy forces us to leave this in.
  597.  */
  598.  
  599. static unsigned short(*h) ();    /* pointer to hash function */
  600.  
  601. static unsigned short
  602. oldh(pred, foll)        /* old hash function */
  603.     unsigned short  pred;    /* code for preceeding string */
  604.     unsigned char   foll;    /* value of following char */
  605. {
  606.     long            local;    /* local hash value */
  607.  
  608.     local = ((pred + foll) | 0x0800) & 0xFFFF; /* create the hash key */
  609.     local *= local;        /* square it */
  610.     return (local >> 6) & 0x0FFF;    /* return the middle 12 bits */
  611. }
  612.  
  613. static unsigned short
  614. newh(pred, foll)        /* new hash function */
  615.     unsigned short  pred;    /* code for preceeding string */
  616.     unsigned char   foll;    /* value of following char */
  617. {
  618.     return (((pred + foll) & 0xFFFF) * 15073) & 0xFFF; /* faster hash */
  619. }
  620.  
  621. /*
  622.  * The eolist() function is used to trace down a list of entries with
  623.  * duplicate keys until the last duplicate is found.
  624.  */
  625.  
  626. static unsigned short
  627. eolist(index)            /* find last duplicate */
  628.     unsigned short  index;
  629. {
  630.     int             temp;
  631.  
  632.     while (temp = string_tab[index].next)    /* while more duplicates */
  633.         index = temp;
  634.  
  635.     return index;
  636. }
  637.  
  638. /*
  639.  * The hash() routine is used to find a spot in the hash table for a new
  640.  * entry.  It performs a "hash and linear probe" lookup, using h() to
  641.  * calculate the starting hash value and eolist() to perform the linear
  642.  * probe.  This routine DOES NOT detect a table full condition.  That MUST be
  643.  * checked for elsewhere.
  644.  */
  645.  
  646. static unsigned short
  647. hash(pred, foll)        /* find spot in the string table */
  648.     unsigned short  pred;    /* code for preceeding string */
  649.     unsigned char   foll;    /* char following string */
  650. {
  651.     unsigned short  local, tempnext;    /* scratch storage */
  652.     struct entry   *ep;    /* allows faster table handling */
  653.  
  654.     local = (*h) (pred, foll);    /* get initial hash value */
  655.  
  656.     if (!string_tab[local].used)    /* if that spot is free */
  657.         return local;    /* then that's all we need */
  658.  
  659.     else {            /* else a collision has occured */
  660.         local = eolist(local);    /* move to last duplicate */
  661.  
  662.         /*
  663.          * We must find an empty spot. We start looking 101 places
  664.          * down the table from the last duplicate. 
  665.          */
  666.  
  667.         tempnext = (local + 101) & 0x0FFF;
  668.         ep = &string_tab[tempnext];    /* initialize pointer */
  669.  
  670.         while (ep->used) {    /* while empty spot not found */
  671.             if (++tempnext == TABSIZE) {    /* if we are at the end */
  672.                 tempnext = 0;    /* wrap to beginning of table */
  673.                 ep = string_tab;
  674.             } else
  675.                 ++ep;    /* point to next element in table */
  676.         }
  677.  
  678.         /*
  679.          * local still has the pointer to the last duplicate, while
  680.          * tempnext has the pointer to the spot we found.  We use
  681.          * this to maintain the chain of pointers to duplicates. 
  682.          */
  683.  
  684.         string_tab[local].next = tempnext;
  685.  
  686.         return tempnext;
  687.     }
  688. }
  689.  
  690. /*
  691.  * The init_tab() routine is used to initialize our hash table. You realize,
  692.  * of course, that "initialize" is a complete misnomer.
  693.  */
  694.  
  695. static          void
  696. init_tab()
  697. {                /* set ground state in hash table */
  698.     unsigned int    i;    /* table index */
  699.  
  700.     setmem((char *) string_tab, sizeof(string_tab), 0);
  701.  
  702.     for (i = 0; i < 256; i++)    /* list all single byte strings */
  703.         upd_tab(NO_PRED, i);
  704.  
  705.     inbuf = EMPTY;        /* nothing is in our buffer */
  706. }
  707.  
  708. /*
  709.  * The upd_tab routine is used to add a new entry to the string table. As
  710.  * previously stated, no checks are made to ensure that the table has any
  711.  * room.  This must be done elsewhere.
  712.  */
  713.  
  714. void
  715. upd_tab(pred, foll)        /* add an entry to the table */
  716.     unsigned short  pred;    /* code for preceeding string */
  717.     unsigned short  foll;    /* character which follows string */
  718. {
  719.     struct entry   *ep;    /* pointer to current entry */
  720.  
  721.     /* calculate offset just once */
  722.  
  723.     ep = &string_tab[hash(pred, foll)];
  724.  
  725.     ep->used = TRUE;    /* this spot is now in use */
  726.     ep->next = 0;        /* no duplicates after this yet */
  727.     ep->predecessor = pred;    /* note code of preceeding string */
  728.     ep->follower = foll;    /* note char after string */
  729. }
  730.  
  731. /*
  732.  * This algorithm encoded a file into twelve bit strings (three nybbles). The
  733.  * gocode() routine is used to read these strings a byte (or two) at a time.
  734.  */
  735.  
  736. static          int
  737. gocode(fd)            /* read in a twelve bit code */
  738.     FILE           *fd;    /* file to get code from */
  739. {
  740.     unsigned short  localbuf, returnval;
  741.     int             temp;
  742.  
  743.     if (inbuf == EMPTY) {    /* if on a code boundary */
  744.         if ((temp = getc_unp(fd)) == EOF)    /* get start of next
  745.                              * code */
  746.             return EOF;    /* pass back end of file status */
  747.         localbuf = temp & 0xFF;    /* mask down to true byte value */
  748.         if ((temp = getc_unp(fd)) == EOF)
  749.             /* get end of code, * start of next */
  750.             return EOF;    /* this should never happen */
  751.         inbuf = temp & 0xFF;    /* mask down to true byte value */
  752.  
  753.         returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
  754.         inbuf &= 0x000F;/* leave partial code pending */
  755.     } else {        /* buffer contains first nybble */
  756.         if ((temp = getc_unp(fd)) == EOF)
  757.             return EOF;
  758.         localbuf = temp & 0xFF;
  759.  
  760.         returnval = localbuf + ((inbuf << 8) & 0xF00);
  761.         inbuf = EMPTY;    /* note no hanging nybbles */
  762.     }
  763.     return returnval;    /* pass back assembled code */
  764. }
  765.  
  766. static          void
  767. push(c)                /* push char onto stack */
  768.     int             c;    /* character to push */
  769. {
  770.     stack[sp] = ((char) c);    /* coerce integer into a char */
  771.  
  772.     if (++sp >= TABSIZE)
  773.         abort("Stack overflow\n");
  774. }
  775.  
  776. static          int
  777. pop()
  778. {                /* pop character from stack */
  779.     if (sp > 0)
  780.         return ((int) stack[--sp]);    /* leave ptr at next empty
  781.                          * slot */
  782.  
  783.     else
  784.         return EMPTY;
  785. }
  786.  
  787. /***** LEMPEL-ZEV DECOMPRESSION *****/
  788.  
  789. static int      code_count;    /* needed to detect table full */
  790. static int      firstc;        /* true only on first character */
  791.  
  792. void
  793. init_ucr(new)            /* get set for uncrunching */
  794.     int             new;    /* true to use new hash function */
  795. {
  796.     if (new)        /* set proper hash function */
  797.         h = newh;
  798.     else
  799.         h = oldh;
  800.  
  801.     sp = 0;            /* clear out the stack */
  802.     init_tab();        /* set up atomic code definitions */
  803.     code_count = TABSIZE - 256;    /* note space left in table */
  804.     firstc = 1;        /* true only on first code */
  805. }
  806.  
  807. int
  808. getc_ucr(f)            /* get next uncrunched byte */
  809.     FILE           *f;    /* file containing crunched data */
  810. {
  811.     int             code, newcode;
  812.     static int      oldcode, finchar;
  813.     struct entry   *ep;    /* allows faster table handling */
  814.  
  815.     if (firstc) {        /* first code is always known */
  816.         firstc = FALSE;    /* but next will not be first */
  817.         oldcode = gocode(f);
  818.         return finchar = string_tab[oldcode].follower;
  819.     }
  820.     if (!sp) {        /* if stack is empty */
  821.         if ((code = newcode = gocode(f)) == EOF)
  822.             return EOF;
  823.  
  824.         ep = &string_tab[code];    /* initialize pointer */
  825.  
  826.         if (!ep->used) {/* if code isn't known */
  827.             code = oldcode;
  828.             ep = &string_tab[code];    /* re-initialize pointer */
  829.             push(finchar);
  830.         }
  831.         while (ep->predecessor != NO_PRED) {
  832.             push(ep->follower);    /* decode string backwards */
  833.             code = ep->predecessor;
  834.             ep = &string_tab[code];
  835.         }
  836.  
  837.         push(finchar = ep->follower);    /* save first character also */
  838.  
  839.         /*
  840.          * The above loop will terminate, one way or another, with
  841.          * string_tab[code].follower equal to the first character in
  842.          * the string. 
  843.          */
  844.  
  845.         if (code_count) {    /* if room left in string table */
  846.             upd_tab(oldcode, finchar);
  847.             --code_count;
  848.         }
  849.         oldcode = newcode;
  850.     }
  851.     return pop();        /* return saved character */
  852. }
  853. @
  854.  
  855.  
  856. 1.5
  857. log
  858. @Clear up a few more declarations
  859. @
  860. text
  861. @d2 1
  862. a2 1
  863.  * $Header: arclzw.c,v 1.4 88/06/01 16:27:59 hyc Locked $
  864. d62 1
  865. a62 1
  866. };            /* string_tab[TABSIZE];    /* the code string table */
  867. @
  868.  
  869.  
  870. 1.4
  871. log
  872. @Missed a declaration...
  873. @
  874. text
  875. @d2 1
  876. a2 1
  877.  * $Header: arclzw.c,v 1.3 88/06/01 15:50:26 hyc Locked $
  878. d38 1
  879. d40 3
  880. d103 1
  881. a103 1
  882. static struct    entry *string_tab=htab;    /* old crunch string table */
  883. d106 1
  884. a106 1
  885. static unsigned char *suffix=htab;    /* suffix table (uncrunch) */
  886. @
  887.  
  888.  
  889. 1.3
  890. log
  891. @Merge Atari ST code
  892. @
  893. text
  894. @d2 1
  895. a2 1
  896.  * $Header: arclzw.c,v 1.2 88/06/01 14:44:34 hyc Locked $
  897. d102 1
  898. a102 1
  899. extern unsigned char suffix[HSIZE];    /* suffix table (uncrunch) */
  900. @
  901.  
  902.  
  903. 1.2
  904. log
  905. @Fixed declarations...
  906. @
  907. text
  908. @d2 1
  909. a2 1
  910.  * $Header: arclzw.c,v 1.8 88/04/19 01:39:52 hyc Exp $
  911. d58 1
  912. a58 1
  913. }               string_tab[TABSIZE];    /* the code string table */
  914. d96 2
  915. a97 5
  916. #ifdef MSDOS
  917. static long    *htab = string_tab;    /* hash code table   (crunch) */
  918. #else
  919. extern long     htab[HSIZE];
  920. #endif
  921. d99 1
  922. d101 2
  923. a102 6
  924. static unsigned short *prefix = codetab;    /* prefix code table (uncrunch) */
  925. #ifdef MSDOS
  926. static unsigned char *suffix = string_tab;    /* suffix table (uncrunch) */
  927. #else
  928. extern unsigned char suffix[HSIZE];
  929. #endif
  930. d178 2
  931. a179 1
  932. printf("%x\n", r_off);
  933. d188 2
  934. a189 1
  935.         *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  936. a202 1
  937.  
  938. d344 2
  939. a345 3
  940. init_cm(f, t)            /* initialize for compression */
  941.     FILE           *f;    /* file we will be compressing */
  942.     FILE           *t;    /* where we will put it */
  943. @
  944.  
  945.  
  946. 1.1
  947. log
  948. @Initial revision
  949. @
  950. text
  951. @d2 1
  952. a2 15
  953.  * $Log:    arclzw.c,v $
  954.  * Revision 1.2  87/12/20  03:17:39  hyc
  955.  * Fix some problems introduced by indent...
  956.  * 
  957.  * Revision 1.1  87/12/19  04:52:17  hyc
  958.  * Initial revision
  959.  * 
  960.  * Revision 1.3.1.1  87/08/13  17:03:36  hyc
  961.  * Run thru indent, fixed some signed vs. unsigned problems
  962.  * with bp <-> buf, and inbuf and localbuf...
  963.  *  Revision 1.3  87/07/21  11:41:41  hyc *** empty
  964.  * log message ***
  965.  * 
  966.  * Revision 1.2  87/07/21  08:45:24  hyc *** empty log message ***
  967.  * 
  968. d36 5
  969. d50 2
  970. a51 2
  971. static unsigned INT inbuf;    /* partial input code storage */
  972. static INT      sp;        /* current stack pointer */
  973. d53 1
  974. a53 1
  975. static struct entry {        /* string table entry format */
  976. a54 2
  977.     unsigned INT    next;    /* ptr to next in collision list */
  978.     unsigned INT    predecessor;    /* code for preceeding string */
  979. d56 2
  980. d67 2
  981. a68 2
  982. static INT      n_bits;        /* number of bits/code */
  983. static INT      maxcode;    /* maximum code, given n_bits */
  984. d70 1
  985. a70 1
  986. static INT      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  987. d83 6
  988. a88 6
  989. static INT      offset;        /* byte offset for code output */
  990. static LONG     in_count;    /* length of input */
  991. static LONG     bytes_out;    /* length of compressed output */
  992. static LONG     bytes_ref;    /* output quality reference */
  993. static LONG     bytes_last;    /* output size at last checkpoint */
  994. static unsigned INT ent;
  995. d97 1
  996. a97 1
  997. static LONG    *htab = string_tab;    /* hash code table   (crunch) */
  998. d99 1
  999. a99 1
  1000. static LONG     htab[HSIZE];
  1001. d101 1
  1002. a101 1
  1003. static unsigned INT codetab[HSIZE];    /* string code table (crunch) */
  1004. d103 1
  1005. a103 1
  1006. static unsigned INT *prefix = codetab;    /* prefix code table (uncrunch) */
  1007. d107 1
  1008. a107 1
  1009. static unsigned char suffix[HSIZE];
  1010. d110 3
  1011. a112 3
  1012. static INT      free_ent;    /* first unused entry */
  1013. static INT      firstcmp;    /* true at start of compression */
  1014. static unsigned char stack[HSIZE];    /* local push/pop stack */
  1015. d119 1
  1016. a119 1
  1017. static INT      clear_flg;
  1018. d121 2
  1019. a122 2
  1020. static LONG     checkpoint;
  1021. INT             upd_tab();
  1022. d139 1
  1023. a139 1
  1024. static          INT
  1025. a142 2
  1026.     INT             putcode();
  1027.  
  1028. d174 1
  1029. a174 1
  1030. static          INT
  1031. d176 1
  1032. a176 1
  1033.     INT             code;    /* code to output */
  1034. d179 2
  1035. a180 2
  1036.     INT             r_off = offset;    /* right offset */
  1037.     INT             bits = n_bits;    /* bits to go */
  1038. d182 1
  1039. a182 1
  1040.     INT             n;    /* index */
  1041. d184 1
  1042. d267 1
  1043. a267 1
  1044. static          INT
  1045. d271 3
  1046. a273 3
  1047.     INT             code;
  1048.     static INT      offset = 0, size = 0;
  1049.     INT             r_off, bits;
  1050. d298 1
  1051. a298 1
  1052.                 buf[size] = code;
  1053. d348 1
  1054. a348 1
  1055. INT
  1056. d361 1
  1057. a361 1
  1058.     setmem(htab, HSIZE * sizeof(LONG), 0xff);
  1059. d369 1
  1060. a369 1
  1061. INT
  1062. d374 4
  1063. a377 4
  1064.     static LONG     fcode;
  1065.     static INT      hshift;
  1066.     INT             i;
  1067.     INT             disp;
  1068. d383 1
  1069. a383 1
  1070.         for (fcode = (LONG) HSIZE; fcode < 65536L; fcode *= 2L)
  1071. d392 1
  1072. a392 1
  1073.     fcode = (LONG) (((LONG) c << BITS) + ent);
  1074. d426 1
  1075. a426 1
  1076. LONG
  1077. d443 1
  1078. a443 1
  1079. INT
  1080. d449 2
  1081. a450 2
  1082.     INT             finchar;
  1083.     INT             code, oldcode, incode;
  1084. d462 1
  1085. a462 1
  1086.     setmem(prefix, 256 * sizeof(INT), 0);    /* reset decode string table */
  1087. d471 1
  1088. a471 1
  1089.     putc_ncr((char) finchar, t);    /* first code must be 8 bits=char */
  1090. d476 1
  1091. a476 1
  1092.             setmem(prefix, 256 * sizeof(INT), 0);
  1093. d487 9
  1094. d551 1
  1095. a551 1
  1096. static unsigned INT(*h) ();    /* pointer to hash function */
  1097. d553 1
  1098. a553 1
  1099. static unsigned INT
  1100. d555 1
  1101. a555 1
  1102.     unsigned INT    pred;    /* code for preceeding string */
  1103. d558 1
  1104. a558 1
  1105.     LONG            local;    /* local hash value */
  1106. d565 1
  1107. a565 1
  1108. static unsigned INT
  1109. d567 1
  1110. a567 1
  1111.     unsigned INT    pred;    /* code for preceeding string */
  1112. d578 1
  1113. a578 1
  1114. static unsigned INT
  1115. d580 1
  1116. a580 1
  1117.     unsigned INT    index;
  1118. d582 1
  1119. a582 1
  1120.     INT             temp;
  1121. d598 1
  1122. a598 1
  1123. static unsigned INT
  1124. d600 1
  1125. a600 1
  1126.     unsigned INT    pred;    /* code for preceeding string */
  1127. d603 1
  1128. a603 1
  1129.     unsigned INT    local, tempnext;    /* scratch storage */
  1130. a642 29
  1131.  * The unhash() function is used to search the hash table for a given key.
  1132.  * Like hash(), it performs a hash and linear probe search.  It returns
  1133.  * either the number of the entry (if found) or NOT_FND (if not found).
  1134.  */
  1135.  
  1136. static unsigned INT
  1137. unhash(pred, foll)        /* search string table for a key */
  1138.     unsigned INT    pred;    /* code of preceeding string */
  1139.     unsigned char   foll;    /* character following string */
  1140. {
  1141.     unsigned INT    local, offset;    /* scratch storage */
  1142.     struct entry   *ep;    /* this speeds up access */
  1143.  
  1144.     local = (*h) (pred, foll);    /* initial hash */
  1145.  
  1146.     while (1) {
  1147.         ep = &string_tab[local];    /* speed up table access */
  1148.  
  1149.         if ((ep->predecessor == pred) && (ep->follower == foll))
  1150.             return local;    /* we have a match */
  1151.  
  1152.         if (!ep->next)    /* if no more duplicates */
  1153.             return NOT_FND;    /* then key is not listed */
  1154.  
  1155.         local = ep->next;    /* move on to next duplicate */
  1156.     }
  1157. }
  1158.  
  1159. /*
  1160. d647 1
  1161. a647 1
  1162. static          INT
  1163. d650 1
  1164. a650 1
  1165.     unsigned INT    i;    /* table index */
  1166. d666 1
  1167. a666 1
  1168. INT
  1169. d668 2
  1170. a669 2
  1171.     unsigned INT    pred;    /* code for preceeding string */
  1172.     unsigned INT    foll;    /* character which follows string */
  1173. d688 1
  1174. a688 1
  1175. static          INT
  1176. d692 2
  1177. a693 2
  1178.     unsigned INT    localbuf, returnval;
  1179.     INT             temp;
  1180. d718 1
  1181. a718 1
  1182. static          INT
  1183. d720 1
  1184. a720 1
  1185.     INT             c;    /* character to push */
  1186. d728 1
  1187. a728 1
  1188. static          INT
  1189. d741 2
  1190. a742 3
  1191. static INT      code_count;    /* needed to detect table full */
  1192. static unsigned INT code;    /* where we are so far */
  1193. static INT      firstc;        /* true only on first character */
  1194. d744 1
  1195. a744 1
  1196. INT
  1197. d746 1
  1198. a746 1
  1199.     INT             new;    /* true to use new hash function */
  1200. d759 1
  1201. a759 1
  1202. INT
  1203. d763 2
  1204. a764 3
  1205.     unsigned INT    c;    /* a character of input */
  1206.     INT             code, newcode;
  1207.     static INT      oldcode, finchar;
  1208. @
  1209.