home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / ARC521-2.ZIP / ARCSQS.C < prev    next >
C/C++ Source or Header  |  1989-12-29  |  12KB  |  483 lines
  1. /*
  2.  * $Header: arcsqs.c,v 1.3 88/07/31 18:54:14 hyc Exp $
  3.  */
  4.  
  5. /*  ARC - Archive utility - SQUASH
  6.  
  7. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  8.  
  9.  This is a quick hack to ARCLZW to make it handle squashed archives.
  10.  Dan Lanciani (ddl@harvard.*) July 87
  11.  
  12. */
  13.  
  14. /*
  15.  * $Header: arcsqs.c,v 1.3 88/07/31 18:54:14 hyc Exp $
  16.  */
  17.  
  18. #include <stdio.h>
  19. #include "arc.h"
  20.  
  21. int    getc_unp();
  22. void    putc_pak(), putc_unp();
  23. static void    putcode();
  24.  
  25. /* definitions for the new dynamic Lempel-Zev crunching */
  26.  
  27. #define BITS   13        /* maximum bits per code */
  28. #define HSIZE  10007        /* 80% occupancy */
  29. #define INIT_BITS 9        /* initial number of bits/code */
  30. static int      n_bits;        /* number of bits/code */
  31. static int      maxcode;    /* maximum code, given n_bits */
  32. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  33. static int      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  34.  
  35. static unsigned char buf[BITS];    /* input/output buffer */
  36.  
  37. static unsigned char lmask[9] =    /* left side masks */
  38. {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  39. static unsigned char rmask[9] =    /* right side masks */
  40. {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  41.  
  42. static int      offset;        /* byte offset for code output */
  43. static long     in_count;    /* length of input */
  44. static long     bytes_out;    /* length of compressed output */
  45. static unsigned short ent;
  46.  
  47. long     htab[HSIZE];    /* hash code table   (crunch) */
  48. unsigned short codetab[HSIZE];    /* string code table (crunch) */
  49.  
  50. static unsigned short *prefix = codetab;  /* prefix code table (uncrunch) */
  51. static unsigned char *suffix=(unsigned char *)htab;  /* suffix table (uncrunch) */
  52. static int      free_ent;    /* first unused entry */
  53. static int      firstcmp;    /* true at start of compression */
  54. unsigned char stack[HSIZE];    /* local push/pop stack */
  55.  
  56. /*
  57.  * block compression parameters -- after all codes are used up,
  58.  * and compression rate changes, start over.
  59.  */
  60.  
  61. static int      clear_flg;
  62. static long     ratio;
  63. #define CHECK_GAP 10000        /* ratio check interval */
  64. static long     checkpoint;
  65.  
  66. /*
  67.  * the next two codes should not be changed lightly, as they must not
  68.  * lie within the contiguous general code space.
  69.  */
  70. #define FIRST   257        /* first free entry */
  71. #define CLEAR   256        /* table clear output code */
  72.  
  73. static void
  74. cl_block(t)            /* table clear for block compress */
  75.     FILE           *t;    /* our output file */
  76. {
  77.     long            rat;
  78.     int             cnt;
  79.  
  80.     checkpoint = in_count + CHECK_GAP;
  81.  
  82.     if (in_count > 0x007fffffL) {    /* shift will overflow */
  83.         rat = bytes_out >> 8;
  84.         if (rat == 0)    /* Don't divide by zero */
  85.             rat = 0x7fffffffL;
  86.         else
  87.             rat = in_count / rat;
  88.     } else
  89.         rat = (in_count << 8) / bytes_out;    /* 8 fractional bits */
  90.  
  91.     if (rat > ratio)
  92.         ratio = rat;
  93.     else {
  94.         ratio = 0;
  95.         /* setmem(htab, HSIZE * sizeof(long), 0xff); */
  96.         for ( cnt = 0; cnt < HSIZE; cnt++ )
  97.             htab[cnt] = -1;
  98.         free_ent = FIRST;
  99.         clear_flg = 1;
  100.         putcode(CLEAR, t);
  101.     }
  102. }
  103.  
  104. /*****************************************************************
  105.  *
  106.  * Output a given code.
  107.  * Inputs:
  108.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  109.  *              that n_bits =< (long)wordsize - 1.
  110.  * Outputs:
  111.  *      Outputs code to the file.
  112.  * Assumptions:
  113.  *      Chars are 8 bits long.
  114.  * Algorithm:
  115.  *      Maintain a BITS character long buffer (so that 8 codes will
  116.  * fit in it exactly).  When the buffer fills up empty it and start over.
  117.  */
  118.  
  119. static void
  120. putcode(code, t)        /* output a code */
  121.     int             code;    /* code to output */
  122.     FILE           *t;    /* where to put it */
  123. {
  124.     int             r_off = offset;    /* right offset */
  125.     int             bits = n_bits;    /* bits to go */
  126.     unsigned char  *bp = buf;    /* buffer pointer */
  127.     int             n;    /* index */
  128.     register int    ztmp;
  129.  
  130.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  131.         bp += (r_off >> 3);
  132.         r_off &= 7;
  133.  
  134.         /*
  135.          * Since code is always >= 8 bits, only need to mask the
  136.          * first hunk on the left.
  137.          */
  138.         ztmp = (code << r_off) & lmask[r_off];
  139.         *bp = (*bp & rmask[r_off]) | ztmp;
  140.         bp++;
  141.         bits -= (8 - r_off);
  142.         code >>= (8 - r_off);
  143.  
  144.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  145.         if (bits >= 8) {
  146.             *bp++ = code;
  147.             code >>= 8;
  148.             bits -= 8;
  149.         }
  150.         /* Last bits. */
  151.         if (bits)
  152.             *bp = code;
  153.  
  154.         offset += n_bits;
  155.  
  156.         if (offset == (n_bits << 3)) {
  157.             bp = buf;
  158.             bits = n_bits;
  159.             bytes_out += bits;
  160.             do
  161.                 putc_pak(*bp++, t);
  162.             while (--bits);
  163.             offset = 0;
  164.         }
  165.         /*
  166.          * If the next entry is going to be too big for the code
  167.          * size, then increase it, if possible.
  168.          */
  169.         if (free_ent > maxcode || clear_flg > 0) {    /* Write the whole
  170.                                  * buffer, because the
  171.                                  * input side won't
  172.                                  * discover the size
  173.                                  * increase until after
  174.                                  * it has read it. */
  175.             if (offset > 0) {
  176.                 bp = buf;    /* reset pointer for writing */
  177.                 bytes_out += n = n_bits;
  178.                 while (n--)
  179.                     putc_pak(*bp++, t);
  180.             }
  181.             offset = 0;
  182.  
  183.             if (clear_flg) {    /* reset if clearing */
  184.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  185.                 clear_flg = 0;
  186.             } else {/* else use more bits */
  187.                 n_bits++;
  188.                 if (n_bits == BITS)
  189.                     maxcode = maxcodemax;
  190.                 else
  191.                     maxcode = MAXCODE(n_bits);
  192.             }
  193.         }
  194.     } else {        /* dump the buffer on EOF */
  195.         bytes_out += n = (offset + 7) / 8;
  196.  
  197.         if (offset > 0)
  198.             while (n--)
  199.                 putc_pak(*bp++, t);
  200.         offset = 0;
  201.     }
  202. }
  203.  
  204. /*****************************************************************
  205.  *
  206.  * Read one code from the standard input.  If EOF, return -1.
  207.  * Inputs:
  208.  *      cmpin
  209.  * Outputs:
  210.  *      code or -1 is returned.
  211.  */
  212.  
  213. static int
  214. getcode(f)            /* get a code */
  215.     FILE           *f;    /* file to get from */
  216. {
  217.     int             code;
  218.     static int      offset = 0, size = 0;
  219.     int             r_off, bits;
  220.     unsigned char  *bp = buf;
  221.  
  222.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  223.         /* If the next entry will be too big for the current code
  224.          * size, then we must increase the size. This implies reading
  225.          * a new buffer full, too. */
  226.         if (free_ent > maxcode) {
  227.             n_bits++;
  228.             if (n_bits == BITS)
  229.                 maxcode = maxcodemax;    /* won't get any bigger
  230.                              * now */
  231.             else
  232.                 maxcode = MAXCODE(n_bits);
  233.         }
  234.         if (clear_flg > 0) {
  235.             maxcode = MAXCODE(n_bits = INIT_BITS);
  236.             clear_flg = 0;
  237.         }
  238.         for (size = 0; size < n_bits; size++) {
  239.             if ((code = getc_unp(f)) == EOF)
  240.                 break;
  241.             else
  242.                 buf[size] = code;
  243.         }
  244.         if (size <= 0)
  245.             return -1;    /* end of file */
  246.  
  247.         offset = 0;
  248.         /* Round size down to integral number of codes */
  249.         size = (size << 3) - (n_bits - 1);
  250.     }
  251.     r_off = offset;
  252.     bits = n_bits;
  253.  
  254.     /*
  255.      * Get to the first byte.
  256.      */
  257.     bp += (r_off >> 3);
  258.     r_off &= 7;
  259.  
  260.     /* Get first part (low order bits) */
  261.     code = (*bp++ >> r_off);
  262.     bits -= 8 - r_off;
  263.     r_off = 8 - r_off;    /* now, offset into code word */
  264.  
  265.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  266.     if (bits >= 8) {
  267.         code |= *bp++ << r_off;
  268.         r_off += 8;
  269.         bits -= 8;
  270.     }
  271.     /* high order bits. */
  272.     code |= (*bp & rmask[bits]) << r_off;
  273.     offset += n_bits;
  274.  
  275.     return code;
  276. }
  277.  
  278. /*
  279.  * compress a file
  280.  *
  281.  * Algorithm:  use open addressing double hashing (no chaining) on the
  282.  * prefix code / next character combination.  We do a variant of Knuth's
  283.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  284.  * secondary probe.  Here, the modular division first probe is gives way
  285.  * to a faster exclusive-or manipulation.  Also do block compression with
  286.  * an adaptive reset, where the code table is cleared when the compression
  287.  * ratio decreases, but after the table fills.  The variable-length output
  288.  * codes are re-sized at this point, and a special CLEAR code is generated
  289.  * for the decompressor.
  290.  */
  291.  
  292. void
  293. sqinit_cm()            /* initialize for compression */
  294. {
  295.     int cnt;
  296.  
  297.     offset = 0;
  298.     bytes_out = 0;
  299.     clear_flg = 0;
  300.     ratio = 0;
  301.     in_count = 1;
  302.     checkpoint = CHECK_GAP;
  303.     maxcode = MAXCODE(n_bits = INIT_BITS);
  304.     free_ent = FIRST;
  305.     /* setmem(htab, HSIZE * sizeof(long), 0xff); */
  306.     for ( cnt = 0; cnt < HSIZE; cnt++ )
  307.         htab[cnt] = -1;
  308.     n_bits = INIT_BITS;    /* set starting code size */
  309.  
  310.     firstcmp = 1;        /* next byte will be first */
  311. }
  312.  
  313. void
  314. sqputc_cm(c, t)            /* compress a character */
  315.     unsigned char   c;    /* character to compress */
  316.     FILE           *t;    /* where to put it */
  317. {
  318.     static long     fcode;
  319.     static int      hshift;
  320.     int             i;
  321.     int             disp;
  322.  
  323.     if (firstcmp) {        /* special case for first byte */
  324.         ent = c;    /* remember first byte */
  325.  
  326.         hshift = 0;
  327.  
  328.         fcode = (long) HSIZE;
  329.         while ( fcode < 65536L )
  330.         {
  331.             hshift++;
  332.             fcode += fcode;
  333.         }
  334.  
  335. /*
  336.  * The following statement (replaced by the preceding) dumps
  337.  * if compiled by the SCO XENIX C compiler (or hangs).
  338.  *
  339.  * for (fcode = (long) HSIZE; fcode < 65536L; fcode *= 2L)
  340.  *    hshift++;
  341.  */
  342.  
  343.         hshift = 8 - hshift;    /* set hash code range bund */
  344.  
  345.         firstcmp = 0;    /* no longer first */
  346.         return;
  347.     }
  348.     in_count++;
  349.     fcode = (long) (((long) c << BITS) + ent);
  350.     i = (c << hshift) ^ ent;/* xor hashing */
  351.  
  352.     if (htab[i] == fcode) {
  353.         ent = codetab[i];
  354.         return;
  355.     } else if (htab[i] < 0)    /* empty slot */
  356.         goto nomatch;
  357.     disp = HSIZE - i;    /* secondary hash (after G.Knott) */
  358.     if (i == 0)
  359.         disp = 1;
  360.  
  361. probe:
  362.     if ((i -= disp) < 0)
  363.         i += HSIZE;
  364.  
  365.     if (htab[i] == fcode) {
  366.         ent = codetab[i];
  367.         return;
  368.     }
  369.     if (htab[i] > 0)
  370.         goto probe;
  371.  
  372. nomatch:
  373.     putcode(ent, t);
  374.     ent = c;
  375.     if (free_ent < maxcodemax) {
  376.         codetab[i] = free_ent++;    /* code -> hashtable */
  377.         htab[i] = fcode;
  378.     } else if ((long) in_count >= checkpoint)
  379.         cl_block(t);
  380. }
  381.  
  382. long
  383. sqpred_cm(t)            /* finish compressing a file */
  384.     FILE           *t;    /* where to put it */
  385. {
  386.     putcode(ent, t);    /* put out the final code */
  387.     putcode(-1, t);        /* tell output we are done */
  388.  
  389.     return bytes_out;    /* say how big it got */
  390. }
  391.  
  392. /*
  393.  * Decompress a file.  This routine adapts to the codes in the file
  394.  * building the string table on-the-fly; requiring no table to be stored
  395.  * in the compressed file.  The tables used herein are shared with those of
  396.  * the compress() routine.  See the definitions above.
  397.  */
  398.  
  399. void
  400. sqdecomp(f, t)            /* decompress a file */
  401.     FILE           *f;    /* file to read codes from */
  402.     FILE           *t;    /* file to write text to */
  403. {
  404.     unsigned char  *stackp;
  405.     int             finchar;
  406.     int             code, oldcode, incode;
  407.  
  408.     n_bits = INIT_BITS;    /* set starting code size */
  409.     clear_flg = 0;
  410.  
  411.     /*
  412.      * As above, initialize the first 256 entries in the table.
  413.      */
  414.     maxcode = MAXCODE(n_bits = INIT_BITS);
  415.     for (code = 255; code >= 0; code--) {
  416.         prefix[code] = 0;
  417.         suffix[code] = (unsigned char) code;
  418.     }
  419.     free_ent = FIRST;
  420.  
  421.     finchar = oldcode = getcode(f);
  422.     if (oldcode == -1)    /* EOF already? */
  423.         return;        /* Get out of here */
  424.     putc_unp((char) finchar, t);    /* first code must be 8 bits=char */
  425.     stackp = stack;
  426.  
  427.     while ((code = getcode(f)) > -1) {
  428.         if (code == CLEAR) {
  429.             for (code = 255; code >= 0; code--)
  430.                 prefix[code] = 0;
  431.             clear_flg = 1;
  432.             free_ent = FIRST - 1;
  433.             if ((code = getcode(f)) == -1)    /* O, untimely death! */
  434.                 break;
  435.         }
  436.         incode = code;
  437.         /*
  438.          * Special case for KwKwK string.
  439.          */
  440.         if (code >= free_ent) {
  441.             if (code > free_ent) {
  442.                 if (warn) {
  443.                     printf("Corrupted compressed file.\n");
  444.                     printf("Invalid code %d when max is %d.\n",
  445.                         code, free_ent);
  446.                 }
  447.                 nerrs++;
  448.                 return;
  449.             }
  450.             *stackp++ = finchar;
  451.             code = oldcode;
  452.         }
  453.         /*
  454.          * Generate output characters in reverse order
  455.          */
  456.         while (code >= 256) {
  457.             *stackp++ = suffix[code];
  458.             code = prefix[code];
  459.         }
  460.         *stackp++ = finchar = suffix[code];
  461.  
  462.         /*
  463.          * And put them out in forward order
  464.          */
  465.         do
  466.             putc_unp(*--stackp, t);
  467.         while (stackp > stack);
  468.  
  469.         /*
  470.          * Generate the new entry.
  471.          */
  472.         if ((code = free_ent) < maxcodemax) {
  473.             prefix[code] = (unsigned short) oldcode;
  474.             suffix[code] = finchar;
  475.             free_ent = code + 1;
  476.         }
  477.         /*
  478.          * Remember previous code.
  479.          */
  480.         oldcode = incode;
  481.     }
  482. }
  483.