lzw.cpp

zlib-1.2.3.tar是新的zlib库藏 用于压缩 等等

/* 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.
*/

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... */
#endif

static 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. */
/* 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. */
static 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. */
static unsigned int             bit_counter_min_decoding;
/* Bit counter to encode 'initialization_code'. */
/* initialization_code and end_information_code are both consecutive
   coming up just after the last known word in the initial dictionary. */

static p_dic_link decode_dictionary[1<<EXP2_DIC_MAX];

static void init_decode_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 ((decode_dictionary[i]=(p_dic_link)malloc(sizeof(t_dic_link)))==NULL)
           { while (i)
             { i--;
               free(decode_dictionary[i]);
             }
             exit(BAD_MEM_ALLOC);
           }
        if (i<initialization_code)
           LINK_CHAR(decode_dictionary[i])=i;
        LINK_PRED(decode_dictionary[i])=NULL;
      }
  index_dic=end_information_code+1;
  bit_counter_decoding=bit_counter_min_decoding;
}
static void init_decode_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)&&(decode_dictionary[i]!=NULL);i++)
      LINK_PRED(decode_dictionary[i])=NULL;
  index_dic=end_information_code+1;
  bit_counter_decoding=bit_counter_min_decoding;
}

static void remove_decode_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)&&(decode_dictionary[i]!=NULL);i++)
      free(decode_dictionary[i]);
}

static void write_output(unsigned int 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.
*/
{ 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);
        }
}

static 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;
}

static void write_link(p_dic_link chainage, unsigned int* 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.
*/
{ 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);
       }
}

static unsigned int write_string(unsigned int pred_code,
    unsigned int current_code, unsigned int 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 character;

  if (current_code<index_dic)
     write_link(decode_dictionary[current_code],&character);
  else { write_link(decode_dictionary[pred_code],&character);
         write_output(first_char);
       }
  return character;
}

static void add_string(unsigned int code, unsigned int first_char)
/* Returned parameters: None.
   Action: Adds the string given by 'code' to the dictionary.
   Errors: None.
*/
{ LINK_CHAR(decode_dictionary[index_dic])=first_char;
  LINK_PRED(decode_dictionary[index_dic])=decode_dictionary[code];
  index_dic++;
  if ((unsigned)index_dic+1==(unsigned)(1<<bit_counter_decoding))
     bit_counter_decoding++;
}

static 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;
}

static 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;
}

int decode_lzw() /* 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 = 0, current_code = 0;
  unsigned int first_char = 0;

  if (!end_of_data())
     { init_decode_dictionary1();
       current_code=read_code_lr();
#ifdef TYPE_GIF_ENCODING
       if (current_code!=initialization_code)
          { fprintf(stderr,"Fichier de codes invalide!\n");
            remove_decode_dictionary();
            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_decode_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");
                         exit(BAD_DATA_CODE);
                       }
#ifdef AUTO_REINIT_DIC
                      if (index_dic==index_dic_max)
                         { fprintf(stderr,"Depassement de capacite du dictionary!\n");
                           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_decode_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");
                    exit(BAD_DATA_CODE);
                  }
               first_char=write_string(pred_code,current_code,first_char);
               if (index_dic==index_dic_max-2)
                  { init_decode_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_decode_dictionary();
#endif
       complete_output();
     }
     return 0;
}