huffman.cpp

《Visual C++小波变换技术与工程实践》靳济芳编著的光盘程序。

        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);
    assert(lNOfSymbols>1);
    assert(lMaxCodeSize);
    m_pTree = new CHuffmanDecoderNode [lNOfSymbols - 1];
    lTableSize=lNOfSymbols-1;
    Char *pCode = new Char[lMaxCodeSize];
    huffmanTable.clear();
    huffmanTable.seekg(0,ios::beg);
    while(huffmanTable.peek()!=EOF)
    {
        Int lCodeSize;
        Int lSymbol;
        Int lCurrentNode=0;
        if (processOneLine (huffmanTable,lSymbol,lCodeSize,pCode))
        {
            assert((lSymbol<lNOfSymbols)||bIncompleteTree);                                              
            assert(lCodeSize);                                                        
            for(Int i=0;i<lCodeSize;i++)                                             
            {                                                                         
				assert ((lCurrentNode<lNOfSymbols-1)||bIncompleteTree);                                 
                int iBit=pCode[i];                                                    
                assert((iBit==0)||(iBit==1));                                         
                if(i==(lCodeSize-1))                                                  
                {                                                                     
                    if(iBit==0)                                                       
                    {                                                                 
                        assert(!m_pTree[lCurrentNode].is0Valid());                    
                        m_pTree[lCurrentNode].m_c0End=1;                              
                        m_pTree[lCurrentNode].m_l0NextNodeOrSymbol=lSymbol;           
                    }                                                                 
                    else                                                              
                    {                                                                 
                        assert(!m_pTree[lCurrentNode].is1Valid());                    
                        m_pTree[lCurrentNode].m_c1End=1;                              
                        m_pTree[lCurrentNode].m_l1NextNodeOrSymbol=lSymbol;           
                    }                                                                 
                }                                                                     
                else                                                                  
                {                                                                     
                    if(iBit==0)                                                       
                    {                                                                 
                        if(!m_pTree[lCurrentNode].is0Valid())                         
                        {                                                             
							if(bIncompleteTree)
                                if(lNextFreeNode>=lTableSize)
                                {
                                    realloc(lTableSize,lTableSize+10);
                                    lTableSize+=10;
                                };
                            assert((lNextFreeNode<lNOfSymbols-1)||bIncompleteTree);                    
                            m_pTree[lCurrentNode].m_c0End=0;                          
                            m_pTree[lCurrentNode].m_l0NextNodeOrSymbol=lNextFreeNode; 
                            lNextFreeNode++;                                          
                        };                                                            
                        assert(m_pTree[lCurrentNode].m_c0End==0);                     
                        lCurrentNode=m_pTree[lCurrentNode].m_l0NextNodeOrSymbol;      
                    }                                                                 
                    else                                                              
                    {                                                                 
                        if(!m_pTree[lCurrentNode].is1Valid())                         
                        {                                                             
							if(bIncompleteTree)
                                if(lNextFreeNode>=lTableSize)
                                {
                                    realloc(lTableSize,lTableSize+10);
                                    lTableSize+=10;
                                };
                            assert((lNextFreeNode<lNOfSymbols-1)||bIncompleteTree);                    
                            m_pTree[lCurrentNode].m_c1End=0;                          
                            m_pTree[lCurrentNode].m_l1NextNodeOrSymbol=lNextFreeNode; 
                            lNextFreeNode++;                                          
                        };                                                            
                        assert(m_pTree[lCurrentNode].m_c1End==0);                     
                        lCurrentNode=m_pTree[lCurrentNode].m_l1NextNodeOrSymbol;      
                    }                                                                
                }                                                                    
            }
        }
    }
    for(Int i=0;i<lTableSize;i++)
    {
        assert((m_pTree[i].is0Valid())||bIncompleteTree);
        assert((m_pTree[i].is1Valid())||bIncompleteTree);
    };
    delete pCode;
}

void CHuffmanDecoder::loadTable(VlcTable *pVlc,Bool bIncompleteTree)
{
    Int lTableSize;
    Int lNextFreeNode = 1;
    Int lNOfSymbols = 0;
    Int lMaxCodeSize = 0;
	VlcTable *pVlcTmp;
    for(pVlcTmp = pVlc; pVlcTmp->pchBits!=NULL; pVlcTmp++)
    {
        lNOfSymbols++;
		Int lCodeSize = strlen(pVlcTmp->pchBits);

		assert(pVlcTmp->lSymbol>=0 && pVlcTmp->lSymbol<1000);
		assert(lCodeSize>0);

        if(lCodeSize>lMaxCodeSize)
			lMaxCodeSize=lCodeSize;
    }
    assert(lNOfSymbols>1);
    assert(lMaxCodeSize>0);
	
    m_pTree = new CHuffmanDecoderNode [lNOfSymbols - 1];
    lTableSize=lNOfSymbols-1;

    for(pVlcTmp = pVlc; pVlcTmp->pchBits!=NULL; pVlcTmp++)
    {
        Int lCodeSize = strlen(pVlcTmp->pchBits);
        Int lSymbol = pVlcTmp->lSymbol;
        Int lCurrentNode = 0;
		//printf("%d\t%d\t%s\n",lSymbol, lCodeSize, pVlcTmp->pchBits);

        assert((lSymbol<lNOfSymbols)||bIncompleteTree);                                              
        assert(lCodeSize);                                                        
        for(Int i=0;i<lCodeSize;i++)                                             
        {                                                                         
			assert ((lCurrentNode<lNOfSymbols-1)||bIncompleteTree);
            int iBit = pVlcTmp->pchBits[i] - '0';
			assert((iBit==0)||(iBit==1));                                         
            if(i==(lCodeSize-1))                                                  
            {                                                                     
                if(iBit==0)                                                       
                {                                                                 
                    assert(!m_pTree[lCurrentNode].is0Valid());                    
                    m_pTree[lCurrentNode].m_c0End=1;                              
                    m_pTree[lCurrentNode].m_l0NextNodeOrSymbol=lSymbol;           
                }                                                                 
                else                                                              
                {                                                                 
                    assert(!m_pTree[lCurrentNode].is1Valid());                    
                    m_pTree[lCurrentNode].m_c1End=1;                              
                    m_pTree[lCurrentNode].m_l1NextNodeOrSymbol=lSymbol;           
                }                                                                 
            }                                                                     
            else                                                                  
            {                                                                     
                if(iBit==0)                                                       
                {                                                                 
                    if(!m_pTree[lCurrentNode].is0Valid())                         
                    {                                                             
						if(bIncompleteTree)
                            if(lNextFreeNode>=lTableSize)
                            {
                                realloc(lTableSize,lTableSize+10);
                                lTableSize+=10;
                            };
                        assert((lNextFreeNode<lNOfSymbols-1)||bIncompleteTree);                    
                        m_pTree[lCurrentNode].m_c0End=0;                          
                        m_pTree[lCurrentNode].m_l0NextNodeOrSymbol=lNextFreeNode; 
                        lNextFreeNode++;                                          
                    };                                                            
                    assert(m_pTree[lCurrentNode].m_c0End==0);                     
                    lCurrentNode=m_pTree[lCurrentNode].m_l0NextNodeOrSymbol;      
                }                                                                 
                else                                                              
                {                                                                 
                    if(!m_pTree[lCurrentNode].is1Valid())                         
                    {                                                             
						if(bIncompleteTree)
                            if(lNextFreeNode>=lTableSize)
                            {
                                realloc(lTableSize,lTableSize+10);
                                lTableSize+=10;
                            };
                        assert((lNextFreeNode<lNOfSymbols-1)||bIncompleteTree);                    
                        m_pTree[lCurrentNode].m_c1End=0;                          
                        m_pTree[lCurrentNode].m_l1NextNodeOrSymbol=lNextFreeNode; 
                        lNextFreeNode++;                                          
                    };                                                            
                    assert(m_pTree[lCurrentNode].m_c1End==0);                     
                    lCurrentNode=m_pTree[lCurrentNode].m_l1NextNodeOrSymbol;      
                }                                                                
            }                                                                    
        }
    }
    for(Int i=0;i<lTableSize;i++)
    {
        assert((m_pTree[i].is0Valid())||bIncompleteTree);
        assert((m_pTree[i].is1Valid())||bIncompleteTree);
    }
}

Void CHuffmanDecoder::attachStream(CInBitStream &bitStream)
{
    m_pBitStream=&bitStream;
}

Int CHuffmanDecoder::decodeSymbol()
{
    Char cEnd=0;
    Int lNextNodeOrSymbol=0;
    do
    {
        Int iBit;
        iBit=m_pBitStream->getBits(1);
        if(iBit==0)
        {
            if(m_pTree[lNextNodeOrSymbol].is0Valid())
            {
                cEnd=m_pTree[lNextNodeOrSymbol].m_c0End;
                lNextNodeOrSymbol=m_pTree[lNextNodeOrSymbol].m_l0NextNodeOrSymbol;
            }
            else
            {
                cEnd=TRUE;
                lNextNodeOrSymbol=-1;
            }
        }
        else
        {
            if(m_pTree[lNextNodeOrSymbol].is1Valid())
            {
                cEnd=m_pTree[lNextNodeOrSymbol].m_c1End;
                lNextNodeOrSymbol=m_pTree[lNextNodeOrSymbol].m_l1NextNodeOrSymbol;
            }
            else
            {
                cEnd=TRUE;
                lNextNodeOrSymbol=-1;
            }
        };
    }
    while(cEnd==0);