Octane v1.01.20 - The Open Compression Toolkit for C++

http://octane.sourceforge.net/

coders/coder_huffman/huffmancoder.cpp

Go to the documentation of this file.

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// 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();
}
//---------------------------------------------------------------------------

 

Generated on 20 May 2004 by doxygen 1.3.3