Port some table-generating stuff from unjpeg.

diff --git a/Makefile b/Makefile
index 7d9b6d0e33657a21df69d4e56474cc53073603e3..ed0aab2a16703163c562dc1cbc8b4db7a734b8c3 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -12,13 +12,19 @@ INPUT_TEST_OBJS=input.o input_test.o
 input_test: $(INPUT_TEST_OBJS)
        $(CC) $(LDFLAGS) -o $@ $(INPUT_TEST_OBJS)
 
 input_test: $(INPUT_TEST_OBJS)
        $(CC) $(LDFLAGS) -o $@ $(INPUT_TEST_OBJS)
 

+DEHUFF_TEST_OBJS=dehuff.o dehuff_test.o
+dehuff_test: $(DEHUFF_TEST_OBJS)
+       $(CC) $(LDFLAGS) -o $@ $(DEHUFF_TEST_OBJS)
+

 OBJS=$(UNSTUFF_TEST_OBJS)
 
 OBJS=$(UNSTUFF_TEST_OBJS)
 

-tests: unstuff_test input_test
+tests: unstuff_test input_test dehuff_test

 clean:
        $(RM) $(UNSTUFF_TEST_OBJS) unstuff_test
        $(RM) $(INPUT_TEST_OBJS) input_test
 clean:
        $(RM) $(UNSTUFF_TEST_OBJS) unstuff_test
        $(RM) $(INPUT_TEST_OBJS) input_test

+       $(RM) $(DEHUFF_TEST_OBJS) dehuff_test

 
 test: tests
        ./unstuff_test
        ./input_test
 
 test: tests
        ./unstuff_test
        ./input_test

+       ./dehuff_test

diff --git a/dehuff.c b/dehuff.c
new file mode 100644 (file)
index 0000000..3e0fd6c
--- /dev/null
+++ b/dehuff.c
@@ -0,0 +1,127 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "dehuff.h"
+
+void reliable_read(raw_input_func_t* input_func, void* userdata, uint8_t* buf, size_t len)
+{
+       while (len > 0) {
+               ssize_t bytes_read = input_func(userdata, buf, len);
+               assert(bytes_read <= len);
+
+               // TODO: We need better error handling here. setjmp()/longjmp()
+               // should hopefully do the trick, but we need to take care for
+               // suspension.
+               if (bytes_read == (ssize_t)-1) {
+                       fprintf(stderr, "Input function returned error\n");
+                       exit(1);
+               }
+               if (bytes_read == 0) {
+                       fprintf(stderr, "Premature EOF\n");
+                       exit(1);
+               }
+
+               buf += bytes_read;
+               len -= bytes_read;
+       }
+}
+
+uint16_t read_length(raw_input_func_t* input_func, void* userdata)
+{
+       uint8_t buf[2];
+       reliable_read(input_func, userdata, buf, 2);
+       return (buf[0] << 8) | buf[1];
+}
+
+void read_huffman_tables(huffman_tables_t* dst, raw_input_func_t* input_func, void* userdata)
+{
+       size_t len = read_length(input_func, userdata);
+       assert(len > 2);
+       len -= 2;
+
+       // TODO: check for NULL return
+       uint8_t* buf = (uint8_t*)malloc(len);
+       uint8_t* inptr = buf;
+       reliable_read(input_func, userdata, buf, len);
+       
+       while (len > 0) {
+               unsigned char tc_th = *inptr++;
+               --len;
+               unsigned table_class = tc_th >> 4;
+               unsigned table_dest = tc_th & 0x0f;
+               
+               if (table_class != 0 && table_class != 1) {
+                       fprintf(stderr, "Error: Unknown table class %u\n", table_class);
+                       exit(1);
+               }
+               if (table_dest >= 4) {
+                       fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
+                       exit(1);
+               }
+
+               struct huffman_table* tbl = dst[table_class][table_dest];
+               if (len < 16) {
+                       fprintf(stderr, "Short read for num_codes\n");
+                       exit(1);
+               }
+               for (unsigned i = 0; i < 16; ++i) {
+                       tbl->num_codes[i] = *inptr++;
+                       --len;
+               }
+               for (unsigned i = 0, k = 0; i < 16; ++i) {
+                       if (len < tbl->num_codes[i]) {
+                               fprintf(stderr, "Short read for codes\n");
+                               exit(1);
+                       }
+                       for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
+                               tbl->codes[k] = *inptr++;
+                               --len;
+                       }
+               }
+
+               // Generate derived tables
+
+               // generate_size_table (figure C.1)
+               {
+                       unsigned k = 0;
+                       for (unsigned i = 0; i < 16; ++i) {
+                               for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
+                                       tbl->huffsize[k] = i + 1;
+                               }
+                       }
+                       tbl->huffsize[k] = 0;
+               }
+
+               // generate_code_table (figure C.2)
+               unsigned si = tbl->huffsize[0];
+               for (unsigned i = 0, j = 0;; ) {
+                       tbl->huffcode[i++] = j++;
+                       if (tbl->huffsize[i] == si) {
+                               continue;
+                       }
+                       if (tbl->huffsize[i] == 0) {
+                               break;
+                       }
+
+                       do {
+                               j <<= 1;
+                       } while (++si != tbl->huffsize[i]);
+               }
+
+               // decoder_tables (figure F.15)
+               for (unsigned i = 0, j = 0; i < 16; ++i) {
+                       if (tbl->num_codes[i] == 0) {
+                               tbl->maxcode[i] = -1;
+                               continue;
+                       }
+
+                       tbl->valptr[i] = j;
+                       tbl->mincode[i] = tbl->huffcode[j];
+                       j += tbl->num_codes[i];
+                       tbl->maxcode[i] = tbl->huffcode[j - 1];
+               }
+       }
+
+       free(buf);
+}

diff --git a/dehuff.h b/dehuff.h
new file mode 100644 (file)
index 0000000..b79a79a
--- /dev/null
+++ b/dehuff.h
@@ -0,0 +1,34 @@
+#ifndef _DEHUFF_H
+#define _DEHUFF_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+// A function to read bytes from some input source. The bytes should be
+// already unstuffed (and thus without markers).
+// A return value of -1 indicates error, a return value of 0 indicates EOF.
+typedef ssize_t (raw_input_func_t)(void*, uint8_t*, size_t);
+
+struct huffman_table {
+       unsigned num_codes[17];     // BITS
+       unsigned char codes[256];   // HUFFVAL
+       
+       // Derived values.
+       unsigned huffsize[256];
+       unsigned huffcode[256];
+       int maxcode[16];
+       int mincode[16];
+       unsigned valptr[16];
+};
+
+enum coefficient_class {
+       DC_CLASS = 0,
+       AC_CLASS,
+       NUM_COEFF_CLASSES
+};
+typedef struct huffman_table huffman_tables_t[NUM_COEFF_CLASSES][4];
+
+void read_huffman_tables(huffman_tables_t* dst, raw_input_func_t* input_func, void* userdata);
+
+#endif /* !defined(_DEHUFF_H) */

diff --git a/dehuff_test.c b/dehuff_test.c
new file mode 100644 (file)
index 0000000..e383a1d
--- /dev/null
+++ b/dehuff_test.c
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+
+#include "dehuff.h"
+
+struct custom_read_userdata {
+       uint8_t* bytes;
+       unsigned bytes_left;
+};
+
+ssize_t custom_read(void* userdata, uint8_t* buf, size_t count)
+{
+       struct custom_read_userdata* ud = (struct custom_read_userdata*)userdata;
+       size_t num_to_read = (ud->bytes_left > count ? count : ud->bytes_left);
+       memcpy(buf, ud->bytes, num_to_read);
+       ud->bytes += num_to_read;
+       ud->bytes_left -= num_to_read;
+       return num_to_read;     
+}
+
+// Uses the example from section K.3.1 from the JPEG standard.
+void test_table_gen()
+{
+       uint8_t bytes[] = {
+               // Chunk length: Chunk length (2) + coefficient class (1) + 
+               // code lengths (16) + code words (12)
+               0, 31, 
+
+               // DC coefficient, table 0
+               0x00,
+
+               // List of code lengths
+               0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+
+               // Code words
+               0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,
+       };
+
+       // Expected results (table K.3)
+       struct {
+               unsigned code_length;
+               unsigned code_word;
+       } expected_table[12] = {
+               { 2, 0x0 },
+               { 3, 0x2 },
+               { 3, 0x3 },
+               { 3, 0x4 },
+               { 3, 0x5 },
+               { 3, 0x6 },
+               { 4, 0xe },
+               { 5, 0x1e },
+               { 6, 0x3e },
+               { 7, 0x7e },
+               { 8, 0xfe },
+               { 9, 0x1fe },
+       };
+
+       struct custom_read_userdata ud;
+       ud.bytes = bytes;
+       ud.bytes_left = sizeof(bytes);
+
+       huffman_tables_t tables;
+       read_huffman_tables(&tables, custom_read, &ud);
+               
+       struct huffman_table* tbl = &tables[DC_CLASS][0];       
+       for (unsigned i = 0; i < 12; ++i) {
+               assert(tbl->huffsize[i] == expected_table[i].code_length);
+               assert(tbl->huffcode[i] == expected_table[i].code_word);
+       }
+}
+
+int main(void)
+{
+       printf("test_table_gen()\n");
+       test_table_gen();
+       
+       printf("All tests pass.\n");
+       return 0;
+}