]> git.sesse.net Git - fjl/blob - dehuff.c
Enable -Wall -Wextra.
[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
8 void reliable_read(raw_input_func_t* input_func, void* userdata, uint8_t* buf, size_t len)
9 {
10         while (len > 0) {
11                 ssize_t bytes_read = input_func(userdata, buf, len);
12                 assert(bytes_read <= len);
13
14                 // TODO: We need better error handling here. setjmp()/longjmp()
15                 // should hopefully do the trick, but we need to take care for
16                 // suspension.
17                 if (bytes_read == (ssize_t)-1) {
18                         fprintf(stderr, "Input function returned error\n");
19                         exit(1);
20                 }
21                 if (bytes_read == 0) {
22                         fprintf(stderr, "Premature EOF\n");
23                         exit(1);
24                 }
25
26                 buf += bytes_read;
27                 len -= bytes_read;
28         }
29 }
30
31 uint16_t read_length(raw_input_func_t* input_func, void* userdata)
32 {
33         uint8_t buf[2];
34         reliable_read(input_func, userdata, buf, 2);
35         return (buf[0] << 8) | buf[1];
36 }
37
38 void read_huffman_tables(huffman_tables_t* dst, raw_input_func_t* input_func, void* userdata)
39 {
40         size_t len = read_length(input_func, userdata);
41         assert(len > 2);
42         len -= 2;
43
44         // TODO: check for NULL return
45         uint8_t* buf = (uint8_t*)malloc(len);
46         uint8_t* inptr = buf;
47         reliable_read(input_func, userdata, buf, len);
48         
49         while (len > 0) {
50                 unsigned char tc_th = *inptr++;
51                 --len;
52                 unsigned table_class = tc_th >> 4;
53                 unsigned table_dest = tc_th & 0x0f;
54                 
55                 if (table_class != 0 && table_class != 1) {
56                         fprintf(stderr, "Error: Unknown table class %u\n", table_class);
57                         exit(1);
58                 }
59                 if (table_dest >= 4) {
60                         fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
61                         exit(1);
62                 }
63
64                 struct huffman_table* tbl = dst[table_class][table_dest];
65                 if (len < 16) {
66                         fprintf(stderr, "Short read for num_codes\n");
67                         exit(1);
68                 }
69                 for (unsigned i = 0; i < 16; ++i) {
70                         tbl->num_codes[i] = *inptr++;
71                         --len;
72                 }
73                 for (unsigned i = 0, k = 0; i < 16; ++i) {
74                         if (len < tbl->num_codes[i]) {
75                                 fprintf(stderr, "Short read for codes\n");
76                                 exit(1);
77                         }
78                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
79                                 tbl->codes[k] = *inptr++;
80                                 --len;
81                         }
82                 }
83
84                 // Generate derived tables
85
86                 // generate_size_table (figure C.1)
87                 {
88                         unsigned k = 0;
89                         for (unsigned i = 0; i < 16; ++i) {
90                                 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
91                                         tbl->huffsize[k] = i + 1;
92                                 }
93                         }
94                         tbl->huffsize[k] = 0;
95                 }
96
97                 // generate_code_table (figure C.2)
98                 unsigned si = tbl->huffsize[0];
99                 for (unsigned i = 0, j = 0;; ) {
100                         tbl->huffcode[i++] = j++;
101                         if (tbl->huffsize[i] == si) {
102                                 continue;
103                         }
104                         if (tbl->huffsize[i] == 0) {
105                                 break;
106                         }
107
108                         do {
109                                 j <<= 1;
110                         } while (++si != tbl->huffsize[i]);
111                 }
112
113                 // decoder_tables (figure F.15)
114                 for (unsigned i = 0, j = 0; i < 16; ++i) {
115                         if (tbl->num_codes[i] == 0) {
116                                 tbl->maxcode[i] = -1;
117                                 continue;
118                         }
119
120                         tbl->valptr[i] = j;
121                         tbl->mincode[i] = tbl->huffcode[j];
122                         j += tbl->num_codes[i];
123                         tbl->maxcode[i] = tbl->huffcode[j - 1];
124                 }
125
126                 // Generate the lookup tables
127                 for (unsigned i = 0; i < DEHUF_TABLE_SIZE; ++i) {
128                         tbl->lookup_table_codes[i] = DEHUF_SLOW_PATH;
129                         tbl->lookup_table_length[i] = DEHUF_SLOW_PATH;
130                 }
131         
132                 unsigned k = 0; 
133                 for (unsigned i = 0; i < 16; ++i) {
134                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
135                                 const unsigned code = tbl->huffcode[k];
136                                 const unsigned length = tbl->huffsize[k];
137                                 if (length > DEHUF_TABLE_BITS) {
138                                         continue;
139                                 }
140                                 const unsigned prefix_min = code << (DEHUF_TABLE_BITS - length);
141                                 const unsigned prefix_max = ((code + 1) << (DEHUF_TABLE_BITS - length));
142
143                                 for (unsigned elem = prefix_min; elem < prefix_max; ++elem) {
144                                         assert(tbl->lookup_table_codes[elem] == DEHUF_SLOW_PATH);
145                                         assert(tbl->lookup_table_length[elem] == DEHUF_SLOW_PATH);
146                                         tbl->lookup_table_codes[elem] = k;
147                                         tbl->lookup_table_length[elem] = length;
148                                 }
149                         }
150                 }       
151         }
152
153         free(buf);
154 }
155
156 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
157                                        struct bit_source* source) {
158         possibly_refill(source, 1);
159         unsigned code = read_bits(source, 1);
160         int i = 0;
161
162         while (code > table->maxcode[i] || table->maxcode[i] == -1) {
163                 possibly_refill(source, 1);
164                 code = (code << 1) | read_bits(source, 1);
165                 ++i;
166
167                 if (i > 15) {
168                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
169                         exit(1);
170                 }
171         }
172
173         return table->codes[table->valptr[i] + code - table->mincode[i]];
174 }