/* File: dcodhuff.c   Author: David Bourgin   Creation date: 15/2/94   Last update: 24/7/95   Purpose: Example of Huffman decoding with a file source to decompress.*/#include <stdio.h>/* For routines printf,fgetc and fputc */#include <memory.h>/* For routine memset */#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  1typedef struct s_tree { unsigned int byte;                             /* A byte has to be coded as an unsigned integer to allow a node to have a value over 255 */                         struct s_tree *left_ptr,                                       *right_ptr;                       } t_tree,*p_tree;#define TREE_BYTE(ptr_tree)  ((*(ptr_tree)).byte)#define LEFTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).left_ptr)#define RIGHTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).right_ptr)typedef struct { unsigned char bits[32];                 unsigned int bits_nb;                 unsigned char presence;               } t_bin_val;#define BITS_BIN_VAL(x)  ((x).bits)#define NB_BITS_BIN_VAL(x)  ((x).bits_nb)#define PRESENCE_BIN_VAL(x)  ((x).presence)/* 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 char bit_counter_to_read=0;unsigned int val_to_read=0;unsigned char read_code_1_bit()/* Returned parameters: Returns an unsigned integer with the 0-bit (on the right of the integer) valid   Action: Reads the next bit in the stream of data to compress   Errors: An input/output error could disturb the running of the program   The source must have enough bits to read*/{ unsigned int result;  if (bit_counter_to_read)     { bit_counter_to_read--;       result=(val_to_read >> bit_counter_to_read) & 1;     }  else { val_to_read=read_byte();         bit_counter_to_read=7;         result=(val_to_read >> 7) & 1;       }  val_to_read &= 127;  return result;}unsigned int read_code_n_bits(n)/* Returned parameters: Returns an unsigned integer with the n-bits (on the right of the integer) valid   Action: Reads the next n bits in the stream of data to compress   Errors: An input/output error could disturb the running of the program   The source must have enough bits to read*/unsigned char n;{ unsigned int result;  while ((bit_counter_to_read<n)&&(!end_of_data()))        { val_to_read=(val_to_read << 8)+read_byte();          bit_counter_to_read += 8;        }  bit_counter_to_read -= n;  result=val_to_read >> bit_counter_to_read;  val_to_read &= ((1<<bit_counter_to_read)-1);  return result;}void read_header(codes_table)/* Returned parameters: The contain of 'codes_table' is modified   Action: Rebuilds the binary encoding array by using the header   Errors: An input/output error could disturb the running of the program*/t_bin_val codes_table[257];{ register unsigned int i,j;  char byte_nb;  (void)memset((char *)codes_table,0,257*sizeof(*codes_table));                             /* == Decoding of the first part of the header === */  if (read_code_1_bit())                             /* First bit=0 => Present bytes coded on n*8 bits                                         =1 => Present bytes coded on 256 bits */     for (i=0;i<=255;i++)         PRESENCE_BIN_VAL(codes_table[i])=read_code_1_bit();  else { i=read_code_n_bits(5)+1;         while (i)               { PRESENCE_BIN_VAL(codes_table[read_code_n_bits(8)])=1;                 i--;               }       }  PRESENCE_BIN_VAL(codes_table[256])=1;                             /* Presence of a fictive 256-byte is enforced! */                             /* == Decoding the second part of the header == */  for (i=0;i<=256;i++)      if PRESENCE_BIN_VAL(codes_table[i])         { if (read_code_1_bit())                             /* First bit=0 => 5 bits of binary length-1 followed by a binary word                                         =1 => 8 bits of binary length-1 followed by a binary word */              j=read_code_n_bits(8)+1;           else j=read_code_n_bits(5)+1;           NB_BITS_BIN_VAL(codes_table[i])=j;                             /* Reading of a binary word */           byte_nb=(j+7) >> 3;           if (j & 7)              {              /* Reads the bits that takes less than one byte */                byte_nb--;                BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(j & 7);              }           while (byte_nb)                 {           /* Reads the bits that takes one byte, at least */                   byte_nb--;                   BITS_BIN_VAL(codes_table[i])[byte_nb]=(unsigned char)read_code_n_bits(8);                 }         }}void suppress_tree(tree)/* Returned parameters: None   Action: Suppresses the allocated memory for the tree   Errors: None if the tree has been build with dynamical allocations!*/p_tree tree;{ if (tree!=NULL)     { suppress_tree(LEFTPTR_OF_TREE(tree));       suppress_tree(RIGHTPTR_OF_TREE(tree));       free(tree);     }}p_tree tree_encoding(codes_table)/* Returned parameters: A binary tree is returned   Action: Returns the decoding binary tree built from 'codes_table'   Errors: None*/t_bin_val codes_table[257];{ register unsigned int i;  unsigned int j;  p_tree ptr_tree,current_node;  if ((ptr_tree=(p_tree)malloc(sizeof(t_tree)))==NULL)     exit(BAD_MEM_ALLOC);  TREE_BYTE(ptr_tree)=257;  LEFTPTR_OF_TREE(ptr_tree)=NULL;  RIGHTPTR_OF_TREE(ptr_tree)=NULL;  for (i=0;i<=256;i++)      { for (current_node=ptr_tree,j=NB_BITS_BIN_VAL(codes_table[i]);j;j--)          { if (BITS_BIN_VAL(codes_table[i])[(j-1) >> 3] & (1 << ((j-1) & 7)))               if (LEFTPTR_OF_TREE(current_node)==NULL)                  { if ((LEFTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL)                       { suppress_tree(ptr_tree);                         exit(BAD_MEM_ALLOC);                       }                    current_node=LEFTPTR_OF_TREE(current_node);                    LEFTPTR_OF_TREE(current_node)=NULL;                    RIGHTPTR_OF_TREE(current_node)=NULL;                  }               else current_node=LEFTPTR_OF_TREE(current_node);            else if (RIGHTPTR_OF_TREE(current_node)==NULL)                    { if ((RIGHTPTR_OF_TREE(current_node)=(p_tree)malloc(sizeof(t_tree)))==NULL)                       { suppress_tree(ptr_tree);                         exit(BAD_MEM_ALLOC);                       }                      current_node=RIGHTPTR_OF_TREE(current_node);                      LEFTPTR_OF_TREE(current_node)=NULL;                      RIGHTPTR_OF_TREE(current_node)=NULL;                    }                 else current_node=RIGHTPTR_OF_TREE(current_node);            if (j==1)               TREE_BYTE(current_node)=i;            else TREE_BYTE(current_node)=257;          }      };  return (ptr_tree);}void huffmandecoding()/* Returned parameters: None   Action: Decompresses with Huffman method all bytes read by the function 'read_code_1_bit' and 'read_code_n_bits'   Errors: An input/output error could disturb the running of the program*/{ t_bin_val encoding_table[257];  p_tree ptr_tree,current_node;  if (!end_of_data())    /* Are there data to compress? */     { read_header(encoding_table);       ptr_tree=tree_encoding(encoding_table);       do { current_node=ptr_tree;            while (TREE_BYTE(current_node)==257)                  if (read_code_1_bit())                             /* Bit=1 => Got to left in the node of the tree                                   =0 => Got to right in the node of the tree */                     current_node=LEFTPTR_OF_TREE(current_node);                  else current_node=RIGHTPTR_OF_TREE(current_node);            if (TREE_BYTE(current_node)<=255)               write_byte(TREE_BYTE(current_node));          }       while (TREE_BYTE(current_node)!=256);       suppress_tree(ptr_tree);     }}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 Huffman method\n");  printf("as given 'La Video et Les Imprimantes sur PC'\n");  printf("\nUse: dcodhuff 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 { huffmandecoding();                   fclose(source_file);                   fclose(dest_file);                 }  printf("Execution of dcodhuff completed.\n");  return (NO_ERROR);}