/* HUFFMAN ENCODING PROG */

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int BYTECOUNTER;

struct htree {
	BYTECOUNTER cnt;
	struct htree *parent;
	struct htree *right;
	struct htree *left;
};

struct htree ht[512];
struct htree *root;

void buildtree(void)
{
	int treect = 256;
	int i;
	
	while (1) {
		struct htree *h1 = NULL, *h2 = NULL;
		
		for (i=0; i<treect; i++) {
			if (ht+i != h1) {
				if (ht[i].cnt>0 && ht[i].parent == NULL) {
					if (h1==NULL || ht[i].cnt<h1->cnt) {
						if (h2==NULL || h1->cnt<h2->cnt)
							h2 = h1;
						h1 = ht+i;
					}
					else if (h2==NULL || ht[i].cnt <h2->cnt)
						h2 = ht+i;
				}
			}
		}
		if (h2==NULL) {
			root = h1;
			break;
		}
		h1->parent = ht+treect;
		h2->parent = ht+treect;
		ht[treect].cnt = h1->cnt + h2->cnt;
		ht[treect].right = h1;
		ht[treect].left = h2;
		treect++;
	}
}
	
static void compress(FILE *fo, struct htree *h, struct htree *child);
static void outbit(FILE *fo, int bit);

void main(int argc, char *argv[])
{
	FILE *fi,*fo;
	int c;
	BYTECOUNTER bytectr = 0;
	int maxx = 0;
	
	if (argc<3) {
		printf("usage : huffc infile outfile\n");
		exit(1);
	}
	
	if ((fi=fopen(argv[1],"rb"))==NULL) {
		printf("Cannot open input file %s\n",argv[1]);
		exit(1);
	}
	
	if ((fo=fopen(argv[2],"wb"))==NULL) {
		printf("Cannot open output file %s\n",argv[2]);
		exit(1);
	}
	
	while ((c=fgetc(fi)) != EOF) {
		c &= 255;
		ht[c].cnt++;
		bytectr++;
	}
	
	fwrite (&bytectr,sizeof bytectr,1,fo);
	
	for (c=0;c<256;c++)
		if (ht[c].cnt>maxx) maxx=ht[c].cnt;
			
	for (c=0;c<256;c++) {
		if (ht[c].cnt>0)
			ht[c].cnt=((ht[c].cnt*254)/maxx)+1;
		fputc((unsigned char)ht[c].cnt,fo);
#ifdef DEBUG
		fprintf(stderr,"  %3u",ht[c].cnt);
#endif
	}
	
	buildtree();
	
	fseek(fi,0L,0);
	while ((c=fgetc(fi)) != EOF)
		compress(fo,ht+(c&255),NULL);
	for (c=0;c<8;c++) outbit(fo,0);
	fclose(fi);
	fclose(fo);
}

static void compress(FILE *fo,struct htree *h,struct htree *child)
{
	if (h->parent != NULL)
		compress(fo,h->parent,h);
	if (child) {
		if (child==h->right)
			outbit(fo,0);
		else if (child == h->left)
			outbit(fo,1);
	}
}

static char out8;
static int ct8;

static void outbit(FILE *fo, int bit)
{
	if (ct8==8) {
		fputc(out8,fo);
		ct8=0;
	}
	out8=(out8<<1) | bit;
	ct8++;
}