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