chcode.h

用于数据流压缩的huffman算法源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BITS            15
#define MAX_CODE        ( ( 1<<BITS )-1 )
#define TABLE_SIZE      35023l
#define TABLE_BANKS     ( ( TABLE_SIZE>>8 )+1 )
#define END_OF_STREAM   256
#define BUMP_CODE       257
#define FLUSH_CODE      258
#define FIRST_CODE      259
#define UNUSED          -1
#define PACIFIER_COUNT  2047

/*long  array[128]={6,33,34,35,36,37,38,39,5,41,42,43,44,45,46,47,
//		48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,7,65,66,67,
//		68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,
//		88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,
//		106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,
//		121,122,123,124,125,126,127,3,129,130,131,132,133,134,4,
//		136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,
//		151,152,153,154,155,156,157,158,159};
*/long  array[64]={48,49,50,51,52,53,54,55,56,57,
                    65,66,67,68,69,70,71,72,73,74,75,76,
                    77,78,79,80,81,82,83,84,85,86,87,88,89,90,
                    97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,
                    117,118,119,120,121,122,40,41};


struct dictionary{
   long  code_value;
   long  parent_code;
   char character;
   } * dict[TABLE_BANKS];

typedef struct bit_stream{
  unsigned char mask;
  long  rack;
  long  pacifier_counter;
  }BIT_STREAM;

void InitializeDictionary();
void InitializeStorage();
unsigned long  find_child_node( long  parent_code,long  child_character );
unsigned long  decode_string( unsigned long  offset,unsigned long  code );

void OutputBits( BIT_STREAM * bit_stream,
                 unsigned long code,
                 long  count,
                 unsigned char * outstream,
                 long * flag );
unsigned long InputBits( BIT_STREAM  * bit_stream,
                         long bit_count,
			 unsigned char * instream,
			 long length,
                         long * flag );

long code( unsigned char * instream,long length,unsigned char * outstream );
long uncode( unsigned char * instream,long length,unsigned char * outstream );

BIT_STREAM * OpenOutputBitStream( void );
BIT_STREAM * OpenInputBitStream( void );

void CompressStream( BIT_STREAM * output,
		   unsigned char * instream,
		   long length,
		   unsigned char * outstream ,
                   long * flag);
long ExpandStream( BIT_STREAM * input,
                   unsigned char * instream,
                   long length,
                   unsigned char * outstream);
long compress_code( unsigned char * instream,long length );
long uncode_expand( unsigned char * instream,long length );

#define DICT(i) dict[i>>8][i&0xff]

char decode_stack[TABLE_SIZE];
unsigned long  next_code;
long  current_code_bits;
unsigned long  next_bump_code;


long compress_code( unsigned char * instream,long length )
{
  BIT_STREAM * output;
  unsigned char * outstream,* copy_outstream;
  unsigned char * mediastream,* copy_mediastream;
  long * flag,i;
  if(length==0) return(length);  
  outstream=(unsigned char *)malloc(2*length+1);
  copy_outstream=outstream;
  mediastream=(unsigned char *)malloc(2*length);
  copy_mediastream=mediastream;
  flag=(long *)malloc(8);
  *flag=0;
  setbuf( stdout,NULL );
  output=OpenOutputBitStream();
  CompressStream( output,instream,length,outstream,flag );
  for( i=1l;i<=*flag;i++ )  * mediastream++=*outstream++;
  mediastream-=*flag;
  outstream-=*flag;
  length=code( mediastream,*flag,outstream );
  for( i=1l;i<=length;i++ ) *instream++=*outstream++;
  *instream='\0';
  instream-=length;
  outstream-=length;
  free((unsigned char *)copy_outstream);
  free((unsigned char *)copy_mediastream);
  free((long *)flag);
  free((BIT_STREAM *)output);
  return(length);
}

void InitializeDictionary()
{
  unsigned long  i;

  for( i=0;i<TABLE_SIZE;i++ )
       DICT(i).code_value=UNUSED;
  next_code=FIRST_CODE;
  current_code_bits=9;
  next_bump_code=511;
}

void InitializeStorage()
{
  long  i;

  for( i=0;i<TABLE_BANKS;i++ )
       dict[i]=( struct dictionary * )calloc( 256,sizeof( struct dictionary ) );
  return;
}

void CompressStream( BIT_STREAM * output,
                     unsigned char * instream,
                     long length,
                     unsigned char * outstream,
                     long * flag)
{
  long  character;
  long  string_code;
  unsigned long  index;
  long i,j,k;


  InitializeStorage();
  InitializeDictionary();
  string_code=*instream; instream++;
  for( i=1l;i<=(length+1);i++ ){
         character= * instream;
         if(i==length) character=13;
         if(i==(length+1)) character=10;
         instream++;
         index=find_child_node( string_code,character );
         if( DICT( index ).code_value!=-1 )
             string_code=DICT( index ).code_value;
          else {
             DICT( index ).code_value=next_code++;
             DICT( index ).parent_code=string_code;
             DICT( index ).character=( char )character;
             j=*flag;
             OutputBits( output,( unsigned long )string_code,
                         current_code_bits,outstream,flag );
             for( k=1l;k<=(*flag-j);k++ ) *outstream++;
             string_code=character;
             if( next_code>MAX_CODE ) {
                 j=*flag;
                 OutputBits( output,( unsigned long )FLUSH_CODE,
                             current_code_bits,outstream,flag );
                 for( k=1l;k<=(*flag-j);k++ ) *outstream++;
                 InitializeDictionary();
               }
             else if( next_code>next_bump_code ){
                      j=*flag;
                      OutputBits( output,( unsigned long )BUMP_CODE,
                                  current_code_bits,outstream,flag);
                      for( k=1l;k<=(*flag-j);k++ ) *outstream++;
                      current_code_bits++;
                      next_bump_code<<=1;
                      next_bump_code|=1;

                  }
               }
              }
  j=*flag;
  OutputBits( output,( unsigned long )string_code,
              current_code_bits,outstream,flag );
  for( k=1l;k<=(*flag-j);k++ ) *outstream++;
  OutputBits( output,( unsigned long )END_OF_STREAM,
              current_code_bits,outstream,flag );
  for( k=0;k<TABLE_BANKS;k++ )
      free( (struct dictionary *) dict[k] );
}

unsigned long  find_child_node( long  parent_code,long  child_character )
{
  unsigned long  index;
  long  offset;

  index=( child_character<<( BITS-8 ) )^parent_code;
  if( index==0 )
      offset=1;
  else
      offset=TABLE_SIZE-index;
  for( ; ; ) {
       if( DICT( index ).code_value==UNUSED )
           return( ( unsigned long  )index );
       if( DICT( index ).parent_code==parent_code &&
           DICT( index ).character==( char )child_character )
           return( index );
       if( ( long  )index>=offset )
           index-=offset;
       else
           index+=TABLE_SIZE-offset;
       }
}


unsigned long  decode_string( unsigned long  count,unsigned long  code )
{
  while( code>256 ){
         decode_stack[count++]=DICT( code ).character;
         code=DICT( code ).parent_code;
         }
  decode_stack[count++]=( char )code;
  return( count );
}

void OutputBits( BIT_STREAM * bit_stream,unsigned long code,long  count,
                 unsigned char * outstream,long * flag )
{
  unsigned long mask;

  mask=1l<<( count-1 );
  while( mask!=0 ) {
     if( mask & code )
         bit_stream->rack|=bit_stream->mask;
     bit_stream->mask>>=1;
     if( bit_stream->mask==0 )  {
          * outstream=(unsigned char)(bit_stream->rack);
		  (*flag)++;
          outstream++;
          if( ( bit_stream->pacifier_counter++ & PACIFIER_COUNT )==0 );

         bit_stream->rack=0;
         bit_stream->mask=0x80;
        }
     mask >>= 1;
  }
}


BIT_STREAM * OpenOutputBitStream( )
{
  BIT_STREAM * bit_stream;

  bit_stream=( BIT_STREAM * )calloc( 1,sizeof( BIT_STREAM ) );
  if( bit_stream==NULL )
    return( bit_stream );
  bit_stream->rack=0;
  bit_stream->mask=0x80;
  bit_stream->pacifier_counter=0;
  return( bit_stream );
}

long  code( unsigned char * mediastream,
           long length,unsigned char * outstream )
{

  unsigned char rackin,rackout,out_char;
  long  i,j,flag;
  short mask;
  long number;
  unsigned char bit[8];


  if( length/3*3==length ) number=length*8/6;
  else number=(length*8/6+1);
  flag=2;
  for( i=1l;i<=number;i++ ){
          if( flag==10 ) flag=2;
	  mask=0x01;
          rackout=0;
          if( (flag==8)||(i==number) ) rackin=0;
          else{ rackin=* mediastream;
                mediastream++; }
	  rackout=(rackin>>flag);
          for( j=(9-flag);j<=6;j++ )
               rackout |= bit[j];
          out_char=(unsigned char)(array[rackout]);
          *outstream++=out_char;
          for( j=(7-flag);j<=6;j++ ){
               bit[j]=rackin & mask;
               bit[j]<<=(6-flag);
	       mask<<=1;}
          flag+=2;
         }
  return( number );
}

long uncode_expand( unsigned char * instream,long length )
{
  BIT_STREAM * input;
  unsigned char * outstream,* copy_outstream;
  unsigned char * mediastream,* copy_mediastream;
  long i;
  if(length==0) return(length);  
  outstream=(unsigned char *)malloc(4*length);
  copy_outstream=outstream;
  mediastream=(unsigned char *)malloc(2*length);
  copy_mediastream=mediastream;
  setbuf( stdout,NULL );
  input=OpenInputBitStream( );
  length=uncode( instream,length,outstream);
  for( i=1l;i<=length;i++ ) *mediastream++=*outstream++;
  mediastream-=length;
  outstream-=length;
  length=ExpandStream( input,mediastream,length,outstream);
  for( i=1l;i<=length;i++ ) *instream++=*outstream++;
  *instream='\0';
  instream-=length;
  outstream-=length;
  free((unsigned char *)copy_outstream );
  free((unsigned char *)copy_mediastream);
  free((BIT_STREAM *)input);
  return( length-2);
}


long ExpandStream( BIT_STREAM * input,unsigned char * instream,long length,
                   unsigned char * outstream )
{
  unsigned long new_code;
  unsigned long old_code;
  long character;
  unsigned long count;
  long k,j,ff=0;
  long * flag;

  flag=(long *)malloc(sizeof(long));
  *flag=0l;
  InitializeStorage();
  for( ; ; ) {
        InitializeDictionary();
        k=*flag;
        old_code=( unsigned long )InputBits( input,current_code_bits,
                                 instream,length,flag );
        for( j=1l;j<=(*flag-k);j++ ) instream++;
        /*************/
        if( old_code==(unsigned long)(length|0x10000000) )  return( ff );
        /*************/
        if( old_code==END_OF_STREAM )
            { instream-=*flag;free((long*)flag); return( ff );}
        character=old_code;
        *outstream++=(unsigned char)(character);ff++;
        for( ; ; ) {
             k=*flag;
             new_code=( unsigned long )InputBits( input,current_code_bits ,
                                         instream,length,flag );
             for( j=1l;j<=(*flag-k);j++ ) instream++;
        /*************/
        if( new_code==(unsigned long)(length|0x10000000) )
		   { return(ff);}
        /*************/
        if( new_code==END_OF_STREAM )
            { instream-=*flag;free((long *)flag); return( ff );}
        if( new_code==FLUSH_CODE )
            break;
        if( new_code==BUMP_CODE ) {
            current_code_bits++;
            continue;
        }
        if( new_code>=next_code ) {
            decode_stack[0]=( char )character;
            count=decode_string( 1,old_code );
            }
        else
            count=decode_string( 0,new_code );
        character=decode_stack[count-1];
        while( count>0 )
             {  * outstream++=decode_stack[--count];ff++;}

        DICT( next_code ).parent_code=old_code;
        DICT( next_code ).character=( char )character;
        next_code++;
        old_code=new_code;
        }
     }
}


unsigned long InputBits( BIT_STREAM * bit_stream,long bit_count,
			 unsigned char * instream,long length,long * flag )
{
  unsigned long mask;
  unsigned long return_value;

  mask=1l<<( bit_count-1 );
  return_value=0;
  while( mask!=0 ) {
     if( bit_stream->mask==0x80 ) {
         bit_stream->rack=* instream++; (*flag)++;
         /****************/
         if( *flag==length ) return( length|0x10000000 );
         /****************/
         if( ( bit_stream->pacifier_counter++ & PACIFIER_COUNT )==0 );
         }
     if( bit_stream->rack & bit_stream->mask )
         return_value|=mask;
     mask>>=1;
     bit_stream->mask>>=1;
     if( bit_stream->mask==0 )
         bit_stream->mask=0x80;
   }
  return( return_value );
}

BIT_STREAM * OpenInputBitStream( )
{
  BIT_STREAM * bit_stream;

  bit_stream=( BIT_STREAM * )calloc( 1,sizeof( BIT_STREAM ) );
  if( bit_stream==NULL )
    return( bit_stream );
  bit_stream->rack=0;
  bit_stream->mask=0x80;
  bit_stream->pacifier_counter=0;
  return( bit_stream );
}

long uncode( unsigned char * instream,long length,unsigned char * outstream )
{
  unsigned char rackin;
  unsigned char rackout;
  short mask;
  long j,flag;
  unsigned char bit[8];
  long i,k=0;
  
  for( i=1l;i<=length;i++ ){
       rackin=* instream++;
       for( j=0;j<=63;j++ )
	    if( array[j]==rackin )  break;
       rackin=(unsigned char)(j);
       rackout=( rackin<<2 ) ;
       for( flag=1;flag<=5;flag+=2 ){
            mask=0x20;
	    rackin=*instream++;
            i++;if(i>length) break;
            for( j=0;j<=63;j++ )
		 if( array[j]==rackin ) break;
            rackin=(unsigned char)(j);
            for( j=flag;j>=0;j-- ){
                 bit[j]=rackin & mask;
                 bit[j]>>=(5-flag);
                 rackout |= bit[j];
                 mask>>=1;
                 }
       
       *outstream++=rackout; k++;
       rackout=( rackin<<(flag+3) );
       }
  }
  * outstream++=0xfe;k+=1;
  return( k );
}