home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Programmierung / SOURCE.mdf / programm / msdos / c / xv221src / unsupt / vms / decompre.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-26  |  8.1 KB  |  341 lines
  1. /* 
  2.  *  D e c o m p r e s s   
  3.  *
  4.  *  Data decompression program for LZW compression
  5.  *
  6.  */
  7.  
  8. /* Get the usual include files */
  9.  
  10. #include <stdio.h>
  11. #include <ctype.h>
  12. #include <types.h>
  13. #include <stat.h>
  14.  
  15. /* Define some useful constants */
  16.  
  17. #define BITS          16
  18. #define HSIZE      69001            /* 95% occupancy */
  19. #define BIT_MASK    0x1F
  20. #define INIT_BITS      9            /* initial number of bits/code */
  21. #define BLOCK_MASK  0x80
  22. #define FIRST        257            /* first free entry */
  23. #define CLEAR        256            /* table clear output code */
  24. #ifndef VMS
  25. #define GOOD_EXIT      0
  26. #define BAD_EXIT       1
  27. #else
  28. #define GOOD_EXIT      1
  29. #define BAD_EXIT       0
  30. #endif
  31.  
  32. /* Define some useful macros */
  33.  
  34. #define MAXCODE(n_bits)     ((1 << (n_bits)) - 1)
  35. #define htabof(i)           htab[i]
  36. #define codetabof(i)        codetab[i]
  37. #define tab_prefixof(i)     codetabof (i)
  38. #define tab_suffixof(i)     ((char_type *) (htab))[i]
  39. #define de_stack            ((char_type *) &tab_suffixof (1 << BITS))
  40.  
  41. /* Set up our typedefs */
  42.  
  43. typedef long int code_int;
  44. typedef long int count_int;
  45. typedef unsigned char char_type;
  46.  
  47. /* Declare the global variables */
  48.  
  49. char_type magic_header[] = {"\037\235"};        /* 1F 9D */
  50. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF};
  51.  
  52. int n_bits;                             /* number of bits/code */
  53. int maxbits = BITS;                     /* user settable max # bits/code */
  54. code_int maxcode;                       /* maximum code, given n_bits */
  55. code_int maxmaxcode = 1 << BITS;        /* should NEVER generate this code */
  56.  
  57. count_int htab [HSIZE];
  58. unsigned short codetab [HSIZE];
  59.  
  60. code_int free_ent = 0;                  /* first unused entry */
  61.  
  62. /* Define our function prototypes */
  63.  
  64. code_int getcode ( );
  65.  
  66. /*
  67.  *  Block compression parameters -- after all codes are used up,
  68.  *  and compression rate changes, start over.
  69.  *
  70.  */
  71.  
  72. int block_compress = BLOCK_MASK;
  73. int clear_flg = 0;
  74. char ofname [100];
  75.  
  76. /*
  77.  *  m a i n
  78.  *
  79.  *  Algorithm from "A Technique for High Performance Data Compression",
  80.  *  Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  81.  *
  82.  *  Algorithm:
  83.  *
  84.  *      Modified Lempel-Ziv method (LZW).  Basically finds common
  85.  *  substrings and replaces them with a variable size code.  This is
  86.  *  deterministic, and can be done on the fly.  Thus, the decompression
  87.  *  procedure needs no input table, but tracks the way the table was built.
  88.  *
  89.  */
  90.  
  91. int main (argc, argv)
  92.  
  93. int argc; 
  94. char *argv[];
  95.  
  96. {
  97.     char tempname[100];
  98.     char *fileptr;
  99.  
  100.     if (argc != 2) {
  101.         printf ("Usage: decompress filename.\n");
  102.         exit (BAD_EXIT);
  103.     }
  104.  
  105.     /* Get input file (no extension) */
  106.  
  107.     fileptr = argv[1];     
  108.  
  109.     /* Add .Z suffix */
  110.  
  111.     strcpy (tempname, fileptr);
  112.     strcat (tempname, ".Z");
  113.     fileptr = tempname;
  114.                 
  115.     /* Open input file */
  116.  
  117.     if ((freopen (fileptr, "r", stdin)) == NULL) {
  118.         perror (fileptr);
  119.         exit (BAD_EXIT);
  120.     }
  121.  
  122.     /* Check the magic number */
  123.  
  124.     if ((getchar ( ) != (magic_header[0] & 0xFF)) ||
  125.         (getchar ( ) != (magic_header[1] & 0xFF))) {
  126.         fprintf (stderr, "%s: not in compressed format\n", fileptr);
  127.         exit (BAD_EXIT);
  128.     }
  129.  
  130.     maxbits = getchar ( );        /* set bits from file */
  131.     block_compress = maxbits & BLOCK_MASK;
  132.     maxbits &= BIT_MASK;
  133.     maxmaxcode = 1 << maxbits;
  134.  
  135.     if (maxbits > BITS) {
  136.         fprintf (stderr, "%s: compressed with %d bits, can only handle %d bits\n",
  137.           fileptr, maxbits, BITS);
  138.         exit (BAD_EXIT);
  139.     }
  140.  
  141.     /* Generate output filename */
  142.  
  143.     strcpy (ofname, fileptr);
  144.     ofname[strlen (fileptr) - 2] = '\0';  /* Strip off .Z */
  145.     
  146.     /* Open output file */
  147.  
  148.     if (freopen (ofname, "w", stdout) == NULL) {
  149.         perror (ofname);
  150.         exit (BAD_EXIT);
  151.     }
  152.  
  153.     /* Actually do the decompression */
  154.  
  155.     decompress ( );
  156.  
  157.     fclose (stdout);
  158.     exit (GOOD_EXIT);
  159. }
  160.  
  161. writeerr ( )
  162. {
  163.     perror (ofname);
  164.     exit (BAD_EXIT);
  165. }
  166.  
  167. /*
  168.  *  d e c o m p r e s s
  169.  *
  170.  *  Decompress stdin to stdout.  This routine adapts to the codes in the
  171.  *  file building the "string" table on-the-fly; requiring no table to
  172.  *  be stored in the compressed file.  
  173.  *
  174.  */
  175.  
  176. decompress ( ) 
  177. {
  178.     register char_type *stackp;
  179.     register int finchar;
  180.     register code_int code, oldcode, incode;
  181.  
  182.     /* Initialize the first 256 entries in the table */
  183.  
  184.     maxcode = MAXCODE (n_bits = INIT_BITS);
  185.  
  186.     for (code = 255; code >= 0; code--) {
  187.         tab_prefixof (code) = 0;
  188.         tab_suffixof (code) = (char_type) code;
  189.     }
  190.  
  191.     free_ent = ((block_compress) ? FIRST : 256);
  192.  
  193.     finchar = oldcode = getcode ( );
  194.  
  195.     if (oldcode == -1)                  /* EOF already? */
  196.         return;                         /* Get out of here */
  197.  
  198.     putchar ((char) finchar);           /* first code must be 8 bits = char */
  199.  
  200.     if (ferror (stdout))                /* Crash if can't write */
  201.         writeerr ( );
  202.  
  203.     stackp = de_stack;
  204.  
  205.     while ((code = getcode ( )) > -1) {
  206.  
  207.         if ((code == CLEAR) && block_compress) {
  208.  
  209.             for (code = 255; code >= 0; code--)
  210.                 tab_prefixof (code) = 0;
  211.  
  212.             clear_flg = 1;
  213.             free_ent = FIRST - 1;
  214.  
  215.             if ((code = getcode ( )) == -1)     /* O, untimely death! */
  216.                 break;
  217.         }
  218.  
  219.         incode = code;
  220.  
  221.         /* Special case for KwKwK string */
  222.  
  223.         if (code >= free_ent) {
  224.             *stackp++ = finchar;
  225.             code = oldcode;
  226.         }
  227.  
  228.         /* Generate output characters in reverse order */
  229.  
  230.         while (code >= 256) {
  231.             *stackp++ = tab_suffixof (code);
  232.             code = tab_prefixof (code);
  233.         }
  234.  
  235.         *stackp++ = finchar = tab_suffixof (code);
  236.  
  237.         /* And put them out in forward order */
  238.  
  239.         do {
  240.             putchar (*--stackp);
  241.         } while (stackp > de_stack);
  242.  
  243.         /* Generate the new entry */
  244.  
  245.         if ((code = free_ent) < maxmaxcode) {
  246.             tab_prefixof (code) = (unsigned short) oldcode;
  247.             tab_suffixof (code) = finchar;
  248.             free_ent = code + 1;
  249.         } 
  250.  
  251.         /* Remember previous code */
  252.  
  253.         oldcode = incode;
  254.     }
  255.  
  256.     fflush (stdout);
  257.  
  258.     if (ferror (stdout))
  259.         writeerr ( );
  260. }
  261.  
  262. /*
  263.  *  g e t c o d e
  264.  *
  265.  *  Read one code from the standard input.  If EOF, return -1.
  266.  *
  267.  */
  268.  
  269. code_int getcode ( ) 
  270. {
  271.     register code_int code;
  272.     static int offset = 0, size = 0;
  273.     static char_type buf[BITS];
  274.     register int r_off, bits;
  275.     register char_type *bp = buf;
  276.  
  277.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  278.  
  279.         /*
  280.          * If the next entry will be too big for the current code
  281.          * size, then we must increase the size.  This implies reading
  282.          * a new buffer full, too.
  283.          *
  284.          */
  285.  
  286.         if (free_ent > maxcode) {
  287.             n_bits++;
  288.  
  289.             if (n_bits == maxbits)
  290.                 maxcode = maxmaxcode;   /* Won't get any bigger now */
  291.             else
  292.                 maxcode = MAXCODE (n_bits);
  293.         }
  294.  
  295.         if (clear_flg > 0) {
  296.             maxcode = MAXCODE (n_bits = INIT_BITS);
  297.             clear_flg = 0;
  298.         }
  299.  
  300.         size = fread (buf, 1, n_bits, stdin);
  301.  
  302.         if (size <= 0)
  303.             return (-1);                /* End of file */
  304.  
  305.         offset = 0;
  306.  
  307.         /* Round size down to an integral number of codes */
  308.  
  309.         size = (size << 3) - (n_bits - 1);
  310.     }
  311.  
  312.     r_off = offset;
  313.     bits = n_bits;
  314.  
  315.     /* Get to the first byte */
  316.  
  317.     bp += (r_off >> 3);
  318.     r_off &= 7;
  319.  
  320.     /* Get first part (low order bits) */
  321.  
  322.     code = (*bp++ >> r_off);
  323.     bits -= (8 - r_off);
  324.     r_off = 8 - r_off;                  /* Now, offset into code word */
  325.  
  326.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits) */
  327.  
  328.     if (bits >= 8) {
  329.         code |= *bp++ << r_off;
  330.         r_off += 8;
  331.         bits -= 8;
  332.     }
  333.  
  334.     /* Handle the high order bits */
  335.  
  336.     code |= (*bp & rmask[bits]) << r_off;
  337.     offset += n_bits;
  338.  
  339.     return (code);
  340. }
  341.