Add an example huffman (variable code length) decoder

* configure.ac:
* examples/Makefile.am:
* examples/huffman/Makefile.am:
* examples/huffman/huffman.c: (huffman_new), (huffman_add_code),
(huffman_decode_iterate), (huffman_decode_ref):
* examples/huffman/huffman.h:
* examples/huffman/huffman_test.c: (main):

7 files changed, 173 insertions, 1 deletions

diff --git a/ChangeLog b/ChangeLog
index ed12680..45790e3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2005-04-28  David Schleef  <ds@schleef.org>
+
+	Add an example huffman (variable code length) decoder
+	* configure.ac:
+	* examples/Makefile.am:
+	* examples/huffman/Makefile.am:
+	* examples/huffman/huffman.c: (huffman_new), (huffman_add_code),
+	(huffman_decode_iterate), (huffman_decode_ref):
+	* examples/huffman/huffman.h:
+	* examples/huffman/huffman_test.c: (main):
+
 2005-04-26  David Schleef  <ds@schleef.org>
 
 	* configure.ac: version bump
diff --git a/configure.ac b/configure.ac
index cb4697b..f37c6a4 100644
--- a/configure.ac
+++ b/configure.ac
@@ -189,6 +189,7 @@ liboil/simdpack/Makefile
 liboil/utf8/Makefile
 testsuite/Makefile
 examples/Makefile
+examples/huffman/Makefile
 examples/jpeg/Makefile
 examples/md5/Makefile
 examples/uberopt/Makefile
diff --git a/examples/Makefile.am b/examples/Makefile.am
index ae1a990..cb2eae1 100644
--- a/examples/Makefile.am
+++ b/examples/Makefile.am
@@ -1,5 +1,5 @@
 
-SUBDIRS = jpeg md5 uberopt work
+SUBDIRS = jpeg md5 uberopt work huffman
 
 noinst_PROGRAMS = example1 oil-inspect
 
diff --git a/examples/huffman/Makefile.am b/examples/huffman/Makefile.am
new file mode 100644
index 0000000..f9d5be4
--- /dev/null
+++ b/examples/huffman/Makefile.am
@@ -0,0 +1,10 @@
+
+noinst_PROGRAMS = huffman_test
+
+huffman_test_SOURCES = \
+	huffman.c \
+	huffman.h \
+	huffman_test.c
+huffman_test_CFLAGS = $(LIBOIL_CFLAGS)
+huffman_test_LDFLAGS = $(LIBOIL_LDFLAGS)
+
diff --git a/examples/huffman/huffman.c b/examples/huffman/huffman.c
new file mode 100644
index 0000000..b1eee26
--- /dev/null
+++ b/examples/huffman/huffman.c
@@ -0,0 +1,84 @@
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "huffman.h"
+
+
+
+Huffman *
+huffman_new (void)
+{
+  Huffman *huff;
+
+  huff = malloc (sizeof (Huffman));
+  memset (huff, 0, sizeof(Huffman));
+
+  return huff;
+}
+
+
+void
+huffman_add_code (Huffman *huff, unsigned int code, int n_bits,
+    int value)
+{
+  huff->codes = realloc(huff->codes,
+      sizeof(HuffmanCode) * (huff->n_codes + 1));
+  huff->codes[huff->n_codes].value = value;
+  huff->codes[huff->n_codes].code = code << (32 - n_bits);
+  huff->codes[huff->n_codes].mask = 0xffffffff << (32 - n_bits);
+  huff->codes[huff->n_codes].n_bits = n_bits;
+
+  huff->n_codes++;
+}
+
+
+void huffman_decode_iterate (Huffman *huff)
+{
+  unsigned int bits;
+  int i;
+
+  if (huff->state == HUFF_NEED_BYTE) {
+    huff->state_bits = (huff->state_bits << 8) | huff->next_byte;
+    huff->state_n_bits += 8;
+  }
+
+  bits = huff->state_bits << (32 - huff->state_n_bits);
+
+  for(i=0;i<huff->n_codes;i++){
+    if (huff->codes[i].n_bits <= huff->state_n_bits &&
+        huff->codes[i].code == (bits & huff->codes[i].mask)) {
+      huff->out_value = huff->codes[i].value;
+      break;
+    }
+  }
+  if (i == huff->n_codes) {
+    huff->state = HUFF_NEED_BYTE;
+  } else {
+    huff->state = HUFF_OK;
+  }
+
+}
+
+void huffman_decode_ref (Huffman *huff, int *dest, unsigned char *src, int n)
+{
+  int i;
+
+  i = 0;
+  while(n>0 || huff->state == HUFF_OK){
+    printf("STATE %d\n", huff->state);
+    if (huff->state == HUFF_NEED_BYTE) {
+      printf("pushing byte %02x\n", *src);
+      huff->next_byte = *src;
+      src++;
+      n--;
+    }
+    huffman_decode_iterate (huff);
+    if (huff->state == HUFF_OK) {
+      printf("got value %d\n", huff->out_value);
+      dest[i] = huff->out_value;
+    }
+  }
+}
+
diff --git a/examples/huffman/huffman.h b/examples/huffman/huffman.h
new file mode 100644
index 0000000..e11ebf1
--- /dev/null
+++ b/examples/huffman/huffman.h
@@ -0,0 +1,53 @@
+
+#ifndef _HUFFMAN_H_
+#define _HUFFMAN_H_
+
+enum {
+  HUFF_OK = 0,
+  HUFF_NEED_BYTE
+};
+
+typedef struct _Huffman Huffman;
+typedef struct _HuffmanCode HuffmanCode;
+typedef struct _HuffmanTable HuffmanTable;
+typedef struct _HuffmanTableEntry HuffmanTableEntry;
+
+struct _Huffman {
+  int n_codes;
+  HuffmanCode *codes;
+  HuffmanTable *tables;
+
+  int state;
+  unsigned int state_bits;
+  int state_n_bits;
+
+  unsigned char next_byte;
+  int out_value;
+};
+
+struct _HuffmanCode {
+  unsigned int code;
+  unsigned int mask;
+  int n_bits;
+  int value;
+};
+
+struct _HuffmanTableEntry {
+  unsigned int codes[8];
+  int n_codes;
+  struct _HuffmanTable *next_table;
+};
+
+struct _HuffmanTable {
+  int n_bits;
+  unsigned int bits;
+  HuffmanTableEntry entries[256];
+};
+
+
+Huffman * huffman_new (void);
+void huffman_add_code (Huffman *huff, unsigned int code, int n_bits, int value);
+void huffman_decode_ref (Huffman *huff, int *dest, unsigned char *src, int n);
+
+#endif
+
diff --git a/examples/huffman/huffman_test.c b/examples/huffman/huffman_test.c
new file mode 100644
index 0000000..43e688b
--- /dev/null
+++ b/examples/huffman/huffman_test.c
@@ -0,0 +1,13 @@
+
+#include "huffman.h"
+#include <stdio.h>
+
+
+int
+main (int argc, char *argv[])
+{
+
+
+  return 0;
+}
+