huffmannodes.cpp

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

/// @file huffmannodes.cpp
/// Huffman node classes
///
/// @remarks
/// The HuffNode_Leaf is the base class for all symbols, and is (despite the
///  elaborate interface), a very lightweight data structure, containing
///  only a symbol id and a numeric weight.
///
/// @author mouser
/// @date   2003.07.29
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// application includes
#include "huffmannodes.hpp"
// system includes
using namespace std;
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// The traverse_buildbitcodes member function is recursively compute bitcodes for each leaf; it will code entire tree if called on the root.
void HuffNode::traverse_buildbitcodes(bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength)
{
	// only the derived versions of this virtual function should ever be called.
	cout << " error -> HuffNode::traverse_buildbitcodes should not be called." << endl;
}

void HuffNode_Middle::traverse_buildbitcodes(bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength)
{
	// traverse_buildbitcodes left tree
	if (bitsetlength>DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH)
		{
		// we allow for the possibility that some initially built symbols will have a bitdepth which is too long for the dictionary
		//  such symbols must be removed prior during pruning (note we record above the real bitdepth, but here only copy the limit)
		// we comment this out here (the warning will still be shown when listing symbolset)
		bitsetlength=DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH;
		}
	current_bitset[bitsetlength]=false;
	child0->traverse_buildbitcodes(current_bitset,bitsetlength+1);
	// traverse_buildbitcodes right tree
	current_bitset[bitsetlength]=true;
	child1->traverse_buildbitcodes(current_bitset,bitsetlength+1);
}

void HuffNode_Leaf::traverse_buildbitcodes(bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength)
{
	// set bits used to code this symbol (the DEF_HUFFMANPQ_MAXFUNCBITS is just an insanely large number of bits which doesn't affect memory usage)
	int count, length;
	// first store the bitset in the leaf
	code_bitsetlength=bitsetlength;
	length=bitsetlength;
	if (length>DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH)
		{
		// we allow for the possibility that some initially built symbols will have a bitdepth which is too long for the dictionary
		//  such symbols must be removed prior during pruning (note we record above the real bitdepth, but here only copy the limit)
		// we comment this out here (the warning will still be shown when listing symbolset)
		length=DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH;
		}
	// copy the bitset
	for (count=0;count<length;++count)
		code_bitset[count]=current_bitset[count];
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
string HuffNode_Leaf::get_bitcode_string()
{
	// return the bitcode in nice string, for debugging
	string bitset_string;
	int count;

	// don't try to read more than we actually stored
	int length=code_bitsetlength;
	if (length>DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH)
		length=DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH;

	for (count=0;count<length;++count)
		{
		if (code_bitset[count]==false)
			bitset_string+="0";
		else
			bitset_string+="1";
		}

	// add a note if its truncated (and thus unusable)
	if (code_bitsetlength>length)
		{
		char dummystr[80];
		sprintf(dummystr," (only %d of %d bits stored; symbol unuseable).",length,code_bitsetlength);
		bitset_string+=dummystr;
		}

	// return bits as string
	return bitset_string;
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
bool HuffNode_Leaf::AddBitsToBitWriter(bitwriter &bw)
{
	// push the bits from this code into the bitset
	// protect against too many bits
	int length=code_bitsetlength;
	if (length>DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH)
		{
		// this is an error - it means we get a symbol whose bitcode we didn't store fully
		return false;
		}

	// add bits
	for (int count=0;count<length;++count)
		bw.put_bit(code_bitset[count]);
		
	// return success
	return true;
}
//---------------------------------------------------------------------------