From 47de6c270a336574dce220cde780a802a513d113 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Fri, 2 Jan 2009 19:12:21 +0100 Subject: [PATCH] Port some table-generating stuff from unjpeg. --- Makefile | 8 +++- dehuff.c | 127 ++++++++++++++++++++++++++++++++++++++++++++++++++ dehuff.h | 34 ++++++++++++++ dehuff_test.c | 80 +++++++++++++++++++++++++++++++ 4 files changed, 248 insertions(+), 1 deletion(-) create mode 100644 dehuff.c create mode 100644 dehuff.h create mode 100644 dehuff_test.c diff --git a/Makefile b/Makefile index 7d9b6d0..ed0aab2 100644 --- 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) +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 diff --git a/dehuff.c b/dehuff.c new file mode 100644 index 0000000..3e0fd6c --- /dev/null +++ b/dehuff.c @@ -0,0 +1,127 @@ +#include +#include +#include + +#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 index 0000000..b79a79a --- /dev/null +++ b/dehuff.h @@ -0,0 +1,34 @@ +#ifndef _DEHUFF_H +#define _DEHUFF_H 1 + +#include +#include +#include + +// 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 index 0000000..e383a1d --- /dev/null +++ b/dehuff_test.c @@ -0,0 +1,80 @@ +#include +#include +#include + +#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; +} -- 2.39.2