huffmancoder.hpp

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

/// @file huffmancoder.hpp
/// Simple Huffman Coder class
///
/// @remarks
/// This Coder performs standard, simple Huffman coding.
///
/// @todo There seems to be a bug in this code which is causing very large
///  bitcodes for rare symbols - they should not get this large afaik.
///  it may have to do with a flaw in the implementation, or be due to the
///  fact that we are artifically forcing the tree to keep some primitive
///  ascii characters which actually get frequency counts of 0.
///
/// @author mouser
/// @date   2003.07.29
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// recursive header protection
#ifndef HuffmanCoderH
#define HuffmanCoderH
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// application includes
#include "huffmannodes.hpp"
#include "../coder.hpp"
#include "../../modelers/modeler.hpp"
// system includes
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
/// During compression, the job of the Coder class is use probability information
///  from the modeler to figure out the optimal bitcodes to use when writing
///  symbols into the output stream.  During decompression, the coder is
///  responsible for reading bitcodes from the input and providing a stream of
///  symbol numbers to the compressor.
///
/// The Huffman Coding algorithm was invented by David A. Huffman,
///  http://www.wikipedia.org/wiki/Huffman_coding
///
/// The idea of using an STL priority queue to build the Huffman tree is from
///  Mark Nelson, http://dogma.net/markn/articles/pq_stl/priority.htm.
///
/// @ingroup Coders
///
class HuffmanCoder : public OctaneCoder
{
protected:
	/// Stl priority queue for Huffman tree, built from "huffman nodes"
	/// @see huffmannodes.hpp
	THuffmanNodePriorityQueue symbolsetpq;
	/// vector of pointers to symbols, for fast lookup when it comes time to writing symbols by symbol#
	vector<HuffNode_Leaf*> symbolvector;
	/// vector iterator
	vector<HuffNode_Leaf*>::iterator symbolvector_pos;
public:
	//---------------------------------------------------------------------------
	/// constructor
	HuffmanCoder() { ; }
	/// destructor
	virtual ~HuffmanCoder() { ; }
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// OCTANE PUBLIC API - RTTI FUNCTIONS - these are supported by all derived classes
	virtual std::string GetName() {return "HuffmanCoder";}
	virtual std::string GetDescription() {return "Huffman Coder";}
	virtual std::string GetHelpInformation() { return ""; }
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// OCTANE PUBLIC API - AUXILIARY FUNCTIONS - these are supported by all derived classes
	virtual void ShowDebuggingInfo();
	virtual unsigned int GetMemoryUsed();
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// CODER PUBLIC API - PARSING FUNCTIONS
	virtual bool WriteSymbolBits(int symbolnum,bitwriter &bw);
	virtual bool DecodeSymbolFromInput(int &symbolnum, bitreader &br);
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// CODER PUBLIC API - STATE PREPARATION
	virtual void ResetState() {;};
	virtual void SynchronizeStateForNewStream() {;};
	virtual bool IsReadyToCode() {if (symbolvector.size()>0) return true; else return false;};
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// CODER PUBLIC API - MODEL CHANGE NOTIFICATION
	virtual void ReceiveNotification_ModelChange_AllSymbolWeights(OctaneModeler *modelerp) {BuildUpdateHuffmanTreeAndBitcodes(modelerp);};
	virtual void ReceiveNotification_ModelChange_SingleSymbolWeight(OctaneModeler *modelerp,int symbolnum) {BuildUpdateHuffmanTreeAndBitcodes(modelerp);};
	//---------------------------------------------------------------------------
protected:
	// priority queue huffman-tree stuff
	/// Using the current probability vector from the modeler, build a huffman tree and compute bitcodes for each symbol.
	bool BuildUpdateHuffmanTreeAndBitcodes(OctaneModeler *modelerp);
	/// Traverse built tree and assign bitcodes.
	void TraverseHuffmanTreeBuildBitcodes();
	/// Free any current tree and symbols in preparation for rebuilding.
	void FreeSymbols();
	/// Show bitcodes for each symbol - useful for debugging.
	void ShowBitStrings();
};
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------