1 /*
2 * Copyright 2020 Ondrej Zary <ondrej@zary.sk>
3 * based on Docupen tools (C) 2008 Florian Heinz <fh@cronon-ag.de>
4 * based on code found in package sfftobmp (Thanks Peter!)
5 */
6
7 #include <stdlib.h>
8 #include <string.h>
9 #include "huffman.h"
10
11 struct huffman {
12 unsigned short code;
13 int len;
14 unsigned char bits;
15 };
16
17 #define NOT_FOUND -1
18 #define RL_EOL -2
19 struct huffman black[], white[], blackterm[], whiteterm[];
20
skip(struct decoder * d,int nrbits)21 static void skip(struct decoder *d, int nrbits) {
22 d->bitoff += nrbits % 8;
23 d->byteoff += nrbits / 8 + (d->bitoff / 8);
24 d->bitoff %= 8;
25 }
26
get(struct decoder * d,int nrbits)27 static unsigned short get(struct decoder *d, int nrbits) {
28 unsigned short ret = 0;
29 int bitoff, byteoff, i = 16;
30
31 bitoff = d->bitoff;
32 byteoff = d->byteoff;
33
34 while (nrbits--) {
35 ret >>= 1;
36 i--;
37 ret |= !!((d->data[byteoff] & (1 << (7 - bitoff++)))) << 15;
38 if (bitoff >= 8) {
39 byteoff++;
40 bitoff = 0;
41 }
42 if (byteoff >= d->length)
43 return -1;
44 }
45
46 return ret >> i;
47 }
48
find(struct decoder * d,struct huffman * tab)49 static int find(struct decoder *d, struct huffman *tab)
50 {
51 unsigned short bits;
52
53 while (tab->code) {
54 bits = get(d, tab->bits);
55 if (bits == tab->code) {
56 skip(d, tab->bits);
57 return tab->len;
58 }
59 tab++;
60 }
61
62 return NOT_FOUND;
63 }
64
decoder_init(struct decoder * d,void * data,int length)65 void decoder_init(struct decoder *d, void *data, int length) {
66 memset(d, 0, sizeof(struct decoder));
67 d->data = data;
68 d->length = length;
69 }
70
decoder_token(struct decoder * d,int * type,int * len)71 int decoder_token(struct decoder *d, int *type, int *len) {
72 int l;
73 int found_nonterm = 0;
74
75 *type = DECODER_NOOP;
76
77 l = find(d, d->state & WHITE ? whiteterm : blackterm);
78 if (l == NOT_FOUND) {
79 if (d->state & TERM)
80 return -1;
81 l = find(d, d->state & WHITE ? white : black);
82 if (l == NOT_FOUND)
83 return -1;
84 found_nonterm = 1;
85 }
86
87 if (l == RL_EOL) {
88 *type = DECODER_EOL;
89 if (d->bitoff > 0) {
90 d->bitoff = 0;
91 d->byteoff++;
92 }
93 return 0;
94 }
95
96 if (l > 0) {
97 *type = d->state & WHITE ? DECODER_WHITE : DECODER_BLACK;
98 *len = l;
99 }
100 if (found_nonterm)
101 d->state = d->state & WHITE ? WHITE | TERM : BLACK | TERM;
102 else
103 d->state = d->state & WHITE ? BLACK : WHITE;
104
105 return 0;
106 }
107
108 struct huffman black[] = {
109 { 0x0080, RL_EOL, 8 },
110 { 0x0800, RL_EOL, 12 },
111 { 0x001b, 64, 5 },
112 { 0x0009, 128, 5 },
113 { 0x003a, 192, 6 },
114 { 0x0076, 256, 7 },
115 { 0x006c, 320, 8 },
116 { 0x00ec, 384, 8 },
117 { 0x0026, 448, 8 },
118 { 0x00a6, 512, 8 },
119 { 0x0016, 576, 8 },
120 { 0x00e6, 640, 8 },
121 { 0x0066, 704, 9 },
122 { 0x0166, 768, 9 },
123 { 0x0096, 832, 9 },
124 { 0x0196, 896, 9 },
125 { 0x0056, 960, 9 },
126 { 0x0156, 1024, 9 },
127 { 0x00d6, 1088, 9 },
128 { 0x01d6, 1152, 9 },
129 { 0x0036, 1216, 9 },
130 { 0x0136, 1280, 9 },
131 { 0x00b6, 1344, 9 },
132 { 0x01b6, 1408, 9 },
133 { 0x0032, 1472, 9 },
134 { 0x0132, 1536, 9 },
135 { 0x00b2, 1600, 9 },
136 { 0x0006, 1664, 6 },
137 { 0x01b2, 1728, 9 },
138 { 0x0080, 1792, 11 },
139 { 0x0180, 1856, 11 },
140 { 0x0580, 1920, 11 },
141 { 0x0480, 1984, 12 },
142 { 0x0c80, 2048, 12 },
143 { 0x0280, 2112, 12 },
144 { 0x0a80, 2176, 12 },
145 { 0x0680, 2240, 12 },
146 { 0x0e80, 2304, 12 },
147 { 0x0380, 2368, 12 },
148 { 0x0b80, 2432, 12 },
149 { 0x0780, 2496, 12 },
150 { 0x0f80, 2560, 12 },
151 { 0, 0, 0 }
152 };
153
154 struct huffman blackterm[] = {
155 { 0x0080, RL_EOL, 8 },
156 { 0x0800, RL_EOL, 12 },
157 { 0x00ac, 0, 8 },
158 { 0x0038, 1, 6 },
159 { 0x000e, 2, 4 },
160 { 0x0001, 3, 4 },
161 { 0x000d, 4, 4 },
162 { 0x0003, 5, 4 },
163 { 0x0007, 6, 4 },
164 { 0x000f, 7, 4 },
165 { 0x0019, 8, 5 },
166 { 0x0005, 9, 5 },
167 { 0x001c, 10, 5 },
168 { 0x0002, 11, 5 },
169 { 0x0004, 12, 6 },
170 { 0x0030, 13, 6 },
171 { 0x000b, 14, 6 },
172 { 0x002b, 15, 6 },
173 { 0x0015, 16, 6 },
174 { 0x0035, 17, 6 },
175 { 0x0072, 18, 7 },
176 { 0x0018, 19, 7 },
177 { 0x0008, 20, 7 },
178 { 0x0074, 21, 7 },
179 { 0x0060, 22, 7 },
180 { 0x0010, 23, 7 },
181 { 0x000a, 24, 7 },
182 { 0x006a, 25, 7 },
183 { 0x0064, 26, 7 },
184 { 0x0012, 27, 7 },
185 { 0x000c, 28, 7 },
186 { 0x0040, 29, 8 },
187 { 0x00c0, 30, 8 },
188 { 0x0058, 31, 8 },
189 { 0x00d8, 32, 8 },
190 { 0x0048, 33, 8 },
191 { 0x00c8, 34, 8 },
192 { 0x0028, 35, 8 },
193 { 0x00a8, 36, 8 },
194 { 0x0068, 37, 8 },
195 { 0x00e8, 38, 8 },
196 { 0x0014, 39, 8 },
197 { 0x0094, 40, 8 },
198 { 0x0054, 41, 8 },
199 { 0x00d4, 42, 8 },
200 { 0x0034, 43, 8 },
201 { 0x00b4, 44, 8 },
202 { 0x0020, 45, 8 },
203 { 0x00a0, 46, 8 },
204 { 0x0050, 47, 8 },
205 { 0x00d0, 48, 8 },
206 { 0x004a, 49, 8 },
207 { 0x00ca, 50, 8 },
208 { 0x002a, 51, 8 },
209 { 0x00aa, 52, 8 },
210 { 0x0024, 53, 8 },
211 { 0x00a4, 54, 8 },
212 { 0x001a, 55, 8 },
213 { 0x009a, 56, 8 },
214 { 0x005a, 57, 8 },
215 { 0x00da, 58, 8 },
216 { 0x0052, 59, 8 },
217 { 0x00d2, 60, 8 },
218 { 0x004c, 61, 8 },
219 { 0x00cc, 62, 8 },
220 { 0x002c, 63, 8 },
221 { 0, 0, 0 }
222 };
223
224 struct huffman white[] = {
225 { 0x0080, RL_EOL, 8 },
226 { 0x0800 ,RL_EOL, 12 },
227 { 0x03c0, 64, 10 },
228 { 0x0130, 128, 12 },
229 { 0x0930, 192, 12 },
230 { 0x0da0, 256, 12 },
231 { 0x0cc0, 320, 12 },
232 { 0x02c0, 384, 12 },
233 { 0x0ac0, 448, 12 },
234 { 0x06c0, 512, 13 },
235 { 0x16c0, 576, 13 },
236 { 0x0a40, 640, 13 },
237 { 0x1a40, 704, 13 },
238 { 0x0640, 768, 13 },
239 { 0x1640, 832, 13 },
240 { 0x09c0, 896, 13 },
241 { 0x19c0, 960, 13 },
242 { 0x05c0, 1024, 13 },
243 { 0x15c0, 1088, 13 },
244 { 0x0dc0, 1152, 13 },
245 { 0x1dc0, 1216, 13 },
246 { 0x0940, 1280, 13 },
247 { 0x1940, 1344, 13 },
248 { 0x0540, 1408, 13 },
249 { 0x1540, 1472, 13 },
250 { 0x0b40, 1536, 13 },
251 { 0x1b40, 1600, 13 },
252 { 0x04c0, 1664, 13 },
253 { 0x14c0, 1728, 13 },
254 { 0x0080, 1792, 11 },
255 { 0x0180, 1856, 11 },
256 { 0x0580, 1920, 11 },
257 { 0x0480, 1984, 12 },
258 { 0x0c80, 2048, 12 },
259 { 0x0280, 2112, 12 },
260 { 0x0a80, 2176, 12 },
261 { 0x0680, 2240, 12 },
262 { 0x0e80, 2304, 12 },
263 { 0x0380, 2368, 12 },
264 { 0x0b80, 2432, 12 },
265 { 0x0780, 2496, 12 },
266 { 0x0f80, 2560, 12 },
267 { 0, 0, 0 }
268 };
269
270 struct huffman whiteterm[] = {
271 { 0x0080, RL_EOL, 8 },
272 { 0x0800, RL_EOL, 12 },
273 { 0x03b0, 0, 10 },
274 { 0x0002, 1, 3 },
275 { 0x0003, 2, 2 },
276 { 0x0001, 3, 2 },
277 { 0x0006, 4, 3 },
278 { 0x000c, 5, 4 },
279 { 0x0004, 6, 4 },
280 { 0x0018, 7, 5 },
281 { 0x0028, 8, 6 },
282 { 0x0008, 9, 6 },
283 { 0x0010, 10, 7 },
284 { 0x0050, 11, 7 },
285 { 0x0070, 12, 7 },
286 { 0x0020, 13, 8 },
287 { 0x00e0, 14, 8 },
288 { 0x0030, 15, 9 },
289 { 0x03a0, 16, 10 },
290 { 0x0060, 17, 10 },
291 { 0x0040, 18, 10 },
292 { 0x0730, 19, 11 },
293 { 0x00b0, 20, 11 },
294 { 0x01b0, 21, 11 },
295 { 0x0760, 22, 11 },
296 { 0x00a0, 23, 11 },
297 { 0x0740, 24, 11 },
298 { 0x00c0, 25, 11 },
299 { 0x0530, 26, 12 },
300 { 0x0d30, 27, 12 },
301 { 0x0330, 28, 12 },
302 { 0x0b30, 29, 12 },
303 { 0x0160, 30, 12 },
304 { 0x0960, 31, 12 },
305 { 0x0560, 32, 12 },
306 { 0x0d60, 33, 12 },
307 { 0x04b0, 34, 12 },
308 { 0x0cb0, 35, 12 },
309 { 0x02b0, 36, 12 },
310 { 0x0ab0, 37, 12 },
311 { 0x06b0, 38, 12 },
312 { 0x0eb0, 39, 12 },
313 { 0x0360, 40, 12 },
314 { 0x0b60, 41, 12 },
315 { 0x05b0, 42, 12 },
316 { 0x0db0, 43, 12 },
317 { 0x02a0, 44, 12 },
318 { 0x0aa0, 45, 12 },
319 { 0x06a0, 46, 12 },
320 { 0x0ea0, 47, 12 },
321 { 0x0260, 48, 12 },
322 { 0x0a60, 49, 12 },
323 { 0x04a0, 50, 12 },
324 { 0x0ca0, 51, 12 },
325 { 0x0240, 52, 12 },
326 { 0x0ec0, 53, 12 },
327 { 0x01c0, 54, 12 },
328 { 0x0e40, 55, 12 },
329 { 0x0140, 56, 12 },
330 { 0x01a0, 57, 12 },
331 { 0x09a0, 58, 12 },
332 { 0x0d40, 59, 12 },
333 { 0x0340, 60, 12 },
334 { 0x05a0, 61, 12 },
335 { 0x0660, 62, 12 },
336 { 0x0e60, 63, 12 },
337 { 0, 0, 0 }
338 };
339