#include "stdafx.h"
#include "stdio.h"
#include "memory.h"
#include "assert.h"
#include "lzwtable.h"
#include "lzwcode.h"

/*
CDecodeBitArray
*/
CDecodeBitArray::CDecodeBitArray(DWORD dwInitWidth)// width in bit
{
	m_pbBits=NULL;
	m_dwWidthInByte=0;
	m_dwTail=m_dwHead=0;
	if(dwInitWidth)
		InitBits(dwInitWidth);
}
CDecodeBitArray::~CDecodeBitArray()
{
	ClearBits();
}
void CDecodeBitArray::ClearBits(void)
{
	if(m_pbBits)
		delete m_pbBits;
	m_dwTail=m_dwHead=0;
	m_dwWidthInByte=0;
}
void CDecodeBitArray::InitBits(DWORD dwInitWidth)
{
	ClearBits();
	DWORD dwLength=dwInitWidth/8;
	dwLength+=(dwInitWidth%8)?1:0;
	m_pbBits=new BYTE[dwLength];
	m_dwHead=m_dwTail=0;
	m_dwWidthInByte=dwLength;
}
void CDecodeBitArray::InitBytes(DWORD dwInitWidth)
{
	InitBits(dwInitWidth*8);
}
DWORD CDecodeBitArray::GetLeftBytes(void)
{
	DWORD dwLeftBytes;
	DWORD dwLeftBits=GetLeftBits();
	dwLeftBytes=dwLeftBits/8;
	dwLeftBytes+=(dwLeftBits%8)?1:0;
	return dwLeftBytes;
}
WORD CDecodeBitArray::RemoveBits(int iWidth)
{
	WORD wGet=0;
	for(int i=iWidth-1;i>=0;i--)
	{
		if(RemoveFirstBit())
			SET_BIT_1(wGet,i);
	}
	return wGet;
}
WORD CDecodeBitArray::RemoveFirstBit(void)
{
	BYTE* pbFirstByte=m_pbBits+m_dwHead/8;
	BYTE bFirstByte=*pbFirstByte;
	WORD wGet=(CHECK_BIT_1(bFirstByte,7-m_dwHead%8))?1:0;
	m_dwHead++;
	return wGet;
}
BOOL CDecodeBitArray::AddBytes(BYTE* pbAdd,int iLength)
{
	if(m_pbBits==NULL)
		return FALSE;
	Resort();
	memcpy(m_pbBits+m_dwTail/8,pbAdd,iLength);
	m_dwTail+=8*(DWORD)iLength;
	return TRUE;
}
void CDecodeBitArray::Resort(void)
{// because m_dwTail%8 always equal 0
	if(m_dwHead<8)
		return;
	if(m_dwTail==m_dwHead)
	{
		m_dwTail=m_dwHead=0;
		return;
	}
	DWORD dwLength=GetLeftBytes();
	DWORD dwHead=m_dwHead%8;
	DWORD dwMove=m_dwHead-dwHead;
	memcpy(m_pbBits,m_pbBits+(m_dwHead/8),(int)dwLength);
	m_dwHead=dwHead;
	m_dwTail-=dwMove;
}

/*
class CEncodeBitArray
*/
CEncodeBitArray::CEncodeBitArray(DWORD dwInitWidth)
{
	if(dwInitWidth==0)
		m_pbBits=NULL;
	else
		InitBits(dwInitWidth);
}
CEncodeBitArray::~CEncodeBitArray()
{
	ClearBits();
}
BOOL CEncodeBitArray::InitBits(DWORD dwInitWidth)
{
	ClearBits();
	assert(dwInitWidth);
	m_dwWidthInByte=dwInitWidth/8;
	m_dwWidthInByte+=(dwInitWidth%8)?1:0;
	m_pbBits=new BYTE[m_dwWidthInByte];
	m_dwTail=0;
	return TRUE;
}
void CEncodeBitArray::ClearBits(void)
{
	if(m_pbBits)
		delete m_pbBits;
	m_pbBits=NULL;
}
BOOL CEncodeBitArray::AddBits(WORD wAdd,int iWidth)
{
	if(m_pbBits==NULL)
		return FALSE;
	for(int i=iWidth-1;i>=0;i--)
	{
		BYTE* pbByte=m_pbBits+m_dwTail/8;
		if(CHECK_BIT_1(wAdd,i))
			SET_BIT_1(*pbByte,7-m_dwTail%8);
		else
			SET_BIT_0(*pbByte,7-m_dwTail%8);
		m_dwTail++;
	}
	return TRUE;
}
DWORD CEncodeBitArray::GetBytesWidth(void)
{
	DWORD dwBytes=m_dwTail/8;
	dwBytes+=(m_dwTail%8)?1:0;
	return dwBytes;
}
int CEncodeBitArray::RemoveBytes(BYTE *pbGet,int iWant)
{
	if(m_pbBits==NULL)
		return -1;
	int iTotal=(int)GetBytesWidth();
	if(iWant>iTotal)
		iWant=iTotal;
	if(pbGet!=NULL)
		memcpy(pbGet,m_pbBits,iWant);
	memcpy(m_pbBits,m_pbBits+iWant,iTotal-iWant);
	int iTail=(int)m_dwTail;
	iTail-=iWant*8;
	if(iTail<0)
		iTail=0;
	m_dwTail=iTail;
	return iWant;
}
BOOL CLZWDecode::BeginLZWDecode(const DWORD dwLength,// the compressed length
								FUN_LZWDECODEGETNEXTBYTES pfunLZWGetNextBytes,
								FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte,
								WORD wBuffer,
								FUN_LZWDECODEDBYTES pfunLZWDecodedBytes,
								DWORD dwBytesOnce)
{
	m_dwDecodedByte=0;
	//printf("enter decode press a key\n");
	BYTE *pbNewData=new BYTE[4000],*pbOutData=new BYTE[4000];
	BYTE *pbBuffer=new BYTE[wBuffer];
	BYTE bFirst;
	m_LZWTable.InitLZWTable();
	int iBitWidth=9;
	m_iTotalEntry=LZW_BEGIN_ENTRY;
	BYTE* pbDecodedData;
	WORD wOld,wLastLen;
	m_baContain.InitBits((wBuffer+20)*8);
	int iR=0;
	DWORD dwRead=0;
	while(1)
	{
		if(m_baContain.GetLeftBytes()<5)
		{
			WORD wGetBytes=wBuffer;
			if((DWORD)wGetBytes+dwRead>dwLength)
				wGetBytes=(WORD)(dwLength-dwRead);
			if(wGetBytes!=0)
			{
				pfunLZWGetNextBytes(pbBuffer,wGetBytes);
				m_baContain.AddBytes(pbBuffer,wBuffer);
				dwRead+=wGetBytes;
			}
		}
		int iT=m_iTotalEntry+1;
		iT>>=9;
		iBitWidth=9;
		while(iT>0)
		{
			iT>>=1;
			iBitWidth++;
		}
		WORD wGet=m_baContain.RemoveBits(iBitWidth);
		if(wGet==LZW_END_CODE)
		{
			break;
		}
		if(wGet==LZW_CLEAR_CODE)
		{
			m_LZWTable.InitLZWTable();
			wGet=m_baContain.RemoveBits(9);
			if(wGet==LZW_END_CODE)
				break;
			pbDecodedData=m_LZWTable.GetMatchData(wGet);
			WriteDecode(pbDecodedData,
						pfunLZWPutNextByte,
						pfunLZWDecodedBytes,
						dwBytesOnce);
			wOld=wGet;
			m_iTotalEntry=258;
		}
		else
		{// not clear
			pbDecodedData=m_LZWTable.GetMatchData(wGet);
			if(NULL!=pbDecodedData)
			{// in table
				bFirst=pbDecodedData[2];
				WriteDecode(pbDecodedData,
							pfunLZWPutNextByte,
							pfunLZWDecodedBytes,
							dwBytesOnce);
				if(wOld!=LZW_CLEAR_CODE)
				{// not the first code be read in
					pbDecodedData=m_LZWTable.GetMatchData(wOld);
					wLastLen=*((WORD*)pbDecodedData);
					memcpy(pbNewData,pbDecodedData+2,wLastLen);
					pbNewData[wLastLen]=bFirst;
					m_LZWTable.AddToChild((WORD)m_iTotalEntry,pbNewData,wLastLen+1);
					m_iTotalEntry+=1;
				}
				wOld=wGet;
			}
			else
			{
				pbDecodedData=m_LZWTable.GetMatchData(wOld);
				bFirst=pbDecodedData[2];
				wLastLen=*((WORD*)pbDecodedData);
				memcpy(pbOutData+2,pbDecodedData+2,wLastLen);
				pbOutData[wLastLen+2]=bFirst;
				*((WORD*)pbOutData)=wLastLen+1;
				WriteDecode(pbOutData,
							pfunLZWPutNextByte,
							pfunLZWDecodedBytes,
							dwBytesOnce);
				if(m_iTotalEntry>=4096)
				{
					int _j=0;
				}
				m_LZWTable.AddToChild((WORD)m_iTotalEntry,pbOutData+2,wLastLen+1);
				m_iTotalEntry+=1;
				wOld=wGet;
			}
		}
		//pbDecodedData=table.GetMatchData(wGet);
		//WORD wLen=*((WORD*)pbDecodedData);
		//pbDecodedData+=2;
	}
	delete pbNewData;
	delete pbOutData;
	delete pbBuffer;
	return dwRead==dwLength;
}								
void CLZWDecode::WriteDecode(BYTE* pbWrite,
							FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte,
							FUN_LZWDECODEDBYTES pfunLZWDecodedBytes,
							DWORD dwBytesOnce)
{
	if(pbWrite==NULL)
		return;
	WORD wLength=*((WORD*)pbWrite);
	pbWrite+=2;
	for(DWORD i=0;i<wLength;i++)
	{
		pfunLZWPutNextByte(*pbWrite);
		pbWrite++;
		if((pfunLZWDecodedBytes!=NULL)
			&& (dwBytesOnce)
			&& (m_dwDecodedByte%dwBytesOnce==0))
		{
			pfunLZWDecodedBytes();
		}
	}
	m_dwDecodedByte+=wLength;
}
void CLZWDecode::EndLZWDecode(FUN_LZWDECODEPUTNEXTBYTE pfunLZWPutNextByte)
{
}

/*
CLZWEncode
*/
BOOL CLZWEncode::BeginLZWEncode(const DWORD dwLength,
								FUN_LZWENCODEGETNEXTBYTE pfunLZWGetNextByte,
								FUN_LZWENCODEPUTNEXTBYTES pfunLZWPutNextBytes,
								WORD wBufferLen,
								FUN_LZWENCODEDBYTES pfunLZWEncodedBytes,
								DWORD dwBytesOnce)
{
	m_dwCompressedLength=0;
	int iBufferLen=wBufferLen;
	BYTE bGet;
	m_LZWTable.InitLZWTable();// init the entry table
	m_baContain.InitBits((iBufferLen+8)*8);// init the bit array
	m_baContain.AddBits(LZW_CLEAR_CODE,9);// add the first clear code
	/// below : begin the algorithm
	PLZWENCODEENTRY pCurrent=m_LZWTable.GetHead();
	int iBitWidth;
	DWORD dwEncoded=0;
	for(DWORD i=0;i<dwLength;i++)
	{// for each byte
		if(!pfunLZWGetNextByte(bGet))
			return FALSE;
		PLZWENCODEENTRY pChild=m_LZWTable.FindMatchChild(bGet,pCurrent);
		if(pChild)
		{// has found the continue
			pCurrent=pChild;
		}
		else
		{// not find write last code & add new entry 
			iBitWidth=GetBitWidth();
			WORD wW=pCurrent->wCode;
			m_baContain.AddBits(wW,iBitWidth);// add last code to buffer
			m_LZWTable.AddToChild(bGet,pCurrent);// add last code to table
			if(m_baContain.GetBytesWidth()>(DWORD)iBufferLen)
			{
				m_dwCompressedLength+=(DWORD)iBufferLen;
				pfunLZWPutNextBytes(m_baContain.GetBits(),iBufferLen);
				m_baContain.RemoveBytes(NULL,iBufferLen);
			}
			if(m_LZWTable.GetTableEntryNumber()>=(m_wMaxEntry-3))
			{
				iBitWidth=GetBitWidth();
				m_baContain.AddBits(LZW_CLEAR_CODE,iBitWidth);
				m_LZWTable.InitLZWTable();
			}
			pCurrent=m_LZWTable.FindMatchChild(bGet,m_LZWTable.GetHead());
		}
		dwEncoded++;
		if(pfunLZWEncodedBytes && dwEncoded==dwBytesOnce)         
		{
			pfunLZWEncodedBytes();
			dwEncoded=0;
		}
	}
	iBitWidth=GetBitWidth();
	m_baContain.AddBits(pCurrent->wCode,iBitWidth);// add last code to buffer
	return TRUE;
}
void CLZWEncode::EndLZWEncode(FUN_LZWENCODEPUTNEXTBYTES pfunLZWPutNextBytes)
{
	int iBitWidth=GetBitWidth();
	m_baContain.AddBits(LZW_END_CODE,iBitWidth);
	m_dwCompressedLength+=m_baContain.GetBytesWidth();
	pfunLZWPutNextBytes(m_baContain.GetBits(),(int)m_baContain.GetBytesWidth());
	m_LZWTable.ClearLZWTable();
	m_baContain.ClearBits();
};
int CLZWEncode::GetBitWidth(void)
{
	int iTotal=(int)m_LZWTable.GetTableEntryNumber();
	iTotal>>=9;
	int iBitWidth=9;
	while(iTotal>0)
	{
		iTotal>>=1;
		iBitWidth+=1;
	}
	return iBitWidth;
}