home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 2 / RISC_DISC_2.iso / pd_share / utilities / cli / nspark / compress_c < prev    next >
Encoding:
Text File  |  1995-01-06  |  7.1 KB  |  307 lines
  1. /*
  2.  * compress/uncompress archive
  3.  *
  4.  * Authors:    Spencer W. Thomas    (decvax!utah-cs!thomas)
  5.  *        Jim McKie        (decvax!mcvax!jim)
  6.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  7.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  8.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  9.  *        Joe Orost        (decvax!vax135!petsd!joe)
  10.  *
  11.  * NOTE: these functions also support "squash" (which is just a
  12.  * 13-bit compress), and "crunch" (which is a 12-bit compress
  13.  * with additional run-length encoding).  AJD
  14.  *
  15.  * $Header: compress.c 1.9 95/01/06 $
  16.  * $Log:    compress.c,v $
  17.  * Revision 1.9  95/01/06  12:00:06  arb
  18.  * Fixes for Alpha.
  19.  *
  20.  * Revision 1.8  94/02/28  23:57:55  arb
  21.  * Fixed number of compression bits for ArcFS format archives
  22.  *
  23.  * Revision 1.7  93/08/20  11:35:20  arb
  24.  * Prevent printing of "uncompressed" etc. if quiet flag is set
  25.  *
  26.  * Revision 1.6  92/12/07  17:17:28  duplain
  27.  * reformatted source.
  28.  * 
  29.  * Revision 1.5  92/11/09  14:48:00  duplain
  30.  * Initialised offset and size from getcode() each time uncompress() called.
  31.  * 
  32.  * Revision 1.4  92/11/02  11:43:14  duplain
  33.  * Correct comment about crunch/squash in header.
  34.  * 
  35.  * Revision 1.3  92/10/23  14:08:13  duplain
  36.  * Minor changes to printf's at end of uncompress.
  37.  * 
  38.  * Revision 1.2  92/10/01  11:20:19  duplain
  39.  * Added check for EOF.
  40.  * 
  41.  * Revision 1.1  92/09/29  18:02:14  duplain
  42.  * Initial revision
  43.  * 
  44.  */
  45.  
  46. #include <stdio.h>
  47. #include "spark.h"
  48. #include "pack.h"
  49. #include "main.h"
  50. #include "crc.h"
  51. #include "io.h"
  52. #include "arcfs.h"
  53.  
  54. #ifdef UNIX
  55. static char rcsid[] = "$Header: compress.c 1.9 95/01/06 $";
  56. #endif /* UNIX */
  57.  
  58. #define PBITS 16
  59. #define CRUNCHBITS 12
  60. #define SQUASHBITS 13
  61. #define COMPRESSBITS 16
  62. #define HSIZE 65536
  63. #define INIT_BITS 9        /* initial number of bits/code */
  64. #define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  65. #define htabof(i) htab[i]
  66. #define codetabof(i) codetab[i]
  67. #define tab_prefixof(i)    codetabof(i)
  68. #define tab_suffixof(i)    ((char_type *)(htab))[i]
  69. #define de_stack ((char_type *)&tab_suffixof(1<<COMPRESSBITS))
  70. #define FIRST 257        /* first free entry */
  71. #define    CLEAR 256        /* table clear output code */
  72.  
  73. typedef Word code_int;
  74. typedef Word count_int;
  75. typedef unsigned char char_type;
  76.  
  77. static int n_bits;        /* number of bits/code */
  78. static int maxbits;        /* user settable max # bits/code */
  79. static code_int maxcode;    /* maximum code, given n_bits */
  80. static code_int maxmaxcode;    /* should NEVER generate this code */
  81. static count_int htab[HSIZE];
  82. static unsigned short codetab[HSIZE];
  83. static char_type rmask[9] ={0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  84. static code_int free_ent;    /* first unused entry */
  85. static int clear_flg;
  86. static long readsize;        /* number of bytes left to read */
  87. static int offset, size;    /* from getcode() */
  88.  
  89. static code_int getcode P__((FILE *ifp));
  90.  
  91. Status
  92. uncompress(header, ifp, ofp, type)
  93.     Header *header;
  94.     FILE *ifp, *ofp;
  95.     CompType type;
  96. {
  97.     register char_type *stackp;
  98.     register int finchar;
  99.     register code_int code, oldcode, incode;
  100.     char *message;
  101.  
  102.     crc = 0;
  103.     clear_flg = 0;
  104.     offset = 0;
  105.     size = 0;
  106.     readsize = header->complen;
  107.  
  108.     if (type == SQUASH)
  109.     maxbits = SQUASHBITS;
  110.     else {
  111.     if (arcfs)
  112.         maxbits = arcfs_maxbits;
  113.     else
  114.     {
  115.         maxbits = read_byte(ifp);
  116.         readsize--;
  117.     }
  118.     }
  119.     maxmaxcode = 1 << maxbits;
  120.  
  121.     /*
  122.      * As above, initialize the first 256 entries in the table.
  123.      */
  124.     maxcode = MAXCODE(n_bits = INIT_BITS);
  125.     for (code = 255; code >= 0; code--) {
  126.     tab_prefixof(code) = 0;
  127.     tab_suffixof(code) = (char_type) code;
  128.     }
  129.     free_ent = FIRST;
  130.  
  131.     finchar = oldcode = getcode(ifp);
  132.     if (oldcode == -1)    /* EOF already? */
  133.     goto compress_exit;    /* Get out of here */
  134.  
  135.     /* first code must be 8 bits = char */
  136.     if (type == CRUNCH) {
  137.     putc_init();
  138.     putc_ncr(ofp, finchar);
  139.     } else {
  140.     if (!testing)
  141.         write_byte(ofp, finchar);
  142.     calccrc(finchar);
  143.     }
  144.  
  145.     stackp = de_stack;
  146.  
  147.     while ((code = getcode(ifp)) != -1) {
  148.     if (check_stream(ifp) != FNOERR)
  149.         break;
  150.     if (code == CLEAR) {
  151.         for (code = 255; code >= 0; code--)
  152.         tab_prefixof(code) = 0;
  153.         clear_flg = 1;
  154.         free_ent = FIRST - 1;
  155.         if ((code = getcode(ifp)) == -1)    /* O, untimely death! */
  156.         break;
  157.     }
  158.     incode = code;
  159.     /*
  160.      * Special case for KwKwK string.
  161.      */
  162.     if (code >= free_ent) {
  163.         *stackp++ = finchar;
  164.         code = oldcode;
  165.     }
  166.     /*
  167.      * Generate output characters in reverse order
  168.      */
  169.  
  170.     while (code >= 256) {
  171.         *stackp++ = tab_suffixof(code);
  172.         code = tab_prefixof(code);
  173.     }
  174.     *stackp++ = finchar = tab_suffixof(code);
  175.     
  176.     /*
  177.      * And put them out in forward order
  178.      */
  179.     while (stackp > de_stack) {
  180.         stackp--;
  181.         if (type == CRUNCH)
  182.         putc_ncr(ofp, *stackp);
  183.         else {
  184.         if (!testing)
  185.             write_byte(ofp, *stackp);
  186.         calccrc(*stackp);
  187.         }
  188.     }
  189.  
  190.     /*
  191.      * Generate the new entry.
  192.      */
  193.     if ((code = free_ent) < maxmaxcode) {
  194.         tab_prefixof(code) = oldcode;
  195.         tab_suffixof(code) = finchar;
  196.         free_ent = code + 1;
  197.     }
  198.     /*
  199.      * Remember previous code.
  200.      */
  201.     oldcode = incode;
  202.     }
  203. compress_exit:
  204.     if (check_stream(ifp) == FRWERR)
  205.     return (RERR);
  206.     if (!testing && check_stream(ofp) == FRWERR)
  207.     return (WERR);
  208.     if ((Halfword)crc != header->crc)
  209.     return (CRCERR);
  210.     if (testing)
  211.     switch(type) {
  212.     case COMPRESS:
  213.         message = "OK (compressed)";
  214.         break;
  215.     case CRUNCH:
  216.         message = "OK (crunched)";
  217.         break;
  218.     case SQUASH:
  219.         message = "OK (squashed)";
  220.         break;
  221.     default:
  222.         message = "internal error";
  223.         break;
  224.     }
  225.     else
  226.     switch(type) {
  227.     case COMPRESS:
  228.         message = "uncompressed";
  229.         break;
  230.     case CRUNCH:
  231.         message = "uncrunched";
  232.         break;
  233.     case SQUASH:
  234.         message = "unsquashed";
  235.         break;
  236.     default:
  237.         message = "internal error";
  238.         break;
  239.     }
  240.     if (!quiet) printf(message);
  241.     return (NOERR);
  242. }
  243.  
  244. /*
  245.  * Read one code from the input.  If EOF, return -1.
  246.  */
  247. static code_int
  248. getcode(ifp)
  249.     FILE *ifp;
  250. {
  251.     register code_int code;
  252.     static char_type buf[COMPRESSBITS];
  253.     register int r_off, bits;
  254.     register char_type *bp = buf;
  255.  
  256.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  257.     /*
  258.      * If the next entry will be too big for the current code
  259.      * size, then we must increase the size.  This implies
  260.      * reading a new buffer full, too.
  261.      */
  262.     if (free_ent > maxcode) {
  263.         n_bits++;
  264.         maxcode = n_bits == maxbits ? maxmaxcode :
  265.         MAXCODE(n_bits);
  266.     }
  267.     if (clear_flg > 0) {
  268.         maxcode = MAXCODE(n_bits = INIT_BITS);
  269.         clear_flg = 0;
  270.     }
  271.     if (readsize == 0)
  272.         return (-1);
  273.     size = readsize < n_bits ? readsize : n_bits;
  274.     size = fread(buf, 1, size, ifp);
  275.     if (size <= 0)
  276.         return (-1);    /* end of file */
  277.     readsize -= size;
  278.     offset = 0;
  279.     /* Round size down to integral number of codes */
  280.     size = (size << 3) - (n_bits - 1);
  281.     }
  282.     r_off = offset;
  283.     bits = n_bits;
  284.  
  285.     /*
  286.      * Get to the first byte.
  287.      */
  288.     bp += (r_off >> 3);
  289.     r_off &= 7;
  290.     /* Get first part (low order bits) */
  291.  
  292.     code = (*bp++ >> r_off);
  293.     bits -= (8 - r_off);
  294.     r_off = 8 - r_off;    /* now, offset into code word */
  295.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  296.     if (bits >= 8) {
  297.     code |= *bp++ << r_off;
  298.     r_off += 8;
  299.     bits -= 8;
  300.     }
  301.     /* high order bits. */
  302.     code |= (*bp & rmask[bits]) << r_off;
  303.     offset += n_bits;
  304.  
  305.     return (code);
  306. }
  307.