huffmancoder.cpp

Octane v1.01.20 The Open Compression Toolkit for C++ . The Open Compression Toolkit is a set of mo

/// @file huffmancoder.cpp
/// Simple Huffman Coder class
///
/// @remarks
/// This Coder performs standard, simple huffman coding.
///
/// @author mouser
/// @date   2003.07.29
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// application includes
#include "huffmancoder.hpp"
// system includes
#include <assert.h>
//---------------------------------------------------------------------------






//---------------------------------------------------------------------------
// Functions from OCTANE PUBLIC API
void HuffmanCoder::ShowDebuggingInfo()
{
	// show bit strings
	ShowBitStrings();
	// show memory used by priority queue
	std::cout << " Memory used by Huffman Coder:         " << GetMemoryUsed() << " bytes.\n";
}

unsigned int HuffmanCoder::GetMemoryUsed()
{
	// approximate memory usage of the priority queue
	unsigned int memoryused=0;
	memoryused+=sizeof(symbolsetpq);
	if (symbolsetpq.size()!=0)
		memoryused+=(symbolsetpq.top())->get_memoryused();
	memoryused+=sizeof(symbolvector);
	if (symbolvector.size()!=0)
		memoryused+=(unsigned int)(symbolvector.capacity()*sizeof(HuffNode_Leaf*));

	return memoryused;
}
//---------------------------------------------------------------------------





//---------------------------------------------------------------------------
// Functions from CODER PUBLIC API
bool HuffmanCoder::WriteSymbolBits(int symbolnum,bitwriter &bw)
{
	// write bits for symbol number - this is easy because we've precomputed the bitvectors for every symbol
	assert(symbolnum<(int)(symbolvector.size()));
	return symbolvector[symbolnum]->AddBitsToBitWriter(bw);
}

bool HuffmanCoder::DecodeSymbolFromInput(int &symbolnum, bitreader &br)
{
	// decode a symbol from the input, and set symbolnum to symbol number
	// return false on no symbols left in stream
	HuffNode* nodep;
	bool bitvalue;
	
	// now walk through the input bits	
	nodep = symbolsetpq.top();
	while (!br.empty())
		{
		// grab a bit
		bitvalue = br.get_bit();

		// traverse down tree
		if (bitvalue==false)
			nodep=nodep->get_child0();
		else
			nodep=nodep->get_child1();
		if (nodep==NULL)
			{
			cerr << "ERROR: Internal error traversing huffman tree in huffmancoder.cpp, in HuffmanCoder::DecodeSymbolFromInput()." << endl;
			break;
			}

		// if its leaf we got our symbol
		if (nodep->isleaf())
			{
			// we hit a leaf, so this is our decoded symbol - return its number
			symbolnum=((HuffNode_Leaf*)nodep)->get_symbolid();
			return true;
			}
		else
			{
			// just a middle node, so keep traversing
			}
		}
	
	// no symbols to read
	return false;
}
//---------------------------------------------------------------------------




	
//---------------------------------------------------------------------------
// Helpers
void  HuffmanCoder::ShowBitStrings()
{
	// show bitstrings for debugging
	string bitset_string;
	THuffmanNodeWeight symbolweight;
	int symbolid;

	// show the dictionary sorted alphabetically
	if (symbolsetpq.size()>0)
		{
		cout << "SymbolSet Huffman Codes ("<<(unsigned int)(symbolvector.size())<<" entries)\n";
		cout << " " << setiosflags(ios::left) << setw(10) << "symbolid" << " " << setw(16) << "weight" << " " << "bitstring\n";
		cout << " " << setiosflags(ios::left) << setw(10) << "--------" << " " << setw(16) << "------" << " " << "----------\n";
		for (symbolvector_pos=symbolvector.begin();symbolvector_pos!=symbolvector.end();++symbolvector_pos)
			{
			symbolid=(*symbolvector_pos)->get_symbolid();
			symbolweight = (*symbolvector_pos)->get_weight();
			bitset_string=(*symbolvector_pos)->get_bitcode_string();
			cout << " " << setiosflags(ios::left) << setw(10) << symbolid << " " << setw(16) << symbolweight << " " << bitset_string <<"\n";
			}
		cout << "\n";
		}
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Building and managing the priority queue (huffman tree)

bool HuffmanCoder::BuildUpdateHuffmanTreeAndBitcodes(OctaneModeler *modelerp)
{
	// the SymbolSet is ready to be processed into a priority queue and for us to generate bitcodes
	// this can safely be called multiple times, so you can engage in a series
	// of pruning symbol set, generating bitcodes, and repeating the process to reduce bitcode lengths
	HuffNode *topmostp;
	HuffNode_Leaf *symbolleafp;

	// Free any priority queue
	FreeSymbols();

	// Loop through all symbols in modeler and add them as new leaf symbols in a priority queue and fast lookup vector
	int symbolcount=modelerp->GetSymbolCount();
	for (int index=0;index<symbolcount;++index)
		{
		// create symbol as new leaf to priority queue, recording its index in vector with a two-way link
		symbolleafp = new HuffNode_Leaf(index,modelerp->GetWeightVectorItem(index));
		// add symbol as leaf in priority queue
		symbolsetpq.push(symbolleafp);
		// add symbol leaf to vector (note this will never change, its for fast indexed lookup since pq nodes move around)
		symbolvector.push_back(symbolleafp);
		}

	// Build Priority Queue.  This loop removes the two smallest HuffNodes from the queue.
	//  It creates a new internal HuffNode that has those two HuffNodes as children. The new internal HuffNode is then inserted into the priority queue.
	//  When there is only one HuffNode in the priority queue, the tree is complete.
	while ( symbolsetpq.size() > 1 )
		{
		// pop topmost but save it so we can add it as left child
		topmostp=symbolsetpq.top();
		HuffNode *child0 = topmostp;
		symbolsetpq.pop();
		// pop next topmost but save it so we can add it as left child
		topmostp=symbolsetpq.top();
		HuffNode *child1 = topmostp;
		symbolsetpq.pop();
		// now make a new parent node with these two children
		symbolsetpq.push(new HuffNode_Middle(child0,child1));
		}

	// Traverse_buildbitcodes tree and build bit codes (create a bitset big enough to hold largest code length)
	TraverseHuffmanTreeBuildBitcodes();

	// now a test, show debugging info
	// ShowDebuggingInfo();

	// return success
	return true;
}


void HuffmanCoder::TraverseHuffmanTreeBuildBitcodes()
	{
	// begin recursive traverse of the huffman tree, used for building bitcodes
	bitset<DEF_HUFFMANPQ_MAXFUNCBITS> current_bitset;
	(symbolsetpq.top())->traverse_buildbitcodes(current_bitset,0);
	}


void HuffmanCoder::FreeSymbols()
{
	// free the priority queue
	HuffNode* topmostp;
	while ( symbolsetpq.size() >= 1 )
		{
		// grab topmost and delete all of its children, then it (there really should be only 1 at top after building huffman tree)
		topmostp=symbolsetpq.top();
		// note we tell the node to delete itself and all its children
		topmostp->recursive_freechildren();
		delete topmostp;
		// now pop it off
		symbolsetpq.pop();
		}
	// now free the symbol vector
	symbolvector.clear();
}
//---------------------------------------------------------------------------