compress.c

UNIX、Linux环境下

/*	Copyright (c) 1990, 1991, 1992, 1993 Novell, Inc. All Rights Reserved.	*/
/*	Copyright (c) 1984, 1985, 1986, 1987, 1988, 1989, 1990 Novell, Inc. All Rights Reserved.	*/
/*	  All Rights Reserved  	*/

/*	THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF Novell Inc.	*/
/*	The copyright notice above does not evidence any   	*/
/*	actual or intended publication of such source code.	*/

#ident	"@(#)compress:compress.c	1.4.5.12"
#ident "$Header: compress.c 1.2 91/09/09 $"

/*
 *	Copyright (c) 1986, 1987, 1988, 1989 The Santa Cruz Operation, Inc.
 *	All rights reserved.
 *
 *	Copyright (c) 1986 Regents of the University of California.
 *	All rights reserved.  The Berkeley software License Agreement
 *	specifies the terms and conditions for redistribution.
 *
 *	Copyright (c) 1986, 1987, 1988, Sun Microsystems, Inc.
 *	All Rights Reserved.
 */

/* 
 * Compress - data compression program 
 */
#define	min(a,b)	((a>b) ? b : a)

/*
 * machine variants which require cc -Dmachine:  pdp11, z8000, pcxt
 */

/*
 * Set USERMEM to the maximum amount of physical user memory available
 * in bytes.  USERMEM is used to determine the maximum BITS that can be used
 * for compression.
 *
 * SACREDMEM is the amount of physical memory saved for others; compress
 * will hog the rest.
 */
#ifndef SACREDMEM
#define SACREDMEM	0
#endif

#ifndef USERMEM
# define USERMEM 	450000	/* default user memory */
#endif

#ifdef USERMEM
# if USERMEM >= (433484+SACREDMEM)
#  define PBITS	16
# else
#  if USERMEM >= (229600+SACREDMEM)
#   define PBITS	15
#  else
#   if USERMEM >= (127536+SACREDMEM)
#    define PBITS	14
#   else
#    if USERMEM >= (73464+SACREDMEM)
#     define PBITS	13
#    else
#     define PBITS	12
#    endif
#   endif
#  endif
# endif
# undef USERMEM
#endif /* USERMEM */

#ifdef PBITS		/* Preferred BITS for this memory size */
# ifndef BITS
#  define BITS PBITS
# endif /* BITS */
#endif /* PBITS */

#if BITS == 16
# define HSIZE	69001		/* 95% occupancy */
#endif
#if BITS == 15
# define HSIZE	35023		/* 94% occupancy */
#endif
#if BITS == 14
# define HSIZE	18013		/* 91% occupancy */
#endif
#if BITS == 13
# define HSIZE	9001		/* 91% occupancy */
#endif
#if BITS <= 12
# define HSIZE	5003		/* 80% occupancy */
#endif


/*
 * a code_int must be able to hold 2**BITS values of type int, and also -1
 */
#if BITS > 15
typedef long int	code_int;
#else
typedef int		code_int;
#endif

typedef long int	  count_int;

 typedef	unsigned char	char_type;

char_type magic_header[] = { "\037\235" };	/* 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 */

/*
 * compress.c - File compression ala IEEE Computer, June 1984.
 */
static char rcs_ident[] = "$Header: compress.c 1.2 91/09/09 $";

#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <utime.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>

/* Locally-defined void functions. */
void	compress(),
	output(),
	decompress(),
	writeerr(),
	copystat(),
	cl_block(),
	cl_hash(),
	prratio(),
	do_Pflag(),
	version();
     
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];
unsigned short 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)	((char_type *)(htab))[i]
# define de_stack		((char_type *)&tab_suffixof(1<<BITS))

code_int free_ent = 0;			/* first unused entry */
int exit_stat = 0;			/* per-file status */
int perm_stat = 0;			/* permanent status */
int zflg = 0;				/* zcat called */
int uflg = 0;				/* uncompress called */
int cflg = 0;				/* compress called */

code_int getcode();

int nomagic = 0;	/* Use a 3-byte magic number header, unless old file */
int zcat_flg = 0;	/* Write output on stdout, suppress messages */
int precious = 1;	/* Don't unlink output file on interrupt */
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 int 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;
int rpipe, Pflag=0;		/* Read end of pipe and flag. */
char *ctmp="Comprtmp";		/* Tmp file used in do_Pflag. */
#ifdef DEBUG
int verbose = 0;
int debug = 0;
#endif /* DEBUG */
void (*oldint)();
int bgnd_flag;

int do_decomp = 0;
extern int opterr, optind;
extern char *optarg;

/*****************************************************************
 * TAG( main )
 *
 * 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:
 *	-d:	    If given, decompression is done instead.
 *
 *      -c:         Write output on stdout, don't remove original.
 *
 *      -b:         Parameter limits the max number of bits/code.
 *
 *	-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
 *
 *      -P:         Parameter is the read end of a pipe. File names are read
 *                  from pipe until a Null is read or the pipe is closed.
 *                  Always overwrites the original file.
 *
 *      file ...:   Files to be compressed.  If none specified, and not
 *                  -P option then 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.
 */

main( argc, argv )
register int argc; char **argv;
{
    int overwrite = 0;	/* Do not overwrite unless given -f flag */
    int c, errflg;
    char *tempname = (char *)NULL;
    char **filelist, **fileptr;
    char *tmp_p;
    char *cp;
    struct stat statbuf;
    extern void onintr(), oops();
    long name_max; /* limit on file name length */

    /* This bg check only works for sh. */
    if ( (oldint = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {
	signal ( SIGINT, onintr );
	signal ( SIGSEGV, oops );
    }
    bgnd_flag = oldint != SIG_DFL;
    errflg = 0;
    
    filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
    *filelist = NULL;

    if ((cp = strrchr(argv[0], '/')) != (char *)NULL)
	cp++;
    else 
	cp = argv[0];

    if(strcmp(cp, "uncompress") == 0) {
	do_decomp = 1;
	uflg = 1;
    } else if(strcmp(cp, "zcat") == 0) {
	do_decomp = 1;
	zcat_flg = 1;
	zflg = 1;
    } else cflg = 1;

    /* Argument Processing
     * All flags are optional.
     * -D => debug
     * -V => print Version; debug verbose
     * -d => do_decomp
     * -v => unquiet
     * -f => force overwrite of output file
     * -n => no header: useful to uncompress old files
     * -b maxbits => maxbits.  If -b is specified, then maxbits MUST be
     *	    given also.
     * -c => cat all output to stdout
     * -C => generate output compatible with compress 2.0.
     * -P pipe_desc => Pass file names through a pipe in <stdio.h> defined
     *       BUFSIZ data chunks whose read end is defined by pipe_desc.
     *       Always overwrites original file.
     * If a string is left, must be an input filename.
     */

     if (cflg) { 	/* compress called */
         while ((c = getopt(argc, argv, "b:cCdDfFnP:qvV")) != EOF)
		    switch (c) {
#ifdef DEBUG
		    case 'D':
			debug = 1;
			break;
		    case 'V':
			verbose = 1;
			version();
			break;
#else
		    case 'V':
			version();
			break;
#endif /* DEBUG */
		    case 'v':
			quiet = 0;
			break;
		    case 'd':
			do_decomp = 1;
			break;
		    case 'f':
		    case 'F':
			overwrite = 1;
			force = 1;
			break;
		    case 'n':
			nomagic = 1;
			break;
		    case 'C':
			block_compress = 0;
			break;
		    case 'b':
			maxbits = strtol(optarg, &tmp_p, 10);
			if (*tmp_p != (char)NULL) {
				fprintf(stderr, "Invalid argument \"%s\" for -%c\n", optarg, c);
				errflg++;
				break;
			}
    			if(maxbits < INIT_BITS) maxbits = INIT_BITS;
    			if (maxbits > BITS) maxbits = BITS;
			break;
		    case 'c':
			zcat_flg = 1;
			break;
		    case 'q':
			quiet = 1;
			break;
                    case 'P':
			rpipe = strtol(optarg, &tmp_p, 10);
			if (*tmp_p != (char)NULL) {
				fprintf(stderr, "Invalid argument \"%s\" for -%c\n", optarg, c);
				errflg++;
				break;
			}
			Pflag=1;
                        break;
		    case '?':
			errflg++;
			break;
		}
    	if (errflg) {
#ifdef DEBUG
	    fprintf(stderr,"Usage: compress [-cfvVdD] [-b maxbits] [file ...]\n");
#else
	    fprintf(stderr,"Usage: compress [-cfv] [-b maxbits] [file ...]\n");
#endif /* DEBUG */
	    exit(1);
    	}
    } else if (uflg) { 	/* uncompress */
         while ((c = getopt(argc, argv, "cfP:v")) != EOF)
		    switch (c) {
		    case 'c':
			zcat_flg = 1;
			break;
		    case 'f':
			overwrite = 1;
			break;
                    case 'P':
			rpipe = strtol(optarg, &tmp_p, 10);
			if (*tmp_p != (char)NULL) {
				fprintf(stderr, "Invalid argument \"%s\" for -%c\n", optarg, c);
				errflg++;
				break;
			}
			Pflag=1;
                        break;
		    case 'v':
			quiet = 0;
			break;
		    case '?':
			errflg++;
			break;
		   }
         if (errflg) {
		fprintf(stderr,"Usage: uncompress [-cfv] [file ...]\n");
		exit(1);
    	 }
    } else { 	/* zcat */
         while ((c = getopt(argc, argv, "")) != EOF)
		    switch (c) {
		    case '?':
			errflg++;
			break;
		   }
	if (errflg) {
		fprintf(stderr,"Usage: zcat [file ...]\n");
		exit(1);
    	}
    }

    /* Build input file list */
    for ( ; optind < argc; optind++)
	*fileptr++ = argv[optind];
    *fileptr = NULL;

    maxmaxcode = 1 << maxbits;

    /* Read names from a pipe and compress/decompress overwriting */
    /* the original file.                                         */
    if (Pflag)  do_Pflag();

    if (*filelist != NULL) {
	for (fileptr = filelist; *fileptr; fileptr++) {
	    exit_stat = 0;
	    if (do_decomp) {	/* DECOMPRESSION */
		/* Check for .Z suffix */
		if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") != 0) {
		    /*
		     * No .Z, so tack one on.
		     * (For allocating temporary string, add 3 to 
		     * strlen: 1 for terminating NULL, 2 for ".Z".)
		     */
		    tempname = (char *)malloc(strlen(*fileptr) + 3);
		    if (tempname == (char *) NULL) {
			fprintf(stderr, "%s\n", strerror(errno));
			exit(1);
		    }
		    strcpy(tempname, *fileptr);
		    strcat(tempname, ".Z");
		    *fileptr = tempname;
		}
		/* Open input file */
		if ((freopen(*fileptr, "r", stdin)) == NULL) {
		    perror(*fileptr);
		    perm_stat = 1;
		    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);
			perm_stat = 1;
		        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 */
		if ((ofname = strdup(*fileptr)) == (char *)NULL) {
		    fprintf(stderr, "%s\n", strerror(errno));
		    exit(1);
		}
		ofname[strlen(*fileptr) - 2] = '\0';  /* Strip off .Z */

	    } else {	/* COMPRESSION */
		if (strcmp(*fileptr + strlen(*fileptr) - 2, ".Z") == 0) {
	    	    exit_stat = 1;
		    fprintf(stderr, "%s: already has .Z suffix -- no change\n",
			    *fileptr);
		    continue;
		}