huffmancoder.cpp.bak

有关huffman的程序对大家学习数据结构有好处但不是所有人都用得上

// HuffmanCoder.cpp: implementation of the HuffmanCoder class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "HuffmanTest.h"
#include "HuffmanCoder.h"

#include <string>

#include <sys/types.h>
#include <sys/stat.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define BYTESWAP(In_Int) ( ((In_Int & 0xFF000000) >> 24) | ((In_Int & 0x00FF0000) >> 8) | ((In_Int & 0x0000FF00) << 8) | ((In_Int & 0x000000FF) << 24) )

#pragma warning (disable: 4786)

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

HuffmanCoder::HuffmanCoder()
{
	InFileName=OutFileName=NULL;

	MyListener=NULL;
	MyLog=NULL;
}

HuffmanCoder::~HuffmanCoder()
{

}

 //////////////////////////////////
// Interface helpers

void HuffmanCoder::SetUIHelpers(ProgressListener *NewListener, WinLog *NewLogTarget)
{
	MyListener=NewListener;
	MyLog=NewLogTarget;
}

void HuffmanCoder::SetInFile(const char *NewInFN)
{
	delete[] InFileName;

	InFileName=new char[strlen(NewInFN)+1];
	strcpy(InFileName,NewInFN);
}

void HuffmanCoder::SetOutFile(const char *NewOutFN)
{
	delete[] OutFileName;

	OutFileName=new char[strlen(NewOutFN)+1];
	strcpy(OutFileName,NewOutFN);
}

unsigned int HuffmanCoder::ThreadEncoder(void *CoderPtr)
{
	return ((HuffmanCoder *)CoderPtr)->Encode();
}

unsigned int HuffmanCoder::ThreadDecoder(void *CoderPtr)
{
	return ((HuffmanCoder *)CoderPtr)->Decode();
}

 //////////////////////////////////
// Main interface

unsigned int HuffmanCoder::Encode()
{
	MyLog->LogText("Encoding thread started.");

	FILE *InFile=Loggedfopen(InFileName,"rb");
	if (!InFile)
		return 1;

	MyLog->LogText("Building frequency table...");
	MyListener->SetProgressMsg("Counting: %d%%");

	unsigned int FileSize;
	//NOT PORTABLE IN ANY WAY!!!
	struct _stat TmpOut;
	_stat(InFileName,&TmpOut);
	FileSize=TmpOut.st_size;

	MyListener->SetMax(FileSize);

	unsigned int *FreqA=new unsigned int[256];
	FillFreqA(InFile,FreqA);
	fclose(InFile);

	MyLog->LogText("Building Huffman tree...");
	/*Note: this can be optimized to allocate just
	enough space for N symbols (that is, to create
	( N + (N-1) ) nodes).*/
	SLinkTree<HNode> *HuffTree=new SLinkTree<HNode>(256+255);
	SLinkTree<HNode>::iterator HRoot=BuildHuffTree(FreqA, &HuffTree);

	MyLog->LogText("Flattening the Huffman tree...");
	HTEntry LookupTable[256];
	BuildHuffTable(HRoot,LookupTable);
	delete[] HuffTree;

	PrintTableStats(LookupTable,FreqA,MyLog);

	//Delete the freq array & the tree.
	delete[] FreqA;
	MyLog->LogText("Initialization pass complete.");

	/*Now we have the lookup table, so we can start
	writing the output for real.*/

	InFile=Loggedfopen(InFileName,"rb");
	FILE *OutFile=Loggedfopen(OutFileName,"wb");
	if ((!InFile) || (!OutFile))
		return 1;

	//Write header.
	fwrite("Huffy1",6,1,OutFile);
	
	/*Now, write the table. Only existing entries will be
	written.*/
	MyLog->LogText("Writing lookup table...");
	WriteHTable(OutFile,LookupTable);

	MyListener->SetProgressMsg("Encoding: %d%%");
	MyLog->LogText("Writing encoded file...");
	WriteCodedFile(InFile,FileSize,OutFile,LookupTable);

	fclose(InFile);
	fclose(OutFile);
	MyLog->LogText("Encoding thread complete.");

	return 0;
}

unsigned int HuffmanCoder::Decode()
{
	MyLog->LogText("Decoding thread started.");
	
	FILE *InFile=Loggedfopen(InFileName,"rb");
	
	char HeaderBuff[6];
	fread(HeaderBuff,6,1,InFile);
	if (memcmp(HeaderBuff,"Huffy1",6))
	{
		fclose(InFile);
		MyLog->LogText("Header mismatch: input file is not Huffy-encoded!");
		return 2;
	}

	MyLog->LogText("Reading Huffman table...");
	HTEntry *LookupTable=new HTEntry[256];
	ReadHTable(InFile,LookupTable);

	MyLog->LogText("Re-creating Huffman tree...");
	HNode *HuffTree=new HNode;
	unsigned char LastName=BuildHuffTree(LookupTable,HuffTree);

	delete[] LookupTable;

	MyLog->LogText("Compiling node transition table...");
	MyListener->SetProgressMsg("Building: %d%%");

	//Create NameCount*256 entries.
	TTEntry *TransitionA=new TTEntry[((LastName+1) << 8)];
	BuildTTable(HuffTree,LastName+1,TransitionA);
	
	delete HuffTree;

	MyListener->SetProgressMsg("Decoding: %d%%");

	FILE *OutFile=Loggedfopen(OutFileName,"wb");
	MyLog->LogText("Writing decoded file...");
	WriteDecodedFile(InFile,OutFile,TransitionA);

	fclose(InFile);
	fclose(OutFile);

	MyLog->LogText("Decoding thread complete.");

	return 0;	
}

 //////////////////////////////////
// Decoder helpers

void HuffmanCoder::ReadHTable(FILE *SourceFile, HTEntry *OutTable)
{
	unsigned int x;
	//Init the table, as if a complete table was present.
	for (x=0; x<256; x++)
		OutTable[x].CodeLen=0;

	unsigned char CodeCount;
	fread(&CodeCount,1,1,SourceFile);

	unsigned char CurrSymbol;
	for (x=0; x<CodeCount; x++)
	{
		fread(&CurrSymbol,1,1,SourceFile);
		fread(&(OutTable[CurrSymbol].CodeLen),1,1,SourceFile);
		//Debug: reads 4-byte codes only.
		fread(&(OutTable[CurrSymbol].Code),4,1,SourceFile);
	}
}

void HuffmanCoder::WriteDecodedFile(FILE *InFile, FILE *OutFile, TTEntry *TransTable)
{
	unsigned int OutSize;
	fread(&OutSize,4,1,InFile);

	MyListener->SetMax(OutSize);

	unsigned int x=0;
	TTEntry *CurrEntry;
	unsigned char CurrByte,CurrName=0;
	while (x<OutSize)
	{
		fread(&CurrByte,1,1,InFile);
		/*Look up the current transition table entry,
		based on the current state & the bytes in the stream.*/
		CurrEntry=&(TransTable[(CurrName << 8) + CurrByte]);

		if (x+CurrEntry->OutSymbolCount>OutSize)
			fwrite(CurrEntry->OutSymbolA,OutSize-x,1,OutFile);
		else
			fwrite(CurrEntry->OutSymbolA,CurrEntry->OutSymbolCount,1,OutFile);
		x+=CurrEntry->OutSymbolCount;

		//Go to the next state.
		CurrName=CurrEntry->NextNodeName;

		MyListener->Update(x);
	}
}

unsigned char HuffmanCoder::BuildHuffTree(HTEntry *SourceTable, HNode *TargetRoot)
{
	//Needed to name every node.
	TargetRoot->Symbol=0;

	unsigned char CurrName=0;
	unsigned int x;
	for (x=0; x<256; x++)
	{
		if (SourceTable[x].CodeLen)
			CurrName=BuildHuffTreeInternal(CurrName,x,&(SourceTable[x]),TargetRoot);
	}

	return CurrName;
}

unsigned char HuffmanCoder::BuildHuffTreeInternal(unsigned char CurrName, unsigned char CurrSymbol, HTEntry *SourceEntry, HNode *TargetNode)
{
	if (SourceEntry->CodeLen==1)
	{
		//Create a leaf node.
		if (SourceEntry->Code >> 31)
		{
			TargetNode->Right=new HNode;
			TargetNode->Right->Symbol=CurrSymbol;
		}
		else
		{
			TargetNode->Left=new HNode;
			TargetNode->Left->Symbol=CurrSymbol;
		}

		return CurrName;
	}
	else
	{
		//Create an internal node.
		HNode *NewNode;
		if (SourceEntry->Code >> 31)
		{
			if (TargetNode->Right)
			{
				SourceEntry->Code<<=1;
				SourceEntry->CodeLen--;
				return BuildHuffTreeInternal(CurrName,CurrSymbol,SourceEntry,TargetNode->Right);
			}
			else
			{
				NewNode=new HNode;
				TargetNode->Right=NewNode;
			}
		}
		else
		{
			if (TargetNode->Left)
			{
				SourceEntry->Code<<=1;
				SourceEntry->CodeLen--;
				return BuildHuffTreeInternal(CurrName,CurrSymbol,SourceEntry,TargetNode->Left);
			}
			else
			{
				NewNode=new HNode;
				TargetNode->Left=NewNode;
			}
		}
		
		CurrName++;
		NewNode->Parent=TargetNode;
		NewNode->Symbol=CurrName;

		SourceEntry->Code<<=1;
		SourceEntry->CodeLen--;
		return BuildHuffTreeInternal(CurrName,CurrSymbol,SourceEntry,NewNode);
	}
}

/*To access a table entry, address the table as follows:
OutTable[(CurrState << 8) + CodedByte].*/
void HuffmanCoder::BuildTTable(HNode *SourceNode, unsigned char NameCount, TTEntry *OutTable)
{
	unsigned int x,y;

	/*HNode **NodeLookupA=new HNode *[NameCount];
	for (x=0; x<NameCount; x++)
		NodeLookupA[x]=LookupInternalNode(SourceNode,x);

	for (y=0; y<NameCount; y++)
	{
		for (x=0; x<256; x++)
			FillTTEntry(SourceNode, NodeLookupA[y],x, &(OutTable[(y << 8)+x]) );
	}*/

	MyListener->SetMax(NameCount);

	HNode *CurrStartNode;
	for (y=0; y<NameCount; y++)
	{
		CurrStartNode=LookupInternalNode(SourceNode,y);
		for (x=0; x<256; x++)
			FillTTEntry(SourceNode, CurrStartNode, x, &(OutTable[(y << 8)+x]) );

		MyListener->Update(y);
	}
}

void HuffmanCoder::FillTTEntry(HNode *RootNode, HNode *StartNode, unsigned char EncodedByte, TTEntry *OutEntry)
{
	for (char x=7; x>=0; x--)
	{
		//Traverse the tree further.