home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / decomp.arc / DECOMP.C next >
Encoding:
C/C++ Source or Header  |  1990-01-29  |  9.6 KB  |  371 lines
  1. /*
  2.  * Compress - data compression program
  3.  */
  4. #define    min(a,b)    ((a>b) ? b : a)
  5.  
  6. # define BITS   16
  7. #define HSIZE 1L<<BITS
  8. /*
  9.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  10.  */
  11. #if BITS > 15
  12. typedef long int    code_int;
  13. #else
  14. typedef int        code_int;
  15. #endif
  16.  
  17. #ifdef SIGNED_COMPARE_SLOW
  18. typedef unsigned long int count_int;
  19. typedef unsigned short int count_short;
  20. #else
  21. typedef long int      count_int;
  22. #endif
  23.  
  24. #ifdef NO_UCHAR
  25.  typedef char    char_type;
  26. #else
  27.  typedef    unsigned char    char_type;
  28. #endif /* UCHAR */
  29. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  30.  
  31. /* Defines for third byte of header */
  32. #define BIT_MASK    0x1f
  33. #define BLOCK_MASK    0x80
  34. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  35.    a fourth header byte (for expansion).
  36. */
  37. #define INIT_BITS 9            /* initial number of bits/code */
  38.  
  39. /*
  40.  * compress.c - File compression ala IEEE Computer, June 1984.
  41.  *
  42.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  43.  *        Jim McKie        (decvax!mcvax!jim)
  44.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  45.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  46.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  47.  *        Joe Orost        (decvax!vax135!petsd!joe)
  48.  *
  49.  * modified for MS-DOS, decompression only, by B.D. Ripley, 1/90
  50.  *        b.d.ripley@uk.ac.strath.vaxa
  51.  */
  52.  
  53. #include <stdio.h>
  54. #include <ctype.h>
  55. #include <alloc.h>
  56. #include <sys/types.h>
  57. #include <sys/stat.h>
  58.  
  59. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  60.  
  61. int n_bits;                /* number of bits/code */
  62. int maxbits = BITS;            /* user settable max # bits/code */
  63. code_int maxcode;            /* maximum code, given n_bits */
  64. code_int maxmaxcode = 1L << BITS;    /* should NEVER generate this code */
  65. # define MAXCODE(n_bits)    ((1L << (n_bits)) - 1)
  66.  
  67. char_type huge *htab;
  68. unsigned short huge *codetab;
  69. count_int fsize, hsize;
  70.  
  71. #define tab_prefixof(i)    codetab[i]
  72. #define tab_suffixof(i)    htab[i]
  73.  
  74. char_type *de_stack;
  75.  
  76. code_int free_ent = 0;            /* first unused entry */
  77. int exit_stat = 0;
  78.  
  79. code_int getcode();
  80.  
  81. Usage() {
  82. fprintf(stderr,"Usage: decomp infile outfile\n");
  83. }
  84.  
  85. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  86. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  87. int quiet = 1;        /* don't tell me about compression */
  88.  
  89. /*
  90.  * block compression parameters -- after all codes are used up,
  91.  * and compression rate changes, start over.
  92.  */
  93. int block_compress = BLOCK_MASK;
  94. int clear_flg = 0;
  95. long int ratio = 0;
  96. /*
  97.  * the next two codes should not be changed lightly, as they must not
  98.  * lie within the contiguous general code space.
  99.  */
  100. #define FIRST    257    /* first free entry */
  101. #define    CLEAR    256    /* table clear output code */
  102.  
  103. char ifname[100], ofname [100];
  104.  
  105. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  106.  
  107.  
  108. /*****************************************************************
  109.  * TAG( main )
  110.  *
  111.  * Algorithm from "A Technique for High Performance Data Compression",
  112.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  113.  *
  114.  * Algorithm:
  115.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  116.  * substrings and replaces them with a variable size code.  This is
  117.  * deterministic, and can be done on the fly.  Thus, the decompression
  118.  * procedure needs no input table, but tracks the way the table was built.
  119.  */
  120.  
  121. main( argc, argv )
  122. register int argc; char **argv;
  123. {
  124.     struct stat statbuf;
  125.  
  126.  
  127.     if (argc <  3) {Usage(); exit(1);}
  128.     strcpy (ifname , argv[1]);
  129.     strcpy (ofname , argv[2]);
  130.  
  131.     if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  132.     if (maxbits > BITS) maxbits = BITS;
  133.     maxmaxcode = 1L << maxbits;
  134.  
  135.         /* Open input file */
  136.         if ((freopen(ifname, "rb", stdin)) == NULL) {
  137.             perror(ifname); exit(1);
  138.         }
  139.         stat(ifname, &statbuf);
  140.         fsize = statbuf.st_size;
  141.         /* Check the magic number */
  142.         if (nomagic == 0) {
  143.             if ((getchar() != (magic_header[0] & 0xFF))
  144.              || (getchar() != (magic_header[1] & 0xFF))) {
  145.             fprintf(stderr, "%s: not in compressed format\n",
  146.                 ifname);
  147.             exit(1);
  148.             }
  149.             maxbits = getchar();    /* set -b from file */
  150.             block_compress = maxbits & BLOCK_MASK;
  151.             maxbits &= BIT_MASK;
  152.             maxmaxcode = 1L << maxbits;
  153.             if(maxbits > BITS) {
  154.             fprintf(stderr,
  155.             "%s: compressed with %d bits, can only handle %d bits\n",
  156.             ifname, maxbits, BITS);
  157.             exit(1);
  158.             }
  159.         }
  160.         /* Check for overwrite of existing file */
  161.         if (stat(ofname, &statbuf) == 0) {
  162.             char response[2];
  163.             response[0] = 'n';
  164.             fprintf(stderr, "%s already exists;", ofname);
  165.             fprintf(stderr, " do you wish to overwrite %s (y or n)? ",
  166.             ofname);
  167.             fflush(stderr);
  168.             read(2, response, 2);
  169.             while (response[1] != '\n') {
  170.                 if (read(2, response+1, 1) < 0) {    /* Ack! */
  171.                 perror("stderr"); break;
  172.                 }
  173.             }
  174.             if (response[0] != 'y') {
  175.             fprintf(stderr, "\tnot overwritten\n");
  176.             exit(1);
  177.             }
  178.         }
  179.         if (freopen(ofname, "wb", stdout) == NULL) {
  180.             perror(ofname);
  181.             exit(1);
  182.         }
  183.  
  184.     hsize = min(HSIZE, fsize); /* cannot have more codes than file size */
  185.     htab = (char_type huge*)farcalloc(hsize, sizeof(char_type));
  186.     if (htab == NULL) {
  187.     fprintf(stderr,"Not enough memory\n");
  188.     fprintf(stderr,"Far heap size %lu hsize %u\n",farcoreleft(), hsize);
  189.     exit(1);
  190.     }
  191.     codetab = (unsigned short huge*)farcalloc(hsize, sizeof(unsigned short));
  192.     if(codetab == NULL) {
  193.     fprintf(stderr, "Not enough memory\n");
  194.     fprintf(stderr,"Far heap size %lu hsize %u\n",farcoreleft(), hsize);
  195.     exit(1);
  196.     }
  197.     de_stack = (char_type *)malloc(8000);
  198.  
  199.     decompress();
  200.     exit(0);
  201. }
  202.  
  203.  
  204. /*
  205.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  206.  * file building the "string" table on-the-fly; requiring no table to
  207.  * be stored in the compressed file.  The tables used herein are shared
  208.  * with those of the compress() routine.  See the definitions above.
  209.  */
  210.  
  211. decompress() {
  212.     register char_type *stackp;
  213.     register code_int finchar;
  214.     register code_int code, oldcode, incode;
  215.  
  216.     /*
  217.      * As above, initialize the first 256 entries in the table.
  218.      */
  219.     maxcode = MAXCODE(n_bits = INIT_BITS);
  220.     for ( code = 255; code >= 0; code-- ) {
  221.     tab_prefixof(code) = 0;
  222.     tab_suffixof(code) = (char_type)code;
  223.     }
  224.     free_ent = ((block_compress) ? FIRST : 256 );
  225.  
  226.     finchar = oldcode = getcode();
  227.     if(oldcode == -1)    /* EOF already? */
  228.     return;            /* Get out of here */
  229.     putchar( (char)finchar );        /* first code must be 8 bits = char */
  230.     if(ferror(stdout))        /* Crash if can't write */
  231.     writeerr();
  232.     stackp = de_stack;
  233.  
  234.     while ( (code = getcode()) > -1 ) {
  235.  
  236.     if ( (code == CLEAR) && block_compress ) {
  237.         for ( code = 255; code >= 0; code-- )
  238.         tab_prefixof(code) = 0;
  239.         clear_flg = 1;
  240.         free_ent = FIRST - 1;
  241.         if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  242.         break;
  243.     }
  244.     incode = code;
  245.     /*
  246.      * Special case for KwKwK string.
  247.      */
  248.     if ( code >= free_ent ) {
  249.             *stackp++ = finchar;
  250.         code = oldcode;
  251.     }
  252.  
  253.     /*
  254.      * Generate output characters in reverse order
  255.      */
  256. #ifdef SIGNED_COMPARE_SLOW
  257.     while ( ((unsigned long)code) >= ((unsigned long)256) ) {
  258. #else
  259.     while ( code >= 256 ) {
  260. #endif
  261.         *stackp++ = tab_suffixof(code);
  262.         code = tab_prefixof(code);
  263.     }
  264.     *stackp++ = finchar = tab_suffixof(code);
  265.  
  266.     /*
  267.      * And put them out in forward order
  268.      */
  269.     do
  270.         putchar ( *--stackp );
  271.     while ( stackp > de_stack );
  272.  
  273.     /*
  274.      * Generate the new entry.
  275.      */
  276.     if ( (code=free_ent) < maxmaxcode ) {
  277.         tab_prefixof(code) = (unsigned short)oldcode;
  278.         tab_suffixof(code) = finchar;
  279.         free_ent = code+1;
  280.     }
  281.     /*
  282.      * Remember previous code.
  283.      */
  284.     oldcode = incode;
  285.     }
  286.     fflush( stdout );
  287.     if(ferror(stdout))
  288.     writeerr();
  289. }
  290.  
  291. /*****************************************************************
  292.  * TAG( getcode )
  293.  *
  294.  * Read one code from the standard input.  If EOF, return -1.
  295.  * Inputs:
  296.  *     stdin
  297.  * Outputs:
  298.  *     code or -1 is returned.
  299.  */
  300.  
  301. code_int
  302. getcode() {
  303.     register code_int code;
  304.     static long int offset = 0, size = 0;
  305.     static char_type buf[BITS];
  306.     register int r_off, bits;
  307.     register char_type *bp = buf;
  308.  
  309.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  310.     /*
  311.      * If the next entry will be too big for the current code
  312.      * size, then we must increase the size.  This implies reading
  313.      * a new buffer full, too.
  314.      */
  315.     if ( free_ent > maxcode ) {
  316.         n_bits++;
  317.         if ( n_bits == maxbits )
  318.         maxcode = maxmaxcode;    /* won't get any bigger now */
  319.         else
  320.         maxcode = MAXCODE(n_bits);
  321.     }
  322.     if ( clear_flg > 0) {
  323.             maxcode = MAXCODE (n_bits = INIT_BITS);
  324.         clear_flg = 0;
  325.     }
  326.     size = fread( buf, 1, n_bits, stdin );
  327.     if ( size <= 0 )
  328.         return -1;            /* end of file */
  329.     offset = 0;
  330.     /* Round size down to integral number of codes */
  331.     size = (size << 3) - (n_bits - 1);
  332.     }
  333.     r_off = offset;
  334.     bits = n_bits;
  335.     /*
  336.      * Get to the first byte.
  337.      */
  338.     bp += (r_off >> 3);
  339.     r_off &= 7;
  340.     /* Get first part (low order bits) */
  341. #ifdef NO_UCHAR
  342.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  343. #else
  344.     code = (*bp++ >> r_off);
  345. #endif /* NO_UCHAR */
  346.     bits -= (8 - r_off);
  347.     r_off = 8 - r_off;        /* now, offset into code word */
  348.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  349.     if ( bits >= 8 ) {
  350. #ifdef NO_UCHAR
  351.         code |= (*bp++ & 0xff) << r_off;
  352. #else
  353.         code |= *bp++ << r_off;
  354. #endif /* NO_UCHAR */
  355.         r_off += 8;
  356.         bits -= 8;
  357.     }
  358.     /* high order bits. */
  359.     code |= (*bp & rmask[bits]) << r_off;
  360.     offset += n_bits;
  361.  
  362.     return code;
  363. }
  364.  
  365. writeerr()
  366. {
  367.     perror ( ofname );
  368.     unlink ( ofname );
  369.     exit ( 1 );
  370. }
  371.