/*
File:	UNSHRINK.C - Include file for ZTYPE.
Date:	July 26, 1990
Author:	Copyright 1990 by Carson Wilson, Sysop, 
		  Antelope Freeway RAS, 312/764-5162, Chicago.

Derived from UNZIP20.ZIP, Copyright 1989 by Samuel H. Smith.
*/

#include <stdio.h>
#include <ztype.h>

/* ------------------------------------------------------------- */
/*
 * Shrinking is	a Dynamic Ziv-Lempel-Welch compression algorithm
 * with	partial	clearing.
 *
 */

void unShrink()
{
	#define	 GetCode(dest) READBIT(codesize,dest)
	#define hsize 256

	int i, soutcnt, z;
	int code;	
	unsigned stackp;
	int finchar;
	int oldcode;
	int incode;
	unsigned pr;
	unsigned cd;

	int prefix_of[8192+1];
	char suffix_of[8192+1];
	char stack[hsize+1];

	maxcodemax = 1 << max_bits;	/* 1 shl 13 = 2000h */
	codesize = init_bits;	/* = 9 */
	maxcode	= (1 <<	codesize) - 1;
	free_ent = FIRST_ENT;
	offset = 0; sizex = 0;

	for (code = maxcodemax; code > 255; code--) prefix_of[code] = -1;

	for (code = 255; code >= 0; code--) {
		prefix_of[code]	= 0; suffix_of[code] = code;
	}

	GetCode(oldcode);	/* read 9 bits */
	if (zipeof) return;
	finchar	= oldcode;
	OUTB(finchar);
	stackp = hsize;

	while (!zipeof)	{
		GetCode(code);
		if (zipeof) return;
		while (code == clear) /* 256 */ {
			GetCode(code);
			switch (code) {
			case 1:
				codesize++;
				if (codesize ==	max_bits)
					maxcode	= maxcodemax;
				else
					maxcode	= (1 <<	codesize) - 1;
				break;
			case 2:
				/* mark	all nodes as potentially unused	*/
				for (cd	= FIRST_ENT; cd < free_ent; cd++)
					prefix_of[cd] |= 0x8000;

				/* unmark those	that are used by other nodes */
				for (cd	= FIRST_ENT; cd < free_ent; cd++) {
					pr = prefix_of[cd] & 0x7fff;	/* reference to another node? */
					if (pr >= FIRST_ENT)		/* flag	node as	referenced */
						prefix_of[pr] &= 0x7fff;
				}
				/* clear the ones that are still marked	*/
				for (cd	= FIRST_ENT; cd < free_ent; cd++)
					if ((prefix_of[cd] & 0x8000) !=	0)
						prefix_of[cd] =	-1;

				/* find	first cleared node as next free_ent */
				cd = FIRST_ENT;
				while ((cd < maxcodemax) && (prefix_of[cd] != -1))
					cd++;
				free_ent = cd;
				break;
			}
			GetCode(code);
			if (zipeof) return;
		}
		/* special case	for KwKwK string */
		incode = code;
		if (prefix_of[code] == -1) {
			stack[--stackp]	= finchar;
			code = oldcode;
		}
		/* generate output characters in reverse order */
		while (code >= FIRST_ENT) {
			stack[--stackp]	= suffix_of[code];
			code = prefix_of[code];
		}
		finchar	= suffix_of[code];
		stack[--stackp]	= finchar;

		/* and put them out in forward order, block copy */
		soutcnt = (outcnt[3] + (outcnt[2] << 8));
		z = hsize-stackp;
		if ((z+soutcnt) < ONEK) {
			cpymem(&stack[stackp],outptr,z);
			outptr += z;
			soutcnt += z;
			long(0,outcnt,soutcnt);
			stackp = hsize;
		}
		/* output byte by byte if we can't go by blocks */
		else while (stackp < hsize) OUTB(stack[stackp++]);

		/* generate new	entry */
		code = free_ent;
		if (code < maxcodemax) {
			prefix_of[code]	= oldcode;
			suffix_of[code]	= finchar;
			do code++;
			while ((code < maxcodemax) && (prefix_of[code] != -1));
			free_ent = code;
		}
		/* remember previous code */
		oldcode	= incode;
	}
}