//'AwardMod BIOS Manipulation Tool
//'Copyright (C) 2001 Josef Hill
//'
//'This program is free software; you can redistribute it and/or
//'modify it under the terms of the GNU General Public License
//'as published by the Free Software Foundation; either version 2
//'of the License, or any later version.
//'
//'This program is distributed in the hope that it will be useful,
//'but WITHOUT ANY WARRANTY; without even the implied warranty of
//'MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//'GNU General Public License for more details.
//'
//'You should have received a copy of the GNU General Public License
//'along with this program; if not, write to the Free Software
//'Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.


#include "stdafx.h"
#include "lhaenc.h"



#define  CHAR_BIT 8
#define  UCHAR_MAX 255
#define  DICBIT 13
#define  DICSIZ (1U << DICBIT)
#define  MAXMATCH  256
#define  THRESHOLD  3
#define  PERC_FLAG  0X8000
#define  NC  (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
#define  CBIT  9
#define  CODE_BIT  16
#define  NP  (DICBIT + 1)
#define  NT  (CODE_BIT + 3)
#define  PBIT  4
#define  TBIT  5
#define  NIL 0
#define  MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)


byte maBuf[16 * 1024 + 1];
byte maCLen[NC + 1];
byte maPTLen[NT + 1];
word maCFreq[2* NC -1 + 1];
word maPFreq[2* NP -1 + 1];
word maTFreq[2* NT -1 + 1];
word maCCode[NC + 1];
word maPTCode[NT + 1];
dword maLeft[2 * NC - 1 + 1];
dword maRight[2*NC-1 + 1];
dword maHeap[NC +1 + 1];
word maLenCnt[17 + 1];
byte maText[DICSIZ * 2 + MAXMATCH + 1];
dword maLevel[DICSIZ + UCHAR_MAX + 1 + 1];
byte maChildCount[DICSIZ + UCHAR_MAX + 1 + 1];
dword maPosition[DICSIZ + UCHAR_MAX + 1 + 1];
dword maParent[DICSIZ * 2 + 1];
dword maPrev[DICSIZ * 2 + 1];
dword maNext[MAX_HASH_VAL + 1 + 1];

dword mpBuf;
dword mpCLen;
dword mpPTLen;
dword mpCFreq;
dword mpCCode;
dword mpPFreq;
dword mpPTCode;
dword mpTFreq;
dword mpLeft;
dword mpRight;
dword mpHeap;
dword mpLenCnt;
dword mpText;
dword mpLevel;
dword mpChildCount;
dword mpPosition;
dword mpParent;
dword mpPrev;
dword mpNext;

word * maFreq;
word * maSortPtr;
byte * maLen;

dword  mpFreq;
dword  mpSortPtr;
dword  mpLen;

byte* maIn;
dword mpIn;
dword mlIn;

byte* maOut;
dword mpOut;
dword mlOut;

//'io
dword mP;
dword mMP;
dword mA;
dword mR;
dword mML;
dword mI;
dword mUP;
dword mS;
dword mSBB;
dword mBC;
dword mBfS;
dword mBS;
dword mOM;
dword mOP;
dword mO;
dword mSHE;
dword mN;
dword mHS;
dword mD;
dword mCP;

dword mSEQ;

void clean();
void init_slide();
dword hash(dword iP, byte iC);
dword child(dword iQ, byte iC);
void makechild(dword iQ, byte iC, dword iR);
void split(dword iO);
void insert_node();
void delete_node();
void get_next_match();
dword mRead(dword iP,dword iNP);
void count_maTFreq();
void write_maPTLen(dword iNP,dword iNB ,dword iIS );
void write_maCLen();
void encode_c(dword iC);
void encode_p(dword iP);
void send_block();
void Output(dword iC , dword iP );
void huf_encode_start();
void huf_encode_end();
void putbits(dword iNP , dword iX );
void init_putbits();
void count_len(dword iI);
dword make_tree(dword iNP ,word * iAF , byte * iAL ,word * iAC ) ;
void downheap(dword iI );
void make_len(dword iR );
void make_code(dword iNP ,byte * iAL ,word * iAC );

void __stdcall lhaenc_setinput(byte* iStr, dword* iLen)
{
	dword lC;
	clean();
	
	mlIn = iLen[0];
	maIn = new byte[(mlIn)];
	//maIn = new byte[mlIn];
	for (lC=0;lC<mlIn ;lC++)
	{
		maIn[lC] = iStr[lC];
	}
	mpIn = 0;

	maOut = new byte[(mlIn)];
	//maOut = new byte[mlIn];
	mpOut = 0;

	init_slide();
	huf_encode_start();
	mR = mRead(DICSIZ,DICSIZ + MAXMATCH);
	mML = 0;
	mP = DICSIZ;
	insert_node();
	if (mML > mR) 
	{
		mML = mR;
	}
}


void __stdcall lhaenc_getoutput(byte* iStr, dword* iLen)
{
	dword lC;
	
	mlOut = (mpOut < mlIn ? mpOut : 0);

	for (lC=0;lC< mlOut;lC++)
	{
		iStr[lC]=maOut[lC];
	}
	iLen[0] = mpOut;
	delete maIn;
	delete maOut;
}

void __stdcall lhaenc_work(void)
{
	dword lLML;
	dword lLMP;

	while ((mR > 0) && (mUP == 0)) 
	{
		lLML = mML;
		lLMP = mMP;
		get_next_match();
		if (mML > mR) 
		{
			mML = mR;
		}
		if ((mML > lLML) | (lLML < THRESHOLD))
		{
			Output(maText[mpText + (mP -1)],0); 
		}
		else
		{
			Output(lLML + (UCHAR_MAX + 1 - THRESHOLD),(mP - lLMP -2) & (DICSIZ -1));
			while (--lLML > 0)
			{
				get_next_match();
			}
			if (mML > mR)
			{
				mML = mR;
			}
		}
		if ((mR < 2000) && (mSEQ > 2)) {
			mR = mR;
		}
	}
	huf_encode_end();
}

void clean()
{
	dword lC;

	mML = 0;
	mP = DICSIZ;

	mD = 0;
	mCP = 0;
	mMP = 0;
	mA = 0;
	mUP = 0;
	mS = 0;
	mSBB = 0;
	mBC = 0;
	mBfS = 0;
	mBS = 0;
	mOM = 0;
	mOP = 0;
	mO = 0;
	mSHE = 0;
	mN = 0;
	mHS = 0;

	for (lC=0;lC < (16 * 1024) + 1 ;lC++)
	{
		maBuf[lC] = 0;
	}
	for (lC=0;lC < NC + 1 ;lC++)
	{
		maCLen[lC] = 0;
	}
	for (lC=0;lC < NT + 1  ;lC++)
	{
		maPTLen[lC] = 0;
	}
	for (lC=0;lC < 2 * NC -1 ;lC++)
	{
		maCFreq[lC] = 0;
	}
	for (lC=0;lC < NC + 1 ;lC++)
	{
		maCCode[lC] = 0;
	}
	for (lC=0;lC < 2 * NP ;lC++)
	{
		maPFreq[lC] = 0;
	}
	for (lC=0;lC < NT + 1 ;lC++)
	{
		maPTCode[lC] = 0;
	}
	for (lC=0;lC < NT ;lC++)
	{
		maTFreq[lC] = 0;
	}
	for (lC=0;lC < 2 * NT ;lC++)
	{
		maLeft[lC] = 0;
	}
	for (lC=0;lC < 2 * NC ;lC++)
	{
		maRight[lC] = 0;
	}
	for (lC=0;lC < 2 * NC ;lC++)
	{
		maHeap[lC] = 0;
	}
	for (lC=0;lC < NC + 2 ;lC++)
	{
		maLenCnt[lC] = 0;
	}
	for (lC=0;lC < DICSIZ * 2 + MAXMATCH + 1 ;lC++)
	{
		maText[lC] = 0;
	}
	for (lC=0;lC < DICSIZ + UCHAR_MAX + 2 ;lC++)
	{
		maLevel[lC] = 0;
	}
	for (lC=0;lC < DICSIZ + UCHAR_MAX + 2 ;lC++)
	{
		maChildCount[lC] = 0;
	}
	for (lC=0;lC < DICSIZ + UCHAR_MAX + 2 ;lC++)
	{
		maPosition[lC] = 0;
	}
	for (lC=0;lC < DICSIZ * 2 + 1 ;lC++)
	{
		maParent[lC] = 0;
	}
	for (lC=0;lC < DICSIZ * 2 + 1 ;lC++)
	{
		maPrev[lC] = 0;
	}
	for (lC=0;lC < MAX_HASH_VAL + 2 ;lC++)
	{
		maNext[lC] = 0;
	}
}

void init_slide(void)
{
	dword lI;
	for (lI = DICSIZ; lI <DICSIZ + UCHAR_MAX + 1;lI++)
	{
		maLevel[mpLevel + lI] = 1;
		maPosition[mpPosition + lI] = NIL;
	}
	for (lI = DICSIZ; lI <(DICSIZ * 2) ;lI++)
	{
		maParent[mpParent + lI] = NIL;
	}
	mA = 1;
	for (lI = 1; lI <DICSIZ - 1;lI++)
	{
		maNext[mpNext + lI] = lI + 1;
	}
	maNext[mpNext  + DICSIZ -1] = NIL;
	for (lI = DICSIZ * 2; lI <MAX_HASH_VAL + 1;lI++)
	{
		maNext[mpNext  + lI] = NIL;
	}
}

dword hash(dword iP, byte iC)
{
	return (iP + (iC<<(DICBIT - 9)) + DICSIZ*2);
}

dword child(dword iQ, byte iC)
{
	dword lR;
	lR = maNext[mpNext + hash(iQ,iC)];
	maParent[mpParent] = iQ;
	while (maParent[mpParent + lR] != iQ)
	{
		lR = maNext[mpNext + lR];
	}
	return lR;
}

void makechild(dword iQ, byte iC, dword iR)
{
	dword lH;
	dword lT;
	lH = hash(iQ,iC);
	lT = maNext[mpNext + lH];
	maNext[mpNext + lH] = iR;
	maNext[mpNext + iR] = lT;
	maPrev[mpPrev + lT] = iR;
	maPrev[mpPrev + iR] = lH;
	maParent[mpParent + iR] = iQ;
	maChildCount[mpChildCount + iQ]++;
}

void split(dword iO)
{
	
	dword lN;
	dword lT;
	lN = mA;
	mA = maNext[mpNext + lN];
	maChildCount[mpChildCount + lN] = 0;
	lT = maPrev[mpPrev + iO];
	maPrev[mpPrev + lN] = lT;
	maNext[mpNext + lT] = lN;
	lT = maNext[mpNext + iO];
	maNext[mpNext + lN] = lT;
	maPrev[mpPrev + lT] = lN;
	maParent[mpParent + lN] = maParent[ mpParent + iO];
    maLevel[mpLevel + lN] = mML;
    maPosition[mpPosition + lN] = mP;
    makechild (lN, (byte) maText[mpText + (mMP + mML)], iO);
    makechild (lN, (byte) maText[mpText + (mP + mML)], mP);
}










void insert_node()
{
	dword lQ;
    dword lR;
    dword lJ;
    dword lT;
    dword lT1;
    dword lT2;
	byte lC;
	
    if (mML >= 4)
	{
        mML--;
        lR = (mMP + 1) | DICSIZ;
        while ((lQ = maParent[mpParent + lR]) == NIL)
		{
            lR = maNext[mpNext + lR];
        }
        while ((maLevel[mpLevel + lQ]) >= mML)
		{
			lR = lQ;
            lQ = maParent[mpParent + lQ];
        }
        lT = lQ;
        while (maPosition[mpPosition + lT] >= PERC_FLAG )
		{
            maPosition[mpPosition + lT] = mP;
            lT = maParent[mpParent + lT];
		}
        if (lT < DICSIZ) 
		{
			maPosition[mpPosition + lT] = mP | PERC_FLAG;
		}
	}
	else 
	{
		lQ = maText[mpText + (mP)] + DICSIZ;
		lC = (byte) maText[mpText + (mP + 1)];
        if ((lR = child(lQ, lC)) == NIL) 
		{
            makechild (lQ, lC, mP);
            mML = 1;
            return;
        }
        mML = 2;
    }
	
    while (0 == 0)
	{
		
        if (lR >= DICSIZ) 
		{
            lJ = MAXMATCH;
            mMP = lR;
        } 
		else 
		{
            lJ = maLevel[mpLevel + lR];
            mMP = maPosition[mpPosition + lR] & (~PERC_FLAG);
        }
        if (mMP >= mP) 
		{
            mMP -=  DICSIZ;
        }
        lT1 = mpText + (mP + mML);
        lT2 = mpText + (mMP + mML);
		
        while (mML < lJ)
		{
            if (maText[lT1] != maText[lT2]) 
			{
                split (lR);
                return;
            }
            mML++;
            lT1++;
            lT2++;
        }
		
        if (mML >= MAXMATCH) 
		{
			break;		
		}
        maPosition[mpPosition + lR] = mP;
        lQ = lR;
        if ((lR = child(lQ,(byte)  maText[lT1])) == NIL) 
		{
            makechild (lQ, (byte)maText[lT1], mP);
            return;
        }
        mML++;
    }
	
    lT = maPrev[mpPrev + lR];
    maPrev[mpPrev + mP] = lT;
    maNext[mpNext + lT] = mP;
    lT = maNext[mpNext + lR];
    maNext[mpNext + mP] = lT;
    maPrev[mpPrev + lT] = mP;
    maParent[mpParent + mP] = lQ;
    maParent[mpParent + lR] = NIL;
    maNext[mpNext + lR] = mP;  /* special use of next() */
}

void delete_node()
{
    dword lQ;
    dword lR;
    dword lS;
    dword lT;
    dword lU;
    if (maParent[mpParent + mP] == NIL) 
	{ 
		return;
	}
    lR = maPrev[mpPrev + mP];
    lS = maNext[mpNext + mP];
    maNext[mpNext + lR] = lS;
    maPrev[mpPrev + lS] = lR;
    lR = maParent[mpParent + mP];
    maParent[mpParent + mP] = NIL;
    if (lR >= DICSIZ) 
	{ 
		return;
	}
    if (--maChildCount[mpChildCount + lR] > 1) 
	{ 
		return;
	}
    lT = maPosition[mpPosition + lR] & (~PERC_FLAG);
    if (lT >= mP)
	{ 
		lT -= DICSIZ;
	}
    lS = lT;
    lQ = maParent[mpParent + lR];
	lU = maPosition[mpPosition + lQ];
    while ((lU & PERC_FLAG) != 0)
	{
        lU = lU & ~PERC_FLAG;
        if (lU >= mP) 
		{ 
			lU = lU - DICSIZ;
		}
        if (lU > lS) 
		{ 
			lS = lU;
		}
        maPosition[mpPosition + lQ] = (lS | DICSIZ);
        lQ = maParent[mpParent + lQ];

		lU = maPosition[mpPosition + lQ];
    }
    if (lQ < DICSIZ) 
	{
        if (lU >= mP) 
		{
			lU = lU - DICSIZ;
		}
        if (lU > lS) 
		{ 
			lS = lU;
		}