huffman.c

Implementation of Huffman code in C

/*
 * Definition for Huffman coding 
 *
 * vim: ts=4 sw=4 cindent nowrap
 */
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"

typedef struct{
	unsigned long count;
	int parent, lchild, rchild;
} HNODE;
HNODE hTree[512];
typedef struct{
	unsigned long code;
	int codelength;
} HCODE;
HCODE hCode[256];
unsigned long counts[256];

void BuildCounts( FILE *fp);
int BuildTree( void);
void BuildCode( void);
void HuffmanEncode( FILE *fp, BITFILE *bf);
void HuffmanDecode( BITFILE *bf, FILE *fp);

void BuildCounts( FILE *fp){
	int c;
	for( c=0; c<256; c++) counts[c] = 0;
	while( EOF!=(c=fgetc(fp))) counts[c]++;
}

int BuildTree( void){
	int i;
	int min1, min2, nextfree;
	for( i=0; i<256; i++){
		hTree[i].count = counts[i];
		hTree[i].parent = 0;
		hTree[i].lchild = 0;
		hTree[i].rchild = 0;
	}
	for( i=256; i<512; i++){
		hTree[i].count = 0;
		hTree[i].parent = 0;
		hTree[i].lchild = 0;
		hTree[i].rchild = 0;
	}
	hTree[511].count = 0xFFFFFFFFL;
	nextfree = 256;
	for( ;;nextfree++){
		min1=min2=511;
		for( i=0; i<nextfree; i++){
			if( 0<hTree[i].count && 0==hTree[i].parent){ // free node
				// update min1,min2, for min1, min2 and i
				if( hTree[i].count < hTree[min1].count){
					min2=min1;
					min1=i;
				}else if( hTree[i].count < hTree[min2].count){
					min2=i;
				}
			}
		}
		if( 511==min2)  break;  //done if only one node left( the root)
		// now min1,min2 are the least weighted nodes before nextfree
		// update nextfree as parents of min1,min2
		hTree[nextfree].count = hTree[min1].count + hTree[min2].count;
		hTree[nextfree].lchild = min1;
		hTree[nextfree].rchild = min2;
		// min1 and min2 need to be updated too
		hTree[min1].parent = nextfree;
		hTree[min2].parent = nextfree;
	}
	nextfree --;
	return nextfree;
}

void BuildCode( void){
	unsigned long code;
	unsigned long mask;
	int n, codelength;
	int currentNode, parentNode;
	for( n=0; n<256; n++){
		codelength = 0;
		code = 0;
		mask = 1;
		for( currentNode=n, parentNode=hTree[currentNode].parent; 
				0!=parentNode; 
				currentNode=parentNode, parentNode=hTree[parentNode].parent){
			if( currentNode == hTree[parentNode].rchild)
				code |= mask;
			mask <<= 1;
			codelength++;
		}
		hCode[n].code = code;
		hCode[n].codelength = codelength;
	}
}

void HuffmanEncode( FILE *fp, BITFILE *bf){
	unsigned long filelength;
	int i;
	BuildCounts( fp);
	fseek( fp, 0, SEEK_END);
	filelength = ftell( fp);
	BitsOutput( bf, filelength, 4*8);
	for( i=0; i<256; i++) BitsOutput( bf, counts[i], 4*8);
	BuildTree( );
	BuildCode( );
	fseek( fp, 0, SEEK_SET);
	while( EOF!=(i=fgetc(fp))){
		BitsOutput( bf, hCode[i].code, hCode[i].codelength);
	}
}

void HuffmanDecode( BITFILE *bf, FILE *fp){
	unsigned long filelength;
	int i;
	int rootNode;
	int node;

	filelength = BitsInput( bf, 4*8);
	if( -1 == filelength) filelength = 0;
	// reading the counts
	for( i=0; i<256; i++) counts[i] = BitsInput( bf, 4*8);
	rootNode = BuildTree( );
	while( 0<filelength){
		node = rootNode;
		do{
			if( 0 == BitInput( bf)) node = hTree[node].lchild;
			else node = hTree[node].rchild;
		}while( 255<node);
		fputc( node, fp);
		filelength --;
	}
}

int main( int argc, char **argv){
	FILE *fp;
	BITFILE *bf;

	if( 4>argc){
		fprintf( stdout, "usage: %s <o> <ifile> <ofile>\n", argv[0]);
		fprintf( stdout, "\t<o>: E or D reffers encode or decode\n");
		fprintf( stdout, "\t<ifile>: input file name\n");
		fprintf( stdout, "\t<ofile>: output file name\n");
		return -1;
	}
	if( 'E' == argv[1][0]){ // do encoding
		fp = fopen( argv[2], "rb");
		bf = OpenBitFileOutput( argv[3]);
		if( NULL!=fp && NULL!=bf){
			HuffmanEncode( fp, bf);
			fclose( fp);
			CloseBitFileOutput( bf);
			fprintf( stdout, "encoding done\n");
		}
	}else if( 'D' == argv[1][0]){	// do decoding
		bf = OpenBitFileInput( argv[2]);
		fp = fopen( argv[3], "wb");
		if( NULL!=fp && NULL!=bf){
			HuffmanDecode( bf, fp);
			fclose( fp);
			CloseBitFileInput( bf);
			fprintf( stdout, "decoding done\n");
		}
	}else{	// otherwise
		fprintf( stderr, "not supported operation\n");
	}
	return 0;
}