I forgot where my previous huffman implementations are hidden, so
had to make a new one to test something, hope somebody would find
it useful.
Code:
#include <stdio.h>
const int CNUM=256;
int freq[2*CNUM], freq1[CNUM], p[2*CNUM][2], cl[CNUM];
char code[CNUM];
void DumpCode( int c, int i=0 ) {
if( c<CNUM ) {
code[i]=0; cl[c]=i;
printf( "%02X <%s>\n", c, code );
} else {
code[i]='0'; DumpCode( p[c][0], i+1 );
code[i]='1'; DumpCode( p[c][1], i+1 );
}
}
int main( int argc, char** argv ) {
int c,i,j,n,m,mi;
FILE* f = fopen( "book1", "rb" ); if( f==0 ) return 1;
// get symbol freqs
for( i=0; i<CNUM; i++ ) freq1[i]=0;
for(; (c=getc(f))!=-1; freq1[c]++ );
for( i=0; i<CNUM; i++ ) freq[i]=freq1[i];
for( n=CNUM,mi=0; mi>=0; n++ ) {
freq[n] = 0;
for( j=0; j<2; j++ ) {
for( i=0,mi=-1; i<n; i++ ) if( (freq[i]>0) && ((mi<0)||(freq[i]<m)) ) m=freq[i],mi=i;
if( mi>=0 ) freq[n]+=freq[mi], freq[mi]=0, p[n][j]=mi;
}
}
DumpCode( p[n-1][0] );
int sum = 0;
for( i=0; i<n; i++ ) sum += freq1[i]*cl[i];
printf( "codelength = %i bits = %i bytes\n", sum, (sum+7)>>3 );
return 0;
}