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