Archive | Uncategorized RSS feed for this section

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

Hello world!

13 Oct

Welcome to WordPress.com! This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog and what you plan to do with it.

Happy blogging!