huffmancoder.cpp.bak

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

		if ( (EncodedByte >> x) & 1 )
			StartNode=StartNode->Right;
		else
			StartNode=StartNode->Left;

		if (!(StartNode->Left))		
		{
			//Output a symbol, then jump to the root.
			if (OutEntry->OutSymbolA)
			{
				unsigned char *TmpBuff=new unsigned char[OutEntry->OutSymbolCount+1];
				memcpy(TmpBuff,OutEntry->OutSymbolA,OutEntry->OutSymbolCount);

				TmpBuff[OutEntry->OutSymbolCount]=StartNode->Symbol;
				
				delete[] OutEntry->OutSymbolA;
				OutEntry->OutSymbolA=TmpBuff;
				OutEntry->OutSymbolCount++;
			}
			else
			{
				OutEntry->OutSymbolA=new unsigned char;			
				*(OutEntry->OutSymbolA)=StartNode->Symbol;
				OutEntry->OutSymbolCount=1;
			}

			StartNode=RootNode;
		}
		/*
		if (StartNode->Left)
		{
			//Traverse the tree further.
			if ( (EncodedByte >> x) & 1 )
				StartNode=StartNode->Right;
			else
				StartNode=StartNode->Left;
		}
		else
		{
			//Output a symbol, then jump to the root.
			if (OutEntry->OutSymbolA)
			{
				unsigned char *TmpBuff=new unsigned char[OutEntry->OutSymbolCount+1];
				memcpy(TmpBuff,OutEntry->OutSymbolA,OutEntry->OutSymbolCount);

				TmpBuff[OutEntry->OutSymbolCount]=StartNode->Symbol;
				
				delete[] OutEntry->OutSymbolA;
				OutEntry->OutSymbolA=TmpBuff;
				OutEntry->OutSymbolCount++;
			}
			else
			{
				OutEntry->OutSymbolA=new unsigned char;			
				*(OutEntry->OutSymbolA)=StartNode->Symbol;
				OutEntry->OutSymbolCount=1;
			}

			StartNode=RootNode;
		}
		*/
	}
	OutEntry->NextNodeName=StartNode->Symbol;
}

HuffmanCoder::HNode * HuffmanCoder::LookupInternalNode(HNode *RootNode, unsigned char NodeName)
{
	if (RootNode->Symbol==NodeName)
		return RootNode;
	else
	{
		HNode *RetNode;
		//Call only if the child is an internal node
		if (RootNode->Left->Left)
		{
			RetNode=LookupInternalNode(RootNode->Left,NodeName);
			if (RetNode)
				return RetNode;
		}
		if (RootNode->Right->Left)
		{
			RetNode=LookupInternalNode(RootNode->Right,NodeName);
			if (RetNode)
				return RetNode;
		}

		return NULL;
	}
}

 //////////////////////////////////
// Encoder helpers

//WARNING: This needs the original freq array!
void HuffmanCoder::PrintTableStats(HTEntry *SourceTable, HNode *FreqA, WinLog *OutLog)
{
	unsigned char MaxCodeLen=0,MinCodeLen=255;

	unsigned int InputLength=0,CodeCount=0,CodeLenSum=0;

	unsigned int x;
	for (x=0; x<256; x++)
	{
		if (SourceTable[x].CodeLen)
		{
			if (SourceTable[x].CodeLen>MaxCodeLen)
				MaxCodeLen=SourceTable[x].CodeLen;
			if (SourceTable[x].CodeLen<MinCodeLen)
				MinCodeLen=SourceTable[x].CodeLen;

			InputLength+=FreqA[x].Weight;
			CodeLenSum+=SourceTable[x].CodeLen;

			CodeCount++;
		}
	}

	OutLog->LogText("Encoder stats:");
	
	char PrintTmp[128];
	sprintf(PrintTmp,"  Input stream length: %d",InputLength);
	OutLog->LogText(PrintTmp);

	sprintf(PrintTmp,"  Max / Min codelength: %d / %d",MaxCodeLen,MinCodeLen);
	OutLog->LogText(PrintTmp);

	sprintf(PrintTmp,"  Number of individual codes: %d",CodeCount);
	OutLog->LogText(PrintTmp);

	sprintf(PrintTmp,"  Average codelength(not weighted): %f",(float)CodeLenSum/CodeCount);
	OutLog->LogText(PrintTmp);

}

void HuffmanCoder::WriteHTable(FILE *OutFile, HTEntry *CodeTable)
{
	unsigned int x;
	unsigned char CodeCount=0;
	for (x=0; x<256; x++)
	{
		if (CodeTable[x].CodeLen)
			CodeCount++;
	}

	fwrite(&CodeCount,1,1,OutFile);

	//unsigned int CurrCode;
	for (x=0; x<256; x++)
	{
		if (CodeTable[x].CodeLen)
		{
			fwrite(&x,1,1,OutFile);
			fwrite(&(CodeTable[x].CodeLen),1,1,OutFile);
			//Debug: outputs 4-byte codes only.
			fwrite(&(CodeTable[x].Code),4,1,OutFile);
			/*if (CodeTable[x].CodeLen>24)
				fwrite(&(CodeTable[x].Code),4,1,OutFile);
			else if ((CodeTable[x].CodeLen<25) && (CodeTable[x].CodeLen>16))
			{
				CurrCode=CodeTable[x].Code >> 8;
				fwrite(&CurrCode,3,1,OutFile);
			}
			else if ((CodeTable[x].CodeLen<17) && (CodeTable[x].CodeLen>8))
			{
				CurrCode=CodeTable[x].Code >> 16;
				fwrite(&CurrCode,2,1,OutFile);
			}
			else //if (CodeTable[x].CodeLen<9)
			{
				CurrCode=CodeTable[x].Code >> 24;
				fwrite(&CurrCode,1,1,OutFile);
			}*/
		}
	}
}

void HuffmanCoder::WriteCodedFile(FILE *InFile, unsigned int StreamLen, FILE *OutFile, HTEntry *CodeTable)
{
	MyListener->SetMax(StreamLen);
	fwrite(&StreamLen,4,1,OutFile);

	unsigned int CurrProg=0;

	unsigned int OutBuff=0;
	unsigned char CurrSymbol,OutBuffLen=0;
	HTEntry *CurrCode;
	while (!feof(InFile))
	{
		fread(&CurrSymbol,1,1,InFile);
		CurrCode=&(CodeTable[CurrSymbol]);

		if ((CurrCode->CodeLen+OutBuffLen)<33)
		{
			OutBuff|=(CurrCode->Code) >> OutBuffLen;
			OutBuffLen+=CurrCode->CodeLen;

			//A special case to speed up writing.
			if (OutBuffLen==32)
			{
#if HUFFY_LITTLEENDIAN
				OutBuff=BYTESWAP(OutBuff);
#endif
				fwrite(&OutBuff,4,1,OutFile);
				OutBuff=0;
				OutBuffLen=0;
			}
		}
		else
		{
			OutBuff|=(CurrCode->Code) >> (OutBuffLen);
#if HUFFY_LITTLEENDIAN
			OutBuff=BYTESWAP(OutBuff);
#endif
			fwrite(&OutBuff,4,1,OutFile);

			OutBuff=(CurrCode->Code) << (32-OutBuffLen);
			OutBuffLen=CurrCode->CodeLen-(32-OutBuffLen);
		}

		MyListener->Update(++CurrProg);
	}

	//Write the final 4 bytes.
	if (OutBuffLen)
	{
#if HUFFY_LITTLEENDIAN
		OutBuff=BYTESWAP(OutBuff);
#endif
		fwrite(&OutBuff,4,1,OutFile);
	}
}

/*As we know the maximum number of symbols, this
dinamic tree method can be optimized to a statically
linked list-like one.
One just needs to calculate the maximum number of nodes
needed to create a huffman tree for N symbols.*/
SLinkTree<HNode>::iterator HuffmanCoder::BuildHuffTree(unsigned int *FreqA, SLinkTree<HNode> **OutTree)
{
	std::list<HNode *> BaseList;
	
	unsigned int x;
	for (x=0; x<256; x++)
	{
		if (FreqA[x].Weight)
			OrderedInsert(BaseList,new HNode(FreqA[x]));
	}

	HNode *CurrNode;
	std::list<HNode *>::iterator CurrLeft,CurrRight;
	while (BaseList.size()>1)
	{
		CurrLeft=CurrRight=BaseList.begin();
		++CurrRight;

		CurrNode=new HNode;
		CurrNode->Left=*(CurrLeft.operator->());
		CurrNode->Right=*(CurrRight.operator->());

		CurrNode->Left->Parent=CurrNode->Right->Parent=CurrNode;
		CurrNode->Weight=CurrNode->Left->Weight + CurrNode->Right->Weight;

		BaseList.erase(CurrLeft);
		BaseList.erase(CurrRight);

		OrderedInsert(BaseList,CurrNode);
	}

	//The only one remaining node must be the root.
	return *(BaseList.begin().operator->());
}

void HuffmanCoder::BuildHuffTable(HNode *HTreeRoot, HTEntry *OutTable)
{
	if (HTreeRoot->Left)
	{
		BuildTableInternal(HTreeRoot->Left,0,1,OutTable);
		BuildTableInternal(HTreeRoot->Right,(unsigned int)1 << 31,1,OutTable);
	}
	else
	{
		OutTable[HTreeRoot->Symbol].Code=0;
		OutTable[HTreeRoot->Symbol].CodeLen=1;
	}
}

/*The codes are built to be aligned with the  _left_
side of the integer. For example, a huffman code 'b1'
is represented by "b1000...00".*/
void HuffmanCoder::BuildTableInternal(HNode *HTreeRoot, unsigned int CurrCode, unsigned char CurrCodeLen, HTEntry *OutTable)
{
	if (HTreeRoot->Left)
	{
		CurrCodeLen++;
		BuildTableInternal(HTreeRoot->Left,CurrCode,CurrCodeLen,OutTable);
		//Append bit "1" after the current code
		BuildTableInternal(HTreeRoot->Right,CurrCode | (1 << (32-CurrCodeLen)),CurrCodeLen,OutTable);
	}
	else
	{
		OutTable[HTreeRoot->Symbol].Code=CurrCode;
		OutTable[HTreeRoot->Symbol].CodeLen=CurrCodeLen;
	}
}

//Assumes a buffered file!! (Means it's slow as hell.)
void HuffmanCoder::FillFreqA(FILE *InFile, unsigned int *OutA)
{
	MyListener->Reset();
	for (int x=0; x<256; x++)
		OutA[x]=0;

	unsigned int CurrProg=0;
	unsigned char InChar;
	while (!feof(InFile))
	{
		fread(&InChar,1,1,InFile);
		OutA[InChar]++;

		//== !(CurrProg % 0xFFF)
		if ((CurrProg & 0xFFF)==0x800)
			MyListener->Update(++CurrProg);
	}
}

/*This should be fast enough for building
the huffman tree for now. However, it
definitely needs improvement.*/
void HuffmanCoder::OrderedInsert(std::list<HNode *> &TargetList, HNode *NewNode)
{
	std::list<HNode *>::iterator NowI=TargetList.begin(),EndI=TargetList.end();
	unsigned int NewNodeWeight=NewNode->Weight;
	while ((NowI!=EndI) && ( (*( NowI.operator->()) )->Weight<=NewNodeWeight))
		++NowI;

	TargetList.insert(NowI,NewNode);
}

FILE *HuffmanCoder::Loggedfopen(const char *FName, const char *Mode)
{
	FILE *RetFile=fopen(FName,Mode);
	if (!RetFile)
	{
		std::string TmpMsg="ERR: Failed to open file \"";
		TmpMsg+=FName;
		TmpMsg+="\".";
		MyLog->LogText(TmpMsg.data());
	}
	else
	{
		std::string TmpMsg="Opened file \"";
		TmpMsg+=FName;
		TmpMsg+="\".";
		MyLog->LogText(TmpMsg.data());
	}

	return RetFile;
}