/* HUFFMAN DECODING PROG */

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

typedef unsigned int BYTECOUNTER;

struct htree {
	unsigned char ch;
	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 int decompress(FILE *fi,struct htree *root);

void main(int argc,char *argv[])
{
	FILE *fi,*fo;
	unsigned char c;
	BYTECOUNTER bytectr;
	int count;
	
	if (argc < 3) {
		printf("usage: huffd 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);
	}
	
	fread(&bytectr,sizeof bytectr,1,fi);
	
	for (count=0;count<256;count++) {
		c=fgetc(fi);
		ht[count].cnt=(BYTECOUNTER)c;
#ifdef DEBUG
		fprintf(stderr,"  %3u",ht[count].cnt);
#endif
		ht[count].ch=count;
	}
	
	buildtree();
	
	while (bytectr--)
		fputc(decompress(fi,root),fo);
	fclose(fo);
	fclose(fi);
}

static int in8;
static int ct8 = 8;

static int inbit(FILE *fi)
{
	int obit;
	if (ct8==8) {
		in8 = fgetc(fi);
		ct8 = 0;
	}
	obit = in8 & 0x80;
	in8 <<= 1;
	ct8++;
	return obit;
}

static int decompress(FILE *fi,struct htree *h)
{
	while (h->right != NULL)
		if (inbit(fi))
			h = h->left;
		else
			h = h->right;
	return h->ch;
}