lzw.c

This is code tutorial for image processing include:histogram,sketon....

           inserting new characters into the front of
           the string.
*/

build_string(w, number, string_table)
   char   w[];
   short  number;
   struct table_item string_table[];
{
   if(string_table[number].character != '\0'){
      insert_into_w(w, string_table[number].character);
      if(string_table[number].num != 0)
         build_string(w, string_table[number].num, string_table);
   }
}  /* ends build_string */





/* 2.3.1.1
            This function inserts the character x into the
            front of string w.
*/

insert_into_w(w, x)
   char w[], x;
{
   char temp;
   int  i, j, not_finished;

      /* first find the end of the string w */
   i = 0;
   not_finished = 1;
   while(not_finished){
      if(w[i] == '\0')
         not_finished = 0;
      else
         i++;
   }  /* ends while not_finished */
   w[i+1] = '\0';
   for(j=i; j>0; j--)
      w[j] = w[j-1];
   w[0] = x;

}  /* ends insert_into_w */






/* 2.4
        This function appends the character k onto the
        end of the string w.
*/

append_to_w(w, k)
   char w[], k;
{
   int i, searching;
   i = 0;
   searching = 1;
   while(searching){
      if(w[i] == '\0')
         searching = 0;
      else
         i++;
   }
   w[i] = k;
   w[i+1] = '\0';

}  /* ends append_to_w */



/* 2.5
        This function inserts the string w and character
        k into the string table.

        Search the table from bottom up until you find
        the first open place.
        Set the character of that place to k.
        set the num of that place to the value returned
        by find_string_w_in_table.
*/

insert_into_table(w, k, string_table)
   char   w[], k;
   struct table_item string_table[];
{
   int   i, j, searching;
   short s;

   i         = TABLE_SIZE - 1;
   searching = 1;

   while(searching){
      if(string_table[i].character != '\0')
         searching = 0;
      else{
         i--;
         if(i < 0)
            printf("\n2.5> Table full - cannot insert");
      }
   }  /* ends while searching */

   find_string_w_in_table(w, string_table, &s);

   string_table[i+1].num       = s;
   string_table[i+1].character = k;
/*printf("\n2.5> inserted string %s and char %c into table", w,k);*/
/*print_string_table(string_table);*/
}  /* ends is_in_string_table */




/*******************************************************

          D E C O M P R E S S I O N    C O D E

*******************************************************/



/* 3.0
*/

perform_decompression(string_table, in_file_desc, out_file_desc)
   int    in_file_desc, out_file_desc;
   struct table_item string_table[];
{

   char   c,
          final_char,
          k,
          out_buffer[IB_LENGTH],
          special_char,
          stack[100],
          w[100];

   int    bytes_read,
          bytes_written,
          decoding,
          i,
          in_counter,
          j,
          out_counter,
          special_case,
          stack_pointer,
          still_reading;

   short  code,
          in_buffer[OB_LENGTH],
          incode,
          oldcode,
          s;

   for(i=0; i<OB_LENGTH; i++)
      in_buffer[i] = 0;
   for(i=0; i<IB_LENGTH; i++)
      out_buffer[i] = '\0';

   stack_pointer = -1;
   in_counter    = 0;
   out_counter   = 0;
   still_reading = 1;

   while(still_reading){

      bytes_read = read_compressed_file(in_buffer, in_file_desc);
      if(bytes_read < OB_LENGTH*2)
         still_reading = 0;
/***********
printf("\n3.0> read %d bytes", bytes_read);
for(i=0; i<bytes_read/2; i++){
 if( (i%15) == 0) printf("\n3.0> ");
 printf("-%3d", in_buffer[i]);
}
************/

      code    = in_buffer[in_counter];
      in_counter++;
      oldcode = code;
      code_of(code, &s, &k, string_table);
      output_character(k, out_buffer, &out_counter, out_file_desc);
      final_char = k; /* step 4 in algorithm */

      decoding = 1;
      while(decoding){

             /* NEXT CODE */

             /* The next few if, else, if's are checking to
                see if the input compressed file is empty */

             /* end of in_buffer and end of file
                so decode last input and quit */
         if( (in_counter >= bytes_read/2)   &&
             (still_reading == 0)){
            bytes_written = my_write(out_file_desc, out_buffer,
                                     out_counter);
printf("\n2.0> wrote %d bytes", bytes_written);
            decoding = 0;
         }  /* ends if end of in_buffer and end of file */

            /* else end of in_buffer but not end of file
               so reset in_counter and go back and read
               more data */
         else{
            if( (in_counter >= bytes_read/2)   &&
                (still_reading == 1)){
               in_counter = 0;
               decoding   = 0;
            }  /* ends if end of in_buffer */

            else{ /* not end of in_buffer
                     we have input to process so let's
                     process it (step 5 in algorithm */

               code   = in_buffer[in_counter];
               in_counter++;
               incode = code;

               if(not_in_string_table(code, string_table)){
                  /* ??? output_character(final_char, out_buffer,
                                   &out_counter, out_file_desc);*/
                  push_onto_stack(final_char, stack, &stack_pointer);
                  code   = oldcode;
                  incode = new_code_of(oldcode, final_char, string_table);
               }  /* ends if not_in_string_table */

                  /* next_symbol looks at the code
                     if it is a num + char then it strips off
                     the chars and puts them on a stack until
                     they are all gone.
                  */

               next_symbol(&code, string_table,
                           stack, &stack_pointer);

                  /* code of CODE is a single character */
               code_of(code, &s, &k, string_table);
               if(s == 0){  /* if code of CODE is a single char */
                  output_character(k, out_buffer, &out_counter,
                                   out_file_desc);
                  final_char = k;

                     /* do while stack not empty */
                  while(stack_pointer > -1){
                     pop_off_of_stack(&c, stack, &stack_pointer);
                     output_character(c, out_buffer, &out_counter,
                                      out_file_desc);
                  }  /* ends while stack not empty */

                  put_num_char_in_string_table(oldcode, k,
                                            string_table);

                  oldcode = incode;
               }  /* ends else code of CODE is a single character */

            }  /* ends else not end of in_buffer */

         }  /* ends else end of in_buffer
               but not end of file */

      }  /* ends while decoding */

   }  /* ends while still_reading */

}  /* ends perform_decompression */



/* 3.1
         This function reads the type short from the
         compressed file.
*/

read_compressed_file(in_buffer, in_file_desc)
   short in_buffer[];
   int   in_file_desc;
{
   int i, bytes_read;
   union {
           char  bytes[OB_LENGTH*2];
           short nums[OB_LENGTH];
         }  buffer;

   for(i=0; i<OB_LENGTH*2; i++)
      buffer.bytes[i] = '\0';

   bytes_read = my_read(in_file_desc, buffer.bytes, OB_LENGTH*2);
   /*printf("\n3.1> Read %d bytes using file header", bytes_read);*/

   for(i=0; i<bytes_read/2; i++){
      in_buffer[i] = buffer.nums[i];
      /*printf("\n3.1> read short [%3d] = %3d", i, buffer.nums[i]);*/
   }
   return(bytes_read);
}




/* 3.2
        This function looks in the string table and sets
        the char x and short s to the values in the
        table at location = code.
        x = string_table[code].character
        s = string_table[code].num
*/

code_of(code, s, x, string_table)
   char   *x;
   short  code, *s;
   struct table_item string_table[];
{
   *x = string_table[code].character;
   *s = string_table[code].num;
}  /* ends code_of */









/* 3.3
        This function outputs the character k.  It puts it
        in the output buffer.  If the output buffer is full
        it writes the buffer to the output file.
*/
output_character(k, out_buffer, out_counter, out_file_desc)
   char k, out_buffer[];
   int  *out_counter, out_file_desc;
{
   int bytes_written;

   if(*out_counter >= IB_LENGTH){
      bytes_written = my_write(out_file_desc, out_buffer, IB_LENGTH);
printf("\n3.3> wrote %d bytes", bytes_written);
      *out_counter = 0;
   }

   out_buffer[*out_counter] = k;
   *out_counter = *out_counter + 1;

}  /* ends output_character */





/* 3.4
        This function looks in the string table
        at location code to see if it exists as a
        valid code, i.e. if its character is
        non-null.  If the code does not exist
        it returns a 1.  If the code does exist
        it returns a 0.
*/
not_in_string_table(code, string_table)
   short  code;
   struct table_item string_table[];
{
   int i, result;
   result = 0;
   if(string_table[code].character == '\0')
      result = 1;
   return(result);
}  /* ends not_in_string_table */





/* 3.5
       Return the place
       of this new code to incode.
       Do not insert the char and oldcode
       into the table.
*/

new_code_of(oldcode, final_char, string_table)
   char  final_char;
   short oldcode;
   struct table_item string_table[];
{
   int i, new_code, searching;

   searching = 1;
   i = TABLE_SIZE - 1;
   while(searching){
      if(string_table[i].character != '\0')
         searching = 0;
      else
         i--;
   }

   new_code = i+1;

   printf("\n3.5> inserted into table, new code=%d", new_code);
   return(new_code);
}  /* ends new_code_of */




/* 3.6
        This function looks at code in the string
        table to see if it is a single character
        or a num + char.  If it is a num + char
        it pushes the char onto the stack, sets code
        to the num, and calls itself recursively.
*/

next_symbol(code, string_table, stack, stack_pointer)
   char   stack[], *stack_pointer;
   short  *code;
   struct table_item string_table[];
{
   short code2, s;
   char  c;

   code2 = *code;

   code_of(code2, &s, &c, string_table);
   if(s != 0){  /* if code of CODE is a num + char
                   push char onto stack */
      push_onto_stack(c, stack, stack_pointer);
        /* code = code_of code.num
           if s > 255 then it will be
           another num + char so call next_symbol
           recursively */
      if(s > 255){
         /*code_of(s, code, &c, string_table);
           next_symbol(code, string_table, stack, stack_pointer);*/
           *code = s;
           next_symbol(code, string_table, stack, stack_pointer);
      }
      else /* else s is not a num + char so set the
              code to s so next_symbol will not return
              a code of zero by mistake */
         *code = s;
   }  /* ends if s != 0 */

}  /* ends next_symbol */




        /* NOTE: The stack in this program is an array of
                 char.  Initially, stack_pointer = -1.
                 stack_pointer points to the "top of"
                 the stack.

                 To push onto stack just
                 increment stack_pointer then
                 set stack[stack_pointer] = x.

                 To pop off stack just set
                 x = stack[stack_pointer] and decrement
                 the stack_pointer.

                 The stack is empty when
                 stack_pointer == -1
        */

/* 3.7
        This function pushes the character x down onto
        a stack.
*/

push_onto_stack(x, stack, stack_pointer)
   char stack[], x;
   int  *stack_pointer;
{
   *stack_pointer = *stack_pointer + 1;
   stack[*stack_pointer] = x;
}  /* ends push_onto_stack */




/* 3.8
        This function pops an element off the top of the
        stack and sends it back to the calling funtion.
*/

pop_off_of_stack(x, stack, stack_pointer)
   char stack[], *x;
   int  *stack_pointer;
{
   *x = stack[*stack_pointer];
   *stack_pointer = *stack_pointer - 1;
}  /* ends pop_off_of_stack */



/* 3.9
        This function puts the num and char into the
        string table.
*/

put_num_char_in_string_table(n, c, string_table)
   char   c;
   short  n;
   struct table_item string_table[];
{
   int i, searching;

   searching = 1;
   i = TABLE_SIZE - 1;
   while(searching){
      if(string_table[i].character != '\0')
         searching = 0;
      else
         i--;
   }

   string_table[i+1].num       = n;
   string_table[i+1].character = c;

}  /* ends put_num_char_in_string_table */