Subversion Repositories planix.SVN

/*

 * compress - File compression ala IEEE Computer, June 1984.

 *

 * Algorithm from "A Technique for High Performance Data Compression",

 * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.

 *

 * Usage: compress [-dfvc] [-b bits] [file ...]

 * Inputs:

 *	-b:	limit the max number of bits/code.

 *	-c:	write output on stdout, don't remove original.

 *	-d:	decompress instead.

 *	-f:	Forces output file to be generated, even if one already

 *		exists, and even if no space is saved by compressing.

 *		If -f is not used, the user will be prompted if stdin is

 *		a tty, otherwise, the output file will not be overwritten.

 *	-v:	Write compression statistics

 *

 * 	file ...: Files to be compressed.  If none specified, stdin is used.

 * Outputs:

 *	file.Z:	Compressed form of file with same mode, owner, and utimes

 * 		or stdout (if stdin used as input)

 *

 * Assumptions:

 *	When filenames are given, replaces with the compressed version

 *	(.Z suffix) only if the file decreases in size.

 * Algorithm:

 * 	Modified Lempel-Ziv method (LZW).  Basically finds common

 * substrings and replaces them with a variable size code.  This is

 * deterministic, and can be done on the fly.  Thus, the decompression

 * procedure needs no input table, but tracks the way the table was built.

 * Authors:	Spencer W. Thomas	(decvax!harpo!utah-cs!utah-gr!thomas)

 *		Jim McKie		(decvax!mcvax!jim)

 *		Steve Davies		(decvax!vax135!petsd!peora!srd)

 *		Ken Turkowski		(decvax!decwrl!turtlevax!ken)

 *		James A. Woods		(decvax!ihnp4!ames!jaw)

 *		Joe Orost		(decvax!vax135!petsd!joe)

 */

#define _PLAN9_SOURCE

#define _BSD_EXTENSION

#define _POSIX_SOURCE

#include <u.h>

#include <stdio.h>

#include <ctype.h>

#include <stdlib.h>

#include <unistd.h>

#include <string.h>

#include <signal.h>

#include <utime.h>

#include <sys/types.h>

#include <sys/stat.h>

#define	min(a,b)	((a>b) ? b : a)

#define BITS	16

#define HSIZE	69001		/* 95% occupancy */

/*

 * a code_int must be able to hold 2**BITS values of type int, and also -1

 */

typedef long	code_int;

typedef long	count_int;

static char rcs_ident[] = "$Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $";

uchar magic_header[] = { 0x1F, 0x9D };	/* 1F 9D */

/* Defines for third byte of header */

#define BIT_MASK	0x1f

#define BLOCK_MASK	0x80

/* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is

	a fourth header byte (for expansion).

*/

#define INIT_BITS 9			/* initial number of bits/code */

#define ARGVAL() (*++(*argv) || (--argc && *++argv))

int n_bits;				/* number of bits/code */

int maxbits = BITS;			/* user settable max # bits/code */

code_int maxcode;			/* maximum code, given n_bits */

code_int maxmaxcode = 1 << BITS;	/* should NEVER generate this code */

#define MAXCODE(n_bits)	((1 << (n_bits)) - 1)

count_int htab[HSIZE];

ushort codetab[HSIZE];

#define htabof(i)	htab[i]

#define codetabof(i)	codetab[i]

code_int hsize = HSIZE;			/* for dynamic table sizing */

count_int fsize;

/*

 * To save much memory, we overlay the table used by compress() with those

 * used by decompress().  The tab_prefix table is the same size and type

 * as the codetab.  The tab_suffix table needs 2**BITS characters.  We

 * get this from the beginning of htab.  The output stack uses the rest

 * of htab, and contains characters.  There is plenty of room for any

 * possible stack (stack used to be 8000 characters).

 */

#define tab_prefixof(i)	codetabof(i)

#define tab_suffixof(i)	((uchar *)(htab))[i]

#define de_stack		((uchar *)&tab_suffixof(1<<BITS))

code_int free_ent = 0;			/* first unused entry */

int exit_stat = 0;

void	cl_block(void);

void	cl_hash(count_int);

void	compress(void);

void	copystat(char *, char *);

void	decompress(void);

int	foreground(void);

code_int getcode(void);

void	onintr(int);

void	oops(int);

void	output(code_int);

void	prratio(FILE *, long, long);

void	version(void);

void	writeerr(void);

void

Usage(void)

{

#ifdef DEBUG

	fprintf(stderr,"Usage: compress [-cdfDV] [-b maxbits] [file ...]\n");

#else

	fprintf(stderr,"Usage: compress [-cdfvV] [-b maxbits] [file ...]\n");

#endif /* DEBUG */

}

int debug = 0;

int nomagic = 0;	/* Use a 3-byte magic number header, unless old file */

int zcat_flg = 0;	/* Write output on stdout, suppress messages */

int quiet = 1;		/* don't tell me about compression */

/*

 * block compression parameters -- after all codes are used up,

 * and compression rate changes, start over.

 */

int block_compress = BLOCK_MASK;

int clear_flg = 0;

long ratio = 0;

#define CHECK_GAP 10000	/* ratio check interval */

count_int checkpoint = CHECK_GAP;

/*

 * the next two codes should not be changed lightly, as they must not

 * lie within the contiguous general code space.

 */

#define FIRST	257	/* first free entry */

#define	CLEAR	256	/* table clear output code */

int force = 0;

char ofname [100];

#ifdef DEBUG

int verbose = 0;

#endif /* DEBUG */

void (*bgnd_flag)(int);

int do_decomp = 0;

main(argc, argv)

int argc;

char **argv;

{

	int overwrite = 0;	/* Do not overwrite unless given -f flag */

	char tempname[512];

	char **filelist, **fileptr;

	char *cp;

	struct stat statbuf;

	if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {

		signal(SIGINT, onintr);

		signal(SIGSEGV, oops);

	}

	filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));

	*filelist = NULL;

	if((cp = strrchr(argv[0], '/')) != 0)

		cp++;

	else

		cp = argv[0];

	if(strcmp(cp, "uncompress") == 0)

		do_decomp = 1;

	else if(strcmp(cp, "zcat") == 0) {

		do_decomp = 1;

		zcat_flg = 1;

	}

	/*

	 * Argument Processing

	 * All flags are optional.

	 * -C	generate output compatible with compress 2.0.

	 * -D	debug

	 * -V	print Version; debug verbose

	 * -b maxbits	maxbits.  If -b is specified, then maxbits MUST be

	 *		given also.

	 * -c	cat all output to stdout

	 * -d	do_decomp

	 * -f	force overwrite of output file

	 * -n	no header: useful to uncompress old files

	 * -v	unquiet

	 * if a string is left, must be an input filename.

	 */

	for (argc--, argv++; argc > 0; argc--, argv++) {

	if (**argv == '-') {	/* A flag argument */

		while (*++(*argv)) {	/* Process all flags in this arg */

		switch (**argv) {

		case 'C':

			block_compress = 0;

			break;

#ifdef DEBUG

		case 'D':

			debug = 1;

			break;

		case 'V':

			verbose = 1;

			version();

			break;

#else

		case 'V':

			version();

			break;

#endif

		case 'b':

			if (!ARGVAL()) {

				fprintf(stderr, "Missing maxbits\n");

				Usage();

				exit(1);

			}

			maxbits = atoi(*argv);

			goto nextarg;

		case 'c':

			zcat_flg = 1;

			break;

		case 'd':

			do_decomp = 1;

			break;

		case 'f':

		case 'F':

			overwrite = 1;

			force = 1;

			break;

		case 'n':

			nomagic = 1;

			break;

		case 'q':

			quiet = 1;

			break;

		case 'v':

			quiet = 0;

			break;

		default:

			fprintf(stderr, "Unknown flag: '%c'; ", **argv);

			Usage();

			exit(1);

		}

		}

	} else {			/* Input file name */

		*fileptr++ = *argv;	/* Build input file list */

		*fileptr = NULL;

		/* process nextarg; */

	}

nextarg:

		continue;

	}

	if(maxbits < INIT_BITS) maxbits = INIT_BITS;

	if (maxbits > BITS) maxbits = BITS;

	maxmaxcode = 1 << maxbits;

	if (*filelist != NULL) {

	for (fileptr = filelist; *fileptr; fileptr++) {

		exit_stat = 0;

		if (do_decomp != 0) {			/* DECOMPRESSION */

		/* Check for .Z suffix */

		if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") != 0) {

			/* No .Z: tack one on */

			strcpy(tempname, *fileptr);

			strcat(tempname, ".Z");

			*fileptr = tempname;

		}

		/* Open input file */

		if ((freopen(*fileptr, "r", stdin)) == NULL) {

			perror(*fileptr);

			continue;

		}

		/* Check the magic number */

		if (nomagic == 0) {

			if ((getchar() != (magic_header[0] & 0xFF))

			|| (getchar() != (magic_header[1] & 0xFF))) {

				fprintf(stderr, "%s: not in compressed format\n",

					*fileptr);

				continue;

			}

			maxbits = getchar();	/* set -b from file */

			block_compress = maxbits & BLOCK_MASK;

			maxbits &= BIT_MASK;

			maxmaxcode = 1 << maxbits;

			if(maxbits > BITS) {

				fprintf(stderr,

		"%s: compressed with %d bits, can only handle %d bits\n",

					*fileptr, maxbits, BITS);

				continue;

			}

		}

		/* Generate output filename */

		strcpy(ofname, *fileptr);

		ofname[strlen(*fileptr) - 2] = '\0';  /* Strip off .Z */

		} else {				/* COMPRESSION */

		if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") == 0) {

			fprintf(stderr,

				"%s: already has .Z suffix -- no change\n",

				*fileptr);

			continue;

		}

		/* Open input file */

		if ((freopen(*fileptr, "r", stdin)) == NULL) {

			perror(*fileptr);

			continue;

		}

		(void) stat(*fileptr, &statbuf);

		fsize = (long) statbuf.st_size;

		/*

		 * tune hash table size for small files -- ad hoc,

		 * but the sizes match earlier #defines, which

		 * serve as upper bounds on the number of output codes.

		 */

		hsize = HSIZE;

		if (fsize < (1 << 12))

			hsize = min(5003, HSIZE);

		else if (fsize < (1 << 13))

			hsize = min(9001, HSIZE);

		else if (fsize < (1 << 14))

			hsize = min (18013, HSIZE);

		else if (fsize < (1 << 15))

			hsize = min (35023, HSIZE);

		else if (fsize < 47000)

			hsize = min (50021, HSIZE);

		/* Generate output filename */

		strcpy(ofname, *fileptr);

#ifndef BSD4_2

		if ((cp=strrchr(ofname,'/')) != NULL)

			cp++;

		else

			cp = ofname;

		/*

		 *** changed 12 to 25;  should be NAMELEN-3, but I don't want

		 * to fight the headers.	ehg 5 Nov 92 **

		 */

		if (strlen(cp) > 25) {

			fprintf(stderr, "%s: filename too long to tack on .Z\n",

				cp);

			continue;

		}

#endif

		strcat(ofname, ".Z");

		}

		/* Check for overwrite of existing file */

		if (overwrite == 0 && zcat_flg == 0 &&

		   stat(ofname, &statbuf) == 0) {

			char response[2];

			response[0] = 'n';

			fprintf(stderr, "%s already exists;", ofname);

			if (foreground()) {

				fprintf(stderr,

				    " do you wish to overwrite %s (y or n)? ",

					ofname);

				fflush(stderr);

				(void) read(2, response, 2);

				while (response[1] != '\n')

					if (read(2, response+1, 1) < 0) {

						/* Ack! */

						perror("stderr");

						break;

					}

			}

			if (response[0] != 'y') {

				fprintf(stderr, "\tnot overwritten\n");

				continue;

			}

		}

		if(zcat_flg == 0) {		/* Open output file */

			if (freopen(ofname, "w", stdout) == NULL) {

				perror(ofname);

				continue;

			}

			if(!quiet)

				fprintf(stderr, "%s: ", *fileptr);

		}

		/* Actually do the compression/decompression */

		if (do_decomp == 0)

			compress();

#ifndef DEBUG

		else

			decompress();

#else

		else if (debug == 0)

			decompress();

		else

			printcodes();

		if (verbose)

			dump_tab();

#endif						/* DEBUG */

		if(zcat_flg == 0) {

			copystat(*fileptr, ofname);	/* Copy stats */

			if (exit_stat == 1 || !quiet)

				putc('\n', stderr);

		}

	}

	} else {		/* Standard input */

	if (do_decomp == 0) {

		compress();

#ifdef DEBUG

		if(verbose)

			dump_tab();

#endif

		if(!quiet)

			putc('\n', stderr);

	} else {

		/* Check the magic number */

		if (nomagic == 0) {

		if ((getchar()!=(magic_header[0] & 0xFF))

		 || (getchar()!=(magic_header[1] & 0xFF))) {

			fprintf(stderr, "stdin: not in compressed format\n");

			exit(1);

		}

		maxbits = getchar();	/* set -b from file */

		block_compress = maxbits & BLOCK_MASK;

		maxbits &= BIT_MASK;

		maxmaxcode = 1 << maxbits;

		fsize = 100000;		/* assume stdin large for USERMEM */

		if(maxbits > BITS) {

			fprintf(stderr,

			"stdin: compressed with %d bits, can only handle %d bits\n",

			maxbits, BITS);

			exit(1);

		}

		}

#ifndef DEBUG

		decompress();

#else

		if (debug == 0)

			decompress();

		else

			printcodes();

		if (verbose)

			dump_tab();

#endif						/* DEBUG */

	}

	}

	exit(exit_stat);

	return 0;

}

static int offset;

long in_count = 1;		/* length of input */

long bytes_out;			/* length of compressed output */

long out_count = 0;		/* # of codes output (for debugging) */

/*

 * compress stdin to stdout

 *

 * Algorithm:  use open addressing double hashing (no chaining) on the

 * prefix code / next character combination.  We do a variant of Knuth's

 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime

 * secondary probe.  Here, the modular division first probe is gives way

 * to a faster exclusive-or manipulation.  Also do block compression with

 * an adaptive reset, whereby the code table is cleared when the compression

 * ratio decreases, but after the table fills.  The variable-length output

 * codes are re-sized at this point, and a special CLEAR code is generated

 * for the decompressor.  Late addition:  construct the table according to

 * file size for noticeable speed improvement on small files.  Please direct

 * questions about this implementation to ames!jaw.

 */

void

compress(void)

{

	code_int ent, hsize_reg;

	code_int i;

	int c, disp, hshift;

	long fcode;

	if (nomagic == 0) {

		putchar(magic_header[0]);

		putchar(magic_header[1]);

		putchar((char)(maxbits | block_compress));

		if(ferror(stdout))

			writeerr();

	}

	offset = 0;

	bytes_out = 3;		/* includes 3-byte header mojo */

	out_count = 0;

	clear_flg = 0;

	ratio = 0;

	in_count = 1;

	checkpoint = CHECK_GAP;

	maxcode = MAXCODE(n_bits = INIT_BITS);

	free_ent = (block_compress? FIRST: 256);

	ent = getchar ();

	hshift = 0;

	for (fcode = (long)hsize;  fcode < 65536L; fcode *= 2)

		hshift++;

	hshift = 8 - hshift;		/* set hash code range bound */

	hsize_reg = hsize;

	cl_hash( (count_int) hsize_reg);		/* clear hash table */

	while ((c = getchar()) != EOF) {

		in_count++;

		fcode = (long) (((long) c << maxbits) + ent);

	 	i = ((c << hshift) ^ ent);	/* xor hashing */

		if (htabof (i) == fcode) {

			ent = codetabof(i);

			continue;

		} else if ((long)htabof(i) < 0 )	/* empty slot */

			goto nomatch;

	 	disp = hsize_reg - i;	/* secondary hash (after G. Knott) */

		if (i == 0)

			disp = 1;

probe:

		if ((i -= disp) < 0)

			i += hsize_reg;

		if (htabof (i) == fcode) {

			ent = codetabof(i);

			continue;

		}

		if ((long)htabof(i) > 0)

			goto probe;

nomatch:

		output((code_int)ent);

		out_count++;

	 	ent = c;

		if (free_ent < maxmaxcode) {

	 		codetabof(i) = free_ent++;	/* code -> hashtable */

			htabof(i) = fcode;

		} else if ((count_int)in_count >= checkpoint && block_compress)

			cl_block ();

	}

	/*

	* Put out the final code.

	*/

	output( (code_int)ent );

	out_count++;

	output( (code_int)-1 );

	/*

	* Print out stats on stderr

	*/

	if(zcat_flg == 0 && !quiet) {

#ifdef DEBUG

	fprintf( stderr,

		"%ld chars in, %ld codes (%ld bytes) out, compression factor: ",

		in_count, out_count, bytes_out );

	prratio( stderr, in_count, bytes_out );

	fprintf( stderr, "\n");

	fprintf( stderr, "\tCompression as in compact: " );

	prratio( stderr, in_count-bytes_out, in_count );

	fprintf( stderr, "\n");

	fprintf( stderr, "\tLargest code (of last block) was %d (%d bits)\n",

		free_ent - 1, n_bits );

#else /* !DEBUG */

	fprintf( stderr, "Compression: " );

	prratio( stderr, in_count-bytes_out, in_count );

#endif /* DEBUG */

	}

	if(bytes_out > in_count)	/* exit(2) if no savings */

		exit_stat = 2;

}

/*

 * TAG( output )

 *

 * Output the given code.

 * Inputs:

 * 	code:	A n_bits-bit integer.  If == -1, then EOF.  This assumes

 *		that n_bits =< (long)wordsize - 1.

 * Outputs:

 * 	Outputs code to the file.

 * Assumptions:

 *	Chars are 8 bits long.

 * Algorithm:

 * 	Maintain a BITS character long buffer (so that 8 codes will

 * fit in it exactly).  When the buffer fills up empty it and start over.

 */

static char buf[BITS];

uchar lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};

uchar rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

void

output( code )

code_int  code;

{

#ifdef DEBUG

	static int col = 0;

#endif

	int r_off = offset, bits= n_bits;

	char *bp = buf;

#ifdef DEBUG

	if (verbose)

		fprintf(stderr, "%5d%c", code,

			(col+=6) >= 74? (col = 0, '\n'): ' ');

#endif

	if (code >= 0) {

		/*

		 * byte/bit numbering on the VAX is simulated by the

		 * following code

		 */

		/*

		 * Get to the first byte.

		 */

		bp += (r_off >> 3);

		r_off &= 7;

		/*

		 * Since code is always >= 8 bits, only need to mask the first

		 * hunk on the left.

		 */

		*bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];

		bp++;

		bits -=  8 - r_off;

		code >>= 8 - r_off;

		/* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */

		if ( bits >= 8 ) {

			*bp++ = code;

			code >>= 8;

			bits -= 8;

		}

		/* Last bits. */

		if(bits)

			*bp = code;

		offset += n_bits;

		if ( offset == (n_bits << 3) ) {

			bp = buf;

			bits = n_bits;

			bytes_out += bits;

			do {

				putchar(*bp++);

			} while(--bits);

			offset = 0;

		}

		/*

		 * If the next entry is going to be too big for the code size,

		 * then increase it, if possible.

		 */

		if ( free_ent > maxcode || (clear_flg > 0)) {

			/*

			* Write the whole buffer, because the input side won't

			* discover the size increase until after it has read it.

			*/

			if ( offset > 0 ) {

				if( fwrite( buf, 1, n_bits, stdout ) != n_bits)

					writeerr();

				bytes_out += n_bits;

			}

			offset = 0;

			if ( clear_flg ) {

				maxcode = MAXCODE (n_bits = INIT_BITS);

				clear_flg = 0;

			} else {

				n_bits++;

				if ( n_bits == maxbits )

					maxcode = maxmaxcode;

				else

					maxcode = MAXCODE(n_bits);

			}

#ifdef DEBUG

			if ( debug ) {

				fprintf(stderr,

					"\nChange to %d bits\n", n_bits);

				col = 0;

			}

#endif

		}

	} else {

		/*

		 * At EOF, write the rest of the buffer.

		 */

		if ( offset > 0 )

			fwrite( buf, 1, (offset + 7) / 8, stdout );

		bytes_out += (offset + 7) / 8;

		offset = 0;

		fflush( stdout );

#ifdef DEBUG

		if ( verbose )

			fprintf( stderr, "\n" );

#endif

		if( ferror( stdout ) )

			writeerr();

	}

}

/*

 * Decompress stdin to stdout.  This routine adapts to the codes in the

 * file building the "string" table on-the-fly; requiring no table to

 * be stored in the compressed file.  The tables used herein are shared

 * with those of the compress() routine.  See the definitions above.

 */

void

decompress(void)

{

	int finchar;

	code_int code, oldcode, incode;

	uchar *stackp;

	/*

	* As above, initialize the first 256 entries in the table.

	*/

	maxcode = MAXCODE(n_bits = INIT_BITS);

	for (code = 255; code >= 0; code--) {

		tab_prefixof(code) = 0;

		tab_suffixof(code) = (uchar)code;

	}

	free_ent = (block_compress? FIRST: 256);

	finchar = oldcode = getcode();

	if(oldcode == -1)		/* EOF already? */

		return;			/* Get out of here */

	putchar((char)finchar);		/* first code must be 8 bits = char */

	if(ferror(stdout))		/* Crash if can't write */

		writeerr();

	stackp = de_stack;

	while ((code = getcode()) > -1) {

		if ((code == CLEAR) && block_compress) {

			for (code = 255; code >= 0; code--)

				tab_prefixof(code) = 0;

			clear_flg = 1;

			free_ent = FIRST - 1;

			if ((code = getcode()) == -1)	/* O, untimely death! */

				break;

		}

		incode = code;

		/*

		 * Special case for KwKwK string.

		 */

		if (code >= free_ent) {

			*stackp++ = finchar;

			code = oldcode;

		}

		/*

		 * Generate output characters in reverse order

		 */

		while (code >= 256) {

			*stackp++ = tab_suffixof(code);

			code = tab_prefixof(code);

		}

		*stackp++ = finchar = tab_suffixof(code);

		/*

		 * And put them out in forward order

		 */

		do {

			putchar(*--stackp);

		} while (stackp > de_stack);

		/*

		 * Generate the new entry.

		 */

		if ( (code=free_ent) < maxmaxcode ) {

			tab_prefixof(code) = (ushort)oldcode;

			tab_suffixof(code) = finchar;

			free_ent = code+1;

		}

		/*

		 * Remember previous code.

		 */

		oldcode = incode;

	}

	fflush(stdout);

	if(ferror(stdout))

		writeerr();

}

/*

 * TAG( getcode )

 *

 * Read one code from the standard input.  If EOF, return -1.

 * Inputs:

 * 	stdin

 * Outputs:

 * 	code or -1 is returned.

 */

code_int

getcode()

{

	int r_off, bits;

	code_int code;

	static int offset = 0, size = 0;

	static uchar buf[BITS];

	uchar *bp = buf;

	if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {

		/*

		 * If the next entry will be too big for the current code

		 * size, then we must increase the size.  This implies reading

		 * a new buffer full, too.

		 */

		if ( free_ent > maxcode ) {

			n_bits++;

			if ( n_bits == maxbits )

				maxcode = maxmaxcode; /* won't get any bigger now */

			else

				maxcode = MAXCODE(n_bits);

		}

		if ( clear_flg > 0) {

			maxcode = MAXCODE(n_bits = INIT_BITS);

			clear_flg = 0;

		}

		size = fread(buf, 1, n_bits, stdin);

		if (size <= 0)

			return -1;			/* end of file */

		offset = 0;

		/* Round size down to integral number of codes */