lzwright.c

lzwdechengxu.rar

/*这是“BOOK修改"与“LZW Data Compression”结合的程序，只是前者对后者的变量一些的改了一下，基本上一样，但以后都对此进行修改，理论上应该正确吧~但压缩后比原文件大，可以还原*/
#include "stdio.h"
#include <stdlib.h>
#include <string.h>


#define BITS 12
#define MAX_VALUE ((1<<BITS)-1)
#define MAX_CODE MAX_VALUE-1
#define TABLE_SIZE 5021
#define FIRST_CODE 256
#define UNUSED -1


#ifdef __STDC__
find_child_node(int parent_code,unsigned int child_character);
unsigned int decode_string(unsigned int offset,unsigned int code);
#else
find_child_node();
unsigned int decode_string();
#endif

void *malloc(); 

struct dictionary{
   int code_value;
   unsigned int parent_code;
   unsigned char character;
}dict[TABLE_SIZE];

unsigned char decode_stack[TABLE_SIZE];


InputBits(input,bit)
FILE *input;
int bit;
{
   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-bit);
   input_bit_buffer<<=bit;
   input_bit_count-=bit;
   return(return_value);
}

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

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

find_child_node(parent_code,child_character)
int parent_code;
unsigned int child_character;
{
   int index;
   int 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(index);
      if(dict[index].parent_code==parent_code&&dict[index].character==child_character)
          return(index);
      index-=offset;
      if(index<0)
          index+=TABLE_SIZE;
   }
}

unsigned int decode_string(count,code)
unsigned int count;
unsigned int code;
{   int i=0;
    while(code>255){
         decode_stack[count++]=dict[code].character;
         code=dict[code].parent_code;
         if (i++>=MAX_CODE)
    {
      printf("Fatal error during code expansion.\n");
      exit(0);
    }
    }
    decode_stack[count++]=(char)code;
    return(count);
}

CompressFile(input,output)
FILE *input;
FILE *output;
{  
   unsigned int next_code;
   unsigned int character;
   unsigned int string_code;
   unsigned int index;
   int i;

   next_code=FIRST_CODE;
   for(i=0;i<TABLE_SIZE;i++)
       dict[i].code_value=UNUSED;
   printf("Compressing...\n");
   string_code=getc(input);

   while((character=getc(input))!=(unsigned)EOF)
   {
       index=find_child_node(string_code,character);
       if(dict[index].code_value!=-1)
           string_code=dict[index].code_value;
       else
       {
          if(next_code<=MAX_CODE)
          {
             dict[index].code_value=next_code++;
             dict[index].parent_code=string_code;
             dict[index].character=character;
          }
          OutputBits(output,string_code,BITS);
          string_code=character;
       }
   }
   OutputBits(output,string_code,BITS);
   OutputBits(output,MAX_VALUE,BITS);     
      OutputBits(output,0,BITS);     /*!!!!!!*/
   
   printf("\n");
}

ExpandFile(input,output)
FILE *input;
FILE *output;
{  
   unsigned int next_code;
   unsigned int new_code;
   unsigned int old_code;
   int character;
   int count;

   next_code=FIRST_CODE;
   printf("Expanding...\n");
   old_code=(unsigned int)InputBits(input,BITS);   /*!!!!!!*/
   if(old_code==(MAX_VALUE))
       return;
   character=old_code;
   putc(old_code,output);
   while((new_code=InputBits(input,BITS))!=MAX_VALUE){                        /*&&new_code>=0*/
        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)
            putc(decode_stack[--count],output);
        if(next_code<=MAX_CODE)
        {
            dict[next_code].parent_code=old_code;
            dict[next_code].character=(char)character;
            next_code++;
        }
        old_code=new_code;
  }
  
      printf("\n");
}



main()
{  
   int   choise; 
   int *code_value;
   int *parent_code;
   char *character;
   FILE *infile;
   FILE *outfile;
   char   *infilename,*outfilename;

   infilename=malloc(sizeof(char));
   outfilename=malloc(sizeof(char));
   code_value=malloc(TABLE_SIZE*sizeof(int));
   parent_code=malloc(TABLE_SIZE*sizeof(int));
   character=malloc(TABLE_SIZE*sizeof(char));
   if(code_value==NULL||parent_code==NULL||character==NULL||infilename==NULL||outfilename==NULL)
      {
        printf("Fatal error allocating table space!\n");
        exit(0);
      } 
   printf("\n<1>   for   Compress.\n<2>   for   Expand.\n<0>   for   Exit!\n   ");
    printf("Please   Input   Your   Choise:");
    scanf("%d",&choise);
    if(choise==1)
{
  printf("\nPlease   Input   The   Compressing   File   Name:");
  scanf("%s",infilename);
  if((infile=fopen(infilename,"rb"))==NULL)
  {printf("Cannot   open   the   %s   file!\n",infilename);exit(1);}
  printf("\nPlease   Input   The   Name   for   the   Compressed   File:");
  scanf("%s",outfilename);
  if((outfile=fopen(outfilename,"wb"))==NULL)
  {printf("Cannot   open   the   %s   file!\n",outfilename);exit(1);}
  CompressFile(infile,outfile);
  fclose(infile);
  fclose(outfile);
  free(code_value);
}
    else   if(choise==2)
{
  printf("\nPlease   Input   THe   Expanding   File   Name:");
  scanf("%s",infilename);
  if((infile=fopen(infilename,"rb"))==NULL)
  {printf("Cannot   open   the   %s   file!\n",infilename);exit(1);}
  printf("\nPlease   INput   the   Name   for   THe   Expanded   File:");
  scanf("%s",outfilename);
  if((outfile=fopen(outfilename,"wb"))==NULL)
  {printf("Cannot   open   the   %s   file!\n",outfilename);exit(1);}
  ExpandFile(infile,outfile);
  fclose(infile);
  fclose(outfile);
  free(parent_code);
  free(character);
}
    else   exit(1);
}