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