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


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;

#include	"tiny.h"

/* Global variables */
u_char	*srce_p;						/* ptr to data to be compressed */
u_char	*start_p;						/* ptr to the same as above, for when file data is read a 2nd time */
u_char	*end_p;							/* ptr to last byte of uncompressed data */
u_char	*dest_p;						/* ptr to buffer for compressed data */

int	buflen = 0;					/* to test compressed data isn't greater then original */
int	errval = 0;						/* errval is returned if malloc fails (T_MEM_ERROR) */
int	bytecount = 0;						/* if no errors, number of bytes written is returned */



void	quicksort(p_tree array[], int	left, int right);


#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()  (srce_p = start_p)
#define end_of_data()  		(((srce_p > end_p) || (bytecount > buflen)))
#define read_byte() 			(*(srce_p++))
#define write_byte(byte)  { ((*dest_p++) = (byte)); (bytecount++); }

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]);
             
							errval = T_MEM_ERROR;
							return NULL;
           }

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

			
			quicksort(occurrences_table,0,257-1); /* don't use qsort */

		// (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]);
										
										errval = T_MEM_ERROR;
										return NULL;
                  }


               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;
								
							 quicksort(occurrences_table,0,i);  /* don't use qsort */

            //   (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((u_char *)&code_val,0,sizeof(code_val));
  (void)memset((u_char *)codes_table,0,257*sizeof(*codes_table));
  encode_codes_table(tree,codes_table,&code_val);
}

int 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 */
     { if(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 */
       }
     }

	if(bytecount > buflen)		/* compressed data larger than original */
		errval = T_BUF_ERROR;

	if(errval)								
		return errval;				/* error occurred */
	else
		return bytecount;				/* size of compressed data */
}

//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);
}
*/



/* Replacement quick sort routine, qsort() crashing on yaroze */
void	quicksort(p_tree array[], int	low, int hi)
{
	int			left,right;
	u_int		pivot_val;
	p_tree	temp;
	
	/* get comparand value */
	if(low == hi)
		pivot_val = array[low]->weight;
	else
		pivot_val = array[(low + hi) / 2]->weight;

	left = low;
	right = hi;

	do
	{
		/* step through checking greater values are on left side */
		while((left <= hi) && (array[left]->weight > pivot_val))
			left++;

		/* lesser values on right side */
		while((right >= low) && (array[right]->weight < pivot_val))
			right--;
		
		if(left <= right)		/* switch values to correct sides */
		{
			temp = array[left];

			array[left] = array[right];
			array[right] = temp;

			left++;
			right--;
		}
	}while(left <= right);

	/* recursive sort of each partition */
	if(right > low)
		quicksort(array, low, right);

	if(left < hi)
		quicksort(array, left, hi);
}