Date: Thu, 5 Feb 87 14:12:35 est
From: David Krowitz <mit-erl!mit-kermit!bert!krowitz@EDDIE.MIT.EDU>


Here is a version of the compress program for the Apollo workstations.
It is pretty much the same as the Alliant version except for the
documentation and the makefile. The packed file starts below the
dashed line.

                                      -- David Krowitz
---------------------------------------------------------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	compress.dir
# This archive created: Thu Feb  5 14:10:15 1987
export PATH; PATH=/bin:$PATH
if test ! -d 'compress.dir'
then
	mkdir 'compress.dir'
fi
cd 'compress.dir'
if test -f 'Makefile'
then
	echo shar: will not over-write existing file "'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
CC=/bin/cc
COMFLAGS=-O
BIN=//bert/users/userlib/com

all :  compress

compress : compress.c 
	$(CC) $(COMFLAGS) -DUSERMEM=512000 -o compress compress.c

install: compress
	/com/cpf compress $(BIN)/compress -r -f -du
	/com/cpf compress.hlp /sys/help/compress.hlp -r -f -du
	/com/crl $(BIN)/uncompress $(BIN)/compress -r
	/com/crl $(BIN)/zcat $(BIN)/compress -r

clean:
	/bin/rm -f *.bak

SHAR_EOF
chmod +x 'Makefile'
fi # end of overwriting check
if test -f 'README'
then
	echo shar: will not over-write existing file "'README'"
else
cat << \SHAR_EOF > 'README'
(Scott Turner)
srt@cs.ucla.edu

I don't know anything about USERMEM.  Makefile refers you here, but there
wasn't a README in the distribution I got. This compiled with a usermem
of 16000, so that should probably work for you.

Compress does a tricky thing:  uncompress & zcat are the same program.  It 
merely checks to see how it was invoked.  So uncompress & zcat are links
to compress.

Unfortunately, to get compress.c under 32K, I had to delete most of the 
comments and some of the ifdefs.  If you want this stuff, write me.

-----------------------------------------------------------------

Some comments on the Apollo port of 'compress':

The compression factor gets better if you compile the program 
with a larger value for USERMEM. USERMEME=512000 seems to give
the best compression ratios. Since 'compress' is a unix program
it does not know about object types. Files which have been 
compressed and then uncompressed will have a default file type
of 'uasc'. You can use the program /com/obty <filename> <type>
to reset the correct object type. 'compress' seems to work well
on 'uasc' (text) and 'obj' (executable) files, although you have
to reset the object type of the 'obj' files. It does not work
with 'rec' (binary data) files for some reason. When the file is
uncompressed, the file is always shorter than its original length.
The program has not been tested with other file types.

                                    -- David Krowitz

mit-erl!mit-kermit!krowitz@eddie.mit.edu
mit-erl!mit-kermit!krowitz@mit-eddie.arpa
david@mit-mc.arpa
(in order of decreasing preference)

SHAR_EOF
chmod +x 'README'
fi # end of overwriting check
if test -f 'compress.1'
then
	echo shar: will not over-write existing file "'compress.1'"
else
cat << \SHAR_EOF > 'compress.1'
.PU
.TH COMPRESS 1 local
.SH NAME
compress, uncompress, zcat  \-  compress and uncompress files
.SH SYNOPSIS
.ll +8
.B compress
[
.B \-d
] [
.B \-f
] [
.B \-F
] [
.B \-q
] [
.B \-c
] [
.B \-b
.I bits
] [
.I "filename \&..."
]
.ll -8
.br
.B uncompress
[
.B \-f
] [
.B \-q
] [
.B \-c
] [
.I "filename \&..."
]
.br
.B zcat
[
.I "filename \&..."
]
.SH DESCRIPTION
Compresses the specified files or standard input.
Each file is replaced by a file with the extension
.B "\&.Z,"
but only if the file got smaller.
If no files are specified,
the compression is applied to the standard input
and is written to standard output
regardless of the results.
Compressed files can be restored
to their original form by specifying the
.B \-d
option, or by running
.I uncompress
(linked to
.IR compress ),
on the 
.B "\&.Z"
files or the standard input.
.PP
If the output file exists, it will not be overwritten unless the
.B \-f
flag is given.  If
.B \-f
is not specified and
.I compress
is run in the foreground,
the user is prompted
as to whether the file should be overwritten.
.PP
If the
.B \-F
flag is given, all files specified are replaced with
.B "\&.Z"
files \- even if the file didn't get smaller.
.PP
When file names are given, the ownership (if run by root), modes, accessed
and modified times are maintained between the file and its 
.B "\&.Z"
version.  In this respect,
.I compress
can be used for archival purposes, yet can still be used with
.IR make "(1)"
after uncompression.
.PP
The
.B \-c
option causes the results of the compress/uncompress operation to be written
to stdout; no files are changed.  The
.I zcat
program is the same as specifying
.B \-c
to
.I uncompress
(all files are unpacked and written to stdout).
.PP
.I Compress
uses the modified Lempel-Ziv algorithm described in
"A Technique for High Performance Data Compression",
Terry A. Welch,
.I "IEEE Computer"
Vol 17, No 6 (June 1984), pp 8-19.
Common substrings in the file are first replaced by 9-bit codes 257 and up.
When code 512 is reached, the algorithm switches to 10-bit codes and
continues to use more bits until the
.I bits
limit as specified by the
.B \-b
flag is reached (default 16).
.I Bits
must be between 9 and 16.  The default can be changed in the source to allow
.I compress
to be run on a smaller machine.
.PP
After the
.I bits
limit is reached,
.I compress
periodically checks the compression ratio.  If it is increasing,
.I compress
continues to use the codes that were previously found in the file.  However,
if the compression ratio decreases,
.I compress
discards the table of substrings and rebuilds it from scratch.  This allows
the algorithm to adapt to the next "block" of the file.
.PP
A two byte magic number is prepended to the file
to ensure that neither uncompression of random text nor recompression of 
compressed text are attempted.  In addition, the
.I bits
specified during
.I compress
is written to the file so that the
.B \-b
flag can be omitted for
.IR uncompress \.
.PP
.ne 8
The amount of compression obtained depends on the size of the
input file, the amount of
.I bits
per code, and the distribution of character substrings.
Typically, text files, such as C programs,
are reduced by 50\-60%.
Compression is generally much better than that achieved by
Huffman coding (as used in
.IR pack ),
or adaptive Huffman coding
.RI ( compact ),
and takes less time to compute.
.PP
.PP
After each file is compressed, a message is printed giving the percentage of
the input file that has been saved by compression.  This message is
suppressed when the
.B \-q
(quiet) flag is given.
.PP
The exit status is normally 0;
if the last file gets bigger after compression, the exit status is 2;
if an error occurs, the exit status is 1.
.SH "SEE ALSO"
compact(1), pack(1)
.SH "DIAGNOSTICS"
Usage: compress [-dfFqc] [-b maxbits] [file ...]
.in +8
Invalid options were specified on the command line.
.in -8
Missing maxbits
.in +8
Maxbits must follow
.BR \-b \.
.in -8
Unknown flag: 
.I "\'x\';"
.in +8
Invalid flags were specified on the command line.
.in -8
.IR file :
not in compressed format
.in +8
The specified file has not been compressed.
.in -8
.IR file :
compressed with 
.I xx
bits, can only handle 
.I yy
bits
.in +8
The specified file was compressed by a compress program that could handle
more 
.I bits
than the current compress program.  Recompress the file with a smaller
.IR bits \.
.in -8
.IR file :
already has .Z suffix -- no change
.in +8
Cannot compress a file that has a ".Z" suffix.
.IR mv "(1)"
the file to a different name and try again.
.in -8
.IR file :
filename too long to tack on .Z
.in +8
The specified file cannot be compressed because its filename is longer than
12 characters.
.IR mv "(1)"
the file to a different name and try again.  This message does not occur on
4.2BSD systems.
.in -8
.I file
already exists; do you wish to overwrite (y or n)?
.in +8
Respond "y" if you want the output file to be replaced; "n" if you want it
to be left alone.
.in -8
.IR file :
.in +8
This message fragment is written during the processing of a file.
.in -8
Compression: 
.I "xx.xx%"
.in +8
This message fragment gives the percentage of the input file that has been
saved by compression.
.in -8
-- not a regular file: unchanged
.in +8
This message fragment is written when the input file is not a regular file.
The input file is left unchanged.
.in -8
-- has 
.I xx 
other links: unchanged
.in +8
This message fragment is written when the input file has links.  The input
file is left unchanged.  See
.IR ln "(1)"
for more information.
.in -8
-- file unchanged
.in +8
This message fragment is written when no savings are achieved by
compression.  The input file is left unchanged.
.in -8
-- replaced with 
.I file
.in +8
This message fragment is written when a file has been sucessfully
compressed/uncompressed.
.in -8
SHAR_EOF
chmod +x 'compress.1'
fi # end of overwriting check
if test -f 'compress.c'
then
	echo shar: will not over-write existing file "'compress.c'"
else
cat << \SHAR_EOF > 'compress.c'
/* 
 * 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 interdata               /* (Perkin-Elmer) */
#define SIGNED_COMPARE_SLOW    /* signed compare is slower than unsigned */
#endif

#ifdef pdp11
# define BITS  12      /* max bits/code for 16-bit machine */
# define NO_UCHAR      /* also if "unsigned char" functions as signed char */
# undef USERMEM 
#endif /* pdp11 */     /* don't forget to compile with -i */

#ifdef z8000
# define BITS  12
# undef vax            /* weird preprocessor */
# undef USERMEM 
#endif /* z8000 */

#ifdef pcxt
# define BITS   12
# undef USERMEM
#endif /* pcxt */

#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

#ifdef M_XENIX                 /* Stupid compiler can't handle arrays with */
# if BITS == 16                        /* more than 65535 bytes - so we fake
it */
#  define XENIX_16
# else
#  if BITS > 13                        /* Code only handles BITS = 12, 13, or
16 */
#   define BITS        13
#  endif
# endif
#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

#ifdef SIGNED_COMPARE_SLOW
typedef unsigned long int count_int;
typedef unsigned short int count_short;
#else
typedef long int         count_int;
#endif

#ifdef NO_UCHAR
 typedef char  char_type;
#else
 typedef       unsigned char   char_type;
#endif /* UCHAR */
char_type magic_header[] = { "\037\235" };     /* 1F 9D */

#ifdef apollo
#define MAXNAMELEN 31					/* due to aegis mapping for uppercase : 32-1 */
#endif

/* 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.
 *
 * 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)
 *
 * $Header: compress.c,v 1.1 85/08/05 19:19:52 root Exp $
 * $Log:       compress.c,v $
 * Revision 1.1  85/08/05  19:19:52  root
 * Initial revision
 * 
 * Revision 5.1  86/05/13  Scott R. Turner
 * Cleaned up for Apollo version.
 */

static char rcs_ident[] = "$Header: compress.c,v 1.1 85/08/05 19:19:52 root Exp $";

#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>

#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 */
#ifdef COMPATIBLE              /* But wrong! */
# define MAXCODE(n_bits)       (1 << (n_bits) - 1)
#else
# define MAXCODE(n_bits)       ((1 << (n_bits)) - 1)
#endif /* COMPATIBLE */

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;

#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;

code_int getcode();

Usage() {
fprintf(stderr,"Usage: compress [-dfvcV] [-b maxbits] [file ...]\n");
}
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 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 [100];
int (*bgnd_flag)();

int do_decomp = 0;

/*****************************************************************
 * TAG( main )
 */

main( argc, argv )
register int argc; char **argv;
{
    int overwrite = 0; /* Do not overwrite unless given -f flag */
    char tempname[100];
    char **filelist, **fileptr;
    char *cp, *rindex(), *malloc();
    struct stat statbuf;
    extern onintr(), oops();


    if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {
       signal ( SIGINT, onintr );
       signal ( SIGSEGV, oops );
    }

#ifdef COMPATIBLE
    nomagic = 1;       /* Original didn't have a magic number */
#endif /* COMPATIBLE */

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

    if((cp = rindex(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;
    }

#ifdef BSD4_2
    /* 4.2BSD dependent - take it out if not */
    setlinebuf( stderr );
#endif /* BSD4_2 */

    /* Argument Processing
     */
    for (argc--, argv++; argc > 0; argc--, argv++) {
       if (**argv == '-') {    /* A flag argument */
           while (*++(*argv)) {        /* Process all flags in this arg */
               switch (**argv) {
                   case 'V':
                       version();
                       break;
                   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':
                       if (!ARGVAL()) {
                           fprintf(stderr, "Missing maxbits\n");
                           Usage();
                           exit(1);
                       }
                       maxbits = atoi(*argv);
                       goto nextarg;
                   case 'c':
                       zcat_flg = 1;
                       break;
                   case 'q':
                       quiet = 1;
                       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;
               }
               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         /* Short filenames */
               if ((cp=rindex(ofname,'/')) != NULL)    cp++;
               else                                    cp = ofname;
#ifdef apollo
               if (strlen(cp) > (MAXNAMELEN-2)) {
#else
               if (strlen(cp) > 12) {
#endif
                   fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
                   continue;
               }
#endif  /* BSD4_2              Long filenames allowed */
               strcat(ofname, ".Z");
           }
           /* Check for overwrite of existing file */
           if (overwrite == 0 && zcat_flg == 0) {
               if (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);
                       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();
           else                        decompress();
           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();
               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);
               }
           }
           decompress();
       }
    }
    exit(exit_stat);
}

static int offset;
long int in_count = 1;                 /* length of input */
long int bytes_out;                    /* length of compressed output */
long int out_count = 0;                        /* # of codes output (for
debugging) */

/*
 * compress stdin to stdout
 *
 */

compress() {
    register long fcode;
    register code_int i = 0;
    register int c;
    register code_int ent;
    register int disp;
    register code_int hsize_reg;
    register int hshift;

#ifndef COMPATIBLE
    if (nomagic == 0) {
       putchar(magic_header[0]); putchar(magic_header[1]);
       putchar((char)(maxbits | block_compress));
       if(ferror(stdout))
               writeerr();
    }
#endif /* COMPATIBLE */

    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 *= 2L )
       hshift++;
    hshift = 8 - hshift;               /* set hash code range bound */

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

#ifdef SIGNED_COMPARE_SLOW
    while ( (c = getchar()) != (unsigned) EOF ) {
#else
    while ( (c = getchar()) != EOF ) {
#endif
       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;
#ifdef SIGNED_COMPARE_SLOW
       if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
#else
       if ( free_ent < maxmaxcode ) {
#endif
           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) {
       fprintf( stderr, "Compression: " );
       prratio( stderr, in_count-bytes_out, in_count );
    }
    if(bytes_out > in_count)   /* exit(2) if no savings */
       exit_stat = 2;
    return;
}

/*****************************************************************
 * TAG( output )
 */

static char buf[BITS];

#ifndef vax
char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
#endif /* vax */

output( code )
code_int  code;
{

    /*
     * On the VAX, it is important to have the register declarations
     * in exactly the order given, or the asm will break.
     */
    register int r_off = offset, bits= n_bits;
    register char * bp = buf;

    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);
           }
       }
    } 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 );
       if( ferror( stdout ) )
               writeerr();
    }
}

/*
 */

decompress() {
    register char_type *stackp;
    register int finchar;
    register code_int code, oldcode, incode;

    /*
     * 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) = (char_type)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
        */
#ifdef SIGNED_COMPARE_SLOW
       while ( ((unsigned long)code) >= ((unsigned long)256) ) {
#else
       while ( code >= 256 ) {
#endif
           *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) = (unsigned short)oldcode;
           tab_suffixof(code) = finchar;
           free_ent = code+1;
       } 
       /*
        * Remember previous code.
        */
       oldcode = incode;
    }
    fflush( stdout );
    if(ferror(stdout))
       writeerr();
}

/*****************************************************************
 * TAG( getcode )
 *
 */

code_int
getcode() {
    /*
     * On the VAX, it is important to have the register declarations
     * in exactly the order given, or the asm will break.
     */
    register code_int code;
    static int offset = 0, size = 0;
    static char_type buf[BITS];
    register int r_off, bits;
    register char_type *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 */
       size = (size << 3) - (n_bits - 1);
    }
    r_off = offset;
    bits = n_bits;
       /*
        * Get to the first byte.
        */
       bp += (r_off >> 3);
       r_off &= 7;
       /* Get first part (low order bits) */
#ifdef NO_UCHAR
       code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
#else
       code = (*bp++ >> r_off);
#endif /* NO_UCHAR */
       bits -= (8 - r_off);
       r_off = 8 - r_off;              /* now, offset into code word */
       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
       if ( bits >= 8 ) {
#ifdef NO_UCHAR
           code |= (*bp++ & 0xff) << r_off;
#else
           code |= *bp++ << r_off;
#endif /* NO_UCHAR */
           r_off += 8;
           bits -= 8;
       }
       /* high order bits. */
       code |= (*bp & rmask[bits]) << r_off;
    offset += n_bits;

    return code;
}

char *
rindex(s, c)           /* For those who don't have it in libc.a */
register char *s, c;
{
       char *p;
       for (p = NULL; *s; s++)
           if (*s == c)
               p = s;
       return(p);
}

writeerr()
{
    perror ( ofname );
    unlink ( ofname );
    exit ( 1 );
}

copystat(ifname, ofname)
char *ifname, *ofname;
{
    struct stat statbuf;
    int mode;
    time_t timep[2];

    fclose(stdout);
    if (stat(ifname, &statbuf)) {              /* Get stat on input file */
       perror(ifname);
       return;
    }
    if ((statbuf.st_mode & S_IFMT/*0170000*/) != S_IFREG/*0100000*/) {
       if(quiet)
               fprintf(stderr, "%s: ", ifname);
       fprintf(stderr, " -- not a regular file: unchanged");
       exit_stat = 1;
    } else if (statbuf.st_nlink > 1) {
       if(quiet)
               fprintf(stderr, "%s: ", ifname);
       fprintf(stderr, " -- has %d other links: unchanged",
               statbuf.st_nlink - 1);
       exit_stat = 1;
    } else if (exit_stat == 2 && (!force)) { /* No compression: remove file.Z
*/
       if(!quiet)
               fprintf(stderr, " -- file unchanged");
    } else {                   /* ***** Successful Compression ***** */
       exit_stat = 0;
       mode = statbuf.st_mode & 07777;
       if (chmod(ofname, mode))                /* Copy modes */
           perror(ofname);
       chown(ofname, statbuf.st_uid, statbuf.st_gid);  /* Copy ownership */
       timep[0] = statbuf.st_atime;
       timep[1] = statbuf.st_mtime;
       utime(ofname, timep);   /* Update last accessed and modified times */
       if (unlink(ifname))     /* Remove input file */
           perror(ifname);
       if(!quiet)
               fprintf(stderr, " -- replaced with %s", ofname);
       return;         /* Successful return */
    }

    /* Unsuccessful return -- one of the tests failed */
    if (unlink(ofname))
       perror(ofname);
}
/*
 * This routine returns 1 if we are running in the foreground and stderr
 * is a tty.
 */
foreground()
{
       if(bgnd_flag) { /* background? */
               return(0);
       } else {                        /* foreground */
               if(isatty(2)) {         /* and stderr is a tty */
                       return(1);
               } else {
                       return(0);
               }
       }
}

onintr ( )
{
    unlink ( ofname );
    exit ( 1 );
}

oops ( )       /* wild pointer -- assume bad input */
{
    if ( do_decomp == 1 ) 
       fprintf ( stderr, "uncompress: corrupt input\n" );
    unlink ( ofname );
    exit ( 1 );
}

cl_block ()            /* table clear for block compress */
{
    register long int rat;

    checkpoint = in_count + CHECK_GAP;
    if(in_count > 0x007fffff) {        /* shift will overflow */
       rat = bytes_out >> 8;
       if(rat == 0) {          /* Don't divide by zero */
           rat = 0x7fffffff;
       } else {
           rat = in_count / rat;
       }
    } else {
       rat = (in_count << 8) / bytes_out;      /* 8 fractional bits */
    }
    if ( rat > ratio ) {
       ratio = rat;
    } else {
       ratio = 0;
       cl_hash ( (count_int) hsize );
       free_ent = FIRST;
       clear_flg = 1;
       output ( (code_int) CLEAR );
    }
}

cl_hash(hsize)         /* reset code table */
       register count_int hsize;
{
       register j;
       register long k = hsize;
       register count_int *htab_p = htab+hsize;
       register long i;
       register long m1 = -1;

       i = hsize - 16;
       do {                            /* might use Sys V memset(3) here */
               *(htab_p-16) = m1;
               *(htab_p-15) = m1;
               *(htab_p-14) = m1;
               *(htab_p-13) = m1;
               *(htab_p-12) = m1;
               *(htab_p-11) = m1;
               *(htab_p-10) = m1;
               *(htab_p-9) = m1;
               *(htab_p-8) = m1;
               *(htab_p-7) = m1;
               *(htab_p-6) = m1;
               *(htab_p-5) = m1;
               *(htab_p-4) = m1;
               *(htab_p-3) = m1;
               *(htab_p-2) = m1;
               *(htab_p-1) = m1;
               htab_p -= 16;
       } while ((i -= 16) >= 0);
       for ( i += 16; i > 0; i-- )
               *--htab_p = m1;
}

prratio(stream, num, den)
FILE *stream;
long int num, den;
{
       register int q;                 /* Doesn't need to be long */

       if(num > 214748L) {             /* 2147483647/10000 */
               q = num / (den / 10000L);
       } else {
               q = 10000L * num / den;         /* Long calculations, though */
       }
       if (q < 0) {
               putc('-', stream);
               q = -q;
       }
       fprintf(stream, "%d.%02d%%", q / 100, q % 100);
}

version()
{
       fprintf(stderr, "%s\n", rcs_ident);
       fprintf(stderr, "Options: ");
#ifdef vax
       fprintf(stderr, "vax, ");
#endif
#ifdef NO_UCHAR
       fprintf(stderr, "NO_UCHAR, ");
#endif
#ifdef SIGNED_COMPARE_SLOW
       fprintf(stderr, "SIGNED_COMPARE_SLOW, ");
#endif
#ifdef COMPATIBLE
       fprintf(stderr, "COMPATIBLE, ");
#endif
#ifdef BSD4_2
       fprintf(stderr, "BSD4_2, ");
#endif
       fprintf(stderr, "BITS = %d\n", BITS);
}

SHAR_EOF
chmod +x 'compress.c'
fi # end of overwriting check
if test -f 'compress.hlp'
then
	echo shar: will not over-write existing file "'compress.hlp'"
else
cat << \SHAR_EOF > 'compress.hlp'
1.0;compress (compress/uncompress file), revision 1.0 87/02/03
COMPRESS, uncompress, zcat  \-  compress and uncompress files

usage:  COMPRESS [-d] [-f] [-F] [-q] [-c] [-b bits] [filename]
        UNCOMPRESS [-f] [-q] [-c] [filename]
        ZCAT [filename]


DESCRIPTION
-----------

The 'compress' program compresses the specified files or standard input.
Each file is replaced by a file with the extension '.Z', but only if the
file got smaller. If no files are specified, the compression is applied
to the standard input and is written to standard output regardless of the
results. Compressed files can be restored to their original form by
specifying the '-d' option, or by running the 'uncompress' program
(a link to the 'compress' program ), on the '.Z' files or the standard
input.

If the output file exists, it will not be overwritten unless the '-f'
flag is given.  If '-f' is not specified and 'compress' is run in the
foreground, the user is prompted as to whether the file should be
overwritten.

If the '-F' flag is given, all files specified are replaced with '.Z'
files - even if the file didn't get smaller.

When file names are given, the ownership (if run by root), modes, accessed
and modified times are maintained between the file and its '.Z' version.
In this respect, 'compress' can be used for archival purposes, yet can
still be used with 'make' after uncompression.

The '-c' option causes the results of the compress/uncompress operation
to be written to stdout; no files are changed.  The 'zcat' program is the
same as specifying '-c' to the 'uncompress' program (all files are unpacked
and written to stdout).

'Compress' uses the modified Lempel-Ziv algorithm described in "A Technique
for High Performance Data Compression", Terry A. Welch,  "IEEE Computer"
Vol 17, No 6 (June 1984), pp 8-19. Common substrings in the file are first
replaced by 9-bit codes 257 and up. When code 512 is reached, the algorithm
switches to 10-bit codes and continues to use more bits until the 'bits'
limit as specified by the '-b' flag is reached (default 16). 'Bits' must
be between 9 and 16.  The default can be changed in the source to allow
'compress' to be run on a smaller machine.

After the 'bits' limit is reached, 'compress' periodically checks the
compression ratio.  If it is increasing, 'compress' continues to use the
codes that were previously found in the file.  However, if the compression
ratio decreases, 'compress' discards the table of substrings and rebuilds
it from scratch.  This allows the algorithm to adapt to the next "block" of
the file.

A two byte magic number is prepended to the file to ensure that neither
uncompression of random text nor recompression of compressed text are
attempted.  In addition, the 'bits' specified during 'compress' is written
to the file so that the '-b' flag can be omitted for 'uncompress'.

The amount of compression obtained depends on the size of the input file,
the amount of 'bits' per code, and the distribution of character substrings.
Typically, text files, such as C programs, are reduced by 50\-60%.
Compression is generally much better than that achieved by Huffman coding
(as used in 'pack'), or adaptive Huffman coding ( 'compact' ), and takes
less time to compute.

After each file is compressed, a message is printed giving the percentage of
the input file that has been saved by compression.  This message is
suppressed when the '-q' (quiet) flag is given.

The exit status is normally 0; if the last file gets bigger after compression,
the exit status is 2; if an error occurs, the exit status is 1.


SEE ALSO: compact(1), pack(1)

SHAR_EOF
chmod +x 'compress.hlp'
fi # end of overwriting check
if test -f 'compress.old'
then
	echo shar: will not over-write existing file "'compress.old'"
else
cat << \SHAR_EOF > 'compress.old'
/* 
 * 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 interdata               /* (Perkin-Elmer) */
#define SIGNED_COMPARE_SLOW    /* signed compare is slower than unsigned */
#endif

#ifdef pdp11
# define BITS  12      /* max bits/code for 16-bit machine */
# define NO_UCHAR      /* also if "unsigned char" functions as signed char */
# undef USERMEM 
#endif /* pdp11 */     /* don't forget to compile with -i */

#ifdef z8000
# define BITS  12
# undef vax            /* weird preprocessor */
# undef USERMEM 
#endif /* z8000 */

#ifdef pcxt
# define BITS   12
# undef USERMEM
#endif /* pcxt */

#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

#ifdef M_XENIX                 /* Stupid compiler can't handle arrays with */
# if BITS == 16                        /* more than 65535 bytes - so we fake
it */
#  define XENIX_16
# else
#  if BITS > 13                        /* Code only handles BITS = 12, 13, or
16 */
#   define BITS        13
#  endif
# endif
#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

#ifdef SIGNED_COMPARE_SLOW
typedef unsigned long int count_int;
typedef unsigned short int count_short;
#else
typedef long int         count_int;
#endif

#ifdef NO_UCHAR
 typedef char  char_type;
#else
 typedef       unsigned char   char_type;
#endif /* UCHAR */
char_type magic_header[] = { "\037\235" };     /* 1F 9D */
#ifdef UCLA_CS
char_type Pmagic_header[] = { "\357\276" };     /* EF BE */
#endif /* UCLA_CS */

#ifdef apollo
#define MAXNAMELEN 31					/* due to aegis mapping for uppercase : 32-1 */
#endif

/* 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.
 *
 * 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)
 *
 * $Header: compress.c,v 1.1 85/08/05 19:19:52 root Exp $
 * $Log:       compress.c,v $
 * Revision 1.1  85/08/05  19:19:52  root
 * Initial revision
 * 
 * Revision 5.1  86/05/13  Scott R. Turner
 * Cleaned up for Apollo version.
 *
 * Revision 4.0  85/07/30  12:50:00  joe
 * Removed ferror() calls in output routine on every output except first.
 * Prepared for release to the world.
 * 
 * Revision 3.6  85/07/04  01:22:21  joe
 * Remove much wasted storage by overlaying hash table with the tables
 * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
 * computations.  Fixed dump_tab() DEBUG routine.
 *
 * Revision 3.5  85/06/30  20:47:21  jaw
 * Change hash function to use exclusive-or.  Rip out hash cache.  These
 * speedups render the megamemory version defunct, for now.  Make decoder
 * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
 *
 * Revision 3.4  85/06/27  12:00:00  ken
 * Get rid of all floating-point calculations by doing all compression ratio
 * calculations in fixed point.
 *
 * Revision 3.3  85/06/24  21:53:24  joe
 * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
 * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
 *
 * Revision 3.2  85/06/06  21:53:24  jaw
 * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
 * Default to "quiet" output (no compression statistics).
 *
 * Revision 3.1  85/05/12  18:56:13  jaw
 * Integrate decompress() stack speedups (from early pointer mods by McKie).
 * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
 * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase 
 * output byte count by magic number size.
 * 
 * Revision 3.0   84/11/27  11:50:00  petsd!joe
 * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
 * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
 * unsigned compares on Perkin-Elmer.  Fixed foreground check.
 *
 * Revision 2.7   84/11/16  19:35:39  ames!jaw
 * Cache common hash codes based on input statistics; this improves
 * performance for low-density raster images.  Pass on #ifdef bundle
 * from Turkowski.
 *
 * Revision 2.6   84/11/05  19:18:21  ames!jaw
 * Vary size of hash tables to reduce time for small files.
 * Tune PDP-11 hash function.
 *
 * Revision 2.5   84/10/30  20:15:14  ames!jaw
 * Junk chaining; replace with the simpler (and, on the VAX, faster)
 * double hashing, discussed within.  Make block compression standard.
 *
 * Revision 2.4   84/10/16  11:11:11  ames!jaw
 * Introduce adaptive reset for block compression, to boost the rate
 * another several percent.  (See mailing list notes.)
 *
 * Revision 2.3   84/09/22  22:00:00  petsd!joe
 * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
 * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
 *
 * Revision 2.2   84/09/18  14:12:21  ames!jaw
 * Fold in news changes, small machine typedef from thomas,
 * #ifdef interdata from joe.
 *
 * Revision 2.1   84/09/10  12:34:56  ames!jaw
 * Configured fast table lookup for 32-bit machines.
 * This cuts user time in half for b <= FBITS, and is useful for news batching
 * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
 * added signal catcher [plus beef in writeerr()] to delete effluvia.
 *
 * Revision 2.0   84/08/28  22:00:00  petsd!joe
 * Add check for foreground before prompting user.  Insert maxbits into
 * compressed file.  Force file being uncompressed to end with ".Z".
 * Added "-c" flag and "zcat".  Prepared for release.
 *
 * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
 * Will only compress regular files (no directories), added a magic number
 * header (plus an undocumented -n flag to handle old files without headers),
 * added -f flag to force overwriting of possibly existing destination file,
 * otherwise the user is prompted for a response.  Will tack on a .Z to a
 * filename if it doesn't have one when decompressing.  Will only replace
 * file if it was compressed.
 *
 * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
 * Removed scanargs(), getopt(), added .Z extension and unlimited number of
 * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
 * (-D -d -v -b 12), or combination thereof.  Modes and other status is
 * copied with copystat().  -O bug for 4.2 seems to have disappeared with
 * 1.8.
 *
 * Revision 1.8  84/08/09  23:15:00  joe
 * Made it compatible with vax version, installed jim's fixes/enhancements
 *
 * Revision 1.6  84/08/01  22:08:00  joe
 * Sped up algorithm significantly by sorting the compress chain.
 *
 * Revision 1.5  84/07/13  13:11:00  srd
 * Added C version of vax asm routines.  Changed structure to arrays to
 * save much memory.  Do unsigned compares where possible (faster on
 * Perkin-Elmer)
 *
 * Revision 1.4  84/07/05  03:11:11  thomas
 * Clean up the code a little and lint it.  (Lint complains about all
 * the regs used in the asm, but I'm not going to "fix" this.)
 *
 * Revision 1.3  84/07/05  02:06:54  thomas
 * Minor fixes.
 *
 * Revision 1.2  84/07/05  00:27:27  thomas
 * Add variable bit length output.
 *
 */
static char rcs_ident[] = "$Header: compress.c,v 1.1 85/08/05 19:19:52 root Exp $";

#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>

#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 */
#ifdef COMPATIBLE              /* But wrong! */
# define MAXCODE(n_bits)       (1 << (n_bits) - 1)
#else
# define MAXCODE(n_bits)       ((1 << (n_bits)) - 1)
#endif /* COMPATIBLE */

#ifdef XENIX_16
count_int htab0[8192];
count_int htab1[8192];
count_int htab2[8192];
count_int htab3[8192];
count_int htab4[8192];
count_int htab5[8192];
count_int htab6[8192];
count_int htab7[8192];
count_int htab8[HSIZE-65536];
count_int * htab[9] = {
       htab0, htab1, htab2, htab3, htab4, htab5, htab6, htab7, htab8 };

#define htabof(i)      (htab[(i) >> 13][(i) & 0x1fff])
unsigned short code0tab[16384];
unsigned short code1tab[16384];
unsigned short code2tab[16384];
unsigned short code3tab[16384];
unsigned short code4tab[16384];
unsigned short * codetab[5] = {
       code0tab, code1tab, code2tab, code3tab, code4tab };

#define codetabof(i)   (codetab[(i) >> 14][(i) & 0x3fff])

#else  /* Normal machine */
count_int htab [HSIZE];
unsigned short codetab [HSIZE];
#define htabof(i)      htab[i]
#define codetabof(i)   codetab[i]
#endif /* XENIX_16 */
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)
#ifdef XENIX_16
# define tab_suffixof(i)       ((char_type *)htab[(i)>>15])[(i) & 0x7fff]
# define de_stack              ((char_type *)(htab2))
#else  /* Normal machine */
# define tab_suffixof(i)       ((char_type *)(htab))[i]
# define de_stack              ((char_type *)&tab_suffixof(1<<BITS))
#endif /* XENIX_16 */

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

code_int getcode();

Usage() {
#ifdef DEBUG
fprintf(stderr,"Usage: compress [-dDVfc] [-b maxbits] [file ...]\n");
}
int debug = 0;
#else
fprintf(stderr,"Usage: compress [-dfvcV] [-b maxbits] [file ...]\n");
}
#endif /* DEBUG */
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 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 [100];
#ifdef DEBUG
int verbose = 0;
#endif /* DEBUG */
int (*bgnd_flag)();

int do_decomp = 0;

/*****************************************************************
 * 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
 *
 *     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.
 */

main( argc, argv )
register int argc; char **argv;
{
    int overwrite = 0; /* Do not overwrite unless given -f flag */
    char tempname[100];
    char **filelist, **fileptr;
    char *cp, *rindex(), *malloc();
    struct stat statbuf;
    extern onintr(), oops();


    if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {
       signal ( SIGINT, onintr );
       signal ( SIGSEGV, oops );
    }

#ifdef COMPATIBLE
    nomagic = 1;       /* Original didn't have a magic number */
#endif /* COMPATIBLE */

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

    if((cp = rindex(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;
    }

#ifdef BSD4_2
    /* 4.2BSD dependent - take it out if not */
    setlinebuf( stderr );
#endif /* BSD4_2 */

    /* 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.
     * 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) {
#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':
                       if (!ARGVAL()) {
                           fprintf(stderr, "Missing maxbits\n");
                           Usage();
                           exit(1);
                       }
                       maxbits = atoi(*argv);
                       goto nextarg;
                   case 'c':
                       zcat_flg = 1;
                       break;
                   case 'q':
                       quiet = 1;
                       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;
               }
               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         /* Short filenames */
               if ((cp=rindex(ofname,'/')) != NULL)    cp++;
               else                                    cp = ofname;
#ifdef apollo
               if (strlen(cp) > (MAXNAMELEN-2)) {
#else
               if (strlen(cp) > 12) {
#endif
                   fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
                   continue;
               }
#endif  /* BSD4_2              Long filenames allowed */
               strcat(ofname, ".Z");
           }
           /* Check for overwrite of existing file */
           if (overwrite == 0 && zcat_flg == 0) {
               if (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);
                       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 /* DEBUG */
               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);
}

static int offset;
long int in_count = 1;                 /* length of input */
long int bytes_out;                    /* length of compressed output */
long int 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.
 */

compress() {
    register long fcode;
    register code_int i = 0;
    register int c;
    register code_int ent;
#ifdef XENIX_16
    register code_int disp;
#else  /* Normal machine */
    register int disp;
#endif
    register code_int hsize_reg;
    register int hshift;

#ifndef COMPATIBLE
    if (nomagic == 0) {
       putchar(magic_header[0]); putchar(magic_header[1]);
       putchar((char)(maxbits | block_compress));
       if(ferror(stdout))
               writeerr();
    }
#endif /* COMPATIBLE */

    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 *= 2L )
       hshift++;
    hshift = 8 - hshift;               /* set hash code range bound */

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

#ifdef SIGNED_COMPARE_SLOW
    while ( (c = getchar()) != (unsigned) EOF ) {
#else
    while ( (c = getchar()) != EOF ) {
#endif
       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;
#ifdef SIGNED_COMPARE_SLOW
       if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
#else
       if ( free_ent < maxmaxcode ) {
#endif
           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;
    return;
}

/*****************************************************************
 * 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).  Use the VAX insv instruction to insert each
 * code in turn.  When the buffer fills up empty it and start over.
 */

static char buf[BITS];

#ifndef vax
char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
#endif /* vax */

output( code )
code_int  code;
{
#ifdef DEBUG
    static int col = 0;
#endif /* DEBUG */

    /*
     * On the VAX, it is important to have the register declarations
     * in exactly the order given, or the asm will break.
     */
    register int r_off = offset, bits= n_bits;
    register char * bp = buf;

#ifdef DEBUG
       if ( verbose )
           fprintf( stderr, "%5d%c", code,
                   (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
#endif /* DEBUG */
    if ( code >= 0 ) {
#ifdef vax
       /* VAX DEPENDENT!! Implementation on other machines is below.
        *
        * Translation: Insert BITS bits from the argument starting at
        * offset bits from the beginning of buf.
        */
       0;      /* Work around for pcc -O bug with asm and if stmt */
       asm( "insv      4(ap),r11,r10,(r9)" );
#else /* not a vax */
/* 
 * 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;
#endif /* vax */
       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 /* DEBUG */
       }
    } 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 /* DEBUG */
       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.
 */

decompress() {
    register char_type *stackp;
    register int finchar;
    register code_int code, oldcode, incode;

    /*
     * 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) = (char_type)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
        */
#ifdef SIGNED_COMPARE_SLOW
       while ( ((unsigned long)code) >= ((unsigned long)256) ) {
#else
       while ( code >= 256 ) {
#endif
           *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) = (unsigned short)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() {
    /*
     * On the VAX, it is important to have the register declarations
     * in exactly the order given, or the asm will break.
     */
    register code_int code;
    static int offset = 0, size = 0;
    static char_type buf[BITS];
    register int r_off, bits;
    register char_type *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 */
       size = (size << 3) - (n_bits - 1);
    }
    r_off = offset;
    bits = n_bits;
#ifdef vax
    asm( "extzv   r10,r9,(r8),r11" );
#else /* not a vax */
       /*
        * Get to the first byte.
        */
       bp += (r_off >> 3);
       r_off &= 7;
       /* Get first part (low order bits) */
#ifdef NO_UCHAR
       code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
#else
       code = (*bp++ >> r_off);
#endif /* NO_UCHAR */
       bits -= (8 - r_off);
       r_off = 8 - r_off;              /* now, offset into code word */
       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
       if ( bits >= 8 ) {
#ifdef NO_UCHAR
           code |= (*bp++ & 0xff) << r_off;
#else
           code |= *bp++ << r_off;
#endif /* NO_UCHAR */
           r_off += 8;
           bits -= 8;
       }
       /* high order bits. */
       code |= (*bp & rmask[bits]) << r_off;
#endif /* vax */
    offset += n_bits;

    return code;
}

char *
rindex(s, c)           /* For those who don't have it in libc.a */
register char *s, c;
{
       char *p;
       for (p = NULL; *s; s++)
           if (*s == c)
               p = s;
       return(p);
}

#ifdef DEBUG
printcodes()
{
    /*
     * Just print out codes from input file.  For debugging.
     */
    code_int code;
    int col = 0, bits;

    bits = n_bits = INIT_BITS;
    maxcode = MAXCODE(n_bits);
    free_ent = ((block_compress) ? FIRST : 256 );
    while ( ( code = getcode() ) >= 0 ) {
       if ( (code == CLEAR) && block_compress ) {
           free_ent = FIRST - 1;
           clear_flg = 1;
       }
       else if ( free_ent < maxmaxcode )
           free_ent++;
       if ( bits != n_bits ) {
           fprintf(stderr, "\nChange to %d bits\n", n_bits );
           bits = n_bits;
           col = 0;
       }
       fprintf(stderr, "%5d%c", code, (col+=6) >= 74 ? (col = 0, '\n') : ' '
);
    }
    putc( '\n', stderr );
    exit( 0 );
}

code_int sorttab[1<<BITS];     /* sorted pointers into htab */

dump_tab()     /* dump string table */
{
    register int i, first;
    register ent;
#define STACK_SIZE     15000
    int stack_top = STACK_SIZE;
    register c;

    if(do_decomp == 0) {       /* compressing */
       register int flag = 1;

       for(i=0; i<hsize; i++) {        /* build sort pointers */
               if((long)htabof(i) >= 0) {
                       sorttab[codetabof(i)] = i;
               }
       }
       first = block_compress ? FIRST : 256;
       for(i = first; i < free_ent; i++) {
               fprintf(stderr, "%5d: \"", i);
               de_stack[--stack_top] = '\n';
               de_stack[--stack_top] = '"';
               stack_top = in_stack((htabof(sorttab[i])>>maxbits)&0xff, 
                                     stack_top);
               for(ent=htabof(sorttab[i]) & ((1<<maxbits)-1);
                   ent > 256;
                   ent=htabof(sorttab[ent]) & ((1<<maxbits)-1)) {
                       stack_top = in_stack(htabof(sorttab[ent]) >> maxbits,
                                               stack_top);
               }
               stack_top = in_stack(ent, stack_top);
               fwrite( &de_stack[stack_top], 1, STACK_SIZE-stack_top, stderr);
               stack_top = STACK_SIZE;
       }
   } else if(!debug) { /* decompressing */

       for ( i = 0; i < free_ent; i++ ) {
          ent = i;
          c = tab_suffixof(ent);
          if ( isascii(c) && isprint(c) )
              fprintf( stderr, "%5d: %5d/'%c'  \"",
                          ent, tab_prefixof(ent), c );
          else
              fprintf( stderr, "%5d: %5d/\\%03o \"",
                          ent, tab_prefixof(ent), c );
          de_stack[--stack_top] = '\n';
          de_stack[--stack_top] = '"';
          for ( ; ent != NULL;
                  ent = (ent >= FIRST ? tab_prefixof(ent) : NULL) ) {
              stack_top = in_stack(tab_suffixof(ent), stack_top);
          }
          fwrite( &de_stack[stack_top], 1, STACK_SIZE - stack_top, stderr );
          stack_top = STACK_SIZE;
       }
    }
}

int
in_stack(c, stack_top)
       register c, stack_top;
{
       if ( (isascii(c) && isprint(c) && c != '\\') || c == ' ' ) {
           de_stack[--stack_top] = c;
       } else {
           switch( c ) {
           case '\n': de_stack[--stack_top] = 'n'; break;
           case '\t': de_stack[--stack_top] = 't'; break;
           case '\b': de_stack[--stack_top] = 'b'; break;
           case '\f': de_stack[--stack_top] = 'f'; break;
           case '\r': de_stack[--stack_top] = 'r'; break;
           case '\\': de_stack[--stack_top] = '\\'; break;
           default:
               de_stack[--stack_top] = '0' + c % 8;
               de_stack[--stack_top] = '0' + (c / 8) % 8;
               de_stack[--stack_top] = '0' + c / 64;
               break;
           }
           de_stack[--stack_top] = '\\';
       }
       return stack_top;
}
#endif /* DEBUG */

writeerr()
{
    perror ( ofname );
    unlink ( ofname );
    exit ( 1 );
}

copystat(ifname, ofname)
char *ifname, *ofname;
{
    struct stat statbuf;
    int mode;
    time_t timep[2];

    fclose(stdout);
    if (stat(ifname, &statbuf)) {              /* Get stat on input file */
       perror(ifname);
       return;
    }
    if ((statbuf.st_mode & S_IFMT/*0170000*/) != S_IFREG/*0100000*/) {
       if(quiet)
               fprintf(stderr, "%s: ", ifname);
       fprintf(stderr, " -- not a regular file: unchanged");
       exit_stat = 1;
    } else if (statbuf.st_nlink > 1) {
       if(quiet)
               fprintf(stderr, "%s: ", ifname);
       fprintf(stderr, " -- has %d other links: unchanged",
               statbuf.st_nlink - 1);
       exit_stat = 1;
    } else if (exit_stat == 2 && (!force)) { /* No compression: remove file.Z
*/
       if(!quiet)
               fprintf(stderr, " -- file unchanged");
    } else {                   /* ***** Successful Compression ***** */
       exit_stat = 0;
       mode = statbuf.st_mode & 07777;
       if (chmod(ofname, mode))                /* Copy modes */
           perror(ofname);
       chown(ofname, statbuf.st_uid, statbuf.st_gid);  /* Copy ownership */
       timep[0] = statbuf.st_atime;
       timep[1] = statbuf.st_mtime;
       utime(ofname, timep);   /* Update last accessed and modified times */
       if (unlink(ifname))     /* Remove input file */
           perror(ifname);
       if(!quiet)
               fprintf(stderr, " -- replaced with %s", ofname);
       return;         /* Successful return */
    }

    /* Unsuccessful return -- one of the tests failed */
    if (unlink(ofname))
       perror(ofname);
}
/*
 * This routine returns 1 if we are running in the foreground and stderr
 * is a tty.
 */
foreground()
{
       if(bgnd_flag) { /* background? */
               return(0);
       } else {                        /* foreground */
               if(isatty(2)) {         /* and stderr is a tty */
                       return(1);
               } else {
                       return(0);
               }
       }
}

onintr ( )
{
    unlink ( ofname );
    exit ( 1 );
}

oops ( )       /* wild pointer -- assume bad input */
{
    if ( do_decomp == 1 ) 
       fprintf ( stderr, "uncompress: corrupt input\n" );
    unlink ( ofname );
    exit ( 1 );
}

cl_block ()            /* table clear for block compress */
{
    register long int rat;

    checkpoint = in_count + CHECK_GAP;
#ifdef DEBUG
       if ( debug ) {
               fprintf ( stderr, "count: %ld, ratio: ", in_count );
               prratio ( stderr, in_count, bytes_out );
               fprintf ( stderr, "\n");
       }
#endif /* DEBUG */

    if(in_count > 0x007fffff) {        /* shift will overflow */
       rat = bytes_out >> 8;
       if(rat == 0) {          /* Don't divide by zero */
           rat = 0x7fffffff;
       } else {
           rat = in_count / rat;
       }
    } else {
       rat = (in_count << 8) / bytes_out;      /* 8 fractional bits */
    }
    if ( rat > ratio ) {
       ratio = rat;
    } else {
       ratio = 0;
#ifdef DEBUG
       if(verbose)
               dump_tab();     /* dump string table */
#endif
       cl_hash ( (count_int) hsize );
       free_ent = FIRST;
       clear_flg = 1;
       output ( (code_int) CLEAR );
#ifdef DEBUG
       if(debug)
               fprintf ( stderr, "clear\n" );
#endif /* DEBUG */
    }
}

cl_hash(hsize)         /* reset code table */
       register count_int hsize;
{
#ifndef XENIX_16       /* Normal machine */
       register count_int *htab_p = htab+hsize;
#else
       register j;
       register long k = hsize;
       register count_int *htab_p;
#endif
       register long i;
       register long m1 = -1;

#ifdef XENIX_16
    for(j=0; j<=8 && k>=0; j++,k-=8192) {
       i = 8192;
       if(k < 8192) {
               i = k;
       }
       htab_p = &(htab[j][i]);
       i -= 16;
       if(i > 0) {
#else
       i = hsize - 16;
#endif
       do {                            /* might use Sys V memset(3) here */
               *(htab_p-16) = m1;
               *(htab_p-15) = m1;
               *(htab_p-14) = m1;
               *(htab_p-13) = m1;
               *(htab_p-12) = m1;
               *(htab_p-11) = m1;
               *(htab_p-10) = m1;
               *(htab_p-9) = m1;
               *(htab_p-8) = m1;
               *(htab_p-7) = m1;
               *(htab_p-6) = m1;
               *(htab_p-5) = m1;
               *(htab_p-4) = m1;
               *(htab_p-3) = m1;
               *(htab_p-2) = m1;
               *(htab_p-1) = m1;
               htab_p -= 16;
       } while ((i -= 16) >= 0);
#ifdef XENIX_16
       }
    }
#endif
       for ( i += 16; i > 0; i-- )
               *--htab_p = m1;
}

prratio(stream, num, den)
FILE *stream;
long int num, den;
{
       register int q;                 /* Doesn't need to be long */

       if(num > 214748L) {             /* 2147483647/10000 */
               q = num / (den / 10000L);
       } else {
               q = 10000L * num / den;         /* Long calculations, though */
       }
       if (q < 0) {
               putc('-', stream);
               q = -q;
       }
       fprintf(stream, "%d.%02d%%", q / 100, q % 100);
}

version()
{
       fprintf(stderr, "%s\n", rcs_ident);
       fprintf(stderr, "Options: ");
#ifdef vax
       fprintf(stderr, "vax, ");
#endif
#ifdef NO_UCHAR
       fprintf(stderr, "NO_UCHAR, ");
#endif
#ifdef SIGNED_COMPARE_SLOW
       fprintf(stderr, "SIGNED_COMPARE_SLOW, ");
#endif
#ifdef XENIX_16
       fprintf(stderr, "XENIX_16, ");
#endif
#ifdef COMPATIBLE
       fprintf(stderr, "COMPATIBLE, ");
#endif
#ifdef DEBUG
       fprintf(stderr, "DEBUG, ");
#endif
#ifdef BSD4_2
       fprintf(stderr, "BSD4_2, ");
#endif
       fprintf(stderr, "BITS = %d\n", BITS);
}

SHAR_EOF
chmod +x 'compress.old'
fi # end of overwriting check
cd ..
#	End of shell archive
exit 0