huff_encode.c

Huffman压缩解压的完整程序

/* --- C ---  
************************************************************************
*
*    Filename    : huff.c
*    Description : Huffman-decoding
*    Part of     : SECMPEG
*
*    Version     : 1.0
*    Language    : C
*    For machine : SunOS 4.1.x, INTERACTIVE Unix 2.2.1, Linux, MS-DOS
*    Compile as  : see Makefile
*
*    Authors     : Juergen Meyer, Frank Gadegast
*    Contact     : [e-mail], [e-mail]
*
************************************************************************
*/

#include "defs.h"
#include <stdio.h>
#include <stdlib.h>
#ifdef DOS
#ifdef GNU
  #include <malloc.h>
#else
  #include <alloc.h>
#endif
#else
  #include <malloc.h>
#endif
#include "huff.h"

/* ------ DEFINES ------ */

#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)

/* ------ PUBLIC ------ */

int 	InitHuffman();
void    FreeHuffTables();
INT     Decode(DHUFF *);


/* ------ PRIVAT ------ */

static DHUFF *MakeDhuff();
static void   LoadDTable();
static INT    GetNextState();
static void   AddCode(INT,INT,INT,DHUFF *);

/* ------ IMPORT ------ */
extern int _GetBit();             /* decode.c */


INT huffmantable_count;

extern INT Loud;
extern INT ErrorValue;
extern INT FrameInterval;



INT NumberBitsCoded=0;

DHUFF *MBADHuff            = NULL;
DHUFF *MVDDHuff            = NULL;
DHUFF *CBPDHuff            = NULL;
DHUFF *T1DHuff             = NULL;
DHUFF *T2DHuff             = NULL;
DHUFF *IntraDHuff          = NULL;
DHUFF *PredictedDHuff      = NULL;
DHUFF *InterpolatedDHuff   = NULL;
DHUFF *DCLumDHuff          = NULL;
DHUFF *DCChromDHuff        = NULL;
DHUFF **ModuloDHuff        = NULL;
INT   **MyCoef             = NULL;

int	InitHuffman()
{


    INT i,j,count,largest,smallest,size;
    

#ifdef DEBUG
  fprintf(stderr,"%s : %d\n","init huffmann tables",huffmantable_count++);
#endif

  MBADHuff = MakeDhuff();
  MVDDHuff = MakeDhuff();
  CBPDHuff = MakeDhuff();
  T1DHuff = MakeDhuff();
  T2DHuff = MakeDhuff();
  IntraDHuff = MakeDhuff();
  PredictedDHuff = MakeDhuff();
  InterpolatedDHuff = MakeDhuff();
  DCLumDHuff = MakeDhuff();
  DCChromDHuff = MakeDhuff();

 
  LoadDTable(MBACoeff,MBADHuff);
  LoadDTable(MVDCoeff,MVDDHuff);
  LoadDTable(CBPCoeff,CBPDHuff);
  LoadDTable(TCoeff1,T1DHuff);
  LoadDTable(TCoeff2,T2DHuff);
  LoadDTable(IntraTypeCoeff,IntraDHuff);
  LoadDTable(PredictedTypeCoeff,PredictedDHuff);
  LoadDTable(InterpolatedTypeCoeff,InterpolatedDHuff);
  LoadDTable(DCLumCoeff,DCLumDHuff);
  LoadDTable(DCChromCoeff,DCChromDHuff);


   return(TRUE);
}
void   FreeHuffTables()
{
       if(MBADHuff)          free(MBADHuff);
       if(MVDDHuff)          free(MVDDHuff);
       if(CBPDHuff)          free(CBPDHuff);
       if(T1DHuff)           free(T1DHuff);
       if(T2DHuff)           free(T2DHuff);
       if(IntraDHuff)        free(IntraDHuff);
       if(PredictedDHuff)    free(PredictedDHuff);
       if(InterpolatedDHuff) free(InterpolatedDHuff);
       if(DCLumDHuff)        free(DCLumDHuff);
       if(DCChromDHuff)      free(DCChromDHuff);
       if(ModuloDHuff)       free(ModuloDHuff);

       if(MyCoef)            free(MyCoef);
}


static DHUFF *MakeDhuff()
{

  INT i;
  DHUFF *temp = NULL;

#ifdef HUFF_DEBUG
  fprintf(stderr,"%s\n","make decode-huffman structure");
#endif

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


static void LoadDTable(INT *array,DHUFF *table)
{
#ifdef HUFF_DEBUG
     fprintf(stderr,"%s\n","make decode-huffman table");
#endif

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


static INT GetNextState(DHUFF *huff)
{

#ifdef HUFF_DEBUG
       fprintf(stderr," %s\n","get next state");
#endif
  if (huff->NumberStates==512)
    {
      fprintf(stderr,"Overflow\n");
      error_exit(ERROR_BOUNDS);
    }
  return(huff->NumberStates++);
}


INT Decode(DHUFF *huff)
{

  INT Next,cb;
  INT CurrentState=0;

  while(TRUE)
    {
      cb = (INT)GetBit();
      if (cb)
	{
	  Next =  GetLeft(CurrentState,huff);
	  if (Next == EmptyState)
	  {
#ifdef DEBUG
	      fprintf(stderr,"Invalid State Reached (decode).\n");
#endif
	      error_exit(ERROR_BOUNDS);
	  }
	  else if (Numberp(Next))
	    return(GetHVal(Next));
	  else
	    CurrentState = Next;
	}
      else
	{
	  Next =  GetRight(CurrentState,huff);
	  if (Next == EmptyState)
	  {
#ifdef DEBUG
	      fprintf(stderr,"Invalid State Reached (decode).\n");
#endif
	      error_exit(ERROR_BOUNDS);
	  }
	  else if (Numberp(Next))
	    return(GetHVal(Next));
	  else
	    CurrentState = Next;
	}
    }
}

static void AddCode(INT n,INT code,INT value,DHUFF *huff)
{
  INT i,Next;
  INT CurrentState=0;

#ifdef HUFF_DEBUG
       fprintf(stderr," %s\n","add code");
	      fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
		     n,code,value);
#endif

  if (value < 0)
  {
#ifdef HUFF_DEBUG
      fprintf(stderr,"Negative addcode value: %d\n",value);
#endif
      error_exit(ERROR_BOUNDS);
  }

  for(i=n-1;i>0;i--)
    {
      if (code & (1 << i))
	{
	  Next = GetLeft(CurrentState,huff);
	  if (Next == EmptyState)
	    {
	      Next = GetNextState(huff);
	      SetLeft(Next,CurrentState,huff);
	      CurrentState = Next;
	    }
	  else if (Numberp(Next))
	    {
#ifdef HUFF_DEBUG
	      fprintf(stderr,"Bad Value/State match (L) :\n");
	      fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
		     n,code,value);
#endif
	      error_exit(ERROR_BOUNDS);
	    }
	  else
	    {
	      CurrentState = Next;
	    }
	}
      else
	{
	  Next = GetRight(CurrentState,huff);
	  if (Next == EmptyState)
	    {
	      Next = GetNextState(huff);
	      SetRight(Next,CurrentState,huff);
	      CurrentState = Next;
	    }
	  else if (Numberp(Next))
	    {
#ifdef HUFF_DEBUG
	      fprintf(stderr,"Bad Value/State match: (R) \n");
	      fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
		     n,code,value);
#endif
	      error_exit(ERROR_BOUNDS);
	    }
	  else
	    {
	      CurrentState = Next;
	    }
	}
    }
  if (code & 1)
    {
      Next = GetLeft(CurrentState,huff);

      if (Next != EmptyState)
	{

#ifdef HUFF_DEBUG
	  fprintf(stderr,"Overflow on Huffman Table: Nonunique prefix(L).\n");
	  fprintf(stderr,"Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
#endif
	  error_exit(ERROR_BOUNDS);
	}
      SetLeft(MakeHVal(value),CurrentState,huff);
    }
  else
    {
      Next = GetRight(CurrentState,huff);
    
      if (Next != EmptyState)
	{
#ifdef HUFF_DEBUG
	  fprintf(stderr,"Overflow on Huffman Table: Nonunique prefix(R).\n");
	  fprintf(stderr,"Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
#endif
	  error_exit(ERROR_BOUNDS);
	}
      SetRight(MakeHVal(value),CurrentState,huff);
    }
}