/***************************************************************************
 * comptst.c - File compression ala IEEE Computer, June 1984.
 *
 * Modifications & Additions:
 *
 * UPDATED FOR VAX VMS usage of RMS BLOCK I/O.
 *  24-FEB-1988 - R.E.Newman. Jr.
 * Added Documentation from LZCMP software from DECUS tapes
 *  27-MAY-1988 - R.E.Newman. Jr.   V1.2
 *
 * 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 [-i] [-d] [-b maxbits] ifile [ofile]
 *
 * Switches:
 *	-d:	    If given, decompression is done instead.
 *	-b:	    Bits to use (DEFAULTS: 16 for VAX, 13 for micro)
 *	-i:	    Inhibit Deletion After Comp/Decomp
 *	-n:	    Print no Diagnostic Messages.
 *
 * Files:
 *	none	    print usage.
 *	1	    if -d switch then     decompress   to stdout
 *		    else if ending  in .Z decompresses to file without .Z
 *		    else if not end in .Z compresses   to file with    .Z
 *      2           compresses or decompresses files according to -d switch
 *
 * Notes:
 *	The actual extension can be either .Z for .z (case is folded)
 *	On VMS the extension searched/created is _Y instead of .Z
 *	If one filename is given then the input is deleted after comp/decomp
 *	unless the "-i" option is given.
 *
 *      If the CALLSUB compile option is defined, COMPTST.C compiles as
 *      a subroutine, and can be called from a main program. The exit
 *	status is returned like a function. The routine to call is "cmprss".
 *	BOTH arguments are specified by REFERENCE. "argcc" is the argument
 *	count. "argv" is a pointer to a string which is delimited with
 *	nulls for each ascii parameter. The "first" argv argument is not the
 *      name of the call name, but the first parameter in the call line.
 *
 *
 * 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.

LZW compression algorithm

	This section is abstracted from Terry Welch's article
	referenced below.  The algorithm builds a string
	translation table that maps substrings in the input
	into fixed-length codes.  The compress algorithm may
	be described as follows:

	  1. Initialize table to contain single-character
	     strings.
	  2. Read the first character.  Set <w> (the prefix
	     string) to that character.
	  3. (step): Read next input character, K.
 	  4. If at end of file, output code(<w>); exit.
	  5. If <w>K is in the string table:
		Set <w> to <w>K; goto step 3.
	  6. Else <w>K is not in the string table.
		Output code(<w>);
		Put <w>K into the string table;
		Set <w> to K; Goto step 3.

	"At each execution of the basic step an acceptable input
	string <w> has been parsed off.  The next character K is
	read and the extended string <w>K is tested to see if it
	exists in the string table.  If it is there, then the
	extended string becomes the parsed string <w> and the
	step is repeated.  If <w>K is not in the string table,
	then it is entered, the code for the successfully
	parsed string <w> is put out as comprssed data, the
	character K becomes the beginning of the next string,
	and the step is repeated."

	The decompression algorithm translates each received
	code into a prefix string and extension [suffix] character.
	The extension character is stored (in a push-down stack),
	and the prefix translated again, until the prefix is a
	single character, which completes decompression of this
	code.  The entire code is then output by popping the
	stack.

	"An update to the string table is made for each code received
	(except the first one).  When a code has been translated,
	its final character is used as the extension character,
	combined with the prior string, to add a new string to
	the string table.  This new string is assigned a unique
	code value, which is the same code that the compressor
	assigned to that string.  In this way, the decompressor
	incrementally reconstructs the same string table that
	the decompressor used.... Unfortunately ... [the algorithm]
	does not work for an abnormal case.

	The abnormal case occurs whenever an input character string
	contains the sequence K<w>K<w>K, where K<w> already
	appears in the compressor string table."

	The decompression algorithm, augmented to handle
	the abnormal case, is as follows:

	  1. Read first input code;
	     Store in CODE and OLDcode;
	     With CODE = code(K), output(K);  FINchar = K;
	  2. Read next code to CODE; INcode = CODE;
	     If at end of file, exit;
	  3. If CODE not in string table (special case) then
		Output(FINchar);
		CODE = OLDcode;
		INcode = code(OLDcode, FINchar);

	  4. If CODE == code(<w>K) then
		Push K onto the stack;
		CODE == code(<w>);
		Goto 4.

	  5. If CODE == code(K) then
		Output K;
		FINchar = K;

	  6. While stack not empty
		Output top of stack;
		Pop stack;

	  7. Put OLDcode,K into the string table.
	     OLDcode = INcode;
	     Goto 2.

	The algorithm as implemented here introduces two additional
	complications.

	The actual codes are transmitted using a variable-length
	encoding.  The lowest-level routines increase the number
	of bits in the code when the largest possible code is
	transmitted.

	Periodically, the algorithm checks that compression is
	still increasing.  If the ratio of input bytes to output
	bytes decreases, the entire process is reset.  This can
	happen if the characteristics of the input file change.

Authors

	The algorithm is from "A Technique for High Performance
	Data Compression."  Terry A. Welch. IEEE Computer Vol 17,
	No. 6 (June 1984), pp 8-19.

	This revision is by Martin Minow.

	Unix Compress authors are as follows:

           	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)
                Dave Wecker             (decvax!decwrl!cookie.dec.com!wecker)

 ***************************************************************************/
#include <string.h>
#include <stdlib.h>
#ifdef VMS
/* Define VMS Version of compress. */
#   module COMPRESS V1-31
/* Define RMS I/O Block Opens/Reads/Writes/Close */
#   define RMS
#endif

#ifdef MCH_AMIGA
#define BITS 		13	        /* max bits/code */
#else
#define BITS		16
#endif

#if BITS == 16
#define HSIZE		69001
#endif
#if BITS == 15
#define HSIZE		35023
#endif
#if BITS == 14
#define HSIZE		18013
#endif
#if BITS == 13
#define HSIZE		9001
#endif
#if BITS <= 12
#define HSIZE		5003
#endif

#if BITS > 15
typedef long		code_int;
#else
typedef short		code_int;
#endif

typedef long		count_int;
typedef	unsigned char	char_type;
char_type		magic_header[] = { "\037\237" };	/* 1F 9F */

#define BIT_MASK	0x1f		/* Defines for third byte of header */
#define BLOCK_MASK	0x80
#define INIT_BITS	9		/* initial number of bits/code */
#ifdef VMS
#   include stdio
#else
#   include <stdio.h>
#endif
#ifdef RMS
#   include "RMSACC.H"
#endif

int	    n_bits;			/* number of bits/code */
int	    maxbits;	/* initialized to BITS -user settable max # bits/code */
code_int    maxcode;			/* maximum code, given n_bits */
code_int    maxmaxcode;	/* 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]

/*
 * 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;	/* Init. in Compress/Decompress -first unused entry */
    int	    inlen;			/* use for length of *ifile */
#ifdef VMS
    int	    exit_stat = 1;
    char    *infptr,*strrchr();		/* find last ';' with strrchr */
#else
    int	    exit_stat = 0;
#endif
code_int    getcode();

Usage() {
    fprintf(stderr,"Usage: compress [-i] [-d] [-b maxbits] ifile [ofile]\n");
    }
#ifdef CALLSUB
# define NXTARG (argv=zscan(argv))
# define ARGPTR argv

/* Zero Scan routine */
char	*zscan(cptr)
char *cptr;
{

    while ((*cptr != '\0') && (*cptr != ' '))
	cptr++;
    return (++cptr);
}

#else
# define NXTARG (++argv)
# define ARGPTR *argv
#endif
/*
 * block compression parameters -- after all codes are used up,
 * and compression rate changes, start over.
 */

int	    block_compress; /* = BLOCK_MASK -Init. Before call to compress() */
int	    clear_flg;
long	    ratio;
#define	    CHECK_GAP	10000	/* ratio check interval */
count_int   checkpoint;

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

char	    do_decomp;		/* Initialized below in main */
char	    do_unlink;		/* '' */
char	    no_unlink;		/* '' */
char	    no_print;		/* '' */

#ifdef RMS
struct RAB *irb,*orb;
struct FAB *ifb,*ofb;
struct chrblk chb = 0;
struct chrblk ocb = {{0,0},{0,0},0,0,512,512,FAB$C_SEQ,0,FAB$C_FIX,0,
    0,1,FAB$M_CBT,0};
/* Define Output File as FIXED,SEQUENTIAL,512 BYTE BLOCK RECORDS */
unsigned char getchd[2];
#else
FILE	    *ifp,*ofp;
#endif

char	    *ifile, *ofile, outnam[128];

#ifndef CALLSUB
main( argcc, argv )
    int argcc;
    char **argv;
#else
/* Make call to comprss as a subroutine
** status is returned as a function. */
int cmprss( argcc, argvs )
    int *argcc;
    char *argvs;
#endif
{
    int argc;
#ifndef CALLSUB

    argc=argcc-1;   /* Decrement for Call Name */
    argv++;	    /* Move Past Call Name */
#else
    char *argv;

    argv=argvs;
    argc=(*argcc);
#endif

#ifndef RMS
    ifp = (FILE *)stdin;
    ofp = (FILE *)stdout;
#endif
    /* Argument Processing
     * All flags are optional.
     * -d => do_decomp
     */
    if(argc < 1)	/* If nothing given give him usage */
	{
	    Usage();
#ifndef CALLSUB
	    exit(exit_stat);
#else
	    return(exit_stat);
#endif
	};

    maxbits = BITS;		/* Initialize to BITS */
    ifile = NULL; ofile = NULL;	/* Zero Input & Output String File Pointers */
    do_decomp = 0; do_unlink = 0; no_unlink = 0;
    no_print = 0;		/* Set Default to Print Any Info */

    for (; argc > 0; argc--, NXTARG)
	{
	    if (*ARGPTR == '-')
		{	/* A flag argument */
		    switch (((ARGPTR)[1])|' ')	/* Convert to lowercase. */
		    {
		    case 'd':
			do_decomp = 1;
			break;

		    case 'b':
			NXTARG;
			if (--argc <= 0)
			    {
				fprintf(stderr, "Missing maxbits param; ");
				Usage();
				error(0);
			    }
			maxbits = atoi(ARGPTR);
			break;
		    case 'n':
			/* Don't Print any diagnostics. */
			no_print=1;
			break;

		    case 'i':
			/* Inhibit Deletion of file if one name given */
			no_unlink=1;
			break;

		    default:
			fprintf(stderr, "Unknown flag: '%c'; ", (ARGPTR)[1]);
			Usage();
			error(0);
		    }
		}
	    else
		{ /* a file argument */
		    if (!ifile)
			ifile = ARGPTR;
		    else
			if (!ofile)
			    ofile = ARGPTR;
			else
			    {
				fprintf(stderr,"Too many files specified.\n");
				error(0);
			    }
		}
	}

    if (maxbits < INIT_BITS)
	maxbits = INIT_BITS;
    if (maxbits > BITS)
	maxbits = BITS;
    maxmaxcode = 1 << maxbits;		/* Initialize from maxbits */

    if(!no_unlink)do_unlink = 1;	/* Inhibit Input File Deletion. */
    /* If only one file.. figure out what to do by extension */
    if (ifile && !ofile)
	{
#ifdef VMS
/* If *.*_Y extension then decompress on VAX/VMS */
	    inlen = ((infptr=strrchr(ifile,';')) != 0) ?
		(infptr - ifile) : (strlen(ifile));
	    if ((ifile[inlen-1]|' ') == 'y' &&
		ifile[inlen-2] == '_')
#else
/* If *.z extension then decompress on other system. */
	    inlen = strlen(ifile);
	    if ((ifile[inlen-1]|' ') == 'z' &&
		ifile[inlen-2] == '.')
#endif
		{
		    do_decomp = 1;
		    strncpy(outnam,ifile,inlen-2);
		}
	    else
		{
		    do_decomp = 0;
		    strncpy(outnam,ifile,inlen);
#ifdef VMS
		    strcat(outnam,"_Y");
#else
		    strcat(outnam,".Z");
#endif
		}
	    ofile = outnam;
	}
#ifndef RMS
    if (ifile)
	{
	    if (!(ifp = fopen(ifile,"r")))
		{
#else
    if (!ifile || ((ifb=ropen(ifile,0,F_READ|F_BLOCK,&chb,0))==0) ||
	((irb=rconn(ifb,32))==0))
	{
#endif
	    fprintf(stderr,"Can't open input file.\n");
	    error(0);
	}
#ifndef RMS
	}
    if (ofile)
	{
	    if (!(ofp = fopen(ofile,"w")))
		{
#else
    if (do_decomp == 0)
	{
	    if ( !ofile ||
		((ofb=ropen(ofile,0,F_CREAT|F_WRITE|F_BLOCK,&ocb,0))==0) ||
		((orb=rconn(ofb,16))==0) )
		{
#endif
		    fprintf(stderr,"Can't open output file.\n");
		    error(0);
		};
	};
    if (do_decomp == 0)
	{
	    block_compress = BLOCK_MASK;
	    compress();
	}
    else
	{
	/* Check the magic number */
#ifndef	    RMS
	    if ((getc(ifp) != (magic_header[0] & 0xFF))
		    || (getc(ifp) != (magic_header[1] & 0xFF)))
#else
	    if (((rsread(irb,getchd,2,0)&1)==0) ||
		(getchd[0]!= (magic_header[0] & 0xFF)) ||
		(getchd[1]!= (magic_header[1] & 0xFF)))
#endif
		{
		    fprintf(stderr, "Input file not in compressed format.\n");
		    error(0);
		}
#ifndef RMS
	    maxbits	= getc(ifp);
            {
                int i;
                for (i = 0; i < 40; i++) getc(ifp);
            }
#else
	    rsread(irb,getchd,1,0);
/* Read In Maximum Bits */
	    maxbits=getchd[0];
/* Read In Characteristics Block */
	    exit_stat=rsread(irb,&chb,sizeof(struct chrblk),0);
	    if((exit_stat&1)==0)error(0);
	    if (chb.chr$b_sver > 1)
	    {
		fprintf(stderr, "Input file in new compressed format.\n");
		error(0);
	    };
	    if (((ofb=ropen(ofile,0,F_CREAT|F_WRITE|F_BLOCK,&chb,0))==0) ||
		((orb=rconn(ofb,32))==0))
		{
		    fprintf(stderr,"Can't create output file.\n");
		    error(0);
		};

#endif
	    block_compress	= maxbits & BLOCK_MASK;
	    maxbits	       &= BIT_MASK;
	    maxmaxcode		= 1 << maxbits;
	    if(maxbits > BITS)
		{
		fprintf(stderr,
		"Input file compressed with %d bits, can only handle %d bits\n",
		maxbits, BITS);
		error(0);
		}
	    decompress();
	}

    if(exit_stat ==2)
	error(0); /* Error exit if some error occurs, i.e. Print Ratio > 1. */
#ifndef RMS
    if (ifile) fclose(ifp);
    if (ofile) fclose(ofp);
#else
    if (irb)
	{
	    exit_stat=rdisc(irb);
/* Set Bit To Delete File If REQUESTED */
	    if(do_unlink)ifb->fab$l_fop|=FAB$M_DLT;
	    exit_stat=rclose(ifb,0);
	}
    if (orb)
	{
	    exit_stat=rflush(orb);if((exit_stat&1)==0)error(1);
	    exit_stat=rdisc(orb);
	    exit_stat=rclose(ofb,((do_decomp==0) ? 0 :&chb));
	    if((exit_stat&1)==0)
#ifndef CALLSUB
		exit(exit_stat);
#else
		return(exit_stat);
#endif
	}
#endif
#ifndef RMS
    if (do_unlink)
#   ifdef VMS
	delete(ifile);
#   else
	unlink(ifile);
#   endif
#endif
#ifndef CALLSUB
    exit(exit_stat);
#else
    return(exit_stat);
#endif
}

static int  offset;
long	    in_count = 1;		/* length of input */
long	    bytes_out;			/* length of compressed output */
#ifdef VMS
long	    blks_out;			/* block input/output counts */
long	    blks_in;
#endif
long	    out_count = 0;		/* # of codes output (for debugging) */

char	*pratio(num,den)
    long	num,den;
{
    register int q;
    static  char    ratio_str[40];

    if (num > 214748L)
	q = num / (den / 10000L);
    else
	q = 10000L * num / den;
    if (q < 0)
	sprintf(ratio_str,"-%3d.%02d%%",(-q)/100,(-q)%100);
    else
	sprintf(ratio_str," %3d.%02d%%",q/100,q%100);
    return ratio_str;
}
/*
 * compress ifp to ofp / VAX ifb to ofb
 *
 * 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.
 *
 * Actually do compression.  Terminology (and algorithm):
 *
 * Assume the input string is "abcd", we have just processed "ab" and
 * read 'c'.  At this point, a "prefix code" will be assigned to "ab".
 * Search in the prefix:character memory (either the "fast memory" or
 * the hash-code table) for the code followed by this character.  If
 * found, assign the code found to the "prefix code" and read the
 * next character.  If not found, output the current prefix code,
 * generate a new prefix code and store "old_prefix:char" in the
 * table with "new_prefix" as its definition.
 *
 * Naming conventions:
 *   code	a variable containing a prefix code
 *   c or char	a variable containing a character
 *
 * There are three tables that are searched (dependent on compile-time
 * and execution time considerations):
 *   fast	Direct table-lookup -- requires a huge amount of physical
 *		(non-paged) memory, but is very fast.
 *   hash	Hash-coded table-lookup.
 *   cache	A "look-ahead" cache for the hash table that optimizes
 *		searching for the most frequent character.  This considerably
 *		speeds up processing for raster-images (for example) at
 *		a modest amount of memory.
 * Structures are used to hold the actual tables to simplify organization
 * of the program.
 *
 * Subroutines:
 *    compress()	performs data compression on an input datastream.
 */

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

#ifndef RMS
    putc(magic_header[0],ofp); putc(magic_header[1],ofp);
    putc((char)(maxbits | block_compress),ofp);
    if(ferror(ofp))
	error(1);
#else
    exit_stat=rswrit(orb,magic_header,2);
    if((exit_stat&1)!=0)
	getchd[0]=(char)(maxbits | block_compress);
    if((exit_stat&1)!=0)
	exit_stat=rswrit(orb,getchd,1);
    if((exit_stat&1)!=0)
	exit_stat=rswrit(orb,&chb,sizeof(struct chrblk));
    if((exit_stat&1)==0)
	error(1);
#endif
    offset	= 0;
#ifdef RMS
/* includes 3-bytes + chrblk header mojo */
    bytes_out	= 3 + sizeof (struct chrblk);
#else
/* includes 3-byte header mojo */
    bytes_out	= 3;
#endif
    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 );
#ifdef RMS
    ent = ((exit_stat=rsread(irb,getchd,1,0))&1) ? getchd[0] : -1;
    if((exit_stat&1)==0)
	error(0);
#else
    ent	= getc(ifp);
#endif
    hshift = 0;
    for ( fcode = (long) HSIZE;  fcode < 65536L; fcode *= 2L )
	hshift++;
    hshift = 8 - hshift;		/* set hash code range bound */
    cl_hash();				/* clear hash table */
#ifndef RMS
    while ((c = getc(ifp)) != EOF)
	{
#else
    while (((exit_stat=rsread(irb,getchd,1,0))&1)!=0)
	{
	    c=getchd[0];
#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)
		    goto nomatch;	/* empty slot */
	    disp = HSIZE - i;		/* secondary hash (after G. Knott) */
	    if ( i == 0 )
		disp = 1;
probe:
	    if ((i -= disp) < 0)
		i += HSIZE;
	    if (htabof(i) == fcode)
		{
		    ent = codetabof (i);
		    continue;
		}
	    if ((long)htabof(i) > 0)
		goto probe;
nomatch:
	    output((code_int) ent);
	    out_count++;
	    ent = c;
	    if (free_ent < maxmaxcode)
		{
		    codetabof(i) = free_ent++;	    /* code -> hashtable */
		    htabof (i)	 = fcode;
		}
	    else
		if ((count_int)in_count >= checkpoint && block_compress)
		    cl_block ();
	}
#ifdef RMS
    if(exit_stat!=RMS$_EOF)
	error(0);
#endif

    /* Put out the final code. */
    output((code_int)ent);
    out_count++;
    output((code_int)-1);

    /* Print out stats on stderr (if we aren't going to the console) */
    if (ofile && (no_print==0))
	{
	    fprintf(stderr,
		"Compressed %s\nfrom %8ld bytes  to %8ld bytes  (%s)\n",
		ifile,in_count,bytes_out,pratio(bytes_out,in_count));
#ifdef VMS
	    blks_out = (bytes_out + 511) / 512;
	    blks_in = (in_count + 511) / 512;
	    fprintf(stderr,"or   %8ld blocks to %8ld blocks (%s).\n",
		blks_in,blks_out,pratio(blks_out,blks_in));
#endif
	}

    /* exit(2) if no savings */
    if(bytes_out > in_count)
	exit_stat = 2;
    return;
}

/*
 * 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 ofp.
 * 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 VMS
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};
#else
code_int lib$extzv();
#endif

output(code)
code_int  code;
{
    register int    r_off = offset,
		    bits  = n_bits;
    register char   *bp   = buf;

    if ( code >= 0 )
	{
#ifdef VMS
	    lib$insv(&code,&offset,&bits,bp);
#else
	/* Get to the first byte. */
	    bp    += (r_off >> 3);
	    r_off &= 7;

	/*Since code always >= 8 bits, only 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
	    offset += n_bits;
	    if ( offset == (n_bits << 3) )
		{
		    bp		= buf;
		    bits	= n_bits;
		    bytes_out  += bits;
#ifndef RMS
		    do
			putc(*bp++,ofp);
		    while(--bits);
#else
		    exit_stat=rswrit(orb,bp,bits,0);
		    if((exit_stat&1)==0)
			error(1);
		    bp+=bits;bits=0;
#endif
		    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 )
			{
#ifndef RMS
			    if( fwrite( buf, 1, n_bits, ofp ) != n_bits)
				error(1);
#else
			    if(((exit_stat=rswrit(orb,buf,n_bits))&1)==0)
				error(1);
#endif
			    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 )
#ifndef RMS
		fwrite( buf, 1, (offset + 7) / 8, ofp);
#else
	    if(((exit_stat=rswrit(orb,buf,(offset + 7) / 8))&1)==0)
		error(1);
#endif
	    bytes_out += (offset + 7) / 8;
	    offset     = 0;
#ifndef RMS
	    fflush( ofp );
	    if(ferror(ofp))
		error(1);
#endif
	}
}

/*
 * Decompress ifp to ofp.  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);
    clear_flg = 0;
    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)
	return;	    /* EOF already? */
#ifndef RMS
    putc((char)finchar,ofp);	    /* first code must be 8 bits = char */
    if(ferror(ofp))
	error(1);   /* Crash if can't write */
#else
    if(((exit_stat=rswrit(orb,&finchar,1))&1)==0)
	error(1);
#endif
    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)
			break; /* O, untimely death! */
		}
	    incode = code;

	/* Special case for KwKwK string. */
	    if ( code >= free_ent )
		{
		    *stackp++ = finchar;
		    code = oldcode;
		}

	/* Generate output characters in reverse order */
	    while ( code >= 256 )
		{
		    *stackp++ = tab_suffixof(code);
		    code = tab_prefixof(code);
		}
	    *stackp++ = finchar = tab_suffixof(code);

	/* And put them out in forward order */
	    do
#ifndef RMS
		putc (*--stackp,ofp);
#else
		if(((exit_stat=rswrit(orb,--stackp,1))&1)==0)
		    error(1);
/* error on write */
#endif
	    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;
	}
#ifndef RMS
    fflush(ofp);
    if(ferror(ofp))
	error(1);
#endif
    /* Print out stats on stderr (if we aren't going to the console) */
    if (ofile && (no_print == 0))
	fprintf(stderr,"Decompressed %s\n",ofile);
}

/*
 * Read one code from the standard input.  If EOF, return -1.
 * Inputs:
 * 	ifp
 * Outputs:
 * 	code or -1 is returned.
 */

code_int getcode()
{
    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;
		    else
			maxcode = MAXCODE(n_bits);
		}
	    if ( clear_flg > 0)
		{
		    maxcode = MAXCODE(n_bits = INIT_BITS);
		    clear_flg = 0;
		}
#ifndef RMS
	    size = fread( buf, 1, n_bits, ifp );
	    if ( size <= 0 )
		return -1;		/* end of file */
#else
	    exit_stat=rsread(irb,buf,n_bits,&size);
	    if (size <= 0)
		return -1;		/* end of file */
#endif
	    offset = 0;

	/* Round size down to integral number of codes */
	    size = (size << 3) - (n_bits - 1);
	}
    r_off = offset;
    bits  = n_bits;
#if VMS
    code  = lib$extzv (&offset, &bits, bp);
#else
    /* Get to the first byte. */
    bp	   += (r_off >> 3);
    r_off  &= 7;

    /* Get first part (low order bits) */
    code    = (*bp++ >> r_off);
    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 )
	{
	    code  |= *bp++ << r_off;
	    r_off += 8;
	    bits  -= 8;
	}

    /* high order bits. */
    code   |= (*bp & rmask[bits]) << r_off;
#endif
    offset += n_bits;

    return code;
}

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

    checkpoint = in_count + CHECK_GAP;

    if (in_count > 0x007fffffL)
	{	/* shift will overflow */
	    rat = bytes_out >> 8L;
	    if(rat == 0)
		rat = 0x7fffffffL;
	    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();
	    free_ent  = FIRST;
	    clear_flg = 1;
	    output ((code_int) CLEAR);
	}
}

cl_hash()
{		/* reset code table */
    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;
}

error(doerr)
{
    if (doerr)
	perror ("Write error.");
#ifndef RMS
    if (ifp)
	fclose(ifp);
    if (ofp)
	fclose(ofp);
# ifndef CALLSUB
    exit(1^exit_stat);
# else
    return(exit_stat);
# endif
#else
    if (irb)
	{
	    rdisc(irb);	/* Disconnect Input RAB */
	    rclose(ifb,0);  /* Close Input FAB */
	}
    if (orb)
	{
	    rdisc(orb);
	    ofb->fab$l_fop|=FAB$M_DLT;	/* delete file on close */
	    rclose(ofb,0);
	}
# ifndef CALLSUB
    exit(exit_stat);
# else
    return(exit_stat);
# endif
#endif
}