home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / uucp / auucp+-1.02 / fuucp_plus_src.lzh / compress / compress.c next >
Encoding:
C/C++ Source or Header  |  1991-03-13  |  28.2 KB  |  1,191 lines
  1.  
  2. /*
  3.  * Compress - data compression program
  4.  *
  5.  * Additional Features Copyright (C) 1990, 1991 Ingo Feulner:
  6.  *
  7.  * - xx.xx.90: Compress acts now like a real UN*X compress
  8.  *             Compress compiles now under Lattice/SAS C using small code/data model!
  9.  *             Added prototypes so that registerized parameters can be used.
  10.  * - 17.02.91: Speeded up disk access by using a bigger io buf.
  11.  * - 18.02.91: Added the flag '-m'. With this flag the maximum io buf can be set.
  12.  * - 19.02.91: Added online help. Now compress used fewer mem when in decompression mode
  13.  * - 21.02.91: Removed the flag '-m'. Added instead a test for enough free space with
  14.  *             AllocMem(MEMF_LARGEST).
  15.  *
  16.  */
  17.  
  18. #include <string.h>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <ctype.h>
  22. #include <fcntl.h>
  23. #ifdef AMIGA
  24. #define VERDATE " 1.37 (21 Feb 91) "
  25.  
  26. #include <dos.h>
  27. #include <exec/types.h>
  28. #include <exec/memory.h>
  29. #include <libraries/dos.h>
  30. #include <proto/exec.h>
  31. #include <proto/dos.h>
  32. #include "compress.h" /* Prototypes */
  33. #endif /* AMIGA */
  34.  
  35. #ifdef memset
  36. #undef memset
  37. #endif
  38. extern void *__stdargs memset(void *, int, unsigned);
  39.  
  40. /*
  41.  * Set USERMEM to the maximum amount of physical user memory available
  42.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  43.  * for compression.
  44.  *
  45.  * SACREDMEM is the amount of physical memory saved for others; compress
  46.  * will hog the rest.
  47.  */
  48.  
  49. /* Version String for 2.0 */
  50.  
  51. static char *version20 = "$VER: compress" VERDATE "\n\r";
  52.  
  53. #define perror(x)    poserr(x) /* Amiga DOS Error messages */
  54.  
  55. #define USERMEM    450000    /* default user memory */
  56. #define PBITS 16
  57. #define BITS PBITS
  58.  
  59. #define HSIZE    69001        /* 95% occupancy */
  60.  
  61. /*
  62.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  63.  */
  64.  
  65. #if BITS > 15
  66. typedef long int    code_int;
  67. #else
  68. typedef int        code_int;
  69. #endif
  70.  
  71. typedef long int      count_int;
  72. typedef    unsigned char    char_type;
  73.  
  74. char_type magic_header[] = { "\037\235" };      /* 1F 9D */
  75.  
  76. /* Defines for third byte of header */
  77. #define BIT_MASK    0x1f
  78. #define BLOCK_MASK    0x80
  79. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  80.    a fourth header byte (for expansion).
  81. */
  82. #define INIT_BITS 9            /* initial number of bits/code */
  83.  
  84. static char rcs_ident[] = "AmigaUUCP Plus: compress" VERDATE "\n" \
  85.               "Fastest compress in the South...\n" \
  86.                           "Written by Ingo Feulner\n";
  87.  
  88. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  89.  
  90. int n_bits;                /* number of bits/code */
  91. int maxbits = BITS;            /* user settable max # bits/code */
  92. code_int maxcode;            /* maximum code, given n_bits */
  93. code_int maxmaxcode = 1 << BITS;    /* should NEVER generate this code */
  94.  
  95. #define MAXCODE(n_bits)        ((1 << (n_bits)) - 1)
  96.  
  97. count_int *htab;
  98. unsigned short *codetab;
  99.  
  100. // Extension by IF
  101. #define STDIOBUFSIZE 16348
  102. long iobufsize;
  103.  
  104. char *bufin;
  105. char *bufout;
  106.  
  107. #define htabof(i)       htab[i]
  108. #define codetabof(i)    codetab[i]
  109.  
  110. code_int hsize = HSIZE;         /* for dynamic table sizing */
  111. count_int fsize = 0;
  112.  
  113. /*
  114.  * To save much memory, we overlay the table used by compress() with those
  115.  * used by decompress().  The tab_prefix table is the same size and type
  116.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  117.  * get this from the beginning of htab.  The output stack uses the rest
  118.  * of htab, and contains characters.  There is plenty of room for any
  119.  * possible stack (stack used to be 8000 characters).
  120.  */
  121.  
  122. #define tab_prefixof(i) codetabof(i)
  123. #define tab_suffixof(i) ((char_type *)(htab))[i]
  124. #define de_stack    ((char_type *)&tab_suffixof(1<<BITS))
  125.  
  126. code_int free_ent = 0;            /* first unused entry */
  127. int exit_stat = 0;
  128.  
  129.  
  130. void Usage(void)
  131. {
  132.   fprintf(stderr, "Usage: compress [-dfvcV] [-b maxbits] [file ...]\n");
  133.   fprintf(stderr, "\n\t-d: If given, decompression is done instead.\n");
  134.   fprintf(stderr, "\t-c: Write output on stdout, don't remove original.\n");
  135.   fprintf(stderr, "\t-b: Parameter limits the max number of bits/code.\n");
  136.   fprintf(stderr, "\t-f: Forces output file to be generated, even if one already\n");
  137.   fprintf(stderr, "\t    exists, and even if no space is saved by compressing.\n");
  138.   fprintf(stderr, "\t-v: Write compression statistics.\n");
  139.   fprintf(stderr, "\t-V: Print version.\n");
  140. }
  141.  
  142. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  143. int zcat_flg = 0;   /* Write output on stdout, suppress messages */
  144. int quiet = 1;        /* don't tell me about compression */
  145.  
  146. /*
  147.  * block compression parameters -- after all codes are used up,
  148.  * and compression rate changes, start over.
  149.  */
  150.  
  151. int block_compress = BLOCK_MASK;
  152. int clear_flg = 0;
  153. long int ratio = 0;
  154.  
  155. #define CHECK_GAP 10000 /* ratio check interval */
  156.  
  157. count_int checkpoint = CHECK_GAP;
  158. /*
  159.  * the next two codes should not be changed lightly, as they must not
  160.  * lie within the contiguous general code space.
  161.  */
  162.  
  163. #define FIRST    257    /* first free entry */
  164. #define CLEAR    256    /* table clear output code */
  165.  
  166. int force = 0;
  167. char ofname[100];
  168.  
  169. int do_decomp = 0;
  170.  
  171.  
  172. /*****************************************************************
  173.  * TAG( main )
  174.  *
  175.  * Algorithm from "A Technique for High Performance Data Compression",
  176.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  177.  *
  178.  * Usage: compress [-dfvc] [-b bits] [file ...]
  179.  * Inputs:
  180.  *  -d:    If given, decompression is done instead.
  181.  *
  182.  *  -c:    Write output on stdout, don't remove original.
  183.  *
  184.  *  -b:    Parameter limits the max number of bits/code.
  185.  *
  186.  *  -f:    Forces output file to be generated, even if one already
  187.  *         exists, and even if no space is saved by compressing.
  188.  *         If -f is not used, the user will be prompted if stdin is
  189.  *         a tty, otherwise, the output file will not be overwritten.
  190.  *
  191.  *  -v:    Write compression statistics
  192.  *
  193.  *  file ...:   Files to be compressed.  If none specified, stdin
  194.  *              is used.
  195.  * Outputs:
  196.  *  file.Z:     Compressed form of file with same mode, owner, and utimes
  197.  *  or stdout   (if stdin used as input)
  198.  *
  199.  * Assumptions:
  200.  *  When filenames are given, replaces with the compressed version
  201.  *  (.Z suffix) only if the file decreases in size.
  202.  * Algorithm:
  203.  *  Modified Lempel-Ziv method (LZW).  Basically finds common
  204.  *  substrings and replaces them with a variable size code.  This is
  205.  *  deterministic, and can be done on the fly.  Thus, the decompression
  206.  *  procedure needs no input table, but tracks the way the table was built.
  207.  */
  208.  
  209.  
  210. void main(int argc, char **argv)
  211. {
  212.   int overwrite = 0;  /* Do not overwrite unless given -f flag */
  213.   int newsskip  = 0;
  214.   int showversion = 0;
  215.   char tempname[100];
  216.   char **filelist, **fileptr;
  217.   char *cp;
  218.  
  219.  
  220.   filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
  221.   *filelist = NULL;
  222.  
  223.   if((cp = rindex(argv[0], '/')) != 0)
  224.   {
  225.     cp++;
  226.   }
  227.   else
  228.   {
  229.     cp = argv[0];
  230.   }
  231.  
  232.   if(strcmp(cp, "uncompress") == 0)
  233.   {
  234.     do_decomp = 1;
  235.   }
  236.   else if(strcmp(cp, "zcat") == 0)
  237.   {
  238.     do_decomp = 1;
  239.     zcat_flg = 1;
  240.   }
  241.  
  242.   /* Argument Processing
  243.    * All flags are optional.
  244.    * -D => debug
  245.    * -V => print Version; debug verbose
  246.    * -d => do_decomp
  247.    * -v => unquiet
  248.    * -f => force overwrite of output file
  249.    * -n => no header: useful to uncompress old files
  250.    * -b maxbits => maxbits.  If -b is specified, then maxbits MUST be
  251.    *                         given also.
  252.    * -c => cat all output to stdout
  253.    * -C => generate output compatible with compress 2.0.
  254.    *
  255.    * New flags added by Ingo Feulner:
  256.    * -s => skip first 12 bytes from stdin; added for newssupport.
  257.    */
  258.  
  259.   for (argc--, argv++; argc > 0; argc--, argv++)
  260.   {
  261.     if (**argv == '-')    /* A flag argument */
  262.     {
  263.       while (*++(*argv))  /* Process all flags in this arg */
  264.       {
  265.         switch (**argv)
  266.         {
  267.           case 'V':
  268.             showversion = 1;
  269.             break;
  270.           case 'v':
  271.             quiet = 0;
  272.             break;
  273.           case 'd':
  274.             do_decomp = 1;
  275.             break;
  276.           case 'f':
  277.           case 'F':
  278.             overwrite = 1;
  279.             force = 1;
  280.             break;
  281.           case 'n':
  282.             nomagic = 1;
  283.             break;
  284.           case 'C':
  285.             block_compress = 0;
  286.             break;
  287.           case 'b':
  288.             if (!ARGVAL())
  289.             {
  290.               fprintf(stderr, "Missing maxbits\n");
  291.               Usage();
  292.               exit(1);
  293.             }
  294.             maxbits = atoi(*argv);
  295.             goto nextarg;
  296.           case 'c':
  297.             zcat_flg = 1;
  298.             break;
  299.           case 'q':
  300.             quiet = 1;
  301.             break;
  302.           case 's':
  303.             do_decomp = 1;
  304.             newsskip = 1; /* Newssupport flag. See above */
  305.             break;
  306.           case '?':
  307.             Usage();
  308.             exit(0);
  309.             break;
  310.           default:
  311.             fprintf(stderr, "Unknown flag: '%c'; ", **argv);
  312.             Usage();
  313.             exit(1);
  314.         }
  315.       }
  316.     }
  317.     else  /* Input file name */
  318.     {
  319.       *fileptr++ = *argv; /* Build input file list */
  320.       *fileptr = NULL;
  321.       /* process nextarg; */
  322.     }
  323.  
  324.     nextarg:
  325.       continue;
  326.   }
  327.  
  328.   if(showversion != 0)
  329.     version();
  330.  
  331.   if(maxbits < INIT_BITS)
  332.     maxbits = INIT_BITS;
  333.  
  334.   if(maxbits > BITS)
  335.     maxbits = BITS;
  336.  
  337.   maxmaxcode = 1 << maxbits;
  338.  
  339.   /* Now: allocate mem! -IF- */
  340.   if(do_decomp != 1)
  341.     htab = (count_int *)malloc(HSIZE * sizeof(count_int));
  342.   else // If Decompression, we need not so much memory...
  343.     htab = (count_int *)malloc((1L << BITS) + 8000);
  344.   codetab = (unsigned short *)malloc(HSIZE * sizeof(unsigned short));
  345.  
  346.   if(htab == NULL || codetab == NULL)
  347.   {
  348.     fprintf(stderr, "%s: can't allocate memory.\n", argv[0]);
  349.     exit(20);
  350.   }
  351.  
  352.   if(*filelist != NULL)
  353.   {
  354.     for (fileptr = filelist; *fileptr; fileptr++)
  355.     {
  356.       exit_stat = 0;
  357.       if (do_decomp != 0)  /* DECOMPRESSION */
  358.       {
  359.         /* Check for .Z suffix */
  360.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") != 0)
  361.         {
  362.           /* No .Z: tack one on */
  363.           strcpy(tempname, *fileptr);
  364.           strcat(tempname, ".Z");
  365.           *fileptr = tempname;
  366.         }
  367.         /* Open input file */
  368.         if ((freopen(*fileptr, "rb", stdin)) == NULL)
  369.         {
  370.           perror(*fileptr);
  371.           continue;
  372.         }
  373.  
  374.         fsize = getfilesize(*fileptr);
  375.  
  376.         iobufsize = (fsize * 4) / 10;
  377.         if((iobufsize < STDIOBUFSIZE) || (AvailMem(MEMF_LARGEST) < (iobufsize * 2)))
  378.         {
  379.           iobufsize = STDIOBUFSIZE;
  380.         }
  381.  
  382.         if((bufin = malloc(iobufsize)) == NULL)
  383.         {
  384.           fprintf(stderr, "%s: can't allocate memory.\n", argv[0]);
  385.           exit(10);
  386.         }
  387.         setvbuf(stdin, bufin, _IOFBF, iobufsize);
  388.  
  389.         /* Check the magic number */
  390.         if (nomagic == 0)
  391.         {
  392.           if ((getchar() != (magic_header[0] & 0xFF))
  393.            || (getchar() != (magic_header[1] & 0xFF)))
  394.           {
  395.             fprintf(stderr, "%s: not in compressed format\n", *fileptr);
  396.             continue;
  397.           }
  398.           maxbits = getchar();        /* set -b from file */
  399.           block_compress = maxbits & BLOCK_MASK;
  400.           maxbits &= BIT_MASK;
  401.           maxmaxcode = 1 << maxbits;
  402.           if(maxbits > BITS)
  403.           {
  404.             fprintf(stderr, "%s: compressed with %d bits, can only handle %d bits\n",
  405.                             *fileptr, maxbits, BITS);
  406.             continue;
  407.           }
  408.         }
  409.         /* Generate output filename */
  410.         strcpy(ofname, *fileptr);
  411.         ofname[strlen(*fileptr) - 2] = '\0';  /* Strip off .Z */
  412.       }
  413.       else  /* COMPRESSION */
  414.       {
  415.         if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") == 0)
  416.         {
  417.           fprintf(stderr, "%s: already has .Z suffix -- no change\n", *fileptr);
  418.           continue;
  419.         }
  420.  
  421.         /* Open input file */
  422.         if ((freopen(*fileptr, "rb", stdin)) == NULL)
  423.         {
  424.           perror(*fileptr);
  425.           continue;
  426.         }
  427.  
  428.         fsize = getfilesize(*fileptr);
  429.  
  430.         iobufsize = (fsize * 2) / 10;
  431.         if((iobufsize < STDIOBUFSIZE ) || (AvailMem(MEMF_LARGEST) < (iobufsize * 2)))
  432.         {
  433.           iobufsize = STDIOBUFSIZE;
  434.         }
  435.  
  436.         if((bufin = malloc(iobufsize)) == NULL)
  437.         {
  438.           fprintf(stderr, "%s: can't allocate memory.\n", argv[0]);
  439.           exit(10);
  440.         }
  441.         setvbuf(stdin, bufin, _IOFBF, iobufsize);
  442.  
  443.         /*
  444.          * tune hash table size for small files -- ad hoc,
  445.          * but the sizes match earlier #defines, which
  446.          * serve as upper bounds on the number of output codes.
  447.          */
  448.         hsize = HSIZE;
  449.         if ( fsize < (1 << 12) )
  450.           hsize = min ( 5003, HSIZE );
  451.         else if ( fsize < (1 << 13) )
  452.           hsize = min ( 9001, HSIZE );
  453.         else if ( fsize < (1 << 14) )
  454.           hsize = min ( 18013, HSIZE );
  455.         else if ( fsize < (1 << 15) )
  456.           hsize = min ( 35023, HSIZE );
  457.         else if ( fsize < 47000 )
  458.           hsize = min ( 50021, HSIZE );
  459.  
  460.         /* Generate output filename */
  461.  
  462.         strcpy(ofname, *fileptr);
  463.         strcat(ofname, ".Z");
  464.       }
  465.  
  466.       /* Check for overwrite of existing file */
  467.       if(overwrite == 0 && zcat_flg == 0)
  468.       {
  469.         BPTR lock;
  470.  
  471.         if((lock = Lock(ofname, ACCESS_READ)) != NULL)
  472.         {
  473.           char response[2];
  474.  
  475.           UnLock(lock);
  476.  
  477.           fprintf(stderr, "%s already exists;", ofname);
  478.           if(foreground())
  479.           {
  480.             fprintf(stderr, " do you want to overwrite %s (y or n)?", ofname);
  481.             fflush(stderr);
  482.             read(2, response, 2);
  483.             while(response[1] != '\n')
  484.             {
  485.               if(read(2, response+1, 1) < 0)
  486.               {
  487.                 perror("stderr");
  488.                 break;
  489.               }
  490.             }
  491.           }
  492.  
  493.           if(response[0] != 'y')
  494.           {
  495.             fprintf(stderr, "\tnot overwritten\n");
  496.             continue;
  497.           }
  498.         }
  499.       }
  500.  
  501.       if(zcat_flg == 0)         /* Open output file */
  502.       {
  503.         if (freopen(ofname, "wb", stdout) == NULL)
  504.         {
  505.           perror(ofname);
  506.           continue;
  507.         }
  508.  
  509.         if((bufout = malloc(iobufsize)) == NULL)
  510.         {
  511.           fprintf(stderr, "%s: can't allocate memory.\n", argv[0]);
  512.           exit(10);
  513.         }
  514.         setvbuf(stdout, bufout, _IOFBF, iobufsize);
  515.  
  516.         if(!quiet)
  517.           fprintf(stderr, "%s: ", *fileptr);
  518.       }
  519.  
  520.       /* Actually do the compression/decompression */
  521.       if (do_decomp == 0)
  522.         compress();
  523.       else
  524.         decompress();
  525.  
  526.       if(zcat_flg == 0)
  527.       {
  528.         copystat(*fileptr, ofname);     /* Copy stats */
  529.         if((exit_stat == 1) || (!quiet))
  530.           putc('\n', stderr);
  531.       }
  532.     }
  533.   }   /* Standard input */
  534.   else
  535.   {
  536.     bufin  = malloc(STDIOBUFSIZE);
  537.     bufout = malloc(STDIOBUFSIZE);
  538.  
  539.     if(bufin == NULL || bufout == NULL)
  540.     {
  541.       fprintf(stderr, "%s: can't allocate memory.\n", argv[0]);
  542.       exit(10);
  543.     }
  544.     /* Set new buffers */
  545.     setvbuf(stdin,  bufin,  _IOFBF, STDIOBUFSIZE);
  546.     setvbuf(stdout, bufout, _IOFBF, STDIOBUFSIZE);
  547.  
  548.     if (do_decomp == 0)
  549.     {
  550.       compress();
  551.       if(!quiet)
  552.         putc('\n', stderr);
  553.     }
  554.     else
  555.     {
  556.       if(newsskip == 1)
  557.       {
  558.         short zaehler = 0;
  559.  
  560.         /* Skip first 12 bytes, which contain "#! cunbatch\n" */
  561.         while(zaehler++ < 12)
  562.           getchar();
  563.       }
  564.  
  565.       /* Check the magic number */
  566.       if (nomagic == 0)
  567.       {
  568.         if ((getchar()!=(magic_header[0] & 0xFF))
  569.          || (getchar()!=(magic_header[1] & 0xFF)))
  570.         {
  571.           fprintf(stderr, "stdin: not in compressed format\n");
  572.           exit(1);
  573.         }
  574.         maxbits = getchar();    /* set -b from file */
  575.         block_compress = maxbits & BLOCK_MASK;
  576.         maxbits &= BIT_MASK;
  577.         maxmaxcode = 1 << maxbits;
  578.         fsize = 100000;     /* assume stdin large for USERMEM */
  579.         if(maxbits > BITS)
  580.         {
  581.           fprintf(stderr,
  582.             "stdin: compressed with %d bits, can only handle %d bits\n",
  583.                 maxbits, BITS);
  584.           exit(1);
  585.         }
  586.       }
  587.       decompress();
  588.     }
  589.   }
  590.   exit(exit_stat);
  591. }
  592.  
  593. static int offset;
  594. long int in_count = 1;    /* length of input */
  595. long int bytes_out;       /* length of compressed output */
  596.  
  597. /*
  598.  * compress stdin to stdout
  599.  *
  600.  * Algorithm:  use open addressing double hashing (no chaining) on the
  601.  * prefix code / next character combination.  We do a variant of Knuth's
  602.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  603.  * secondary probe.  Here, the modular division first probe is gives way
  604.  * to a faster exclusive-or manipulation.  Also do block compression with
  605.  * an adaptive reset, whereby the code table is cleared when the compression
  606.  * ratio decreases, but after the table fills.    The variable-length output
  607.  * codes are re-sized at this point, and a special CLEAR code is generated
  608.  * for the decompressor.  Late addition:  construct the table according to
  609.  * file size for noticeable speed improvement on small files.  Please direct
  610.  * questions about this implementation to ames!jaw.
  611.  */
  612.  
  613. static void compress(void)
  614. {
  615.   long fcode;
  616.   code_int i;
  617.   int c;
  618.   code_int ent;
  619.   int disp;
  620.   code_int hsize_reg;
  621.   int hshift;
  622.  
  623.   if(nomagic == 0)
  624.   {
  625.     putchar(magic_header[0]);
  626.     putchar(magic_header[1]);
  627.  
  628.     putchar((char)(maxbits | block_compress));
  629.     if(ferror(stdout))
  630.       writeerr();
  631.   }
  632.  
  633.   offset = 0;
  634.   bytes_out = 3;    /* includes 3-byte header mojo */
  635.   clear_flg = 0;
  636.   ratio = 0;
  637.   in_count = 1;
  638.   checkpoint = CHECK_GAP;
  639.   maxcode = MAXCODE(n_bits = INIT_BITS);
  640.   free_ent = ((block_compress) ? FIRST : 256 );
  641.  
  642.   ent = getchar();
  643.  
  644.   hshift = 0;
  645.   for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  646.     hshift++;
  647.  
  648.   hshift = 8 - hshift;    /* set hash code range bound */
  649.  
  650.   hsize_reg = hsize;
  651.   cl_hash( (count_int) hsize_reg);            /* clear hash table */
  652.  
  653.   while ( (c = getchar()) != EOF )
  654.   {
  655.     in_count++;
  656.     fcode = (long) (((long) c << maxbits) + ent);
  657.     i = ((c << hshift) ^ ent);      /* xor hashing */
  658.  
  659.     if ( htabof (i) == fcode )
  660.     {
  661.       ent = codetabof (i);
  662.       continue;
  663.     }
  664.     else if ( (long)htabof (i) < 0 )      /* empty slot */
  665.       goto nomatch;
  666.  
  667.     disp = hsize_reg - i;        /* secondary hash (after G. Knott) */
  668.     if ( i == 0 )
  669.       disp = 1;
  670.  
  671. probe:
  672.     if ( (i -= disp) < 0 )
  673.       i += hsize_reg;
  674.  
  675.     if ( htabof (i) == fcode )
  676.     {
  677.       ent = codetabof (i);
  678.       continue;
  679.     }
  680.     if ( (long)htabof (i) > 0 )
  681.       goto probe;
  682. nomatch:
  683.     output ( (code_int) ent );
  684.     ent = c;
  685.  
  686.     if ( free_ent < maxmaxcode )
  687.     {
  688.       codetabof (i) = free_ent++; /* code -> hashtable */
  689.       htabof (i) = fcode;
  690.     }
  691.     else if ( (count_int)in_count >= checkpoint && block_compress )
  692.       cl_block();
  693.   }
  694.   /*
  695.    * Put out the final code.
  696.    */
  697.   output( (code_int)ent );
  698.   output( (code_int)-1 );
  699.  
  700.   /*
  701.    * Print out stats on stderr
  702.    */
  703.   if(zcat_flg == 0 && (!quiet))
  704.   {
  705.     fprintf( stderr, "Compression: " );
  706.     prratio( stderr, in_count-bytes_out, in_count );
  707.   }
  708.     if(bytes_out > in_count)    /* exit(2) if no savings */
  709.       exit_stat = 2;
  710.     return;
  711. }
  712.  
  713. /*****************************************************************
  714.  * TAG( output )
  715.  *
  716.  * Output the given code.
  717.  * Inputs:
  718.  *   code:  A n_bits-bit integer.  If == -1, then EOF.  This assumes
  719.  *          that n_bits =< (long)wordsize - 1.
  720.  * Outputs:
  721.  *   Outputs code to the file.
  722.  * Assumptions:
  723.  *   Chars are 8 bits long.
  724.  * Algorithm:
  725.  *   Maintain a BITS character long buffer (so that 8 codes will
  726.  *   fit in it exactly). Use the VAX insv instruction to insert each
  727.  *   code in turn.  When the buffer fills up empty it and start over.
  728.  */
  729.  
  730. static char buf[BITS];
  731.  
  732. char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  733. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  734.  
  735. void output(code)
  736. code_int  code;
  737. {
  738.   int r_off = offset, bits = n_bits;
  739.   char *bp = buf;
  740.  
  741.   if ( code >= 0 )
  742.   {
  743.     /*
  744.      * Get to the first byte.
  745.      */
  746.  
  747.     bp += (r_off >> 3);
  748.     r_off &= 7;
  749.  
  750.     /*
  751.      * Since code is always >= 8 bits, only need to mask the first
  752.      * hunk on the left.
  753.      */
  754.  
  755.     *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  756.     bp++;
  757.     bits -= (8 - r_off);
  758.     code >>=(8 - r_off);
  759.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  760.     if ( bits >= 8 )
  761.     {
  762.       *bp++ = code;
  763.       code >>= 8;
  764.       bits -= 8;
  765.     }
  766.     /* Last bits. */
  767.     if(bits)
  768.       *bp = code;
  769.  
  770.     offset += n_bits;
  771.     if ( offset == (n_bits << 3) )
  772.     {
  773.       bp = buf;
  774.       bits = n_bits;
  775.       bytes_out += bits;
  776.       do
  777.         putchar(*bp++);
  778.       while(--bits);
  779.       offset = 0;
  780.     }
  781.  
  782.     /*
  783.      * If the next entry is going to be too big for the code size,
  784.      * then increase it, if possible.
  785.      */
  786.     if ( free_ent > maxcode || (clear_flg > 0))
  787.     {
  788.       /*
  789.        * Write the whole buffer, because the input side won't
  790.        * discover the size increase until after it has read it.
  791.        */
  792.       if ( offset > 0 )
  793.       {
  794.         if( fwrite( buf, 1, n_bits, stdout ) != n_bits)
  795.           writeerr();
  796.         bytes_out += n_bits;
  797.       }
  798.       offset = 0;
  799.  
  800.       if ( clear_flg )
  801.       {
  802.         maxcode = MAXCODE (n_bits = INIT_BITS);
  803.         clear_flg = 0;
  804.       }
  805.       else
  806.       {
  807.         n_bits++;
  808.         if ( n_bits == maxbits )
  809.           maxcode = maxmaxcode;
  810.         else
  811.           maxcode = MAXCODE(n_bits);
  812.       }
  813.     }
  814.   }
  815.   else
  816.   {
  817.     /*
  818.      * At EOF, write the rest of the buffer.
  819.      */
  820.     if ( offset > 0 )
  821.       fwrite( buf, 1, (offset + 7) / 8, stdout );
  822.     bytes_out += (offset + 7) / 8;
  823.     offset = 0;
  824.     fflush( stdout );
  825.  
  826.     if( ferror( stdout ) )
  827.       writeerr();
  828.   }
  829. }
  830.  
  831. /*
  832.  * Decompress stdin to stdout.    This routine adapts to the codes in the
  833.  * file building the "string" table on-the-fly; requiring no table to
  834.  * be stored in the compressed file.  The tables used herein are shared
  835.  * with those of the compress() routine.  See the definitions above.
  836.  */
  837.  
  838. static void decompress(void)
  839. {
  840.   char_type *stackp;
  841.   int finchar;
  842.   code_int code, oldcode, incode;
  843.  
  844.   /*
  845.    * As above, initialize the first 256 entries in the table.
  846.    */
  847.   maxcode = MAXCODE(n_bits = INIT_BITS);
  848.   for ( code = 255; code >= 0; code-- )
  849.   {
  850.     tab_prefixof(code) = 0;
  851.     tab_suffixof(code) = (char_type)code;
  852.   }
  853.   free_ent = ((block_compress) ? FIRST : 256 );
  854.  
  855.   finchar = oldcode = getcode();
  856.   if(oldcode == -1)   /* EOF already? */
  857.     return;     /* Get out of here */
  858.   putchar( (char)finchar );           /* first code must be 8 bits = char */
  859.   if(ferror(stdout))          /* Crash if can't write */
  860.     writeerr();
  861.   stackp = de_stack;
  862.  
  863.   while ( (code = getcode()) > -1 )
  864.   {
  865.     if ( (code == CLEAR) && block_compress )
  866.     {
  867.       for ( code = 255; code >= 0; code-- )
  868.         tab_prefixof(code) = 0;
  869.       clear_flg = 1;
  870.       free_ent = FIRST - 1;
  871.       if ( (code = getcode ()) == -1 )    /* O, untimely death! */
  872.         break;
  873.     }
  874.     incode = code;
  875.  
  876.     /*
  877.      * Special case for KwKwK string.
  878.      */
  879.  
  880.     if ( code >= free_ent )
  881.     {
  882.       *stackp++ = finchar;
  883.       code = oldcode;
  884.     }
  885.  
  886.    /*
  887.     * Generate output characters in reverse order
  888.     */
  889.  
  890.     while ( code >= 256 )
  891.     {
  892.       *stackp++ = tab_suffixof(code);
  893.       code = tab_prefixof(code);
  894.     }
  895.     *stackp++ = finchar = tab_suffixof(code);
  896.  
  897.     /*
  898.      * And put them out in forward order
  899.      */
  900.     do
  901.       putchar ( *--stackp );
  902.     while ( stackp > de_stack );
  903.  
  904.     /*
  905.      * Generate the new entry.
  906.      */
  907.     if((code = free_ent) < maxmaxcode)
  908.     {
  909.       tab_prefixof(code) = (unsigned short)oldcode;
  910.       tab_suffixof(code) = finchar;
  911.       free_ent = code+1;
  912.     }
  913.     /*
  914.      * Remember previous code.
  915.      */
  916.     oldcode = incode;
  917.   }
  918.   fflush(stdout);
  919.   if(ferror(stdout))
  920.     writeerr();
  921. }
  922.  
  923. /*****************************************************************
  924.  * TAG( getcode )
  925.  *
  926.  * Read one code from the standard input.  If EOF, return -1.
  927.  * Inputs:
  928.  *  stdin
  929.  * Outputs:
  930.  *  code or -1 is returned.
  931.  */
  932.  
  933. code_int getcode(void)
  934. {
  935.   code_int code;
  936.   static int offset = 0, size = 0;
  937.   static char_type buf[BITS];
  938.   int r_off, bits;
  939.   char_type *bp = buf;
  940.  
  941.   if ( clear_flg > 0 || offset >= size || free_ent > maxcode )
  942.   {
  943.     /*
  944.      * If the next entry will be too big for the current code
  945.      * size, then we must increase the size.  This implies reading
  946.      * a new buffer full, too.
  947.      */
  948.     if ( free_ent > maxcode )
  949.     {
  950.       n_bits++;
  951.       if ( n_bits == maxbits )
  952.         maxcode = maxmaxcode;    /* won't get any bigger now */
  953.       else
  954.         maxcode = MAXCODE(n_bits);
  955.     }
  956.     if ( clear_flg > 0)
  957.     {
  958.       maxcode = MAXCODE (n_bits = INIT_BITS);
  959.       clear_flg = 0;
  960.     }
  961.  
  962.     size = fread( buf, 1, n_bits, stdin );
  963.     if ( size <= 0 )
  964.       return -1;      /* end of file */
  965.     offset = 0;
  966.     /* Round size down to integral number of codes */
  967.     size = (size << 3) - (n_bits - 1);
  968.   }
  969.   r_off = offset;
  970.   bits = n_bits;
  971.  
  972.   /*
  973.    * Get to the first byte.
  974.    */
  975.   bp += (r_off >> 3);
  976.   r_off &= 7;
  977.  
  978.   /* Get first part (low order bits) */
  979.   code = (*bp++ >> r_off);
  980.  
  981.   bits -= (8 - r_off);
  982.   r_off = 8 - r_off;    /* now, offset into code word */
  983.  
  984.   /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  985.   if ( bits >= 8 )
  986.   {
  987.     code |= *bp++ << r_off;
  988.     r_off += 8;
  989.     bits -= 8;
  990.   }
  991.  
  992.   /* high order bits. */
  993.   code |= (*bp & rmask[bits]) << r_off;
  994.   offset += n_bits;
  995.  
  996.   return code;
  997. }
  998.  
  999. char *rindex(char *s, char c) /* For those who don't have it in libc.a */
  1000. {
  1001.   char *p;
  1002.  
  1003.   for (p = NULL; *s; s++)
  1004.     if(*s == c)
  1005.       p = s;
  1006.  
  1007.   return(p);
  1008. }
  1009.  
  1010. void writeerr(void)
  1011. {
  1012.   perror(ofname);
  1013.   remove(ofname);
  1014.   exit(1);
  1015. }
  1016.  
  1017. void copystat(char *ifname, char *ofname)
  1018. {
  1019.   fclose(stdin);
  1020.   fclose(stdout);
  1021.  
  1022.   if(exit_stat == 2 && (!force))
  1023.   {
  1024.     if(!quiet)
  1025.       fprintf(stderr, " -- file unchanged");
  1026.   }
  1027.   else
  1028.   {
  1029.     exit_stat = 0;
  1030.  
  1031.     if(remove(ifname))
  1032.       perror(ifname);
  1033.  
  1034.     if(!quiet)
  1035.       fprintf(stderr, " -- replaced with %s", ofname);
  1036.  
  1037.     return;
  1038.   }
  1039.  
  1040.   if(remove(ofname))
  1041.     perror(ofname);
  1042. }
  1043.  
  1044. int foreground(void)
  1045. {
  1046.   if(IsInteractive(Input()) != DOSFALSE)
  1047.   {
  1048.     return 1;
  1049.   }
  1050.   else
  1051.     return 0;
  1052. }
  1053.  
  1054. void onintr(void)
  1055. {
  1056.   remove(ofname);
  1057.   exit(1);
  1058. }
  1059.  
  1060. void oops(void)        /* wild pointer -- assume bad input */
  1061. {
  1062.   if(do_decomp == 1)
  1063.     fprintf(stderr, "uncompress: corrupt input\n");
  1064.   remove(ofname);
  1065.   exit(1);
  1066. }
  1067.  
  1068. void cl_block(void)             /* table clear for block compress */
  1069. {
  1070.   long int rat;
  1071.  
  1072.   checkpoint = in_count + CHECK_GAP;
  1073.  
  1074.   if(in_count > 0x007fffff)  /* shift will overflow */
  1075.   {
  1076.     rat = bytes_out >> 8;
  1077.     if(rat == 0)          /* Don't divide by zero */
  1078.     {
  1079.       rat = 0x7fffffff;
  1080.     }
  1081.     else
  1082.     {
  1083.       rat = in_count / rat;
  1084.     }
  1085.   }
  1086.   else
  1087.   {
  1088.     rat = (in_count << 8) / bytes_out;      /* 8 fractional bits */
  1089.   }
  1090.  
  1091.   if ( rat > ratio )
  1092.   {
  1093.     ratio = rat;
  1094.   }
  1095.   else
  1096.   {
  1097.       ratio = 0;
  1098.  
  1099.     cl_hash ( (count_int) hsize );
  1100.     free_ent = FIRST;
  1101.     clear_flg = 1;
  1102.     output ( (code_int) CLEAR );
  1103.   }
  1104. }
  1105.  
  1106. void cl_hash(count_int hsize)          /* reset code table */
  1107. {
  1108.     count_int *htab_p = htab + hsize;
  1109.     const long m1 = -1;
  1110.     long i;
  1111.  
  1112.     i = hsize - 16;
  1113.     do
  1114.     {
  1115.                 *(htab_p - 16) = m1;
  1116.                 *(htab_p - 15) = m1;
  1117.                 *(htab_p - 14) = m1;
  1118.                 *(htab_p - 13) = m1;
  1119.                 *(htab_p - 12) = m1;
  1120.                 *(htab_p - 11) = m1;
  1121.                 *(htab_p - 10) = m1;
  1122.                 *(htab_p -  9) = m1;
  1123.                 *(htab_p -  8) = m1;
  1124.                 *(htab_p -  7) = m1;
  1125.                 *(htab_p -  6) = m1;
  1126.                 *(htab_p -  5) = m1;
  1127.                 *(htab_p -  4) = m1;
  1128.                 *(htab_p -  3) = m1;
  1129.                 *(htab_p -  2) = m1;
  1130.                 *(htab_p -  1) = m1;
  1131.         htab_p -= 16;
  1132.     } while ((i -= 16) >= 0);
  1133.  
  1134.     for ( i += 16; i > 0; i-- )
  1135.         *--htab_p = m1;
  1136. }
  1137.  
  1138. void prratio(FILE *stream, long int num, long int den)
  1139. {
  1140.     int q;         /* Doesn't need to be long */
  1141.  
  1142.     if(num > 214748L)            /* 2147483647/10000 */
  1143.     {
  1144.         q = num / (den / 10000L);
  1145.     }
  1146.     else
  1147.     {
  1148.         q = 10000L * num / den;  /* Long calculations, though */
  1149.     }
  1150.  
  1151.     if (q < 0)
  1152.     {
  1153.         putc('-', stream);
  1154.         q = -q;
  1155.     }
  1156.     fprintf(stream, "%d.%02d%%", q / 100, q % 100);
  1157. }
  1158.  
  1159. void version(void)
  1160. {
  1161.     fprintf(stderr, "%s\n", rcs_ident);
  1162.     fprintf(stderr, "Options: ");
  1163.     fprintf(stderr, "BITS = %d\n", BITS);
  1164. }
  1165.  
  1166. /*
  1167.  *  getfilesize() for the AMIGA.
  1168.  *  22.4.90 Ingo Feulner.
  1169.  */
  1170.  
  1171. long getfilesize(char *name)
  1172. {
  1173.   long size = 100000;
  1174.   struct FileInfoBlock *fib;
  1175.   BPTR lock;
  1176.  
  1177.   if((fib = AllocMem(sizeof(struct FileInfoBlock), MEMF_CLEAR)) != NULL)
  1178.   {
  1179.     if((lock = Lock(name, ACCESS_READ)) != NULL)
  1180.     {
  1181.       if((Examine(lock, fib)) != DOSFALSE)
  1182.       {
  1183.         size = fib->fib_Size;
  1184.       }
  1185.       UnLock(lock);
  1186.     }
  1187.     FreeMem(fib, sizeof(struct FileInfoBlock));
  1188.   }
  1189.   return(size);
  1190. }
  1191.