/* File: codhuff.c
  Author: David Bourgin (David.Bourgin@ufrima.imag.fr)
  Creation date: 7/2/94
  Last update: 24/7/95
  Purpose: Example of Huffman encoding with a file source to compress.
  Attention: The compiler must have been configured for a stack of at least
  20 kb.
*/

#include <stdio.h>
/* For routines fgetc,fputc,fwrite and rewind */
#include <memory.h>
/* For routines memset,memcpy */
#include <malloc.h>
/* For routines malloc and free */
#include <stdlib.h>
/* For routines qsort et 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;

typedef 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 */
            unsigned long int weight;
            struct s_tree *left_ptr,
                   *right_ptr;
           } t_tree,*p_tree;
#define BYTE_OF_TREE(ptr_tree) ((*(ptr_tree)).byte)
#define WEIGHT_OF_TREE(ptr_tree) ((*(ptr_tree)).weight)
#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;
        } t_bin_val;
#define BITS_BIN_VAL(bin_val) ((bin_val).bits)
#define BITS_NB_BIN_VAL(bin_val) ((bin_val).bits_nb)

               /* Being that fgetc=EOF only after any access
                then 'stored_byte_status' is 'TRUE' if a byte has been stored with 'fgetc'
                or 'FALSE' if there's no valid byte not already read and not handled in 'stored_byte_val' */
int stored_byte_status=FALSE;
int stored_byte_val;

/* Pseudo procedures */
#define beginning_of_data() { (void)rewind(source_file); stored_byte_status=FALSE; }
#define end_of_data() (stored_byte_status?FALSE:!(stored_byte_status=((stored_byte_val=fgetc(source_file))!=EOF)))
#define read_byte() (stored_byte_status?stored_byte_status=FALSE,(unsigned char)stored_byte_val:(unsigned char)fgetc(source_file))
#define write_byte(byte) ((void)fputc((byte),dest_file))

unsigned char bit_counter_to_write=0;
unsigned int val_to_write=0;

void write_bin_val(bin_val)
/* Returned parameters: None
  Action: Writes in the output stream the value binary-coded into 'bin_val'
  Errors: An input/output error could disturb the running of the program
*/
t_bin_val bin_val;
{ unsigned char bin_pos,
        byte_pos;

 byte_pos=(BITS_NB_BIN_VAL(bin_val)+7) >> 3;
 bin_pos=BITS_NB_BIN_VAL(bin_val) & 7;
 if (bin_pos)
   { byte_pos--;
    val_to_write=(val_to_write<<bin_pos)|BITS_BIN_VAL(bin_val)[byte_pos];
    bit_counter_to_write += bin_pos;
    if (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);
     }
   }
 while (byte_pos)
    { byte_pos--;
     val_to_write=(val_to_write<<8)|BITS_BIN_VAL(bin_val)[byte_pos];
     write_byte((unsigned char)(val_to_write>>bit_counter_to_write));
     val_to_write &= ((1<<bit_counter_to_write)-1);
    }
}

void fill_encoding()
/* Returned parameters: None
  Action: Fills the last byte to write in the output stream with zero values
  Errors: An input/output error could disturb the running of the program
*/
{ if (bit_counter_to_write)
   write_byte(val_to_write << (8-bit_counter_to_write));
}

void write_header(codes_table)
/* Returned parameters: None
  Action: Writes the header in the stream of codes
  Errors: An input/output error could disturb the running of the program
*/
t_bin_val codes_table[257];
{ register unsigned int i,j;
 t_bin_val bin_val_to_0,
      bin_val_to_1,
      bin_val;     /* Is used to send in binary mode via write_bin_val */

 *BITS_BIN_VAL(bin_val_to_0)=0;
 BITS_NB_BIN_VAL(bin_val_to_0)=1;
 *BITS_BIN_VAL(bin_val_to_1)=1;
 BITS_NB_BIN_VAL(bin_val_to_1)=1;
 for (i=0,j=0;j<=255;j++)
   if BITS_NB_BIN_VAL(codes_table[j])
     i++;
               /* From there, i contains the number of bytes of the several non null occurrences to encode */
               /* First part of the header: Specifies the bytes that appear in the source of encoding */
 if (i<32)
   {            /* Encoding of the appeared bytes with a block of bytes */
    write_bin_val(bin_val_to_0);
    BITS_NB_BIN_VAL(bin_val)=5;
    *BITS_BIN_VAL(bin_val)=(unsigned char)(i-1);
    write_bin_val(bin_val);
    BITS_NB_BIN_VAL(bin_val)=8;
    for (j=0;j<=255;j++)
      if BITS_NB_BIN_VAL(codes_table[j])
       { *BITS_BIN_VAL(bin_val)=(unsigned char)j;
        write_bin_val(bin_val);
       }
   }
 else {           /* Encoding of the appeared bytes with a block of bits */
     write_bin_val(bin_val_to_1);
     for (j=0;j<=255;j++)
       if BITS_NB_BIN_VAL(codes_table[j])
        write_bin_val(bin_val_to_1);
       else write_bin_val(bin_val_to_0);
   };
               /* Second part of the header: Specifies the encoding of the bytes (fictive or not) that appear in the source of encoding */
 for (i=0;i<=256;i++)
   if (j=BITS_NB_BIN_VAL(codes_table[i]))
     { if (j<33)
       { write_bin_val(bin_val_to_0);
        BITS_NB_BIN_VAL(bin_val)=5;
       }
      else { write_bin_val(bin_val_to_1);
         BITS_NB_BIN_VAL(bin_val)=8;
        }
      *BITS_BIN_VAL(bin_val)=(unsigned char)(j-1);
      write_bin_val(bin_val);
      write_bin_val(codes_table[i]);
     }
}

int weight_tree_comp(tree1,tree2)
/* Returned parameters: Returns a comparison status
  Action: Returns a negative, zero or positive integer depending on the weight
  of 'tree2' is less than, equal to, or greater than the weight of 'tree1'
  Errors: None
*/
p_tree *tree1,*tree2;
{ return (WEIGHT_OF_TREE(*tree2) ^ WEIGHT_OF_TREE(*tree1))?((WEIGHT_OF_TREE(*tree2)<WEIGHT_OF_TREE(*tree1))?-1:1):0;
}

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 build_tree_encoding()
/* Returned parameters: Returns a tree of encoding
  Action: Generates an Huffman encoding tree based on the data from the stream to compress
  Errors: If no memory is available for the allocations then a 'BAD_MEM_ALLOC' exception is raised
*/
{ register unsigned int i;
 p_tree occurrences_table[257],
     ptr_fictive_tree;

               /* Sets up the occurrences number of all bytes to 0 */
 for (i=0;i<=256;i++)
   { if ((occurrences_table[i]=(p_tree)malloc(sizeof(t_tree)))==NULL)
      { for (;i;i--)
         free(occurrences_table[i-1]);
       exit(BAD_MEM_ALLOC);
      }
    BYTE_OF_TREE(occurrences_table[i])=i;
    WEIGHT_OF_TREE(occurrences_table[i])=0;
    LEFTPTR_OF_TREE(occurrences_table[i])=NULL;
    RIGHTPTR_OF_TREE(occurrences_table[i])=NULL;
   }
               /* Valids the occurrences of 'occurrences_table' with regard to the data to compressr */
 if (!end_of_data())
   { while (!end_of_data())
       { i=read_byte();
        WEIGHT_OF_TREE(occurrences_table[i])++;
       }
    WEIGHT_OF_TREE(occurrences_table[256])=1;
               /* Sorts the occurrences table depending on the weight of each character */
    (void)qsort(occurrences_table,257,sizeof(p_tree),weight_tree_comp);
    for (i=256;(i!=0)&&(!WEIGHT_OF_TREE(occurrences_table[i]));i--)
      free(occurrences_table[i]);
    i++;
               /* From there, 'i' gives the number of different bytes with a null occurrence in the stream to compress */
    while (i>0)      /* Looks up (i+1)/2 times the occurrence table to link the nodes in an uniq tree */
       { if ((ptr_fictive_tree=(p_tree)malloc(sizeof(t_tree)))==NULL)
         { for (i=0;i<=256;i++)
            suppress_tree(occurrences_table[i]);
          exit(BAD_MEM_ALLOC);
         }
        BYTE_OF_TREE(ptr_fictive_tree)=257;
        WEIGHT_OF_TREE(ptr_fictive_tree)=WEIGHT_OF_TREE(occurrences_table[--i]);
        LEFTPTR_OF_TREE(ptr_fictive_tree)=occurrences_table[i];
        if (i)
         { i--;
          WEIGHT_OF_TREE(ptr_fictive_tree) += WEIGHT_OF_TREE(occurrences_table[i]);
          RIGHTPTR_OF_TREE(ptr_fictive_tree)=occurrences_table[i];
         }
        else RIGHTPTR_OF_TREE(ptr_fictive_tree)=NULL;
        occurrences_table[i]=ptr_fictive_tree;
        (void)qsort((char *)occurrences_table,i+1,sizeof(p_tree),weight_tree_comp);
        if (i)    /* Is there an other node in the occurrence tables? */
         i++;    /* Yes, then takes care to the fictive node */
       }
   }
 return (*occurrences_table);
}

void encode_codes_table(tree,codes_table,code_val)
/* Returned parameters: The data of 'codes_table' can have been modified
  Action: Stores the encoding tree as a binary encoding table to speed up the access.
  'val_code' gives the encoding for the current node of the tree
  Errors: None
*/
p_tree tree;
t_bin_val codes_table[257],
     *code_val;
{ register unsigned int i;
 t_bin_val tmp_code_val;

 if (BYTE_OF_TREE(tree)==257)
   { if (LEFTPTR_OF_TREE(tree)!=NULL)
               /* The sub-trees on left begin with an bit set to 1 */
     { tmp_code_val = *code_val;
      for (i=31;i>0;i--)
        BITS_BIN_VAL(*code_val)[i]=(BITS_BIN_VAL(*code_val)[i] << 1)|(BITS_BIN_VAL(*code_val)[i-1] >> 7);
      *BITS_BIN_VAL(*code_val)=(*BITS_BIN_VAL(*code_val) << 1) | 1;
      BITS_NB_BIN_VAL(*code_val)++;
      encode_codes_table(LEFTPTR_OF_TREE(tree),codes_table,code_val);
      *code_val = tmp_code_val;
     };
    if (RIGHTPTR_OF_TREE(tree)!=NULL)
               /* The sub-trees on right begin with an bit set to 0 */
     { tmp_code_val = *code_val;
      for (i=31;i>0;i--)
        BITS_BIN_VAL(*code_val)[i]=(BITS_BIN_VAL(*code_val)[i] << 1)|(BITS_BIN_VAL(*code_val)[i-1] >> 7);
      *BITS_BIN_VAL(*code_val) <<= 1;
      BITS_NB_BIN_VAL(*code_val)++;
      encode_codes_table(RIGHTPTR_OF_TREE(tree),codes_table,code_val);
      *code_val = tmp_code_val;
     };
   }
 else codes_table[BYTE_OF_TREE(tree)] = *code_val;
}

void create_codes_table(tree,codes_table)
/* Returned parameters: The data in 'codes_table' will be modified
  Action: Stores the encoding tree as a binary encoding table to speed up the access by calling encode_codes_table
  Errors: None
*/
p_tree tree;
t_bin_val codes_table[257];
{ register unsigned int i;
 t_bin_val code_val;

 (void)memset((char *)&code_val,0,sizeof(code_val));
 (void)memset((char *)codes_table,0,257*sizeof(*codes_table));
 encode_codes_table(tree,codes_table,&code_val);
}

void huffmanencoding()
/* Returned parameters: None
  Action: Compresses with Huffman method all bytes read by the function 'read_byte'
  Errors: An input/output error could disturb the running of the program
*/
{ p_tree tree;
 t_bin_val encoding_table[257];
 unsigned char byte_read;

 if (!end_of_data())
               /* Generates only whether there are data */
   { tree=build_tree_encoding();
               /* Creation of the best adapted tree */
    create_codes_table(tree,encoding_table);
    suppress_tree(tree);
               /* Obtains the binary encoding in an array to speed up the accesses */
    write_header(encoding_table);
               /* Writes the defintion of the encoding */
    beginning_of_data(); /* Real compression of the data */
    while (!end_of_data())
       { byte_read=read_byte();
        write_bin_val(encoding_table[byte_read]);
       }
    write_bin_val(encoding_table[256]);
               /* Code of the end of encoding */
    fill_encoding();
               /* Fills the last byte before closing file, if any */
   }
}

void help()
/* 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 Huffman method\n");
 printf("as given in 'La Video et Les Imprimantes sur PC'\n");
 printf("\nUse: codhuff 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)
   { help();
    exit(BAD_ARGUMENT);
   }
 else if ((source_file=fopen(argv[1],"rb"))==NULL)
     { help();
      exit(BAD_FILE_NAME);
     }
    else if ((dest_file=fopen(argv[2],"wb"))==NULL)
        { help();
         exit(BAD_FILE_NAME);
        }
      else { huffmanencoding();
          fclose(source_file);
          fclose(dest_file);
         }
 printf("Execution of codhuff completed.\n");
 return (NO_ERROR);
}