huffman.cpp

网络MPEG4IP流媒体开发源代码

/*************************************************************************

This software module was originally developed by 

	Ming-Chieh Lee ([e-mail]), Microsoft Corporation
	Wei-ge Chen ([e-mail]), Microsoft Corporation
	Bruce Lin ([e-mail]), Microsoft Corporation
	Chuang Gu ([e-mail]), Microsoft Corporation
	(date: March, 1996)

and edited by
	Yoshihiro Kikuchi (TOSHIBA CORPORATION)
	Takeshi Nagai (TOSHIBA CORPORATION)
	Toshiaki Watanabe (TOSHIBA CORPORATION)
	Noboru Yamaguchi (TOSHIBA CORPORATION)

in the course of development of the MPEG-4 Video (ISO/IEC 14496-2). 
This software module is an implementation of a part of one or more MPEG-4 Video tools 
as specified by the MPEG-4 Video. 
ISO/IEC gives users of the MPEG-4 Video free license to this software module or modifications 
thereof for use in hardware or software products claiming conformance to the MPEG-4 Video. 
Those intending to use this software module in hardware or software products are advised that its use may infringe existing patents. 
The original developer of this software module and his/her company, 
the subsequent editors and their companies, 
and ISO/IEC have no liability for use of this software module or modifications thereof in an implementation. 
Copyright is not released for non MPEG-4 Video conforming products. 
Microsoft retains full right to use the code for his/her own purpose, 
assign or donate the code to a third party and to inhibit third parties from using the code for non <MPEG standard> conforming products. 
This copyright notice must be included in all copies or derivative works. 

Copyright (c) 1996, 1997.

Module Name:
	
	huffman.cpp

Abstract:

	Classes for Huffman encode/decode.

Revision History:

*************************************************************************/

#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include "typeapi.h"
#include "entropy.hpp"
#include "huffman.hpp"
#include "iostream.h"
#include "fstream.h"
#include "math.h"
#include "bitstrm.hpp"

#include "vlc.hpp"

#ifdef __MFC_
#ifdef _DEBUG
#undef THIS_FILE
static char BASED_CODE THIS_FILE[] = __FILE__;
#endif

#define new DEBUG_NEW				   
#endif // __MFC_

#ifdef __PC_COMPILER_
#define FULLNAME(dir, filename) strcpy (pch, "\\"#dir"\\"#filename);
#else 
#define FULLNAME(dir, filename) strcpy (pch, "/"#dir"/"#filename);
#endif

class CNode
{
friend class CHuffmanTree;
friend Int huffmanNodeCompare (const Void* Element1,const Void* Element2);
private:
    Char m_cCode;
    Int m_lNodeIndex;
    Int m_lFrequency;
    Int m_lBalancer;
    CNode () {m_cCode = 0; m_lNodeIndex = -1; m_lFrequency = 0; m_lBalancer = 1;};
};

Class CHuffmanDecoderNode
{
friend class CHuffmanDecoder;
    Char m_c0End;
    Char m_c1End;
    Int m_l0NextNodeOrSymbol;
    Int m_l1NextNodeOrSymbol;
    CHuffmanDecoderNode () {m_c0End=0;m_c1End=0;
            m_l0NextNodeOrSymbol=-1;m_l1NextNodeOrSymbol=-1;};
    Bool is0Valid() {if ((m_c0End==0)&&(m_l0NextNodeOrSymbol==-1))
            return FALSE;return TRUE;};
    Bool is1Valid() {if ((m_c1End==0)&&(m_l1NextNodeOrSymbol==-1))
            return FALSE;return TRUE;};
};

CHuffmanTree::CHuffmanTree (Int lNOfSymbols, Int *lpFrequencies)
{
    assert(lNOfSymbols>1);
    m_lNOfSymbols=lNOfSymbols;
    m_pNodes = new CNode[2*m_lNOfSymbols-1];
    if(lpFrequencies)
        setFrequencies (lpFrequencies);
}

CHuffmanTree::~CHuffmanTree()
{
    delete[]m_pNodes;
}

Void CHuffmanTree::writeSymbol (Int symbolNo,ostream &stream)
{
    stream<<symbolNo<<" ";
}

Void CHuffmanTree::setFrequencies (Int* lpFrequencies)
{
    for (Int lIndex=0;lIndex<m_lNOfSymbols;lIndex++)
        setFrequency(lpFrequencies[lIndex],lIndex);
}

Void CHuffmanTree::setFrequency (Int lFrequency, Int lIndex)
{
    m_pNodes[lIndex].m_lFrequency=lFrequency;
}

Int huffmanNodeCompare (const Void* Element1, const Void* Element2)
{
    if((*((CNode**)Element1))->m_lFrequency<
            (*((CNode**)Element2))->m_lFrequency)return  1;   
    if((*((CNode**)Element1))->m_lFrequency>
            (*((CNode**)Element2))->m_lFrequency)return -1;
    if((*((CNode**)Element1))->m_lBalancer<
            (*((CNode**)Element2))->m_lBalancer)return  1;   
    if((*((CNode**)Element1))->m_lBalancer>
            (*((CNode**)Element2))->m_lBalancer)return -1;
    return 0;
}

Void CHuffmanTree::buildTree ()
{
    assert(m_lNOfSymbols>1);
    Int NOfNodesForSorting=m_lNOfSymbols;
    Int NextFreeNode=m_lNOfSymbols;
    CNode **pSortingArray;
    pSortingArray=new CNode*[m_lNOfSymbols];
    for (Int i=0;i<m_lNOfSymbols;i++)
        pSortingArray [i] = &m_pNodes[i];
    
    while (NOfNodesForSorting>1)
    {
        qsort(&pSortingArray[0],NOfNodesForSorting,
                sizeof(pSortingArray[0]),huffmanNodeCompare);
        pSortingArray[NOfNodesForSorting-2]->m_lNodeIndex=NextFreeNode;
        pSortingArray[NOfNodesForSorting-1]->m_lNodeIndex=NextFreeNode;
        pSortingArray[NOfNodesForSorting-2]->m_cCode=0;
        pSortingArray[NOfNodesForSorting-1]->m_cCode=1;
        m_pNodes[NextFreeNode].m_lFrequency=
                pSortingArray[NOfNodesForSorting-2]->m_lFrequency+
                pSortingArray[NOfNodesForSorting-1]->m_lFrequency;
        m_pNodes[NextFreeNode].m_lBalancer=
                pSortingArray[NOfNodesForSorting-2]->m_lBalancer+
                pSortingArray[NOfNodesForSorting-1]->m_lBalancer;
        pSortingArray[NOfNodesForSorting-2]=&m_pNodes[NextFreeNode];
        NOfNodesForSorting--;
        NextFreeNode++;
    };
    delete pSortingArray;
}

void CHuffmanTree::writeOneTableEntry(ostream &stream, Int entryNo,
                                    Double lTotalFrequency, Double &dNOfBits)
{
    Double dP=m_pNodes[entryNo].m_lFrequency/(Double)lTotalFrequency;
    Char *pCodeArray=new Char[m_lNOfSymbols-1];
    Int lNode=entryNo;
    Int lCodeNo=0;
    while(lNode!=2*m_lNOfSymbols-2)
    {
        pCodeArray[lCodeNo++]=m_pNodes[lNode].m_cCode;
        lNode=m_pNodes[lNode].m_lNodeIndex;
    };
    writeSymbol(entryNo,stream);
    dNOfBits+=dP*lCodeNo;
    while(lCodeNo>0)
    {
        lCodeNo--;
        stream<<(Int)pCodeArray[lCodeNo];
    };
    stream<<endl;
    delete pCodeArray;
}

Void CHuffmanTree::writeTable (ostream &stream)
{
    Int lTotalFrequency=0;
    Double dEntropy=0;
    Double dNOfBits=0;
    statistics (lTotalFrequency, dEntropy);
    for (Int i = 0; i < m_lNOfSymbols; i++)
        writeOneTableEntry (stream, i, lTotalFrequency, dNOfBits);
    printStatistics (dEntropy, dNOfBits, stream);
}

Void CHuffmanTree::writeTableSorted(ostream &stream)
{
    Int lTotalFrequency=0;
    Double dEntropy=0;
    Double dNOfBits=0;
    statistics(lTotalFrequency,dEntropy);
    CNode **pSortingArray;
    pSortingArray = new CNode*[m_lNOfSymbols];
	Int i;
    for (i = 0; i < m_lNOfSymbols; i++)
        pSortingArray [i] = &m_pNodes[i];
    qsort(&pSortingArray[0],m_lNOfSymbols,
            sizeof (pSortingArray [0]), huffmanNodeCompare);
    for(i=0;i<m_lNOfSymbols;i++)
        writeOneTableEntry (stream, pSortingArray [i] - m_pNodes,
                lTotalFrequency,dNOfBits);
    delete pSortingArray;
    printStatistics (dEntropy, dNOfBits, stream);
}

Void CHuffmanTree::statistics (Int& lTotalFrequency,Double &dEntropy)
{
	Int i;
    for (i=0;i<m_lNOfSymbols;i++)
        lTotalFrequency+=m_pNodes[i].m_lFrequency;
    for(i=0;i<m_lNOfSymbols;i++)
    {
        double dP=m_pNodes[i].m_lFrequency/(double)lTotalFrequency;
        if(dP!=0)
            dEntropy+=dP*log(1.0/dP)/log(2.0);    
    };
}

Void CHuffmanTree::printStatistics (Double dEntropy, Double dNOfBits, ostream &stream)
{
    stream<<endl<<endl;
    stream<<"//Entropy Per Symbol : "<<dEntropy<<endl;
    stream<<"//Bits Per Symbol    : "<<dNOfBits<<endl;
    stream<<"//Table Efficiency   : "<<dEntropy/dNOfBits<<endl;
}

Int CHuffmanCoDec::makeIndexFromSymbolInTable(istream &huffmanTable)  
{
    Int lR;
	huffmanTable >> lR;
	return lR;
}

Void CHuffmanCoDec::trashRestOfLine (istream &str)
{
    Int iC;
    do
    {
        iC = str.get ();
    }
    while ((iC!='\n') && (iC!=EOF));
}

Bool CHuffmanCoDec::processOneLine (istream &huffmanTable, Int &lSymbol,
                    Int &lCodeSize, Char *pCode)
{
	huffmanTable >> ws;
    while(huffmanTable.peek()=='/')
    {
		trashRestOfLine (huffmanTable);
		huffmanTable >> ws;
    }
    if(huffmanTable.peek()==EOF)
        return FALSE;

	lSymbol=makeIndexFromSymbolInTable(huffmanTable);      
	huffmanTable >> ws;
	int iC=huffmanTable.get();                            
	lCodeSize=0;                                       
	while((iC=='0')||(iC=='1'))                             
    {                                                       
        if(pCode)                                           
        {                                                   
            if(iC=='0')                                     
                pCode[lCodeSize]=0;                         
            else                                            
                pCode[lCodeSize]=1;                         
        };                                                  
        lCodeSize++;                                        
        iC=huffmanTable.get();                            
    };
    if((iC!='\n')&&(iC!=EOF))
        trashRestOfLine(huffmanTable);                         
    assert(lCodeSize);
    return TRUE;
}

Void CHuffmanCoDec::profileTable (istream &huffmanTable,
            Int &lNOfSymbols, Int &lMaxCodeSize)
{
    huffmanTable.clear();
    huffmanTable.seekg(0,ios::beg);
    lNOfSymbols=0;
    lMaxCodeSize=0;
    while(huffmanTable.peek()!=EOF)
    {
        Int lCodeSize;
        Int lSymbol;
        if (processOneLine(huffmanTable,lSymbol,lCodeSize,NULL))
        {
            lNOfSymbols++;
            if(lCodeSize>lMaxCodeSize)
                lMaxCodeSize=lCodeSize;
            assert(lCodeSize);
        };
    };
    assert(lNOfSymbols>1);
    assert(lMaxCodeSize);
}

CHuffmanDecoder::CHuffmanDecoder (CInBitStream &bitStream)
{
    attachStream (bitStream);
}

CHuffmanDecoder::CHuffmanDecoder (CInBitStream &bitStream, VlcTable *pVlc)
{
    attachStream (bitStream);
	loadTable (pVlc);

}

CHuffmanDecoder::~CHuffmanDecoder()
{
    delete []m_pTree;
}

Void CHuffmanDecoder::realloc(Int lOldSize,Int lNewSize)
{
    CHuffmanDecoderNode *pNewTree=new CHuffmanDecoderNode[lNewSize];
    Int i;
    for(i=0;i<lOldSize;i++)
    {
        pNewTree[i].m_c0End=m_pTree[i].m_c0End;
        pNewTree[i].m_c1End=m_pTree[i].m_c1End;
        pNewTree[i].m_l0NextNodeOrSymbol=m_pTree[i].m_l0NextNodeOrSymbol;
        pNewTree[i].m_l1NextNodeOrSymbol=m_pTree[i].m_l1NextNodeOrSymbol;
    };
    delete []m_pTree;
    m_pTree=pNewTree;
}

void CHuffmanDecoder::loadTable(istream &huffmanTable,Bool bIncompleteTree)
{
    Int lTableSize;
    Int lNOfSymbols;
    Int lMaxCodeSize;
    Int lNextFreeNode=1;
    profileTable (huffmanTable,lNOfSymbols,lMaxCodeSize);