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