home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / packer / comp16 / compress.c next >
Encoding:
C/C++ Source or Header  |  1994-06-05  |  33.1 KB  |  1,236 lines
  1. /* 
  2.  * Compress - data compression program 
  3.  */
  4. static char rcs_ident[] = "@(#) compress,v 4.1 (DOS) 89/11/10 02:43:00 doug Release $";
  5.  
  6. /*
  7.  * compress.c - File compression ala IEEE Computer, June 1984.
  8.  *
  9.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  10.  *        Jim McKie        (decvax!mcvax!jim)
  11.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  12.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  13.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  14.  *        Joe Orost        (decvax!vax135!petsd!joe)
  15.  *        Doug Graham        (uunet!mitel!sce!tsmith!graham)
  16.  *
  17.  * Revision 4.1 (DOS) 89/11/10 02:43:00 doug
  18.  * Ported to MSDOS. Still works elsewhere, but maybe not as quickly.
  19.  * Removed as much long arithmetic as possible for speed on 16 bit machines.
  20.  * Use unsigned short's instead. Changed secondary hashing function to limit
  21.  * hash table size to 64K. This means table indexes can be 16 bit shorts.
  22.  * This compress will not generate codes from MAXMAXCODE (0xf000) thru
  23.  * 0xffff. Doesn't appear to hurt compression much. Removed speed hacks for
  24.  * other machines so I could understand the code. Added some for the i8088.
  25.  * Send CLEAR immediately when hash table fills instead of waiting for the
  26.  * compression ratio to drop. This is faster, and in some cases improves
  27.  * compression (but more often reduces it slightly). Junked the variable
  28.  * size hash table stuff because I am depending on 16 bit unsigned integer
  29.  * wrap around for indexing into hash table, so the table must have 2^16
  30.  * entries. Took out the XENIX_16 stuff. The DOS way ought to work on Xenix
  31.  * as well, and should be faster, but I don't have access to Xenix in order
  32.  * to find out. Added some extra error checking on decompression to try to
  33.  * avoid blowing the machine out of the water when decompressing a corrupt
  34.  * file. Add "okunlink" to avoid the problem of losing the output file as
  35.  * well as the input file if ^C is hit at the wrong time. Lot's of other
  36.  * cosmetic changes.
  37.  *
  38.  * Revision 4.0  85/07/30  12:50:00  joe
  39.  * Removed ferror() calls in output routine on every output except first.
  40.  * Prepared for release to the world.
  41.  * 
  42.  * Revision 3.6  85/07/04  01:22:21  joe
  43.  * Remove much wasted storage by overlaying hash table with the tables
  44.  * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
  45.  * computations.  Fixed dump_tab() DEBUG routine.
  46.  *
  47.  * Revision 3.5  85/06/30  20:47:21  jaw
  48.  * Change hash function to use exclusive-or.  Rip out hash cache.  These
  49.  * speedups render the megamemory version defunct, for now.  Make decoder
  50.  * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
  51.  *
  52.  * Revision 3.4  85/06/27  12:00:00  ken
  53.  * Get rid of all floating-point calculations by doing all compression ratio
  54.  * calculations in fixed point.
  55.  *
  56.  * Revision 3.3  85/06/24  21:53:24  joe
  57.  * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
  58.  * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
  59.  *
  60.  * Revision 3.2  85/06/06  21:53:24  jaw
  61.  * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
  62.  * Default to "quiet" output (no compression statistics).
  63.  *
  64.  * Revision 3.1  85/05/12  18:56:13  jaw
  65.  * Integrate decompress() stack speedups (from early pointer mods by McKie).
  66.  * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
  67.  * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase 
  68.  * output byte count by magic number size.
  69.  * 
  70.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  71.  * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  72.  * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
  73.  * unsigned compares on Perkin-Elmer.  Fixed foreground check.
  74.  *
  75.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  76.  * Cache common hash codes based on input statistics; this improves
  77.  * performance for low-density raster images.  Pass on #ifdef bundle
  78.  * from Turkowski.
  79.  *
  80.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  81.  * Vary size of hash tables to reduce time for small files.
  82.  * Tune PDP-11 hash function.
  83.  *
  84.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  85.  * Junk chaining; replace with the simpler (and, on the VAX, faster)
  86.  * double hashing, discussed within.  Make block compression standard.
  87.  *
  88.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  89.  * Introduce adaptive reset for block compression, to boost the rate
  90.  * another several percent.  (See mailing list notes.)
  91.  *
  92.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  93.  * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  94.  * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  95.  *
  96.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  97.  * Fold in news changes, small machine typedef from thomas,
  98.  * #ifdef interdata from joe.
  99.  *
  100.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  101.  * Configured fast table lookup for 32-bit machines.
  102.  * This cuts user time in half for b <= FBITS, and is useful for news batching
  103.  * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  104.  * added signal catcher [plus beef in writeerr()] to delete effluvia.
  105.  *
  106.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  107.  * Add check for foreground before prompting user.  Insert maxbits into
  108.  * compressed file.  Force file being uncompressed to end with ".Z".
  109.  * Added "-c" flag and "zcat".  Prepared for release.
  110.  *
  111.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  112.  * Will only compress regular files (no directories), added a magic number
  113.  * header (plus an undocumented -n flag to handle old files without headers),
  114.  * added -f flag to force overwriting of possibly existing destination file,
  115.  * otherwise the user is prompted for a response.  Will tack on a .Z to a
  116.  * filename if it doesn't have one when decompressing.  Will only replace
  117.  * file if it was compressed.
  118.  *
  119.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  120.  * Removed scanargs(), getopt(), added .Z extension and unlimited number of
  121.  * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  122.  * (-D -d -v -b 12), or combination thereof.  Modes and other status is
  123.  * copied with copystat().  -O bug for 4.2 seems to have disappeared with
  124.  * 1.8.
  125.  *
  126.  * Revision 1.8  84/08/09  23:15:00  joe
  127.  * Made it compatible with vax version, installed jim's fixes/enhancements
  128.  *
  129.  * Revision 1.6  84/08/01  22:08:00  joe
  130.  * Sped up algorithm significantly by sorting the compress chain.
  131.  *
  132.  * Revision 1.5  84/07/13  13:11:00  srd
  133.  * Added C version of vax asm routines.  Changed structure to arrays to
  134.  * save much memory.  Do unsigned compares where possible (faster on
  135.  * Perkin-Elmer)
  136.  *
  137.  * Revision 1.4  84/07/05  03:11:11  thomas
  138.  * Clean up the code a little and lint it.  (Lint complains about all
  139.  * the regs used in the asm, but I'm not going to "fix" this.)
  140.  *
  141.  * Revision 1.3  84/07/05  02:06:54  thomas
  142.  * Minor fixes.
  143.  *
  144.  * Revision 1.2  84/07/05  00:27:27  thomas
  145.  * Add variable bit length output.
  146.  *
  147.  */
  148.  
  149. #include <stdio.h>
  150. #include <ctype.h>
  151. #include <signal.h>
  152. #include <sys/types.h>
  153. #include <sys/stat.h>
  154. #ifndef __ZTC__
  155. #include <malloc.h>
  156. #endif
  157. #ifndef BSD4_2
  158. #include <stdlib.h>
  159. #include <io.h>
  160. #endif
  161. #include <string.h>
  162. #include <fcntl.h>
  163. #ifdef MSDOS
  164. #include <dos.h>
  165. #endif
  166.  
  167. #ifdef PROTO
  168. /*
  169.  * Zortech appears to be missing this prototype, and MSC uses some
  170.  * silly structure as the second arg. Turbo C doesn't support this
  171.  * call at all.
  172.  */
  173. extern int utime(char *path, time_t times[]);
  174. #endif
  175.  
  176. #define BITS        16        /* max number of bits/code */
  177. #define INIT_BITS    9        /* initial number of bits/code */
  178.  
  179. #define MAXCODE(n_bits)        ((code_t)((1L << (n_bits)) - 1))
  180.  
  181. /*
  182.  * Magic numbers which should appear at the beginning of a compressed file.
  183.  */
  184. #define MAGIC0    0x1f
  185. #define MAGIC1    0x9d
  186.  
  187. /*
  188.  * Defines for third byte of header
  189.  */
  190. #define BIT_MASK    0x1f
  191. #define BLOCK_MASK    0x80
  192.  
  193. #if 0
  194. #define CHECK_GAP    10000        /* ratio check interval */
  195. #endif
  196.  
  197. /*
  198.  * the next two codes should not be changed lightly, as they must not
  199.  * lie within the contiguous general code space.
  200.  */ 
  201. #define FIRST    257        /* first free entry */
  202. #define    CLEAR    256        /* table clear output code */
  203.  
  204. #define DE_STACKLEN    8192    /* Size of decoder stack */
  205.  
  206. #define HSIZE    (1L << 16)    /* Size of the hash table. Don't change this */
  207.  
  208. typedef unsigned char    uchar;
  209. typedef unsigned long    ulong;
  210. typedef unsigned short    code_t;
  211. typedef    unsigned short    hash_t;
  212.  
  213. #ifdef PROTO
  214. #define ARGS(x)    x
  215. #else
  216. #define ARGS(x)    ()
  217. #endif
  218.  
  219. void        main ARGS((int argc, char **argv));
  220. void        Usage ARGS((void));
  221. void        version ARGS((void));
  222. void        compress ARGS((void));
  223. void        decompress ARGS((void));
  224. void        copystat ARGS((void));
  225. void        writeerr ARGS((void));
  226. void        cl_hash ARGS((void));
  227. void        putcode ARGS((code_t code));
  228. void        prratio ARGS((long num, long den));
  229. int        ofopen ARGS((char *filename));
  230. int        ifopen ARGS((char *filename));
  231. int        check_magic ARGS((void));
  232. int        need_clear ARGS((void));
  233. void        onintr ARGS(());
  234. void        oops ARGS(());
  235. int        taballoc ARGS((void));
  236. void        clearhash ARGS((void));
  237.  
  238. /*
  239.  * block compression parameters -- after all codes are used up,
  240.  * and compression rate changes, start over.
  241.  */
  242. int        block_compress = BLOCK_MASK;
  243.  
  244. int        maxbits = BITS;        /* user settable max # bits/code */
  245. int        magic = 1;        /* 3-byte magic number header */
  246. int        zcat_flg = 0;        /* Output on stdout */
  247. int        verbose = 0;        /* don't tell me about compression */
  248. int        force = 0;        /* Force overwrite of output file */
  249. int        do_decomp = 0;        /* Decompress rather than compress. */
  250. char        ofname[100];        /* Output file name */
  251. int        foreground;        /* Running in foreground? */
  252. int        exit_stat = 0;        /* Exit status */
  253. uchar        bitbuf[BITS+2];        /* For (dis)assembling code bytes */
  254. int        okunlink;        /* OK for sig handler to unlink output file */
  255. char        *ifname;
  256.  
  257. #ifdef i8088
  258.  
  259. uchar        *de_stack;
  260. uchar far    *charptr1;
  261. uchar far    *codeptrs1[2];
  262. uchar far    *codeptrs2[2];
  263.  
  264. #define de_suffixof(i)    charptr1[i]
  265. #define de_prefixof(i)    (*(code_t far *)&codeptrs1[i&1][i&~1])
  266.  
  267. #define en_hashchar(i)    charptr1[i]
  268. #define en_hashent(i)    (*(code_t far *)&codeptrs1[i&1][i&~1])
  269. #define en_hashcode(i)    (*(code_t far *)&codeptrs2[i&1][i&~1])
  270.  
  271. #ifndef MK_FP
  272. #define MK_FP(seg, ofs) \
  273.     ((void far *)(((ulong)(seg) << 16) | (unsigned)(ofs)))
  274. #endif
  275.  
  276. #define    PARA    16        /* Size of a paragraph */
  277.  
  278. /*
  279.  * Return a segment address which is the segment part of the normalized
  280.  * version of "fp" rounded upwards.
  281.  * I use this on the far pointers returned by "farmalloc". While
  282.  * they are probably already normalized, I have never seen this
  283.  * stated anywhere in the doc's.
  284.  *
  285.  * There is a lot of junk below which would be unecessary if only
  286.  * there were a reasonably compiler independent way of allocating
  287.  * a given number of PARAGRAPHS (like TC's allocmem). I can't find
  288.  * one though.
  289.  */
  290. #define FP_SEGCEIL(fp) \
  291.     (FP_SEG(fp) + (FP_OFF(fp) + PARA - 1)/PARA)
  292.  
  293. /*
  294.  * Allocate space for the tables used in {en,de}coding. These tables
  295.  * reside in the far heap. It may seem inefficient to be using far pointers
  296.  * for the base of these tables, because the offset portion will always be zero.
  297.  * We could just keep the segment address of the base, and then do something
  298.  * like:
  299.  *         *MK_FP(baseseg, offset) = blahblah;
  300.  *
  301.  * whenever we need to access the table. This SHOULD be more efficient,
  302.  * but the compilers do not appear to generate very efficient code in this
  303.  * case. Huge pointers are not used, because they are slow, and because
  304.  * Zortech does not support them.
  305.  */
  306.  
  307. #ifdef MSC
  308. #define farmalloc(n)    halloc(n, 1)
  309. #endif
  310.  
  311. int taballoc()
  312. {
  313.     char far *X;
  314.  
  315.     if (do_decomp) {
  316.         if ((de_stack = malloc(DE_STACKLEN)) == 0)
  317.             return (0);
  318.     }
  319.     else {
  320.         if ((X = farmalloc((HSIZE + PARA) * sizeof(code_t))) == 0)
  321.             return (0);
  322.         codeptrs2[0] = MK_FP(FP_SEGCEIL(X), 0);
  323.         codeptrs2[1] = MK_FP(FP_SEGCEIL(X) + HSIZE/PARA, 0);
  324.     }
  325.  
  326.     if ((X = farmalloc((HSIZE + PARA) * sizeof(char))) == 0)
  327.         return (0);
  328.     charptr1 = MK_FP(FP_SEGCEIL(X), 0);
  329.  
  330.     if ((X = farmalloc((HSIZE + PARA) * sizeof(code_t))) == 0)
  331.         return (0);
  332.     codeptrs1[0] = MK_FP(FP_SEGCEIL(X), 0);
  333.     codeptrs1[1] = MK_FP(FP_SEGCEIL(X) + HSIZE/PARA, 0);
  334.  
  335.     return (1);
  336. }
  337.  
  338. #else
  339.  
  340. uchar    chartab1[HSIZE];
  341. code_t    codetab1[HSIZE];
  342. code_t    codetab2[HSIZE];
  343.  
  344. #define de_suffixof(i)    chartab1[i]
  345. #define de_prefixof(i)    codetab1[i]
  346. #define de_stack    (uchar *)codetab2
  347.  
  348. #define en_hashchar(i)    chartab1[i]
  349. #define en_hashent(i)    codetab1[i]
  350. #define en_hashcode(i)    codetab2[i]
  351.  
  352. #endif
  353.  
  354. void Usage()
  355. {
  356.     fprintf(stderr, "Usage: compress [-dfvcVnC] [-b maxbits] [file ...]\n");
  357.     fprintf(stderr, "    -V => print Version\n");
  358.     fprintf(stderr, "    -d => decompress\n");
  359.     fprintf(stderr, "    -v => verbose\n");
  360.     fprintf(stderr, "    -f => force overwrite of output file\n");
  361.     fprintf(stderr, "    -n => no header: useful to uncompress old files\n");
  362.     fprintf(stderr, "    -b maxbits => maxbits. Default %d\n", BITS);
  363.     fprintf(stderr, "    -c => cat all output to stdout\n");
  364.     fprintf(stderr, "    -C => generate output compatible with compress 2.0.\n");
  365. }
  366.  
  367. /*****************************************************************
  368.  * TAG( main )
  369.  *
  370.  * Algorithm from "A Technique for High Performance Data Compression",
  371.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  372.  *
  373.  * Usage: compress [-dfvc] [-b bits] [file ...]
  374.  * Inputs:
  375.  *    -d:        If given, decompression is done instead.
  376.  *
  377.  *      -c:         Write output on stdout, don't remove original.
  378.  *
  379.  *      -b:         Parameter limits the max number of bits/code.
  380.  *
  381.  *    -f:        Forces output file to be generated, even if one already
  382.  *            exists, and even if no space is saved by compressing.
  383.  *            If -f is not used, the user will be prompted if stdin is
  384.  *            a tty, otherwise, the output file will not be overwritten.
  385.  *
  386.  *      -v:        Write compression statistics
  387.  *
  388.  *     file ...:   Files to be compressed.  If none specified, stdin
  389.  *            is used.
  390.  * Outputs:
  391.  *    file.Z:        Compressed form of file with same mode, owner, and utimes
  392.  *     or stdout   (if stdin used as input)
  393.  *
  394.  * Assumptions:
  395.  *    When filenames are given, replaces with the compressed version
  396.  *    (.Z suffix) only if the file decreases in size.
  397.  * Algorithm:
  398.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  399.  * substrings and replaces them with a variable size code.  This is
  400.  * deterministic, and can be done on the fly.  Thus, the decompression
  401.  * procedure needs no input table, but tracks the way the table was built.
  402.  */
  403.  
  404. #ifdef __ZTC__
  405. #include <int.h>
  406. int silly_nonsense(struct INT_DATA *foo) {raise(SIGINT); return 1;}
  407. #endif
  408.  
  409. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  410.  
  411. void main(argc, argv)
  412. int argc;
  413. char **argv;
  414. {
  415.     char tempname[100], *cp;
  416.  
  417.     if (signal(SIGINT, SIG_IGN) != SIG_IGN) {
  418.         signal(SIGINT, onintr);
  419. #ifdef __ZTC__
  420.         /*
  421.          * The "signal" call above isn't good enough for Zortech
  422.          */
  423.         int_intercept(0x23, silly_nonsense, 256);
  424. #endif
  425. #ifdef SIGSEGV
  426.         signal(SIGSEGV, oops);
  427. #endif
  428.         if (isatty(2))
  429.             foreground = 1;
  430.     }
  431.  
  432. #ifndef MSDOS
  433.     if ((cp = strrchr(argv[0], '/')) != 0)
  434.         cp++;
  435.     else
  436.         cp = argv[0];
  437. #else
  438.     for (cp = argv[0]; *cp; cp++)
  439.         if (*cp == '/' || *cp == '\\')
  440.             argv[0] = cp + 1;
  441.     cp = strlwr(argv[0]);
  442. #endif
  443.     /* Limited to 8 char filenames under DOS */
  444.     if (strncmp(cp, "uncompress", 8) == 0)
  445.         do_decomp = 1;
  446.     else if (strncmp(cp, "zcat", 4) == 0) {
  447.         do_decomp = 1;
  448.         zcat_flg = 1;
  449.     }
  450.  
  451. #ifdef BSD4_2
  452.     /* 4.2BSD dependent - take it out if not */
  453.     setlinebuf(stderr);
  454. #endif /* BSD4_2 */
  455.  
  456.     for (argc--, argv++; argc > 0 && **argv == '-'; argc--, argv++) {
  457.         while (*++(*argv)) {    /* Process all flags in this arg */
  458.             switch (**argv) {
  459.             case 'V':
  460.                 version();
  461.                 break;
  462.             case 'v':
  463.                 verbose = 1;
  464.                 break;
  465.             case 'd':
  466.                 do_decomp = 1;
  467.                 break;
  468.             case 'f':
  469.             case 'F':
  470.                 force = 1;
  471.                 break;
  472.             case 'n':
  473.                 magic = 0;
  474.                 break;
  475.             case 'C':
  476.                 block_compress = 0;
  477.                 break;
  478.             case 'b':
  479.                 if (!ARGVAL()) {
  480.                     fprintf(stderr, "Missing maxbits\n");
  481.                     Usage();
  482.                     exit(1);
  483.                 }
  484.                 maxbits = atoi(*argv);
  485.                 goto nextarg;
  486.             case 'c':
  487.                 zcat_flg = 1;
  488.                 break;
  489.             case 'q':
  490.                 verbose = 0;
  491.                 break;
  492.             default:
  493.                 fprintf(stderr, "Unknown flag: '%c'; ", **argv);
  494.                 Usage();
  495.                 exit(1);
  496.             }
  497.         }
  498. nextarg:;
  499.     }
  500.  
  501. #ifdef i8088
  502.     if (! taballoc()) {
  503.         fprintf(stderr, "compress: out of memory\n");
  504.         exit(1);
  505.     }
  506. #endif
  507.     /*
  508.      * If no filename args, do standard input.
  509.      */
  510.     if (argc <= 0) {
  511.         if (! ifopen((char *)0) || ! ofopen((char *)0))
  512.             exit(1);
  513.  
  514.         ifname = "stdin";
  515.  
  516.         if (do_decomp) {
  517.             if (!check_magic())
  518.                 exit(1);
  519.             decompress();
  520.         }
  521.         else {
  522.             compress();
  523.             if (verbose)
  524.                 putc('\n', stderr);
  525.         }
  526.         exit(exit_stat);
  527.     }
  528.  
  529.     while (--argc >= 0) {
  530.         char *suf;
  531.  
  532.         ifname = *argv++;
  533.         suf = strrchr(ifname, '.');
  534.  
  535.         exit_stat = 0;
  536.         okunlink = 0;
  537.  
  538.         if (do_decomp) {        /* DECOMPRESSION */
  539.             if (!suf || (strcmp(suf, ".Z") && strcmp(suf, ".z"))) {
  540.                 strcpy(tempname, ifname);
  541.                 strcat(tempname, ".Z");
  542.                 ifname = tempname;
  543.             }
  544.             if (! ifopen(ifname) || !check_magic())
  545.                 continue;
  546.             if (zcat_flg)
  547.                 ofname[0] = '\0';
  548.             else {
  549.                 strcpy(ofname, ifname);
  550.                 ofname[strlen(ifname) - 2] = '\0';
  551.             }
  552.             if (!ofopen(ofname))
  553.                 continue;
  554.             if (!zcat_flg && verbose)
  555.                 fprintf(stderr, "%s: ", ifname);
  556.             decompress();
  557.         }
  558.         else {                /* COMPRESSION */
  559.             if (suf && (!strcmp(suf, ".Z") || !strcmp(suf, ".z"))) {
  560.                 fprintf(stderr, "%s: already has .Z suffix -- no change\n",
  561.                     ifname);
  562.                 continue;
  563.             }
  564.             if (! ifopen(ifname))
  565.                 continue;
  566.             if (zcat_flg)
  567.                 ofname[0] = 0;
  568.             else {
  569.                 strcpy(ofname, ifname);
  570. #ifndef MSDOS    /* We'll let ofopen do the complaining */
  571. #ifndef BSD4_2
  572.                 if ((cp = strrchr(ofname, '/')) != NULL)
  573.                     cp++;
  574.                 else
  575.                     cp = ofname;
  576.                 if (strlen(cp) > 12) {
  577.                     fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
  578.                     continue;
  579.                 }
  580. #endif
  581. #endif
  582.                 strcat(ofname, ".Z");
  583.             }
  584.             if (! ofopen(ofname))
  585.                 continue;
  586.             if (! zcat_flg && verbose)
  587.                 fprintf(stderr, "%s: ", ifname);
  588.             compress();
  589.         }
  590.  
  591.         if (! zcat_flg) {
  592.             copystat();
  593.             if ((exit_stat == 1) || verbose)
  594.                 putc('\n', stderr);
  595.         }
  596.     }
  597.     exit(exit_stat);
  598. }
  599.  
  600. /*
  601.  * compress stdin to stdout
  602.  *
  603.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  604.  * prefix code / next character combination.  We do a variant of Knuth's
  605.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  606.  * secondary probe.  Here, the modular division first probe is gives way
  607.  * to a faster exclusive-or manipulation.  Also do block compression with
  608.  * an adaptive reset, whereby the code table is cleared when the compression
  609.  * ratio decreases, but after the table fills.  The variable-length output
  610.  * codes are re-sized at this point, and a special CLEAR code is generated
  611.  * for the decompressor.  Late addition:  construct the table according to
  612.  * file size for noticeable speed improvement on small files.  Please direct
  613.  * questions about this implementation to ames!jaw.
  614.  *
  615.  * Secondary hash function changed slightly for DOS. Hash table used to be
  616.  * > 64K. This is slow on a 16 bit machine because it means long arithmetic,
  617.  * and more complicated addressing of tables in the far address space.
  618.  * We now restrict the table size to 64K, and, so that the table does
  619.  * not overfill, restrict the codes that we will generate to MAXMAXCODE.
  620.  * This causes slightly poorer compression in some cases, but, interestingly
  621.  * enough, also causes better compression ratios in certain other cases.
  622.  * Yes, this is all compatible with other compresses.
  623.  */
  624. static long    in_count;        /* length of input */
  625. static long    out_count;        /* length of compressed output */
  626. static long    ratio;            /* in_count/out_count * 256 */
  627. static int    n_bits;            /* number of bits/code */
  628. static int    n_bits8;        /* bits/code times 8 */
  629. static int    bitoffset;        /* Offset into bitbuf */
  630.  
  631. #define NOENT        ((code_t)0xffff)
  632. #define MAXMAXCODE    ((code_t)0xf000)
  633.  
  634. /*
  635.  * Clear out the hash table. We try to do this as quickly as possible, because
  636.  * it's running time dominates for small files. For big files, it doesn't matter
  637.  * much because it doesn't get called often. Now I understand why the original
  638.  * had a variable size hash table.
  639.  */
  640. void clearhash()
  641. {
  642. #ifdef i8088
  643.     register unsigned i;
  644.     code_t far *hp;
  645.  
  646.     hp = (code_t far *)codeptrs1[0];
  647.     i = (unsigned)(HSIZE/2);
  648.     do
  649.         *hp++ = NOENT;
  650.     while (--i > 0);
  651.  
  652.     hp = (code_t far *)codeptrs1[1];
  653.     i = (unsigned)(HSIZE/2);
  654.     do
  655.         *hp++ = NOENT;
  656.     while (--i > 0);
  657. #else
  658.     /*
  659.      * WARNING: assumes that NOENT == 0xffff
  660.      */
  661.     memset((char *)codetab1, 0xff, HSIZE*sizeof(code_t));
  662. #endif
  663. }
  664.  
  665. /*
  666.  * Compress stdin to stdout.
  667.  */
  668. void compress()
  669. {
  670.     register hash_t    i;
  671.     register code_t    ent;
  672.     hash_t        disp;
  673.     int        c;
  674.     code_t        freecode;    /* first unused entry */
  675.     code_t        maxcode;    /* maximum code, given n_bits */
  676.     code_t        maxmaxcode;
  677.     code_t        k;
  678. #ifdef CHECK_GAP
  679.     long        checkpoint = 0;
  680. #endif
  681.  
  682.     if (maxbits < INIT_BITS)
  683.         maxbits = INIT_BITS;
  684.     if (maxbits > BITS)
  685.         maxbits = BITS;
  686.  
  687.     if (magic) {
  688.         putchar(MAGIC0); putchar(MAGIC1);
  689.         putchar(maxbits | block_compress);
  690.         if (ferror(stdout))
  691.             writeerr();
  692.     }
  693.  
  694.     bitbuf[bitoffset = 0] = 0;
  695.     out_count = 3;            /* includes 3-byte header mojo */
  696.     ratio = 0;
  697.     in_count = 1;
  698.  
  699.     n_bits = INIT_BITS;
  700.     n_bits8 = INIT_BITS << 3;
  701.     maxcode = MAXCODE(INIT_BITS);
  702.     maxmaxcode = MAXCODE(maxbits);
  703.     if (maxmaxcode > MAXMAXCODE)
  704.         maxmaxcode = MAXMAXCODE;
  705.  
  706.     freecode = ((block_compress) ? FIRST : 256);
  707.  
  708.     clearhash();
  709.  
  710.     ent = getchar();
  711.  
  712.     while ((c = getchar()) != EOF) {
  713.         in_count++;
  714.  
  715.         i = (hash_t)(c << 8) ^ ent;        /* xor hashing */
  716.  
  717.         if ((k = en_hashent(i)) == ent && en_hashchar(i) == (uchar)c) {
  718.             ent = en_hashcode(i);
  719.             goto Continue;
  720.         }
  721.  
  722.         if (k != NOENT) {
  723.             /*
  724.              * New secondary hash for 64K table.
  725.              * Experiment shows that the shift by 6 works well.
  726.              * Beats me why. "disp" must be relatively
  727.              * prime to the table size. Since the table size is a
  728.              * power of 2, this means "disp" must be odd.
  729.              *
  730.              * Note that we do not do a range check before doing
  731.              * "i -= disp". It is assumed that the hash table size
  732.              * (HSIZE) is 64K, and that the type "hash_t" (which
  733.              * is unsigned short) is 16 bits. Thus it is impossible
  734.              * for "i" to be out of range. On a machine with something
  735.              * other than 16 bit shorts, this would have to change.
  736.              */
  737.             disp = ((hash_t)(c << 6) ^ ent) | 1;
  738.             do {
  739.                 i -= disp;
  740.                 if ((k = en_hashent(i)) == ent &&
  741.                     en_hashchar(i) == (uchar)c) {
  742.                     ent = en_hashcode(i);
  743.                     goto Continue;
  744.                 }
  745.             } while (k != NOENT);
  746.         }
  747.  
  748.         putcode(ent);
  749.  
  750.         if (freecode <= maxmaxcode) {
  751.             /*
  752.              * Add the new entry.
  753.              */
  754.             en_hashchar(i) = (uchar)c;
  755.             en_hashent(i) = ent;
  756.             en_hashcode(i) = freecode;
  757.  
  758.             /*
  759.              * If the next entry is going to be too big for the
  760.              * code size, then increase it, if possible.
  761.              */
  762.             if (freecode++ > maxcode) {
  763.                 while (bitoffset)
  764.                     putcode(0);
  765.                 ++n_bits;
  766.                 n_bits8 += 8;
  767.                 maxcode = MAXCODE(n_bits);
  768.             }
  769.         }
  770. #ifdef CHECK_GAP
  771.         else if (in_count >= checkpoint && block_compress) {
  772.             checkpoint = in_count + CHECK_GAP;
  773.             if (need_clear()) {
  774. #else
  775.         else if (block_compress) {
  776.             if (1) {
  777. #endif
  778.                 putcode(CLEAR);
  779.                 while (bitoffset > 0)
  780.                     putcode(0);
  781.                 clearhash();
  782.                 freecode = FIRST;
  783.                 maxcode = MAXCODE(INIT_BITS);
  784.                 n_bits = INIT_BITS;
  785.                 n_bits8 = n_bits << 3;
  786.             }
  787.         }
  788.         ent = c;
  789. Continue:;
  790.     }
  791.     /*
  792.      * Put out the final code.
  793.      */
  794.     putcode(ent);
  795.  
  796.     /*
  797.      * At EOF, write the rest of the buffer.
  798.      */
  799.     if (bitoffset > 0)
  800.         fwrite(bitbuf, 1, (bitoffset + 7) / 8, stdout);
  801.     out_count += (bitoffset + 7) / 8;
  802.     fflush(stdout);
  803.     if (ferror(stdout))
  804.         writeerr();
  805.  
  806.     /*
  807.      * Print out stats on stderr
  808.      */
  809.     if (! zcat_flg && verbose) {
  810.         fprintf(stderr, "Compression: ");
  811.         prratio(in_count - out_count, in_count);
  812.     }
  813.     if (out_count > in_count)    /* exit(2) if no savings */
  814.         exit_stat = 2;
  815. }
  816.  
  817. /*
  818.  * Output the given code. Assumes that chars are 8 bits.
  819.  * "n_bits" output bytes (containing 8 codes) are assembled
  820.  * in in "bitbuf", and then written out.
  821.  */
  822. void putcode(code)
  823. code_t code;
  824. {
  825.     register int i;
  826.     register uchar *bp;
  827.  
  828.     bp = &bitbuf[(bitoffset >> 3)];
  829.     i = bitoffset & 7;
  830.     bp[0] |= (uchar)(code << i);
  831.     bp[1] = (uchar)(code >>= (8 - i));
  832.     bp[2] = (uchar)(code >> 8);
  833.  
  834.     if ((bitoffset += n_bits) == n_bits8) {
  835.         bp = bitbuf;
  836.         i = n_bits;
  837.         out_count += i;
  838.         do
  839.             putchar(*bp++);
  840.         while (--i);
  841.         bitbuf[bitoffset = 0] = 0;
  842.     }
  843. }
  844.  
  845. #ifdef CHECK_GAP
  846. /*
  847.  * Compute the current compression ratio, and return non-zero if
  848.  * it is has decreased since the last we checked.
  849.  *
  850.  * Don't use this anymore. Whenever the hash table fills,
  851.  * we send a CLEAR immediately (if block_compress). This is faster,
  852.  * and doesn't appear to affect the compression ratio much.
  853.  */
  854. int need_clear()
  855. {
  856.     long rat;
  857.  
  858.     if (in_count > 0x007fffffL) {        /* shift will overflow */
  859.         rat = out_count >> 8;
  860.         if (rat == 0)                 /* Don't divide by zero */
  861.             rat = 0x7fffffffL;
  862.         else
  863.             rat = in_count / rat;
  864.     } else
  865.         rat = (in_count << 8) / out_count;
  866.  
  867.     if (rat > ratio) {
  868.         ratio = rat;
  869.         return (0);
  870.     }
  871.     else {
  872.         ratio = 0;
  873.         return (1);
  874.     }
  875. }
  876. #endif
  877.  
  878. /*
  879.  * Decompress stdin to stdout. This code assumes that chars are 8 bits.
  880.  */
  881. void decompress()
  882. {
  883.     register uchar    *stackp;
  884.     register code_t    code;
  885.     code_t        oldcode, incode;
  886.     code_t        codemask;
  887.     code_t        freecode;        /* first unused entry */
  888.     code_t        maxcode;        /* maximum code, given n_bits */
  889.     code_t        maxmaxcode;
  890.     int        finchar;
  891.     int        size;            /* #bits in bitbuf */
  892.     int        bitoff;            /* Offset into bitbuf */
  893.     int        n_bits;            /* number of bits/code */
  894. #ifndef i8088
  895.     register uchar    *bp;
  896. #endif
  897.  
  898.     n_bits = INIT_BITS;
  899.     maxcode = MAXCODE(INIT_BITS) - 1;
  900.     codemask = MAXCODE(INIT_BITS);
  901.     freecode = ((block_compress) ? FIRST : 256) - 1;
  902.     maxmaxcode = MAXCODE(maxbits);
  903.  
  904.     /*
  905.      * Read the first code into "oldcode"
  906.      */
  907.     if ((size = fread(bitbuf, 1, n_bits, stdin)) <= 0)
  908.         return;
  909.     size = (size << 3) - (n_bits - 1);
  910.     oldcode = (bitbuf[0] | (bitbuf[1] << 8)) & codemask;
  911.     bitoff = n_bits;
  912.  
  913.     /*
  914.      * First code must be 8 bits == char. Write it, and die
  915.      * if it can't be written.
  916.      */
  917.     putchar(finchar = oldcode);
  918.     if (ferror(stdout))
  919.         writeerr();
  920.  
  921.     stackp = de_stack;
  922.  
  923.     for ( ; ; ) {
  924.         if (bitoff >= size) {
  925.             if ((size = fread(bitbuf, 1, n_bits, stdin)) <= 0)
  926.                 break;
  927.             /* Round size down to integral number of codes */
  928.             size = (size << 3) - (n_bits - 1);
  929.             bitoff = 0;
  930.         }
  931.         /*
  932.          * Read the next code into "code". On the 8088,
  933.          * a slight speedup is possible because it has the right byte
  934.          * order, and no alignment restrictions.
  935.          */
  936. #ifdef i8088
  937.         code = ((code_t)(*(long *)&bitbuf[(bitoff >> 3)] >>
  938.              (bitoff&7))) & codemask;
  939. #else
  940.         bp = &bitbuf[(bitoff >> 3)];
  941.         code = (code_t)(((bp[0] | (code_t)bp[1] << 8) |
  942.              (ulong)bp[2] << 16) >> (bitoff & 7)) & codemask;
  943. #endif
  944.         bitoff += n_bits;
  945.  
  946.         if ((code == CLEAR) && block_compress) {
  947.             n_bits = INIT_BITS;
  948.                 maxcode = MAXCODE(INIT_BITS) - 1;
  949.             codemask = MAXCODE(INIT_BITS);
  950.             freecode = (FIRST - 1) - 1;
  951.             size = 0;
  952.             continue;
  953.         }
  954.         incode = code;
  955.  
  956.         /*
  957.          * Special case for KwKwK string.
  958.          */
  959.         if (code > freecode) {
  960.             if (code != freecode + 1)
  961.                 oops();
  962.                 *stackp++ = (uchar)finchar;
  963.             code = oldcode;
  964.         }
  965.  
  966.         /*
  967.          * Generate output characters in reverse order
  968.          */
  969.         while (code >= 256) {
  970.             *stackp++ = de_suffixof(code);
  971.             code = de_prefixof(code);
  972.         }
  973.  
  974.         /*
  975.          * And write them out in the forward order.
  976.          */
  977.         putchar(finchar = code);
  978.         for (code = (stackp - de_stack) + 1; --code != 0; )
  979.             putchar(*--stackp);
  980.  
  981.         /*
  982.          * Generate the new entry.
  983.          */
  984.         if (freecode < maxmaxcode) {
  985.             if (++freecode > maxcode) {
  986.                 if (++n_bits == maxbits)
  987.                     maxcode = maxmaxcode;
  988.                 else
  989.                     maxcode = MAXCODE(n_bits) - 1;
  990.                 size = 0;
  991.                 codemask = MAXCODE(n_bits);
  992.             }
  993.             de_prefixof(freecode) = oldcode;
  994.             de_suffixof(freecode) = (uchar)finchar;
  995.         } 
  996.         /*
  997.          * Remember previous code.
  998.          */
  999.         oldcode = incode;
  1000.     }
  1001.     fflush(stdout);
  1002.     if (ferror(stdout))
  1003.         writeerr();
  1004. }
  1005.  
  1006. /*
  1007.  * Check a compressed file to make sure it has the proper magic number
  1008.  * at the beginning. Also read the third byte to determine "maxbits",
  1009.  * and "block_compress".
  1010.  */
  1011. int check_magic()
  1012. {
  1013.     if (! magic)
  1014.         return (1);
  1015.     if ((getchar() != MAGIC0) || (getchar() != MAGIC1)) {
  1016.         fprintf(stderr, "%s: not in compressed format\n", ifname);
  1017.         return (0);
  1018.     }
  1019.     maxbits = getchar();    /* set -b from file */
  1020.     block_compress = maxbits & BLOCK_MASK;
  1021.     maxbits &= BIT_MASK;
  1022.     if (maxbits > BITS) {
  1023.         fprintf(stderr,
  1024.            "%s: compressed with %d bits, can only handle %d bits\n",
  1025.             ifname, maxbits, BITS);
  1026.         return (0);
  1027.     }
  1028.     return (1);
  1029. }
  1030.  
  1031. void writeerr()
  1032. {
  1033.     perror(ofname);
  1034.     fclose(stdout);
  1035.     unlink(ofname);
  1036.     exit(1);
  1037. }
  1038.  
  1039. /*
  1040.  * Copy the permissions and file times from the input file to the
  1041.  * output.
  1042.  */
  1043. void copystat()
  1044. {
  1045.     struct stat statbuf;
  1046.     int mode;
  1047.     void (* ss)();
  1048. #ifndef __TURBOC__
  1049.     time_t timep[2];
  1050. #else
  1051.     struct ftime filetime;
  1052.     int fd;
  1053. #endif
  1054.  
  1055.     fclose(stdout);
  1056.     if (stat(ifname, &statbuf)) {        /* Get stat on input file */
  1057.         perror(ifname);
  1058.         return;
  1059.     }
  1060.     if ((statbuf.st_mode & S_IFMT) != S_IFREG) {
  1061.         if (! verbose)
  1062.                 fprintf(stderr, "%s: ", ifname);
  1063.         fprintf(stderr, " -- not a regular file: unchanged");
  1064.         exit_stat = 1;
  1065.     }
  1066.     else if (statbuf.st_nlink > 1) {
  1067.         if (! verbose)
  1068.             fprintf(stderr, "%s: ", ifname);
  1069.         fprintf(stderr, " -- has %d other links: unchanged",
  1070.             statbuf.st_nlink - 1);
  1071.         exit_stat = 1;
  1072.     }
  1073.     else if (exit_stat == 2 && !force) { /* No compression: remove file.Z */
  1074.         if (verbose)
  1075.             fprintf(stderr, " -- file unchanged");
  1076.     }
  1077.     else {            /* ***** Successful Compression ***** */
  1078.         exit_stat = 0;
  1079.         mode = statbuf.st_mode & 07777;
  1080. #ifndef __ZTC__
  1081.         if (chmod(ofname, mode))        /* Copy modes */
  1082.             perror(ofname);
  1083. #endif
  1084. #ifndef MSDOS
  1085.         chown(ofname, statbuf.st_uid, statbuf.st_gid);    /* Copy ownership */
  1086. #endif
  1087. #ifndef __TURBOC__
  1088.         timep[0] = statbuf.st_atime;
  1089.         timep[1] = statbuf.st_mtime;
  1090.         utime(ofname, timep);
  1091. #else
  1092.         if ((fd = open(ofname, O_RDONLY)) >= 0) {
  1093.             if (getftime(fileno(stdin), &filetime) == 0)
  1094.                 setftime(fd, &filetime);
  1095.             close(fd);
  1096.         }
  1097. #endif
  1098.         fclose(stdin);
  1099.         ss = signal(SIGINT, SIG_IGN);
  1100.         okunlink = 0;
  1101.         /* ^C here would leave both input, and output files around */
  1102.         if (unlink(ifname))    /* Remove input file */
  1103.             perror(ifname);
  1104.         signal(SIGINT, ss);
  1105.         if (verbose)
  1106.             fprintf(stderr, " -- replaced with %s", ofname);
  1107.         return;        /* Successful return */
  1108.     }
  1109.  
  1110.     /* Unsuccessful return -- one of the tests failed */
  1111.  
  1112.     if (unlink(ofname))
  1113.         perror(ofname);
  1114. }
  1115.  
  1116. void onintr()
  1117. {
  1118.     fclose(stdout);
  1119.     if (okunlink)
  1120.         unlink(ofname);
  1121.     exit(1);
  1122. }
  1123.  
  1124. void oops()    /* wild pointer -- assume bad input */
  1125. {
  1126.     if (do_decomp) 
  1127.         fprintf (stderr, "uncompress: %s is corrupt.\n", ifname);
  1128.     fclose(stdout);
  1129.     if (okunlink)
  1130.         unlink(ofname);
  1131.     exit(1);
  1132. }
  1133.  
  1134. void prratio(num, den)
  1135. long int num, den;
  1136. {
  1137.     register int q;                /* Doesn't need to be long */
  1138.  
  1139.     if (num > 214748L)            /* 2147483647/10000 */
  1140.         q = (int)(num / (den / 10000L));
  1141.     else
  1142.         q = (int)(10000L * num / den);    /* Long calculations, though */
  1143.     if (q < 0) {
  1144.         putc('-', stderr);
  1145.         q = -q;
  1146.     }
  1147.     fprintf(stderr, "%d.%02d%%", q / 100, q % 100);
  1148. }
  1149.  
  1150. void version()
  1151. {
  1152.     fprintf(stderr, "%s\n", rcs_ident);
  1153.     fprintf(stderr, "BITS = %d\n", BITS);
  1154. }
  1155.  
  1156. /*
  1157.  * Open the file "ofname" for binary output with possible check
  1158.  * for overwrite. If all goes well, return non-zero, else zero.
  1159.  */
  1160. int ofopen(filename)
  1161. char *filename;
  1162. {
  1163.     static char IOoutbuf[8192];
  1164.     struct stat statbuf;
  1165.  
  1166.     if (filename && !*filename)
  1167.         filename = 0;
  1168.  
  1169.     /*
  1170.      * Check for overwrite of existing file
  1171.      */
  1172.     if (filename && !force && stat(filename, &statbuf) == 0) {
  1173.         char response[2];
  1174.         response[0] = 'n';
  1175.         fprintf(stderr, "%s already exists;", filename);
  1176.         if (foreground) {
  1177.             fprintf(stderr, " do you wish to overwrite %s (y or n)? ", filename);
  1178.             fflush(stderr);
  1179.             read(2, response, 2);
  1180.             while (response[1] != '\n') {
  1181.                 if (read(2, response+1, 1) < 0)    { /* Ack! */
  1182.                     perror("stderr");
  1183.                     break;
  1184.                 }
  1185.             }
  1186.         }
  1187.         if (response[0] != 'y') {
  1188.             fprintf(stderr, "\tnot overwritten\n");
  1189.             return (0);
  1190.         }
  1191.     }
  1192.  
  1193.     okunlink = 1;
  1194.     /*
  1195.      * Open the output file.
  1196.      */
  1197.     if (filename && !freopen(filename, "wb", stdout)) {
  1198.         perror(filename);
  1199.         return (0);
  1200.     }
  1201. #ifdef O_BINARY
  1202.     setmode(fileno(stdout), O_BINARY);
  1203. #else
  1204. #ifdef __ZTC__
  1205.     /*
  1206.      * I'm sure there must be a better way in Zortech C to change the
  1207.      * mode of an already opened file, but I can't find it. It doesn't
  1208.      * have a "setmode" call it seems.
  1209.      */
  1210.     stdout->_flag &= ~_IOTRAN;
  1211. #endif
  1212. #endif
  1213.     setvbuf(stdout, IOoutbuf, _IOFBF, sizeof(IOoutbuf));
  1214.     return (1);
  1215. }
  1216.  
  1217. ifopen(filename)
  1218. char *filename;
  1219. {
  1220.     static char IOinbuf[8192];
  1221.  
  1222.     if (filename && !freopen(filename, "rb", stdin)) {
  1223.         perror(filename);
  1224.         return (0);
  1225.     }
  1226. #ifdef O_BINARY
  1227.     setmode(fileno(stdin), O_BINARY);
  1228. #else
  1229. #ifdef __ZTC__
  1230.     stdin->_flag &= ~_IOTRAN;
  1231. #endif
  1232. #endif
  1233.     setvbuf(stdin, IOinbuf, _IOFBF, sizeof(IOinbuf));
  1234.     return (1);
  1235. }
  1236.