lzwtable.cpp

用VC++实现LZW算法

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"  
#include "string.h"
#include "memory.h"         
#include "conio.h"
#include "lzwcode.h"
#include "lzwtable.h"

/*
class CLZWEncodeTable
*/
CLZWDecodeTable::CLZWDecodeTable(BOOL fInit)
{
	m_pbContain=NULL;
	m_dwTableEntryNumber=0;
	if(fInit)
		InitLZWTable();
}
CLZWDecodeTable::~CLZWDecodeTable()
{
	ClearDecodeTable();
}
void CLZWDecodeTable::ClearDecodeTable(void)
{   
	if(m_pbContain==NULL)
		return;
	for(int i=0;i<4096;i++)
	{
		if(m_pbContain[i])
			delete (m_pbContain[i]);
	}
	delete m_pbContain;
	m_pbContain=NULL;
	m_dwTableEntryNumber=0;
}
void CLZWDecodeTable::InitLZWTable(void)
{
	ClearDecodeTable();
	m_pbContain=new BYTE*[4096];
	int iSize=sizeof(m_pbContain);
	//if(NULL==m_pbContain)
	//	AfxMessageBox("error new m_pbContain=BYTE*[4096]");
	for(int i=0;i<4096;i++)
	{
		m_pbContain[i]=NULL;
	}
	for(i=0;i<=255;i++)
	{
		m_pbContain[i]=new BYTE[1+2];
		*((WORD*)m_pbContain[i])=1;
		m_pbContain[i][2]=(BYTE)i;
	}
	m_dwTableEntryNumber=LZW_BEGIN_ENTRY;
}
BYTE* CLZWDecodeTable::GetMatchData(WORD wCode)
{
	return m_pbContain[wCode];
}
void CLZWDecodeTable::AddToChild(WORD wCode,BYTE *pbContain,int iLength)
{
	ASSERT(wCode<4096);
	if(m_pbContain[wCode])
		delete m_pbContain[wCode];
	m_pbContain[wCode]=new BYTE[iLength+2];
	*((WORD*)m_pbContain[wCode])=(WORD)iLength;
	memcpy(m_pbContain[wCode]+2,pbContain,iLength);
}

/*
class CLZWEncodeTable
*/
CLZWEncodeTable::CLZWEncodeTable(BOOL fInit)
{
	if(fInit)
		InitLZWTable();
	else
	{
		m_dwTableEntryNumber=0;
		m_EntryHead.pRightBrother=NULL;
		m_EntryHead.pChild=NULL;
	}
}
CLZWEncodeTable::~CLZWEncodeTable()
{
	ClearLZWTable();
}
void CLZWEncodeTable::ClearLZWTable(void)
{
	if(m_EntryHead.pChild==NULL)
		return;
	m_dwTableEntryNumber=0;
	int iRe=0;
	while(m_EntryHead.pChild)
	{
		RemoveFirstChild();
		iRe++;
		//printf("remove %d\n",++iRe);;
	}
}
void CLZWEncodeTable::RemoveFirstChild(void)
{
	PLZWENCODEENTRY pFirstChild=m_EntryHead.pChild;// this child will be removed
	if(pFirstChild->pChild)
	{
		m_EntryHead.pChild=pFirstChild->pChild;
		if(m_EntryHead.pChild->pRightBrother)
		{
			PLZWENCODEENTRY pRightBrother=FindRightBrother(m_EntryHead.pChild);
			pRightBrother->pRightBrother=pFirstChild->pRightBrother;
		}
		else
			(m_EntryHead.pChild)->pRightBrother=pFirstChild->pRightBrother;
		//delete pFirstChild;
	}
	else
		m_EntryHead.pChild=pFirstChild->pRightBrother;
	delete pFirstChild;
}
PLZWENCODEENTRY CLZWEncodeTable::FindRightBrother(PLZWENCODEENTRY pCurrent)
{
	PLZWENCODEENTRY pFind;
	pFind=pCurrent;
	while(pFind->pRightBrother)
	{
		pFind=pFind->pRightBrother;
	}
	return pFind;
}
void CLZWEncodeTable::InitLZWTable(void)
{// init the table ,it has 256 items code from 0 to 255
	ClearLZWTable();
	PLZWENCODEENTRY pEntryFirst=new LZWENCODEENTRY;
	pEntryFirst->wCode=(WORD)0;
	pEntryFirst->bLast=(BYTE)0;
	pEntryFirst->pRightBrother=pEntryFirst->pChild=NULL;
	m_EntryHead.pChild=pEntryFirst;
	m_EntryHead.pRightBrother=NULL;
	PLZWENCODEENTRY pPrev=pEntryFirst;
	for(int i=1;i<=255;i++)
	{// set the brother nodes
		PLZWENCODEENTRY pEntry=new LZWENCODEENTRY;
		pEntry->wCode=(WORD)i;
		pEntry->bLast=(BYTE)i;
		pEntry->pChild=pEntry->pRightBrother=NULL;
		pPrev->pRightBrother=pEntry;
		pPrev=pEntry;
	}
	m_dwTableEntryNumber=258;
	m_uNextCodeForUse=LZW_BEGIN_ENTRY;
}
PLZWENCODEENTRY CLZWEncodeTable::FindMatchChild(BYTE bChildLast,PLZWENCODEENTRY pCurrent)
{// return the find child entry
	if(pCurrent->pChild==NULL)
		return NULL;
	PLZWENCODEENTRY pChild=pCurrent->pChild;
	// pChild is the current's child
	// and all pChild's brother is the current's child
	while(pChild!=NULL)
	{
		if(pChild->bLast==bChildLast)
			return pChild;
		pChild=pChild->pRightBrother;
	}
	return NULL;
}
PLZWENCODEENTRY CLZWEncodeTable::AddToChild(BYTE bLast,PLZWENCODEENTRY pCurrent)
{
	ASSERT(pCurrent);
	PLZWENCODEENTRY pChild=new LZWENCODEENTRY;
	if(pChild==NULL)
	{
		int _j=0;
	}
	pChild->pChild=pChild->pRightBrother=NULL;
	pChild->bLast=bLast;
	pChild->wCode=(WORD)m_uNextCodeForUse;
	if(pChild->wCode==LZW_CLEAR_CODE)
	{
		int _i=0;
	}
	m_uNextCodeForUse++;
	m_dwTableEntryNumber++;
	pChild->pRightBrother=pCurrent->pChild;
	pCurrent->pChild=pChild;
	return pChild;
}