home *** CD-ROM | disk | FTP | other *** search
/ Chip 2002 June / Chip_2002-06_cd1.bin / zkuste / wincom / download / uncompress.1.0.ME-src.cab / uncompress-src / DECOMP.C next >
Encoding:
C/C++ Source or Header  |  2001-08-23  |  10.8 KB  |  417 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.  * modified for Win32, decompression only by Siarhei Zharski 08/2000
  52.  *      imker@gmx.li
  53.  */
  54.  
  55. #include <stdio.h>
  56. #include <stdlib.h>
  57. #include <string.h>
  58. #include <ctype.h>
  59. #include <io.h>
  60. #include <time.h>
  61. //#include <alloc.h>
  62. #include <sys/types.h>
  63. #include <sys/stat.h>
  64.  
  65. #define huge 
  66.  
  67. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  68.  
  69. int n_bits;                /* number of bits/code */
  70. int maxbits = BITS;            /* user settable max # bits/code */
  71. code_int maxcode;            /* maximum code, given n_bits */
  72. code_int maxmaxcode = 1L << BITS;    /* should NEVER generate this code */
  73. # define MAXCODE(n_bits)    ((1L << (n_bits)) - 1)
  74.  
  75. char_type huge *htab;
  76. unsigned short huge *codetab;
  77. count_int fsize, hsize;
  78.  
  79. #define tab_prefixof(i)    codetab[i]
  80. #define tab_suffixof(i)    htab[i]
  81.  
  82. char_type *de_stack;
  83.  
  84. code_int free_ent = 0;            /* first unused entry */
  85. int exit_stat = 0;
  86.  
  87. code_int getcode();
  88.  
  89. Usage() {
  90. fprintf(stderr,"Usage: decomp [l] infile\n");
  91. return 0;
  92. }
  93.  
  94. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  95. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  96. int quiet = 1;        /* don't tell me about compression */
  97.  
  98. /*
  99.  * block compression parameters -- after all codes are used up,
  100.  * and compression rate changes, start over.
  101.  */
  102. int block_compress = BLOCK_MASK;
  103. int clear_flg = 0;
  104. long int ratio = 0;
  105. /*
  106.  * the next two codes should not be changed lightly, as they must not
  107.  * lie within the contiguous general code space.
  108.  */
  109. #define FIRST    257    /* first free entry */
  110. #define    CLEAR    256    /* table clear output code */
  111.  
  112. char ifname[100], ofname [100];
  113.  
  114. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  115.  
  116.  
  117. /*****************************************************************
  118.  * TAG( main )
  119.  *
  120.  * Algorithm from "A Technique for High Performance Data Compression",
  121.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  122.  *
  123.  * Algorithm:
  124.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  125.  * substrings and replaces them with a variable size code.  This is
  126.  * deterministic, and can be done on the fly.  Thus, the decompression
  127.  * procedure needs no input table, but tracks the way the table was built.
  128.  */
  129.  
  130. main( argc, argv )
  131. register int argc; char **argv;
  132. {
  133.     struct stat statbuf;
  134.     int nListAsked=0;
  135.  
  136.     printf("UNIX-style decompressor, modified by Siarhei Zharski version 1.0 08/2000\n");
  137.  
  138.     if (argc <  2) {Usage(); exit(1);}
  139.  
  140.     nListAsked = (argv[1][0] == 'l');
  141.  
  142.     if(!nListAsked)
  143.     {
  144.         strcpy (ifname , argv[1]);
  145.         //strcpy (ofname , argv[2]);
  146.     }
  147.     else
  148.     {
  149.         strcpy (ifname , argv[2]);
  150.         //strcpy (ofname , argv[3]);
  151.     }
  152.  
  153.     _splitpath(ifname,0,0,ofname,0);
  154.  
  155.     if(maxbits < INIT_BITS) maxbits = INIT_BITS;
  156.     if (maxbits > BITS) maxbits = BITS;
  157.     maxmaxcode = 1L << maxbits;
  158.  
  159.         /* Open input file */
  160.         if ((freopen(ifname, "rb", stdin)) == NULL) {
  161.             perror(ifname); exit(1);
  162.         }
  163.         stat(ifname, &statbuf);
  164.         fsize = statbuf.st_size;
  165.         /* Another Turbo C bug -- can return wrong file sizes*/
  166.         if (fsize < 0) fsize = 1000000;
  167.         /* Check the magic number */
  168.         if (nomagic == 0) {
  169.             if ((getchar() != (magic_header[0] & 0xFF))
  170.              || (getchar() != (magic_header[1] & 0xFF))) {
  171.             fprintf(stderr, "%s: not in compressed format\n",
  172.                 ifname);
  173.             exit(1);
  174.             }
  175.             maxbits = getchar();    /* set -b from file */
  176.             block_compress = maxbits & BLOCK_MASK;
  177.             maxbits &= BIT_MASK;
  178.             maxmaxcode = 1L << maxbits;
  179.             if(maxbits > BITS) {
  180.             fprintf(stderr,
  181.             "%s: compressed with %d bits, can only handle %d bits\n",
  182.             ifname, maxbits, BITS);
  183.             exit(1);
  184.             }
  185.         }
  186.  
  187.         if(nListAsked)
  188.         {
  189.             struct tm *ptm =gmtime(&statbuf.st_mtime);
  190.  
  191.             printf("Date       Time           Size Name\n");
  192.             printf("===============================================================\n");
  193.             printf("%02d/%02d/%04d %02d:%02d:%02d %10d %s\n",ptm->tm_mday,ptm->tm_mon,ptm->tm_year+1900,
  194.                     ptm->tm_hour,ptm->tm_min,ptm->tm_sec,
  195.                     statbuf.st_size,ofname);
  196.             printf("---------------------------------------------------------------\n");
  197.             exit(0);
  198.         }
  199.  
  200.         /* Check for overwrite of existing file */
  201.         if (stat(ofname, &statbuf) == 0) {
  202.             char response[2];
  203.             response[0] = 'n';
  204.             fprintf(stderr, "%s already exists;", ofname);
  205.             fprintf(stderr, " do you wish to overwrite %s (y or n)? ",
  206.             ofname);
  207.             fflush(stderr);
  208.             read(2, response, 2);
  209.             while (response[1] != '\n') {
  210.                 if (read(2, response+1, 1) < 0) {    /* Ack! */
  211.                 perror("stderr"); break;
  212.                 }
  213.             }
  214.             if (response[0] != 'y') {
  215.             fprintf(stderr, "\tnot overwritten\n");
  216.             exit(1);
  217.             }
  218.         }
  219.         if (freopen(ofname, "wb", stdout) == NULL) {
  220.             perror(ofname);
  221.             exit(1);
  222.         }
  223.  
  224.     hsize = min(HSIZE, fsize); /* cannot have more codes than file size */
  225.     htab = (char_type huge*)calloc(hsize, sizeof(char_type));
  226.     if (htab == NULL) {
  227.     fprintf(stderr,"Not enough memory\n");
  228.     //fprintf(stderr,"Far heap size %lu hsize %u\n",coreleft(), hsize);
  229.     exit(1);
  230.     }
  231.     codetab = (unsigned short huge*)calloc(hsize, sizeof(unsigned short));
  232.     if(codetab == NULL) {
  233.     fprintf(stderr, "Not enough memory\n");
  234.     //fprintf(stderr,"Far heap size %lu hsize %u\n",farcoreleft(), hsize);
  235.     exit(1);
  236.     }
  237.     de_stack = (char_type *)malloc(8000);
  238.  
  239.     decompress();
  240.  
  241.     printf("finished decompressing %s\n",ofname);
  242.  
  243.     exit(0);
  244. }
  245.  
  246.  
  247. /*
  248.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  249.  * file building the "string" table on-the-fly; requiring no table to
  250.  * be stored in the compressed file.  The tables used herein are shared
  251.  * with those of the compress() routine.  See the definitions above.
  252.  */
  253.  
  254. decompress() {
  255.     register char_type *stackp;
  256.     register code_int finchar;
  257.     register code_int code, oldcode, incode;
  258.  
  259.     /*
  260.      * As above, initialize the first 256 entries in the table.
  261.      */
  262.     maxcode = MAXCODE(n_bits = INIT_BITS);
  263.     for ( code = 255; code >= 0; code-- ) {
  264.     tab_prefixof(code) = 0;
  265.     tab_suffixof(code) = (char_type)code;
  266.     }
  267.     free_ent = ((block_compress) ? FIRST : 256 );
  268.  
  269.     finchar = oldcode = getcode();
  270.     if(oldcode == -1)    /* EOF already? */
  271.     return;            /* Get out of here */
  272.     putchar( (char)finchar );        /* first code must be 8 bits = char */
  273.     if(ferror(stdout))        /* Crash if can't write */
  274.     writeerr();
  275.     stackp = de_stack;
  276.  
  277.     while ( (code = getcode()) > -1 ) {
  278.  
  279.     if ( (code == CLEAR) && block_compress ) {
  280.         for ( code = 255; code >= 0; code-- )
  281.         tab_prefixof(code) = 0;
  282.         clear_flg = 1;
  283.         free_ent = FIRST - 1;
  284.         if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  285.         break;
  286.     }
  287.     incode = code;
  288.     /*
  289.      * Special case for KwKwK string.
  290.      */
  291.     if ( code >= free_ent ) {
  292.             *stackp++ = finchar;
  293.         code = oldcode;
  294.     }
  295.  
  296.     /*
  297.      * Generate output characters in reverse order
  298.      */
  299. #ifdef SIGNED_COMPARE_SLOW
  300.     while ( ((unsigned long)code) >= ((unsigned long)256) ) {
  301. #else
  302.     while ( code >= 256 ) {
  303. #endif
  304.         *stackp++ = tab_suffixof(code);
  305.         code = tab_prefixof(code);
  306.     }
  307.     *stackp++ = finchar = tab_suffixof(code);
  308.  
  309.     /*
  310.      * And put them out in forward order
  311.      */
  312.     do
  313.         putchar ( *--stackp );
  314.     while ( stackp > de_stack );
  315.  
  316.     /*
  317.      * Generate the new entry.
  318.      */
  319.     if ( (code=free_ent) < maxmaxcode ) {
  320.         tab_prefixof(code) = (unsigned short)oldcode;
  321.         tab_suffixof(code) = finchar;
  322.         free_ent = code+1;
  323.     }
  324.     /*
  325.      * Remember previous code.
  326.      */
  327.     oldcode = incode;
  328.     }
  329.     fflush( stdout );
  330.     if(ferror(stdout))
  331.     writeerr();
  332. }
  333.  
  334. /*****************************************************************
  335.  * TAG( getcode )
  336.  *
  337.  * Read one code from the standard input.  If EOF, return -1.
  338.  * Inputs:
  339.  *     stdin
  340.  * Outputs:
  341.  *     code or -1 is returned.
  342.  */
  343.  
  344. code_int
  345. getcode() {
  346.     register code_int code;
  347.     static long int offset = 0, size = 0;
  348.     static char_type buf[BITS];
  349.     register int r_off, bits;
  350.     register char_type *bp = buf;
  351.  
  352.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
  353.     /*
  354.      * If the next entry will be too big for the current code
  355.      * size, then we must increase the size.  This implies reading
  356.      * a new buffer full, too.
  357.      */
  358.     if ( free_ent > maxcode ) {
  359.         n_bits++;
  360.         if ( n_bits == maxbits )
  361.         maxcode = maxmaxcode;    /* won't get any bigger now */
  362.         else
  363.         maxcode = MAXCODE(n_bits);
  364.     }
  365.     if ( clear_flg > 0) {
  366.             maxcode = MAXCODE (n_bits = INIT_BITS);
  367.         clear_flg = 0;
  368.     }
  369.     size = fread( buf, 1, n_bits, stdin );
  370.     if ( size <= 0 )
  371.         return -1;            /* end of file */
  372.     offset = 0;
  373.     /* Round size down to integral number of codes */
  374.     size = (size << 3) - (n_bits - 1);
  375.     }
  376.     r_off = offset;
  377.     bits = n_bits;
  378.     /*
  379.      * Get to the first byte.
  380.      */
  381.     bp += (r_off >> 3);
  382.     r_off &= 7;
  383.     /* Get first part (low order bits) */
  384. #ifdef NO_UCHAR
  385.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  386. #else
  387.     code = (*bp++ >> r_off);
  388. #endif /* NO_UCHAR */
  389.     bits -= (8 - r_off);
  390.     r_off = 8 - r_off;        /* now, offset into code word */
  391.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  392.     if ( bits >= 8 ) {
  393. #ifdef NO_UCHAR
  394.         code |= (*bp++ & 0xff) << r_off;
  395. #else
  396.         code |= *bp++ << r_off;
  397. #endif /* NO_UCHAR */
  398.         r_off += 8;
  399.         bits -= 8;
  400.     }
  401.     /* high order bits. */
  402.     code |= (*bp & rmask[bits]) << r_off;
  403.     offset += n_bits;
  404. /* Turbo C sign extends, so correct this bug (?) */
  405. #if BITS > 15
  406.     code &= 0xffff;
  407. #endif
  408.     return code;
  409. }
  410.  
  411. writeerr()
  412. {
  413.     perror ( ofname );
  414.     unlink ( ofname );
  415.     exit ( 1 );
  416. }
  417.