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;
123 // Generate the AC lookup tables.
124 for (unsigned i = 0; i < DEHUF_AC_TABLE_SIZE; ++i) {
125 tbl->ac_table_codes[i] = AC_DEHUF_SLOW_PATH;
127 int lookup = i >> (DEHUF_AC_TABLE_BITS - DEHUF_TABLE_BITS);
128 int rs = tbl->lookup_table_codes[lookup];
129 unsigned length = tbl->lookup_table_length[lookup];
130 if (rs == DEHUF_SLOW_PATH) {
131 // Not enough bits to decode even the length.
136 tbl->ac_table_codes[i] = AC_END_OF_BLOCK;
137 tbl->ac_table_length[i] = length;
138 tbl->ac_table_skip[i] = 1;
142 // 16 zero coefficients.
143 tbl->ac_table_codes[i] = AC_SIXTEEN_ZEROS;
144 tbl->ac_table_length[i] = length;
145 tbl->ac_table_skip[i] = 16;
149 unsigned r = rs >> 4;
150 unsigned s = rs & 0xf;
151 if (s > DEHUF_AC_TABLE_BITS - length) {
152 // Not enough bits to decode this coefficient.
156 unsigned bits = (i >> (DEHUF_AC_TABLE_BITS - length - s)) & ((1 << s) - 1);
158 tbl->ac_table_codes[i] = extend(bits, s);
159 tbl->ac_table_length[i] = length + s;
160 tbl->ac_table_skip[i] = r + 1;
162 assert(tbl->ac_table_length[i] <= DEHUF_AC_TABLE_BITS);
169 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
170 struct bit_source* source) {
171 possibly_refill(source, 1);
172 unsigned code = read_bits(source, 1);
175 while (table->maxcode[i] == -1 || code > (unsigned)table->maxcode[i]) {
176 possibly_refill(source, 1);
177 code = (code << 1) | read_bits(source, 1);
181 fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
186 return table->codes[table->valptr[i] + code - table->mincode[i]];