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