/* File: codlzw.c   Author: David Bourgin   Creation date: 25/3/95   Last update: 12/10/95   Purpose: Example of LZW encoding with a file source to compress.*/#include <stdio.h>/* For routines printf,fgetc and fputc. */#include <malloc.h>/* For routines malloc and free. */#include <stdlib.h>/* For routine exit. *//* Error codes returned to the caller. */#define NO_ERROR       0#define BAD_FILE_NAME  1#define BAD_ARGUMENT   2#define BAD_MEM_ALLOC  3/* Useful constants. */#define FALSE 0#define TRUE  1/* Global variables. */FILE *source_file,*dest_file;                             /* Being that fgetc=EOF only after an access                                then 'byte_stored_status' is 'TRUE' if a byte has been stored by 'fgetc'                                or 'FALSE' if there's no valid byte not handled in 'val_byte_stored' */int byte_stored_status=FALSE;int byte_stored_val;/* Pseudo procedures */#define end_of_data()  (byte_stored_status?FALSE:!(byte_stored_status=((byte_stored_val=fgetc(source_file))!=EOF)))#define read_byte()  (byte_stored_status?byte_stored_status=FALSE,(unsigned char)byte_stored_val:(unsigned char)fgetc(source_file))#define write_byte(byte)  ((void)fputc((byte),dest_file))unsigned long int val_to_read=0,                  val_to_write=0;unsigned char bit_counter_to_read=0,              bit_counter_to_write=0;typedef struct s_dic_val { unsigned int character;                           unsigned int code;                           struct s_dic_val *left_ptr,                                            *right_ptr;                         } t_dic_val,*p_dic_val;#define CHAR_DIC_VAL(ptr_dic)  ((*(ptr_dic)).character)#define CODE_DIC_VAL(ptr_dic)  ((*(ptr_dic)).code)#define PLEFT_DIC_VAL(ptr_dic)  ((*(ptr_dic)).left_ptr)#define PRIGHT_DIC_VAL(ptr_dic)  ((*(ptr_dic)).right_ptr)#define TYPE_GIF_ENCODING/* Enforces including marker codes initialization_code et end_information_code.   To invalid this option, set the line #define... in comments. */unsigned int index_dic;/* Word counter already known in the dictionary. */unsigned char bit_counter_encoding;/* Bit counter in the encoding. */#define EXP2_DIC_MAX  12/* 2^EXP2_DIC_MAX gives the maximum word counter in the dictionary during *all* the compressions.   Possible values: 3 to 25.   Attention: Beyond 12, you can have some errors of memory allocation   depending on your compiler and your computer. */unsigned int index_dic_max;/* index_dic_max gives the maximum word counter in the dictionary during *one* compression.   This constant is restricted to the range of end_information_code to 2^EXP2_DIC_MAX. */unsigned char input_bit_counter,/* Bit counter for each data in input.   With input_bit_counter=1, we can compress/decompress monochrome pictures   and with input_bit_counter=8, we can handle 256-colors pictures or any kind of files. */              bit_counter_min_encoding;/* Bit counter to encode 'initialization_code'. */unsigned int initialization_code;unsigned int end_information_code;/* initialization_code and end_information_code are both consecutive   coming up just after the last known word in the initial dictionary. */p_dic_val dictionary[1<<EXP2_DIC_MAX];void init_dictionary1()/* Returned parameters: None.   Action: First initialization of the dictionary when we start an encoding.   Errors: None if there is enough room.*/{ register unsigned int i;  index_dic_max=1<<12;       /* Attention: Possible values: 2^3 to 2^EXP2_DIC_MAX. */  input_bit_counter=8;       /* Attention: Possible values: 1 to EXP2_DIC_MAX-1                                (usually, for pictures, set up to 1, or 4, or 8, in the case                                of monochrome, or 16-colors, or 256-colors picture). */  if (input_bit_counter==1)     bit_counter_min_encoding=3;  else bit_counter_min_encoding=input_bit_counter+1;  initialization_code=1<<(bit_counter_min_encoding-1);#ifdef TYPE_GIF_ENCODING  end_information_code=initialization_code+1;#else  end_information_code=initialization_code-1;#endif  for (i=0;i<=end_information_code;i++)      { if ((dictionary[i]=(p_dic_val)malloc(sizeof(t_dic_val)))==NULL)           { while (i)             { i--;               free(dictionary[i]);             }             exit(BAD_MEM_ALLOC);           }        CHAR_DIC_VAL(dictionary[i])=i;        CODE_DIC_VAL(dictionary[i])=i;        PLEFT_DIC_VAL(dictionary[i])=NULL;        PRIGHT_DIC_VAL(dictionary[i])=NULL;      }  for (;i<index_dic_max;i++)      dictionary[i]=NULL;  index_dic=end_information_code+1;  bit_counter_encoding=bit_counter_min_encoding;}void init_dictionary2()/* Returned parameters: None.   Action: Initialization of the dictionary during the encoding.   Errors: None.*/{ register unsigned int i;  for (i=0;i<index_dic_max;i++)      { PLEFT_DIC_VAL(dictionary[i])=NULL;        PRIGHT_DIC_VAL(dictionary[i])=NULL;      }  index_dic=end_information_code+1;  bit_counter_encoding=bit_counter_min_encoding;}void remove_dictionary()/* Returned parameters: None.   Action: Removes the dictionary used for the decoding from the dynamical memory.   Errors: None.*/{ register unsigned int i;  for (i=0;(i<index_dic_max)&&(dictionary[i]!=NULL);i++)      free(dictionary[i]);}p_dic_val find_node(current_node,symbol)/* Returned parameters: Returns a node in the tree of the dictionary.   Action: Looks for 'symbol' from 'current_node'.   This research is made from the left pointer of 'current_node'   (if the left pointer wasn't equal to NULL) and then move to all the right   pointers until we reach the node containing 'symbol' or the last node which   right pointer is NULL.   Errors: If the symbol has not been found out, (current_node=returned node) or (CHAR_DIC_VAL(returned node)#symbol).   The 'current_node' given to this routine must never be equal to NULL.*/p_dic_val current_node;unsigned int symbol;{ p_dic_val new_node;  if (PLEFT_DIC_VAL(current_node)==NULL)     return current_node;  else { new_node=PLEFT_DIC_VAL(current_node);         while ((CHAR_DIC_VAL(new_node)!=symbol)&&(PRIGHT_DIC_VAL(new_node)!=NULL))               new_node=PRIGHT_DIC_VAL(new_node);         return new_node;       }}void add_node(current_node,new_node,symbol)/* Returned parameters: None.   Action: Creates a new_node in the tree of dictionary.   The summoning of this routine is normally done after a call to to find_node.   Errors: None.*/p_dic_val current_node,new_node;unsigned int symbol;{ if (dictionary[index_dic]==NULL)     { if ((dictionary[index_dic]=(p_dic_val)malloc(sizeof(t_dic_val)))==NULL)          { remove_dictionary();            exit(BAD_MEM_ALLOC);          }       CODE_DIC_VAL(dictionary[index_dic])=index_dic;       PLEFT_DIC_VAL(dictionary[index_dic])=NULL;       PRIGHT_DIC_VAL(dictionary[index_dic])=NULL;     }  CHAR_DIC_VAL(dictionary[index_dic])=symbol;  if (current_node==new_node)     PLEFT_DIC_VAL(new_node)=dictionary[index_dic];  else PRIGHT_DIC_VAL(new_node)=dictionary[index_dic];  index_dic++;  if (index_dic==(1 << bit_counter_encoding))     bit_counter_encoding++;}#define dictionary_sature()  (index_dic==index_dic_max)void write_code_lr(value)/* Returned parameters: None.   Action: Sends the value coded on 'bit_counter_encoding' bits in the stream of output codes.   The bits are stored from right to left. Example: aaabbbbcccc is written:   Bits     7 6 5 4 3 2 1 0   Byte 1   a a a b b b b c   Byte 2   c c c ? ? ? ? ?   Errors: An input/output error could disturb the running of the program.*/unsigned int value;{ val_to_write=(val_to_write << bit_counter_encoding) | value;  bit_counter_to_write += bit_counter_encoding;  while (bit_counter_to_write>=8)        { bit_counter_to_write -= 8;          write_byte((unsigned char)(val_to_write >> bit_counter_to_write));          val_to_write &= ((1<< bit_counter_to_write)-1);        }}void complete_encoding_lr()/* Returned parameters: None.   Action: Adds 0-bits to the last byte to write, if any.   This procedure is to be considered with the procedure write_code_lr.   Errors: An input/output error could disturb the running of the program.*/{ if (bit_counter_to_write>0)     write_byte((unsigned char)(val_to_write << (8-bit_counter_to_write)));  val_to_write=bit_counter_to_write=0;}void write_code_rl(value)/* Returned parameters: None.   Action: Sends the value coded on 'bit_counter_encoding' bits in the stream of output codes.   The bits are stored from right to left. Example: aaabbbbcccc is written:   Bits     7 6 5 4 3 2 1 0   Byte 1   c b b b b a a a   Byte 2   ? ? ? ? ? c c c   Errors: An input/output error could disturb the running of the program.*/unsigned int value;{ val_to_write |= ((unsigned long int)value) << bit_counter_to_write;  bit_counter_to_write += bit_counter_encoding;  while (bit_counter_to_write>=8)        { bit_counter_to_write -= 8;          write_byte((unsigned char)(val_to_write&0xFF));          val_to_write = (val_to_write>>8)&((1<< bit_counter_to_write)-1);        }}void complete_encoding_rl()/* Returned parameters: None.   Action: Adds 0-bits to the last byte to write, if any.   This procedure is to be considered with the procedure write_code_rl.   Errors: An input/output error could disturb the running of the program.*/{ if (bit_counter_to_write>0)     write_byte((unsigned char)val_to_write);  val_to_write=bit_counter_to_write=0;}unsigned int read_input()/* Returned parameters: None.   Action: Reads input_bit_counter via the function 'read_byte'.   Errors: An input/output error could disturb the running of the program.*/{ unsigned int read_code;  while (bit_counter_to_read<input_bit_counter)        { val_to_read=(val_to_read<<8)|read_byte();          bit_counter_to_read += 8;        }  bit_counter_to_read -= input_bit_counter;  read_code=val_to_read>>bit_counter_to_read;  val_to_read &= ((1<<bit_counter_to_read)-1);  return read_code;}#define end_input()  ((bit_counter_to_read<input_bit_counter)&&end_of_data())void lzwencoding()/* Returned parameters: None.   Action: Compresses with LZW method all bytes read by the function 'read_input'.   Errors: An input/output error could disturb the running of the program.*/{ p_dic_val current_node,new_node;  unsigned int symbol;  if (!end_input())     { init_dictionary1();#ifdef TYPE_GIF_ENCODING       write_code_lr(initialization_code);#endif       current_node=dictionary[read_input()];       while (!end_input())             { symbol=read_input();               new_node=find_node(current_node,symbol);               if ((new_node!=current_node)&&(CHAR_DIC_VAL(new_node)==symbol))                  current_node=new_node;               else { write_code_lr(CODE_DIC_VAL(current_node));                      add_node(current_node,new_node,symbol);                      if dictionary_sature()                         {#ifdef TYPE_GIF_ENCODING                           write_code_lr(initialization_code);#endif                           init_dictionary2();                         }                      current_node=dictionary[symbol];                    }             }       write_code_lr(CODE_DIC_VAL(current_node));#ifdef TYPE_GIF_ENCODING       write_code_lr(end_information_code);#endif       complete_encoding_lr();       remove_dictionary();     }}void aide()/* Returned parameters: None.   Action: Displays the help of the program and then stops its running.   Errors: None.*/{ printf("This utility enables you to compress a file by using LZW method\n");  printf("as given 'La Video et Les Imprimantes sur PC'\n");  printf("\nUse: codlzw source target\n");  printf("source: Name of the file to compress\n");  printf("target: Name of the compressed file\n");}int main(argc,argv)/* Returned parameters: Returns an error code (0=None).   Action: Main procedure.   Errors: Detected, handled and an error code is returned, if any.*/int argc;char *argv[];{ if (argc!=3)     { aide();       exit(BAD_ARGUMENT);     }  else if ((source_file=fopen(argv[1],"rb"))==NULL)          { aide();            exit(BAD_FILE_NAME);          }       else if ((dest_file=fopen(argv[2],"wb"))==NULL)               { aide();                 exit(BAD_FILE_NAME);               }            else { lzwencoding();                   fclose(source_file);                   fclose(dest_file);                 }  printf("Execution of codlzw completed.\n");  return (NO_ERROR);}