Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/jbig2dec/jbig2_huffman.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /* Copyright (C) 2001-2023 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
13 CA 94129, USA, for further information.
14 */
15
16 /*
17 jbig2dec
18 */
19
20 /* Huffman table decoding procedures
21 -- See Annex B of the JBIG2 specification */
22
23 #ifdef HAVE_CONFIG_H
24 #include "config.h"
25 #endif
26 #include "os_types.h"
27
28 #include <stdlib.h>
29 #include <string.h>
30
31 #ifdef JBIG2_DEBUG
32 #include <stdio.h>
33 #endif
34
35 #include "jbig2.h"
36 #include "jbig2_priv.h"
37 #include "jbig2_huffman.h"
38 #include "jbig2_hufftab.h"
39 #include "jbig2_image.h"
40 #include "jbig2_segment.h"
41
42 #define JBIG2_HUFFMAN_FLAGS_ISOOB 1
43 #define JBIG2_HUFFMAN_FLAGS_ISLOW 2
44 #define JBIG2_HUFFMAN_FLAGS_ISEXT 4
45
46 struct _Jbig2HuffmanState {
47 /* The current bit offset is equal to (offset * 8) + offset_bits.
48 The MSB of this_word is the current bit offset. The MSB of next_word
49 is (offset + 4) * 8. */
50 uint32_t this_word;
51 uint32_t next_word;
52 uint32_t offset_bits;
53 uint32_t offset;
54 uint32_t offset_limit;
55
56 Jbig2WordStream *ws;
57 Jbig2Ctx *ctx;
58 };
59
60 #define huff_get_next_word(hs, offset, word) \
61 (hs)->ws->get_next_word((hs)->ctx, (hs)->ws, (offset), (word))
62
63 /** Allocate and initialize a new huffman coding state
64 * the returned pointer can simply be freed; this does
65 * not affect the associated Jbig2WordStream.
66 */
67 Jbig2HuffmanState *
68 jbig2_huffman_new(Jbig2Ctx *ctx, Jbig2WordStream *ws)
69 {
70 Jbig2HuffmanState *result = NULL;
71 int code;
72
73 result = jbig2_new(ctx, Jbig2HuffmanState, 1);
74
75 if (result != NULL) {
76 result->offset = 0;
77 result->offset_bits = 0;
78 result->offset_limit = 0;
79 result->ws = ws;
80 result->ctx = ctx;
81 code = huff_get_next_word(result, 0, &result->this_word);
82 if (code < 0) {
83 jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read first huffman word");
84 jbig2_huffman_free(ctx, result);
85 return NULL;
86 }
87 code = huff_get_next_word(result, 4, &result->next_word);
88 if (code < 0) {
89 jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read second huffman word");
90 jbig2_huffman_free(ctx, result);
91 return NULL;
92 }
93 } else {
94 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate new huffman coding state");
95 return NULL;
96 }
97
98 return result;
99 }
100
101 /** Free an allocated huffman coding state.
102 * This just calls jbig2_free() if the pointer is not NULL
103 */
104 void
105 jbig2_huffman_free(Jbig2Ctx *ctx, Jbig2HuffmanState *hs)
106 {
107 jbig2_free(ctx->allocator, hs);
108 }
109
110 /** debug routines **/
111 #ifdef JBIG2_DEBUG
112
113 /** print current huffman state */
114 void
115 jbig2_dump_huffman_state(Jbig2HuffmanState *hs)
116 {
117 fprintf(stderr, "huffman state %08x %08x offset %d.%d\n", hs->this_word, hs->next_word, hs->offset, hs->offset_bits);
118 }
119
120 /** print the binary string we're reading from */
121 void
122 jbig2_dump_huffman_binary(Jbig2HuffmanState *hs)
123 {
124 const uint32_t word = hs->this_word;
125 int i;
126
127 fprintf(stderr, "huffman binary ");
128 for (i = 31; i >= 0; i--)
129 fprintf(stderr, ((word >> i) & 1) ? "1" : "0");
130 fprintf(stderr, "\n");
131 }
132
133 /** print huffman table */
134 void
135 jbig2_dump_huffman_table(const Jbig2HuffmanTable *table)
136 {
137 int i;
138 int table_size = (1 << table->log_table_size);
139
140 fprintf(stderr, "huffman table %p (log_table_size=%d, %d entries, entries=%p):\n", table, table->log_table_size, table_size, table->entries);
141 for (i = 0; i < table_size; i++) {
142 fprintf(stderr, "%6d: PREFLEN=%d, RANGELEN=%d, ", i, table->entries[i].PREFLEN, table->entries[i].RANGELEN);
143 if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {
144 fprintf(stderr, "ext=%p", table->entries[i].u.ext_table);
145 } else {
146 fprintf(stderr, "RANGELOW=%d", table->entries[i].u.RANGELOW);
147 }
148 if (table->entries[i].flags) {
149 int need_comma = 0;
150
151 fprintf(stderr, ", flags=0x%x(", table->entries[i].flags);
152 if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISOOB) {
153 fprintf(stderr, "OOB");
154 need_comma = 1;
155 }
156 if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISLOW) {
157 if (need_comma)
158 fprintf(stderr, ",");
159 fprintf(stderr, "LOW");
160 need_comma = 1;
161 }
162 if (table->entries[i].flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {
163 if (need_comma)
164 fprintf(stderr, ",");
165 fprintf(stderr, "EXT");
166 }
167 fprintf(stderr, ")");
168 }
169 fprintf(stderr, "\n");
170 }
171 fprintf(stderr, "\n");
172 }
173
174 #endif /* JBIG2_DEBUG */
175
176 /** Skip bits up to the next byte boundary
177 */
178 int
179 jbig2_huffman_skip(Jbig2HuffmanState *hs)
180 {
181 uint32_t bits = hs->offset_bits & 7;
182 int code;
183
184 if (bits) {
185 bits = 8 - bits;
186 hs->offset_bits += bits;
187 hs->this_word = (hs->this_word << bits) | (hs->next_word >> (32 - hs->offset_bits));
188 }
189
190 if (hs->offset_bits >= 32) {
191 hs->this_word = hs->next_word;
192 hs->offset += 4;
193 code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);
194 if (code < 0) {
195 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read next huffman word when skipping");
196 }
197 hs->offset_bits -= 32;
198 if (hs->offset_bits) {
199 hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));
200 }
201 }
202 return 0;
203 }
204
205 /* skip ahead a specified number of bytes in the word stream
206 */
207 int
208 jbig2_huffman_advance(Jbig2HuffmanState *hs, size_t advance)
209 {
210 int code;
211 hs->offset += advance & ~3;
212 hs->offset_bits += (advance & 3) << 3;
213 if (hs->offset_bits >= 32) {
214 hs->offset += 4;
215 hs->offset_bits -= 32;
216 }
217 code = huff_get_next_word(hs, hs->offset, &hs->this_word);
218 if (code < 0) {
219 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get first huffman word after advancing");
220 }
221 code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);
222 if (code < 0) {
223 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get second huffman word after advancing");
224 }
225 if (hs->offset_bits > 0)
226 hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));
227 return 0;
228 }
229
230 /* return the offset of the huffman decode pointer (in bytes)
231 * from the beginning of the WordStream
232 */
233 uint32_t
234 jbig2_huffman_offset(Jbig2HuffmanState *hs)
235 {
236 return hs->offset + (hs->offset_bits >> 3);
237 }
238
239 /* read a number of bits directly from the huffman state
240 * without decoding against a table
241 */
242 int32_t
243 jbig2_huffman_get_bits(Jbig2HuffmanState *hs, const int bits, int *err)
244 {
245 uint32_t this_word = hs->this_word;
246 int32_t result;
247 int code;
248
249 if (hs->offset_limit && hs->offset >= hs->offset_limit) {
250 *err = -1;
251 return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "end of jbig2 buffer reached at offset %d", hs->offset);
252 }
253
254 result = this_word >> (32 - bits);
255 hs->offset_bits += bits;
256 if (hs->offset_bits >= 32) {
257 hs->offset += 4;
258 hs->offset_bits -= 32;
259 hs->this_word = hs->next_word;
260 code = huff_get_next_word(hs, hs->offset + 4, &hs->next_word);
261 if (code < 0) {
262 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");
263 }
264 if (hs->offset_bits) {
265 hs->this_word = (hs->this_word << hs->offset_bits) | (hs->next_word >> (32 - hs->offset_bits));
266 } else {
267 hs->this_word = (hs->this_word << hs->offset_bits);
268 }
269 } else {
270 hs->this_word = (this_word << bits) | (hs->next_word >> (32 - hs->offset_bits));
271 }
272
273 return result;
274 }
275
276 int32_t
277 jbig2_huffman_get(Jbig2HuffmanState *hs, const Jbig2HuffmanTable *table, bool *oob)
278 {
279 Jbig2HuffmanEntry *entry;
280 byte flags;
281 int offset_bits = hs->offset_bits;
282 uint32_t this_word = hs->this_word;
283 uint32_t next_word;
284 int RANGELEN;
285 int32_t result;
286
287 if (hs->offset_limit && hs->offset >= hs->offset_limit) {
288 if (oob)
289 *oob = -1;
290 return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "end of Jbig2WordStream reached at offset %d", hs->offset);
291 }
292
293 for (;;) {
294 int log_table_size = table->log_table_size;
295 int PREFLEN;
296 int code;
297
298 /* SumatraPDF: shifting by the size of the operand is undefined */
299 entry = &table->entries[log_table_size > 0 ? this_word >> (32 - log_table_size) : 0];
300 flags = entry->flags;
301 PREFLEN = entry->PREFLEN;
302 if (flags == (byte) -1 || PREFLEN == (byte) -1) {
303 if (oob)
304 *oob = -1;
305 return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "encountered unpopulated huffman table entry");
306 }
307
308 next_word = hs->next_word;
309 offset_bits += PREFLEN;
310 if (offset_bits >= 32) {
311 this_word = next_word;
312 hs->offset += 4;
313 code = huff_get_next_word(hs, hs->offset + 4, &next_word);
314 if (code < 0) {
315 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");
316 }
317 offset_bits -= 32;
318 hs->next_word = next_word;
319 PREFLEN = offset_bits;
320 }
321 if (PREFLEN)
322 this_word = (this_word << PREFLEN) | (next_word >> (32 - offset_bits));
323 if (flags & JBIG2_HUFFMAN_FLAGS_ISEXT) {
324 table = entry->u.ext_table;
325 } else
326 break;
327 }
328 result = entry->u.RANGELOW;
329 RANGELEN = entry->RANGELEN;
330 if (RANGELEN > 0) {
331 int32_t HTOFFSET;
332 int code;
333
334 HTOFFSET = this_word >> (32 - RANGELEN);
335 if (flags & JBIG2_HUFFMAN_FLAGS_ISLOW)
336 result -= HTOFFSET;
337 else
338 result += HTOFFSET;
339
340 offset_bits += RANGELEN;
341 if (offset_bits >= 32) {
342 this_word = next_word;
343 hs->offset += 4;
344 code = huff_get_next_word(hs, hs->offset + 4, &next_word);
345 if (code < 0) {
346 return jbig2_error(hs->ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to get next huffman word");
347 }
348 offset_bits -= 32;
349 hs->next_word = next_word;
350 RANGELEN = offset_bits;
351 }
352 if (RANGELEN)
353 this_word = (this_word << RANGELEN) | (next_word >> (32 - offset_bits));
354 }
355
356 hs->this_word = this_word;
357 hs->offset_bits = offset_bits;
358
359 if (oob != NULL)
360 *oob = (flags & JBIG2_HUFFMAN_FLAGS_ISOOB);
361
362 return result;
363 }
364
365 /* TODO: more than 8 bits here is wasteful of memory. We have support
366 for sub-trees in jbig2_huffman_get() above, but don't use it here.
367 We should, and then revert to 8 bits */
368 #define LOG_TABLE_SIZE_MAX 16
369
370 /** Build an in-memory representation of a Huffman table from the
371 * set of template params provided by the spec or a table segment
372 */
373 Jbig2HuffmanTable *
374 jbig2_build_huffman_table(Jbig2Ctx *ctx, const Jbig2HuffmanParams *params)
375 {
376 int *LENCOUNT;
377 int LENMAX = -1;
378 const int lencountcount = 256;
379 const Jbig2HuffmanLine *lines = params->lines;
380 int n_lines = params->n_lines;
381 int i, j;
382 uint32_t max_j;
383 int log_table_size = 0;
384 Jbig2HuffmanTable *result;
385 Jbig2HuffmanEntry *entries;
386 int CURLEN;
387 int firstcode = 0;
388 int CURCODE;
389 int CURTEMP;
390
391 LENCOUNT = jbig2_new(ctx, int, lencountcount);
392
393 if (LENCOUNT == NULL) {
394 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate huffman histogram");
395 return NULL;
396 }
397 memset(LENCOUNT, 0, sizeof(int) * lencountcount);
398
399 /* B.3, 1. */
400 for (i = 0; i < params->n_lines; i++) {
401 int PREFLEN = lines[i].PREFLEN;
402 int lts;
403
404 if (PREFLEN > LENMAX) {
405 for (j = LENMAX + 1; j < PREFLEN + 1; j++)
406 LENCOUNT[j] = 0;
407 LENMAX = PREFLEN;
408 }
409 LENCOUNT[PREFLEN]++;
410
411 lts = PREFLEN + lines[i].RANGELEN;
412 if (lts > LOG_TABLE_SIZE_MAX)
413 lts = PREFLEN;
414 if (lts <= LOG_TABLE_SIZE_MAX && log_table_size < lts)
415 log_table_size = lts;
416 }
417 jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, JBIG2_UNKNOWN_SEGMENT_NUMBER, "constructing huffman table log size %d", log_table_size);
418 max_j = 1 << log_table_size;
419
420 result = jbig2_new(ctx, Jbig2HuffmanTable, 1);
421 if (result == NULL) {
422 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate result");
423 jbig2_free(ctx->allocator, LENCOUNT);
424 return NULL;
425 }
426 result->log_table_size = log_table_size;
427 entries = jbig2_new(ctx, Jbig2HuffmanEntry, max_j);
428 if (entries == NULL) {
429 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate result entries");
430 jbig2_free(ctx->allocator, result);
431 jbig2_free(ctx->allocator, LENCOUNT);
432 return NULL;
433 }
434 /* fill now to catch missing JBIG2Globals later */
435 memset(entries, 0xFF, sizeof(Jbig2HuffmanEntry) * max_j);
436 result->entries = entries;
437
438 LENCOUNT[0] = 0;
439
440 for (CURLEN = 1; CURLEN <= LENMAX; CURLEN++) {
441 int shift = log_table_size - CURLEN;
442
443 /* B.3 3.(a) */
444 firstcode = (firstcode + LENCOUNT[CURLEN - 1]) << 1;
445 CURCODE = firstcode;
446 /* B.3 3.(b) */
447 for (CURTEMP = 0; CURTEMP < n_lines; CURTEMP++) {
448 int PREFLEN = lines[CURTEMP].PREFLEN;
449
450 if (PREFLEN == CURLEN) {
451 int RANGELEN = lines[CURTEMP].RANGELEN;
452 uint32_t start_j = CURCODE << shift;
453 uint32_t end_j = (CURCODE + 1) << shift;
454 uint32_t cur_j;
455 byte eflags = 0;
456
457 if (end_j > max_j) {
458 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "ran off the end of the entries table! (%d >= %d)", end_j, max_j);
459 jbig2_free(ctx->allocator, result->entries);
460 jbig2_free(ctx->allocator, result);
461 jbig2_free(ctx->allocator, LENCOUNT);
462 return NULL;
463 }
464 /* todo: build extension tables */
465 if (params->HTOOB && CURTEMP == n_lines - 1)
466 eflags |= JBIG2_HUFFMAN_FLAGS_ISOOB;
467 if (CURTEMP == n_lines - (params->HTOOB ? 3 : 2))
468 eflags |= JBIG2_HUFFMAN_FLAGS_ISLOW;
469 if (PREFLEN + RANGELEN > LOG_TABLE_SIZE_MAX) {
470 for (cur_j = start_j; cur_j < end_j; cur_j++) {
471 entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW;
472 entries[cur_j].PREFLEN = PREFLEN;
473 entries[cur_j].RANGELEN = RANGELEN;
474 entries[cur_j].flags = eflags;
475 }
476 } else {
477 for (cur_j = start_j; cur_j < end_j; cur_j++) {
478 int32_t HTOFFSET = (cur_j >> (shift - RANGELEN)) & ((1 << RANGELEN) - 1);
479
480 if (eflags & JBIG2_HUFFMAN_FLAGS_ISLOW)
481 entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW - HTOFFSET;
482 else
483 entries[cur_j].u.RANGELOW = lines[CURTEMP].RANGELOW + HTOFFSET;
484 entries[cur_j].PREFLEN = PREFLEN + RANGELEN;
485 entries[cur_j].RANGELEN = 0;
486 entries[cur_j].flags = eflags;
487 }
488 }
489 CURCODE++;
490 }
491 }
492 }
493
494 jbig2_free(ctx->allocator, LENCOUNT);
495
496 return result;
497 }
498
499 /** Free the memory associated with the representation of table */
500 void
501 jbig2_release_huffman_table(Jbig2Ctx *ctx, Jbig2HuffmanTable *table)
502 {
503 if (table != NULL) {
504 jbig2_free(ctx->allocator, table->entries);
505 jbig2_free(ctx->allocator, table);
506 }
507 }
508
509 /* Routines to handle "code table segment (53)" */
510
511 /* return 'bitlen' bits from 'bitoffset' of 'data' */
512 static uint32_t
513 jbig2_table_read_bits(const byte *data, size_t *bitoffset, const int bitlen)
514 {
515 uint32_t result = 0;
516 uint32_t byte_offset = *bitoffset / 8;
517 const int endbit = (*bitoffset & 7) + bitlen;
518 const int n_proc_bytes = (endbit + 7) / 8;
519 const int rshift = n_proc_bytes * 8 - endbit;
520 int i;
521
522 for (i = n_proc_bytes - 1; i >= 0; i--) {
523 uint32_t d = data[byte_offset++];
524 const int nshift = i * 8 - rshift;
525
526 if (nshift > 0)
527 d <<= nshift;
528 else if (nshift < 0)
529 d >>= -nshift;
530 result |= d;
531 }
532 result &= ~(-1 << bitlen);
533 *bitoffset += bitlen;
534 return result;
535 }
536
537 /* Parse a code table segment, store Jbig2HuffmanParams in segment->result */
538 int
539 jbig2_table(Jbig2Ctx *ctx, Jbig2Segment *segment, const byte *segment_data)
540 {
541 Jbig2HuffmanParams *params = NULL;
542 Jbig2HuffmanLine *line = NULL;
543
544 segment->result = NULL;
545 if (segment->data_length < 10)
546 goto too_short;
547
548 {
549 /* B.2 1) (B.2.1) Code table flags */
550 const int code_table_flags = segment_data[0];
551 const int HTOOB = code_table_flags & 0x01; /* Bit 0: HTOOB */
552
553 /* Bits 1-3: Number of bits used in code table line prefix size fields */
554 const int HTPS = (code_table_flags >> 1 & 0x07) + 1;
555
556 /* Bits 4-6: Number of bits used in code table line range size fields */
557 const int HTRS = (code_table_flags >> 4 & 0x07) + 1;
558
559 /* B.2 2) (B.2.2) The lower bound of the first table line in the encoded table */
560 const int32_t HTLOW = jbig2_get_int32(segment_data + 1);
561
562 /* B.2 3) (B.2.3) One larger than the upper bound of
563 the last normal table line in the encoded table */
564 const int32_t HTHIGH = jbig2_get_int32(segment_data + 5);
565
566 /* estimated number of lines in this table, used for allocating memory for lines */
567 const size_t lines_max = (segment->data_length * 8 - HTPS * (HTOOB ? 3 : 2)) / (HTPS + HTRS) + (HTOOB ? 3 : 2);
568
569 /* points to a first table line data */
570 const byte *lines_data = segment_data + 9;
571 const size_t lines_data_bitlen = (segment->data_length - 9) * 8; /* length in bit */
572
573 /* bit offset: controls bit reading */
574 size_t boffset = 0;
575
576 /* B.2 4) */
577 int32_t CURRANGELOW = HTLOW;
578 size_t NTEMP = 0;
579
580 #ifdef JBIG2_DEBUG
581 jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, segment->number,
582 "DECODING USER TABLE... Flags: %d, HTOOB: %d, HTPS: %d, HTRS: %d, HTLOW: %d, HTHIGH: %d",
583 code_table_flags, HTOOB, HTPS, HTRS, HTLOW, HTHIGH);
584 #endif
585
586 if (HTLOW >= HTHIGH) {
587 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "invalid Huffman Table range");
588 goto error_exit;
589 }
590
591 /* allocate HuffmanParams & HuffmanLine */
592 params = jbig2_new(ctx, Jbig2HuffmanParams, 1);
593 if (params == NULL) {
594 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate Huffman Table Parameter");
595 goto error_exit;
596 }
597 line = jbig2_new(ctx, Jbig2HuffmanLine, lines_max);
598 if (line == NULL) {
599 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate huffman table lines");
600 goto error_exit;
601 }
602 /* B.2 5) */
603 while (CURRANGELOW < HTHIGH) {
604 /* B.2 5) a) */
605 if (boffset + HTPS >= lines_data_bitlen)
606 goto too_short;
607 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
608 /* B.2 5) b) */
609 if (boffset + HTRS >= lines_data_bitlen)
610 goto too_short;
611 line[NTEMP].RANGELEN = jbig2_table_read_bits(lines_data, &boffset, HTRS);
612 /* B.2 5) c) */
613 line[NTEMP].RANGELOW = CURRANGELOW;
614 CURRANGELOW += (1 << line[NTEMP].RANGELEN);
615 NTEMP++;
616 }
617 /* B.2 6), B.2 7) lower range table line */
618 if (boffset + HTPS >= lines_data_bitlen)
619 goto too_short;
620 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
621 line[NTEMP].RANGELEN = 32;
622 line[NTEMP].RANGELOW = HTLOW - 1;
623 NTEMP++;
624 /* B.2 8), B.2 9) upper range table line */
625 if (boffset + HTPS >= lines_data_bitlen)
626 goto too_short;
627 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
628 line[NTEMP].RANGELEN = 32;
629 line[NTEMP].RANGELOW = HTHIGH;
630 NTEMP++;
631 /* B.2 10) */
632 if (HTOOB) {
633 /* B.2 10) a), B.2 10) b) out-of-bound table line */
634 if (boffset + HTPS >= lines_data_bitlen)
635 goto too_short;
636 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
637 line[NTEMP].RANGELEN = 0;
638 line[NTEMP].RANGELOW = 0;
639 NTEMP++;
640 }
641 if (NTEMP != lines_max) {
642 Jbig2HuffmanLine *new_line = jbig2_renew(ctx, line,
643 Jbig2HuffmanLine, NTEMP);
644
645 if (new_line == NULL) {
646 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to reallocate huffman table lines");
647 goto error_exit;
648 }
649 line = new_line;
650 }
651 params->HTOOB = HTOOB;
652 params->n_lines = NTEMP;
653 params->lines = line;
654 segment->result = params;
655
656 #ifdef JBIG2_DEBUG
657 {
658 int i;
659
660 for (i = 0; i < NTEMP; i++) {
661 jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, segment->number,
662 "Line: %d, PREFLEN: %d, RANGELEN: %d, RANGELOW: %d",
663 i, params->lines[i].PREFLEN, params->lines[i].RANGELEN, params->lines[i].RANGELOW);
664 }
665 }
666 #endif
667 }
668 return 0;
669
670 too_short:
671 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "segment too short");
672 error_exit:
673 jbig2_free(ctx->allocator, line);
674 jbig2_free(ctx->allocator, params);
675 return -1;
676 }
677
678 /* free Jbig2HuffmanParams allocated by jbig2_huffman_table() */
679 void
680 jbig2_table_free(Jbig2Ctx *ctx, Jbig2HuffmanParams *params)
681 {
682 if (params != NULL) {
683 jbig2_free(ctx->allocator, (void *)params->lines);
684 jbig2_free(ctx->allocator, params);
685 }
686 }
687
688 /* find a user supplied table used by 'segment' and by 'index' */
689 const Jbig2HuffmanParams *
690 jbig2_find_table(Jbig2Ctx *ctx, Jbig2Segment *segment, int index)
691 {
692 int i, table_index = 0;
693
694 for (i = 0; i < segment->referred_to_segment_count; i++) {
695 const Jbig2Segment *const rsegment = jbig2_find_segment(ctx, segment->referred_to_segments[i]);
696
697 if (rsegment && (rsegment->flags & 63) == 53) {
698 if (table_index == index)
699 return (const Jbig2HuffmanParams *)rsegment->result;
700 ++table_index;
701 }
702 }
703
704 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "huffman table not found (%d)", index);
705 return NULL;
706 }
707
708 #ifdef TEST
709 #include <stdio.h>
710
711 /* cc -g -o jbig2_huffman.test1 -DTEST jbig2_huffman.c .libs/libjbig2dec.a */
712
713 /* a test bitstream, and a list of the table indices
714 to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */
715 /* this test stream should decode to { 8, 5, oob, 8 } */
716
717 static const byte test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 };
718 static const byte test_tabindex[] = { 4, 2, 2, 1 };
719
720 static int
721 test_get_word1(Jbig2Ctx *ctx, Jbig2WordStream *self, size_t offset, uint32_t *word)
722 {
723 uint32_t val = 0;
724 int ret = 0;
725
726 if (self == NULL || word == NULL)
727 return -1;
728 if (offset >= sizeof (test_stream))
729 return 0;
730
731 if (offset < sizeof(test_stream)) {
732 val |= test_stream[offset] << 24;
733 ret++;
734 }
735 if (offset + 1 < sizeof(test_stream)) {
736 val |= test_stream[offset + 1] << 16;
737 ret++;
738 }
739 if (offset + 2 < sizeof(test_stream)) {
740 val |= test_stream[offset + 2] << 8;
741 ret++;
742 }
743 if (offset + 3 < sizeof(test_stream)) {
744 val |= test_stream[offset + 3];
745 ret++;
746 }
747 *word = val;
748 return ret;
749 }
750
751 static int test1()
752 {
753 Jbig2Ctx *ctx;
754 Jbig2HuffmanTable *tables[5];
755 Jbig2HuffmanState *hs = NULL;
756 Jbig2WordStream ws;
757 bool oob;
758 int32_t code;
759 int i;
760 int success = 0;
761
762 ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
763 if (ctx == NULL) {
764 fprintf(stderr, "Failed to allocate jbig2 context\n");
765 goto cleanup;
766 }
767
768 tables[0] = NULL;
769 tables[1] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_A);
770 tables[2] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_B);
771 tables[3] = NULL;
772 tables[4] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_D);
773 if (tables[1] == NULL || tables[2] == NULL || tables[4] == NULL)
774 {
775 fprintf(stderr, "Failed to build huffman tables");
776 goto cleanup;
777 }
778
779 ws.get_next_word = test_get_word1;
780 hs = jbig2_huffman_new(ctx, &ws);
781 if (hs == NULL) {
782 fprintf(stderr, "Failed to allocate huffman state");
783 goto cleanup;
784 }
785
786 printf("testing jbig2 huffman decoding...");
787 printf("\t(should be 8 5 (oob) 8)\n");
788
789 {
790 int i;
791 int sequence_length = sizeof(test_tabindex);
792
793 for (i = 0; i < sequence_length; i++) {
794 code = jbig2_huffman_get(hs, tables[test_tabindex[i]], &oob);
795 if (oob)
796 printf("(oob) ");
797 else
798 printf("%d ", code);
799 }
800 }
801
802 printf("\n");
803
804 success = 1;
805
806 cleanup:
807 jbig2_huffman_free(ctx, hs);
808 for (i = 0; i < 5; i++)
809 jbig2_release_huffman_table(ctx, tables[i]);
810 jbig2_ctx_free(ctx);
811
812 return success;
813 }
814
815 #include <stdio.h>
816
817 /* a decoding test of each line from each standard table */
818
819 /* test code for Table B.1 - Standard Huffman table A */
820 const int32_t test_output_A[] = {
821 /* line 0, PREFLEN=1, RANGELEN=4, VAL=0..15, 0+VAL */
822 0, /* 0 0000 */
823 1, /* 0 0001 */
824 14, /* 0 1110 */
825 15, /* 0 1111 */
826 /* line 1, PREFLEN=2, RANGELEN=8, VAL=16..271, 10+(VAL-16) */
827 16, /* 10 00000000 */
828 17, /* 10 00000001 */
829 270, /* 10 11111110 */
830 271, /* 10 11111111 */
831 /* line 2, PREFLEN=3, RANGELEN=16, VAL=272..65807, 110+(VAL-272) */
832 272, /* 110 00000000 00000000 */
833 273, /* 110 00000000 00000001 */
834 65806, /* 110 11111111 11111110 */
835 65807, /* 110 11111111 11111111 */
836 /* line 3, PREFLEN=3, RANGELEN=32, VAL=65808..INF, 111+(VAL-65808) */
837 65808, /* 111 00000000 00000000 00000000 00000000 */
838 65809, /* 111 00000000 00000000 00000000 00000001 */
839 };
840 const byte test_input_A[] = {
841 /* 0000 0000 0101 1100 1111 1000 0000 0010 */
842 0x00, 0x5c, 0xf8, 0x02,
843 /* 0000 0001 1011 1111 1010 1111 1111 1100 */
844 0x01, 0xbf, 0xaf, 0xfc,
845 /* 0000 0000 0000 0001 1000 0000 0000 0000 */
846 0x00, 0x01, 0x80, 0x00,
847 /* 0111 0111 1111 1111 1111 0110 1111 1111 */
848 0x77, 0xff, 0xf6, 0xff,
849 /* 1111 1111 1110 0000 0000 0000 0000 0000 */
850 0xff, 0xe0, 0x00, 0x00,
851 /* 0000 0000 0001 1100 0000 0000 0000 0000 */
852 0x00, 0x1c, 0x00, 0x00,
853 /* 0000 0000 0000 01 */
854 0x00, 0x04,
855 };
856
857 /* test code for Table B.2 - Standard Huffman table B */
858 const int32_t test_output_B[] = {
859 /* line 0, PREFLEN=1, RANGELEN=0, VAL=0, 0 */
860 0, /* 0 */
861 /* line 1, PREFLEN=2, RANGELEN=0, VAL=1, 10 */
862 1, /* 10 */
863 /* line 2, PREFLEN=3, RANGELEN=0, VAL=2, 110 */
864 2, /* 110 */
865 /* line 3, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */
866 3, /* 1110 000 */
867 4, /* 1110 001 */
868 9, /* 1110 110 */
869 10, /* 1110 111 */
870 /* line 4, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */
871 11, /* 11110 000000 */
872 12, /* 11110 000001 */
873 73, /* 11110 111110 */
874 74, /* 11110 111111 */
875 /* line 5, PREFLEN=6, RANGELEN=32, VAL=75..INF, 111110+(VAL-75) */
876 75, /* 111110 00000000 00000000 00000000 00000000 */
877 76, /* 111110 00000000 00000000 00000000 00000001 */
878 /* line 6, PREFLEN=6, VAL=OOB, 111111 */
879 /*OOB*/ /* 111111 */
880 };
881 const byte test_input_B[] = {
882 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
883 0x5b, 0x87, 0x1e, 0xdd,
884 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
885 0xfc, 0x07, 0x81, 0xf7,
886 /* 1101 1110 1111 1111 1110 0000 0000 0000 */
887 0xde, 0xff, 0xe0, 0x00,
888 /* 0000 0000 0000 0000 0000 1111 1000 0000 */
889 0x00, 0x00, 0x0f, 0x80,
890 /* 0000 0000 0000 0000 0000 0000 0111 1111 */
891 0x00, 0x00, 0x00, 0x7f,
892 };
893
894 /* test code for Table B.3 - Standard Huffman table C */
895 const int32_t test_output_C[] = {
896 /* line 0, PREFLEN=8, RANGELEN=8, VAL=-256..-1, 11111110+(VAL+256) */
897 -256, /* 11111110 00000000 */
898 -255, /* 11111110 00000001 */
899 -2, /* 11111110 11111110 */
900 -1, /* 11111110 11111111 */
901 /* line 1, PREFLEN=1, RANGELEN=0, VAL=0, 0 */
902 0, /* 0 */
903 /* line 2, PREFLEN=2, RANGELEN=0, VAL=1, 10 */
904 1, /* 10 */
905 /* line 3, PREFLEN=3, RANGELEN=0, VAL=2, 110 */
906 2, /* 110 */
907 /* line 4, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */
908 3, /* 1110 000 */
909 4, /* 1110 001 */
910 9, /* 1110 110 */
911 10, /* 1110 111 */
912 /* line 5, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */
913 11, /* 11110 000000 */
914 12, /* 11110 000001 */
915 73, /* 11110 111110 */
916 74, /* 11110 111111 */
917 /* line 6, PREFLEN=8, RANGELEN=32, VAL=-INF..-257, 11111111+(-257-VAL) */
918 -257, /* 11111111 00000000 00000000 00000000 00000000 */
919 -258, /* 11111111 00000000 00000000 00000000 00000001 */
920 /* line 7, PREFLEN=7, RANGELEN=32, VAL=75..INF, 1111110+(VAL-75) */
921 75, /* 1111110 00000000 00000000 00000000 00000000 */
922 76, /* 1111110 00000000 00000000 00000000 00000001 */
923 /* line 8, PREFLEN=6, VAL=OOB, 111110 */
924 /*OOB*/ /* 111110 */
925 };
926 const byte test_input_C[] = {
927 /* 1111 1110 0000 0000 1111 1110 0000 0001 */
928 0xfe, 0x00, 0xfe, 0x01,
929 /* 1111 1110 1111 1110 1111 1110 1111 1111 */
930 0xfe, 0xfe, 0xfe, 0xff,
931 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
932 0x5b, 0x87, 0x1e, 0xdd,
933 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
934 0xfc, 0x07, 0x81, 0xf7,
935 /* 1101 1110 1111 1111 1111 1100 0000 0000 */
936 0xde, 0xff, 0xfc, 0x00,
937 /* 0000 0000 0000 0000 0000 0011 1111 1100 */
938 0x00, 0x00, 0x03, 0xfc,
939 /* 0000 0000 0000 0000 0000 0000 0000 0111 */
940 0x00, 0x00, 0x00, 0x07,
941 /* 1111 0000 0000 0000 0000 0000 0000 0000 */
942 0xf0, 0x00, 0x00, 0x00,
943 /* 0000 0111 1110 0000 0000 0000 0000 0000 */
944 0x07, 0xe0, 0x00, 0x00,
945 /* 0000 0000 0001 1111 10 */
946 0x00, 0x1f, 0x80,
947 };
948
949 /* test code for Table B.4 - Standard Huffman table D */
950 const int32_t test_output_D[] = {
951 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
952 1, /* 0 */
953 /* line 1, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
954 2, /* 10 */
955 /* line 2, PREFLEN=3, RANGELEN=0, VAL=3, 110 */
956 3, /* 110 */
957 /* line 3, PREFLEN=4, RANGELEN=3, VAL=4..11, 1110+(VAL-4) */
958 4, /* 1110 000 */
959 5, /* 1110 001 */
960 10, /* 1110 110 */
961 11, /* 1110 111 */
962 /* line 4, PREFLEN=5, RANGELEN=6, VAL=12..75, 11110+(VAL-12) */
963 12, /* 11110 000000 */
964 13, /* 11110 000001 */
965 74, /* 11110 111110 */
966 75, /* 11110 111111 */
967 /* line 5, PREFLEN=5, RANGELEN=32, VAL=76..INF, 11111+(VAL-76) */
968 76, /* 11111 00000000 00000000 00000000 00000000 */
969 77, /* 11111 00000000 00000000 00000000 00000001 */
970 };
971 const byte test_input_D[] = {
972 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
973 0x5b, 0x87, 0x1e, 0xdd,
974 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
975 0xfc, 0x07, 0x81, 0xf7,
976 /* 1101 1110 1111 1111 1110 0000 0000 0000 */
977 0xde, 0xff, 0xe0, 0x00,
978 /* 0000 0000 0000 0000 0001 1111 0000 0000 */
979 0x00, 0x00, 0x1f, 0x00,
980 /* 0000 0000 0000 0000 0000 0001 */
981 0x00, 0x00, 0x01,
982 };
983
984 /* test code for Table B.5 - Standard Huffman table E */
985 const int32_t test_output_E[] = {
986 /* line 0, PREFLEN=7, RANGELEN=8, VAL=-255..0, 1111110+(VAL+255) */
987 -255, /* 1111110 00000000 */
988 -254, /* 1111110 00000001 */
989 -1, /* 1111110 11111110 */
990 0, /* 1111110 11111111 */
991 /* line 1, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
992 1, /* 0 */
993 /* line 2, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
994 2, /* 10 */
995 /* line 3, PREFLEN=3, RANGELEN=0, VAL=3, 110 */
996 3, /* 110 */
997 /* line 4, PREFLEN=4, RANGELEN=3, VAL=4..11, 1110+(VAL-4) */
998 4, /* 1110 000 */
999 5, /* 1110 001 */
1000 10, /* 1110 110 */
1001 11, /* 1110 111 */
1002 /* line 5, PREFLEN=5, RANGELEN=6, VAL=12..75, 11110+(VAL-12) */
1003 12, /* 11110 000000 */
1004 13, /* 11110 000001 */
1005 74, /* 11110 111110 */
1006 75, /* 11110 111111 */
1007 /* line 6, PREFLEN=7, RANGELEN=32, VAL=-INF..-256, 1111111+(-256-VAL) */
1008 -256, /* 1111111 00000000 00000000 00000000 00000000 */
1009 -257, /* 1111111 00000000 00000000 00000000 00000001 */
1010 /* line 6, PREFLEN=6, RANGELEN=32, VAL=76..INF, 111110+(VAL-76) */
1011 76, /* 111110 00000000 00000000 00000000 00000000 */
1012 77, /* 111110 00000000 00000000 00000000 00000001 */
1013 };
1014 const byte test_input_E[] = {
1015 /* 1111 1100 0000 0001 1111 1000 0000 0111 */
1016 0xfc, 0x01, 0xf8, 0x07,
1017 /* 1111 0111 1111 0111 1110 1111 1111 0101 */
1018 0xf7, 0xf7, 0xef, 0xf5,
1019 /* 1011 1000 0111 0001 1110 1101 1101 1111 */
1020 0xb8, 0x71, 0xed, 0xdf,
1021 /* 1100 0000 0111 1000 0001 1111 0111 1101 */
1022 0xc0, 0x78, 0x1f, 0x7d,
1023 /* 1110 1111 1111 1111 1000 0000 0000 0000 */
1024 0xef, 0xff, 0x80, 0x00,
1025 /* 0000 0000 0000 0000 0111 1111 0000 0000 */
1026 0x00, 0x00, 0x7f, 0x00,
1027 /* 0000 0000 0000 0000 0000 0001 1111 1000 */
1028 0x00, 0x00, 0x01, 0xf8,
1029 /* 0000 0000 0000 0000 0000 0000 0000 0011 */
1030 0x00, 0x00, 0x00, 0x03,
1031 /* 1110 0000 0000 0000 0000 0000 0000 0000 */
1032 0xe0, 0x00, 0x00, 0x00,
1033 /* 0001 */
1034 0x10,
1035 };
1036
1037 /* test code for Table B.6 - Standard Huffman table F */
1038 const int32_t test_output_F[] = {
1039 /* line 0, PREFLEN=5, RANGELEN=10, VAL=-2048..-1025, 11100+(VAL+2048) */
1040 -2048, /* 11100 00000000 00 */
1041 -2047, /* 11100 00000000 01 */
1042 -1026, /* 11100 11111111 10 */
1043 -1025, /* 11100 11111111 11 */
1044 /* line 1, PREFLEN=4, RANGELEN=9, VAL=-1024..-513, 1000+(VAL+1024) */
1045 -1024, /* 1000 00000000 0 */
1046 -1023, /* 1000 00000000 1 */
1047 -514, /* 1000 11111111 0 */
1048 -513, /* 1000 11111111 1 */
1049 /* line 2, PREFLEN=4, RANGELEN=8, VAL=-512..-257, 1001+(VAL+512) */
1050 -512, /* 1001 00000000 */
1051 -511, /* 1001 00000001 */
1052 -258, /* 1001 11111110 */
1053 -257, /* 1001 11111111 */
1054 /* line 3, PREFLEN=4, RANGELEN=7, VAL=-256..-129, 1010+(VAL+256) */
1055 -256, /* 1010 0000000 */
1056 -255, /* 1010 0000001 */
1057 -130, /* 1010 1111110 */
1058 -129, /* 1010 1111111 */
1059 /* line 4, PREFLEN=5, RANGELEN=6, VAL=-128..-65, 11101+(VAL+128) */
1060 -128, /* 11101 000000 */
1061 -127, /* 11101 000001 */
1062 -66, /* 11101 111110 */
1063 -65, /* 11101 111111 */
1064 /* line 5, PREFLEN=5, RANGELEN=5, VAL=-64..-33, 11110+(VAL+64) */
1065 -64, /* 11110 00000 */
1066 -63, /* 11110 00001 */
1067 -34, /* 11110 11110 */
1068 -33, /* 11110 11111 */
1069 /* line 6, PREFLEN=4, RANGELEN=5, VAL=-32..-1, 1011+(VAL+32) */
1070 -32, /* 1011 00000 */
1071 -31, /* 1011 00001 */
1072 -2, /* 1011 11110 */
1073 -1, /* 1011 11111 */
1074 /* line 7, PREFLEN=2, RANGELEN=7, VAL=0..127, 00+VAL */
1075 0, /* 00 0000000 */
1076 1, /* 00 0000001 */
1077 126, /* 00 1111110 */
1078 127, /* 00 1111111 */
1079 /* line 8, PREFLEN=3, RANGELEN=7, VAL=128..255, 010+(VAL-128) */
1080 128, /* 010 0000000 */
1081 129, /* 010 0000001 */
1082 254, /* 010 1111110 */
1083 255, /* 010 1111111 */
1084 /* line 9, PREFLEN=3, RANGELEN=8, VAL=256..511, 011+(VAL-256) */
1085 256, /* 011 00000000 */
1086 257, /* 011 00000001 */
1087 510, /* 011 11111110 */
1088 511, /* 011 11111111 */
1089 /* line 10, PREFLEN=4, RANGELEN=9, VAL=512..1023, 1100+(VAL-512) */
1090 512, /* 1100 00000000 0 */
1091 513, /* 1100 00000000 1 */
1092 1022, /* 1100 11111111 0 */
1093 1023, /* 1100 11111111 1 */
1094 /* line 11, PREFLEN=4, RANGELEN=10, VAL=1024..2047, 1101+(VAL-1024) */
1095 1024, /* 1101 00000000 00 */
1096 1025, /* 1101 00000000 01 */
1097 2046, /* 1101 11111111 10 */
1098 2047, /* 1101 11111111 11 */
1099 /* line 12, PREFLEN=6, RANGELEN=32, VAL=-INF..-2049, 111110+(-2049-VAL) */
1100 -2049, /* 111110 00000000 00000000 00000000 00000000 */
1101 -2050, /* 111110 00000000 00000000 00000000 00000001 */
1102 /* line 13, PREFLEN=6, RANGELEN=32, VAL=2048..INF, 111111+(VAL-2048) */
1103 2048, /* 111111 00000000 00000000 00000000 00000000 */
1104 2049, /* 111111 00000000 00000000 00000000 00000001 */
1105 };
1106 const byte test_input_F[] = {
1107 /* 1110 0000 0000 0001 1100 0000 0000 0111 */
1108 0xe0, 0x01, 0xc0, 0x07,
1109 /* 1001 1111 1111 0111 0011 1111 1111 1000 */
1110 0x9f, 0xf7, 0x3f, 0xf8,
1111 /* 0000 0000 0100 0000 0000 0110 0011 1111 */
1112 0x00, 0x40, 0x06, 0x3f,
1113 /* 1101 0001 1111 1111 1001 0000 0000 1001 */
1114 0xd1, 0xff, 0x90, 0x09,
1115 /* 0000 0001 1001 1111 1110 1001 1111 1111 */
1116 0x01, 0x9f, 0xe9, 0xff,
1117 /* 1010 0000 0001 0100 0000 0110 1011 1111 */
1118 0xa0, 0x14, 0x06, 0xbf,
1119 /* 0101 0111 1111 1110 1000 0001 1101 0000 */
1120 0x57, 0xfe, 0x81, 0xd0,
1121 /* 0111 1011 1111 0111 0111 1111 1111 0000 */
1122 0x7b, 0xf7, 0x7f, 0xf0,
1123 /* 0011 1100 0001 1111 0111 1011 1101 1111 */
1124 0x3c, 0x1f, 0x7b, 0xdf,
1125 /* 1011 0000 0101 1000 0110 1111 1101 0111 */
1126 0xb0, 0x58, 0x6f, 0xd7,
1127 /* 1111 0000 0000 0000 0000 0100 1111 1100 */
1128 0xf0, 0x00, 0x04, 0xfc,
1129 /* 0111 1111 0100 0000 0001 0000 0001 0101 */
1130 0x7f, 0x40, 0x10, 0x15,
1131 /* 1111 1001 0111 1111 0110 0000 0000 1100 */
1132 0xf9, 0x7f, 0x60, 0x0c,
1133 /* 0000 0101 1111 1111 0011 1111 1111 1100 */
1134 0x05, 0xff, 0x3f, 0xfc,
1135 /* 0000 0000 0110 0000 0000 0111 0011 1111 */
1136 0x00, 0x60, 0x07, 0x3f,
1137 /* 1101 1001 1111 1111 1101 0000 0000 0011 */
1138 0xd9, 0xff, 0xd0, 0x03,
1139 /* 0100 0000 0001 1101 1111 1111 1011 0111 */
1140 0x40, 0x1d, 0xff, 0xb7,
1141 /* 1111 1111 1111 1000 0000 0000 0000 0000 */
1142 0xff, 0xf8, 0x00, 0x00,
1143 /* 0000 0000 0000 0011 1110 0000 0000 0000 */
1144 0x00, 0x03, 0xe0, 0x00,
1145 /* 0000 0000 0000 0000 0001 1111 1100 0000 */
1146 0x00, 0x00, 0x1f, 0xc0,
1147 /* 0000 0000 0000 0000 0000 0000 0011 1111 */
1148 0x00, 0x00, 0x00, 0x3f,
1149 /* 0000 0000 0000 0000 0000 0000 0000 0001 */
1150 0x00, 0x00, 0x00, 0x01,
1151 };
1152
1153 /* test code for Table B.7 - Standard Huffman table G */
1154 const int32_t test_output_G[] = {
1155 /* line 0, PREFLEN=4, RANGELEN=9, VAL=-1024..-513, 1000+(VAL+1024) */
1156 -1024, /* 1000 00000000 0 */
1157 -1023, /* 1000 00000000 1 */
1158 -514, /* 1000 11111111 0 */
1159 -513, /* 1000 11111111 1 */
1160 /* line 1, PREFLEN=3, RANGELEN=8, VAL=-512..-257, 000+(VAL+512) */
1161 -512, /* 000 00000000 */
1162 -511, /* 000 00000001 */
1163 -258, /* 000 11111110 */
1164 -257, /* 000 11111111 */
1165 /* line 2, PREFLEN=4, RANGELEN=7, VAL=-256..-129, 1001+(VAL+256) */
1166 -256, /* 1001 0000000 */
1167 -255, /* 1001 0000001 */
1168 -130, /* 1001 1111110 */
1169 -129, /* 1001 1111111 */
1170 /* line 3, PREFLEN=5, RANGELEN=6, VAL=-128..-65, 11010+(VAL+128) */
1171 -128, /* 11010 000000 */
1172 -127, /* 11010 000001 */
1173 -66, /* 11010 111110 */
1174 -65, /* 11010 111111 */
1175 /* line 4, PREFLEN=5, RANGELEN=5, VAL=-64..-33, 11011+(VAL+64) */
1176 -64, /* 11011 00000 */
1177 -63, /* 11011 00001 */
1178 -34, /* 11011 11110 */
1179 -33, /* 11011 11111 */
1180 /* line 5, PREFLEN=4, RANGELEN=5, VAL=-32..-1, 1010+(VAL+32) */
1181 -32, /* 1010 00000 */
1182 -31, /* 1010 00001 */
1183 -2, /* 1010 11110 */
1184 -1, /* 1010 11111 */
1185 /* line 6, PREFLEN=4, RANGELEN=5, VAL=0..31, 1011+VAL */
1186 0, /* 1011 00000 */
1187 1, /* 1011 00001 */
1188 30, /* 1011 11110 */
1189 31, /* 1011 11111 */
1190 /* line 7, PREFLEN=5, RANGELEN=5, VAL=32..63, 11100+(VAL-32) */
1191 32, /* 11100 00000 */
1192 33, /* 11100 00001 */
1193 62, /* 11100 11110 */
1194 63, /* 11100 11111 */
1195 /* line 8, PREFLEN=5, RANGELEN=6, VAL=64..127, 11101+(VAL-64) */
1196 64, /* 11101 000000 */
1197 65, /* 11101 000001 */
1198 126, /* 11101 111110 */
1199 127, /* 11101 111111 */
1200 /* line 9, PREFLEN=4, RANGELEN=7, VAL=128..255, 1100+(VAL-128) */
1201 128, /* 1100 0000000 */
1202 129, /* 1100 0000001 */
1203 254, /* 1100 1111110 */
1204 255, /* 1100 1111111 */
1205 /* line 10, PREFLEN=3, RANGELEN=8, VAL=256..511, 001+(VAL-256) */
1206 256, /* 001 00000000 */
1207 257, /* 001 00000001 */
1208 510, /* 001 11111110 */
1209 511, /* 001 11111111 */
1210 /* line 11, PREFLEN=3, RANGELEN=9, VAL=512..1023, 010+(VAL-512) */
1211 512, /* 010 00000000 0 */
1212 513, /* 010 00000000 1 */
1213 1022, /* 010 11111111 0 */
1214 1023, /* 010 11111111 1 */
1215 /* line 12, PREFLEN=3, RANGELEN=10, VAL=1024..2047, 011+(VAL-1024) */
1216 1024, /* 011 00000000 00 */
1217 1025, /* 011 00000000 01 */
1218 2046, /* 011 11111111 10 */
1219 2047, /* 011 11111111 11 */
1220 /* line 13, PREFLEN=5, RANGELEN=32, VAL=-INF..-1025, 11110+(-1025-VAL) */
1221 -1025, /* 11110 00000000 00000000 00000000 00000000 */
1222 -1026, /* 11110 00000000 00000000 00000000 00000001 */
1223 /* line 14, PREFLEN=5, RANGELEN=32, VAL=2048..INF, 11111+(VAL-2048) */
1224 2048, /* 11111 00000000 00000000 00000000 00000000 */
1225 2049, /* 11111 00000000 00000000 00000000 00000001 */
1226 };
1227 const byte test_input_G[] = {
1228 /* 1000 0000 0000 0100 0000 0000 0110 0011 */
1229 0x80, 0x04, 0x00, 0x63,
1230 /* 1111 1101 0001 1111 1111 0000 0000 0000 */
1231 0xfd, 0x1f, 0xf0, 0x00,
1232 /* 0000 0000 0100 0111 1111 0000 1111 1111 */
1233 0x00, 0x47, 0xf0, 0xff,
1234 /* 1001 0000 0001 0010 0000 0110 0111 1111 */
1235 0x90, 0x12, 0x06, 0x7f,
1236 /* 0100 1111 1111 1101 0000 0001 1010 0000 */
1237 0x4f, 0xfd, 0x01, 0xa0,
1238 /* 0111 0101 1111 0110 1011 1111 1101 1000 */
1239 0x75, 0xf6, 0xbf, 0xd8,
1240 /* 0011 0110 0001 1101 1111 1011 0111 1111 */
1241 0x36, 0x1d, 0xfb, 0x7f,
1242 /* 1010 0000 0101 0000 0110 1011 1101 0101 */
1243 0xa0, 0x50, 0x6b, 0xd5,
1244 /* 1111 1011 0000 0101 1000 0110 1111 1101 */
1245 0xfb, 0x05, 0x86, 0xfd,
1246 /* 0111 1111 1110 0000 0011 1000 0001 1110 */
1247 0x7f, 0xe0, 0x38, 0x1e,
1248 /* 0111 1011 1001 1111 1110 1000 0001 1101 */
1249 0x7b, 0x9f, 0xe8, 0x1d,
1250 /* 0000 0111 1011 1111 0111 0111 1111 1100 */
1251 0x07, 0xbf, 0x77, 0xfc,
1252 /* 0000 0001 1000 0000 0111 0011 1111 0110 */
1253 0x01, 0x80, 0x73, 0xf6,
1254 /* 0111 1111 0010 0000 0000 0100 0000 0100 */
1255 0x7f, 0x20, 0x04, 0x04,
1256 /* 1111 1111 0001 1111 1111 0100 0000 0000 */
1257 0xff, 0x1f, 0xf4, 0x00,
1258 /* 0100 0000 0001 0101 1111 1110 0101 1111 */
1259 0x40, 0x15, 0xfe, 0x5f,
1260 /* 1111 0110 0000 0000 0011 0000 0000 0101 */
1261 0xf6, 0x00, 0x30, 0x05,
1262 /* 1111 1111 1100 1111 1111 1111 1111 0000 */
1263 0xff, 0xcf, 0xff, 0xf0,
1264 /* 0000 0000 0000 0000 0000 0000 0000 0111 */
1265 0x00, 0x00, 0x00, 0x07,
1266 /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1267 0x80, 0x00, 0x00, 0x00,
1268 /* 0111 1110 0000 0000 0000 0000 0000 0000 */
1269 0x7e, 0x00, 0x00, 0x00,
1270 /* 0000 0001 1111 0000 0000 0000 0000 0000 */
1271 0x01, 0xf0, 0x00, 0x00,
1272 /* 0000 0000 0001 */
1273 0x00, 0x10,
1274 };
1275
1276 /* test code for Table B.8 - Standard Huffman table H */
1277 const int32_t test_output_H[] = {
1278 /* line 0, PREFLEN=8, RANGELEN=3, VAL=-15..-8, 11111100+(VAL+15) */
1279 -15, /* 11111100 000 */
1280 -14, /* 11111100 001 */
1281 -9, /* 11111100 110 */
1282 -8, /* 11111100 111 */
1283 /* line 1, PREFLEN=9, RANGELEN=1, VAL=-7..-6, 111111100+(VAL+7) */
1284 -7, /* 111111100 0 */
1285 -6, /* 111111100 1 */
1286 /* line 2, PREFLEN=8, RANGELEN=1, VAL=-5..-4, 11111101+(VAL+5) */
1287 -5, /* 11111101 0 */
1288 -4, /* 11111101 1 */
1289 /* line 3, PREFLEN=9, RANGELEN=0, VAL=-3, 111111101 */
1290 -3, /* 111111101 */
1291 /* line 4, PREFLEN=7, RANGELEN=0, VAL=-2, 1111100 */
1292 -2, /* 1111100 */
1293 /* line 5, PREFLEN=4, RANGELEN=0, VAL=-1, 1010 */
1294 -1, /* 1010 */
1295 /* line 6, PREFLEN=2, RANGELEN=1, VAL=0..1, 00+VAL */
1296 0, /* 00 0 */
1297 1, /* 00 1 */
1298 /* line 7, PREFLEN=5, RANGELEN=0, VAL=2, 11010 */
1299 2, /* 11010 */
1300 /* line 8, PREFLEN=6, RANGELEN=0, VAL=3, 111010 */
1301 3, /* 111010 */
1302 /* line 9, PREFLEN=3, RANGELEN=4, VAL=4..19, 100+(VAL-4) */
1303 4, /* 100 0000 */
1304 5, /* 100 0001 */
1305 18, /* 100 1110 */
1306 19, /* 100 1111 */
1307 /* line 10, PREFLEN=6, RANGELEN=1, VAL=20..21, 111011+(VAL-20) */
1308 20, /* 111011 0 */
1309 21, /* 111011 1 */
1310 /* line 11, PREFLEN=4, RANGELEN=4, VAL=22..37, 1011+(VAL-22) */
1311 22, /* 1011 0000 */
1312 23, /* 1011 0001 */
1313 36, /* 1011 1110 */
1314 37, /* 1011 1111 */
1315 /* line 12, PREFLEN=4, RANGELEN=5, VAL=38..69, 1100+(VAL-38) */
1316 38, /* 1100 00000 */
1317 39, /* 1100 00001 */
1318 68, /* 1100 11110 */
1319 69, /* 1100 11111 */
1320 /* line 13, PREFLEN=5, RANGELEN=6, VAL=70..133, 11011+(VAL-70) */
1321 70, /* 11011 000000 */
1322 71, /* 11011 000001 */
1323 132, /* 11011 111110 */
1324 133, /* 11011 111111 */
1325 /* line 14, PREFLEN=5, RANGELEN=7, VAL=134..261, 11100+(VAL-134) */
1326 134, /* 11100 0000000 */
1327 135, /* 11100 0000001 */
1328 260, /* 11100 1111110 */
1329 261, /* 11100 1111111 */
1330 /* line 15, PREFLEN=6, RANGELEN=7, VAL=262..389, 111100+(VAL-262) */
1331 262, /* 111100 0000000 */
1332 263, /* 111100 0000001 */
1333 388, /* 111100 1111110 */
1334 389, /* 111100 1111111 */
1335 /* line 16, PREFLEN=7, RANGELEN=8, VAL=390..645, 1111101+(VAL-390) */
1336 390, /* 1111101 00000000 */
1337 391, /* 1111101 00000001 */
1338 644, /* 1111101 11111110 */
1339 645, /* 1111101 11111111 */
1340 /* line 17, PREFLEN=6, RANGELEN=10, VAL=646..1669, 111101+(VAL-646) */
1341 646, /* 111101 00000000 00 */
1342 647, /* 111101 00000000 01 */
1343 1668, /* 111101 11111111 10 */
1344 1669, /* 111101 11111111 11 */
1345 /* line 18, PREFLEN=9, RANGELEN=32, VAL=-INF..-16, 111111110+(-16-VAL) */
1346 -16, /* 111111110 00000000 00000000 00000000 00000000 */
1347 -17, /* 111111110 00000000 00000000 00000000 00000001 */
1348 /* line 19, PREFLEN=9, RANGELEN=32, VAL=1670..INF, 111111111+(VAL-1670) */
1349 1670, /* 111111111 00000000 00000000 00000000 00000000 */
1350 1671, /* 111111111 00000000 00000000 00000000 00000001 */
1351 /* line 20, PREFLEN=2, VAL=OOB, 01 */
1352 /*OOB*/ /* 01 */
1353 };
1354 const byte test_input_H[] = {
1355 /* 1111 1100 0001 1111 1000 0111 1111 0011 */
1356 0xfc, 0x1f, 0x87, 0xf3,
1357 /* 0111 1110 0111 1111 1110 0011 1111 1001 */
1358 0x7e, 0x7f, 0xe3, 0xf9,
1359 /* 1111 1101 0111 1110 1111 1111 1011 1111 */
1360 0xfd, 0x7e, 0xff, 0xbf,
1361 /* 0010 1000 0001 1101 0111 0101 0000 0010 */
1362 0x28, 0x1d, 0x75, 0x02,
1363 /* 0000 1100 1110 1001 1111 1101 1011 1011 */
1364 0x0c, 0xe9, 0xfd, 0xbb,
1365 /* 1101 1000 0101 1000 1101 1111 0101 1111 */
1366 0xd8, 0x58, 0xdf, 0x5f,
1367 /* 1110 0000 0011 0000 0011 1001 1110 1100 */
1368 0xe0, 0x30, 0x39, 0xec,
1369 /* 1111 1110 1100 0000 1101 1000 0011 1011 */
1370 0xfe, 0xc0, 0xd8, 0x3b,
1371 /* 1111 1011 0111 1111 1111 0000 0000 0111 */
1372 0xfb, 0x7f, 0xf0, 0x07,
1373 /* 0000 0000 1111 0011 1111 0111 0011 1111 */
1374 0x00, 0xf3, 0xf7, 0x3f,
1375 /* 1111 1000 0000 0011 1100 0000 0011 1110 */
1376 0xf8, 0x03, 0xc0, 0x3e,
1377 /* 0111 1110 1111 0011 1111 1111 1101 0000 */
1378 0x7e, 0xf3, 0xff, 0xd0,
1379 /* 0000 1111 1010 0000 0011 1111 0111 1111 */
1380 0x0f, 0xa0, 0x3f, 0x7f,
1381 /* 1011 1110 1111 1111 1111 1010 0000 0000 */
1382 0xbe, 0xff, 0xfa, 0x00,
1383 /* 0111 1010 0000 0000 1111 1011 1111 1111 */
1384 0x7a, 0x00, 0xfb, 0xff,
1385 /* 0111 1011 1111 1111 1111 1111 1000 0000 */
1386 0x7b, 0xff, 0xff, 0x80,
1387 /* 0000 0000 0000 0000 0000 0000 0011 1111 */
1388 0x00, 0x00, 0x00, 0x3f,
1389 /* 1100 0000 0000 0000 0000 0000 0000 0000 */
1390 0xc0, 0x00, 0x00, 0x00,
1391 /* 0011 1111 1111 0000 0000 0000 0000 0000 */
1392 0x3f, 0xf0, 0x00, 0x00,
1393 /* 0000 0000 0000 1111 1111 1000 0000 0000 */
1394 0x00, 0x0f, 0xf8, 0x00,
1395 /* 0000 0000 0000 0000 0000 101 */
1396 0x00, 0x00, 0x0a,
1397 };
1398
1399 /* test code for Table B.9 - Standard Huffman table I */
1400 const int32_t test_output_I[] = {
1401 /* line 0, PREFLEN=8, RANGELEN=4, VAL=-31..-16, 11111100+(VAL+31) */
1402 -31, /* 11111100 0000 */
1403 -30, /* 11111100 0001 */
1404 -17, /* 11111100 1110 */
1405 -16, /* 11111100 1111 */
1406 /* line 1, PREFLEN=9, RANGELEN=2, VAL=-15..-12, 111111100+(VAL+15) */
1407 -15, /* 111111100 00 */
1408 -14, /* 111111100 01 */
1409 -13, /* 111111100 10 */
1410 -12, /* 111111100 11 */
1411 /* line 2, PREFLEN=8, RANGELEN=2, VAL=-11..-8, 11111101+(VAL+11) */
1412 -11, /* 11111101 00 */
1413 -10, /* 11111101 01 */
1414 -9, /* 11111101 10 */
1415 -8, /* 11111101 11 */
1416 /* line 3, PREFLEN=9, RANGELEN=1, VAL=-7..-6, 111111101+(VAL+7) */
1417 -7, /* 111111101 0 */
1418 -6, /* 111111101 1 */
1419 /* line 4, PREFLEN=7, RANGELEN=1, VAL=-5..-4, 1111100+(VAL+5) */
1420 -5, /* 1111100 0 */
1421 -4, /* 1111100 1 */
1422 /* line 5, PREFLEN=4, RANGELEN=1, VAL=-3..-2, 1010+(VAL+3) */
1423 -3, /* 1010 0 */
1424 -2, /* 1010 1 */
1425 /* line 6, PREFLEN=3, RANGELEN=1, VAL=-1..0, 010+(VAL+1) */
1426 -1, /* 010 0 */
1427 0, /* 010 1 */
1428 /* line 7, PREFLEN=3, RANGELEN=1, VAL=1..2, 011+(VAL-1) */
1429 1, /* 011 0 */
1430 2, /* 011 1 */
1431 /* line 8, PREFLEN=5, RANGELEN=1, VAL=3..4, 11010+(VAL-3) */
1432 3, /* 11010 0 */
1433 4, /* 11010 1 */
1434 /* line 9, PREFLEN=6, RANGELEN=1, VAL=5..6, 111010+(VAL-5) */
1435 5, /* 111010 0 */
1436 6, /* 111010 1 */
1437 /* line 10, PREFLEN=3, RANGELEN=5, VAL=7..38, 100+(VAL-7) */
1438 7, /* 100 00000 */
1439 8, /* 100 00001 */
1440 37, /* 100 11110 */
1441 38, /* 100 11111 */
1442 /* line 11, PREFLEN=6, RANGELEN=2, VAL=39..42, 111011+(VAL-39) */
1443 39, /* 111011 00 */
1444 40, /* 111011 01 */
1445 41, /* 111011 10 */
1446 42, /* 111011 11 */
1447 /* line 12, PREFLEN=4, RANGELEN=5, VAL=43..74, 1011+(VAL-43) */
1448 43, /* 1011 00000 */
1449 44, /* 1011 00001 */
1450 73, /* 1011 11110 */
1451 74, /* 1011 11111 */
1452 /* line 13, PREFLEN=4, RANGELEN=6, VAL=75..138, 1100+(VAL-75) */
1453 75, /* 1100 000000 */
1454 76, /* 1100 000001 */
1455 137, /* 1100 111110 */
1456 138, /* 1100 111111 */
1457 /* line 14, PREFLEN=5, RANGELEN=7, VAL=139..266, 11011+(VAL-139) */
1458 139, /* 11011 0000000 */
1459 140, /* 11011 0000001 */
1460 265, /* 11011 1111110 */
1461 266, /* 11011 1111111 */
1462 /* line 15, PREFLEN=5, RANGELEN=8, VAL=267..522, 11100+(VAL-267) */
1463 267, /* 11100 00000000 */
1464 268, /* 11100 00000001 */
1465 521, /* 11100 11111110 */
1466 522, /* 11100 11111111 */
1467 /* line 16, PREFLEN=6, RANGELEN=8, VAL=523..778, 111100+(VAL-523) */
1468 523, /* 111100 00000000 */
1469 524, /* 111100 00000001 */
1470 777, /* 111100 11111110 */
1471 778, /* 111100 11111111 */
1472 /* line 17, PREFLEN=7, RANGELEN=9, VAL=779..1290, 1111101+(VAL-779) */
1473 779, /* 1111101 00000000 0 */
1474 780, /* 1111101 00000000 1 */
1475 1289, /* 1111101 11111111 0 */
1476 1290, /* 1111101 11111111 1 */
1477 /* line 18, PREFLEN=6, RANGELEN=11, VAL=1291..3338, 111101+(VAL-1291) */
1478 1291, /* 111101 00000000 000 */
1479 1292, /* 111101 00000000 001 */
1480 3337, /* 111101 11111111 110 */
1481 3338, /* 111101 11111111 111 */
1482 /* line 19, PREFLEN=9, RANGELEN=32, VAL=-INF..-32, 111111110+(-32-VAL) */
1483 -32, /* 111111110 00000000 00000000 00000000 00000000 */
1484 -33, /* 111111110 00000000 00000000 00000000 00000001 */
1485 /* line 20, PREFLEN=9, RANGELEN=32, VAL=3339..INF, 111111111+(VAL-3339) */
1486 3339, /* 111111111 00000000 00000000 00000000 00000000 */
1487 3340, /* 111111111 00000000 00000000 00000000 00000001 */
1488 /* line 21, PREFLEN=2, VAL=OOB, 00 */
1489 /*OOB*/ /* 00 */
1490 };
1491 const byte test_input_I[] = {
1492 /* 1111 1100 0000 1111 1100 0001 1111 1100 */
1493 0xfc, 0x0f, 0xc1, 0xfc,
1494 /* 1110 1111 1100 1111 1111 1110 0001 1111 */
1495 0xef, 0xcf, 0xfe, 0x1f,
1496 /* 1100 0111 1111 1001 0111 1111 0011 1111 */
1497 0xc7, 0xf9, 0x7f, 0x3f,
1498 /* 1101 0011 1111 0101 1111 1101 1011 1111 */
1499 0xd3, 0xf5, 0xfd, 0xbf,
1500 /* 0111 1111 1110 1011 1111 1011 1111 1000 */
1501 0x7f, 0xeb, 0xfb, 0xf8,
1502 /* 1111 1001 1010 0101 0101 0001 0101 1001 */
1503 0xf9, 0xa5, 0x51, 0x59,
1504 /* 1111 0100 1101 0111 1010 0111 0101 1000 */
1505 0xf4, 0xd7, 0xa7, 0x58,
1506 /* 0000 1000 0001 1001 1110 1001 1111 1110 */
1507 0x08, 0x19, 0xe9, 0xfe,
1508 /* 1100 1110 1101 1110 1110 1110 1111 1011 */
1509 0xce, 0xde, 0xee, 0xfb,
1510 /* 0000 0101 1000 0110 1111 1101 0111 1111 */
1511 0x05, 0x86, 0xfd, 0x7f,
1512 /* 1100 0000 0011 0000 0001 1100 1111 1011 */
1513 0xc0, 0x30, 0x1c, 0xfb,
1514 /* 0011 1111 1101 1000 0000 1101 1000 0001 */
1515 0x3f, 0xd8, 0x0d, 0x81,
1516 /* 1101 1111 1110 1101 1111 1111 1110 0000 */
1517 0xdf, 0xed, 0xff, 0xe0,
1518 /* 0000 0111 0000 0000 0111 1001 1111 1101 */
1519 0x07, 0x00, 0x79, 0xfd,
1520 /* 1100 1111 1111 1111 0000 0000 0011 1100 */
1521 0xcf, 0xff, 0x00, 0x3c,
1522 /* 0000 0001 1111 0011 1111 1011 1100 1111 */
1523 0x01, 0xf3, 0xfb, 0xcf,
1524 /* 1111 1111 1010 0000 0000 1111 1010 0000 */
1525 0xff, 0xa0, 0x0f, 0xa0,
1526 /* 0001 1111 1011 1111 1110 1111 1011 1111 */
1527 0x1f, 0xbf, 0xef, 0xbf,
1528 /* 1111 1111 0100 0000 0000 0111 1010 0000 */
1529 0xff, 0x40, 0x07, 0xa0,
1530 /* 0000 0111 1101 1111 1111 1101 1110 1111 */
1531 0x07, 0xdf, 0xfd, 0xef,
1532 /* 1111 1111 1111 1111 0000 0000 0000 0000 */
1533 0xff, 0xff, 0x00, 0x00,
1534 /* 0000 0000 0000 0000 0111 1111 1000 0000 */
1535 0x00, 0x00, 0x7f, 0x80,
1536 /* 0000 0000 0000 0000 0000 0000 0111 1111 */
1537 0x00, 0x00, 0x00, 0x7f,
1538 /* 1110 0000 0000 0000 0000 0000 0000 0000 */
1539 0xe0, 0x00, 0x00, 0x00,
1540 /* 0001 1111 1111 0000 0000 0000 0000 0000 */
1541 0x1f, 0xf0, 0x00, 0x00,
1542 /* 0000 0000 0001 00 */
1543 0x00, 0x10,
1544 };
1545
1546 /* test code for Table B.10 - Standard Huffman table J */
1547 const int32_t test_output_J[] = {
1548 /* line 0, PREFLEN=7, RANGELEN=4, VAL=-21..-6, 1111010+(VAL+21) */
1549 -21, /* 1111010 0000 */
1550 -20, /* 1111010 0001 */
1551 -7, /* 1111010 1110 */
1552 -6, /* 1111010 1111 */
1553 /* line 1, PREFLEN=8, RANGELEN=0, VAL=-5, 11111100 */
1554 -5, /* 11111100 */
1555 /* line 2, PREFLEN=7, RANGELEN=0, VAL=-5, 1111011 */
1556 -4, /* 1111011 */
1557 /* line 3, PREFLEN=5, RANGELEN=0, VAL=-3, 11000 */
1558 -3, /* 11000 */
1559 /* line 4, PREFLEN=2, RANGELEN=2, VAL=-2..1, 00+(VAL+2) */
1560 -2, /* 00 00 */
1561 -1, /* 00 01 */
1562 0, /* 00 10 */
1563 1, /* 00 11 */
1564 /* line 5, PREFLEN=5, RANGELEN=0, VAL=2, 11001 */
1565 2, /* 11001 */
1566 /* line 6, PREFLEN=6, RANGELEN=0, VAL=3, 110110 */
1567 3, /* 110110 */
1568 /* line 7, PREFLEN=7, RANGELEN=0, VAL=4, 1111100 */
1569 4, /* 1111100 */
1570 /* line 8, PREFLEN=8, RANGELEN=0, VAL=5, 11111101 */
1571 5, /* 11111101 */
1572 /* line 9, PREFLEN=2, RANGELEN=6, VAL=6..69, 01+(VAL-6) */
1573 6, /* 01 000000 */
1574 7, /* 01 000001 */
1575 68, /* 01 111110 */
1576 69, /* 01 111111 */
1577 /* line 8, PREFLEN=5, RANGELEN=5, VAL=70..101, 11010+(VAL-70) */
1578 70, /* 11010 00000 */
1579 71, /* 11010 00001 */
1580 100, /* 11010 11110 */
1581 101, /* 11010 11111 */
1582 /* line 9, PREFLEN=6, RANGELEN=5, VAL=102..133, 110111+(VAL-102) */
1583 102, /* 110111 00000 */
1584 103, /* 110111 00001 */
1585 132, /* 110111 11110 */
1586 133, /* 110111 11111 */
1587 /* line 10, PREFLEN=6, RANGELEN=6, VAL=134..197, 111000+(VAL-134) */
1588 134, /* 111000 000000 */
1589 135, /* 111000 000001 */
1590 196, /* 111000 111110 */
1591 197, /* 111000 111111 */
1592 /* line 11, PREFLEN=6, RANGELEN=7, VAL=198..325, 111001+(VAL-198) */
1593 198, /* 111001 0000000 */
1594 199, /* 111001 0000001 */
1595 324, /* 111001 1111110 */
1596 325, /* 111001 1111111 */
1597 /* line 12, PREFLEN=6, RANGELEN=8, VAL=326..581, 111010+(VAL-326) */
1598 326, /* 111010 00000000 */
1599 327, /* 111010 00000001 */
1600 580, /* 111010 11111110 */
1601 581, /* 111010 11111111 */
1602 /* line 13, PREFLEN=6, RANGELEN=9, VAL=582..1093, 111011+(VAL-582) */
1603 582, /* 111011 00000000 0 */
1604 583, /* 111011 00000000 1 */
1605 1092, /* 111011 11111111 0 */
1606 1093, /* 111011 11111111 1 */
1607 /* line 14, PREFLEN=6, RANGELEN=10, VAL=1094..2117, 111100+(VAL-1094) */
1608 1094, /* 111100 00000000 00 */
1609 1095, /* 111100 00000000 01 */
1610 2116, /* 111100 11111111 10 */
1611 2117, /* 111100 11111111 11 */
1612 /* line 15, PREFLEN=7, RANGELEN=11, VAL=2118..4165, 1111101+(VAL-2118) */
1613 2118, /* 1111101 00000000 000 */
1614 2119, /* 1111101 00000000 001 */
1615 4164, /* 1111101 11111111 110 */
1616 4165, /* 1111101 11111111 111 */
1617 /* line 16, PREFLEN=8, RANGELEN=32, VAL=-INF..-22, 11111110+(-22-VAL) */
1618 -22, /* 11111110 00000000 00000000 00000000 00000000 */
1619 -23, /* 11111110 00000000 00000000 00000000 00000001 */
1620 /* line 17, PREFLEN=8, RANGELEN=32, VAL=4166..INF, 11111111+(VAL-4166) */
1621 4166, /* 11111111 00000000 00000000 00000000 00000000 */
1622 4167, /* 11111111 00000000 00000000 00000000 00000001 */
1623 /* line 8, PREFLEN=2, VAL=OOB, 10 */
1624 /*OOB*/ /* 10 */
1625 };
1626 const byte test_input_J[] = {
1627 /* 1111 0100 0001 1110 1000 0111 1101 0111 */
1628 0xf4, 0x1e, 0x87, 0xd7,
1629 /* 0111 1010 1111 1111 1100 1111 0111 1000 */
1630 0x7a, 0xff, 0xcf, 0x78,
1631 /* 0000 0001 0010 0011 1100 1110 1101 1111 */
1632 0x01, 0x23, 0xce, 0xdf,
1633 /* 0011 1111 0101 0000 0001 0000 0101 1111 */
1634 0x3f, 0x50, 0x10, 0x5f,
1635 /* 1001 1111 1111 0100 0000 1101 0000 0111 */
1636 0x9f, 0xf4, 0x0d, 0x07,
1637 /* 0101 1110 1101 0111 1111 0111 0000 0110 */
1638 0x5e, 0xd7, 0xf7, 0x06,
1639 /* 1110 0001 1101 1111 1101 1011 1111 1111 */
1640 0xe1, 0xdf, 0xdb, 0xff,
1641 /* 1000 0000 0011 1000 0000 0111 1000 1111 */
1642 0x80, 0x38, 0x07, 0x8f,
1643 /* 1011 1000 1111 1111 1001 0000 0001 1100 */
1644 0xb8, 0xff, 0x90, 0x1c,
1645 /* 1000 0001 1110 0111 1111 0111 0011 1111 */
1646 0x81, 0xe7, 0xf7, 0x3f,
1647 /* 1111 1010 0000 0000 1110 1000 0000 0111 */
1648 0xfa, 0x00, 0xe8, 0x07,
1649 /* 1010 1111 1110 1110 1011 1111 1111 1011 */
1650 0xaf, 0xee, 0xbf, 0xfb,
1651 /* 0000 0000 0111 0110 0000 0001 1110 1111 */
1652 0x00, 0x76, 0x01, 0xef,
1653 /* 1111 1101 1101 1111 1111 1111 1100 0000 */
1654 0xfd, 0xdf, 0xff, 0xc0,
1655 /* 0000 0011 1100 0000 0000 0111 1100 1111 */
1656 0x03, 0xc0, 0x07, 0xcf,
1657 /* 1111 1011 1100 1111 1111 1111 1110 1000 */
1658 0xfb, 0xcf, 0xff, 0xe8,
1659 /* 0000 0000 1111 1010 0000 0000 0111 1110 */
1660 0x00, 0xfa, 0x00, 0x7e,
1661 /* 1111 1111 1110 1111 1011 1111 1111 1111 */
1662 0xff, 0xef, 0xbf, 0xff,
1663 /* 1111 1000 0000 0000 0000 0000 0000 0000 */
1664 0xf8, 0x00, 0x00, 0x00,
1665 /* 0000 0011 1111 1000 0000 0000 0000 0000 */
1666 0x03, 0xf8, 0x00, 0x00,
1667 /* 0000 0000 0000 0111 1111 1100 0000 0000 */
1668 0x00, 0x07, 0xfc, 0x00,
1669 /* 0000 0000 0000 0000 0000 0011 1111 1100 */
1670 0x00, 0x00, 0x03, 0xfc,
1671 /* 0000 0000 0000 0000 0000 0000 0000 0110 */
1672 0x00, 0x00, 0x00, 0x06,
1673 };
1674
1675 /* test code for Table B.11 - Standard Huffman table K */
1676 const int32_t test_output_K[] = {
1677 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1678 1, /* 0 */
1679 /* line 1, PREFLEN=2, RANGELEN=1, VAL=2..3, 10+(VAL-2) */
1680 2, /* 10 0 */
1681 3, /* 10 1 */
1682 /* line 2, PREFLEN=4, RANGELEN=0, VAL=4, 1100 */
1683 4, /* 1100 */
1684 /* line 3, PREFLEN=4, RANGELEN=1, VAL=5..6, 1101+(VAL-5) */
1685 5, /* 1101 0 */
1686 6, /* 1101 1 */
1687 /* line 4, PREFLEN=5, RANGELEN=1, VAL=7..8, 11100+(VAL-7) */
1688 7, /* 11100 0 */
1689 8, /* 11100 1 */
1690 /* line 5, PREFLEN=5, RANGELEN=2, VAL=9..12, 11101+(VAL-9) */
1691 9, /* 11101 00 */
1692 10, /* 11101 01 */
1693 11, /* 11101 10 */
1694 12, /* 11101 11 */
1695 /* line 6, PREFLEN=6, RANGELEN=2, VAL=13..16, 111100+(VAL-13) */
1696 13, /* 111100 00 */
1697 14, /* 111100 01 */
1698 15, /* 111100 10 */
1699 16, /* 111100 11 */
1700 /* line 7, PREFLEN=7, RANGELEN=2, VAL=17..20, 1111010+(VAL-17) */
1701 17, /* 1111010 00 */
1702 18, /* 1111010 01 */
1703 19, /* 1111010 10 */
1704 20, /* 1111010 11 */
1705 /* line 8, PREFLEN=7, RANGELEN=3, VAL=21..28, 1111011+(VAL-21) */
1706 21, /* 1111011 000 */
1707 22, /* 1111011 001 */
1708 27, /* 1111011 110 */
1709 28, /* 1111011 111 */
1710 /* line 9, PREFLEN=7, RANGELEN=4, VAL=29..44, 1111100+(VAL-29) */
1711 29, /* 1111100 0000 */
1712 30, /* 1111100 0001 */
1713 43, /* 1111100 1110 */
1714 44, /* 1111100 1111 */
1715 /* line 10, PREFLEN=7, RANGELEN=5, VAL=45..76, 1111101+(VAL-45) */
1716 45, /* 1111101 00000 */
1717 46, /* 1111101 00001 */
1718 75, /* 1111101 11110 */
1719 76, /* 1111101 11111 */
1720 /* line 11, PREFLEN=7, RANGELEN=6, VAL=77..140, 1111110+(VAL-77) */
1721 77, /* 1111110 000000 */
1722 78, /* 1111110 000001 */
1723 139, /* 1111110 111110 */
1724 140, /* 1111110 111111 */
1725 /* line 12, PREFLEN=7, RANGELEN=32, VAL=141..INF, 1111111+(VAL-141) */
1726 141, /* 1111111 00000000 00000000 00000000 00000000 */
1727 142, /* 1111111 00000000 00000000 00000000 00000001 */
1728 };
1729 const byte test_input_K[] = {
1730 /* 0100 1011 1001 1010 1101 1111 0001 1100 */
1731 0x4b, 0x9a, 0xdf, 0x1c,
1732 /* 1111 0100 1110 1011 1101 1011 1011 1111 */
1733 0xf4, 0xeb, 0xdb, 0xbf,
1734 /* 1000 0111 1000 1111 1001 0111 1001 1111 */
1735 0x87, 0x8f, 0x97, 0x9f,
1736 /* 1010 0011 1101 0011 1110 1010 1111 0101 */
1737 0xa3, 0xd3, 0xea, 0xf5,
1738 /* 1111 1011 0001 1110 1100 1111 1011 1101 */
1739 0xfb, 0x1e, 0xcf, 0xbd,
1740 /* 1110 1111 1111 1100 0000 1111 1000 0011 */
1741 0xef, 0xfc, 0x0f, 0x83,
1742 /* 1111 0011 1011 1110 0111 1111 1101 0000 */
1743 0xf3, 0xbe, 0x7f, 0xd0,
1744 /* 0111 1101 0000 1111 1101 1111 0111 1101 */
1745 0x7d, 0x0f, 0xdf, 0x7d,
1746 /* 1111 1111 1110 0000 0011 1111 0000 0011 */
1747 0xff, 0xe0, 0x3f, 0x03,
1748 /* 1111 1011 1110 1111 1101 1111 1111 1111 */
1749 0xfb, 0xef, 0xdf, 0xff,
1750 /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1751 0x00, 0x00, 0x00, 0x00,
1752 /* 1111 1110 0000 0000 0000 0000 0000 0000 */
1753 0xfe, 0x00, 0x00, 0x00,
1754 /* 0000 001 */
1755 0x02,
1756 };
1757
1758 /* test code for Table B.12 - Standard Huffman table L */
1759 const int32_t test_output_L[] = {
1760 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1761 1, /* 0 */
1762 /* line 1, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
1763 2, /* 10 */
1764 /* line 2, PREFLEN=3, RANGELEN=1, VAL=3..4, 110+(VAL-3) */
1765 3, /* 110 0 */
1766 4, /* 110 1 */
1767 /* line 3, PREFLEN=5, RANGELEN=0, VAL=5, 11100 */
1768 5, /* 11100 */
1769 /* line 4, PREFLEN=5, RANGELEN=1, VAL=6..7, 11101+(VAL-7) */
1770 6, /* 11101 0 */
1771 7, /* 11101 1 */
1772 /* line 5, PREFLEN=6, RANGELEN=1, VAL=8..9, 111100+(VAL-8) */
1773 8, /* 111100 0 */
1774 9, /* 111100 1 */
1775 /* line 6, PREFLEN=7, RANGELEN=0, VAL=10, 1111010 */
1776 10, /* 1111010 */
1777 /* line 7, PREFLEN=7, RANGELEN=1, VAL=11..12, 1111011+(VAL-11) */
1778 11, /* 1111011 0 */
1779 12, /* 1111011 1 */
1780 /* line 8, PREFLEN=7, RANGELEN=2, VAL=13..16, 1111100+(VAL-13) */
1781 13, /* 1111100 00 */
1782 14, /* 1111100 01 */
1783 15, /* 1111100 10 */
1784 16, /* 1111100 11 */
1785 /* line 9, PREFLEN=7, RANGELEN=3, VAL=17..24, 1111101+(VAL-17) */
1786 17, /* 1111101 000 */
1787 18, /* 1111101 001 */
1788 23, /* 1111101 110 */
1789 24, /* 1111101 111 */
1790 /* line 10, PREFLEN=7, RANGELEN=4, VAL=25..40, 1111110+(VAL-25) */
1791 25, /* 1111110 0000 */
1792 26, /* 1111110 0001 */
1793 39, /* 1111110 1110 */
1794 40, /* 1111110 1111 */
1795 /* line 11, PREFLEN=8, RANGELEN=5, VAL=41..72, 11111110+(VAL-41) */
1796 41, /* 11111110 00000 */
1797 42, /* 11111110 00001 */
1798 71, /* 11111110 11110 */
1799 72, /* 11111110 11111 */
1800 /* line 12, PREFLEN=8, RANGELEN=32, VAL=73..INF, 11111111+(VAL-73) */
1801 73, /* 11111111 00000000 00000000 00000000 00000000 */
1802 74, /* 11111111 00000000 00000000 00000000 00000001 */
1803 };
1804 const byte test_input_L[] = {
1805 /* 0101 1001 1011 1100 1110 1011 1011 1111 */
1806 0x59, 0xbc, 0xeb, 0xbf,
1807 /* 0001 1110 0111 1101 0111 1011 0111 1011 */
1808 0x1e, 0x7d, 0x7b, 0x7b,
1809 /* 1111 1100 0011 1110 0011 1111 0010 1111 */
1810 0xfc, 0x3e, 0x3f, 0x2f,
1811 /* 1001 1111 1101 0001 1111 0100 1111 1101 */
1812 0x9f, 0xd1, 0xf4, 0xfd,
1813 /* 1101 1111 0111 1111 1110 0000 1111 1100 */
1814 0xdf, 0x7f, 0xe0, 0xfc,
1815 /* 0011 1111 1011 1011 1111 0111 1111 1111 */
1816 0x3f, 0xbb, 0xf7, 0xff,
1817 /* 0000 0011 1111 1000 0011 1111 1101 1110 */
1818 0x03, 0xf8, 0x3f, 0xde,
1819 /* 1111 1110 1111 1111 1111 1000 0000 0000 */
1820 0xfe, 0xff, 0xf8, 0x00,
1821 /* 0000 0000 0000 0000 0000 0111 1111 1000 */
1822 0x00, 0x00, 0x07, 0xf8,
1823 /* 0000 0000 0000 0000 0000 0000 0000 1 */
1824 0x00, 0x00, 0x00, 0x08,
1825 };
1826
1827 /* test code for Table B.13 - Standard Huffman table M */
1828 const int32_t test_output_M[] = {
1829 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1830 1, /* 0 */
1831 /* line 1, PREFLEN=3, RANGELEN=0, VAL=2, 100 */
1832 2, /* 100 */
1833 /* line 2, PREFLEN=3, RANGELEN=0, VAL=3, 1100 */
1834 3, /* 1100 */
1835 /* line 3, PREFLEN=5, RANGELEN=0, VAL=4, 11100 */
1836 4, /* 11100 */
1837 /* line 4, PREFLEN=4, RANGELEN=1, VAL=5..6, 1101+(VAL-5) */
1838 5, /* 1101 0 */
1839 6, /* 1101 1 */
1840 /* line 5, PREFLEN=3, RANGELEN=3, VAL=7..14, 101+(VAL-7) */
1841 7, /* 101 000 */
1842 8, /* 101 001 */
1843 13, /* 101 110 */
1844 14, /* 101 111 */
1845 /* line 6, PREFLEN=6, RANGELEN=1, VAL=15..16, 111010+(VAL-15) */
1846 15, /* 111010 0 */
1847 16, /* 111010 1 */
1848 /* line 7, PREFLEN=6, RANGELEN=2, VAL=17..20, 111011+(VAL-17) */
1849 17, /* 111011 00 */
1850 18, /* 111011 01 */
1851 19, /* 111011 10 */
1852 20, /* 111011 11 */
1853 /* line 8, PREFLEN=6, RANGELEN=3, VAL=21..28, 111100+(VAL-21) */
1854 21, /* 111100 000 */
1855 22, /* 111100 001 */
1856 27, /* 111100 110 */
1857 28, /* 111100 111 */
1858 /* line 9, PREFLEN=6, RANGELEN=4, VAL=29..44, 111101+(VAL-29) */
1859 29, /* 111101 0000 */
1860 30, /* 111101 0001 */
1861 43, /* 111101 1110 */
1862 44, /* 111101 1111 */
1863 /* line 10, PREFLEN=6, RANGELEN=5, VAL=45..76, 111110+(VAL-45) */
1864 45, /* 111110 00000 */
1865 46, /* 111110 00001 */
1866 75, /* 111110 11110 */
1867 76, /* 111110 11111 */
1868 /* line 11, PREFLEN=7, RANGELEN=6, VAL=77..140, 1111110+(VAL-77) */
1869 77, /* 1111110 000000 */
1870 78, /* 1111110 000001 */
1871 139, /* 1111110 111110 */
1872 140, /* 1111110 111111 */
1873 /* line 12, PREFLEN=7, RANGELEN=32, VAL=141..INF, 1111111+(VAL-141) */
1874 141, /* 1111111 00000000 00000000 00000000 00000000 */
1875 142, /* 1111111 00000000 00000000 00000000 00000001 */
1876 };
1877 const byte test_input_M[] = {
1878 /* 0100 1100 1110 0110 1011 0111 0100 0101 */
1879 0x4c, 0xe6, 0xb7, 0x45,
1880 /* 0011 0111 0101 1111 1101 0011 1010 1111 */
1881 0x37, 0x5f, 0xd3, 0xaf,
1882 /* 0110 0111 0110 1111 0111 0111 0111 1111 */
1883 0x67, 0x6f, 0x77, 0x7f,
1884 /* 1000 0011 1100 0011 1110 0110 1111 0011 */
1885 0x83, 0xc3, 0xe6, 0xf3,
1886 /* 1111 1010 0001 1110 1000 1111 1011 1101 */
1887 0xfa, 0x1e, 0x8f, 0xbd,
1888 /* 1110 1111 1111 1100 0000 1111 1000 0011 */
1889 0xef, 0xfc, 0x0f, 0x83,
1890 /* 1111 0111 1011 1110 1111 1111 1110 0000 */
1891 0xf7, 0xbe, 0xff, 0xe0,
1892 /* 0011 1111 0000 0011 1111 1011 1110 1111 */
1893 0x3f, 0x03, 0xfb, 0xef,
1894 /* 1101 1111 1111 1111 0000 0000 0000 0000 */
1895 0xdf, 0xff, 0x00, 0x00,
1896 /* 0000 0000 0000 0000 1111 1110 0000 0000 */
1897 0x00, 0x00, 0xfe, 0x00,
1898 /* 0000 0000 0000 0000 0000 001 */
1899 0x00, 0x00, 0x02,
1900 };
1901
1902 /* test code for Table B.14 - Standard Huffman table N */
1903 const int32_t test_output_N[] = {
1904 /* line 0, PREFLEN=3, RANGELEN=0, VAL=-2, 100 */
1905 -2, /* 100 */
1906 /* line 1, PREFLEN=3, RANGELEN=0, VAL=-1, 101 */
1907 -1, /* 101 */
1908 /* line 2, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1909 0, /* 0 */
1910 /* line 3, PREFLEN=3, RANGELEN=0, VAL=1, 110 */
1911 1, /* 110 */
1912 /* line 4, PREFLEN=3, RANGELEN=0, VAL=2, 111 */
1913 2, /* 111 */
1914 };
1915 const byte test_input_N[] = {
1916 /* 1001 0101 1011 1 */
1917 0x95, 0xb8,
1918 };
1919
1920 /* test code for Table B.15 - Standard Huffman table O */
1921 const int32_t test_output_O[] = {
1922 /* line 0, PREFLEN=7, RANGELEN=4, VAL=-24..-9, 1111100+(VAL+24) */
1923 -24, /* 1111100 0000 */
1924 -23, /* 1111100 0001 */
1925 -10, /* 1111100 1110 */
1926 -9, /* 1111100 1111 */
1927 /* line 1, PREFLEN=6, RANGELEN=2, VAL=-8..-5, 111100+(VAL+8) */
1928 -8, /* 111100 00 */
1929 -7, /* 111100 01 */
1930 -6, /* 111100 10 */
1931 -5, /* 111100 11 */
1932 /* line 2, PREFLEN=5, RANGELEN=1, VAL=-4..-3, 11100+(VAL+4) */
1933 -4, /* 11100 0 */
1934 -3, /* 11100 1 */
1935 /* line 3, PREFLEN=4, RANGELEN=0, VAL=-2, 1100 */
1936 -2, /* 1100 */
1937 /* line 4, PREFLEN=3, RANGELEN=0, VAL=-1, 100 */
1938 -1, /* 100 */
1939 /* line 5, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1940 0, /* 0 */
1941 /* line 6, PREFLEN=3, RANGELEN=0, VAL=1, 101 */
1942 1, /* 101 */
1943 /* line 7, PREFLEN=4, RANGELEN=0, VAL=2, 1101 */
1944 2, /* 1101 */
1945 /* line 8, PREFLEN=5, RANGELEN=1, VAL=3..4, 11101+(VAL-3) */
1946 3, /* 11101 0 */
1947 4, /* 11101 1 */
1948 /* line 9, PREFLEN=6, RANGELEN=2, VAL=5..8, 111101+(VAL-5) */
1949 5, /* 111101 00 */
1950 6, /* 111101 01 */
1951 7, /* 111101 10 */
1952 8, /* 111101 11 */
1953 /* line 10, PREFLEN=7, RANGELEN=4, VAL=9..24, 1111101+(VAL-9) */
1954 9, /* 1111101 0000 */
1955 10, /* 1111101 0001 */
1956 23, /* 1111101 1110 */
1957 24, /* 1111101 1111 */
1958 /* line 11, PREFLEN=7, RANGELEN=32, VAL=-INF..-25, 1111110+(-25-VAL) */
1959 -25, /* 1111110 00000000 00000000 00000000 00000000 */
1960 -26, /* 1111110 00000000 00000000 00000000 00000001 */
1961 /* line 12, PREFLEN=7, RANGELEN=32, VAL=25..INF, 1111111+(VAL-25) */
1962 25, /* 1111111 00000000 00000000 00000000 00000000 */
1963 26, /* 1111111 00000000 00000000 00000000 00000001 */
1964 };
1965 const byte test_input_O[] = {
1966 /* 1111 1000 0001 1111 0000 0111 1110 0111 */
1967 0xf8, 0x1f, 0x07, 0xe7,
1968 /* 0111 1100 1111 1111 0000 1111 0001 1111 */
1969 0x7c, 0xff, 0x0f, 0x1f,
1970 /* 0010 1111 0011 1110 0011 1001 1100 1000 */
1971 0x2f, 0x3e, 0x39, 0xc8,
1972 /* 1011 1011 1101 0111 0111 1110 1001 1110 */
1973 0xbb, 0xd7, 0x7e, 0x9e,
1974 /* 1011 1110 1101 1110 1111 1111 0100 0011 */
1975 0xbe, 0xde, 0xff, 0x43,
1976 /* 1110 1000 1111 1101 1110 1111 1011 1111 */
1977 0xe8, 0xfd, 0xef, 0xbf,
1978 /* 1111 1000 0000 0000 0000 0000 0000 0000 */
1979 0xf8, 0x00, 0x00, 0x00,
1980 /* 0000 0011 1111 0000 0000 0000 0000 0000 */
1981 0x03, 0xf0, 0x00, 0x00,
1982 /* 0000 0000 0000 1111 1111 0000 0000 0000 */
1983 0x00, 0x0f, 0xf0, 0x00,
1984 /* 0000 0000 0000 0000 0000 1111 1110 0000 */
1985 0x00, 0x00, 0x0f, 0xe0,
1986 /* 0000 0000 0000 0000 0000 0000 001 */
1987 0x00, 0x00, 0x00, 0x20,
1988 };
1989
1990 typedef struct test_huffmancodes {
1991 const char *name;
1992 const Jbig2HuffmanParams *params;
1993 const byte *input;
1994 const size_t input_len;
1995 const int32_t *output;
1996 const size_t output_len;
1997 } test_huffmancodes_t;
1998
1999 #define countof(x) (sizeof((x)) / sizeof((x)[0]))
2000
2001 #define DEF_TEST_HUFFMANCODES(x) { \
2002 #x, \
2003 &jbig2_huffman_params_##x, \
2004 test_input_##x, countof(test_input_##x), \
2005 test_output_##x, countof(test_output_##x), \
2006 }
2007
2008 test_huffmancodes_t tests[] = {
2009 DEF_TEST_HUFFMANCODES(A),
2010 DEF_TEST_HUFFMANCODES(B),
2011 DEF_TEST_HUFFMANCODES(C),
2012 DEF_TEST_HUFFMANCODES(D),
2013 DEF_TEST_HUFFMANCODES(E),
2014 DEF_TEST_HUFFMANCODES(F),
2015 DEF_TEST_HUFFMANCODES(G),
2016 DEF_TEST_HUFFMANCODES(H),
2017 DEF_TEST_HUFFMANCODES(I),
2018 DEF_TEST_HUFFMANCODES(J),
2019 DEF_TEST_HUFFMANCODES(K),
2020 DEF_TEST_HUFFMANCODES(L),
2021 DEF_TEST_HUFFMANCODES(M),
2022 DEF_TEST_HUFFMANCODES(N),
2023 DEF_TEST_HUFFMANCODES(O),
2024 };
2025
2026 typedef struct test_stream {
2027 Jbig2WordStream ws;
2028 test_huffmancodes_t *h;
2029 } test_stream_t;
2030
2031 static int
2032 test_get_word2(Jbig2Ctx *ctx, Jbig2WordStream *self, size_t offset, uint32_t *word)
2033 {
2034 test_stream_t *st = (test_stream_t *) self;
2035 uint32_t val = 0;
2036 int ret = 0;
2037
2038 if (st == NULL || st->h == NULL || word == NULL)
2039 return -1;
2040 if (offset >= st->h->input_len)
2041 return 0;
2042
2043 if (offset < st->h->input_len) {
2044 val |= (st->h->input[offset] << 24);
2045 ret++;
2046 }
2047 if (offset + 1 < st->h->input_len) {
2048 val |= (st->h->input[offset + 1] << 16);
2049 ret++;
2050 }
2051 if (offset + 2 < st->h->input_len) {
2052 val |= (st->h->input[offset + 2] << 8);
2053 ret++;
2054 }
2055 if (offset + 3 < st->h->input_len) {
2056 val |= st->h->input[offset + 3];
2057 ret++;
2058 }
2059 *word = val;
2060 return ret;
2061 }
2062
2063 static int test2()
2064 {
2065 Jbig2Ctx *ctx;
2066 int success = 0;
2067 int i;
2068
2069 ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
2070 if (ctx == NULL) {
2071 fprintf(stderr, "Failed to allocate jbig2 context\n");
2072 return 0;
2073 }
2074
2075 for (i = 0; i < (int) countof(tests); i++) {
2076 Jbig2HuffmanTable *table;
2077 Jbig2HuffmanState *hs;
2078 test_stream_t st;
2079 int32_t code;
2080 bool oob;
2081 size_t j;
2082
2083 st.ws.get_next_word = test_get_word2;
2084 st.h = &tests[i];
2085 printf("testing Standard Huffman table %s: ", st.h->name);
2086 table = jbig2_build_huffman_table(ctx, st.h->params);
2087 if (table == NULL) {
2088 fprintf(stderr, "jbig2_build_huffman_table() returned NULL!\n");
2089 jbig2_ctx_free(ctx);
2090 return 0;
2091 }
2092 /* jbig2_dump_huffman_table(table); */
2093 hs = jbig2_huffman_new(ctx, &st.ws);
2094 if (hs == NULL) {
2095 fprintf(stderr, "jbig2_huffman_new() returned NULL!\n");
2096 jbig2_release_huffman_table(ctx, table);
2097 jbig2_ctx_free(ctx);
2098 return 0;
2099 }
2100 for (j = 0; j < st.h->output_len; j++) {
2101 printf("%d...", st.h->output[j]);
2102 code = jbig2_huffman_get(hs, table, &oob);
2103 if (code == st.h->output[j] && !oob) {
2104 printf("ok, ");
2105 } else {
2106 int need_comma = 0;
2107
2108 printf("NG(");
2109 if (code != st.h->output[j]) {
2110 printf("%d", code);
2111 need_comma = 1;
2112 }
2113 if (oob) {
2114 if (need_comma)
2115 printf(",");
2116 printf("OOB");
2117 }
2118 printf("), ");
2119 }
2120 }
2121 if (st.h->params->HTOOB) {
2122 printf("OOB...");
2123 code = jbig2_huffman_get(hs, table, &oob);
2124 if (oob) {
2125 printf("ok");
2126 } else {
2127 printf("NG(%d)", code);
2128 }
2129 }
2130 printf("\n");
2131 jbig2_huffman_free(ctx, hs);
2132 jbig2_release_huffman_table(ctx, table);
2133 }
2134
2135 jbig2_ctx_free(ctx);
2136
2137 if (i == countof(tests))
2138 success = 1;
2139
2140 return success;
2141 }
2142
2143 int
2144 main(int argc, char **argv)
2145 {
2146 return test1() && test2() ? 0 : 1;
2147 }
2148 #endif