zipex.h

本程序是基于Hufuman编码压缩算法的成熟代码实现

/***********************************************************************/
/* 本程序是基于Hufuman编码压缩算法的实现 作者: 王新华          */
/***********************************************************************/

#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 NOUSED1          -1
#define PACIFIER_COUNT  2047

#define MAXDATALEN      5242880   //设置最大数据流的长度,这里设为5M


/****************************************************************/
/*                数据结构定义                                  */
/****************************************************************/

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( unsigned char * instream,long length );
long uncompress( 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;


/****************************************************************/
/*                       函数实现                               */
/****************************************************************/

/***********************************************
  compress函数说明
  功能：      
  对数据流进行压缩编码

  参数说明:
  instream    --- 需要压缩的源数据所在缓存区的首地址,压缩后数据也放在该缓存区中

  返回值:
  压缩后数据的长度
**********************************************/


long compress( 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);
}


/***********************************************
  uncompress函数说明
  功能：      
  对数据流进行解压缩编码

  参数说明:
  instream    --- 需要解压缩的源数据所在缓存区的首地址,解压缩后数据也放在该缓存区中

  返回值:
  解压缩后数据的长度
**********************************************/

long uncompress( 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+MAXDATALEN);
  copy_outstream=outstream;
  mediastream=(unsigned char *)malloc(2*length);
  copy_mediastream=mediastream;
  setbuf( stdout,NULL );
  input=OpenInputBitStream( );
  length=uncode( instream,length,outstream);
 // free(instream);
  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);
  
  //释放在expandstream中为分配的内存

  for( int k1=0;k1<TABLE_BANKS;k1++ )
      free( (struct dictionary *) dict[k1] );

  return( length-2);
}


void InitializeDictionary()
{
  unsigned long  i;

  for( i=0;i<TABLE_SIZE;i++ )
       DICT(i).code_value=NOUSED1;
  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;