Some asm() correction.
[fjl] / dehuff.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4
5 #include "bytesource.h"
6 #include "dehuff.h"
7 #include "input.h"
8
9 void read_huffman_tables(huffman_tables_t* dst, input_func_t* input_func, void* userdata)
10 {
11         size_t len = read_uint16(input_func, userdata);
12         assert(len > 2);
13         len -= 2;
14
15         // TODO: check for NULL return
16         uint8_t* buf = (uint8_t*)malloc(len);
17         uint8_t* inptr = buf;
18         reliable_read(input_func, userdata, buf, len);
19         
20         while (len > 0) {
21                 unsigned char tc_th = *inptr++;
22                 --len;
23                 unsigned table_class = tc_th >> 4;
24                 unsigned table_dest = tc_th & 0x0f;
25                 
26                 if (table_class != 0 && table_class != 1) {
27                         fprintf(stderr, "Error: Unknown table class %u\n", table_class);
28                         exit(1);
29                 }
30                 if (table_dest >= 4) {
31                         fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
32                         exit(1);
33                 }
34
35                 struct huffman_table* tbl = &((*dst)[table_class][table_dest]);
36                 if (len < 16) {
37                         fprintf(stderr, "Short read for num_codes\n");
38                         exit(1);
39                 }
40                 for (unsigned i = 0; i < 16; ++i) {
41                         tbl->num_codes[i] = *inptr++;
42                         --len;
43                 }
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");
47                                 exit(1);
48                         }
49                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
50                                 tbl->codes[k] = *inptr++;
51                                 --len;
52                         }
53                 }
54
55                 // Generate derived tables
56
57                 // generate_size_table (figure C.1)
58                 {
59                         unsigned k = 0;
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;
63                                 }
64                         }
65                         tbl->huffsize[k] = 0;
66                 }
67
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) {
73                                 continue;
74                         }
75                         if (tbl->huffsize[i] == 0) {
76                                 break;
77                         }
78
79                         do {
80                                 j <<= 1;
81                         } while (++si != tbl->huffsize[i]);
82                 }
83
84                 // decoder_tables (figure F.15)
85                 for (unsigned i = 0, j = 0; i < 16; ++i) {
86                         if (tbl->num_codes[i] == 0) {
87                                 tbl->maxcode[i] = -1;
88                                 continue;
89                         }
90
91                         tbl->valptr[i] = j;
92                         tbl->mincode[i] = tbl->huffcode[j];
93                         j += tbl->num_codes[i];
94                         tbl->maxcode[i] = tbl->huffcode[j - 1];
95                 }
96
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;
101                 }
102         
103                 unsigned k = 0; 
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) {
109                                         continue;
110                                 }
111                                 const unsigned prefix_min = code << (DEHUF_TABLE_BITS - length);
112                                 const unsigned prefix_max = ((code + 1) << (DEHUF_TABLE_BITS - length));
113
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;
119                                 }
120                         }
121                 }       
122         }
123
124         free(buf);
125 }
126
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);
131         int i = 0;
132
133         while (table->maxcode[i] == -1 || code > (unsigned)table->maxcode[i]) {
134                 possibly_refill(source, 1);
135                 code = (code << 1) | read_bits(source, 1);
136                 ++i;
137
138                 if (i > 15) {
139                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
140                         exit(1);
141                 }
142         }
143
144         return table->codes[table->valptr[i] + code - table->mincode[i]];
145 }