Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
8619 | maxcodehac | 1 | /* |
2 | jbig2dec |
||
3 | |||
4 | Copyright (C) 2001-2005 Artifex Software, Inc. |
||
5 | |||
6 | This software is distributed under license and may not |
||
7 | be copied, modified or distributed except as expressly |
||
8 | authorized under the terms of the license contained in |
||
9 | the file LICENSE in this distribution. |
||
10 | |||
11 | For further licensing information refer to http://artifex.com/ or |
||
12 | contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, |
||
13 | San Rafael, CA 94903, U.S.A., +1(415)492-9861. |
||
14 | */ |
||
15 | |||
16 | /* Huffman table decoding procedures |
||
17 | -- See Annex B of the JBIG2 specification */ |
||
18 | |||
19 | #ifdef HAVE_CONFIG_H |
||
20 | #include "config.h" |
||
21 | #endif |
||
22 | #include "os_types.h" |
||
23 | |||
24 | #include |
||
25 | #include |
||
26 | |||
27 | #ifdef JBIG2_DEBUG |
||
28 | #include |
||
29 | #endif |
||
30 | |||
31 | #include "jbig2.h" |
||
32 | #include "jbig2_priv.h" |
||
33 | #include "jbig2_huffman.h" |
||
34 | #include "jbig2_hufftab.h" |
||
35 | |||
36 | #define JBIG2_HUFFMAN_FLAGS_ISOOB 1 |
||
37 | #define JBIG2_HUFFMAN_FLAGS_ISLOW 2 |
||
38 | #define JBIG2_HUFFMAN_FLAGS_ISEXT 4 |
||
39 | |||
40 | |||
41 | |||
42 | struct _Jbig2HuffmanState { |
||
43 | /* The current bit offset is equal to (offset * 8) + offset_bits. |
||
44 | The MSB of this_word is the current bit offset. The MSB of next_word |
||
45 | is (offset + 4) * 8. */ |
||
46 | uint32_t this_word; |
||
47 | uint32_t next_word; |
||
48 | int offset_bits; |
||
49 | int offset; |
||
50 | |||
51 | Jbig2WordStream *ws; |
||
52 | }; |
||
53 | |||
54 | |||
55 | /** Allocate and initialize a new huffman coding state |
||
56 | * the returned pointer can simply be freed; this does |
||
57 | * not affect the associated Jbig2WordStream. |
||
58 | */ |
||
59 | Jbig2HuffmanState * |
||
60 | jbig2_huffman_new (Jbig2Ctx *ctx, Jbig2WordStream *ws) |
||
61 | { |
||
62 | Jbig2HuffmanState *result; |
||
63 | |||
64 | result = (Jbig2HuffmanState *)jbig2_alloc(ctx->allocator, |
||
65 | sizeof(Jbig2HuffmanState)); |
||
66 | |||
67 | if (result != NULL) { |
||
68 | result->offset = 0; |
||
69 | result->offset_bits = 0; |
||
70 | result->this_word = ws->get_next_word (ws, 0); |
||
71 | result->next_word = ws->get_next_word (ws, 4); |
||
72 | |||
73 | result->ws = ws; |
||
74 | } |
||
75 | |||
76 | return result; |
||
77 | } |
||
78 | |||
79 | /** Free an allocated huffman coding state. |
||
80 | * This just calls jbig2_free() if the pointer is not NULL |
||
81 | */ |
||
82 | void |
||
83 | jbig2_huffman_free (Jbig2Ctx *ctx, Jbig2HuffmanState *hs) |
||
84 | { |
||
85 | if (hs != NULL) free(hs); |
||
86 | return; |
||
87 | } |
||
88 | |||
89 | /** debug routines **/ |
||
90 | #ifdef JBIG2_DEBUG |
||
91 | |||
92 | /** print current huffman state */ |
||
93 | void jbig2_dump_huffman_state(Jbig2HuffmanState *hs) { |
||
94 | fprintf(stderr, "huffman state %08x %08x offset %d.%d\n", |
||
95 | hs->this_word, hs->next_word, hs->offset, hs->offset_bits); |
||
96 | } |
||
97 | |||
98 | /** print the binary string we're reading from */ |
||
99 | void jbig2_dump_huffman_binary(Jbig2HuffmanState *hs) |
||
100 | { |
||
101 | const uint32_t word = hs->this_word; |
||
102 | int i; |
||
103 | |||
104 | fprintf(stderr, "huffman binary "); |
||
105 | for (i = 31; i >= 0; i--) |
||
106 | fprintf(stderr, ((word >> i) & 1) ? "1" : "0"); |
||
107 | fprintf(stderr, "\n"); |
||
108 | } |
||
109 | |||
110 | #endif /* JBIG2_DEBUG */ |
||
111 | |||
112 | /** Skip bits up to the next byte boundary |
||
113 | */ |
||
114 | void |
||
115 | jbig2_huffman_skip(Jbig2HuffmanState *hs) |
||
116 | { |
||
117 | int bits = hs->offset_bits & 7; |
||
118 | |||
119 | if (bits) { |
||
120 | bits = 8 - bits; |
||
121 | hs->offset_bits += bits; |
||
122 | hs->this_word = (hs->this_word << bits) | |
||
123 | (hs->next_word >> (32 - hs->offset_bits)); |
||
124 | } |
||
125 | |||
126 | if (hs->offset_bits >= 32) { |
||
127 | Jbig2WordStream *ws = hs->ws; |
||
128 | hs->this_word = hs->next_word; |
||
129 | hs->offset += 4; |
||
130 | hs->next_word = ws->get_next_word (ws, hs->offset + 4); |
||
131 | hs->offset_bits -= 32; |
||
132 | if (hs->offset_bits) { |
||
133 | hs->this_word = (hs->this_word << hs->offset_bits) | |
||
134 | (hs->next_word >> (32 - hs->offset_bits)); |
||
135 | } |
||
136 | } |
||
137 | } |
||
138 | |||
139 | /* skip ahead a specified number of bytes in the word stream |
||
140 | */ |
||
141 | void jbig2_huffman_advance(Jbig2HuffmanState *hs, int offset) |
||
142 | { |
||
143 | Jbig2WordStream *ws = hs->ws; |
||
144 | |||
145 | hs->offset += offset & ~3; |
||
146 | hs->offset_bits += (offset & 3) << 3; |
||
147 | if (hs->offset_bits >= 32) { |
||
148 | hs->offset += 4; |
||
149 | hs->offset_bits -= 32; |
||
150 | } |
||
151 | hs->this_word = ws->get_next_word (ws, hs->offset); |
||
152 | hs->next_word = ws->get_next_word (ws, hs->offset + 4); |
||
153 | if (hs->offset_bits > 0) |
||
154 | hs->this_word = (hs->this_word << hs->offset_bits) | |
||
155 | (hs->next_word >> (32 - hs->offset_bits)); |
||
156 | } |
||
157 | |||
158 | /* return the offset of the huffman decode pointer (in bytes) |
||
159 | * from the beginning of the WordStream |
||
160 | */ |
||
161 | int |
||
162 | jbig2_huffman_offset(Jbig2HuffmanState *hs) |
||
163 | { |
||
164 | return hs->offset + (hs->offset_bits >> 3); |
||
165 | } |
||
166 | |||
167 | /* read a number of bits directly from the huffman state |
||
168 | * without decoding against a table |
||
169 | */ |
||
170 | int32_t |
||
171 | jbig2_huffman_get_bits (Jbig2HuffmanState *hs, const int bits) |
||
172 | { |
||
173 | uint32_t this_word = hs->this_word; |
||
174 | int32_t result; |
||
175 | |||
176 | result = this_word >> (32 - bits); |
||
177 | hs->offset_bits += bits; |
||
178 | if (hs->offset_bits >= 32) { |
||
179 | hs->offset += 4; |
||
180 | hs->offset_bits -= 32; |
||
181 | hs->this_word = hs->next_word; |
||
182 | hs->next_word = hs->ws->get_next_word(hs->ws, hs->offset + 4); |
||
183 | if (hs->offset_bits) { |
||
184 | hs->this_word = (hs->this_word << hs->offset_bits) | |
||
185 | (hs->next_word >> (32 - hs->offset_bits)); |
||
186 | } else { |
||
187 | hs->this_word = (hs->this_word << hs->offset_bits); |
||
188 | } |
||
189 | } else { |
||
190 | hs->this_word = (this_word << bits) | |
||
191 | (hs->next_word >> (32 - hs->offset_bits)); |
||
192 | } |
||
193 | |||
194 | return result; |
||
195 | } |
||
196 | |||
197 | int32_t |
||
198 | jbig2_huffman_get (Jbig2HuffmanState *hs, |
||
199 | const Jbig2HuffmanTable *table, bool *oob) |
||
200 | { |
||
201 | Jbig2HuffmanEntry *entry; |
||
202 | byte flags; |
||
203 | int offset_bits = hs->offset_bits; |
||
204 | uint32_t this_word = hs->this_word; |
||
205 | uint32_t next_word; |
||
206 | int RANGELEN; |
||
207 | int32_t result; |
||
208 | |||
209 | for (;;) |
||
210 | { |
||
211 | int log_table_size = table->log_table_size; |
||
212 | int PREFLEN; |
||
213 | |||
214 | entry = &table->entries[this_word >> (32 - log_table_size)]; |
||
215 | flags = entry->flags; |
||
216 | PREFLEN = entry->PREFLEN; |
||
217 | |||
218 | next_word = hs->next_word; |
||
219 | offset_bits += PREFLEN; |
||
220 | if (offset_bits >= 32) |
||
221 | { |
||
222 | Jbig2WordStream *ws = hs->ws; |
||
223 | this_word = next_word; |
||
224 | hs->offset += 4; |
||
225 | next_word = ws->get_next_word (ws, hs->offset + 4); |
||
226 | offset_bits -= 32; |
||
227 | hs->next_word = next_word; |
||
228 | PREFLEN = offset_bits; |
||
229 | } |
||
230 | if (PREFLEN) |
||
231 | this_word = (this_word << PREFLEN) | |
||
232 | (next_word >> (32 - offset_bits)); |
||
233 | if (flags & JBIG2_HUFFMAN_FLAGS_ISEXT) |
||
234 | { |
||
235 | table = entry->u.ext_table; |
||
236 | } |
||
237 | else |
||
238 | break; |
||
239 | } |
||
240 | result = entry->u.RANGELOW; |
||
241 | RANGELEN = entry->RANGELEN; |
||
242 | if (RANGELEN > 0) |
||
243 | { |
||
244 | int32_t HTOFFSET; |
||
245 | |||
246 | HTOFFSET = this_word >> (32 - RANGELEN); |
||
247 | if (flags & JBIG2_HUFFMAN_FLAGS_ISLOW) |
||
248 | result -= HTOFFSET; |
||
249 | else |
||
250 | result += HTOFFSET; |
||
251 | |||
252 | offset_bits += RANGELEN; |
||
253 | if (offset_bits >= 32) |
||
254 | { |
||
255 | Jbig2WordStream *ws = hs->ws; |
||
256 | this_word = next_word; |
||
257 | hs->offset += 4; |
||
258 | next_word = ws->get_next_word (ws, hs->offset + 4); |
||
259 | offset_bits -= 32; |
||
260 | hs->next_word = next_word; |
||
261 | RANGELEN = offset_bits; |
||
262 | } |
||
263 | if (RANGELEN) |
||
264 | this_word = (this_word << RANGELEN) | |
||
265 | (next_word >> (32 - offset_bits)); |
||
266 | } |
||
267 | |||
268 | hs->this_word = this_word; |
||
269 | hs->offset_bits = offset_bits; |
||
270 | |||
271 | if (oob != NULL) |
||
272 | *oob = (flags & JBIG2_HUFFMAN_FLAGS_ISOOB); |
||
273 | |||
274 | return result; |
||
275 | } |
||
276 | |||
277 | /* TODO: more than 8 bits here is wasteful of memory. We have support |
||
278 | for sub-trees in jbig2_huffman_get() above, but don't use it here. |
||
279 | We should, and then revert to 8 bits */ |
||
280 | #define LOG_TABLE_SIZE_MAX 16 |
||
281 | |||
282 | /** Build an in-memory representation of a Huffman table from the |
||
283 | * set of template params provided by the spec or a table segment |
||
284 | */ |
||
285 | Jbig2HuffmanTable * |
||
286 | jbig2_build_huffman_table (Jbig2Ctx *ctx, const Jbig2HuffmanParams *params) |
||
287 | { |
||
288 | int *LENCOUNT; |
||
289 | int LENMAX = -1; |
||
290 | const int lencountsize = 256 * sizeof(*LENCOUNT); |
||
291 | const Jbig2HuffmanLine *lines = params->lines; |
||
292 | int n_lines = params->n_lines; |
||
293 | int i, j; |
||
294 | int max_j; |
||
295 | int log_table_size = 0; |
||
296 | Jbig2HuffmanTable *result; |
||
297 | Jbig2HuffmanEntry *entries; |
||
298 | int CURLEN; |
||
299 | int firstcode = 0; |
||
300 | int CURCODE; |
||
301 | int CURTEMP; |
||
302 | |||
303 | LENCOUNT = jbig2_alloc(ctx->allocator, lencountsize); |
||
304 | if (LENCOUNT == NULL) { |
||
305 | jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1, |
||
306 | "couldn't allocate storage for huffman histogram"); |
||
307 | return NULL; |
||
308 | } |
||
309 | memset(LENCOUNT, 0, lencountsize); |
||
310 | |||
311 | /* B.3, 1. */ |
||
312 | for (i = 0; i < params->n_lines; i++) |
||
313 | { |
||
314 | int PREFLEN = lines[i].PREFLEN; |
||
315 | int lts; |
||
316 | |||
317 | if (PREFLEN > LENMAX) |
||
318 | { |
||
319 | for (j = LENMAX + 1; j < PREFLEN + 1; j++) |
||
320 | LENCOUNT[j] = 0; |
||
321 | LENMAX = PREFLEN; |
||
322 | } |
||
323 | LENCOUNT[PREFLEN]++; |
||
324 | |||
325 | lts = PREFLEN + lines[i].RANGELEN; |
||
326 | if (lts > LOG_TABLE_SIZE_MAX) |
||
327 | lts = PREFLEN; |
||
328 | if (lts <= LOG_TABLE_SIZE_MAX && log_table_size < lts) |
||
329 | log_table_size = lts; |
||
330 | } |
||
331 | jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, -1, |
||
332 | "constructing huffman table log size %d", log_table_size); |
||
333 | max_j = 1 << log_table_size; |
||
334 | |||
335 | result = (Jbig2HuffmanTable *)jbig2_alloc(ctx->allocator, sizeof(Jbig2HuffmanTable)); |
||
336 | result->log_table_size = log_table_size; |
||
337 | entries = (Jbig2HuffmanEntry *)jbig2_alloc(ctx->allocator, max_j * sizeof(Jbig2HuffmanEntry)); |
||
338 | result->entries = entries; |
||
339 | |||
340 | LENCOUNT[0] = 0; |
||
341 | |||
342 | for (CURLEN = 1; CURLEN <= LENMAX; CURLEN++) |
||
343 | { |
||
344 | int shift = log_table_size - CURLEN; |
||
345 | |||
346 | /* B.3 3.(a) */ |
||
347 | firstcode = (firstcode + LENCOUNT[CURLEN - 1]) << 1; |
||
348 | CURCODE = firstcode; |
||
349 | /* B.3 3.(b) */ |
||
350 | for (CURTEMP = 0; CURTEMP < n_lines; CURTEMP++) |
||
351 | { |
||
352 | int PREFLEN = lines[CURTEMP].PREFLEN; |
||
353 | if (PREFLEN == CURLEN) |
||
354 | { |
||
355 | int RANGELEN = lines[CURTEMP].RANGELEN; |
||
356 | int start_j = CURCODE << shift; |
||
357 | int end_j = (CURCODE + 1) << shift; |
||
358 | byte eflags = 0; |
||
359 | |||
360 | if (end_j > max_j) { |
||
361 | jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1, |
||
362 | "ran off the end of the entries table! (%d >= %d)", |
||
363 | end_j, max_j); |
||
364 | jbig2_free(ctx->allocator, result->entries); |
||
365 | jbig2_free(ctx->allocator, result); |
||
366 | jbig2_free(ctx->allocator, LENCOUNT); |
||
367 | return NULL; |
||
368 | } |
||
369 | /* todo: build extension tables */ |
||
370 | if (params->HTOOB && CURTEMP == n_lines - 1) |
||
371 | eflags |= JBIG2_HUFFMAN_FLAGS_ISOOB; |
||
372 | if (CURTEMP == n_lines - (params->HTOOB ? 3 : 2)) |
||
373 | eflags |= JBIG2_HUFFMAN_FLAGS_ISLOW; |
||
374 | if (PREFLEN + RANGELEN > LOG_TABLE_SIZE_MAX) { |
||
375 | for (j = start_j; j < end_j; j++) { |
||
376 | entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW; |
||
377 | entries[j].PREFLEN = PREFLEN; |
||
378 | entries[j].RANGELEN = RANGELEN; |
||
379 | entries[j].flags = eflags; |
||
380 | } |
||
381 | } else { |
||
382 | for (j = start_j; j < end_j; j++) { |
||
383 | int32_t HTOFFSET = (j >> (shift - RANGELEN)) & |
||
384 | ((1 << RANGELEN) - 1); |
||
385 | if (eflags & JBIG2_HUFFMAN_FLAGS_ISLOW) |
||
386 | entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW - |
||
387 | HTOFFSET; |
||
388 | else |
||
389 | entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW + |
||
390 | HTOFFSET; |
||
391 | entries[j].PREFLEN = PREFLEN + RANGELEN; |
||
392 | entries[j].RANGELEN = 0; |
||
393 | entries[j].flags = eflags; |
||
394 | } |
||
395 | } |
||
396 | CURCODE++; |
||
397 | } |
||
398 | } |
||
399 | } |
||
400 | |||
401 | jbig2_free(ctx->allocator, LENCOUNT); |
||
402 | |||
403 | return result; |
||
404 | } |
||
405 | |||
406 | /** Free the memory associated with the representation of table */ |
||
407 | void |
||
408 | jbig2_release_huffman_table (Jbig2Ctx *ctx, Jbig2HuffmanTable *table) |
||
409 | { |
||
410 | if (table != NULL) { |
||
411 | jbig2_free(ctx->allocator, table->entries); |
||
412 | jbig2_free(ctx->allocator, table); |
||
413 | } |
||
414 | return; |
||
415 | } |
||
416 | |||
417 | #ifdef TEST |
||
418 | #include |
||
419 | |||
420 | /* a test bitstream, and a list of the table indicies |
||
421 | to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */ |
||
422 | /* this test stream should decode to { 8, 5, oob, 8 } */ |
||
423 | |||
424 | const byte test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 }; |
||
425 | const byte test_tabindex[] = { 4, 2, 2, 1 }; |
||
426 | |||
427 | static uint32_t |
||
428 | test_get_word (Jbig2WordStream *self, int offset) |
||
429 | { |
||
430 | /* assume test_stream[] is at least 4 bytes */ |
||
431 | if (offset+3 > sizeof(test_stream)) |
||
432 | return 0; |
||
433 | else |
||
434 | return ( (test_stream[offset] << 24) | |
||
435 | (test_stream[offset+1] << 16) | |
||
436 | (test_stream[offset+2] << 8) | |
||
437 | (test_stream[offset+3]) ); |
||
438 | } |
||
439 | |||
440 | int |
||
441 | main (int argc, char **argv) |
||
442 | { |
||
443 | Jbig2Ctx *ctx; |
||
444 | Jbig2HuffmanTable *tables[5]; |
||
445 | Jbig2HuffmanState *hs; |
||
446 | Jbig2WordStream ws; |
||
447 | bool oob; |
||
448 | int32_t code; |
||
449 | |||
450 | ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL); |
||
451 | |||
452 | tables[0] = NULL; |
||
453 | tables[1] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_A); |
||
454 | tables[2] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_B); |
||
455 | tables[3] = NULL; |
||
456 | tables[4] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_D); |
||
457 | ws.get_next_word = test_get_word; |
||
458 | hs = jbig2_huffman_new (ctx, &ws); |
||
459 | |||
460 | printf("testing jbig2 huffmann decoding..."); |
||
461 | printf("\t(should be 8 5 (oob) 8)\n"); |
||
462 | |||
463 | { |
||
464 | int i; |
||
465 | int sequence_length = sizeof(test_tabindex); |
||
466 | |||
467 | for (i = 0; i < sequence_length; i++) { |
||
468 | code = jbig2_huffman_get (hs, tables[test_tabindex[i]], &oob); |
||
469 | if (oob) printf("(oob) "); |
||
470 | else printf("%d ", code); |
||
471 | } |
||
472 | } |
||
473 | |||
474 | printf("\n"); |
||
475 | |||
476 | jbig2_ctx_free(ctx); |
||
477 | |||
478 | return 0; |
||
479 | } |
||
480 | #endif>><>><>><>><>>>><>><>>><>=>><>>=>>>><>><>><>><>><>><>><>><>><> |