huffman.c

au1200 linux2.6.11 硬件解码mae驱动和maiplayer播放器源码

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

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)
    Sehoon Son ([e-mail]) Samsung AIT

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.c

Abstract:

	Classes for Huffman encode/decode.

Revision History:

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

#include <stdlib.h>
#include <string.h>
#include "typeapi.h"
#include "huffman.h"
#include "math.h"
#include "bitstrm.h"
#include "vlc.h"
#include "codehead.h"
#include "mode.h"
#include "global.h"
#include "vopses.h"
#include "vopsedec.h"

PPHUFFMAN_DEC_STRUCT m_pentrdecDCT;					// decoder for DCT
PPHUFFMAN_DEC_STRUCT m_pentrdecDCTIntra;			// decoder for Y and A planes of Intra VOP/MB
PPHUFFMAN_DEC_STRUCT m_pentrdecMV;					// decoder for MV
PPHUFFMAN_DEC_STRUCT m_pentrdecMCBPCintra;			// decoder for MCBPC = intra 
PPHUFFMAN_DEC_STRUCT m_pentrdecMCBPCinter;			// decoder for MCBPC = inter 
PPHUFFMAN_DEC_STRUCT m_pentrdecCBPY;				// decoder for CBPY 
PPHUFFMAN_DEC_STRUCT m_pentrdecIntraDCy;			// decoder for IntraDC (mpeg2 mode only)
PPHUFFMAN_DEC_STRUCT m_pentrdecIntraDCc;			// decoder for IntraDC (mpeg2 mode only)
PPHUFFMAN_DEC_STRUCT m_pentrdecMbTypeBVOP;			// decoder for MBtype in B-VOP

#define CHuffmanDecoderNode(pHD)\
{\
    pHD->m_c0End = 0;\
    pHD->m_c1End = 0;\
    pHD->m_l0NextNodeOrSymbol = -1;\
    pHD->m_l1NextNodeOrSymbol = -1;\
}

#ifndef NO_ASSERTS
Bool is0Valid(PHUFFMAN_DEC_STRUCT pHD) 
{
    if ((pHD->m_c0End == 0) && (pHD->m_l0NextNodeOrSymbol == -1))
            return FALSE;

    return TRUE;
}

Bool is1Valid(PHUFFMAN_DEC_STRUCT pHD) 
{
    if ((pHD->m_c1End == 0) && (pHD->m_l1NextNodeOrSymbol == -1))
            return FALSE;

    return TRUE;
}
#endif

Void loadTable(VlcTable *pVlc, PPHUFFMAN_DEC_STRUCT pPHD)
{
    Int lTableSize, i, lNextFreeNode = 1, lNOfSymbols = 0, lMaxCodeSize = 0;
    Int lCodeSize, lSymbol = 0, lCurrentNode, iBit;
	VlcTable *pVlcTmp;

#ifdef FAST_LUT_DECODE	
	// PHD actually starts at first offset; zero entry is LUT pointer
	pPHD = (PPHUFFMAN_DEC_STRUCT)((int) &pPHD[1]);
#endif

    for(pVlcTmp = pVlc; pVlcTmp->pchBits!=NULL; pVlcTmp++)
    {
        lNOfSymbols++;
		lCodeSize = strlen(pVlcTmp->pchBits);

#ifndef NO_ASSERTS
		assert(lNOfSymbols>=0 && lNOfSymbols<1000);
		assert(lCodeSize>0);
#endif

        if(lCodeSize>lMaxCodeSize)
			lMaxCodeSize=lCodeSize;
    }
#ifndef NO_ASSERTS
    assert(lNOfSymbols>1);
    assert(lMaxCodeSize>0);
#endif

    // Since we allocated 20 extra elements, use that here
    lTableSize=lNOfSymbols+20;
    for (i=0;i<lTableSize;i++)
    {
        pPHD[i] = (PHUFFMAN_DEC_STRUCT) malloc (HUFFMAN_DEC_STRUCT_SIZE);

        CHuffmanDecoderNode (pPHD[i]);
    }

    for(pVlcTmp = pVlc; pVlcTmp->pchBits!=NULL; pVlcTmp++, lSymbol++)
    {
        lCodeSize = strlen(pVlcTmp->pchBits);
        lCurrentNode = 0;

#ifndef NO_ASSERTS
        assert(lSymbol<lNOfSymbols);                                              
        assert(lCodeSize);       
#endif
   
        for(i=0;i<lCodeSize;i++)                                             
        {                                                                         
            iBit = pVlcTmp->pchBits[i] - '0';

#ifndef NO_ASSERTS
			assert((iBit==0)||(iBit==1));                                         
#endif
            if(i==(lCodeSize-1))                                                  
            {                                                                     
                if(iBit==0)                                                       
                {                                                                 
#ifndef NO_ASSERTS
                    assert(!is0Valid(pPHD[lCurrentNode]));                    
#endif
                    pPHD[lCurrentNode]->m_c0End=1;                              
                    pPHD[lCurrentNode]->m_l0NextNodeOrSymbol=lSymbol;           
                }                                                                 
                else                                                              
                {                                                                 
#ifndef NO_ASSERTS
                    assert(!is1Valid(pPHD[lCurrentNode]));                    
#endif
                    pPHD[lCurrentNode]->m_c1End=1;                              
                    pPHD[lCurrentNode]->m_l1NextNodeOrSymbol=lSymbol;           
                }                                                                 
            }                                                                     
            else                                                                  
            {                                                                     
                if(iBit==0)                                                       
                {                                                                 
                    if (pPHD[lCurrentNode]->m_l0NextNodeOrSymbol == -1)
                    {
#ifdef DUAL_MODE
                        if(lNextFreeNode>=lTableSize)
                        {
                            pPHD = realloc(lTableSize,lTableSize+10, pPHD);
                            lTableSize+=10;
                        }
#endif
                        pPHD[lCurrentNode]->m_c0End=0;                          
                        pPHD[lCurrentNode]->m_l0NextNodeOrSymbol=lNextFreeNode; 
                        lNextFreeNode++;                                          
                    }
#ifndef NO_ASSERTS
                    assert(pPHD[lCurrentNode]->m_c0End==0);                     
#endif
                    lCurrentNode=pPHD[lCurrentNode]->m_l0NextNodeOrSymbol;      
                }                                                                 
                else                                                              
                {                                                                 
                    if (pPHD[lCurrentNode]->m_l1NextNodeOrSymbol == -1)
                    {
#ifdef DUAL_MODE
                        if(lNextFreeNode>=lTableSize)
                        {
                            pPHD = realloc(lTableSize,lTableSize+10, pPHD);
                            lTableSize+=10;
                        }
#endif
                        pPHD[lCurrentNode]->m_c1End=0;                          
                        pPHD[lCurrentNode]->m_l1NextNodeOrSymbol=lNextFreeNode; 
                        lNextFreeNode++;                                          
                    }
#ifndef NO_ASSERTS
                    assert(pPHD[lCurrentNode]->m_c1End==0);                     
#endif
                    lCurrentNode=pPHD[lCurrentNode]->m_l1NextNodeOrSymbol;      
                }                                                                
            }                                                                    
        }
    }

#ifdef FAST_LUT_DECODE
	/*
	** PHD actually starts at first offset; zero entry is LUT pointer.
	**	Restore pPHD to its original value at function entry.
	*/
	pPHD = (PPHUFFMAN_DEC_STRUCT)((int) pPHD - 4);
	build_tab(pVlc, pPHD, NULL);
#endif
}

#ifdef FAST_LUT_DECODE
/*
** symbol_parse: 
**		<bits> - msb-aligned symbol
**		<n>    - number of bits to parse
**
**		returns the current node for input bits at end of parse
*/
Int symbol_parse(PPHUFFMAN_DEC_STRUCT pPHD, int bits, int n)
{
    Char cEnd=0;
    Int lNextNodeOrSymbol=0, i;
    PHUFFMAN_DEC_STRUCT pHuffDec;

    for (i=0; i<n; i++)
    {
        // Save the current pointer
        pHuffDec = pPHD[lNextNodeOrSymbol];
        cEnd=TRUE;

        if(bits >= 0)  // MSB == 0
        {
            if (pHuffDec->m_l0NextNodeOrSymbol != -1)
            {
                cEnd=pHuffDec->m_c0End;
                lNextNodeOrSymbol=pHuffDec->m_l0NextNodeOrSymbol;
            }
        }
        else
        {
            if (pHuffDec->m_l1NextNodeOrSymbol != -1)
            {
                cEnd=pHuffDec->m_c1End;
                lNextNodeOrSymbol=pHuffDec->m_l1NextNodeOrSymbol;
            }
        }
		bits <<= 1;

#ifndef NO_ASSERTS
		if (cEnd) 
        {
			printf("WARNING: symbol end detected during symbol parse!\n");
		}
#endif
    } 

    return lNextNodeOrSymbol;
}

/*
**	build_tab: construct the huffman decoder table for the code
**	given by pV and pPHD.  If tab_name is null, allocate table
**	dynamically and put its address at pPHD[0] (production case).
**	Otherwise, create a binary file and write to disk.
*/
build_tab(VlcTable *pV, PPHUFFMAN_DEC_STRUCT pPHD, char *tab_name)
{
	FILE *fd;
	sym_tab st[SYM_TAB_LEN];

	VlcTable *pVlcTmp;
	int i, iBit, nShift, symbol, nSymbol=0, lCodeSize, accum;
	for (i=0; i<SYM_TAB_LEN; i++) {
		st[i].sym = st[i].len = 0;
	}

	/*
	**	populate lookup table with {symbol, length} elements.
	**  If symbol is too large (>SYM_TAB_BITS) to be uniquely
	**	decoded, call symbol parser to get decoder state after
	**  parsing the first SYM_TAB_BITS of the symbol and store
	**	that as the "symbol"
	*/
    for(pVlcTmp = pV; pVlcTmp->pchBits!=NULL; pVlcTmp++, nSymbol++)
    {
		lCodeSize = strlen(pVlcTmp->pchBits);

		// pack symbol MSB-justified
		accum = 0;
		for (i=0; i<lCodeSize; i++) {
			iBit = pVlcTmp->pchBits[i] - '0';
			accum = ((accum << 1) | iBit);
		}

		if (lCodeSize > SYM_TAB_BITS) {
			nShift = sizeof(int)*8 - lCodeSize;	// get high 8 bits at MSB
			accum <<= nShift; 
			symbol = symbol_parse(&pPHD[1], accum, SYM_TAB_BITS);
			/*
			** store decoder state at index based on 8 msb's.
			** len is remaining bits in symbol needing to be decoded
			** after the first SYM_TAB_BITS
			*/
			accum = (accum>>24) & 0xff;
			st[accum].sym = symbol;	// decode state machine after leading 8 bits
			st[accum].len = -1;		// indicate bit decode required
			
		}
		else
		{
			/*
			**	fill table locations with index = 
			**  [symbol | x], where x = don't care bits
			*/
			nShift = SYM_TAB_BITS - lCodeSize;	// get high 8 bits at MSB
			accum <<= nShift; 
			for (i=0; i<(1<<nShift); i++) {
				st[accum + i].sym = nSymbol;
				st[accum + i].len = lCodeSize;
			}