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)
-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
+ $(RM) $(DEHUFF_TEST_OBJS) dehuff_test
test: tests
./unstuff_test
./input_test
+ ./dehuff_test
--- /dev/null
+#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);
+}
--- /dev/null
+#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) */
--- /dev/null
+#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;
+}