Simple Huffman Codec

13 Oct

#include “stdio.h”
#include “stdlib.h”
#include “memory.h”
#include “assert.h”

char const source[] = {“HHHTHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHTHHHTHHHTHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHTHHHHTHHHHTHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHHTHHHTHHHHTHHHTHHHHT”};

char const *dictionary[]={ {“THHHH”},{“HHHH”},{“HHH”},{“T”},{“H”}};        // in order of likelihood

int const dictionary_sz[]={5, 4, 3, 1, 1};        // sizes of each dictionary element

unsigned char dest[600];

int next_byte, next_bit = 1, bitcount;

void write_bit (int bit)
{
if (bit)
dest[next_byte] |= next_bit;

if (next_bit & 0x80) {

next_bit = 1;
next_byte ++;
}

else
next_bit <<= 1;

putchar (bit ? ‘1’ : ‘0’);

if (!bit)
putchar (‘ ‘);

bitcount ++;
}

int main()
{
// compress

char const *p = source;

while (*p) {

for (int dx=0; dx < 5; dx++) {

if (memcmp(p,dictionary[dx],dictionary_sz[dx]) == 0) {

for (int i=0; i < dx; i++)
write_bit(1);

write_bit(0);

p += dictionary_sz[dx];

break;
}
}

if (dx >= 5)
assert(dx < 5);
}

printf (“\n\nSource string bits = %d, Total compressed bits = %d\n\n”, sizeof(source), bitcount);

// decompress

next_byte = 0;
next_bit = 1;

while (bitcount) {

int dx = 0;

for (;;) {

int bit = dest[next_byte] & next_bit;

if (next_bit & 0x80) {

next_bit = 1;
next_byte ++;
}

else
next_bit <<= 1;

bitcount –;

if (bit)
dx ++;

else
break;
}

printf (dictionary[dx]);
}

putchar (‘\n’);

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: