/*
**	$Id: BTXDecode.cpp 1.1 1995/12/03 12:16:23 olsen Exp olsen $
**
**	:ts=4
*/

/*
 * Amiga changes copyright © 1995 by Olaf Barthel, All Rights Reserved
 *
 * Copyright (c) 1992, 1993 Arno Augustin, Frank Hoering, University of
 * Erlangen-Nuremberg, Germany.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      Erlangen-Nuremberg, Germany.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
 * EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software has not been validated by the ``Bundesamt fuer Zulassungen in
 * der Telekommunikation'' of the ``Deutsche Bundepost Telekom'' and thus
 * must not be used for accessing the BTX-Network of the Telekom in Germany.
 *
 * Diese Software hat keine Zulassung durch das Bundesamt fuer Zulassungen in
 * der Telekommunikation der Deutschen Bundespost Telekom und darf daher nicht
 * am Netz der Deutschen Bundespost Telekom in Deutschland betrieben werden.
 */

/****************************************************************************/

#include <string.h>
#include <stdlib.h>

/****************************************************************************/

#ifndef _BTXSERVICE_HPP
#include "BTXService.hpp"
#endif

/****************************************************************************/

#define FCS_32(crc,c) (crctab[((crc) ^ (c)) & 0xff] ^ ((crc) >> 8))

/****************************************************************************/

/**************************************************************
	lzhuf.c
	written by Haruyasu Yoshizaki 11/20/1988
	some minor changes 4/6/1989
	comments translated by Haruhiko Okumura 4/7/1989

	modified for Btx-FIF by InfoTeSys GmhH	  1991-11-04
	: use malloc() instead of huge static areas
	: files have to be opened outside of this module
	: FCS-check inluded
	:
	: length field "long(Filesize)" has been removed from file
**************************************************************/

/********** LZSS compression **********/

#define N				4096					/* buffer size */
#define F				60						/* lookahead buffer size */
#define THRESHOLD		2
#define NIL 			N						/* leaf of tree */
#define text_buf_len	(N + F - 1)

#define N_CHAR			(256 - THRESHOLD + F)	/* kinds of characters (character code = 0..N_CHAR-1) */
#define T				(N_CHAR * 2 - 1)		/* size of table */
#define R				(T - 1)					/* position of root */
#define MAX_FREQ		0x8000					/* updates tree when the */
												/* root frequency comes to this value. */
struct lzh_env
{
	UBYTE	InpBuf[2048];
	WORD	InpPos;
	WORD	InpMax;

	UBYTE	OutBuf[1024];
	WORD	OutPos;
	WORD	OutMax;

	UWORD	freq[T + 1];		/* frequency table */

	WORD	prnt[T + N_CHAR];	/* pointers to parent nodes, except for the */
								/* elements [T..T + N_CHAR - 1] which are used to get */
								/* the positions of leaves corresponding to the codes. */
	WORD	son[T];				/* pointers to child nodes (son[], son[] + 1) */

	ULONG	crctab[256];

	UBYTE	*text_buf;
	WORD	match_position;
	WORD	match_length;
	WORD	*lson; 				/*   [N + 1];	*/
	WORD	*rson; 				/*   [N + 257];	*/
	WORD	*dad;				/*   [N + 1];	*/

	UWORD	getbuf;
	WORD	getlen;

	FILE	*infile;
	FILE	*outfile;
};

STATIC WORD InpByt(struct lzh_env *LZHENV)
{
	if(LZHENV->InpPos >= LZHENV->InpMax)
	{
		if((LZHENV->InpMax = (WORD)fread(LZHENV->InpBuf,1,LZHENV->InpMax,LZHENV->infile)) < 1)
			return(0);

		LZHENV->InpPos = 0;
	}

	return(LZHENV->InpBuf[LZHENV->InpPos++]);
}

STATIC WORD OutByt(struct lzh_env *LZHENV,WORD BY)
{
	LZHENV->OutBuf[LZHENV->OutPos++] = (UBYTE)BY;

	if(LZHENV->OutPos == LZHENV->OutMax)
	{
		if(fwrite(LZHENV->OutBuf,LZHENV->OutPos,1,LZHENV->outfile) < 1)
			return(0);

		LZHENV->OutPos = 0;
	}

	return(1);
}

STATIC WORD GetBit(struct lzh_env *LZHENV)   /* get one bit */
{
	WORD i,j;

	j = LZHENV->getlen;

	while(j <= 8)
	{
		if((i = InpByt(LZHENV)) == EOF)
			i = 0;

		LZHENV->getbuf |= (i << (8 - j));

		j += 8;
	}

	i                = (WORD)LZHENV->getbuf;
	LZHENV->getbuf <<= 1;
	LZHENV->getlen   = --j;

	return((WORD)(i < 0));
}

STATIC WORD GetByte(struct lzh_env *LZHENV)  /* get one byte */
{
	UWORD i;
	WORD j;

	j = LZHENV->getlen;

	while(j <= 8)
	{
		if((i = InpByt(LZHENV)) == EOF)
			i = 0;

		LZHENV->getbuf |= i << (8 - j);

		j += 8;
	}

	i                = LZHENV->getbuf;
	LZHENV->getbuf <<= 8;
	LZHENV->getlen   = (WORD)(j - 8);

	return((WORD)((i >> 8) & 0xff));
}

STATIC VOID StopHuff(struct lzh_env *LZHENV)
{
	if(LZHENV->lson)
		free(LZHENV->lson);

	if(LZHENV->rson)
		free(LZHENV->rson);

	if(LZHENV->dad)
		free(LZHENV->dad);

	if(LZHENV->text_buf)
		free(LZHENV->text_buf);

	free(LZHENV);
}

STATIC VOID initCRC(ULONG *crctab)
{
	WORD i,j;
	ULONG crc;

	for(i = 0 ; i < 256 ; i++)
	{
		crc = i;

		for(j = 0 ; j < 8 ; j++)
		{
			if(crc & 1)
				crc = (crc >> 1) ^ 0xEDB88320;
			else
				crc >>= 1;
		}

		crctab[i] = crc;
	}
}

/* initialization of tree */
STATIC struct lzh_env *StartHuff(VOID)
{
	struct lzh_env *LZHENV;
	WORD i,j;

	if(!(LZHENV = (struct lzh_env *)malloc(sizeof(struct lzh_env))))
		return(NULL);

	memset(LZHENV,0,sizeof(struct lzh_env));

	LZHENV->lson		= (WORD *)malloc((N +   1) * sizeof(WORD));
	LZHENV->rson		= (WORD *)malloc((N + 257) * sizeof(WORD));
	LZHENV->dad			= (WORD *)malloc((N +   1) * sizeof(WORD));
	LZHENV->text_buf	= (UBYTE *)malloc(text_buf_len);

	if(!LZHENV->lson || !LZHENV->rson || !LZHENV->dad || !LZHENV->text_buf)
	{
		StopHuff(LZHENV);
		return(NULL);
	}

	memset(LZHENV->lson,0,(N + 1) * sizeof(WORD));
	memset(LZHENV->rson,0,(N + 257) * sizeof(WORD));
	memset(LZHENV->dad,0,(N + 1) * sizeof(WORD));
	memset(LZHENV->text_buf,' ',(N - F));

	LZHENV->InpMax = LZHENV->InpPos = (WORD)sizeof(LZHENV->InpBuf);
	LZHENV->OutMax = (WORD)sizeof(LZHENV->OutBuf);

	initCRC(LZHENV->crctab);

	LZHENV->getbuf = LZHENV->getlen = 0;
	LZHENV->match_position = LZHENV->match_length = 0;

	for(i = 0; i < N_CHAR; i++)
	{
		LZHENV->freq[i]		= 1;
		LZHENV->son[i]		= (WORD)(i + T);
		LZHENV->prnt[i + T]	= (WORD)i;
	}

	i = 0;
	j = N_CHAR;

	while(j <= R)
	{
		LZHENV->freq[j] = (UWORD)(LZHENV->freq[i] + LZHENV->freq[i + 1]);
		LZHENV->son[j]	= i;
		LZHENV->prnt[i] = LZHENV->prnt[i + 1] = j;

		i += 2;

		j++;
	}

	LZHENV->freq[T] = 0xffff;
	LZHENV->prnt[R] = 0;

	return(LZHENV);
}

STATIC VOID reconst(struct lzh_env *LZHENV)	/* reconstruction of tree */
{
	UWORD f,l;
	WORD i,k,j;

	/* collect leaf nodes in the first half of the table */
	/* and replace the freq by (freq + 1) / 2. */
	for(i = k = 0; i < T; ++i)
	{
		if(LZHENV->son[i] >= T)
		{
			LZHENV->freq[k] = (UWORD)((LZHENV->freq[i] + 1) / 2);
			LZHENV->son[k]  = LZHENV->son[i];

			k++;
		}
	}

	/* begin constructing tree by connecting sons */
	for(i = 0,j = N_CHAR; j < T; i += 2,j++)
	{
		k = (WORD)(i + 1);
		f = LZHENV->freq[j] = (UWORD)(LZHENV->freq[i] + LZHENV->freq[k]);

		for(k = (WORD)(j - 1); f < LZHENV->freq[k]; k--);
			k++;

		l = (UWORD)((j - k) * 2);

		memmove(&LZHENV->freq[k + 1],&LZHENV->freq[k],l);
		LZHENV->freq[k] = f;

		memmove(&LZHENV->son[k + 1],&LZHENV->son[k],l);
		LZHENV->son[k] = i;
	}

	/* connect prnt */
	for(i = 0; i < T; i++)
	{
		if((k = LZHENV->son[i]) >= T)
			LZHENV->prnt[k] = i;
		else
			LZHENV->prnt[k] = LZHENV->prnt[k + 1] = i;
	}
}

/* increment frequency of given code by one,and update tree */
STATIC VOID update(struct lzh_env *LZHENV,WORD c)
{
	WORD i,j,k,l;

	if(LZHENV->freq[R] == MAX_FREQ)
		reconst(LZHENV);

	c = LZHENV->prnt[c + T];

	do
	{
		k = (WORD)(++LZHENV->freq[c]);

		/* if the order is disturbed,exchange nodes */
		if(k > LZHENV->freq[l = (WORD)(c + 1)])
		{
			while(k > LZHENV->freq[++l]);
				l--;

			LZHENV->freq[c] = LZHENV->freq[l];
			LZHENV->freq[l] = k;

			i = LZHENV->son[c];

			LZHENV->prnt[i] = l;

			if(i < T)
				LZHENV->prnt[i + 1] = l;

			j = LZHENV->son[l];
			LZHENV->son[l] = i;

			LZHENV->prnt[j] = c;

			if(j < T)
				LZHENV->prnt[j + 1] = c;

			LZHENV->son[c] = j;

			c = l;
		}
	}
	while((c = LZHENV->prnt[c]) != 0);   /* repeat up to root */
}

STATIC WORD DecodeChar(struct lzh_env *LZHENV)
{
	UWORD c;

	c = LZHENV->son[R];

	/* travel from root to leaf,*/
	/* choosing the smaller child node (son[]) if the read bit is 0,*/
	/* the bigger (son[]+1) if 1 */
	while(c < T)
	{
		c += GetBit(LZHENV);
		c = LZHENV->son[c];
	}

	c -= T;
	update(LZHENV,c);

	return((WORD)c);
}

STATIC WORD DecodePosition(struct lzh_env *LZHENV)
{
	/* table for decoding the upper 6 bits of position */
	STATIC UBYTE d_code[256] =
	{
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01,
		0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01,
		0x02,0x02,0x02,0x02,0x02,0x02,0x02,0x02,
		0x02,0x02,0x02,0x02,0x02,0x02,0x02,0x02,
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
		0x09,0x09,0x09,0x09,0x09,0x09,0x09,0x09,
		0x0A,0x0A,0x0A,0x0A,0x0A,0x0A,0x0A,0x0A,
		0x0B,0x0B,0x0B,0x0B,0x0B,0x0B,0x0B,0x0B,
		0x0C,0x0C,0x0C,0x0C,0x0D,0x0D,0x0D,0x0D,
		0x0E,0x0E,0x0E,0x0E,0x0F,0x0F,0x0F,0x0F,
		0x10,0x10,0x10,0x10,0x11,0x11,0x11,0x11,
		0x12,0x12,0x12,0x12,0x13,0x13,0x13,0x13,
		0x14,0x14,0x14,0x14,0x15,0x15,0x15,0x15,
		0x16,0x16,0x16,0x16,0x17,0x17,0x17,0x17,
		0x18,0x18,0x19,0x19,0x1A,0x1A,0x1B,0x1B,
		0x1C,0x1C,0x1D,0x1D,0x1E,0x1E,0x1F,0x1F,
		0x20,0x20,0x21,0x21,0x22,0x22,0x23,0x23,
		0x24,0x24,0x25,0x25,0x26,0x26,0x27,0x27,
		0x28,0x28,0x29,0x29,0x2A,0x2A,0x2B,0x2B,
		0x2C,0x2C,0x2D,0x2D,0x2E,0x2E,0x2F,0x2F,
		0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
		0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F
	};

	STATIC UBYTE d_len[256] =
	{
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x05,0x05,0x05,0x05,0x05,0x05,0x05,0x05,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x06,0x06,0x06,0x06,0x06,0x06,0x06,0x06,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x07,0x07,0x07,0x07,0x07,0x07,0x07,0x07,
		0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,
		0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08
	};

	UWORD i,j,c;

	/* recover upper 6 bits from table */
	i = GetByte(LZHENV);
	c = (UWORD)(d_code[i] << 6);
	j = d_len[i];

	/* read lower 6 bits verbatim */
	j -= 2;

	while(j--)
		i = (UWORD)((i << 1) + GetBit(LZHENV));

	return((WORD)(c | (i & 0x3f)));
}

	// LZH decompression

int BTXService::LZH_Decode(FILE *fi,FILE *fo,long filesize,ULONG *CRC_32)
{
	ULONG OUTCRC = 0xffffffff,*crctab;
	struct lzh_env *LZHENV;
	WORD i,j,k,r,c;
	ULONG count;

	if(!(LZHENV = StartHuff()))
		return(-1);

	LZHENV->infile = fi;
	LZHENV->outfile = fo;

	r = N - F;

	crctab = LZHENV->crctab;

	for(count = 0; count < filesize; )
	{
		if((c = DecodeChar(LZHENV)) < 256)
		{
			if(! OutByt(LZHENV,c))
			{
				StopHuff(LZHENV);
				return(-1);
			}

			OUTCRC = FCS_32(OUTCRC,c);
			LZHENV->text_buf[r++] = (UBYTE) c;
			r &= (N - 1);
			count++;
		}
		else
		{
			i = (WORD)((r - DecodePosition(LZHENV) - 1) & (N - 1));
			j = (WORD)(c - 255 + THRESHOLD);

			for(k = 0; k < j; ++k)
			{
				c = LZHENV->text_buf[(i + k) & (N - 1)];

				if(!OutByt(LZHENV,c))
				{
					StopHuff(LZHENV);
					return(-1);
				}

				OUTCRC = FCS_32(OUTCRC,c);
				LZHENV->text_buf[r++] = (UBYTE) c;
				r &= (N - 1);
				count++;
			}
		}
	}

	if(LZHENV->OutPos)
		fwrite(LZHENV->OutBuf,LZHENV->OutPos,1,LZHENV->outfile);

	StopHuff(LZHENV);

	*CRC_32 = OUTCRC;

	return(0);
}

/****************************************************************************/

	// Run length decompression

int BTXService::RLE_Decode(FILE *in,FILE *out,long filesize,ULONG *CRC_32)
{
	enum { STATE_Raw,STATE_Repeat };

	ULONG *crctab;

	if(crctab = (ULONG *)malloc(sizeof(ULONG) * 256))
	{
		ULONG crc = ~0;
		long total = 0;
		int c,lastc = 0,x,n,i;
		int state = STATE_Raw;
		int result = 0;
		BOOL eaten;

		initCRC(crctab);

		while(total < filesize && !result)
		{
			if((c = fgetc(in)) == EOF)
			{
				result = -1;
				break;
			}

			eaten = FALSE;

			switch(state)
			{
				case STATE_Raw:

						// Start a repeat run?

					if(c == 0x12)
					{
						x = lastc;
						eaten = TRUE;
						state = STATE_Repeat;
					}

					break;

				case STATE_Repeat:

						// Two 0x12 bytes in a row, cancel repeat
						// and just send the second 0x12

					if(c == 0x12)
						state = STATE_Raw;
					else
					{
						n = c - 0x20 - 1;	// first char always gets written
						eaten = TRUE;
						state = STATE_Raw;

						for(i = 0 ; !result && total < filesize && i < n ; i++)
						{
							if(fputc(x,out) == EOF)
								result = -1;
							else
							{
								crc = FCS_32(crc,x);
								total++;
							}
						}
					}

					break;
			}

			if(!eaten)
			{
				if(fputc(c,out) == EOF)
					result = -1;
				else
				{
					crc = FCS_32(crc,c);
					total++;
				}
			}

			lastc = c;
		}

		free(crctab);

		*CRC_32 = crc;

		return(result);
	}
	else
		return(-1);
}