huffman.cpp

网络MPEG4IP流媒体开发源代码

    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((uint32_t)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);
    return lNextNodeOrSymbol;
}

CHuffmanEncoder::~CHuffmanEncoder ()
{
	delete m_pCodeTable; 
	delete m_pSizeTable;
}

CHuffmanEncoder::CHuffmanEncoder(COutBitStream &bitStream)
{
    attachStream(bitStream);
}

CHuffmanEncoder::CHuffmanEncoder(COutBitStream &bitStream, VlcTable *pVlc)
{
	attachStream(bitStream);

	loadTable(pVlc);
}

Void CHuffmanEncoder::loadTable(istream &huffmanTable)
{
    Int lNOfSymbols;
    Int lMaxCodeSize;
    profileTable(huffmanTable,lNOfSymbols,lMaxCodeSize);
    assert(lNOfSymbols>1);
    assert(lMaxCodeSize);
    m_lCodeTableEntrySize=lMaxCodeSize/8;
    if(lMaxCodeSize%8)
        m_lCodeTableEntrySize++;
    m_pSizeTable = new Int [lNOfSymbols];
    m_pCodeTable = new Int [lNOfSymbols];
    Char *pCode=new Char[lMaxCodeSize];
    huffmanTable.clear();
    huffmanTable.seekg(0,ios::beg);
    while(huffmanTable.peek()!=EOF)
    {
        Int lCodeSize;
        Int lSymbol;
        Int iBitPosition=0;
        if(processOneLine(huffmanTable,lSymbol,lCodeSize,pCode))
        {
            assert(lSymbol<lNOfSymbols);                                                 
            assert(lCodeSize >=0 && lCodeSize <= (Int) sizeof (Int) * 8);
            m_pSizeTable[lSymbol]=lCodeSize;                                             
            Int* pCodeTableEntry=&m_pCodeTable[lSymbol]; 
            for(Int i=0;i<lCodeSize;i++)                                                
            {                                                                            
                if(iBitPosition==0)                                                      
                    *pCodeTableEntry=0;                                                  
                assert((pCode[lCodeSize - i - 1]==0)||(pCode[lCodeSize - i - 1]==1));                                    
                if(pCode[lCodeSize - i - 1]==0)                                                          
                    *pCodeTableEntry&=~(0x01<<iBitPosition);                             
                else                                                                     
                    *pCodeTableEntry|=0x01<<iBitPosition;                                
                iBitPosition++;                                                          
				/*
                if(iBitPosition>=8)                                                      
                {                                                                        
                    iBitPosition=0;                                                      
                    pCodeTableEntry++;                                                   
                } 
				*/
            }                                                                           
        }
    }
    delete pCode;
}

Void CHuffmanEncoder::loadTable(VlcTable *pVlc)
{
    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_lCodeTableEntrySize=lMaxCodeSize/8;
    if(lMaxCodeSize%8)
        m_lCodeTableEntrySize++;
    m_pSizeTable = new Int [lNOfSymbols];
    m_pCodeTable = new Int [lNOfSymbols];
	
	for(pVlcTmp = pVlc; pVlcTmp->pchBits!=NULL; pVlcTmp++)
    {
        Int lCodeSize = strlen(pVlcTmp->pchBits);
        Int lSymbol = pVlcTmp->lSymbol;
        Int iBitPosition=0;

        assert(lSymbol<lNOfSymbols);                                                 
        assert(lCodeSize >=0 && lCodeSize <= (Int) sizeof (Int) * 8);
        m_pSizeTable[lSymbol]=lCodeSize;                                             
        Int* pCodeTableEntry=&m_pCodeTable[lSymbol]; 
        for(Int i=0;i<lCodeSize;i++)                                                
        {                                                                            
	        if(iBitPosition==0)                                                      
		        *pCodeTableEntry=0;                                                  
			Int iBitC = pVlcTmp->pchBits[lCodeSize - i - 1];
            assert(iBitC=='0' || iBitC=='1');
            if(iBitC=='0')                                                          
				*pCodeTableEntry&=~(0x01<<iBitPosition);                             
            else                                                                     
                *pCodeTableEntry|=0x01<<iBitPosition;                                
            iBitPosition++;                                                          
			/*
                if(iBitPosition>=8)                                                      
                {                                                                        
                    iBitPosition=0;                                                      
                    pCodeTableEntry++;                                                   
                } 
			*/                                                                         
        }
    }
}

void CHuffmanEncoder::attachStream(COutBitStream &bitStream)
{
    m_pBitStream=&bitStream;
}