Home | History | Annotate | Download | only in compress
      1 /*
      2  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
      3  * Use is subject to license terms.
      4  */
      5 
      6 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
      7 /*	  All Rights Reserved  	*/
      8 
      9 
     10 /*
     11  * Copyright (c) 1986 Regents of the University of California.
     12  * All rights reserved.  The Berkeley software License Agreement
     13  * specifies the terms and conditions for redistribution.
     14  */
     15 
     16 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     17 
     18 /*
     19  * Compress - data compression program
     20  */
     21 #define	min(a, b)	((a > b) ? b : a)
     22 
     23 /*
     24  * machine variants which require cc -Dmachine:  pdp11, z8000, pcxt
     25  */
     26 
     27 /*
     28  * Set USERMEM to the maximum amount of physical user memory available
     29  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
     30  * for compression.
     31  *
     32  * SACREDMEM is the amount of physical memory saved for others; compress
     33  * will hog the rest.
     34  */
     35 #ifndef SACREDMEM
     36 #define	SACREDMEM	0
     37 #endif
     38 
     39 #ifndef USERMEM
     40 #define	USERMEM 	450000	/* default user memory */
     41 #endif
     42 
     43 #ifdef USERMEM
     44 #if USERMEM >= (433484+SACREDMEM)
     45 #define	PBITS	16
     46 #else
     47 #if USERMEM >= (229600+SACREDMEM)
     48 #define	PBITS	15
     49 #else
     50 #if USERMEM >= (127536+SACREDMEM)
     51 #define	PBITS	14
     52 #else
     53 #if USERMEM >= (73464+SACREDMEM)
     54 #define	PBITS	13
     55 #else
     56 #define	PBITS	12
     57 #endif
     58 #endif
     59 #endif
     60 #endif
     61 #undef USERMEM
     62 #endif /* USERMEM */
     63 
     64 #ifdef PBITS		/* Preferred BITS for this memory size */
     65 #ifndef BITS
     66 #define	BITS PBITS
     67 #endif /* BITS */
     68 #endif /* PBITS */
     69 
     70 #if BITS == 16
     71 #define	HSIZE	69001		/* 95% occupancy */
     72 #endif
     73 #if BITS == 15
     74 #define	HSIZE	35023		/* 94% occupancy */
     75 #endif
     76 #if BITS == 14
     77 #define	HSIZE	18013		/* 91% occupancy */
     78 #endif
     79 #if BITS == 13
     80 #define	HSIZE	9001		/* 91% occupancy */
     81 #endif
     82 #if BITS <= 12
     83 #define	HSIZE	5003		/* 80% occupancy */
     84 #endif
     85 
     86 #define	OUTSTACKSIZE	(2<<BITS)
     87 
     88 /*
     89  * a code_int must be able to hold 2**BITS values of type int, and also -1
     90  */
     91 #if BITS > 15
     92 typedef long int	code_int;
     93 #else
     94 typedef int		code_int;
     95 #endif
     96 
     97 typedef long int	count_int;
     98 typedef long long	count_long;
     99 
    100 typedef	unsigned char	char_type;
    101 
    102 static char_type magic_header[] = { "\037\235" }; /* 1F 9D */
    103 
    104 /* Defines for third byte of header */
    105 #define	BIT_MASK	0x1f
    106 #define	BLOCK_MASK	0x80
    107 /*
    108  * Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
    109  * a fourth header byte(for expansion).
    110  */
    111 #define	INIT_BITS 9			/* initial number of bits/code */
    112 
    113 /*
    114  * compress.c - File compression ala IEEE Computer, June 1984.
    115  */
    116 static char rcs_ident[] =
    117 	"$Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $";
    118 
    119 #include <ctype.h>
    120 #include <signal.h>
    121 #include <sys/param.h>
    122 #include <locale.h>
    123 #include <langinfo.h>
    124 #include <sys/acl.h>
    125 #include <utime.h>
    126 #include <libgen.h>
    127 #include <setjmp.h>
    128 #include <aclutils.h>
    129 #include <libcmdutils.h>
    130 #include "getresponse.h"
    131 
    132 
    133 static int n_bits;			/* number of bits/code */
    134 static int maxbits = BITS;	/* user settable max # bits/code */
    135 static code_int maxcode;	/* maximum code, given n_bits */
    136 			/* should NEVER generate this code */
    137 static code_int maxmaxcode = 1 << BITS;
    138 #define	MAXCODE(n_bits)	((1 << (n_bits)) - 1)
    139 
    140 static count_int htab [OUTSTACKSIZE];
    141 static unsigned short codetab [OUTSTACKSIZE];
    142 
    143 #define	htabof(i)	htab[i]
    144 #define	codetabof(i)	codetab[i]
    145 static code_int hsize = HSIZE; /* for dynamic table sizing */
    146 static off_t	fsize;	/* file size of input file */
    147 
    148 /*
    149  * To save much memory, we overlay the table used by compress() with those
    150  * used by decompress().  The tab_prefix table is the same size and type
    151  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
    152  * get this from the beginning of htab.  The output stack uses the rest
    153  * of htab, and contains characters.  There is plenty of room for any
    154  * possible stack (stack used to be 8000 characters).
    155  */
    156 
    157 #define	tab_prefixof(i)		codetabof(i)
    158 #define	tab_suffixof(i)		((char_type *)(htab))[i]
    159 #define	de_stack		((char_type *)&tab_suffixof(1<<BITS))
    160 #define	stack_max		((char_type *)&tab_suffixof(OUTSTACKSIZE))
    161 
    162 static code_int free_ent = 0; /* first unused entry */
    163 static int newline_needed = 0;
    164 static int didnt_shrink = 0;
    165 static int perm_stat = 0;	/* permanent status */
    166 
    167 static code_int getcode();
    168 
    169 	/* Use a 3-byte magic number header, unless old file */
    170 static int nomagic = 0;
    171 	/* Write output on stdout, suppress messages */
    172 static int zcat_flg = 0;	/* use stdout on all files */
    173 static int zcat_cmd = 0;	/* zcat cmd */
    174 static int use_stdout = 0;	/* set for each file processed */
    175 	/* Don't unlink output file on interrupt */
    176 static int precious = 1;
    177 static int quiet = 1;	/* don't tell me about compression */
    178 
    179 /*
    180  * block compression parameters -- after all codes are used up,
    181  * and compression rate changes, start over.
    182  */
    183 static int block_compress = BLOCK_MASK;
    184 static int clear_flg = 0;
    185 static long int ratio = 0;
    186 #define	CHECK_GAP 10000	/* ratio check interval */
    187 static count_long checkpoint = CHECK_GAP;
    188 /*
    189  * the next two codes should not be changed lightly, as they must not
    190  * lie within the contiguous general code space.
    191  */
    192 #define	FIRST	257	/* first free entry */
    193 #define	CLEAR	256	/* table clear output code */
    194 
    195 static int force = 0;
    196 static char ofname [MAXPATHLEN];
    197 
    198 static int Vflg = 0;
    199 static int vflg = 0;
    200 static int qflg = 0;
    201 static int bflg = 0;
    202 static int Fflg = 0;
    203 static int dflg = 0;
    204 static int cflg = 0;
    205 static int Cflg = 0;
    206 
    207 #ifdef DEBUG
    208 int verbose = 0;
    209 int debug = 0;
    210 #endif /* DEBUG */
    211 
    212 static void (*oldint)();
    213 static int bgnd_flag;
    214 
    215 static int do_decomp = 0;
    216 
    217 static char *progname;
    218 static char *optstr;
    219 /*
    220  * Fix lint errors
    221  */
    222 
    223 static char *local_basename(char *);
    224 
    225 static int  addDotZ(char *, size_t);
    226 
    227 static void Usage(void);
    228 static void cl_block(count_long);
    229 static void cl_hash(count_int);
    230 static void compress(void);
    231 static void copystat(char *, struct stat *, char *);
    232 static void decompress(void);
    233 static void ioerror(void);
    234 static void onintr();
    235 static void oops();
    236 static void output(code_int);
    237 static void prratio(FILE *, count_long, count_long);
    238 static void version(void);
    239 
    240 #ifdef DEBUG
    241 static int in_stack(int, int);
    242 static void dump_tab(void);
    243 static void printcodes(void);
    244 #endif
    245 
    246 /* For error-handling */
    247 
    248 static jmp_buf env;
    249 
    250 /* For input and ouput */
    251 
    252 static FILE *inp;		/* the current input file */
    253 static FILE *infile;		/* disk-based input stream */
    254 static FILE *outp;		/* current output file */
    255 static FILE *outfile;		/* disk-based output stream */
    256 
    257 /* For output() */
    258 
    259 static char buf[BITS];
    260 
    261 static char_type lmask[9] =
    262 	{0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
    263 static char_type rmask[9] =
    264 	{0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
    265 
    266 /* For compress () */
    267 
    268 static int offset;
    269 static count_long bytes_out;	/* length of compressed output */
    270 	/* # of codes output (for debugging) */
    271 
    272 /* For dump_tab() */
    273 
    274 #define	STACK_SIZE	15000
    275 #ifdef DEBUG
    276 code_int sorttab[1<<BITS];	/* sorted pointers into htab */
    277 #endif
    278 
    279 /* Extended system attribute support */
    280 
    281 static int saflg = 0;
    282 
    283 /*
    284  * *************************************************************
    285  * TAG( main )
    286  *
    287  * Algorithm from "A Technique for High Performance Data Compression",
    288  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
    289  *
    290  * Usage: compress [-dfvc/] [-b bits] [file ...]
    291  * Inputs:
    292  *	-d:	    If given, decompression is done instead.
    293  *
    294  *	-c:	    Write output on stdout, don't remove original.
    295  *
    296  *	-b:	    Parameter limits the max number of bits/code.
    297  *
    298  *	-f:	    Forces output file to be generated, even if one already
    299  *		    exists, and even if no space is saved by compressing.
    300  *		    If -f is not used, the user will be prompted if stdin is
    301  *		    a tty, otherwise, the output file will not be overwritten.
    302  *
    303  *	-/	    Copies extended attributes and extended system attributes.
    304  *
    305  *  -v:	    Write compression statistics
    306  *
    307  * 	file ...:   Files to be compressed.  If none specified, stdin
    308  *		    is used.
    309  * Outputs:
    310  *	file.Z:	    Compressed form of file with same mode, owner, and utimes
    311  * 	or stdout   (if stdin used as input)
    312  *
    313  * Assumptions:
    314  * When filenames are given, replaces with the compressed version
    315  * (.Z suffix) only if the file decreases in size.
    316  * Algorithm:
    317  * Modified Lempel-Ziv method (LZW).  Basically finds common
    318  * substrings and replaces them with a variable size code.  This is
    319  * deterministic, and can be done on the fly.  Thus, the decompression
    320  * procedure needs no input table, but tracks the way the table was built.
    321  */
    322 
    323 int
    324 main(int argc, char *argv[])
    325 {
    326 	int overwrite = 0;	/* Do not overwrite unless given -f flag */
    327 	char tempname[MAXPATHLEN];
    328 	char line[LINE_MAX];
    329 	char **filelist, **fileptr;
    330 	char *cp;
    331 	struct stat statbuf;
    332 	struct stat ostatbuf;
    333 	int ch;				/* XCU4 */
    334 	char	*p;
    335 	extern int optind, optopt;
    336 	extern char *optarg;
    337 	int dash_count = 0;		/* times "-" is on cmdline */
    338 
    339 	/* XCU4 changes */
    340 	(void) setlocale(LC_ALL, "");
    341 #if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
    342 #define	TEXT_DOMAIN "SYS_TEST"	/* Use this only if it weren't */
    343 #endif
    344 	(void) textdomain(TEXT_DOMAIN);
    345 
    346 	if (init_yes() < 0) {
    347 		(void) fprintf(stderr, gettext(ERR_MSG_INIT_YES),
    348 		    strerror(errno));
    349 		exit(1);
    350 	}
    351 
    352 	/* This bg check only works for sh. */
    353 	if ((oldint = signal(SIGINT, SIG_IGN)) != SIG_IGN) {
    354 		(void) signal(SIGINT, onintr);
    355 		(void) signal(SIGSEGV, oops);
    356 	}
    357 	bgnd_flag = oldint != SIG_DFL;
    358 
    359 	/* Allocate room for argv + "-" (if stdin needs to be added) */
    360 
    361 	filelist = fileptr = (char **)(malloc((argc + 1) * sizeof (*argv)));
    362 	*filelist = NULL;
    363 
    364 	if ((cp = rindex(argv[0], '/')) != 0) {
    365 		cp++;
    366 	} else {
    367 		cp = argv[0];
    368 	}
    369 
    370 	if (strcmp(cp, "uncompress") == 0) {
    371 		do_decomp = 1;
    372 	} else if (strcmp(cp, "zcat") == 0) {
    373 		do_decomp = 1;
    374 		zcat_cmd = zcat_flg = 1;
    375 	}
    376 
    377 	progname = local_basename(argv[0]);
    378 
    379 	/*
    380 	 * Argument Processing
    381 	 * All flags are optional.
    382 	 * -D = > debug
    383 	 * -V = > print Version; debug verbose
    384 	 * -d = > do_decomp
    385 	 * -v = > unquiet
    386 	 * -f = > force overwrite of output file
    387 	 * -n = > no header: useful to uncompress old files
    388 	 * -b	  maxbits => maxbits.  If -b is specified,
    389 	 *	  then maxbits MUST be given also.
    390 	 * -c = > cat all output to stdout
    391 	 * -C = > generate output compatible with compress 2.0.
    392 	 * if a string is left, must be an input filename.
    393 	 */
    394 #ifdef DEBUG
    395 	optstr = "b:cCdDfFnqvV/";
    396 #else
    397 	optstr = "b:cCdfFnqvV/";
    398 #endif
    399 
    400 	while ((ch = getopt(argc, argv, optstr)) != EOF) {
    401 		/* Process all flags in this arg */
    402 		switch (ch) {
    403 #ifdef DEBUG
    404 			case 'D':
    405 				debug = 1;
    406 				break;
    407 			case 'V':
    408 				verbose = 1;
    409 				version();
    410 				break;
    411 #else
    412 			case 'V':
    413 				version();
    414 				Vflg++;
    415 				break;
    416 #endif /* DEBUG */
    417 			case 'v':
    418 				quiet = 0;
    419 				vflg++;
    420 				break;
    421 			case 'd':
    422 				do_decomp = 1;
    423 				dflg++;
    424 				break;
    425 			case 'f':
    426 			case 'F':
    427 				Fflg++;
    428 				overwrite = 1;
    429 				force = 1;
    430 				break;
    431 			case 'n':
    432 				nomagic = 1;
    433 				break;
    434 			case 'C':
    435 				Cflg++;
    436 				block_compress = 0;
    437 				break;
    438 			case 'b':
    439 				bflg++;
    440 				p = optarg;
    441 				if (!p) {
    442 					(void) fprintf(stderr, gettext(
    443 					    "Missing maxbits\n"));
    444 					Usage();
    445 					exit(1);
    446 				}
    447 				maxbits = strtoul(optarg, &p, 10);
    448 				if (*p) {
    449 					(void) fprintf(stderr, gettext(
    450 					    "Missing maxbits\n"));
    451 					Usage();
    452 					exit(1);
    453 				}
    454 				break;
    455 
    456 			case 'c':
    457 				cflg++;
    458 				zcat_flg = 1;
    459 				break;
    460 			case 'q':
    461 				qflg++;
    462 				quiet = 1;
    463 				break;
    464 			case '/':
    465 				saflg++;
    466 				break;
    467 			default:
    468 				(void) fprintf(stderr, gettext(
    469 				    "Unknown flag: '%c'\n"), optopt);
    470 				Usage();
    471 				exit(1);
    472 		}
    473 	} /* while */
    474 
    475 	/*
    476 	 * Validate zcat syntax
    477 	 */
    478 
    479 	if (zcat_cmd && (Fflg | Cflg | cflg |
    480 	    bflg | qflg | dflg | nomagic)) {
    481 		(void) fprintf(stderr, gettext(
    482 		    "Invalid Option\n"));
    483 		Usage();
    484 		exit(1);
    485 	}
    486 
    487 	/*
    488 	 * Process the file list
    489 	 */
    490 
    491 	for (; optind < argc; optind++) {
    492 		if (strcmp(argv[optind], "-") == 0) {
    493 			dash_count++;
    494 		}
    495 
    496 		*fileptr++ = argv[optind];	/* Build input file list */
    497 		*fileptr = NULL;
    498 	}
    499 
    500 	if (dash_count > 1) {
    501 		(void) fprintf(stderr,
    502 		    gettext("%s may only appear once in the file"
    503 		    " list\n"), "\"-\"");
    504 		exit(1);
    505 	}
    506 
    507 	if (fileptr - filelist == 0) {
    508 		*fileptr++ = "-";
    509 		*fileptr = NULL;
    510 	}
    511 
    512 	if (fileptr - filelist > 1 && cflg && !do_decomp) {
    513 		(void) fprintf(stderr,
    514 		    gettext("compress: only one file may be compressed"
    515 		    " to stdout\n"));
    516 		exit(1);
    517 	}
    518 
    519 	if (maxbits < INIT_BITS)
    520 		maxbits = INIT_BITS;
    521 	if (maxbits > BITS)
    522 		maxbits = BITS;
    523 	maxmaxcode = 1 << maxbits;
    524 
    525 	/* Need to open something to close with freopen later */
    526 
    527 	if ((infile = fopen("/dev/null", "r")) == NULL) {
    528 		(void) fprintf(stderr, gettext("Error opening /dev/null for "
    529 		    "input\n"));
    530 		exit(1);
    531 	}
    532 
    533 	if ((outfile = fopen("/dev/null", "w")) == NULL) {
    534 		(void) fprintf(stderr, gettext("Error opening /dev/null for "
    535 		    "output\n"));
    536 		exit(1);
    537 	}
    538 
    539 	for (fileptr = filelist; *fileptr; fileptr++) {
    540 		int jmpval = 0;
    541 		didnt_shrink = 0;
    542 		newline_needed = 0;
    543 
    544 		if (do_decomp) {
    545 			/* DECOMPRESSION */
    546 
    547 			if (strcmp(*fileptr, "-") == 0) {
    548 				/* process stdin */
    549 				inp = stdin;
    550 				outp = stdout;
    551 				use_stdout = 1;
    552 				*fileptr = "stdin"; /* for error messages */
    553 			} else {
    554 				/* process the named file */
    555 
    556 				inp = infile;
    557 				outp = outfile;
    558 				use_stdout = 0;
    559 
    560 				if (zcat_flg) {
    561 					use_stdout = 1;
    562 					outp = stdout;
    563 				}
    564 
    565 				/* Check for .Z suffix */
    566 
    567 				if (strcmp(*fileptr +
    568 				    strlen(*fileptr) - 2, ".Z") != 0) {
    569 					/* No .Z: tack one on */
    570 
    571 					if (strlcpy(tempname, *fileptr,
    572 					    sizeof (tempname)) >=
    573 					    sizeof (tempname)) {
    574 						(void) fprintf(stderr,
    575 						    gettext("%s: filename "
    576 						    "too long\n"),
    577 						    *fileptr);
    578 						perm_stat = 1;
    579 						continue;
    580 					}
    581 
    582 					if (addDotZ(tempname,
    583 					    sizeof (tempname)) < 0) {
    584 						perm_stat = 1;
    585 						continue;
    586 					}
    587 
    588 					*fileptr = tempname;
    589 				}
    590 
    591 				/* Open input file */
    592 
    593 				if (stat(*fileptr, &statbuf) < 0) {
    594 					perror(*fileptr);
    595 					perm_stat = 1;
    596 					continue;
    597 				}
    598 
    599 				if ((freopen(*fileptr, "r", inp)) == NULL) {
    600 					perror(*fileptr);
    601 					perm_stat = 1;
    602 					continue;
    603 				}
    604 			}
    605 
    606 			/* Check the magic number */
    607 
    608 			if (nomagic == 0) {
    609 				if ((getc(inp) !=
    610 				    (magic_header[0] & 0xFF)) ||
    611 				    (getc(inp) !=
    612 				    (magic_header[1] & 0xFF))) {
    613 					(void) fprintf(stderr, gettext(
    614 					    "%s: not in compressed "
    615 					    "format\n"),
    616 					    *fileptr);
    617 					perm_stat = 1;
    618 					continue;
    619 				}
    620 
    621 				/* set -b from file */
    622 				if ((maxbits = getc(inp)) == EOF &&
    623 				    ferror(inp)) {
    624 					perror(*fileptr);
    625 					perm_stat = 1;
    626 					continue;
    627 				}
    628 
    629 				block_compress = maxbits & BLOCK_MASK;
    630 				maxbits &= BIT_MASK;
    631 				maxmaxcode = 1 << maxbits;
    632 
    633 				if (maxbits > BITS) {
    634 					(void) fprintf(stderr,
    635 					    gettext("%s: compressed "
    636 					    "with %d bits, "
    637 					    "can only handle"
    638 					    " %d bits\n"),
    639 					    *fileptr, maxbits, BITS);
    640 					perm_stat = 1;
    641 					continue;
    642 				}
    643 			}
    644 
    645 			if (!use_stdout) {
    646 				/* Generate output filename */
    647 
    648 				if (strlcpy(ofname, *fileptr,
    649 				    sizeof (ofname)) >=
    650 				    sizeof (ofname)) {
    651 					(void) fprintf(stderr,
    652 					    gettext("%s: filename "
    653 					    "too long\n"),
    654 					    *fileptr);
    655 					perm_stat = 1;
    656 					continue;
    657 				}
    658 
    659 				/* Strip off .Z */
    660 
    661 				ofname[strlen(*fileptr) - 2] = '\0';
    662 			}
    663 		} else {
    664 			/* COMPRESSION */
    665 
    666 			if (strcmp(*fileptr, "-") == 0) {
    667 				/* process stdin */
    668 				inp = stdin;
    669 				outp = stdout;
    670 				use_stdout = 1;
    671 				*fileptr = "stdin"; /* for error messages */
    672 
    673 				/* Use the largest possible hash table */
    674 				hsize =  HSIZE;
    675 			} else {
    676 				/* process the named file */
    677 
    678 				inp = infile;
    679 				outp = outfile;
    680 				use_stdout = 0;
    681 
    682 				if (zcat_flg) {
    683 					use_stdout = 1;
    684 					outp = stdout;
    685 				}
    686 
    687 				if (strcmp(*fileptr +
    688 				    strlen(*fileptr) - 2, ".Z") == 0) {
    689 					(void) fprintf(stderr, gettext(
    690 					    "%s: already has .Z "
    691 					    "suffix -- no change\n"),
    692 					    *fileptr);
    693 					perm_stat = 1;
    694 					continue;
    695 				}
    696 				/* Open input file */
    697 
    698 				if (stat(*fileptr, &statbuf) < 0) {
    699 					perror(*fileptr);
    700 					perm_stat = 1;
    701 					continue;
    702 				}
    703 
    704 				if ((freopen(*fileptr, "r", inp)) == NULL) {
    705 					perror(*fileptr);
    706 					perm_stat = 1;
    707 					continue;
    708 				}
    709 
    710 				fsize = (off_t)statbuf.st_size;
    711 
    712 				/*
    713 				 * tune hash table size for small
    714 				 * files -- ad hoc,
    715 				 * but the sizes match earlier #defines, which
    716 				 * serve as upper bounds on the number of
    717 				 * output codes.
    718 				 */
    719 				hsize = HSIZE;
    720 				if (fsize < (1 << 12))
    721 					hsize = min(5003, HSIZE);
    722 				else if (fsize < (1 << 13))
    723 					hsize = min(9001, HSIZE);
    724 				else if (fsize < (1 << 14))
    725 					hsize = min(18013, HSIZE);
    726 				else if (fsize < (1 << 15))
    727 					hsize = min(35023, HSIZE);
    728 				else if (fsize < 47000)
    729 					hsize = min(50021, HSIZE);
    730 
    731 				if (!use_stdout) {
    732 					/* Generate output filename */
    733 
    734 					if (strlcpy(ofname, *fileptr,
    735 					    sizeof (ofname)) >=
    736 					    sizeof (ofname)) {
    737 						(void) fprintf(stderr,
    738 						    gettext("%s: filename "
    739 						    "too long\n"),
    740 						    *fileptr);
    741 						perm_stat = 1;
    742 						continue;
    743 					}
    744 
    745 					if (addDotZ(ofname,
    746 					    sizeof (ofname)) < 0) {
    747 						perm_stat = 1;
    748 						continue;
    749 					}
    750 				}
    751 			}
    752 		}	/* if (do_decomp) */
    753 
    754 		/* Check for overwrite of existing file */
    755 
    756 		if (!overwrite && !use_stdout) {
    757 			if (stat(ofname, &ostatbuf) == 0) {
    758 				(void) fprintf(stderr, gettext(
    759 				    "%s already exists;"), ofname);
    760 				if (bgnd_flag == 0 && isatty(2)) {
    761 					int cin;
    762 
    763 					(void) fprintf(stderr, gettext(
    764 					    " do you wish to overwr"
    765 					    "ite %s (%s or %s)? "),
    766 					    ofname, yesstr, nostr);
    767 					(void) fflush(stderr);
    768 					for (cin = 0; cin < LINE_MAX; cin++)
    769 						line[cin] = 0;
    770 					(void) read(2, line, LINE_MAX);
    771 
    772 					if (yes_check(line) == 0) {
    773 						(void) fprintf(stderr,
    774 						    gettext(
    775 						    "\tnot overwri"
    776 						    "tten\n"));
    777 						continue;
    778 					}
    779 				} else {
    780 					/*
    781 					 * XPG4: Assertion 1009
    782 					 * Standard input is not
    783 					 * terminal, and no '-f',
    784 					 * and file exists.
    785 					 */
    786 
    787 					(void) fprintf(stderr, gettext(
    788 					    "%s: File exists, -f not"
    789 					    " specified, and ru"
    790 					    "nning in the backgro"
    791 					    "und.\n"), *fileptr);
    792 					perm_stat = 1;
    793 					continue;
    794 				}
    795 			}
    796 		}
    797 		if (!use_stdout) {
    798 			if ((pathconf(ofname, _PC_XATTR_EXISTS) == 1) ||
    799 			    (saflg && sysattr_support(ofname,
    800 			    _PC_SATTR_EXISTS) == 1)) {
    801 				(void) unlink(ofname);
    802 			}
    803 			/* Open output file */
    804 			if (freopen(ofname, "w", outp) == NULL) {
    805 				perror(ofname);
    806 				perm_stat = 1;
    807 				continue;
    808 			}
    809 			precious = 0;
    810 			if (!quiet) {
    811 				(void) fprintf(stderr, "%s: ",
    812 				    *fileptr);
    813 				newline_needed = 1;
    814 			}
    815 		} else if (!quiet && !do_decomp) {
    816 			(void) fprintf(stderr, "%s: ",
    817 			    *fileptr);
    818 				newline_needed = 1;
    819 		}
    820 
    821 		/* Actually do the compression/decompression */
    822 
    823 		if ((jmpval = setjmp(env)) == 0) {
    824 			/* We'll see how things go */
    825 #ifndef DEBUG
    826 			if (do_decomp == 0)  {
    827 				compress();
    828 			} else {
    829 				decompress();
    830 			}
    831 #else
    832 			if (do_decomp == 0)  {
    833 				compress();
    834 			} else if (debug == 0)  {
    835 				decompress();
    836 			} else {
    837 				printcodes();
    838 			}
    839 
    840 			if (verbose) {
    841 				dump_tab();
    842 			}
    843 #endif
    844 		} else {
    845 			/*
    846 			 * Things went badly - clean up and go on.
    847 			 * jmpval's values break down as follows:
    848 			 *   1 == message determined by ferror() values.
    849 			 *   2 == input problem message needed.
    850 			 *   3 == output problem message needed.
    851 			 */
    852 
    853 			if (ferror(inp) || jmpval == 2) {
    854 				if (do_decomp) {
    855 					(void) fprintf(stderr, gettext(
    856 					    "uncompress: %s: corrupt"
    857 					    " input\n"), *fileptr);
    858 				} else {
    859 					perror(*fileptr);
    860 				}
    861 			}
    862 
    863 			if (ferror(outp) || jmpval == 3) {
    864 				/* handle output errors */
    865 
    866 				if (use_stdout) {
    867 					perror("");
    868 				} else {
    869 					perror(ofname);
    870 				}
    871 			}
    872 
    873 			if (ofname[0] != '\0') {
    874 				if (unlink(ofname) < 0)  {
    875 					perror(ofname);
    876 				}
    877 
    878 				ofname[0] = '\0';
    879 			}
    880 
    881 			perm_stat = 1;
    882 			continue;
    883 		}
    884 
    885 		/* Things went well */
    886 
    887 		if (!use_stdout) {
    888 				/* Copy stats */
    889 			copystat(*fileptr, &statbuf, ofname);
    890 			precious = 1;
    891 			if (newline_needed) {
    892 				(void) putc('\n', stderr);
    893 			}
    894 			/*
    895 			 * Print the info. for unchanged file
    896 			 * when no -v
    897 			 */
    898 
    899 			if (didnt_shrink) {
    900 				if (!force && perm_stat == 0) {
    901 					if (quiet) {
    902 						(void) fprintf(stderr, gettext(
    903 						    "%s: -- file "
    904 						    "unchanged\n"),
    905 						    *fileptr);
    906 					}
    907 
    908 					perm_stat = 2;
    909 				}
    910 			}
    911 		} else {
    912 			if (didnt_shrink && !force && perm_stat == 0) {
    913 				perm_stat = 2;
    914 			}
    915 
    916 			if (newline_needed) {
    917 				(void) fprintf(stderr, "\n");
    918 			}
    919 		}
    920 	}	/* for */
    921 
    922 	return (perm_stat);
    923 }
    924 
    925 static void
    926 cinterr(int hshift)
    927 {
    928 	/* we have exceeded the hash table */
    929 	(void) fprintf(stderr,
    930 	    "internal error: hashtable exceeded - hsize = %ld\n", hsize);
    931 	(void) fprintf(stderr, "hshift = %d, %d\n", hshift, (1 << hshift) -1);
    932 	(void) fprintf(stderr, "maxbits = %d\n", maxbits);
    933 	(void) fprintf(stderr, "n_bits = %d\n", n_bits);
    934 	(void) fprintf(stderr, "maxcode = %ld\n", maxcode);
    935 	longjmp(env, 1);
    936 }
    937 
    938 static code_int
    939 adjusti(code_int i, code_int hsize_reg)
    940 {
    941 	while (i < 0) {
    942 		i += hsize_reg;
    943 	}
    944 
    945 	while (i >= hsize_reg) {
    946 		i -= hsize_reg;
    947 	}
    948 	return (i);
    949 }
    950 
    951 /*
    952  * compress inp to outp
    953  *
    954  * Algorithm:  use open addressing double hashing(no chaining) on the
    955  * prefix code / next character combination.  We do a variant of Knuth's
    956  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
    957  * secondary probe.  Here, the modular division first probe is gives way
    958  * to a faster exclusive-or manipulation.  Also do block compression with
    959  * an adaptive reset, whereby the code table is cleared when the compression
    960  * ratio decreases, but after the table fills.  The variable-length output
    961  * codes are re-sized at this point, and a special CLEAR code is generated
    962  * for the decompressor.  Late addition:  construct the table according to
    963  * file size for noticeable speed improvement on small files.  Please direct
    964  * questions about this implementation to ames!jaw.
    965  */
    966 
    967 static void
    968 compress()
    969 {
    970 	long fcode;
    971 	code_int i = 0;
    972 	int c;
    973 	code_int ent;
    974 	int disp;
    975 	code_int hsize_reg;
    976 	int hshift;
    977 	int probecnt;
    978 	count_long in_count;
    979 	uint32_t inchi, inclo;
    980 	int maxbits_reg;
    981 	FILE *fin = inp;
    982 #ifdef DEBUG
    983 	count_long out_count = 0;
    984 #endif
    985 
    986 	if (nomagic == 0) {
    987 		if ((putc(magic_header[0], outp) == EOF ||
    988 		    putc(magic_header[1], outp) == EOF ||
    989 		    putc((char)(maxbits | block_compress),
    990 		    outp) == EOF) &&
    991 		    ferror(outp)) {
    992 			ioerror();
    993 		}
    994 	}
    995 
    996 	offset = 0;
    997 	bytes_out = 3;		/* includes 3-byte header mojo */
    998 	clear_flg = 0;
    999 	ratio = 0;
   1000 	in_count = 1;
   1001 	inchi = 0;
   1002 	inclo = 1;
   1003 	checkpoint = CHECK_GAP;
   1004 	maxcode = MAXCODE(n_bits = INIT_BITS);
   1005 	free_ent = ((block_compress) ? FIRST : 256);
   1006 
   1007 	if ((ent = getc(fin)) == EOF && ferror(fin)) {
   1008 		ioerror();
   1009 	}
   1010 
   1011 	hshift = 0;
   1012 
   1013 	for (fcode = (long)hsize;  fcode < 65536L; fcode *= 2L)
   1014 		hshift++;
   1015 
   1016 	hshift = 8 - hshift;		/* set hash code range bound */
   1017 
   1018 	hsize_reg = hsize;
   1019 	maxbits_reg = maxbits;
   1020 
   1021 	cl_hash((count_int) hsize_reg);		/* clear hash table */
   1022 
   1023 	while ((c = getc(fin)) != EOF) {
   1024 		if (++inclo == 0)
   1025 			inchi++;
   1026 		fcode = (long)(((long)c << maxbits_reg) + ent);
   1027 		i = ((c << hshift) ^ ent);	/* xor hashing */
   1028 
   1029 		if ((unsigned int)i >= hsize_reg)
   1030 			i = adjusti(i, hsize_reg);
   1031 
   1032 		if (htabof(i) == fcode) {
   1033 			ent = codetabof(i);
   1034 			continue;
   1035 		} else if ((long)htabof(i) < 0) {
   1036 			/* empty slot */
   1037 			goto nomatch;
   1038 		}
   1039 
   1040 		/* secondary hash (after G. Knott) */
   1041 		disp = hsize_reg - i;
   1042 
   1043 		if (i == 0) {
   1044 			disp = 1;
   1045 		}
   1046 
   1047 		probecnt = 0;
   1048 	probe:
   1049 		if (++probecnt > hsize_reg)
   1050 			cinterr(hshift);
   1051 
   1052 		if ((i -= disp) < 0) {
   1053 			while (i < 0)
   1054 				i += hsize_reg;
   1055 		}
   1056 
   1057 		if (htabof(i) == fcode) {
   1058 			ent = codetabof(i);
   1059 			continue;
   1060 		}
   1061 
   1062 		if ((long)htabof(i) > 0) {
   1063 			goto probe;
   1064 		}
   1065 	nomatch:
   1066 		output((code_int) ent);
   1067 #ifdef DEBUG
   1068 		out_count++;
   1069 #endif
   1070 		ent = c;
   1071 		if (free_ent < maxmaxcode) {
   1072 			codetabof(i) = free_ent++;
   1073 			/* code -> hashtable */
   1074 			htabof(i) = fcode;
   1075 		} else {
   1076 			in_count = ((long long)inchi<<32|inclo);
   1077 			if ((count_long)in_count >=
   1078 			    (count_long)checkpoint && block_compress) {
   1079 				cl_block(in_count);
   1080 			}
   1081 		}
   1082 	}
   1083 
   1084 	in_count = ((long long)inchi<<32|inclo);
   1085 
   1086 	if (ferror(fin) != 0) {
   1087 		ioerror();
   1088 	}
   1089 
   1090 	/*
   1091 	 * Put out the final code.
   1092 	 */
   1093 	output((code_int)ent);
   1094 #ifdef DEBUG
   1095 	out_count++;
   1096 #endif
   1097 
   1098 	output((code_int)-1);
   1099 
   1100 	/*
   1101 	 * Print out stats on stderr
   1102 	 */
   1103 	if (!quiet) {
   1104 #ifdef DEBUG
   1105 		(void) fprintf(stderr,
   1106 		    "%lld chars in, %lld codes (%lld bytes) out, "
   1107 		    "compression factor: ",
   1108 		    (count_long)in_count, (count_long)out_count,
   1109 		    (count_long) bytes_out);
   1110 		prratio(stderr, (count_long)in_count,
   1111 		    (count_long)bytes_out);
   1112 		(void) fprintf(stderr, "\n");
   1113 		(void) fprintf(stderr, "\tCompression as in compact: ");
   1114 		prratio(stderr,
   1115 		    (count_long)in_count-(count_long)bytes_out,
   1116 		    (count_long)in_count);
   1117 		(void) fprintf(stderr, "\n");
   1118 		(void) fprintf(stderr,
   1119 		    "\tLargest code (of last block) was %d"
   1120 		    " (%d bits)\n",
   1121 		    free_ent - 1, n_bits);
   1122 #else /* !DEBUG */
   1123 		(void) fprintf(stderr, gettext("Compression: "));
   1124 		prratio(stderr,
   1125 		    (count_long)in_count-(count_long)bytes_out,
   1126 		    (count_long)in_count);
   1127 #endif /* DEBUG */
   1128 	}
   1129 	/* report if no savings */
   1130 	if ((count_long)bytes_out > (count_long)in_count) {
   1131 		didnt_shrink = 1;
   1132 	}
   1133 }
   1134 
   1135 /*
   1136  * **************************************************************
   1137  * TAG(output)
   1138  *
   1139  * Output the given code.
   1140  * Inputs:
   1141  * 	code:	A n_bits-bit integer.  If == -1, then EOF.  This assumes
   1142  *		that n_bits = < (long)wordsize - 1.
   1143  * Outputs:
   1144  * 	Outputs code to the file.
   1145  * Assumptions:
   1146  *	Chars are 8 bits long.
   1147  * Algorithm:
   1148  * 	Maintain a BITS character long buffer(so that 8 codes will
   1149  * fit in it exactly).  Use the VAX insv instruction to insert each
   1150  * code in turn.  When the buffer fills up empty it and start over.
   1151  */
   1152 
   1153 static void
   1154 output(code_int code)
   1155 {
   1156 #ifdef DEBUG
   1157 	static int col = 0;
   1158 #endif /* DEBUG */
   1159 
   1160 	int r_off = offset, bits = n_bits;
   1161 	char *bp = buf;
   1162 
   1163 #ifdef DEBUG
   1164 	if (verbose)
   1165 		(void) fprintf(stderr, "%5d%c", code,
   1166 		    (col += 6) >= 74 ? (col = 0, '\n') : ' ');
   1167 #endif /* DEBUG */
   1168 	if (code >= 0) {
   1169 		/*
   1170 		 * byte/bit numbering on the VAX is simulated
   1171 		 * by the following code
   1172 		 */
   1173 		/*
   1174 		 * Get to the first byte.
   1175 		 */
   1176 		bp += (r_off >> 3);
   1177 		r_off &= 7;
   1178 		/*
   1179 		 * Since code is always >= 8 bits, only need to mask the first
   1180 		 * hunk on the left.
   1181 		 */
   1182 		*bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
   1183 		bp++;
   1184 		bits -= (8 - r_off);
   1185 		code >>= 8 - r_off;
   1186 		/*
   1187 		 * Get any 8 bit parts in the middle (<=1 for up to 16
   1188 		 * bits).
   1189 		 */
   1190 		if (bits >= 8) {
   1191 			*bp++ = code;
   1192 			code >>= 8;
   1193 			bits -= 8;
   1194 		}
   1195 		/* Last bits. */
   1196 		if (bits)
   1197 			*bp = code;
   1198 		offset += n_bits;
   1199 		if (offset == (n_bits << 3)) {
   1200 			bp = buf;
   1201 			bits = n_bits;
   1202 			bytes_out += bits;
   1203 			do {
   1204 				if (putc(*bp, outp) == EOF &&
   1205 				    ferror(outp)) {
   1206 					ioerror();
   1207 				}
   1208 				bp++;
   1209 			} while (--bits);
   1210 			offset = 0;
   1211 		}
   1212 
   1213 		/*
   1214 		 * If the next entry is going to be too big for the code size,
   1215 		 * then increase it, if possible.
   1216 		 */
   1217 		if (free_ent > maxcode || (clear_flg > 0)) {
   1218 			/*
   1219 			 * Write the whole buffer, because the input
   1220 			 * side won't discover the size increase until
   1221 			 * after it has read it.
   1222 			 */
   1223 			if (offset > 0) {
   1224 				if (fwrite(buf, 1, n_bits, outp) != n_bits) {
   1225 					longjmp(env, 3);
   1226 				}
   1227 				bytes_out += n_bits;
   1228 			}
   1229 			offset = 0;
   1230 
   1231 			if (clear_flg) {
   1232 				maxcode = MAXCODE(n_bits = INIT_BITS);
   1233 				clear_flg = 0;
   1234 			} else {
   1235 				n_bits++;