www.pudn.com > HuffmanForFile.zip > CHCODE.C
#include
#include
#include
#define BITS 15
#define MAX_CODE ( ( 1<>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
/*short 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};
*/short array[128]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,
17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,
37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,
57,58,59,60,61,62,63,64,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,128};
struct dictionary{
short code_value;
short parent_code;
char character;
} * dict[TABLE_BANKS];
typedef struct bit_stream{
unsigned char mask;
short rack;
short pacifier_counter;
}BIT_STREAM;
void InitializeDictionary();
void InitializeStorage();
unsigned short find_child_node( short parent_code,short child_character );
unsigned short decode_string( unsigned short offset,unsigned short code );
void OutputBits( BIT_STREAM * bit_stream,
unsigned long code,
short count,
unsigned char * outstream,
long * flag );
unsigned long InputBits( BIT_STREAM * bit_stream,
short 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 short next_code;
short current_code_bits;
unsigned short 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;
/* 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-=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 short i;
for( i=0;iMAX_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=offset )
index-=offset;
else
index+=TABLE_SIZE-offset;
}
}
unsigned short decode_string( unsigned short count,unsigned short 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,short 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;
short i,j,flag,mask;
long number;
unsigned char bit[8];
if( length/7*7==length ) number=length*8/7;
else number=length*8/7+1;
flag=1;
for( i=1;i<=number;i++ ){
if( flag==9 ) flag=1;
mask=0x01;
rackout=0;
if( (flag==8)||(i==number) ) rackin=0;
else{ rackin=* mediastream;
mediastream++; }
rackout=(rackin>>flag);
for( j=(8-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]<<=(7-flag);
mask<<=1;}
flag++;
}
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;
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-=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 short new_code;
unsigned short old_code;
short character;
unsigned short count;
long k,j,ff=0;
long * flag;
flag=(long *)malloc(sizeof(long));
*flag=0l;
InitializeStorage();
for( ; ; ) {
InitializeDictionary();
k=*flag;
old_code=( unsigned short )InputBits( input,current_code_bits,
instream,length,flag );
for( j=1l;j<=(*flag-k);j++ ) instream++;
/*************/
if( old_code==length ) 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 short )InputBits( input,current_code_bits ,
instream,length,flag );
for( j=1l;j<=(*flag-k);j++ ) instream++;
/*************/
if( new_code==length ) 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,short 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 );
/****************/
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;
short j,flag;
unsigned char bit[8];
long i,k=0;
for( i=1l;i<=length;i++ ){
rackin=* instream++;
for( j=0;j<=127;j++ )
if( array[j]==rackin ) break;
rackin=(unsigned char)(j);
rackout=( rackin<<1 ) ;
for( flag=0;flag<=6;flag++ ){
mask=0x40;
rackin=*instream++;
i++;if(i>length) break;
for( j=0;j<=127;j++ )
if( array[j]==rackin ) break;
rackin=(unsigned char)(j);
for( j=flag;j>=0;j-- ){
bit[j]=rackin & mask;
bit[j]>>=(6-flag);
rackout |= bit[j];
mask>>=1;
}
*outstream++=rackout; k++;
rackout=( rackin<<(flag+2) );
}
}
* outstream++=0xfe;k+=1;
return( k );
}