/*
File:	EXPLODE.C - BDS C source code for ZTYPE.
Date:	July 29, 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>

/* Structures for exploding */

struct sf_entry {   
	int	Code;
	char	Value;
	char	BitLength;
	};

struct sf_tree {   /* a shannon-fano tree */
	struct sf_entry entry[256];
	int	entries;
	int	MaxLength;
	int oddcnt;	/* crw */
	};

/* -------------------------------------------- */

void ReadLengths(tree)
struct sf_tree *tree;
{
	int treeBytes, i, num, len;

	/* get number of bytes in compressed tree */
	READ8B(treeBytes);
	treeBytes++;
	i = 0;
	tree->MaxLength = 0;

 /* High 4 bits: Number	of values at this bit length + 1. (1 - 16)
    Low	 4 bits: Bit Length needed to represent	value +	1. (1 -	16) */

	while (treeBytes--) {
		READ4B(len); len++;
		READ4B(num); num++;
		while (num--) {
			if (len > tree->MaxLength)
				tree->MaxLength = len;
			tree->entry[i].BitLength = len;
			tree->entry[i].Value =	i++;
		}
	}
}
/* -------------------------------------------- */

void SortLengths(tree)
struct sf_tree *tree;

  /* Sort the Bit Lengths in ascending order, while retaining the order
    of the original lengths stored in the file */
{
	int x, y, z;
	int gap;
	struct sf_entry t;
	char found;

	gap = tree->entries / 3 + 1;

	do	{ 
		for (x = 0, y = gap; y <= tree->entries - 1; x++, y++) {
			if (tree->entry[x].BitLength < tree->entry[y].BitLength) ;
			else if ((tree->entry[x].BitLength > tree->entry[y].BitLength) ||
					 (tree->entry[x].Value     > tree->entry[y].Value))
			{
				z = y;
				cpymem(&tree->entry[z],&t,4);
				do
				{
					if ((z -= gap) < 0) 
					{
						z += gap;
						found = 1;
					}
					else 
					{
						cpymem(&tree->entry[z],&tree->entry[z+gap],4);
						found = ((z < gap) || (z == 0) ||
								 (tree->entry[z-gap].BitLength < t.BitLength )   ||
								 ((tree->entry[z-gap].BitLength == t.BitLength)  && 
								  (tree->entry[z-gap].Value < t.Value        )));
					}
				}
				while (!found);
				cpymem(&t,&tree->entry[z],4);
			}
		}
	}
	while (gap /= 2);
}
/* -------------------------------------------- */

void GenerateTrees(tree)
struct sf_tree *tree;
/* Generate the Shannon-Fano trees */
{
	unsigned	GCode;
	int		CodeIncrement;
	int		LastBitLength;
	int		i;

	GCode = 0;
	CodeIncrement = 0;
	LastBitLength = 0;
	i = tree->entries - 1;   /* either 255 or 63 */

	while (i >= 0) {
		GCode += CodeIncrement;
		if (tree->entry[i].BitLength != LastBitLength) {
			LastBitLength = tree->entry[i].BitLength;
			CodeIncrement = 1 << (16 - LastBitLength);
		}
	tree->entry[i--].Code = GCode;
	}
}
/* -------------------------------------------- */

void ReverseBits(tree)
struct sf_tree *tree;

 /* Reverse the	order of all the bits in the above ShannonCode[]
    vector, so that the	most significant bit becomes the least
    significant	bit. For example, the value 0x1234 (hex) would become
    0x2C48 (hex). */

/*  Also sort lists into two "trees", one filled with even and the
	other with odd codes <crw>.
*/
{
	struct sf_tree *oddtree, *eventree;	/* space will be reclaimed */
										/* by output buffer later  */
	int		i, odd, even;
	unsigned	mask;
	unsigned	rmask;
	unsigned	v;
	unsigned	o;
	char		b;	/*crw*/

	odd = even = 0;
	oddtree = outbuf;
	eventree = outbuf + 2000;
	for (i = 0; i <= tree->entries - 1; i++) {
		/* get original	code */
		o = tree->entry[i].Code;

		/* reverse each	bit */
		v = 0;
		for (mask=1, rmask=0x8000; rmask > 0; mask<<=1, rmask>>=1)
			if (o & mask) v |= rmask;
		/* store reversed bits */
		tree->entry[i].Code = v;

		if (v & (1 << tree->entry.BitLength-1)) cpymem(&tree->entry[i],&oddtree->entry[odd++],4);
		else cpymem(&tree->entry[i],&eventree->entry[even++],4);
	}
	tree->oddcnt = odd;
	for (i = 0; i <= odd; i++)
		cpymem(&oddtree->entry[i],&tree->entry[i],4);
	for (i = 0; i <= even; i++)
		cpymem(&eventree->entry[i],&tree->entry[i+odd],4);
}
/* -------------------------------------------- */

void LoadTree(tree,treesize)
struct sf_tree *tree;
int treesize;

/* allocate and load a shannon-fano tree from the compressed file */
{
	tree->entries = treesize;
	ReadLengths(tree);
	SortLengths(tree);
	GenerateTrees(tree);
	ReverseBits(tree);
}
/* -------------------------------------------- */

void ReadTree(tree,dest)
struct sf_tree *tree;
int *dest;

/* read next byte using a shannon-fano tree

- Made faster by initializing bits with first table value and
    REMOVING data error checks 7/4/90 <crw>
*/
{
	char	bits;
	int	cv, cur;
	int	b;

	cur = 0;
	bits = tree->entry[0].BitLength;
	READBIT(bits,cv);
	if (!(cv & (1 << bits - 1))) cur += tree->oddcnt;	/* start at even Codes if even */

	while (1)
	{
		while (tree->entry[cur].BitLength == bits) {
			if (tree->entry[cur].Code == cv) {
				*dest = tree->entry[cur].Value;
				return;
			}
			cur++;
		}
		if(bits_left) { 
			cv |= ((bitbuf & 1) << bits++);
			bitbuf >>= 1;
			bits_left--;
		}
		else cv |= (FillBitBuffer(1) << bits++);
	}
}
/* -------------------------------------------- */

void unImplode()
/* expand imploded data */
{
	int lout, soutcnt, z;
	int op;
	int Length;
	int Distance;
	char ltemp[4], lop[4];
	int ix; 
	struct sf_tree length_tree, distance_tree, lit_tree;

	eightK_dictionary = 
		((lrec.general_purpose_bit_flag & 0x02) != 0);   /* bit 1 */
	lit_tr_present = 
		((lrec.general_purpose_bit_flag & 0x04) != 0);   /* bit 2 */

	if (eightK_dictionary) dict_bits = 7; else dict_bits = 6;

	if (lit_tr_present) {
		minimum_match_length = 3;
		LoadTree(&lit_tree,256);
	}
	else minimum_match_length = 2;

	LoadTree(&length_tree,64);
	LoadTree(&distance_tree,64);

	while ((long(1,long(2,lres,outpos,outcnt),lrec.uncompressed_size) == -1) 
	&& (!zipeof)) {
		READ1B(lout);
		if (lout != 0)   /* encoded data is literal data */ {
			if (lit_tr_present)	/* use Literal Shannon-Fano tree */
				ReadTree(&lit_tree,&lout);
			else
				READ8B(lout);
			OUTB8(lout);
		}
		else /* encoded data is sliding dictionary match */ {
			READBIT(dict_bits,lout);
			Distance = lout;
			ReadTree(&distance_tree,&lout);
			Distance |= (lout << dict_bits);

		/* using the Distance Shannon-Fano tree, read and decode the 
		   upper 6 bits of the Distance value */
			ReadTree(&length_tree,&Length);

		/* using the Length Shannon-Fano tree, read and decode the
		   Length value */
			Length += minimum_match_length;
			if (Length == (63 + minimum_match_length)) {
				READ8B(lout);
				Length += lout;
			}

	/* move	backwards Distance+1 bytes in the output stream, and copy
	  Length characters from this position to the output stream.
	  (if this position is before the start	of the output stream,
	  then assume that all the data	before the start of the	output
	  stream is filled with	zeros) */

			/* op = (outpos + outcnt) - Distance - 1L */

			long(0,ltemp,Distance);	     /* ltemp = Distance    */
			long(2,lop,outpos,outcnt);   /* lop = outpos+outcnt */
			long(3,lop,lop,ltemp);       /* lop -= ltemp        */
			long(3,lop,lop,longone);     /* lop -= 1            */

			if (lop[0] & 0x80) {		/* negative? */
				/* special case- before start of file */
				op = (lop[3] + (lop[2] << 8)); /* op = lop  */
				/* note: truncation assumes < 32k of nulls */
				op |= 0x80;			/* add sign */
				while ((op < 0) && (Length)) {
					OUTB8(0);
					op++;
					Length--;
				}
			}

			/* normal copy of data from output buffer */
			long(0,ltemp,EIGHTK);		/* temp = EIGHTK */	
			long(6,lop,lop,ltemp);		/* lop %= temp   */
			ix = (lop[3] + (lop[2] << 8));	/* ix = temp	 */

			soutcnt = (outcnt[3] + (outcnt[2] << 8));

			/* do a	block memory copy if possible */
			if ( ((ix+Length) < EIGHTK) 
			&&   ((soutcnt+Length) < EIGHTK)
			&&   ((scrcnt+Length) < 2048) ) {
				cpymem(&outbuf[ix],outptr,Length);
				outptr  += Length;
				scrcnt	+= Length;
				soutcnt += Length;
				long(0,outcnt,soutcnt);
			}
			else
			/* otherwise copy byte by byte */
				while (Length--) {
					OUTB8(outbuf[ix]);
					if (++ix >= EIGHTK) ix = 0;
				}
		}
	}
}