huffman2.c

h261协议的h261编码码,lib_261.h里面提供了详细的接口和说明.

/*************************************************************
Copyright (C) 1990, 1991, 1993 Andy C. Hung, all rights reserved.
PUBLIC DOMAIN LICENSE: Stanford University Portable Video Research
Group. If you use this software, you agree to the following: This
program package is purely experimental, and is licensed "as is".
Permission is granted to use, modify, and distribute this program
without charge for any purpose, provided this license/ disclaimer
notice appears in the copies.  No warranty or maintenance is given,
either expressed or implied.  In no event shall the author(s) be
liable to you or a third party for any special, incidental,
consequential, or other damages, arising out of the use or inability
to use the program for any purpose (or the loss of data), even if we
have been advised of such possibilities.  Any public reference or
advertisement of this source code should refer to it as the Portable
Video Research Group (PVRG) code, and not by any author(s) (or
Stanford University) name.
*************************************************************/
/*
************************************************************
huffman.c

This file contains the Huffman routines.

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

/*LABEL huffman.c */

#include <stdio.h>
#include <stdlib.h>
#include "stream2.h"
#include "globals2.h"
#include "ctables2.h"

/*PUBLIC*/

extern void inithuff2();
//extern int Encode_en();
extern int Decode2();
//extern void PrintDhuff();
//extern void PrintEhuff();
//extern void PrintTable();

static DHUFF *MakeDhuff2();
static EHUFF *MakeEhuff2();
static void LoadETable2();


static void LoadDTable2();



static int GetNextState2();
static void AddCode2();

/*PRIVATE*/

#define fgetb mgetb2
//#define fputv_en mputv_en
//#define fputb mputb_en

/* Actual Tables */

extern IMAGE *CImage2;
extern FRAME *CFrame2;
extern int Loud2;
extern int ErrorValue2;

int NumberBitsCoded2=0;

#define GetLeft(sval,huff) (((huff->state[(sval)]) >> 16)& 0x0000ffff)
#define GetRight(sval,huff) ((huff->state[(sval)]) & 0xffff)

#define SetLeft(number,sval,huff) huff->state[(sval)]=\
  (((huff->state[(sval)]) & 0xffff)|(number<<16));
#define SetRight(number,sval,huff) huff->state[(sval)]=\
  (((huff->state[(sval)]) & 0xffff0000)|(number));

#define EmptyState 0xffff
#define Numberp(value) ((value & 0x8000) ? 1 : 0)
#define MakeHVal(value) (value | 0x8000)
#define GetHVal(value) (value & 0x7fff)

#define FREEEHUFF(p) { if(p){ FREE(p->Hlen); FREE(p->Hcode); } FREE(p); }

DHUFF *MBADHuff2;
DHUFF *MVDDHuff2;
DHUFF *CBPDHuff2;
DHUFF *T1DHuff2;
DHUFF *T2DHuff2;
DHUFF *T3DHuff2;

EHUFF *MBAEHuff2;
EHUFF *MVDEHuff2;
EHUFF *CBPEHuff2;
EHUFF *T1EHuff2;
EHUFF *T2EHuff2;
EHUFF *T3EHuff2;

/*START*/
/*BFUNC

inithuff2() initializes all of the Huffman structures to the
appropriate values. It must be called before any of the tables are
used.

EFUNC*/

void inithuff2()
{
  BEGIN("inithuff2");

  //DHUFF
  FREE(MBADHuff2);
  MBADHuff2 = MakeDhuff2();
  FREE(MVDDHuff2);
  MVDDHuff2 = MakeDhuff2();
  FREE(CBPDHuff2);
  CBPDHuff2 = MakeDhuff2();
  FREE(T1DHuff2);
  T1DHuff2 = MakeDhuff2();
  FREE(T2DHuff2);
  T2DHuff2 = MakeDhuff2();
  FREE(T3DHuff2);
  T3DHuff2 = MakeDhuff2();

  //EHUFF
  FREEEHUFF(MBAEHuff2);
  MBAEHuff2 = MakeEhuff2(40);
  FREEEHUFF(MVDEHuff2);
  MVDEHuff2 = MakeEhuff2(40);
  FREEEHUFF(CBPEHuff2);
  CBPEHuff2 = MakeEhuff2(70);
  FREEEHUFF(T1EHuff2);
  T1EHuff2 = MakeEhuff2(8192);
  FREEEHUFF(T2EHuff2);
  T2EHuff2 = MakeEhuff2(8192);
  FREEEHUFF(T3EHuff2);
  T3EHuff2 = MakeEhuff2(20);

  LoadDTable2(MBACoeff2,MBADHuff2);
  LoadETable2(MBACoeff2,MBAEHuff2);
  LoadDTable2(MVDCoeff2,MVDDHuff2);
  LoadETable2(MVDCoeff2,MVDEHuff2);
  LoadDTable2(CBPCoeff2,CBPDHuff2);
  LoadETable2(CBPCoeff2,CBPEHuff2);
  LoadDTable2(TCoeff12,T1DHuff2);
  LoadETable2(TCoeff12,T1EHuff2);
  LoadDTable2(TCoeff22,T2DHuff2);
  LoadETable2(TCoeff22,T2EHuff2);
  LoadDTable2(MTypeCoeff2,T3DHuff2);
  LoadETable2(MTypeCoeff2,T3EHuff2);
}

/*BFUNC

MakeDhuff2() constructs a decoder Huffman table and returns the
structure.

EFUNC*/

static DHUFF *MakeDhuff2()
{
  BEGIN("MakeDhuff2");
  int i;
  DHUFF *temp;

  temp = MakeStructure(DHUFF);
  temp->NumberStates=1;
  for(i=0;i<512;i++) {temp->state[i] = -1;}
  return(temp);
}

/*BFUNC

MakeEhuff2() constructs an encoder huff with a designated table-size.
This table-size, n, is used for the lookup of Huffman values, and must
represent the largest positive Huffman value.

EFUNC*/

//static EHUFF *MakeEhuff2(n)
//     int n;
static EHUFF *MakeEhuff2(int n)
{
  BEGIN("MakeEhuff2");
  int i;
  EHUFF *temp;

  temp = MakeStructure(EHUFF);
  temp->n = n;
  temp->Hlen = (int *) calloc(n,sizeof(int));
  temp->Hcode = (int *) calloc(n,sizeof(int));
  for(i=0;i<n;i++)
    {
      temp->Hlen[i] = -1;
      temp->Hcode[i] = -1;
    }
  return(temp);
}

/*BFUNC

LoadETable2() is used to load an array into an encoder table.  The
array is grouped in triplets and the first negative value signals the
end of the table.

EFUNC*/

//static void LoadETable2(array,table)
//     int *array;
//     EHUFF *table;
static void LoadETable2(int *array,EHUFF *table)
{
	BEGIN("LoadETable2");
    
	while(*array>=0)
	{
		if (*array>table->n)
		{
			WHEREAMI();
			printf("Table overflow.\n");
			exit(ERROR_BOUNDS);
		}
		table->Hlen[*array] = array[1];
		table->Hcode[*array] = array[2];
		array+=3;
	}
}

/*BFUNC

LoadDHUFF() is used to load an array into the DHUFF structure. The
array consists of trios of Huffman definitions, the first one the
value, the next one the size, and the third one the code.

EFUNC*/

//static void LoadDTable2(array,table)
//     int *array;
//     DHUFF *table;
static void LoadDTable2(int *array,DHUFF *table)
{
  BEGIN("LoadDTable2");

  while(*array>=0)
    {
      AddCode2(array[1],array[2],array[0],table);
      array+=3;
    }
}

/*BFUNC

GetNextState2() returns the next free state of the decoder Huffman
structure.  It exits an error upon overflow.

EFUNC*/

//static int GetNextState2(huff)
//     DHUFF *huff;
static int GetNextState2(DHUFF *huff)
{
  BEGIN("GetNextState2");

  if (huff->NumberStates==512)
    {
      WHEREAMI();
      printf("Overflow\n");
      exit(ERROR_BOUNDS);
    }
  return(huff->NumberStates++);
}

/*BFUNC

Encode_en() encodes a value according to a designated encoder Huffman
table out to the stream. It returns the number of bits written to the
stream and a zero on error.

EFUNC*/

//int Encode_en(val,huff)
//     int val;
//     EHUFF *huff;
//int Encode_en(int val,EHUFF *huff)
//{
//  BEGIN("Encode_en");
//
//  if (val < 0)
//    {
//      WHEREAMI(); /* Serious error, illegal, notify... */
//      printf("Out of bounds val:%d.\n",val);
//      return(0);
//    }
//  else if (val>=huff->n)
//    {
//      return(0); /* No serious error, can occur with some values */
//    }
//  else if (huff->Hlen[val]<0)
//    {
//      return(0);  /* No serious error: can pass thru by alerting routine.*/
//    }
//  else
//    {
///*      printf("Value: %d|%x  Length: %d  Code: %d\n",
//	     val,val,huff->Hlen[val],huff->Hcode[val]);*/
//      NumberBitsCoded2+=huff->Hlen[val];
//      fputv_en(huff->Hlen[val],huff->Hcode[val]);
//      return(huff->Hlen[val]);
//    }
//}


/*BFUNC

Decode2() returns an integer read off the stream using the designated
Huffman structure.

EFUNC*/

//int Decode2(huff)
//     DHUFF *huff;

int Decode2(DHUFF *huff)
{
	  BEGIN("Decode2");
	  int Next,cb;
	  int CurrentState=0;

	//static int i=0;
	//int j;
	//if(i>=167){
	//if(i>=186){
	//if(i>=177){
	//	for(j=0;j<5;j++) fprintf(fp,"\n");
	//	fprintf(fp,"num = %d\n",i);
	//	fprintf(fp,"NumberStates=%d\n",huff->NumberStates);
	//	for(j=0;j<512;j++){
	//		fprintf(fp,"huff->state[%d]=%d\n",j,huff->state[j]);
	//	}
	//	printf("i = %d\n",i);
	//}
	//i++;

	



	while(1)
	{
		cb = fgetb();
		if (cb)
		{
			Next =  GetLeft(CurrentState,huff);
			if (Next == EmptyState)
			{
				WHEREAMI();
				printf("Invalid State Reached.\n");
				exit(ERROR_BOUNDS);
			}
			else if (Numberp(Next))
			{
				return(GetHVal(Next));
			}
			else
			{
				CurrentState = Next;
			}
		}
		else
		{
			Next =  GetRight(CurrentState,huff);
			if (Next == EmptyState)
			{
				WHEREAMI();
				printf("Invalid State Reached.\n");
				exit(ERROR_BOUNDS);
			}
			else if (Numberp(Next))//else if(    ( (value & 0x8000) ? 1:0)    )
			{
				return(GetHVal(Next));
			}
			else
			{
				CurrentState = Next;
			}
		}
	}
}

/*BFUNC

AddCode2() adds a Huffman code to the decoder structure. It is called
everytime a new Huffman code is to be defined. This function exits
when an invalid code is attempted to be placed in the structure.

EFUNC*/

//static void AddCode2(n,code,value,huff)
//     int n;
//     int code;
//     int value;
//     DHUFF *huff;
static void AddCode2(int n,int code,int value,DHUFF *huff)
{
	BEGIN("AddCode2");
	int i,Next;
	int CurrentState=0;

	if (value < 0)
	{
		WHEREAMI();
		printf("Negative addcode value: %d\n",value);
		exit(ERROR_BOUNDS);
	}
	for(i=n-1;i>0;i--)
	{
		if (code & (1 << i))
		{
			Next = GetLeft(CurrentState,huff);
			if (Next == EmptyState)
			{
				Next = GetNextState2(huff);
				SetLeft(Next,CurrentState,huff);
				CurrentState = Next;
			}
			else if (Numberp(Next))
			{
				WHEREAMI();
				printf("Bad Value/State match:\n");
				printf("Length: %d   Code: %d  Value: %d\n",n,code,value);
				exit(ERROR_BOUNDS);
			}
			else
			{
				CurrentState = Next;
			}
		}
		else
		{
			Next = GetRight(CurrentState,huff);
			if (Next == EmptyState)
			{
				Next = GetNextState2(huff);
				SetRight(Next,CurrentState,huff);
				CurrentState = Next;
			}
			else if (Numberp(Next))
			{
				WHEREAMI();
				printf("Bad Value/State match:\n");
				printf("Length: %d   Code: %d  Value: %d\n",n,code,value);
				exit(ERROR_BOUNDS);
			}
			else
			{
				CurrentState = Next;
			}
		}
	}
	if (code & 1)
	{
		Next = GetLeft(CurrentState,huff);
		if (Next != EmptyState)
		{
			WHEREAMI();
			printf("Overflow on Huffman Table: Nonunique prefix.\n");
			printf("Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
			exit(ERROR_BOUNDS);
		}
		SetLeft(MakeHVal(value),CurrentState,huff);
	}
	else
	{
		Next = GetRight(CurrentState,huff);
		if (Next != EmptyState)
		{
			WHEREAMI();
			printf("Overflow on Huffman Table: Nonunique prefix.\n");
			printf("Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
			exit(ERROR_BOUNDS);
		}
		SetRight(MakeHVal(value),CurrentState,huff);
	}
}


/*BFUNC

PrintDHUFF() prints out the decoder Huffman structure that is passed
into it.

EFUNC*/

//void PrintDhuff(huff)
//     DHUFF *huff;
//void PrintDhuff(DHUFF *huff)
//{
//  int i;
//
//  printf("Modified Huffman Decoding Structure: %x\n",huff);
//  printf("Number of states %d\n",huff->NumberStates);
//  for(i=0;i<huff->NumberStates;i++)
//    {
//      printf("State: %d  Left State: %x  Right State: %x\n",
//	     i,
//	     GetLeft(i,huff),
//	     GetRight(i,huff));
//    }
//}

/*BFUNC

PrintEhuff() prints the encoder Huffman structure passed into it.

EFUNC*/

//void PrintEhuff(huff)
//     EHUFF *huff;
//void PrintEhuff(EHUFF *huff)
//{
//  BEGIN("PrintEhuff");
//  int i;
//
//  printf("Modified Huffman Encoding Structure: %x\n",huff);
//  printf("Number of values %d\n",huff->n);
//  for(i=0;i<huff->n;i++)
//    {
//      if (huff->Hlen[i]>=0)
//	{
//	  printf("Value: %x  Length: %d  Code: %x\n",
//	     i,huff->Hlen[i],huff->Hcode[i]);
//	}
//    }
//}

/*BFUNC

PrintTable() prints out 256 elements in a nice byte ordered fashion.

EFUNC*/

//void PrintTable(table)
//     int *table;
//void PrintTable(int *table)
//{
//  int i,j;
//
//  for(i=0;i<16;i++)
//    {
//      for(j=0;j<16;j++)
//	{
//	  printf("%2x ",*(table++));
//	}
//      printf("\n");
//    }
//}

void freeHuffman2()
{
	
	//DHUFF
	FREE(MBADHuff2);
	FREE(MVDDHuff2);
	FREE(CBPDHuff2);
	FREE(T1DHuff2);
	FREE(T2DHuff2);
	FREE(T3DHuff2);

	//EHUFF
	FREEEHUFF(MBAEHuff2);
	FREEEHUFF(MVDEHuff2);
	FREEEHUFF(CBPEHuff2);
	FREEEHUFF(T1EHuff2);
	FREEEHUFF(T2EHuff2);
	FREEEHUFF(T3EHuff2);
}

/*END*/