lzw.c

经典的LZW77编码

#include <stdio.h>
#include <malloc.h>

#define INIT_BITS 9
#define MAX_BITS  14           
#define HASHING_SHIFT MAX_BITS - 8

#if MAX_BITS == 14            
#define TABLE_SIZE 18041      
#elif MAX_BITS == 13
#define TABLE_SIZE 9029
#else
#define TABLE_SIZE 5021
#endif

#define CLEAR_TABLE 256   
#define TERMINATOR  257    
#define FIRST_CODE  258    
#define CHECK_TIME  100    

#define MAXVAL(n) (( 1 <<( n )) -1)   

unsigned input_code();
void *malloc();

int *code_value;                      
unsigned int *prefix_code;            
unsigned char *append_character;      
unsigned char decode_stack[4000];     

int num_bits=INIT_BITS;               
unsigned long bytes_in=0,bytes_out=0; 
int max_code;                         
unsigned long checkpoint=CHECK_TIME;  

main(int argc, char *argv[])
{
   FILE *input_file, *output_file, *lzw_file;
   char input_file_name[81];

   code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
   prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
   append_character=malloc(TABLE_SIZE*sizeof(unsigned char));

   if (code_value==NULL || prefix_code==NULL || append_character==NULL) {
      printf("Error allocating table space!\n");
      exit(1);
   }

   if (argc>1)
      strcpy(input_file_name,argv[1]);
   else {
      printf("Input file name: ");
      scanf("%s",input_file_name);
   }
   input_file=fopen(input_file_name,"rb");

   lzw_file=fopen("test.lzw","wb");
   if (input_file == NULL || lzw_file == NULL) {
      printf("Error opening files\n");
      exit(1);
   }
   max_code = MAXVAL(num_bits);    
   compress(input_file,lzw_file);       

   fclose(input_file);
   fclose(lzw_file);
   free(code_value);                   

   lzw_file=fopen("test.lzw","rb");
   output_file=fopen("test.out","wb");
   if (lzw_file == NULL || output_file == NULL) {
      printf("Error opening files\n");
      exit(1);
   }
   num_bits=INIT_BITS;                  
   max_code = MAXVAL(num_bits);
   expand(lzw_file,output_file);        

   fclose(lzw_file);                    
   fclose(output_file);
   free(prefix_code);
   free(append_character);
}

compress(FILE *input, FILE *output)
{
   unsigned int next_code=FIRST_CODE;
   unsigned int character;
   unsigned int string_code;
   unsigned int index;
   int i,             
   ratio_new,         
   ratio_old=100;    

   for (i=0;i<TABLE_SIZE;i++)   
      code_value[i]=-1;
   printf("Compressing\n");
   string_code=getc(input);    


   while((character=getc(input)) != (unsigned)EOF) {
      if (!(++bytes_in % 1000)) {    
//      putchar('.');
      }
      index=find_match(string_code,character);
      if (code_value[index] != -1)
         string_code=code_value[index];
      else {
         if (next_code <= max_code ) {
            code_value[index]=next_code++;
            prefix_code[index]=string_code;
            append_character[index]=character;
         }
         output_code(output,string_code);   
         string_code=character;
         if (next_code > max_code) {      
            if ( num_bits < MAX_BITS) {    
         //     putchar('+');
               max_code = MAXVAL(++num_bits);  
            }
            else if (bytes_in > checkpoint) {         
               if (num_bits == MAX_BITS ) {
                ratio_new = bytes_out*100/bytes_in; 
                if (ratio_new > ratio_old) {        
                  output_code(output,CLEAR_TABLE); 
               //   putchar('C');
                  num_bits=INIT_BITS;
                  next_code=FIRST_CODE;        
                  max_code = MAXVAL(num_bits); 
                  bytes_in = bytes_out = 0;
                  ratio_old=100;               
                  for (i=0;i<TABLE_SIZE;i++)   
                        code_value[i]=-1;
               }
               else                                
               ratio_old = ratio_new;           
            }
            checkpoint = bytes_in + CHECK_TIME;    
            }
         }
      }
   }
   output_code(output,string_code);   
   if (next_code == max_code) {       
      ++num_bits;                   
//      putchar('+');
   }
   output_code(output,TERMINATOR);    
   output_code(output,0);             
   output_code(output,0);
   output_code(output,0);
   putchar('\n');
}


find_match(int hash_prefix, unsigned int hash_character)
{
   int index, offset;

   index = (hash_character << HASHING_SHIFT ) ^ hash_prefix;
   if (index == 0 )
      offset=1;
   else
      offset = TABLE_SIZE - index;
   while(1) {
      if (code_value[index] == -1 )
         return(index);
      if (prefix_code[index] == hash_prefix && 
                                     append_character[index] == hash_character)
         return(index);
      index -= offset;
      if (index < 0)
         index += TABLE_SIZE;
   }
}

expand(FILE *input, FILE *output)
{
   unsigned int next_code=FIRST_CODE;
   unsigned int new_code;
   unsigned int old_code;
   int character,
   counter=0,
   clear_flag=1;         
   unsigned char *string;
   char *decode_string(unsigned char *buffer, unsigned int code);

   printf("Expanding\n");

   while((new_code=input_code(input)) != TERMINATOR) {
      if (clear_flag) {      
         clear_flag=0;
         old_code=new_code;   
         character=old_code;
         putc(old_code,output);
         continue;
      }
      if (new_code == CLEAR_TABLE) {     
         clear_flag=1;
         num_bits=INIT_BITS;
         next_code=FIRST_CODE;
//         putchar('C');
         max_code = MAXVAL(num_bits);
         continue;
      }
      if (++counter == 1000) {          
         counter=0;
//         putchar('.');
      }
      if (new_code >= next_code) {       
         *decode_stack=character;
         string=decode_string(decode_stack+1,old_code);
      }
      else
         string=decode_string(decode_stack,new_code);

      character = *string;              
      while (string >= decode_stack)
         putc(*string--,output);

      if (next_code <= max_code) {     
         prefix_code[next_code]=old_code;
         append_character[next_code++]=character;
         if (next_code == max_code && num_bits < MAX_BITS) {
        //    putchar('+');
            max_code = MAXVAL(++num_bits);
         }
      }
      old_code=new_code;
   }
//   putchar('\n');
}

char *decode_string(unsigned char *buffer, unsigned int code)
{
   int i=0;

   while(code > 255 ) {
      *buffer++ = append_character[code];
      code=prefix_code[code];
      if (i++ >= 4000 ) {
         printf("Error during code expansion\n");
         exit(1);
      }
   }
   *buffer=code;
   return(buffer);
}


unsigned input_code(FILE *input)
{
   unsigned int return_value;
   static int input_bit_count=0;
   static unsigned long input_bit_buffer=0L;

   while (input_bit_count <= 24 ) {
     input_bit_buffer |= (unsigned long) getc(input) << (24 - input_bit_count);
     input_bit_count += 8;
   }
   return_value=input_bit_buffer >> (32-num_bits);
   input_bit_buffer <<= num_bits;
   input_bit_count -= num_bits;
   return(return_value);
}

output_code(FILE *output, unsigned int code)
{
   static int output_bit_count=0;
   static unsigned long output_bit_buffer=0L;

   output_bit_buffer |= (unsigned long) code << (32 - num_bits - 
                                                             output_bit_count);
   output_bit_count += num_bits;
   while (output_bit_count >= 8) {
      putc(output_bit_buffer >> 24, output);
      output_bit_buffer <<= 8;
      output_bit_count -= 8;
      bytes_out++;                  
   }
}