// --------------------------------------------------------------------------
// Citadel: Huf.CPP
//
// This is the huffman encoder/decoder.

#ifndef WINCIT
#include "ctdl.h"
#pragma hdrstop

#include "huf.h"
#include "miscovl.h"


int hufOrig, hufNew;
uint cdecl bitsenc;

hufTree cdecl *htRoot;
discardable *htData;
static int dataOffsets[255];	// 0 to 254

#if VERSION != RELEASE
static void CheckTreePointer(const void *Check, hufTree *cur)
	{
	if (cur)
		{
		if (cur == Check)
			{
			mPrintf(" (Huffman tree)");
			return;
			}

		if (cur->left)
			{
			CheckTreePointer(Check, cur->left);
			}

		if (cur->right)
			{
			CheckTreePointer(Check, cur->right);
			}
		}
	}

void CheckHufPointer(const void *Check)
	{
	CheckDiscardablePtr(htData, Check, "htData");
	CheckTreePointer(Check, htRoot);
	}
#endif


// --------------------------------------------------------------------------
// With hufInit, used to create a tree from the data in huf.h.

static hufTree *followOrMakeTree(hufTree *start, int whichWay)
	{
	if (whichWay)
		{
		// go right
		if (!start->right)
			{
			start->right = new hufTree;

			if (start->right)
				{
				start->right->left = NULL;
				start->right->right = NULL;
				}
			}

		return (start->right);
		}
	else
		{
		// go left
		if (!start->left)
			{
			start->left = new hufTree;

			if (start->left)
				{
				start->left->left = NULL;
				start->left->right = NULL;
				}
			}

		return (start->left);
		}
	}


// --------------------------------------------------------------------------
// Builds tree.

static Bool initHuf(void)
	{
	int i, j;
	hufTree *cur;

	if ((htData = readData(15)) != NULL)
		{
		int p = 0;

		if ((htRoot = new hufTree) == NULL)
			{
			discardData(htData);
			htData = NULL;
			return (FALSE);
			}

		htRoot->left = NULL;
		htRoot->right = NULL;

		for (i = 1; i < 255; i++)
			{
			cur = htRoot;
			dataOffsets[i] = p++;

			for (j = 0; j < ((char *)(htData->data))[dataOffsets[i]]; j++)
				{
				cur = followOrMakeTree(cur, ((char *)(htData->data))[p++]);

				if (!cur)
					{
					discardData(htData);
					htData = NULL;
					freeHufTree();
					return (FALSE);
					}
				}

			cur->theChar = i;
			}

		return (TRUE);
		}
	else
		{
		return (FALSE);
		}
	}


// --------------------------------------------------------------------------
// Unbuilds tree.

static void freeTree(hufTree *cur)
	{
	if (cur->left)
		{
		freeTree(cur->left);
		}

	if (cur->right)
		{
		freeTree(cur->right);
		}

	delete cur;
	}

void freeHufTree(void)
	{
	if (htRoot)
		{
		freeTree(htRoot);
		htRoot = NULL;
		}

	if (htData)
		{
		discardData(htData);
		htData = NULL;
		}
	}

#ifdef UNUSED

 these two functions are not used - faster "decode" in hufbit.asm
 C versions left in tact for portability...


// --------------------------------------------------------------------------
// Returns next bit from str.

int nextBit (uchar *str)
	{
	if (!(bitsenc & 7))
		{
		// first bit of new byte
		if (str[bitsenc >> 3] == ESC)
			{
			bitsenc += 8;
			switch (str[bitsenc >> 3])
				{
				case 1:
					{
					str[bitsenc >> 3] = 0;
					break;
					}

				case 2:
					{
					str[bitsenc >> 3] = ESC;
					break;
					}

				case 3:
					{
					str[bitsenc >> 3] = 255;
					break;
					}

				default:
					{
					mPrintfCR(getmsg(1688), str[bitsenc >> 3]);
					break;
					}
				}
			}
		}

	return (str[bitsenc >> 3] & (1 << 7-(bitsenc++ & 7)));
	}


// --------------------------------------------------------------------------
// Decodes the next sequence in the bitstream.

uchar decode(uchar *str)
	{
	hufTree *cur;
	cur = htRoot;

	while (cur->left)
		{
		if (nextBit(str))
			{
			cur = cur->right;
			}
		else
			{
			cur = cur->left;
			}
		}
	return (cur->theChar);
	}
#endif


// --------------------------------------------------------------------------
// Decompresses string at str - writes back to str.

void decompress(uchar *str)
	{
	int decoded = 0;
	bitsenc = 16;
	hufOrig = 0;

	if (!htRoot)
		{
		if (!initHuf())
			{
			return;
			}
		}

	if (!encbuf)
		{
		encbuf = new uchar[ENCBUFSIZE];

		if (!encbuf)
			{
			return;
			}
		}

	memset(encbuf, 0, ENCBUFSIZE);

	if (str[0] == 1)
		{
		hufNew = strlen((char *) str);
		if (str[1] == ESC)
			{
			bitsenc += 8;
			switch (str[2])
				{
				case 1:
					{
					break;
					}

				case 2:
					{
					hufOrig = ESC;
					break;
					}

				case 3:
					{
					hufOrig = 255;
					break;
					}

				default:
					{
					mPrintfCR(getmsg(1688), str[2]);
					break;
					}
				}
			}
		else
			{
			hufOrig = str[1];
			}

		if (str[bitsenc >> 3] == ESC)
			{
			bitsenc += 8;
			switch (str[bitsenc >> 3])
				{
				case 1:
					{
					// This is a way to work around pre-65.155 corrupted
					// messages. In reality, we should always break here.
					if (hufNew < 300)
						{
						break;
						}

					mPrintfCR(getmsg(1689));
					}

				case 2:
					{
					hufOrig += ESC << 8;
					break;
					}

				case 3:
					{
					hufOrig += 255 << 8;
					break;
					}

				default:
					{
					mPrintfCR(getmsg(1688), str[bitsenc >> 3]);
					break;
					}
				}
			}
		else
			{
			hufOrig += str[bitsenc >> 3] << 8;
			}

		bitsenc += 8;

		// only decode as many bytes as we have room
		if (hufOrig > ENCBUFSIZE - 1) hufOrig = ENCBUFSIZE - 1;

		while (decoded < hufOrig)
			{
			encbuf[decoded++] = decode(str);
			}

		strcpy((char *) str, (char *) encbuf);
		}
	}


// --------------------------------------------------------------------------
// Encodes the character in to the bitstream.

static void encode(uchar in)
	{
	int i;

	if ( (long)bitsenc + (long) ((char *)(htData->data))[dataOffsets[in]] >
			(long)(ENCBUFSIZE-1) * 8
		|| in == 0 || in == 255 || hufNew == -1)
		{
		hufNew = -1;
		return;
		}

	for (i = 0; i < ((char *)(htData->data))[dataOffsets[in]]; i++)
		{
		encbuf[bitsenc >> 3] |= (((char *)(htData->data))[dataOffsets[in] + i + 1] << (7 - (bitsenc++ & 7)));

		if (!(bitsenc & 7)) 	// done with byte; check for icky character
			{
			switch (encbuf[(bitsenc - 1) >> 3])
				{
				case 0:
					{
					encbuf[(bitsenc - 1) >> 3] = ESC;
					encbuf[bitsenc >> 3] = 1;
					bitsenc += 8;
					break;
					}

				case ESC:
					{
					encbuf[bitsenc >> 3] = 2;
					bitsenc += 8;
					break;
					}

				case 255:
					{
					encbuf[(bitsenc - 1) >> 3] = ESC;
					encbuf[bitsenc >> 3] = 3;
					bitsenc += 8;
					break;
					}

				// Default: Leave alone.
				}
			}
		}
	}


// --------------------------------------------------------------------------
// Compresses string at str; new string at str - checks for length.

Bool compress(char *str)
	{
	int i;

	if (!htRoot)
		{
		if (!initHuf())
			{
			return (FALSE);
			}
		}

	if (!encbuf)
		{
		encbuf = new uchar[ENCBUFSIZE];

		if (!encbuf)
			{
			return (FALSE);
			}
		}

	hufOrig = strlen(str);
	memset(encbuf, 0, ENCBUFSIZE);
	bitsenc = 16;

	encbuf[0] = 1;	// compression type
	encbuf[1] = (uchar) (hufOrig & 255);
	switch (encbuf[1])
		{
		case 0:
			{
			encbuf[1] = ESC;
			encbuf[2] = 1;
			bitsenc += 8;
			break;
			}

		case ESC:
			{
			encbuf[2] = 2;
			bitsenc += 8;
			break;
			}

		case 255:
			{
			encbuf[1] = ESC;
			encbuf[2] = 3;
			bitsenc += 8;
			break;
			}
		}

	encbuf[bitsenc >> 3] = (uchar) (hufOrig >> 8);
	switch (encbuf[bitsenc >> 3])
		{
		case 0:
			{
			encbuf[bitsenc >> 3] = ESC;
			bitsenc += 8;
			encbuf[bitsenc >> 3] = 1;
			break;
			}

		case ESC:
			{
			bitsenc += 8;
			encbuf[bitsenc >> 3] = 2;
			break;
			}

		case 255:
			{
			encbuf[bitsenc >> 3] = ESC;
			bitsenc += 8;
			encbuf[bitsenc >> 3] = 3;
			break;
			}
		}
	bitsenc += 8;

	for (i = 0; i < hufOrig; i++)
		{
		encode(str[i]);
		}

	hufNew = strlen((char *) encbuf);

	if (hufNew >= hufOrig || hufNew == -1)
		{
		return (FALSE);
		}
	strcpy(str, (char *) encbuf);
	return (TRUE);
	}
#endif
