/* File: dcodlzw.c   Author: David Bourgin   Creation date: 25/3/95   Last update: 12/10/95   Purpose: Example of LZW decoding with a file source to decompress.*/#include <stdio.h>/* For routines printf,fgetc,fputc. */#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#define BAD_DATA_CODE        4#define DICTIONARY_OVERFLOW  5/* 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_write=0,                  val_to_read=0;unsigned char bit_counter_to_write=0,              bit_counter_to_read=0;typedef struct s_dic_link { unsigned int character;                            struct s_dic_link *predecessor;                          } t_dic_link,*p_dic_link;#define LINK_CHAR(dic)  ((*(dic)).character)#define LINK_PRED(dic)  ((*(dic)).predecessor)#define TYPE_GIF_ENCODING/* Enforces including marker codes initialization_code et end_information_code.   To invalid this option, set the line #define... in comments. */#ifdef TYPE_GIF_ENCODING#define AUTO_REINIT_DIC/* If this macro is defined, the dictionary is always increased   (even if this can make an error of overflow!).   At the opposite, if this macro is undefined, the dictionary is no more updated   as soon as it reaches its maximal capacity. The reception of the code   'initialization_code' will enforce the dictionary to by flushed.   To invalid this option, set the line #define... in comments.   This macro is considered only if TYPE_GIF_ENCODING is defined,   that is why we have the lines #ifdef... and #endif... */#endifunsigned int index_dic;/* Word counter already known in the dictionary. */unsigned char bit_counter_decoding;/* Bit counter in the decoding. */#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 output_bit_counter,/* Bit counter for each data in output.   With output_bit_counter=1, we can compress/decompress monochrome pictures   and with output_bit_counter=8, we can handle 256-colors pictures or any kind of files. */              bit_counter_min_decoding;/* 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_link dictionary[1<<EXP2_DIC_MAX];void init_dictionary1()/* Returned parameters: None.   Action: First initialization of the dictionary when we start an decoding.   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 */  output_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 (output_bit_counter==1)     bit_counter_min_decoding=3;  else bit_counter_min_decoding=output_bit_counter+1;  initialization_code=1<<(bit_counter_min_decoding-1);#ifdef TYPE_GIF_ENCODING  end_information_code=initialization_code+1;#else  end_information_code=initialization_code-1;#endif  for (i=0;i<index_dic_max;i++)      { if ((dictionary[i]=(p_dic_link)malloc(sizeof(t_dic_link)))==NULL)           { while (i)             { i--;               free(dictionary[i]);             }             fclose(source_file);             fclose(dest_file);             exit(BAD_MEM_ALLOC);           }        if (i<initialization_code)           LINK_CHAR(dictionary[i])=i;        LINK_PRED(dictionary[i])=NULL;      }  index_dic=end_information_code+1;  bit_counter_decoding=bit_counter_min_decoding;}void init_dictionary2()/* Returned parameters: None.   Action: Initialization of the dictionary during the decoding.   The dictionary must have been initialized once by 'init_dictionary1'.   Errors: None.*/{ register unsigned int i;  for (i=initialization_code;(i<index_dic_max)&&(dictionary[i]!=NULL);i++)      LINK_PRED(dictionary[i])=NULL;  index_dic=end_information_code+1;  bit_counter_decoding=bit_counter_min_decoding;}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]);}void write_output(value)/* Returned parameters: None.   Action: Writes 'output_bit_counter' via the function write_byte.   Errors: An input/output error could disturb the running of the program.*/unsigned int value;{ val_to_write=(val_to_write << output_bit_counter) | value;  bit_counter_to_write += output_bit_counter;  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_output()/* Returned parameters: None.   Action: Fills the last byte to write with 0-bits, if necessary.   This procedure is to be considered aith the procedure 'write_output'.   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_link(chainage,character)/* Returned parameters: 'character' can have been modified.   Action: Sends the string in the output stream given by the 'link' of the LZW dictionary.   'character' contains to the end of the routine the first character of the string.   Errors: None (except a possible overflow of the operational stack allocated   by the program, which must allows at least 8*INDEX_DIC_MAX bytes, corresponding   to an exceptional case.*/p_dic_link chainage;unsigned int *character;{ if (LINK_PRED(chainage)!=NULL)     { write_link(LINK_PRED(chainage),character);       write_output(LINK_CHAR(chainage));     }  else { write_output(LINK_CHAR(chainage));         *character=LINK_CHAR(chainage);       }}unsigned int write_string(pred_code,current_code,first_char)/* Returned parameters: Returns a byte.   Action: Writes the string of bytes associated to 'current_node' and returns   the first character of this string.   Errors: None.*/unsigned int pred_code,current_code;unsigned int first_char;{ unsigned int character;  if (current_code<index_dic)     write_link(dictionary[current_code],&character);  else { write_link(dictionary[pred_code],&character);         write_output(first_char);       }  return character;}void add_string(code,first_char)/* Returned parameters: None.   Action: Adds the string given by 'code' to the dictionary.   Errors: None.*/unsigned int code;unsigned int first_char;{ LINK_CHAR(dictionary[index_dic])=first_char;  LINK_PRED(dictionary[index_dic])=dictionary[code];  index_dic++;  if (index_dic+1==(1<<bit_counter_decoding))     bit_counter_decoding++;}unsigned int read_code_lr()/* Returned parameters: Returns the value of code.   Action: Returns the value coded on 'bit_counter_decoding' bits from the stream of input codes.   The bits are stored from left to right. 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 read_code;  while (bit_counter_to_read<bit_counter_decoding)        { val_to_read=(val_to_read<<8)|read_byte();          bit_counter_to_read += 8;        }  bit_counter_to_read -= bit_counter_decoding;  read_code=val_to_read>>bit_counter_to_read;  val_to_read &= ((1<<bit_counter_to_read)-1);  return read_code;}unsigned int write_code_rl()/* Returned parameters: Returns the value of code.   Action: Returns the value coded on 'bit_counter_decoding' bits from the stream of input 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 read_code;  while (bit_counter_to_read<bit_counter_decoding)        { val_to_read |= ((unsigned long int)read_byte())<<bit_counter_to_read;          bit_counter_to_read += 8;        }  bit_counter_to_read -= bit_counter_decoding;  read_code=val_to_read & ((1<<bit_counter_decoding)-1);  val_to_read >>= bit_counter_decoding;  return read_code;}void lzwdecoding()/* Returned parameters: None.   Action: Compresses with LZW method all bytes read by the function 'read_code_??'.   (where '??' is 'lr' or 'rl', depending on how you stored the bits in the compressed stream.   Errors: An input/output error could disturb the running of the program.*/{ unsigned int pred_code,current_code;  unsigned int first_char;  if (!end_of_data())     { init_dictionary1();       current_code=read_code_lr();#ifdef TYPE_GIF_ENCODING       if (current_code!=initialization_code)          { fprintf(stderr,"Fichier de codes invalide!\n");            remove_dictionary();            fclose(source_file);            fclose(dest_file);            exit(BAD_DATA_CODE);          }       if ((current_code=read_code_lr())<initialization_code)          { first_char=write_string(pred_code,current_code,first_char);            pred_code=current_code;            current_code=read_code_lr();          }       while (current_code!=end_information_code)             { if (current_code==initialization_code)                  { init_dictionary2();                    current_code=read_code_lr();                    if (current_code<initialization_code)                       { first_char=write_string(pred_code,current_code,first_char);                         pred_code=current_code;                         current_code=read_code_lr();                       }                  }               else { if (current_code>index_dic)                       { fprintf(stderr,"Fichier de codes invalide!\n");                         fclose(source_file);                         fclose(dest_file);                         exit(BAD_DATA_CODE);                       }#ifdef AUTO_REINIT_DIC                      if (index_dic==index_dic_max)                         { fprintf(stderr,"Depassement de capacite du dictionary!\n");                           fclose(source_file);                           fclose(dest_file);                           exit(DICTIONARY_OVERFLOW);                         }                      first_char=write_string(pred_code,current_code,first_char);                      add_string(pred_code,first_char);                      pred_code=current_code;                      current_code=read_code_lr();#else                      first_char=write_string(pred_code,current_code,first_char);                      if (index_dic<index_dic_max)                         add_string(pred_code,first_char);                      pred_code=current_code;                      current_code=read_code_lr();#endif                    }          }    remove_dictionary();#else       pred_code=current_code;       first_char=write_string(pred_code,current_code,first_char);       while ((!end_of_data())||(bit_counter_to_read>=bit_counter_decoding))             { current_code=read_code_lr();               if (current_code>index_dic)                  { fprintf(stderr,"Fichier de codes invalide!\n");                    fclose(source_file);                    fclose(dest_file);                    exit(BAD_DATA_CODE);                  }               first_char=write_string(pred_code,current_code,first_char);               if (index_dic==index_dic_max-2)                  { init_dictionary2();                    if ((!end_of_data())||(bit_counter_to_read>=bit_counter_decoding))                       { pred_code=(current_code=read_code_lr());                         first_char=write_string(pred_code,current_code,first_char);                       }                  }               else add_string(pred_code,first_char);               pred_code=current_code;             }       remove_dictionary();#endif       complete_output();     }}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 decompress a file by using LZW method\n");  printf("as given 'La Video et Les Imprimantes sur PC'\n");  printf("\nUse: dcodlzw source target\n");  printf("source: Name of the file to decompress\n");  printf("target: Name of the restored 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 { lzwdecoding();                   fclose(source_file);                   fclose(dest_file);                 }  printf("Execution of dcodlzw completed.\n");  return (NO_ERROR);}