/*% cc -O -n % -o sq
*/
#include <stdio.h>
#define TRUE 1
#define rewind(c) fseek(c,0L,0);				       /* 1.7 */
#define FALSE 0
#define ERROR (-1)
#define PATHLEN 312	/* Number of characters allowed in pathname */
#define ALTNAME "sq.out"

/* Definitions and external declarations */
#define RECOGNIZE 0xFF76	/* unlikely pattern */
/* *** Stuff for first translation module *** */
#define DLE 0x90


/* *** Stuff for second translation module *** */
#define SPEOF 256	/* special endfile token */
#define NUMVALS 257	/* 256 data values plus SPEOF*/
/* Definitions and external declarations */
int Usestd;	/* Use stdout for squeezed output */
unsigned crc;	/* error check code */
/* *** Stuff for first translation module *** */
int likect;	/*count of consecutive identical chars */
int lastchar, newchar;
char state;
/* states */
#define NOHIST	0	/*don't consider previous input*/
#define SENTCHAR 1	/*lastchar set, no lookahead yet */
#define SENDNEWC 2	/*newchar set, previous sequence done */
#define SENDCNT 3	/*newchar set, DLE sent, send count next */

/* *** Stuff for second translation module *** */
#define NOCHILD -1	/* indicates end of path through tree */
#define NUMNODES (NUMVALS + NUMVALS - 1)	/* nbr of nodes */

#define MAXCOUNT 65535	/* biggest unsigned integer */

/* The following array of structures are the nodes of the
 * binary trees. The first NUMVALS nodes becomethe leaves of the
 * final tree and represent the values of the data bytes being
 * encoded and the special endfile, SPEOF.
 * The remaining nodes become the internal nodes of the final tree.
 */

struct	nd {
	unsigned weight;	/* number of appearances */
	int tdepth;		/* length on longest path in tre*/
	int lchild, rchild;	/* indexes to next level */
}
node[NUMNODES];

int dctreehd;	/*index to head node of final tree */

/* This is the encoding table:
 * The bit strings have first bit in  low bit.
 * Note that counts were scaled so code fits unsigned integer
 */

int codelen[NUMVALS];		/* number of bits in code */
unsigned code[NUMVALS]; 	/* code itself, right adjusted */
unsigned tcode; 		/* temporary code value */


/* Variables used by encoding process */
int curin;	/* Value currently being encoded */
int cbitsrem;	/* Number of code string bits remaining */
unsigned ccode; /* Current code shifted so next code bit is at right */
/* This program compresses a file without losing information.
 * The usq.com program is required to unsqueeze the file
 * before it can be used.
 *
 * Typical compression rates are:
 *	.COM	6%	(Don't bother)
 *	.ASM	33%	(using full ASCII set)
 *	.DIC	46%	(using only uppercase and a few others)
 * Squeezing a really big file takes a few minutes.
 *
 * Useage:
 *	sq file ...
 *
 *
 * The squeezed file name is formed by changing the second from last
 * letter of the file type to Q. If there is no file type,
 * the squeezed file type is QQQ. If the name exists it is
 * overwritten!
 *
 * The transformations compress strings of identical bytes and
 * then encode each resulting byte value and EOF as bit strings
 * having lengths in inverse proportion to their frequency of
 * occurrance in the intermediate input stream. The latter uses
 * the Huffman algorithm. Decoding information is included in
 * the squeezed file, so squeezing short files or files with
 * uniformly distributed byte values will actually increase size.
 */

/* CHANGE HISTORY:
 * 1.5u **nix version - means output to stdout.
 *  (stdin not allowed becuase sq needs to rewind input, which
 *  won't work with pipes.)
 * Filename generation changed to suit **nix and stdio.
 * 1.6u machine independent output for file compatibility with
 *	original CP/M version SQ, when running on machine with
 *	IBM byte ordering such as Z8000 and 68000.
 *
 * 1.7	08/13/83  C86 Version by Wayne Fruhwald
 *	Converted to work with Computer Innovation's C86 c compiler under MSDOS.
 *
 */

#define VERSION "1.7    8-13-83"                                       /* 1.7 */

main(argc, argv)
int argc;
char *argv[];
{
	register i,c;


	/* Process the parameters in order */
	for(i = 1; i < argc; ++i) {
		if(strcmp(argv[i], "-")==0)
			Usestd = TRUE;
	}
	for(i = 1; i < argc; ++i) {
		if(strcmp(argv[i], "-")!=0)
			obey(argv[i]);
	}

	if(argc < 2) {
		fprintf(stderr,"File squeezer version %s by\n\tRichard Greenlaw\n\t251 Colony Ct.\n\tGahanna, Ohio 43230\n", VERSION);
		fprintf(stderr, "Usage: sq [-] pathname ...\n");
		fprintf(stderr, "\t- squeezed output to stdout\n");
		exit(1);
	}
	exit(0);
}

obey(p)
char *p;
{
	char *w,*q;
	char outfile[PATHLEN+2];	/* output file spec. */

	/* First build output file name */

	strcpy(outfile, p);
	/* Find and change output file type */
	for(w=q = outfile; *q != '\0'; ++q)     /* skip leading /'s */
		if( *q == '/')
			w = q+1;
	for(q = w; *q != '\0'; ++q)
		if(*q == '.')
			if(*(q + 1) == '\0')
				*q = '\0';      /* kill trailing dot */
			else
				switch(*(q+2)) {
				case 'q':
				case 'Q':
					fprintf(stderr, "\n%s ignored ( already squeezed?)", p);
					return;
				case '\0':
					*(q+3) = '\0';
					/* fall thru */
				default:
					*(q + 2) = 'Q';
					goto named;
				}
	/* No file type */
	strcat(outfile, ".QQQ");
named:
	if(strlen(w)>14)
		strcpy(outfile, ALTNAME);	/* check for too long name */
	squeeze(p, outfile);
}

squeeze(infile, outfile)
char *infile, *outfile;
{
	register i, c;
	FILE *inbuff, *outbuff; /* file buffers */

	fprintf(stderr, "\n%s -> %s: ", infile, outfile);

	if((inbuff=fopen(infile, "rb")) == NULL) {                     /* 1.7 */
		fprintf(stderr, "Can't open %s for input pass 1\n", infile);
		return;
	}
	if(Usestd)
		outbuff=stdout;
	else if((outbuff=fopen(outfile, "wb")) == NULL) {              /* 1.7 */
		fprintf(stderr, "Can't create %s\n", outfile);
		fclose(inbuff);
		return;
	}

	/* First pass - get properties of file */
	crc = 0;	/* initialize checksum */
	fprintf(stderr, "analyzing, ");
	init_ncr();
	init_huff(inbuff);
	rewind(inbuff);
	/* Write output file header with decoding info */
	wrt_head(outbuff, infile);

	/* Second pass - encode the file */
	fprintf(stderr, "squeezing, ");

	init_ncr();	/* For second pass */

	/* Translate the input file into the output file */
	while((c = gethuff(inbuff)) != EOF)
		if(putc(c, outbuff) == ERROR && ferror(outbuff)) {
			fprintf(stderr, "ERROR - write failure in %s\n", outfile);
			goto closeall;
		}
	fprintf(stderr, " done.\n");
closeall:
	fclose(inbuff);
closeout:
	fflush(outbuff);
	fclose(outbuff);
}


/* First translation - encoding of repeated characters
 * The code is byte for byte pass through except that
 * DLE is encoded as DLE, zero and repeated byte values
 * are encoded as value, DLE, count for count >= 3.
 */

init_ncr()	/*initialize getcnr() */
{
	state = NOHIST;
}

int
getcnr(iob)
FILE *iob;
{
	switch(state) {
	case NOHIST:
		/* No relevant history */
		state = SENTCHAR;
		return lastchar = getc_crc(iob);
	case SENTCHAR:
		/* Lastchar is set, need lookahead */
		switch(lastchar) {
		case DLE:
			state = NOHIST;
			return 0;	/* indicates DLE was the data */
		case EOF:
			return EOF;
		default:
			for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
				;
			switch(likect) {
			case 1:
				return lastchar = newchar;
			case 2:
				/* just pass through */
				state = SENDNEWC;
				return lastchar;
			default:
				state = SENDCNT;
				return DLE;
			}
		}
	case SENDNEWC:
		/* Previous sequence complete, newchar set */
		state = SENTCHAR;
		return lastchar = newchar;
	case SENDCNT:
		/* Sent DLE for repeat sequence, send count */
		state = SENDNEWC;
		return likect;
	default:
		fprintf(stderr,"Bug - bad state\n");
		exit(1);
		/* NOTREACHED */
	}
}


/******** Second translation - bytes to variable length bit strings *********/


/* This translation uses the Huffman algorithm to develop a
 * binary tree representing the decoding information for
 * a variable length bit string code for each input value.
 * Each string's length is in inverse proportion to its
 * frequency of appearance in the incoming data stream.
 * The encoding table is derived from the decoding table.
 *
 * The range of valid values into the Huffman algorithm are
 * the values of a byte stored in an integer plus the special
 * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
 *
 * The "node" array of structures contains the nodes of the
 * binary tree. The first NUMVALS nodes are the leaves of the
 * tree and represent the values of the data bytes being
 * encoded and the special endfile, SPEOF.
 * The remaining nodes become the internal nodes of the tree.
 *
 * In the original design it was believed that
 * a Huffman code would fit in the same number of
 * bits that will hold the sum of all the counts.
 * That was disproven by a user's file and was a rare but
 * infamous bug. This version attempts to choose among equally
 * weighted subtrees according to their maximum depths to avoid
 * unnecessarily long codes. In case that is not sufficient
 * to guarantee codes <= 16 bits long, we initially scale
 * the counts so the total fits in an unsigned integer, but
 * if codes longer than 16 bits are generated the counts are
 * rescaled to a lower ceiling and code generation is retried.
 */

/* Initialize the Huffman translation. This requires reading
 * the input file through any preceding translation functions
 * to get the frequency distribution of the various values.
 */

init_huff(ib)
FILE *ib;
{
	register c, i;
	int btlist[NUMVALS];	/* list of intermediate binary trees */
	int listlen;		/* length of btlist */
	unsigned *wp;		/* simplifies weight counting */
	unsigned ceiling;	/* limit for scaling */

	/* Initialize tree nodes to no weight, no children */
	init_tree();

	/* Build frequency info in tree */
	do {
		c = getcnr(ib);
		if(c == EOF)
			c = SPEOF;
		if(*(wp = &node[c].weight) !=  MAXCOUNT)
			++(*wp);
	}
	while(c != SPEOF);

	ceiling = MAXCOUNT;

	do {	/* Keep trying to scale and encode */
		if(ceiling != MAXCOUNT)
			fprintf(stderr, "*** rescaling ***, ");
		scale(ceiling);
		ceiling /= 2;	/* in case we rescale */

		/* Build list of single node binary trees having
				 * leaves for the input values with non-zero counts
				 */
		for(i = listlen = 0; i < NUMVALS; ++i)
			if(node[i].weight != 0) {
				node[i].tdepth = 0;
				btlist[listlen++] = i;
			}

		/* Arrange list of trees into a heap with the entry
				 * indexing the node with the least weight at the top.
				 */
		heap(btlist, listlen);

		/* Convert the list of trees to a single decoding tree */
		bld_tree(btlist, listlen);

		/* Initialize the encoding table */
		init_enc();

		/* Try to build encoding table.
				 * Fail if any code is > 16 bits long.
				 */
	}
	while(buildenc(0, dctreehd) == ERROR);

	/* Initialize encoding variables */
	cbitsrem = 0;	/*force initial read */
	curin = 0;	/*anything but endfile*/
}

/* The count of number of occurrances of each input value
 * have already been prevented from exceeding MAXCOUNT.
 * Now we must scale them so that their sum doesn't exceed
 * ceiling and yet no non-zero count can become zero.
 * This scaling prevents errors in the weights of the
 * interior nodes of the Huffman tree and also ensures that
 * the codes will fit in an unsigned integer. Rescaling is
 * used if necessary to limit the code length.
 */

scale(ceil)
unsigned ceil;	/* upper limit on total weight */
{
	register i,c;
	int ovflw, divisor;
	unsigned w, sum;
	char increased; 	/* flag */

	do {
		for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
			if(node[i].weight > (ceil - sum))
				++ovflw;
			sum += node[i].weight;
		}

		divisor = ovflw + 1;

		/* Ensure no non-zero values are lost */
		increased = FALSE;
		for(i = 0; i < NUMVALS; ++i) {
			w = node[i].weight;
			if (w < divisor && w != 0) {
				/* Don't fail to provide a code if it's used at all */
				node[i].weight = divisor;
				increased = TRUE;
			}
		}
	}
	while(increased);

	/* Scaling factor choosen, now scale */
	if(divisor > 1)
		for(i = 0; i < NUMVALS; ++i)
			node[i].weight /= divisor;
}

/* heap() and adjust() maintain a list of binary trees as a
 * heap with the top indexing the binary tree on the list
 * which has the least weight or, in case of equal weights,
 * least depth in its longest path. The depth part is not
 * strictly necessary, but tends to avoid long codes which
 * might provoke rescaling.
 */

heap(list, length)
int list[], length;
{
	register i;

	for(i = (length - 2) / 2; i >= 0; --i)
		adjust(list, i, length - 1);
}

/* Make a heap from a heap with a new top */

adjust(list, top, bottom)
int list[], top, bottom;
{
	register k, temp;

	k = 2 * top + 1;	/* left child of top */
	temp = list[top];	/* remember root node of top tree */
	if( k <= bottom) {
		if( k < bottom && cmptrees(list[k], list[k + 1]))
			++k;

		/* k indexes "smaller" child (in heap of trees) of top */
		/* now make top index "smaller" of old top and smallest child */
		if(cmptrees(temp, list[k])) {
			list[top] = list[k];
			list[k] = temp;
			/* Make the changed list a heap */
			adjust(list, k, bottom); /*recursive*/
		}
	}
}

/* Compare two trees, if a > b return true, else return false
 * note comparison rules in previous comments.
 */

cmptrees(a, b)
register int a, b;  /* root nodes of trees */
{
	if(node[a].weight > node[b].weight)
		return TRUE;
	if(node[a].weight == node[b].weight)
		if(node[a].tdepth > node[b].tdepth)
			return TRUE;
	return FALSE;
}

/* HUFFMAN ALGORITHM: develops the single element trees
 * into a single binary tree by forming subtrees rooted in
 * interior nodes having weights equal to the sum of weights of all
 * their descendents and having depth counts indicating the
 * depth of their longest paths.
 *
 * When all trees have been formed into a single tree satisfying
 * the heap property (on weight, with depth as a tie breaker)
 * then the binary code assigned to a leaf (value to be encoded)
 * is then the series of left (0) and right (1)
 * paths leading from the root to the leaf.
 * Note that trees are removed from the heaped list by
 * moving the last element over the top element and
 * reheaping the shorter list.
 */

bld_tree(list, len)
int list[];
int len;
{
	register freenode;		/* next free node in tree */
	register struct nd *frnp;	/* free node pointer */
	int lch, rch;		/* temporaries for left, right children */
	int i;

	/* Initialize index to next available (non-leaf) node.
		 * Lower numbered nodes correspond to leaves (data values).
		 */
	freenode = NUMVALS;

	while(len > 1) {
		/* Take from list two btrees with least weight
				 * and build an interior node pointing to them.
				 * This forms a new tree.
				 */
		lch = list[0];	/* This one will be left child */

		/* delete top (least) tree from the list of trees */
		list[0] = list[--len];
		adjust(list, 0, len - 1);

		/* Take new top (least) tree. Reuse list slot later */
		rch = list[0];	/* This one will be right child */

		/* Form new tree from the two least trees using
				 * a free node as root. Put the new tree in the list.
				 */
		frnp = &node[freenode]; /* address of next free node */
		list[0] = freenode++;	/* put at top for now */
		frnp->lchild = lch;
		frnp->rchild = rch;
		frnp->weight = node[lch].weight + node[rch].weight;
		frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
		/* reheap list	to get least tree at top*/
		adjust(list, 0, len - 1);
	}
	dctreehd = list[0];	/*head of final tree */
}

/* ???????????? */
maxchar(a, b)
{
	return a > b ? a : b;
}
/* Initialize all nodes to single element binary trees
 * with zero weight and depth.
 */

init_tree()
{
	register i;

	for(i = 0; i < NUMNODES; ++i) {
		node[i].weight = 0;
		node[i].tdepth = 0;
		node[i].lchild = NOCHILD;
		node[i].rchild = NOCHILD;
	}
}

init_enc()
{
	register i;

	/* Initialize encoding table */
	for(i = 0; i < NUMVALS; ++i) {
		codelen[i] = 0;
	}
}

/* Recursive routine to walk the indicated subtree and level
 * and maintain the current path code in bstree. When a leaf
 * is found the entire code string and length are put into
 * the encoding table entry for the leaf's data value.
 *
 * Returns ERROR if codes are too long.
 */

int		/* returns ERROR or NULL */
buildenc(level, root)
int level;/* level of tree being examined, from zero */
int root; /* root of subtree is also data value if leaf */
{
	register l, r;

	l = node[root].lchild;
	r = node[root].rchild;

	if( l == NOCHILD && r == NOCHILD) {
		/* Leaf. Previous path determines bit string
				 * code of length level (bits 0 to level - 1).
				 * Ensures unused code bits are zero.
				 */
		codelen[root] = level;
		code[root] = tcode & (((unsigned)~0) >> (16 - level));
		return (level > 16) ? ERROR : NULL;
	}
	else {
		if( l != NOCHILD) {
			/* Clear path bit and continue deeper */
			tcode &= ~(1 << level);
			/* NOTE RECURSION */
			if(buildenc(level + 1, l) == ERROR)
				return ERROR;
		}
		if(r != NOCHILD) {
			/* Set path bit and continue deeper */
			tcode |= 1 << level;
			/* NOTE RECURSION */
			if(buildenc(level + 1, r) == ERROR)
				return ERROR;
		}
	}
	return NULL;	/* if we got here we're ok so far */
}

/* Write out the header of the compressed file */

wrt_head(ob, infile)
FILE *ob;
char *infile;	/* input file name (w/ or w/o drive) */
{
	register l,r;
	int i, k;
	int numnodes;		/* nbr of nodes in simplified tree */

	putwe(RECOGNIZE, ob);	/* identifies as compressed */
	putwe(crc, ob); 	/* unsigned sum of original data */

	/* Record the original file name w/o drive */
	if(*(infile + 1) == ':')
		infile += 2;	/* skip drive */

	do {
		putce(*infile, ob);
	}
	while(*(infile++) != '\0');


	/* Write out a simplified decoding tree. Only the interior
		 * nodes are written. When a child is a leaf index
		 * (representing a data value) it is recoded as
		 * -(index + 1) to distinguish it from interior indexes
		 * which are recoded as positive indexes in the new tree.
		 * Note that this tree will be empty for an empty file.
		 */

	numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
	putwe(numnodes, ob);

	for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
		l = node[i].lchild;
		r = node[i].rchild;
		l = l < NUMVALS ? -(l + 1) : dctreehd - l;
		r = r < NUMVALS ? -(r + 1) : dctreehd - r;
		putwe(l, ob);	/* left child */
		putwe(r, ob);	/* right child */
	}
}

/* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
 *
 * There are two unsynchronized bit-byte relationships here.
 * The input stream bytes are converted to bit strings of
 * various lengths via the static variables named c...
 * These bit strings are concatenated without padding to
 * become the stream of encoded result bytes, which this
 * function returns one at a time. The EOF (end of file) is
 * converted to SPEOF for convenience and encoded like any
 * other input value. True EOF is returned after that.
 *
 * The original gethuff() called a seperate function,
 * getbit(), but that more readable version was too slow.
 */

int		/*  Returns byte values except for EOF */
gethuff(ib)
FILE *ib;
{
	int rbyte;	/* Result byte value */
	int need, take; /* numbers of bits */

	rbyte = 0;
	need = 8;	/* build one byte per call */

	/* Loop to build a byte of encoded data
		 * Initialization forces read the first time
		 */

loop:
	if(cbitsrem >= need) {
		/* Current code fullfills our needs */
		if(need == 0)
			return rbyte;
		/* Take what we need */
		rbyte |= ccode << (8 - need);
		/* And leave the rest */
		ccode >>= need;
		cbitsrem -= need;
		return rbyte;
	}

	/* We need more than current code */
	if(cbitsrem > 0) {
		/* Take what there is */
		rbyte |= ccode << (8 - need);
		need -= cbitsrem;
	}
	/* No more bits in current code string */
	if(curin == SPEOF) {
		/* The end of file token has been encoded. If
				 * result byte has data return it and do EOF next time
				 */
		cbitsrem = 0;

		/*NOTE: +0 is to fight compiler bug? */
		return (need == 8) ? EOF : rbyte + 0;
	}

	/* Get an input byte */
	if((curin = getcnr(ib)) == EOF)
		curin = SPEOF;	/* convenient for encoding */

	/* Get the new byte's code */
	ccode = code[curin];
	cbitsrem = codelen[curin];

	goto loop;
}


/* Get next byte from file and update checksum */

int
getc_crc(ib)
FILE *ib;
{
	register c;

	c = getc(ib);
	if(c != EOF)
		crc += c;	/* checksum */
	return c;
}

/* Output functions with error reporting */

putce(c, iob)
int c;
register FILE *iob;
{
	if(putc(c, iob) == ERROR && ferror(iob)) {
		fprintf(stderr, "sq:Write error\n");
		exit(1);
	}
}

/*
 * machine independent put-word that writes low order byte first
 *  (compatible with CP/M original) regardless of host cpu.
 */
putwe(w, iob)
register int w;
register FILE *iob;
{
	putc(w, iob);
	putc(w>>8, iob);
	if (ferror(iob)) {
		fprintf(stderr, "sq:Write error\n");
		exit(1);
	}
}
—‹^þ6ŠAé2äY‘;Áté	¸+ˆFé ŠF2äP¸H—‹^þ6ŠAé2äY‘;Áté	¸|ˆFézŠF2äP¸H—‹^þ6ŠAé2äY‘;Áté	¸-