5 #include "bytesource.h"
9 void read_huffman_tables(huffman_tables_t* dst, input_func_t* input_func, void* userdata)
11 size_t len = read_uint16(input_func, userdata);
15 // TODO: check for NULL return
16 uint8_t* buf = (uint8_t*)malloc(len);
18 reliable_read(input_func, userdata, buf, len);
21 unsigned char tc_th = *inptr++;
23 unsigned table_class = tc_th >> 4;
24 unsigned table_dest = tc_th & 0x0f;
26 if (table_class != 0 && table_class != 1) {
27 fprintf(stderr, "Error: Unknown table class %u\n", table_class);
30 if (table_dest >= 4) {
31 fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
35 struct huffman_table* tbl = &((*dst)[table_class][table_dest]);
37 fprintf(stderr, "Short read for num_codes\n");
40 for (unsigned i = 0; i < 16; ++i) {
41 tbl->num_codes[i] = *inptr++;
44 for (unsigned i = 0, k = 0; i < 16; ++i) {
45 if (len < tbl->num_codes[i]) {
46 fprintf(stderr, "Short read for codes\n");
49 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
50 tbl->codes[k] = *inptr++;
55 // Generate derived tables
57 // generate_size_table (figure C.1)
60 for (unsigned i = 0; i < 16; ++i) {
61 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
62 tbl->huffsize[k] = i + 1;
68 // generate_code_table (figure C.2)
69 unsigned si = tbl->huffsize[0];
70 for (unsigned i = 0, j = 0;; ) {
71 tbl->huffcode[i++] = j++;
72 if (tbl->huffsize[i] == si) {
75 if (tbl->huffsize[i] == 0) {
81 } while (++si != tbl->huffsize[i]);
84 // decoder_tables (figure F.15)
85 for (unsigned i = 0, j = 0; i < 16; ++i) {
86 if (tbl->num_codes[i] == 0) {
92 tbl->mincode[i] = tbl->huffcode[j];
93 j += tbl->num_codes[i];
94 tbl->maxcode[i] = tbl->huffcode[j - 1];
97 // Generate the lookup tables
98 for (unsigned i = 0; i < DEHUF_TABLE_SIZE; ++i) {
99 tbl->lookup_table_codes[i] = DEHUF_SLOW_PATH;
100 tbl->lookup_table_length[i] = DEHUF_SLOW_PATH;
104 for (unsigned i = 0; i < 16; ++i) {
105 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
106 const unsigned code = tbl->huffcode[k];
107 const unsigned length = tbl->huffsize[k];
108 if (length > DEHUF_TABLE_BITS) {
111 const unsigned prefix_min = code << (DEHUF_TABLE_BITS - length);
112 const unsigned prefix_max = ((code + 1) << (DEHUF_TABLE_BITS - length));
114 for (unsigned elem = prefix_min; elem < prefix_max; ++elem) {
115 assert(tbl->lookup_table_codes[elem] == DEHUF_SLOW_PATH);
116 assert(tbl->lookup_table_length[elem] == DEHUF_SLOW_PATH);
117 tbl->lookup_table_codes[elem] = tbl->codes[k];
118 tbl->lookup_table_length[elem] = length;
127 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
128 struct bit_source* source) {
129 possibly_refill(source, 1);
130 unsigned code = read_bits(source, 1);
133 while (table->maxcode[i] == -1 || code > (unsigned)table->maxcode[i]) {
134 possibly_refill(source, 1);
135 code = (code << 1) | read_bits(source, 1);
139 fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
144 return table->codes[table->valptr[i] + code - table->mincode[i]];