#include "stdio.h"
#include "fcntl.h"
#include "tomlib.h"
#include "setjmp.h"

#include "pq.h"
#include "huffman.h"
#include "pack.h"

#define STATIC

#define MIN_LENGTH		3		/* minimum to be compressed */
#define MAXCODELENGTH 0x0f
#define SENDLEN  	  0xfff		/* MUST BE 00001111111 */

typedef unsigned char uchar;
typedef unsigned short uint;


jmp_buf bit_to_long = {0};


void *ck_alloc(unsigned int len)
{
	void *calloc(),*s;
	if ((s = calloc(len,1)) == NULL)
		panic("can't allocate memory");
}

STATIC uint ln2(register uint charset)
{
	register int ln;
	for (ln = 0; charset > 1; charset >>= 1)
		ln++;
	return ln;
}

typedef struct huff_code {
		unsigned bitcode;
		uchar	 bitcnt;
		} huff_code;

typedef struct huff_icode {
		uchar bitcode;
		uchar bitcnt;
		} huff_icode;


STATIC void	swap_ptr(huff_tab **c1,huff_tab **c2);
STATIC int  cmp_ptr (huff_tab **c1,huff_tab **c2);
STATIC void _fastcall addbit(huff_tab *cpt);
STATIC void _fastcall bit_write(register unsigned value,register int length);
STATIC uint _fastcall bit_read(register int length);
STATIC uint _fastcall huff_read(huff_icode *icode,int maxbit);
/**
*** generate Huffman codes for every character 
**/

panic(char *s)
{
	printf("%s\n",s);
	exit(1);
}

STATIC void swap_ptr(huff_tab **c1,huff_tab **c2)
{
	void *tmp;
	tmp = *c1;
	*c1 = *c2;
	*c2 = tmp;
}
STATIC int cmp_ptr(huff_tab **c1,huff_tab **c2)
{
	return (*c2)->count-(*c1)->count;
}


STATIC int current_max_bit;

STATIC void _fastcall addbit(register huff_tab *cpt)
{
	while (cpt) {
		addbit(cpt->lpt);
		if (++cpt->bitcnt > current_max_bit)
			longjmp(bit_to_long,1);
		cpt = cpt->rpt;							// faster then recursion
		}
}

//**********************************************************************
// generate from huff_tab a field bitlength which holds the best bitlength
// for each character. allthough it would be possible to generate codes
// at the same time this has been avoided to make it easier usable when
// the data are read back
//**********************************************************************


STATIC int gen_length(uchar *bitlength,huff_tab *hufftab,
													int charset,int maxbit)
{
	PQ *pq;
	huff_tab *cpt,*cpt1,*cpt2,*cpt3;
	register int i;
	long bsum;
	int multiply ;
	int anzcodes;

	current_max_bit = maxbit;			// we will not allow a longer table
										// so the table is made more "flat"
	if (setjmp(bit_to_long))
		{
		free(pq);
		for (i=charset,cpt=hufftab;--i >= 0;cpt++)
			{
			if (cpt->count > 1)
				cpt->count /= 2;
			cpt->bitcnt = 0;
			cpt->lpt = cpt->rpt = NULL;
			}
		multiply *= 2;
		}
	else
		multiply = 1;

	pq = pq_create(charset,sizeof(huff_tab*),cmp_ptr,swap_ptr,(void*)0);

	for (anzcodes = 0,i=charset,cpt=hufftab;--i >= 0;cpt++)
		if (cpt->count)
			{
		  	pq_ins(pq,&cpt);
			anzcodes++;
			}

	if (anzcodes == 1)				// the buffer is degenerated
		{							// so we must set one code
		pq_del(pq,&cpt1);
		addbit(cpt1);
		}
	else {

		cpt3 = hufftab+charset;
		while(pq_del(pq,&cpt1) && pq_del(pq,&cpt2))
 			{
			addbit(cpt1);
			addbit(cpt2);
			cpt3->lpt = cpt1;
			cpt3->rpt = cpt2;
			cpt3->bitcnt = cpt2->bitcnt;
			cpt3->count= cpt1->count+cpt2->count;
			pq_ins(pq,&cpt3);
			cpt3++;
	  		}
		}

	for (bsum = 0,i=charset,cpt=hufftab; i ;cpt++,--i)
		{
		bsum += cpt->bitcnt*cpt->count;
		*bitlength++ = cpt->bitcnt;
		}

	free(pq);
	return (int)((bsum+15)/8*multiply);
}

//**********************************************************************
// generate from huff_tab a field bitlength which holds the best bitlength
// for each character. allthough it would be possible to generate codes
// at the same time this has been avoided to make it easier usable when
// the data are read back
//**********************************************************************


STATIC int gen_code(huff_code *hufftab,uchar *bitlength,int charset)
{
	register int loop,bitval,bitmask,first,lastcode,length;
	for (loop = 0; loop < charset;loop++)
		{
		hufftab[loop].bitcnt  = bitlength[loop];
		hufftab[loop].bitcode = 0xffff;
		}

	lastcode = 0;
	bitmask  = 1;
	first = 1;

	for (length = 16; length >= 1; length--,bitmask <<= 1)
		for (loop = 0; loop < charset;loop++)
			{
			if (hufftab[loop].bitcnt  == length)
				{
				if (!first)
					{
					lastcode += bitmask;
					}
				first = 0;
				hufftab[loop].bitcode = lastcode & ~(0xffff >> length);
				}
			}
}
	



STATIC gen_invtab(huff_icode *inv,huff_code *tab,int charset,int max_bit)
{
	register int loop,ival,ianz,bitcnt;

	for (loop = 0; loop < charset; loop++)
		{
		ival = tab[loop].bitcode >> (16-max_bit);
		if ((bitcnt = tab[loop].bitcnt) == 0)
			continue;
		ianz = 1 << (max_bit-tab[loop].bitcnt);
		for ( ; --ianz >= 0;ival++)
			{
			inv[ival].bitcode = loop;
			inv[ival].bitcnt  = bitcnt;
			}
		}
}

#define HIGH_BIT 16
unsigned short bit_value = 0;
unsigned short far *bit_ptr = NULL;
unsigned int   bit_drin= 0;

#define dbrange(x) 0			// ((x) >= 0x1b0 && (x) <= 0x1d0)

STATIC void bit_flush(void)
{
	if (bit_drin)
		*bit_ptr++ = bit_value;
}

STATIC void bit_init(void far *ptr)
{
	bit_ptr  = ptr;
	bit_drin = 0;
	bit_value = 0;
}


STATIC void _fastcall bit_write(register unsigned value,register int length)		
{
	int fits = HIGH_BIT - bit_drin;

	if (length <= fits)
		{
		*bit_ptr |= value >> bit_drin;
		if (length == fits)
			{
			*bit_ptr++ = bit_value | (value >> bit_drin);
			bit_drin  = 0;
			bit_value = 0;
			}
		else 
			{
			bit_value |= value >> bit_drin;
			bit_drin+=length;
			}
		}
	else
		{
		*bit_ptr++ = bit_value | (value >> HIGH_BIT-fits);
		bit_value  = value <<= fits;
		bit_drin = length-fits;
		}
}
STATIC uint _fastcall bit_read(register int maxbit)
{
	register unsigned value;

	if (maxbit <= HIGH_BIT-bit_drin)
		{
		value = (*bit_ptr << bit_drin) >> (HIGH_BIT-maxbit);
		}
	else {
		value = ((bit_ptr[0] << bit_drin) | (bit_ptr[1] >> (HIGH_BIT-bit_drin))) 
				>> (HIGH_BIT-maxbit);
		}		

	if ((bit_drin += maxbit) >= HIGH_BIT)
		bit_drin -= HIGH_BIT,bit_ptr++;

	return value;
}	

STATIC uint _fastcall huff_read(huff_icode *icode,int maxbit)
{
	register int loop,value;unsigned int lmask,*lptr;

	if (maxbit <= HIGH_BIT-bit_drin)
		{
		value = (*bit_ptr << bit_drin) >> (HIGH_BIT-maxbit);
		}
	else {
		value = ((bit_ptr[0] << bit_drin) | (bit_ptr[1] >> (HIGH_BIT-bit_drin))) 
				>> (HIGH_BIT-maxbit);
		}		

	if ((bit_drin += icode[value].bitcnt) >= HIGH_BIT)
		bit_drin -= HIGH_BIT,bit_ptr++;

	return icode[value].bitcode;
}	

//****************************************************************************
// reading / writing characterset bitcounts
//  0) write no characterset at all
//  1) write number of characters (4 Bits) with number of bits (4 Bits) PKZIP
//  2) write for each character number of bits (4 Bits)
//  3) set bitval to 0;
//			while (bitval < bitcnt) write (0x10,2)
//			while (bitval > bitcnt) write (0x11,2)
//			write (0,1)
//  4) if (bitval OK) write (0,1)
//	   else write (1,1),write (number of Bits,4)
//****************************************************************************

unsigned bit_write_method = 0;


int write_cnt0(register uchar *bitlength,int charset,uint test)
{
	return 0;
}

int read_cnt0(register uchar *bitlength,int charset)
{
	int mask,bits;
	for (bits = 0,mask = 1;mask < charset ; mask <<= 1)
		bits++;
	memset(bitlength,bits,charset);
}
//****************************************************************************

int write_cnt1(register uchar *bitlength,int charset,uint test)
{
	register int needed,loop,id;

	for (id = 0,loop=0,needed=0; loop < charset;loop++,bitlength++)
		{
		if (bitlength[0] == bitlength[1] && id < 15 && loop < charset-1)
			id++;
		else
			{
			if (test) bit_write(((bitlength[0] << 4) | id) << 8,8);
			id = 0;
			needed++;
			}
		}
	return needed;
}

read_cnt1(uchar *bitlength,int charset)
{
	register int loop,id,val;

	do 	{
		id  = bit_read(8);
		val = id >> 4;
		id  &= 0x0f;
		do {
			*bitlength++ = val;
			charset--;
			} while (--id >= 0);
		} while (charset > 0);
}


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

int write_cnt2(register uchar *bitlength,int charset,uint test)
{
	if (!test)
		return charset/2;

	do {
		bit_write(*bitlength<<(HIGH_BIT-4),4);	// 4 Bit
		bitlength++;
		} while (--charset);
}
int read_cnt2(register uchar *bitlength,int charset)
{
	do {
		*bitlength++ = bit_read(4);		// 4 Bit
		} while (--charset);
}

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

int write_cnt3(register uchar *bitlength,int charset,uint test)
{
	register int needed,loop,bitval;

	for (bitval = 0,loop=0,needed=0; loop < charset;loop++,bitlength++)
		{
		while (bitval > bitlength[0])
			{
			bitval--,needed+=2;
			if (test)
				bit_write(0x01 << (HIGH_BIT-2),2);
			}
		while (bitval < bitlength[0])
			{
			bitval++,needed+=2;
			if (test)
				bit_write(0x00 << (HIGH_BIT-2),2);
			}
		if (test)
			bit_write(0x1 << (HIGH_BIT-1),1);
		needed++;
		}
	return (needed+7)/8;
}
int read_cnt3(register uchar *bitlength,int charset)
{
	register int needed,loop,bitval;

	for (bitval = 0; --charset >= 0;)
		{
		while (bit_read(1) == 0)
			if (bit_read(1))
				bitval--;
			else
				bitval++;
		*bitlength++ = bitval;
		}
}
//****************************************************************************

int write_cnt4(register uchar *bitlength,int charset,uint test)
{
	register int needed,bitval;

	for (bitval = 0,needed=0; --charset >= 0;bitlength++)
		{
		if (bitval != bitlength[0])
			{
			bitval = bitlength[0],needed+=5;
			if (test)
				{
				bit_write(1 << (HIGH_BIT-1),1);
				bit_write( bitlength[0] << (HIGH_BIT-4),4);
				}
			}
		else
			{
			if (test)
				bit_write(0 << (HIGH_BIT-1),1);
			needed++;
			}
		}
	return (needed+7)/8;
}

int read_cnt4(register uchar *bitlength,int charset)
{
	register int bitval;

	for (bitval = 0; --charset >= 0;bitlength++)
		{
		if (bit_read(1))
			bitval = bit_read(4);
		*bitlength = bitval;
		}
}

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

typedef int (*wrf)(register uchar *,int,uint);
typedef int (*rdf)(register uchar *,int);

wrf write_fun[] = { write_cnt0,write_cnt1,write_cnt2,write_cnt3,write_cnt4};
rdf read_fun[]  = {  read_cnt0, read_cnt1, read_cnt2, read_cnt3, read_cnt4};


test_wr_cnt(uchar *bitlength,int charset)
{
	uint needed = 0xffff,len,method;

	bit_write_method = 1;

	for (method = 1;method < LENGTH(write_fun);method++) 
		{
		len = (*write_fun[method])(bitlength,charset,FALSE);
		if (len < needed)
			bit_write_method = method,needed = len;

		}

	return needed;
}

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




#define LITLEN 256		// characterset for literal characters
#define LENLEN 16		// characterset for length 0..15
#define INDLEN (4096 >> INDSHIFT)	// characterset for index = (0..4096) >> 4
#define MASLEN 256		// characterset for packmask
#define EXTLEN 256		// characterset for extended length
#define INDSHIFT 4
#define INDMASK  0x0f

#define LIT_MAX 12		// MAXIMUM needed bits for each charset
#define IND_MAX 11
#define LEN_MAX 7
#define MAS_MAX 11
#define EXT_MAX 11

#define LIT_FLAG 0
#define IND_FLAG 3
#define LEN_FLAG 6
#define MAS_FLAG 9
#define EXT_FLAG 12


uint do_huff    = 0;	
uint huff_saved = 0;



hs_count(huff_tab *lit_tab,
		huff_tab *len_tab,
		huff_tab *ind_tab,
		huff_tab *mas_tab,
		huff_tab *ext_tab,uchar far *pbuffer,uint packlen)
{
	register int uloop;
	register uchar packmask;
	int length;unsigned index;

	for (uloop = 1;packlen > 0;packmask <<= 1)
		{
		if (--uloop == 0)
			{
			packmask    = *pbuffer++,packlen--;
			mas_tab[packmask].count++;
			uloop = 8;
			}
		if ((packmask & 0x80) == 0)				/* this byte is literally */
			{
			lit_tab[*pbuffer++].count++;
			packlen--;
			}
		else
			{									/* next 2 bytes coded     */
			index = *(int far *)pbuffer;		/* 4 bit length			  */
			length = (index >> 12);
			ind_tab[(index & SENDLEN) >> INDSHIFT].count++;
			len_tab[length].count++;
			if (length == MAXCODELENGTH)		/* length > 18			  */
				{								/* use next byte for length*/
				ext_tab[pbuffer[2]].count++;
				pbuffer += 3;
				packlen -= 3;
				}
			else {
				packlen -= 2;
				pbuffer += 2;
				}
			}			
		}
}

#define HWRITE(x,tab) bit_write(tab[x].bitcode,tab[x].bitcnt)

hs_write(huff_code *lit_code,
		huff_code *len_code,
		huff_code *ind_code,
		huff_code *mas_code,
		huff_code *ext_code,uchar far *pbuffer,uint packlen)
{
	register int uloop;
	register uchar packmask;
	int length;unsigned index;

	for (uloop = 1;packlen > 0;packmask <<= 1)
		{
		if (--uloop == 0)
			{
			packmask    = *pbuffer++,packlen--;
			HWRITE(packmask,mas_code);
			uloop = 8;
			}
		if ((packmask & 0x80) == 0)				/* this byte is literally */
			{
			HWRITE(*pbuffer,lit_code);
			pbuffer++;
			packlen--;
			}
		else
			{									/* next 2 bytes coded     */
			index = *(int far *)pbuffer;		/* 4 bit length			  */
			length = (index >> 12);

			HWRITE(length,len_code);
			index &= SENDLEN;
			HWRITE(index >> INDSHIFT,ind_code);
			bit_write((index&INDMASK) << (HIGH_BIT-INDSHIFT),INDSHIFT);

    		if (length == MAXCODELENGTH)		/* length > 18			  */
				{								/* use next byte for length*/
				HWRITE(pbuffer[2],ext_code);
				pbuffer += 3;
				packlen -= 3;
				}
			else {
				pbuffer += 2;
				packlen -= 2;
				}
			}			
		}
}

unsigned  summup(register huff_tab *tab,uint charset)
{
	uint sum = 0;
	do {
		sum += tab->count;
		tab++;
		} while (--charset);
	return sum;
}


//
// check whether this code should be huffed
// do some (de)allocation at the same time
//
huff_code *hs_wr_code(huff_tab *tab,int charset,int maxbit,uint do_flag)
{
	uchar *bitlength;
	huff_code *code;
	uint   huff_len;
	int    needed,loop;
	uint   flatlen = ln2(charset);					// number of bits in charset
	uint maxlen = (uint)((long)summup(tab,charset) * flatlen / 8);
													// used if stored flat

	bitlength = ck_alloc(charset);

	huff_len = gen_length(bitlength,tab,charset,maxbit);

	needed =   test_wr_cnt(bitlength,charset);

	code = ck_alloc(charset*sizeof(huff_code));

	if (needed + huff_len < maxlen)
		{
		huff_saved += maxlen - (needed + huff_len);
		do_huff |= bit_write_method << do_flag;
		(*write_fun[bit_write_method])(bitlength,charset,TRUE);
		}
	else
		{
		memset(bitlength,flatlen,charset);			// generate flat characterset
		}

	gen_code(code,bitlength,charset);

	free(bitlength);
	free(tab);
	return code;
}

hs_pack(uchar far *hbuffer,uint plen,uchar far *pbuffer,uint length)
{
	huff_tab *lit_tab,*len_tab,*ind_tab,*mas_tab,*ext_tab;
	huff_code *lit_code,*len_code,*ind_code,*mas_code,*ext_code;
	uint   huff_len;
	register int loop;

	memset(hbuffer,0,plen);

	lit_tab  = ck_alloc(LITLEN*2*sizeof(huff_tab));
	ind_tab  = ck_alloc(INDLEN*2*sizeof(huff_tab));
	len_tab  = ck_alloc(LENLEN*2*sizeof(huff_tab));
	mas_tab  = ck_alloc(MASLEN*2*sizeof(huff_tab));
	ext_tab  = ck_alloc(EXTLEN*2*sizeof(huff_tab));

	hs_count(lit_tab,len_tab,ind_tab,mas_tab,ext_tab,pbuffer,length);

	do_huff    = 0;
	huff_saved = 0;

	bit_init(hbuffer+4);

	lit_code = hs_wr_code(lit_tab,LITLEN,LIT_MAX,LIT_FLAG);
	ind_code = hs_wr_code(ind_tab,INDLEN,IND_MAX,IND_FLAG);
	len_code = hs_wr_code(len_tab,LENLEN,LEN_MAX,LEN_FLAG);
	mas_code = hs_wr_code(mas_tab,MASLEN,MAS_MAX,MAS_FLAG);
	ext_code = hs_wr_code(ext_tab,EXTLEN,EXT_MAX,EXT_FLAG);

	if (do_huff == 0 )						// there is nothing to do
		{	
		return 0xffff;
		}

	if (length - huff_saved + 6 >= plen)	// or its not worth the effort	
		{								
		return 0xffff;
		}


	((short far *)hbuffer)[0] = do_huff;
	((short far *)hbuffer)[1] = length;

	hs_write(lit_code,len_code,ind_code,mas_code,ext_code,pbuffer,length);

	free(lit_code);
	free(ind_code);
	free(len_code);
	free(mas_code);
	free(ext_code);

	bit_flush();

	return (uchar far *)bit_ptr - (uchar far *)pbuffer;
}


huff_icode *hs_rd_code(int charset,int maxbit,uint flatlen,int do_flag)
{
	uchar *bitlength;
	huff_code *code;
	huff_icode *icode;
	register int loop;

	bitlength = ck_alloc(charset);

	(*read_fun[(do_huff >> do_flag) & 0x07])(bitlength,charset);

	code = ck_alloc(charset*sizeof(huff_code));
	gen_code(code,bitlength,charset);
	free(bitlength);

	icode = ck_alloc((1<<maxbit)*sizeof(huff_icode));
	gen_invtab(icode,code,charset,maxbit);
	free(code);
	return icode;
}

hs_unpack(uchar far *ubuffer,uchar far *hbuffer,uint packlen)
{
	huff_icode *lit_icode,*len_icode,*ind_icode,*mas_icode,*ext_icode;
	register int uloop;
	register uchar packmask;
	int length;unsigned index;
	uchar far *sbuffer = ubuffer;

	do_huff = ((short far *)hbuffer)[0];
	packlen = ((short far *)hbuffer)[1];

	bit_init(hbuffer+4);

	lit_icode = hs_rd_code(LITLEN,LIT_MAX,8,LIT_FLAG);
	ind_icode = hs_rd_code(INDLEN,IND_MAX,8,IND_FLAG);
	len_icode = hs_rd_code(LENLEN,LEN_MAX,4,LEN_FLAG);
	mas_icode = hs_rd_code(MASLEN,MAS_MAX,8,MAS_FLAG);
	ext_icode = hs_rd_code(EXTLEN,EXT_MAX,8,EXT_FLAG);

	for (uloop = 1;packlen > 0;packmask <<= 1)
		{
		if (--uloop == 0)
			{
			packmask    = huff_read(mas_icode,MAS_MAX),packlen--;
			uloop = 8;
			}
		if ((packmask & 0x80) == 0)				/* this byte is literally */
			{
			*ubuffer++ = huff_read(lit_icode,LIT_MAX),packlen--;
			}
		else
			{									/* next 2 bytes icoded     */
			length = huff_read(len_icode,LEN_MAX)+MIN_LENGTH;
			index  = huff_read(ind_icode,IND_MAX) << INDSHIFT;
			index += bit_read(INDSHIFT);

			if (length == MAXCODELENGTH+MIN_LENGTH)	/* length > 18			  */
				{								/* use next byte for length*/
				length  = huff_read(ext_icode,EXT_MAX);		/* icode is 3 bytes		  */
				packlen -= 3;
				}
			else {
				packlen -= 2;
				}
									/* copy BYTEWISE with OVERWRITE */
			if (index == 1)			// memcpy will not work as it copies WORDS
				memset(ubuffer,*(ubuffer-1),length);
			else
				memcpy(ubuffer,ubuffer-index,length);

			ubuffer += length;
			}			
		}

	free(lit_icode);
	free(ind_icode);
	free(len_icode);
	free(mas_icode);
	free(ext_icode);

	return ubuffer-sbuffer;
}


#ifdef TEST 

/**
**/



#define BSIZE   4096
#define CHARSET 256

unsigned char buffer[BSIZE];
unsigned char pbuffer[BSIZE];
unsigned char ubuffer[BSIZE];


main(int argc,char *argv[])
{
	int  fd;
	uint loop,rd,code;
	uint hufflen;
	long inlen = 0,outlen = 0;
	long time,ptime=0,utime=0;
	
	if ((fd = open(argv[1],O_RDONLY|O_BINARY)) < 0)
		return 1;

	tx_init();
	
	

	while ((rd = read(fd,buffer,BSIZE)) > 0)
		{
		inlen += rd;

		mikro_diff();
		hufflen = huff_pack(pbuffer,BSIZE,buffer,rd,CHARSET,12);
		ptime += mikro_diff();
		
//		printf("%5d --> %5d\n",rd,hufflen);
		if (hufflen == 0xffff)	
			{
			outlen += rd;
			continue;
			}
		outlen += hufflen;

		memset(pbuffer+hufflen,0xaa,3);

		mikro_diff();
		huff_unpack(ubuffer,pbuffer,rd,CHARSET,12);
		utime += mikro_diff();

		for (loop = 0; loop < rd; loop++)
			if (buffer[loop] != ubuffer[loop])
				{
				char b[48];
				printf("differenz at %04x\n",loop);
				memcpy(b,buffer+loop-16,48);
				hexdn(b,48);
				printf("\n");
				memcpy(b,ubuffer+loop-16,48);
				hexdn (b,48);
				exit(1);
				}

		}

	printf("inlen %5ld --> outlen %5ld ptime %5ld utime %5ld",inlen,outlen,ptime,utime);
			
	printf(" pack %5ld unpackc %5ld\n",
			inlen*1000/ptime,
			inlen*1000/utime
			);

	exit(0);
}
#endif