/* huffman data compression */

/* header */
#include <stdio.h>
#include <stdlib.h>

/* define 64 Kbytes if too much usage unsigned long */
typedef unsigned int WORDCOUNT;
typedef unsigned char BYTE;
typedef int HANDLE;

struct BTREE{
	BYTE 		ch;
	WORDCOUNT 	count;
	struct BTREE *parentnode;
	struct BTREE *rightnode;
	struct BTREE *leftnode;
	};

void InitialBinaryTree (void);
void HuffmanCompress (FILE *,struct BTREE *, struct BTREE *);
void BitOutput (FILE *, HANDLE);
HANDLE BitInput (FILE *);
HANDLE HuffmanDecompress(FILE *, struct BTREE *);

/* --------------------------- HUFFC function  ----------------------------*/
/*-main program is assigned to the function of huffman compression file
 from source file

-A:\>huff <source file> <destination file>

*/
/* huff function */
/* demonstrate to initialize all huff structure, bit converter (0,1)
  and converted bit (0,1) */

struct BTREE huff[512];
struct BTREE *root;

void	InitialBinaryTree (void)
{
  int WORDLEN = 256;
  register i;

  while (1) {
    struct BTREE *h1 = NULL;
    struct BTREE *h2 = NULL;

    for (i=0; i < WORDLEN ; i++)
    {
       if (huff+i != h1) {
	if (huff[i].count > 0 && huff[i].parentnode == NULL) {
		if (h1 == NULL || huff[i].count < h1->count)   {
			if (h2 == NULL || huff[i].count < h2->count)
				h2 = h1;
			h1 = huff+i;
		}  /* if h1 */
		else
		   if (h2 == NULL || huff[i].count < h2->count)
				h2 = huff+i;
	} /* if huff[i] */
    }   /* if huff+i */
  } /* for */
  if (h2 == NULL )  {
    root = h1;
    break;
  }                  /* if h2 */
  h1->parentnode = huff+WORDLEN;
  h2->parentnode = huff+WORDLEN;
  huff[WORDLEN].count = h1->count+h2->count;
  huff[WORDLEN].rightnode = h1;
  huff[WORDLEN].leftnode  = h2;
  WORDLEN++;
  }                         /* while */
}	      /* InitialBinaryTree */

void	HuffmanCompress(FILE *fi,struct BTREE *btree,struct BTREE *child)
{
	if (btree->parentnode != NULL)
		HuffmanCompress (fi,btree->parentnode,btree);
	if (child)	{
		if (child == btree->rightnode)
			BitOutput(fi,0);
		else
		if (child == btree->leftnode)
			BitOutput(fi,1);
	}       /* if (child) */
}	/* HuffmanCompress */

static	BYTE	out8;
static	HANDLE	ct8;

void BitOutput(FILE *fi,HANDLE bit)
{
	if (ct8 == 8 || bit == -1)	{
		fputc(out8,fi);
		ct8 = 0;
	}
	out8 = (out8 << 1) | bit;
	ct8++;
} /* BitOutput */

static	BYTE	in8;
static	HANDLE	inct8 = 8;

HANDLE	BitInput(FILE *fi)
{
	HANDLE Obit;

	if(inct8 == 8)	{
		in8 = fgetc(fi);
		inct8 = 0;
	}
	Obit = in8 & 0x80;
	in8 <<= 1;
	inct8++;
	return(Obit);
}                /* BitInput */

HANDLE HuffmanDecompress(FILE *fi,struct BTREE *btree)
{
	while (btree->rightnode != NULL)
		if (BitInput(fi))
			btree=btree->leftnode;
		else  btree=btree->rightnode;
	return(btree->ch);
}                              /* huffman decompress */

		/* huffc */
huffc(FILE *infile, FILE *outfile)
{
    HANDLE c=0, freq=0;
    WORDCOUNT wordcount = 0;

    while ((c=fgetc(infile)) != EOF)     {
	c &= 255;
	if (huff[c].count == 0) 	{
		freq++;
		huff[c].ch = c;
	} /* if huff */
	huff[c].count++;
	wordcount++;
    } /* while c */
    fwrite(&wordcount,sizeof(wordcount),1,outfile);
    fwrite(&freq,sizeof(freq),1,outfile);
    for(c=0; c<256; c++)    {
	if (huff[c].count > 0)   {
		fwrite(&huff[c].ch,sizeof(char),1,outfile);
		fwrite(&huff[c].count,sizeof(WORDCOUNT),1,outfile);
	} /* if huff */
    } /* for c */
    InitialBinaryTree();
    fseek(infile,0L,0);
    while ((c=getc(infile)) != EOF)
	HuffmanCompress(outfile,huff+(c&255),NULL);
    BitOutput(outfile,-1);
} /* huffc */

err_exit(char *s1, char *s2)
{
   printf("%s %s",s1,s2); exit(1);
} /* err_exit */

/* dehuffc */


void dehuffc(FILE *infile, FILE * outfile)
{
	HANDLE c=0, freq = 0;
	WORDCOUNT wordcount = 0;

	fread(&wordcount,sizeof(wordcount),1,infile);
	fread(&freq,sizeof(freq),1,infile);
	while (freq--) 	{
		fread(&c,sizeof(char),1,infile);
		huff[c].ch = c;
		fread(&huff[c].count,sizeof(WORDCOUNT),1,infile);
	} /* while */
	InitialBinaryTree();
	while (wordcount--)
		fputc(HuffmanDecompress(infile,root),outfile);
} /* dehuffc */

/* ------------------ main program ----------------- */
void main (HANDLE argc , BYTE *argv[])
{
    FILE *infile, *outfile;

    printf("\nHuffman Compression Utility (version 1.0)");
    if (argc<4)
	err_exit("Usage : huff [-c] [-d] filein fileout\n","Try again\n");
    if ((infile = fopen(argv[2],"rb"))==NULL)
	err_exit("\nCan\'t open %s",argv[2]);
    if ((outfile = fopen(argv[3],"wb"))==NULL)
	err_exit("\nCan\'t open %s",argv[3]);
    if (strncmp(argv[1],"-c",2)==NULL)
	huffc(infile,outfile);
    else  if (strncmp(argv[1],"-d",2)==NULL)
	     dehuffc(infile,outfile);
	  else { printf("huff: option must be '-c' or '-d'.\n"); exit(-1); }
    fclose(infile);
    fclose(outfile);
}                       /* main program */