1/* Copyright (C) 2001-2019 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., 1305 Grant Avenue - Suite 200, Novato,
13 CA 94945, U.S.A., +1(415)492-9861, 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
46struct _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)->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 */
67Jbig2HuffmanState *
68jbig2_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_FATAL, -1, "failed 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_FATAL, -1, "failed read second huffman word");
90 jbig2_huffman_free(ctx, result);
91 return NULL;
92 }
93 } else {
94 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1, "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 */
104void
105jbig2_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 */
114void
115jbig2_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 */
121void
122jbig2_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 */
134void
135jbig2_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 */
178int
179jbig2_huffman_skip(Jbig2HuffmanState *hs)
180{
181 int 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, -1, "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 */
207int
208jbig2_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, -1, "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, -1, "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 */
233uint32_t
234jbig2_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 */
242int32_t
243jbig2_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, -1, "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, -1, "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
276int32_t
277jbig2_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, -1, "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 && entry->u.RANGELOW == -1) {
303 if (oob)
304 *oob = -1;
305 return jbig2_error(hs->ctx, JBIG2_SEVERITY_FATAL, -1, "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, -1, "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, -1, "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 */
373Jbig2HuffmanTable *
374jbig2_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, -1, "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, -1, "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, -1, "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, -1, "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, -1, "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 */
500void
501jbig2_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' */
512static uint32_t
513jbig2_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 */
538int
539jbig2_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 /* allocate HuffmanParams & HuffmanLine */
587 params = jbig2_new(ctx, Jbig2HuffmanParams, 1);
588 if (params == NULL) {
589 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate Huffman Table Parameter");
590 goto error_exit;
591 }
592 line = jbig2_new(ctx, Jbig2HuffmanLine, lines_max);
593 if (line == NULL) {
594 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to allocate huffman table lines");
595 goto error_exit;
596 }
597 /* B.2 5) */
598 while (CURRANGELOW < HTHIGH) {
599 /* B.2 5) a) */
600 if (boffset + HTPS >= lines_data_bitlen)
601 goto too_short;
602 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
603 /* B.2 5) b) */
604 if (boffset + HTRS >= lines_data_bitlen)
605 goto too_short;
606 line[NTEMP].RANGELEN = jbig2_table_read_bits(lines_data, &boffset, HTRS);
607 /* B.2 5) c) */
608 line[NTEMP].RANGELOW = CURRANGELOW;
609 CURRANGELOW += (1 << line[NTEMP].RANGELEN);
610 NTEMP++;
611 }
612 /* B.2 6), B.2 7) lower range table line */
613 if (boffset + HTPS >= lines_data_bitlen)
614 goto too_short;
615 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
616 line[NTEMP].RANGELEN = 32;
617 line[NTEMP].RANGELOW = HTLOW - 1;
618 NTEMP++;
619 /* B.2 8), B.2 9) upper range table line */
620 if (boffset + HTPS >= lines_data_bitlen)
621 goto too_short;
622 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
623 line[NTEMP].RANGELEN = 32;
624 line[NTEMP].RANGELOW = HTHIGH;
625 NTEMP++;
626 /* B.2 10) */
627 if (HTOOB) {
628 /* B.2 10) a), B.2 10) b) out-of-bound table line */
629 if (boffset + HTPS >= lines_data_bitlen)
630 goto too_short;
631 line[NTEMP].PREFLEN = jbig2_table_read_bits(lines_data, &boffset, HTPS);
632 line[NTEMP].RANGELEN = 0;
633 line[NTEMP].RANGELOW = 0;
634 NTEMP++;
635 }
636 if (NTEMP != lines_max) {
637 Jbig2HuffmanLine *new_line = jbig2_renew(ctx, line,
638 Jbig2HuffmanLine, NTEMP);
639
640 if (new_line == NULL) {
641 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "failed to reallocate huffman table lines");
642 goto error_exit;
643 }
644 line = new_line;
645 }
646 params->HTOOB = HTOOB;
647 params->n_lines = NTEMP;
648 params->lines = line;
649 segment->result = params;
650
651#ifdef JBIG2_DEBUG
652 {
653 int i;
654
655 for (i = 0; i < NTEMP; i++) {
656 jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, segment->number,
657 "Line: %d, PREFLEN: %d, RANGELEN: %d, RANGELOW: %d",
658 i, params->lines[i].PREFLEN, params->lines[i].RANGELEN, params->lines[i].RANGELOW);
659 }
660 }
661#endif
662 }
663 return 0;
664
665too_short:
666 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "segment too short");
667error_exit:
668 jbig2_free(ctx->allocator, line);
669 jbig2_free(ctx->allocator, params);
670 return -1;
671}
672
673/* free Jbig2HuffmanParams allocated by jbig2_huffman_table() */
674void
675jbig2_table_free(Jbig2Ctx *ctx, Jbig2HuffmanParams *params)
676{
677 if (params != NULL) {
678 jbig2_free(ctx->allocator, (void *)params->lines);
679 jbig2_free(ctx->allocator, params);
680 }
681}
682
683/* find a user supplied table used by 'segment' and by 'index' */
684const Jbig2HuffmanParams *
685jbig2_find_table(Jbig2Ctx *ctx, Jbig2Segment *segment, int index)
686{
687 int i, table_index = 0;
688
689 for (i = 0; i < segment->referred_to_segment_count; i++) {
690 const Jbig2Segment *const rsegment = jbig2_find_segment(ctx, segment->referred_to_segments[i]);
691
692 if (rsegment && (rsegment->flags & 63) == 53) {
693 if (table_index == index)
694 return (const Jbig2HuffmanParams *)rsegment->result;
695 ++table_index;
696 }
697 }
698
699 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, segment->number, "huffman table not found (%d)", index);
700 return NULL;
701}
702
703#ifdef TEST
704#include <stdio.h>
705
706/* cc -g -o jbig2_huffman.test1 -DTEST jbig2_huffman.c .libs/libjbig2dec.a */
707
708/* a test bitstream, and a list of the table indices
709 to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */
710/* this test stream should decode to { 8, 5, oob, 8 } */
711
712static const byte test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 };
713static const byte test_tabindex[] = { 4, 2, 2, 1 };
714
715static int
716test_get_word1(Jbig2WordStream *self, size_t offset, uint32_t *word)
717{
718 uint32_t val = 0;
719 int ret = 0;
720
721 if (self == NULL || word == NULL)
722 return -1;
723 if (offset >= sizeof (test_stream))
724 return 0;
725
726 if (offset < sizeof(test_stream)) {
727 val |= test_stream[offset] << 24;
728 ret++;
729 }
730 if (offset + 1 < sizeof(test_stream)) {
731 val |= test_stream[offset + 1] << 16;
732 ret++;
733 }
734 if (offset + 2 < sizeof(test_stream)) {
735 val |= test_stream[offset + 2] << 8;
736 ret++;
737 }
738 if (offset + 3 < sizeof(test_stream)) {
739 val |= test_stream[offset + 3];
740 ret++;
741 }
742 *word = val;
743 return ret;
744}
745
746static int test1()
747{
748 Jbig2Ctx *ctx;
749 Jbig2HuffmanTable *tables[5];
750 Jbig2HuffmanState *hs;
751 Jbig2WordStream ws;
752 bool oob;
753 int32_t code;
754 int i;
755 int success = 0;
756
757 ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
758 if (ctx == NULL) {
759 fprintf(stderr, "Failed to allocate jbig2 context\n");
760 goto cleanup;
761 }
762
763 tables[0] = NULL;
764 tables[1] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_A);
765 tables[2] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_B);
766 tables[3] = NULL;
767 tables[4] = jbig2_build_huffman_table(ctx, &jbig2_huffman_params_D);
768 if (tables[1] == NULL || tables[2] == NULL || tables[4] == NULL)
769 {
770 fprintf(stderr, "Failed to build huffman tables");
771 goto cleanup;
772 }
773
774 ws.get_next_word = test_get_word1;
775 hs = jbig2_huffman_new(ctx, &ws);
776 if (hs == NULL) {
777 fprintf(stderr, "Failed to allocate huffman state");
778 goto cleanup;
779 }
780
781 printf("testing jbig2 huffman decoding...");
782 printf("\t(should be 8 5 (oob) 8)\n");
783
784 {
785 int i;
786 int sequence_length = sizeof(test_tabindex);
787
788 for (i = 0; i < sequence_length; i++) {
789 code = jbig2_huffman_get(hs, tables[test_tabindex[i]], &oob);
790 if (oob)
791 printf("(oob) ");
792 else
793 printf("%d ", code);
794 }
795 }
796
797 printf("\n");
798
799 success = 1;
800
801cleanup:
802 for (i = 0; i < 5; i++)
803 jbig2_release_huffman_table(ctx, tables[i]);
804 jbig2_ctx_free(ctx);
805
806 return success;
807}
808
809#include <stdio.h>
810
811/* a decoding test of each line from each standard table */
812
813/* test code for Table B.1 - Standard Huffman table A */
814const int32_t test_output_A[] = {
815 /* line 0, PREFLEN=1, RANGELEN=4, VAL=0..15, 0+VAL */
816 0, /* 0 0000 */
817 1, /* 0 0001 */
818 14, /* 0 1110 */
819 15, /* 0 1111 */
820 /* line 1, PREFLEN=2, RANGELEN=8, VAL=16..271, 10+(VAL-16) */
821 16, /* 10 00000000 */
822 17, /* 10 00000001 */
823 270, /* 10 11111110 */
824 271, /* 10 11111111 */
825 /* line 2, PREFLEN=3, RANGELEN=16, VAL=272..65807, 110+(VAL-272) */
826 272, /* 110 00000000 00000000 */
827 273, /* 110 00000000 00000001 */
828 65806, /* 110 11111111 11111110 */
829 65807, /* 110 11111111 11111111 */
830 /* line 3, PREFLEN=3, RANGELEN=32, VAL=65808..INF, 111+(VAL-65808) */
831 65808, /* 111 00000000 00000000 00000000 00000000 */
832 65809, /* 111 00000000 00000000 00000000 00000001 */
833};
834const byte test_input_A[] = {
835 /* 0000 0000 0101 1100 1111 1000 0000 0010 */
836 0x00, 0x5c, 0xf8, 0x02,
837 /* 0000 0001 1011 1111 1010 1111 1111 1100 */
838 0x01, 0xbf, 0xaf, 0xfc,
839 /* 0000 0000 0000 0001 1000 0000 0000 0000 */
840 0x00, 0x01, 0x80, 0x00,
841 /* 0111 0111 1111 1111 1111 0110 1111 1111 */
842 0x77, 0xff, 0xf6, 0xff,
843 /* 1111 1111 1110 0000 0000 0000 0000 0000 */
844 0xff, 0xe0, 0x00, 0x00,
845 /* 0000 0000 0001 1100 0000 0000 0000 0000 */
846 0x00, 0x1c, 0x00, 0x00,
847 /* 0000 0000 0000 01 */
848 0x00, 0x04,
849};
850
851/* test code for Table B.2 - Standard Huffman table B */
852const int32_t test_output_B[] = {
853 /* line 0, PREFLEN=1, RANGELEN=0, VAL=0, 0 */
854 0, /* 0 */
855 /* line 1, PREFLEN=2, RANGELEN=0, VAL=1, 10 */
856 1, /* 10 */
857 /* line 2, PREFLEN=3, RANGELEN=0, VAL=2, 110 */
858 2, /* 110 */
859 /* line 3, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */
860 3, /* 1110 000 */
861 4, /* 1110 001 */
862 9, /* 1110 110 */
863 10, /* 1110 111 */
864 /* line 4, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */
865 11, /* 11110 000000 */
866 12, /* 11110 000001 */
867 73, /* 11110 111110 */
868 74, /* 11110 111111 */
869 /* line 5, PREFLEN=6, RANGELEN=32, VAL=75..INF, 111110+(VAL-75) */
870 75, /* 111110 00000000 00000000 00000000 00000000 */
871 76, /* 111110 00000000 00000000 00000000 00000001 */
872 /* line 6, PREFLEN=6, VAL=OOB, 111111 */
873 /*OOB*/ /* 111111 */
874};
875const byte test_input_B[] = {
876 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
877 0x5b, 0x87, 0x1e, 0xdd,
878 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
879 0xfc, 0x07, 0x81, 0xf7,
880 /* 1101 1110 1111 1111 1110 0000 0000 0000 */
881 0xde, 0xff, 0xe0, 0x00,
882 /* 0000 0000 0000 0000 0000 1111 1000 0000 */
883 0x00, 0x00, 0x0f, 0x80,
884 /* 0000 0000 0000 0000 0000 0000 0111 1111 */
885 0x00, 0x00, 0x00, 0x7f,
886};
887
888/* test code for Table B.3 - Standard Huffman table C */
889const int32_t test_output_C[] = {
890 /* line 0, PREFLEN=8, RANGELEN=8, VAL=-256..-1, 11111110+(VAL+256) */
891 -256, /* 11111110 00000000 */
892 -255, /* 11111110 00000001 */
893 -2, /* 11111110 11111110 */
894 -1, /* 11111110 11111111 */
895 /* line 1, PREFLEN=1, RANGELEN=0, VAL=0, 0 */
896 0, /* 0 */
897 /* line 2, PREFLEN=2, RANGELEN=0, VAL=1, 10 */
898 1, /* 10 */
899 /* line 3, PREFLEN=3, RANGELEN=0, VAL=2, 110 */
900 2, /* 110 */
901 /* line 4, PREFLEN=4, RANGELEN=3, VAL=3..10, 1110+(VAL-3) */
902 3, /* 1110 000 */
903 4, /* 1110 001 */
904 9, /* 1110 110 */
905 10, /* 1110 111 */
906 /* line 5, PREFLEN=5, RANGELEN=6, VAL=11..74, 11110+(VAL-11) */
907 11, /* 11110 000000 */
908 12, /* 11110 000001 */
909 73, /* 11110 111110 */
910 74, /* 11110 111111 */
911 /* line 6, PREFLEN=8, RANGELEN=32, VAL=-INF..-257, 11111111+(-257-VAL) */
912 -257, /* 11111111 00000000 00000000 00000000 00000000 */
913 -258, /* 11111111 00000000 00000000 00000000 00000001 */
914 /* line 7, PREFLEN=7, RANGELEN=32, VAL=75..INF, 1111110+(VAL-75) */
915 75, /* 1111110 00000000 00000000 00000000 00000000 */
916 76, /* 1111110 00000000 00000000 00000000 00000001 */
917 /* line 8, PREFLEN=6, VAL=OOB, 111110 */
918 /*OOB*/ /* 111110 */
919};
920const byte test_input_C[] = {
921 /* 1111 1110 0000 0000 1111 1110 0000 0001 */
922 0xfe, 0x00, 0xfe, 0x01,
923 /* 1111 1110 1111 1110 1111 1110 1111 1111 */
924 0xfe, 0xfe, 0xfe, 0xff,
925 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
926 0x5b, 0x87, 0x1e, 0xdd,
927 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
928 0xfc, 0x07, 0x81, 0xf7,
929 /* 1101 1110 1111 1111 1111 1100 0000 0000 */
930 0xde, 0xff, 0xfc, 0x00,
931 /* 0000 0000 0000 0000 0000 0011 1111 1100 */
932 0x00, 0x00, 0x03, 0xfc,
933 /* 0000 0000 0000 0000 0000 0000 0000 0111 */
934 0x00, 0x00, 0x00, 0x07,
935 /* 1111 0000 0000 0000 0000 0000 0000 0000 */
936 0xf0, 0x00, 0x00, 0x00,
937 /* 0000 0111 1110 0000 0000 0000 0000 0000 */
938 0x07, 0xe0, 0x00, 0x00,
939 /* 0000 0000 0001 1111 10 */
940 0x00, 0x1f, 0x80,
941};
942
943/* test code for Table B.4 - Standard Huffman table D */
944const int32_t test_output_D[] = {
945 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
946 1, /* 0 */
947 /* line 1, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
948 2, /* 10 */
949 /* line 2, PREFLEN=3, RANGELEN=0, VAL=3, 110 */
950 3, /* 110 */
951 /* line 3, PREFLEN=4, RANGELEN=3, VAL=4..11, 1110+(VAL-4) */
952 4, /* 1110 000 */
953 5, /* 1110 001 */
954 10, /* 1110 110 */
955 11, /* 1110 111 */
956 /* line 4, PREFLEN=5, RANGELEN=6, VAL=12..75, 11110+(VAL-12) */
957 12, /* 11110 000000 */
958 13, /* 11110 000001 */
959 74, /* 11110 111110 */
960 75, /* 11110 111111 */
961 /* line 5, PREFLEN=5, RANGELEN=32, VAL=76..INF, 11111+(VAL-76) */
962 76, /* 11111 00000000 00000000 00000000 00000000 */
963 77, /* 11111 00000000 00000000 00000000 00000001 */
964};
965const byte test_input_D[] = {
966 /* 0101 1011 1000 0111 0001 1110 1101 1101 */
967 0x5b, 0x87, 0x1e, 0xdd,
968 /* 1111 1100 0000 0111 1000 0001 1111 0111 */
969 0xfc, 0x07, 0x81, 0xf7,
970 /* 1101 1110 1111 1111 1110 0000 0000 0000 */
971 0xde, 0xff, 0xe0, 0x00,
972 /* 0000 0000 0000 0000 0001 1111 0000 0000 */
973 0x00, 0x00, 0x1f, 0x00,
974 /* 0000 0000 0000 0000 0000 0001 */
975 0x00, 0x00, 0x01,
976};
977
978/* test code for Table B.5 - Standard Huffman table E */
979const int32_t test_output_E[] = {
980 /* line 0, PREFLEN=7, RANGELEN=8, VAL=-255..0, 1111110+(VAL+255) */
981 -255, /* 1111110 00000000 */
982 -254, /* 1111110 00000001 */
983 -1, /* 1111110 11111110 */
984 0, /* 1111110 11111111 */
985 /* line 1, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
986 1, /* 0 */
987 /* line 2, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
988 2, /* 10 */
989 /* line 3, PREFLEN=3, RANGELEN=0, VAL=3, 110 */
990 3, /* 110 */
991 /* line 4, PREFLEN=4, RANGELEN=3, VAL=4..11, 1110+(VAL-4) */
992 4, /* 1110 000 */
993 5, /* 1110 001 */
994 10, /* 1110 110 */
995 11, /* 1110 111 */
996 /* line 5, PREFLEN=5, RANGELEN=6, VAL=12..75, 11110+(VAL-12) */
997 12, /* 11110 000000 */
998 13, /* 11110 000001 */
999 74, /* 11110 111110 */
1000 75, /* 11110 111111 */
1001 /* line 6, PREFLEN=7, RANGELEN=32, VAL=-INF..-256, 1111111+(-256-VAL) */
1002 -256, /* 1111111 00000000 00000000 00000000 00000000 */
1003 -257, /* 1111111 00000000 00000000 00000000 00000001 */
1004 /* line 6, PREFLEN=6, RANGELEN=32, VAL=76..INF, 111110+(VAL-76) */
1005 76, /* 111110 00000000 00000000 00000000 00000000 */
1006 77, /* 111110 00000000 00000000 00000000 00000001 */
1007};
1008const byte test_input_E[] = {
1009 /* 1111 1100 0000 0001 1111 1000 0000 0111 */
1010 0xfc, 0x01, 0xf8, 0x07,
1011 /* 1111 0111 1111 0111 1110 1111 1111 0101 */
1012 0xf7, 0xf7, 0xef, 0xf5,
1013 /* 1011 1000 0111 0001 1110 1101 1101 1111 */
1014 0xb8, 0x71, 0xed, 0xdf,
1015 /* 1100 0000 0111 1000 0001 1111 0111 1101 */
1016 0xc0, 0x78, 0x1f, 0x7d,
1017 /* 1110 1111 1111 1111 1000 0000 0000 0000 */
1018 0xef, 0xff, 0x80, 0x00,
1019 /* 0000 0000 0000 0000 0111 1111 0000 0000 */
1020 0x00, 0x00, 0x7f, 0x00,
1021 /* 0000 0000 0000 0000 0000 0001 1111 1000 */
1022 0x00, 0x00, 0x01, 0xf8,
1023 /* 0000 0000 0000 0000 0000 0000 0000 0011 */
1024 0x00, 0x00, 0x00, 0x03,
1025 /* 1110 0000 0000 0000 0000 0000 0000 0000 */
1026 0xe0, 0x00, 0x00, 0x00,
1027 /* 0001 */
1028 0x10,
1029};
1030
1031/* test code for Table B.6 - Standard Huffman table F */
1032const int32_t test_output_F[] = {
1033 /* line 0, PREFLEN=5, RANGELEN=10, VAL=-2048..-1025, 11100+(VAL+2048) */
1034 -2048, /* 11100 00000000 00 */
1035 -2047, /* 11100 00000000 01 */
1036 -1026, /* 11100 11111111 10 */
1037 -1025, /* 11100 11111111 11 */
1038 /* line 1, PREFLEN=4, RANGELEN=9, VAL=-1024..-513, 1000+(VAL+1024) */
1039 -1024, /* 1000 00000000 0 */
1040 -1023, /* 1000 00000000 1 */
1041 -514, /* 1000 11111111 0 */
1042 -513, /* 1000 11111111 1 */
1043 /* line 2, PREFLEN=4, RANGELEN=8, VAL=-512..-257, 1001+(VAL+512) */
1044 -512, /* 1001 00000000 */
1045 -511, /* 1001 00000001 */
1046 -258, /* 1001 11111110 */
1047 -257, /* 1001 11111111 */
1048 /* line 3, PREFLEN=4, RANGELEN=7, VAL=-256..-129, 1010+(VAL+256) */
1049 -256, /* 1010 0000000 */
1050 -255, /* 1010 0000001 */
1051 -130, /* 1010 1111110 */
1052 -129, /* 1010 1111111 */
1053 /* line 4, PREFLEN=5, RANGELEN=6, VAL=-128..-65, 11101+(VAL+128) */
1054 -128, /* 11101 000000 */
1055 -127, /* 11101 000001 */
1056 -66, /* 11101 111110 */
1057 -65, /* 11101 111111 */
1058 /* line 5, PREFLEN=5, RANGELEN=5, VAL=-64..-33, 11110+(VAL+64) */
1059 -64, /* 11110 00000 */
1060 -63, /* 11110 00001 */
1061 -34, /* 11110 11110 */
1062 -33, /* 11110 11111 */
1063 /* line 6, PREFLEN=4, RANGELEN=5, VAL=-32..-1, 1011+(VAL+32) */
1064 -32, /* 1011 00000 */
1065 -31, /* 1011 00001 */
1066 -2, /* 1011 11110 */
1067 -1, /* 1011 11111 */
1068 /* line 7, PREFLEN=2, RANGELEN=7, VAL=0..127, 00+VAL */
1069 0, /* 00 0000000 */
1070 1, /* 00 0000001 */
1071 126, /* 00 1111110 */
1072 127, /* 00 1111111 */
1073 /* line 8, PREFLEN=3, RANGELEN=7, VAL=128..255, 010+(VAL-128) */
1074 128, /* 010 0000000 */
1075 129, /* 010 0000001 */
1076 254, /* 010 1111110 */
1077 255, /* 010 1111111 */
1078 /* line 9, PREFLEN=3, RANGELEN=8, VAL=256..511, 011+(VAL-256) */
1079 256, /* 011 00000000 */
1080 257, /* 011 00000001 */
1081 510, /* 011 11111110 */
1082 511, /* 011 11111111 */
1083 /* line 10, PREFLEN=4, RANGELEN=9, VAL=512..1023, 1100+(VAL-512) */
1084 512, /* 1100 00000000 0 */
1085 513, /* 1100 00000000 1 */
1086 1022, /* 1100 11111111 0 */
1087 1023, /* 1100 11111111 1 */
1088 /* line 11, PREFLEN=4, RANGELEN=10, VAL=1024..2047, 1101+(VAL-1024) */
1089 1024, /* 1101 00000000 00 */
1090 1025, /* 1101 00000000 01 */
1091 2046, /* 1101 11111111 10 */
1092 2047, /* 1101 11111111 11 */
1093 /* line 12, PREFLEN=6, RANGELEN=32, VAL=-INF..-2049, 111110+(-2049-VAL) */
1094 -2049, /* 111110 00000000 00000000 00000000 00000000 */
1095 -2050, /* 111110 00000000 00000000 00000000 00000001 */
1096 /* line 13, PREFLEN=6, RANGELEN=32, VAL=2048..INF, 111111+(VAL-2048) */
1097 2048, /* 111111 00000000 00000000 00000000 00000000 */
1098 2049, /* 111111 00000000 00000000 00000000 00000001 */
1099};
1100const byte test_input_F[] = {
1101 /* 1110 0000 0000 0001 1100 0000 0000 0111 */
1102 0xe0, 0x01, 0xc0, 0x07,
1103 /* 1001 1111 1111 0111 0011 1111 1111 1000 */
1104 0x9f, 0xf7, 0x3f, 0xf8,
1105 /* 0000 0000 0100 0000 0000 0110 0011 1111 */
1106 0x00, 0x40, 0x06, 0x3f,
1107 /* 1101 0001 1111 1111 1001 0000 0000 1001 */
1108 0xd1, 0xff, 0x90, 0x09,
1109 /* 0000 0001 1001 1111 1110 1001 1111 1111 */
1110 0x01, 0x9f, 0xe9, 0xff,
1111 /* 1010 0000 0001 0100 0000 0110 1011 1111 */
1112 0xa0, 0x14, 0x06, 0xbf,
1113 /* 0101 0111 1111 1110 1000 0001 1101 0000 */
1114 0x57, 0xfe, 0x81, 0xd0,
1115 /* 0111 1011 1111 0111 0111 1111 1111 0000 */
1116 0x7b, 0xf7, 0x7f, 0xf0,
1117 /* 0011 1100 0001 1111 0111 1011 1101 1111 */
1118 0x3c, 0x1f, 0x7b, 0xdf,
1119 /* 1011 0000 0101 1000 0110 1111 1101 0111 */
1120 0xb0, 0x58, 0x6f, 0xd7,
1121 /* 1111 0000 0000 0000 0000 0100 1111 1100 */
1122 0xf0, 0x00, 0x04, 0xfc,
1123 /* 0111 1111 0100 0000 0001 0000 0001 0101 */
1124 0x7f, 0x40, 0x10, 0x15,
1125 /* 1111 1001 0111 1111 0110 0000 0000 1100 */
1126 0xf9, 0x7f, 0x60, 0x0c,
1127 /* 0000 0101 1111 1111 0011 1111 1111 1100 */
1128 0x05, 0xff, 0x3f, 0xfc,
1129 /* 0000 0000 0110 0000 0000 0111 0011 1111 */
1130 0x00, 0x60, 0x07, 0x3f,
1131 /* 1101 1001 1111 1111 1101 0000 0000 0011 */
1132 0xd9, 0xff, 0xd0, 0x03,
1133 /* 0100 0000 0001 1101 1111 1111 1011 0111 */
1134 0x40, 0x1d, 0xff, 0xb7,
1135 /* 1111 1111 1111 1000 0000 0000 0000 0000 */
1136 0xff, 0xf8, 0x00, 0x00,
1137 /* 0000 0000 0000 0011 1110 0000 0000 0000 */
1138 0x00, 0x03, 0xe0, 0x00,
1139 /* 0000 0000 0000 0000 0001 1111 1100 0000 */
1140 0x00, 0x00, 0x1f, 0xc0,
1141 /* 0000 0000 0000 0000 0000 0000 0011 1111 */
1142 0x00, 0x00, 0x00, 0x3f,
1143 /* 0000 0000 0000 0000 0000 0000 0000 0001 */
1144 0x00, 0x00, 0x00, 0x01,
1145};
1146
1147/* test code for Table B.7 - Standard Huffman table G */
1148const int32_t test_output_G[] = {
1149 /* line 0, PREFLEN=4, RANGELEN=9, VAL=-1024..-513, 1000+(VAL+1024) */
1150 -1024, /* 1000 00000000 0 */
1151 -1023, /* 1000 00000000 1 */
1152 -514, /* 1000 11111111 0 */
1153 -513, /* 1000 11111111 1 */
1154 /* line 1, PREFLEN=3, RANGELEN=8, VAL=-512..-257, 000+(VAL+512) */
1155 -512, /* 000 00000000 */
1156 -511, /* 000 00000001 */
1157 -258, /* 000 11111110 */
1158 -257, /* 000 11111111 */
1159 /* line 2, PREFLEN=4, RANGELEN=7, VAL=-256..-129, 1001+(VAL+256) */
1160 -256, /* 1001 0000000 */
1161 -255, /* 1001 0000001 */
1162 -130, /* 1001 1111110 */
1163 -129, /* 1001 1111111 */
1164 /* line 3, PREFLEN=5, RANGELEN=6, VAL=-128..-65, 11010+(VAL+128) */
1165 -128, /* 11010 000000 */
1166 -127, /* 11010 000001 */
1167 -66, /* 11010 111110 */
1168 -65, /* 11010 111111 */
1169 /* line 4, PREFLEN=5, RANGELEN=5, VAL=-64..-33, 11011+(VAL+64) */
1170 -64, /* 11011 00000 */
1171 -63, /* 11011 00001 */
1172 -34, /* 11011 11110 */
1173 -33, /* 11011 11111 */
1174 /* line 5, PREFLEN=4, RANGELEN=5, VAL=-32..-1, 1010+(VAL+32) */
1175 -32, /* 1010 00000 */
1176 -31, /* 1010 00001 */
1177 -2, /* 1010 11110 */
1178 -1, /* 1010 11111 */
1179 /* line 6, PREFLEN=4, RANGELEN=5, VAL=0..31, 1011+VAL */
1180 0, /* 1011 00000 */
1181 1, /* 1011 00001 */
1182 30, /* 1011 11110 */
1183 31, /* 1011 11111 */
1184 /* line 7, PREFLEN=5, RANGELEN=5, VAL=32..63, 11100+(VAL-32) */
1185 32, /* 11100 00000 */
1186 33, /* 11100 00001 */
1187 62, /* 11100 11110 */
1188 63, /* 11100 11111 */
1189 /* line 8, PREFLEN=5, RANGELEN=6, VAL=64..127, 11101+(VAL-64) */
1190 64, /* 11101 000000 */
1191 65, /* 11101 000001 */
1192 126, /* 11101 111110 */
1193 127, /* 11101 111111 */
1194 /* line 9, PREFLEN=4, RANGELEN=7, VAL=128..255, 1100+(VAL-128) */
1195 128, /* 1100 0000000 */
1196 129, /* 1100 0000001 */
1197 254, /* 1100 1111110 */
1198 255, /* 1100 1111111 */
1199 /* line 10, PREFLEN=3, RANGELEN=8, VAL=256..511, 001+(VAL-256) */
1200 256, /* 001 00000000 */
1201 257, /* 001 00000001 */
1202 510, /* 001 11111110 */
1203 511, /* 001 11111111 */
1204 /* line 11, PREFLEN=3, RANGELEN=9, VAL=512..1023, 010+(VAL-512) */
1205 512, /* 010 00000000 0 */
1206 513, /* 010 00000000 1 */
1207 1022, /* 010 11111111 0 */
1208 1023, /* 010 11111111 1 */
1209 /* line 12, PREFLEN=3, RANGELEN=10, VAL=1024..2047, 011+(VAL-1024) */
1210 1024, /* 011 00000000 00 */
1211 1025, /* 011 00000000 01 */
1212 2046, /* 011 11111111 10 */
1213 2047, /* 011 11111111 11 */
1214 /* line 13, PREFLEN=5, RANGELEN=32, VAL=-INF..-1025, 11110+(-1025-VAL) */
1215 -1025, /* 11110 00000000 00000000 00000000 00000000 */
1216 -1026, /* 11110 00000000 00000000 00000000 00000001 */
1217 /* line 14, PREFLEN=5, RANGELEN=32, VAL=2048..INF, 11111+(VAL-2048) */
1218 2048, /* 11111 00000000 00000000 00000000 00000000 */
1219 2049, /* 11111 00000000 00000000 00000000 00000001 */
1220};
1221const byte test_input_G[] = {
1222 /* 1000 0000 0000 0100 0000 0000 0110 0011 */
1223 0x80, 0x04, 0x00, 0x63,
1224 /* 1111 1101 0001 1111 1111 0000 0000 0000 */
1225 0xfd, 0x1f, 0xf0, 0x00,
1226 /* 0000 0000 0100 0111 1111 0000 1111 1111 */
1227 0x00, 0x47, 0xf0, 0xff,
1228 /* 1001 0000 0001 0010 0000 0110 0111 1111 */
1229 0x90, 0x12, 0x06, 0x7f,
1230 /* 0100 1111 1111 1101 0000 0001 1010 0000 */
1231 0x4f, 0xfd, 0x01, 0xa0,
1232 /* 0111 0101 1111 0110 1011 1111 1101 1000 */
1233 0x75, 0xf6, 0xbf, 0xd8,
1234 /* 0011 0110 0001 1101 1111 1011 0111 1111 */
1235 0x36, 0x1d, 0xfb, 0x7f,
1236 /* 1010 0000 0101 0000 0110 1011 1101 0101 */
1237 0xa0, 0x50, 0x6b, 0xd5,
1238 /* 1111 1011 0000 0101 1000 0110 1111 1101 */
1239 0xfb, 0x05, 0x86, 0xfd,
1240 /* 0111 1111 1110 0000 0011 1000 0001 1110 */
1241 0x7f, 0xe0, 0x38, 0x1e,
1242 /* 0111 1011 1001 1111 1110 1000 0001 1101 */
1243 0x7b, 0x9f, 0xe8, 0x1d,
1244 /* 0000 0111 1011 1111 0111 0111 1111 1100 */
1245 0x07, 0xbf, 0x77, 0xfc,
1246 /* 0000 0001 1000 0000 0111 0011 1111 0110 */
1247 0x01, 0x80, 0x73, 0xf6,
1248 /* 0111 1111 0010 0000 0000 0100 0000 0100 */
1249 0x7f, 0x20, 0x04, 0x04,
1250 /* 1111 1111 0001 1111 1111 0100 0000 0000 */
1251 0xff, 0x1f, 0xf4, 0x00,
1252 /* 0100 0000 0001 0101 1111 1110 0101 1111 */
1253 0x40, 0x15, 0xfe, 0x5f,
1254 /* 1111 0110 0000 0000 0011 0000 0000 0101 */
1255 0xf6, 0x00, 0x30, 0x05,
1256 /* 1111 1111 1100 1111 1111 1111 1111 0000 */
1257 0xff, 0xcf, 0xff, 0xf0,
1258 /* 0000 0000 0000 0000 0000 0000 0000 0111 */
1259 0x00, 0x00, 0x00, 0x07,
1260 /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1261 0x80, 0x00, 0x00, 0x00,
1262 /* 0111 1110 0000 0000 0000 0000 0000 0000 */
1263 0x7e, 0x00, 0x00, 0x00,
1264 /* 0000 0001 1111 0000 0000 0000 0000 0000 */
1265 0x01, 0xf0, 0x00, 0x00,
1266 /* 0000 0000 0001 */
1267 0x00, 0x10,
1268};
1269
1270/* test code for Table B.8 - Standard Huffman table H */
1271const int32_t test_output_H[] = {
1272 /* line 0, PREFLEN=8, RANGELEN=3, VAL=-15..-8, 11111100+(VAL+15) */
1273 -15, /* 11111100 000 */
1274 -14, /* 11111100 001 */
1275 -9, /* 11111100 110 */
1276 -8, /* 11111100 111 */
1277 /* line 1, PREFLEN=9, RANGELEN=1, VAL=-7..-6, 111111100+(VAL+7) */
1278 -7, /* 111111100 0 */
1279 -6, /* 111111100 1 */
1280 /* line 2, PREFLEN=8, RANGELEN=1, VAL=-5..-4, 11111101+(VAL+5) */
1281 -5, /* 11111101 0 */
1282 -4, /* 11111101 1 */
1283 /* line 3, PREFLEN=9, RANGELEN=0, VAL=-3, 111111101 */
1284 -3, /* 111111101 */
1285 /* line 4, PREFLEN=7, RANGELEN=0, VAL=-2, 1111100 */
1286 -2, /* 1111100 */
1287 /* line 5, PREFLEN=4, RANGELEN=0, VAL=-1, 1010 */
1288 -1, /* 1010 */
1289 /* line 6, PREFLEN=2, RANGELEN=1, VAL=0..1, 00+VAL */
1290 0, /* 00 0 */
1291 1, /* 00 1 */
1292 /* line 7, PREFLEN=5, RANGELEN=0, VAL=2, 11010 */
1293 2, /* 11010 */
1294 /* line 8, PREFLEN=6, RANGELEN=0, VAL=3, 111010 */
1295 3, /* 111010 */
1296 /* line 9, PREFLEN=3, RANGELEN=4, VAL=4..19, 100+(VAL-4) */
1297 4, /* 100 0000 */
1298 5, /* 100 0001 */
1299 18, /* 100 1110 */
1300 19, /* 100 1111 */
1301 /* line 10, PREFLEN=6, RANGELEN=1, VAL=20..21, 111011+(VAL-20) */
1302 20, /* 111011 0 */
1303 21, /* 111011 1 */
1304 /* line 11, PREFLEN=4, RANGELEN=4, VAL=22..37, 1011+(VAL-22) */
1305 22, /* 1011 0000 */
1306 23, /* 1011 0001 */
1307 36, /* 1011 1110 */
1308 37, /* 1011 1111 */
1309 /* line 12, PREFLEN=4, RANGELEN=5, VAL=38..69, 1100+(VAL-38) */
1310 38, /* 1100 00000 */
1311 39, /* 1100 00001 */
1312 68, /* 1100 11110 */
1313 69, /* 1100 11111 */
1314 /* line 13, PREFLEN=5, RANGELEN=6, VAL=70..133, 11011+(VAL-70) */
1315 70, /* 11011 000000 */
1316 71, /* 11011 000001 */
1317 132, /* 11011 111110 */
1318 133, /* 11011 111111 */
1319 /* line 14, PREFLEN=5, RANGELEN=7, VAL=134..261, 11100+(VAL-134) */
1320 134, /* 11100 0000000 */
1321 135, /* 11100 0000001 */
1322 260, /* 11100 1111110 */
1323 261, /* 11100 1111111 */
1324 /* line 15, PREFLEN=6, RANGELEN=7, VAL=262..389, 111100+(VAL-262) */
1325 262, /* 111100 0000000 */
1326 263, /* 111100 0000001 */
1327 388, /* 111100 1111110 */
1328 389, /* 111100 1111111 */
1329 /* line 16, PREFLEN=7, RANGELEN=8, VAL=390..645, 1111101+(VAL-390) */
1330 390, /* 1111101 00000000 */
1331 391, /* 1111101 00000001 */
1332 644, /* 1111101 11111110 */
1333 645, /* 1111101 11111111 */
1334 /* line 17, PREFLEN=6, RANGELEN=10, VAL=646..1669, 111101+(VAL-646) */
1335 646, /* 111101 00000000 00 */
1336 647, /* 111101 00000000 01 */
1337 1668, /* 111101 11111111 10 */
1338 1669, /* 111101 11111111 11 */
1339 /* line 18, PREFLEN=9, RANGELEN=32, VAL=-INF..-16, 111111110+(-16-VAL) */
1340 -16, /* 111111110 00000000 00000000 00000000 00000000 */
1341 -17, /* 111111110 00000000 00000000 00000000 00000001 */
1342 /* line 19, PREFLEN=9, RANGELEN=32, VAL=1670..INF, 111111111+(VAL-1670) */
1343 1670, /* 111111111 00000000 00000000 00000000 00000000 */
1344 1671, /* 111111111 00000000 00000000 00000000 00000001 */
1345 /* line 20, PREFLEN=2, VAL=OOB, 01 */
1346 /*OOB*/ /* 01 */
1347};
1348const byte test_input_H[] = {
1349 /* 1111 1100 0001 1111 1000 0111 1111 0011 */
1350 0xfc, 0x1f, 0x87, 0xf3,
1351 /* 0111 1110 0111 1111 1110 0011 1111 1001 */
1352 0x7e, 0x7f, 0xe3, 0xf9,
1353 /* 1111 1101 0111 1110 1111 1111 1011 1111 */
1354 0xfd, 0x7e, 0xff, 0xbf,
1355 /* 0010 1000 0001 1101 0111 0101 0000 0010 */
1356 0x28, 0x1d, 0x75, 0x02,
1357 /* 0000 1100 1110 1001 1111 1101 1011 1011 */
1358 0x0c, 0xe9, 0xfd, 0xbb,
1359 /* 1101 1000 0101 1000 1101 1111 0101 1111 */
1360 0xd8, 0x58, 0xdf, 0x5f,
1361 /* 1110 0000 0011 0000 0011 1001 1110 1100 */
1362 0xe0, 0x30, 0x39, 0xec,
1363 /* 1111 1110 1100 0000 1101 1000 0011 1011 */
1364 0xfe, 0xc0, 0xd8, 0x3b,
1365 /* 1111 1011 0111 1111 1111 0000 0000 0111 */
1366 0xfb, 0x7f, 0xf0, 0x07,
1367 /* 0000 0000 1111 0011 1111 0111 0011 1111 */
1368 0x00, 0xf3, 0xf7, 0x3f,
1369 /* 1111 1000 0000 0011 1100 0000 0011 1110 */
1370 0xf8, 0x03, 0xc0, 0x3e,
1371 /* 0111 1110 1111 0011 1111 1111 1101 0000 */
1372 0x7e, 0xf3, 0xff, 0xd0,
1373 /* 0000 1111 1010 0000 0011 1111 0111 1111 */
1374 0x0f, 0xa0, 0x3f, 0x7f,
1375 /* 1011 1110 1111 1111 1111 1010 0000 0000 */
1376 0xbe, 0xff, 0xfa, 0x00,
1377 /* 0111 1010 0000 0000 1111 1011 1111 1111 */
1378 0x7a, 0x00, 0xfb, 0xff,
1379 /* 0111 1011 1111 1111 1111 1111 1000 0000 */
1380 0x7b, 0xff, 0xff, 0x80,
1381 /* 0000 0000 0000 0000 0000 0000 0011 1111 */
1382 0x00, 0x00, 0x00, 0x3f,
1383 /* 1100 0000 0000 0000 0000 0000 0000 0000 */
1384 0xc0, 0x00, 0x00, 0x00,
1385 /* 0011 1111 1111 0000 0000 0000 0000 0000 */
1386 0x3f, 0xf0, 0x00, 0x00,
1387 /* 0000 0000 0000 1111 1111 1000 0000 0000 */
1388 0x00, 0x0f, 0xf8, 0x00,
1389 /* 0000 0000 0000 0000 0000 101 */
1390 0x00, 0x00, 0x0a,
1391};
1392
1393/* test code for Table B.9 - Standard Huffman table I */
1394const int32_t test_output_I[] = {
1395 /* line 0, PREFLEN=8, RANGELEN=4, VAL=-31..-16, 11111100+(VAL+31) */
1396 -31, /* 11111100 0000 */
1397 -30, /* 11111100 0001 */
1398 -17, /* 11111100 1110 */
1399 -16, /* 11111100 1111 */
1400 /* line 1, PREFLEN=9, RANGELEN=2, VAL=-15..-12, 111111100+(VAL+15) */
1401 -15, /* 111111100 00 */
1402 -14, /* 111111100 01 */
1403 -13, /* 111111100 10 */
1404 -12, /* 111111100 11 */
1405 /* line 2, PREFLEN=8, RANGELEN=2, VAL=-11..-8, 11111101+(VAL+11) */
1406 -11, /* 11111101 00 */
1407 -10, /* 11111101 01 */
1408 -9, /* 11111101 10 */
1409 -8, /* 11111101 11 */
1410 /* line 3, PREFLEN=9, RANGELEN=1, VAL=-7..-6, 111111101+(VAL+7) */
1411 -7, /* 111111101 0 */
1412 -6, /* 111111101 1 */
1413 /* line 4, PREFLEN=7, RANGELEN=1, VAL=-5..-4, 1111100+(VAL+5) */
1414 -5, /* 1111100 0 */
1415 -4, /* 1111100 1 */
1416 /* line 5, PREFLEN=4, RANGELEN=1, VAL=-3..-2, 1010+(VAL+3) */
1417 -3, /* 1010 0 */
1418 -2, /* 1010 1 */
1419 /* line 6, PREFLEN=3, RANGELEN=1, VAL=-1..0, 010+(VAL+1) */
1420 -1, /* 010 0 */
1421 0, /* 010 1 */
1422 /* line 7, PREFLEN=3, RANGELEN=1, VAL=1..2, 011+(VAL-1) */
1423 1, /* 011 0 */
1424 2, /* 011 1 */
1425 /* line 8, PREFLEN=5, RANGELEN=1, VAL=3..4, 11010+(VAL-3) */
1426 3, /* 11010 0 */
1427 4, /* 11010 1 */
1428 /* line 9, PREFLEN=6, RANGELEN=1, VAL=5..6, 111010+(VAL-5) */
1429 5, /* 111010 0 */
1430 6, /* 111010 1 */
1431 /* line 10, PREFLEN=3, RANGELEN=5, VAL=7..38, 100+(VAL-7) */
1432 7, /* 100 00000 */
1433 8, /* 100 00001 */
1434 37, /* 100 11110 */
1435 38, /* 100 11111 */
1436 /* line 11, PREFLEN=6, RANGELEN=2, VAL=39..42, 111011+(VAL-39) */
1437 39, /* 111011 00 */
1438 40, /* 111011 01 */
1439 41, /* 111011 10 */
1440 42, /* 111011 11 */
1441 /* line 12, PREFLEN=4, RANGELEN=5, VAL=43..74, 1011+(VAL-43) */
1442 43, /* 1011 00000 */
1443 44, /* 1011 00001 */
1444 73, /* 1011 11110 */
1445 74, /* 1011 11111 */
1446 /* line 13, PREFLEN=4, RANGELEN=6, VAL=75..138, 1100+(VAL-75) */
1447 75, /* 1100 000000 */
1448 76, /* 1100 000001 */
1449 137, /* 1100 111110 */
1450 138, /* 1100 111111 */
1451 /* line 14, PREFLEN=5, RANGELEN=7, VAL=139..266, 11011+(VAL-139) */
1452 139, /* 11011 0000000 */
1453 140, /* 11011 0000001 */
1454 265, /* 11011 1111110 */
1455 266, /* 11011 1111111 */
1456 /* line 15, PREFLEN=5, RANGELEN=8, VAL=267..522, 11100+(VAL-267) */
1457 267, /* 11100 00000000 */
1458 268, /* 11100 00000001 */
1459 521, /* 11100 11111110 */
1460 522, /* 11100 11111111 */
1461 /* line 16, PREFLEN=6, RANGELEN=8, VAL=523..778, 111100+(VAL-523) */
1462 523, /* 111100 00000000 */
1463 524, /* 111100 00000001 */
1464 777, /* 111100 11111110 */
1465 778, /* 111100 11111111 */
1466 /* line 17, PREFLEN=7, RANGELEN=9, VAL=779..1290, 1111101+(VAL-779) */
1467 779, /* 1111101 00000000 0 */
1468 780, /* 1111101 00000000 1 */
1469 1289, /* 1111101 11111111 0 */
1470 1290, /* 1111101 11111111 1 */
1471 /* line 18, PREFLEN=6, RANGELEN=11, VAL=1291..3338, 111101+(VAL-1291) */
1472 1291, /* 111101 00000000 000 */
1473 1292, /* 111101 00000000 001 */
1474 3337, /* 111101 11111111 110 */
1475 3338, /* 111101 11111111 111 */
1476 /* line 19, PREFLEN=9, RANGELEN=32, VAL=-INF..-32, 111111110+(-32-VAL) */
1477 -32, /* 111111110 00000000 00000000 00000000 00000000 */
1478 -33, /* 111111110 00000000 00000000 00000000 00000001 */
1479 /* line 20, PREFLEN=9, RANGELEN=32, VAL=3339..INF, 111111111+(VAL-3339) */
1480 3339, /* 111111111 00000000 00000000 00000000 00000000 */
1481 3340, /* 111111111 00000000 00000000 00000000 00000001 */
1482 /* line 21, PREFLEN=2, VAL=OOB, 00 */
1483 /*OOB*/ /* 00 */
1484};
1485const byte test_input_I[] = {
1486 /* 1111 1100 0000 1111 1100 0001 1111 1100 */
1487 0xfc, 0x0f, 0xc1, 0xfc,
1488 /* 1110 1111 1100 1111 1111 1110 0001 1111 */
1489 0xef, 0xcf, 0xfe, 0x1f,
1490 /* 1100 0111 1111 1001 0111 1111 0011 1111 */
1491 0xc7, 0xf9, 0x7f, 0x3f,
1492 /* 1101 0011 1111 0101 1111 1101 1011 1111 */
1493 0xd3, 0xf5, 0xfd, 0xbf,
1494 /* 0111 1111 1110 1011 1111 1011 1111 1000 */
1495 0x7f, 0xeb, 0xfb, 0xf8,
1496 /* 1111 1001 1010 0101 0101 0001 0101 1001 */
1497 0xf9, 0xa5, 0x51, 0x59,
1498 /* 1111 0100 1101 0111 1010 0111 0101 1000 */
1499 0xf4, 0xd7, 0xa7, 0x58,
1500 /* 0000 1000 0001 1001 1110 1001 1111 1110 */
1501 0x08, 0x19, 0xe9, 0xfe,
1502 /* 1100 1110 1101 1110 1110 1110 1111 1011 */
1503 0xce, 0xde, 0xee, 0xfb,
1504 /* 0000 0101 1000 0110 1111 1101 0111 1111 */
1505 0x05, 0x86, 0xfd, 0x7f,
1506 /* 1100 0000 0011 0000 0001 1100 1111 1011 */
1507 0xc0, 0x30, 0x1c, 0xfb,
1508 /* 0011 1111 1101 1000 0000 1101 1000 0001 */
1509 0x3f, 0xd8, 0x0d, 0x81,
1510 /* 1101 1111 1110 1101 1111 1111 1110 0000 */
1511 0xdf, 0xed, 0xff, 0xe0,
1512 /* 0000 0111 0000 0000 0111 1001 1111 1101 */
1513 0x07, 0x00, 0x79, 0xfd,
1514 /* 1100 1111 1111 1111 0000 0000 0011 1100 */
1515 0xcf, 0xff, 0x00, 0x3c,
1516 /* 0000 0001 1111 0011 1111 1011 1100 1111 */
1517 0x01, 0xf3, 0xfb, 0xcf,
1518 /* 1111 1111 1010 0000 0000 1111 1010 0000 */
1519 0xff, 0xa0, 0x0f, 0xa0,
1520 /* 0001 1111 1011 1111 1110 1111 1011 1111 */
1521 0x1f, 0xbf, 0xef, 0xbf,
1522 /* 1111 1111 0100 0000 0000 0111 1010 0000 */
1523 0xff, 0x40, 0x07, 0xa0,
1524 /* 0000 0111 1101 1111 1111 1101 1110 1111 */
1525 0x07, 0xdf, 0xfd, 0xef,
1526 /* 1111 1111 1111 1111 0000 0000 0000 0000 */
1527 0xff, 0xff, 0x00, 0x00,
1528 /* 0000 0000 0000 0000 0111 1111 1000 0000 */
1529 0x00, 0x00, 0x7f, 0x80,
1530 /* 0000 0000 0000 0000 0000 0000 0111 1111 */
1531 0x00, 0x00, 0x00, 0x7f,
1532 /* 1110 0000 0000 0000 0000 0000 0000 0000 */
1533 0xe0, 0x00, 0x00, 0x00,
1534 /* 0001 1111 1111 0000 0000 0000 0000 0000 */
1535 0x1f, 0xf0, 0x00, 0x00,
1536 /* 0000 0000 0001 00 */
1537 0x00, 0x10,
1538};
1539
1540/* test code for Table B.10 - Standard Huffman table J */
1541const int32_t test_output_J[] = {
1542 /* line 0, PREFLEN=7, RANGELEN=4, VAL=-21..-6, 1111010+(VAL+21) */
1543 -21, /* 1111010 0000 */
1544 -20, /* 1111010 0001 */
1545 -7, /* 1111010 1110 */
1546 -6, /* 1111010 1111 */
1547 /* line 1, PREFLEN=8, RANGELEN=0, VAL=-5, 11111100 */
1548 -5, /* 11111100 */
1549 /* line 2, PREFLEN=7, RANGELEN=0, VAL=-5, 1111011 */
1550 -4, /* 1111011 */
1551 /* line 3, PREFLEN=5, RANGELEN=0, VAL=-3, 11000 */
1552 -3, /* 11000 */
1553 /* line 4, PREFLEN=2, RANGELEN=2, VAL=-2..1, 00+(VAL+2) */
1554 -2, /* 00 00 */
1555 -1, /* 00 01 */
1556 0, /* 00 10 */
1557 1, /* 00 11 */
1558 /* line 5, PREFLEN=5, RANGELEN=0, VAL=2, 11001 */
1559 2, /* 11001 */
1560 /* line 6, PREFLEN=6, RANGELEN=0, VAL=3, 110110 */
1561 3, /* 110110 */
1562 /* line 7, PREFLEN=7, RANGELEN=0, VAL=4, 1111100 */
1563 4, /* 1111100 */
1564 /* line 8, PREFLEN=8, RANGELEN=0, VAL=5, 11111101 */
1565 5, /* 11111101 */
1566 /* line 9, PREFLEN=2, RANGELEN=6, VAL=6..69, 01+(VAL-6) */
1567 6, /* 01 000000 */
1568 7, /* 01 000001 */
1569 68, /* 01 111110 */
1570 69, /* 01 111111 */
1571 /* line 8, PREFLEN=5, RANGELEN=5, VAL=70..101, 11010+(VAL-70) */
1572 70, /* 11010 00000 */
1573 71, /* 11010 00001 */
1574 100, /* 11010 11110 */
1575 101, /* 11010 11111 */
1576 /* line 9, PREFLEN=6, RANGELEN=5, VAL=102..133, 110111+(VAL-102) */
1577 102, /* 110111 00000 */
1578 103, /* 110111 00001 */
1579 132, /* 110111 11110 */
1580 133, /* 110111 11111 */
1581 /* line 10, PREFLEN=6, RANGELEN=6, VAL=134..197, 111000+(VAL-134) */
1582 134, /* 111000 000000 */
1583 135, /* 111000 000001 */
1584 196, /* 111000 111110 */
1585 197, /* 111000 111111 */
1586 /* line 11, PREFLEN=6, RANGELEN=7, VAL=198..325, 111001+(VAL-198) */
1587 198, /* 111001 0000000 */
1588 199, /* 111001 0000001 */
1589 324, /* 111001 1111110 */
1590 325, /* 111001 1111111 */
1591 /* line 12, PREFLEN=6, RANGELEN=8, VAL=326..581, 111010+(VAL-326) */
1592 326, /* 111010 00000000 */
1593 327, /* 111010 00000001 */
1594 580, /* 111010 11111110 */
1595 581, /* 111010 11111111 */
1596 /* line 13, PREFLEN=6, RANGELEN=9, VAL=582..1093, 111011+(VAL-582) */
1597 582, /* 111011 00000000 0 */
1598 583, /* 111011 00000000 1 */
1599 1092, /* 111011 11111111 0 */
1600 1093, /* 111011 11111111 1 */
1601 /* line 14, PREFLEN=6, RANGELEN=10, VAL=1094..2117, 111100+(VAL-1094) */
1602 1094, /* 111100 00000000 00 */
1603 1095, /* 111100 00000000 01 */
1604 2116, /* 111100 11111111 10 */
1605 2117, /* 111100 11111111 11 */
1606 /* line 15, PREFLEN=7, RANGELEN=11, VAL=2118..4165, 1111101+(VAL-2118) */
1607 2118, /* 1111101 00000000 000 */
1608 2119, /* 1111101 00000000 001 */
1609 4164, /* 1111101 11111111 110 */
1610 4165, /* 1111101 11111111 111 */
1611 /* line 16, PREFLEN=8, RANGELEN=32, VAL=-INF..-22, 11111110+(-22-VAL) */
1612 -22, /* 11111110 00000000 00000000 00000000 00000000 */
1613 -23, /* 11111110 00000000 00000000 00000000 00000001 */
1614 /* line 17, PREFLEN=8, RANGELEN=32, VAL=4166..INF, 11111111+(VAL-4166) */
1615 4166, /* 11111111 00000000 00000000 00000000 00000000 */
1616 4167, /* 11111111 00000000 00000000 00000000 00000001 */
1617 /* line 8, PREFLEN=2, VAL=OOB, 10 */
1618 /*OOB*/ /* 10 */
1619};
1620const byte test_input_J[] = {
1621 /* 1111 0100 0001 1110 1000 0111 1101 0111 */
1622 0xf4, 0x1e, 0x87, 0xd7,
1623 /* 0111 1010 1111 1111 1100 1111 0111 1000 */
1624 0x7a, 0xff, 0xcf, 0x78,
1625 /* 0000 0001 0010 0011 1100 1110 1101 1111 */
1626 0x01, 0x23, 0xce, 0xdf,
1627 /* 0011 1111 0101 0000 0001 0000 0101 1111 */
1628 0x3f, 0x50, 0x10, 0x5f,
1629 /* 1001 1111 1111 0100 0000 1101 0000 0111 */
1630 0x9f, 0xf4, 0x0d, 0x07,
1631 /* 0101 1110 1101 0111 1111 0111 0000 0110 */
1632 0x5e, 0xd7, 0xf7, 0x06,
1633 /* 1110 0001 1101 1111 1101 1011 1111 1111 */
1634 0xe1, 0xdf, 0xdb, 0xff,
1635 /* 1000 0000 0011 1000 0000 0111 1000 1111 */
1636 0x80, 0x38, 0x07, 0x8f,
1637 /* 1011 1000 1111 1111 1001 0000 0001 1100 */
1638 0xb8, 0xff, 0x90, 0x1c,
1639 /* 1000 0001 1110 0111 1111 0111 0011 1111 */
1640 0x81, 0xe7, 0xf7, 0x3f,
1641 /* 1111 1010 0000 0000 1110 1000 0000 0111 */
1642 0xfa, 0x00, 0xe8, 0x07,
1643 /* 1010 1111 1110 1110 1011 1111 1111 1011 */
1644 0xaf, 0xee, 0xbf, 0xfb,
1645 /* 0000 0000 0111 0110 0000 0001 1110 1111 */
1646 0x00, 0x76, 0x01, 0xef,
1647 /* 1111 1101 1101 1111 1111 1111 1100 0000 */
1648 0xfd, 0xdf, 0xff, 0xc0,
1649 /* 0000 0011 1100 0000 0000 0111 1100 1111 */
1650 0x03, 0xc0, 0x07, 0xcf,
1651 /* 1111 1011 1100 1111 1111 1111 1110 1000 */
1652 0xfb, 0xcf, 0xff, 0xe8,
1653 /* 0000 0000 1111 1010 0000 0000 0111 1110 */
1654 0x00, 0xfa, 0x00, 0x7e,
1655 /* 1111 1111 1110 1111 1011 1111 1111 1111 */
1656 0xff, 0xef, 0xbf, 0xff,
1657 /* 1111 1000 0000 0000 0000 0000 0000 0000 */
1658 0xf8, 0x00, 0x00, 0x00,
1659 /* 0000 0011 1111 1000 0000 0000 0000 0000 */
1660 0x03, 0xf8, 0x00, 0x00,
1661 /* 0000 0000 0000 0111 1111 1100 0000 0000 */
1662 0x00, 0x07, 0xfc, 0x00,
1663 /* 0000 0000 0000 0000 0000 0011 1111 1100 */
1664 0x00, 0x00, 0x03, 0xfc,
1665 /* 0000 0000 0000 0000 0000 0000 0000 0110 */
1666 0x00, 0x00, 0x00, 0x06,
1667};
1668
1669/* test code for Table B.11 - Standard Huffman table K */
1670const int32_t test_output_K[] = {
1671 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1672 1, /* 0 */
1673 /* line 1, PREFLEN=2, RANGELEN=1, VAL=2..3, 10+(VAL-2) */
1674 2, /* 10 0 */
1675 3, /* 10 1 */
1676 /* line 2, PREFLEN=4, RANGELEN=0, VAL=4, 1100 */
1677 4, /* 1100 */
1678 /* line 3, PREFLEN=4, RANGELEN=1, VAL=5..6, 1101+(VAL-5) */
1679 5, /* 1101 0 */
1680 6, /* 1101 1 */
1681 /* line 4, PREFLEN=5, RANGELEN=1, VAL=7..8, 11100+(VAL-7) */
1682 7, /* 11100 0 */
1683 8, /* 11100 1 */
1684 /* line 5, PREFLEN=5, RANGELEN=2, VAL=9..12, 11101+(VAL-9) */
1685 9, /* 11101 00 */
1686 10, /* 11101 01 */
1687 11, /* 11101 10 */
1688 12, /* 11101 11 */
1689 /* line 6, PREFLEN=6, RANGELEN=2, VAL=13..16, 111100+(VAL-13) */
1690 13, /* 111100 00 */
1691 14, /* 111100 01 */
1692 15, /* 111100 10 */
1693 16, /* 111100 11 */
1694 /* line 7, PREFLEN=7, RANGELEN=2, VAL=17..20, 1111010+(VAL-17) */
1695 17, /* 1111010 00 */
1696 18, /* 1111010 01 */
1697 19, /* 1111010 10 */
1698 20, /* 1111010 11 */
1699 /* line 8, PREFLEN=7, RANGELEN=3, VAL=21..28, 1111011+(VAL-21) */
1700 21, /* 1111011 000 */
1701 22, /* 1111011 001 */
1702 27, /* 1111011 110 */
1703 28, /* 1111011 111 */
1704 /* line 9, PREFLEN=7, RANGELEN=4, VAL=29..44, 1111100+(VAL-29) */
1705 29, /* 1111100 0000 */
1706 30, /* 1111100 0001 */
1707 43, /* 1111100 1110 */
1708 44, /* 1111100 1111 */
1709 /* line 10, PREFLEN=7, RANGELEN=5, VAL=45..76, 1111101+(VAL-45) */
1710 45, /* 1111101 00000 */
1711 46, /* 1111101 00001 */
1712 75, /* 1111101 11110 */
1713 76, /* 1111101 11111 */
1714 /* line 11, PREFLEN=7, RANGELEN=6, VAL=77..140, 1111110+(VAL-77) */
1715 77, /* 1111110 000000 */
1716 78, /* 1111110 000001 */
1717 139, /* 1111110 111110 */
1718 140, /* 1111110 111111 */
1719 /* line 12, PREFLEN=7, RANGELEN=32, VAL=141..INF, 1111111+(VAL-141) */
1720 141, /* 1111111 00000000 00000000 00000000 00000000 */
1721 142, /* 1111111 00000000 00000000 00000000 00000001 */
1722};
1723const byte test_input_K[] = {
1724 /* 0100 1011 1001 1010 1101 1111 0001 1100 */
1725 0x4b, 0x9a, 0xdf, 0x1c,
1726 /* 1111 0100 1110 1011 1101 1011 1011 1111 */
1727 0xf4, 0xeb, 0xdb, 0xbf,
1728 /* 1000 0111 1000 1111 1001 0111 1001 1111 */
1729 0x87, 0x8f, 0x97, 0x9f,
1730 /* 1010 0011 1101 0011 1110 1010 1111 0101 */
1731 0xa3, 0xd3, 0xea, 0xf5,
1732 /* 1111 1011 0001 1110 1100 1111 1011 1101 */
1733 0xfb, 0x1e, 0xcf, 0xbd,
1734 /* 1110 1111 1111 1100 0000 1111 1000 0011 */
1735 0xef, 0xfc, 0x0f, 0x83,
1736 /* 1111 0011 1011 1110 0111 1111 1101 0000 */
1737 0xf3, 0xbe, 0x7f, 0xd0,
1738 /* 0111 1101 0000 1111 1101 1111 0111 1101 */
1739 0x7d, 0x0f, 0xdf, 0x7d,
1740 /* 1111 1111 1110 0000 0011 1111 0000 0011 */
1741 0xff, 0xe0, 0x3f, 0x03,
1742 /* 1111 1011 1110 1111 1101 1111 1111 1111 */
1743 0xfb, 0xef, 0xdf, 0xff,
1744 /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1745 0x00, 0x00, 0x00, 0x00,
1746 /* 1111 1110 0000 0000 0000 0000 0000 0000 */
1747 0xfe, 0x00, 0x00, 0x00,
1748 /* 0000 001 */
1749 0x02,
1750};
1751
1752/* test code for Table B.12 - Standard Huffman table L */
1753const int32_t test_output_L[] = {
1754 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1755 1, /* 0 */
1756 /* line 1, PREFLEN=2, RANGELEN=0, VAL=2, 10 */
1757 2, /* 10 */
1758 /* line 2, PREFLEN=3, RANGELEN=1, VAL=3..4, 110+(VAL-3) */
1759 3, /* 110 0 */
1760 4, /* 110 1 */
1761 /* line 3, PREFLEN=5, RANGELEN=0, VAL=5, 11100 */
1762 5, /* 11100 */
1763 /* line 4, PREFLEN=5, RANGELEN=1, VAL=6..7, 11101+(VAL-7) */
1764 6, /* 11101 0 */
1765 7, /* 11101 1 */
1766 /* line 5, PREFLEN=6, RANGELEN=1, VAL=8..9, 111100+(VAL-8) */
1767 8, /* 111100 0 */
1768 9, /* 111100 1 */
1769 /* line 6, PREFLEN=7, RANGELEN=0, VAL=10, 1111010 */
1770 10, /* 1111010 */
1771 /* line 7, PREFLEN=7, RANGELEN=1, VAL=11..12, 1111011+(VAL-11) */
1772 11, /* 1111011 0 */
1773 12, /* 1111011 1 */
1774 /* line 8, PREFLEN=7, RANGELEN=2, VAL=13..16, 1111100+(VAL-13) */
1775 13, /* 1111100 00 */
1776 14, /* 1111100 01 */
1777 15, /* 1111100 10 */
1778 16, /* 1111100 11 */
1779 /* line 9, PREFLEN=7, RANGELEN=3, VAL=17..24, 1111101+(VAL-17) */
1780 17, /* 1111101 000 */
1781 18, /* 1111101 001 */
1782 23, /* 1111101 110 */
1783 24, /* 1111101 111 */
1784 /* line 10, PREFLEN=7, RANGELEN=4, VAL=25..40, 1111110+(VAL-25) */
1785 25, /* 1111110 0000 */
1786 26, /* 1111110 0001 */
1787 39, /* 1111110 1110 */
1788 40, /* 1111110 1111 */
1789 /* line 11, PREFLEN=8, RANGELEN=5, VAL=41..72, 11111110+(VAL-41) */
1790 41, /* 11111110 00000 */
1791 42, /* 11111110 00001 */
1792 71, /* 11111110 11110 */
1793 72, /* 11111110 11111 */
1794 /* line 12, PREFLEN=8, RANGELEN=32, VAL=73..INF, 11111111+(VAL-73) */
1795 73, /* 11111111 00000000 00000000 00000000 00000000 */
1796 74, /* 11111111 00000000 00000000 00000000 00000001 */
1797};
1798const byte test_input_L[] = {
1799 /* 0101 1001 1011 1100 1110 1011 1011 1111 */
1800 0x59, 0xbc, 0xeb, 0xbf,
1801 /* 0001 1110 0111 1101 0111 1011 0111 1011 */
1802 0x1e, 0x7d, 0x7b, 0x7b,
1803 /* 1111 1100 0011 1110 0011 1111 0010 1111 */
1804 0xfc, 0x3e, 0x3f, 0x2f,
1805 /* 1001 1111 1101 0001 1111 0100 1111 1101 */
1806 0x9f, 0xd1, 0xf4, 0xfd,
1807 /* 1101 1111 0111 1111 1110 0000 1111 1100 */
1808 0xdf, 0x7f, 0xe0, 0xfc,
1809 /* 0011 1111 1011 1011 1111 0111 1111 1111 */
1810 0x3f, 0xbb, 0xf7, 0xff,
1811 /* 0000 0011 1111 1000 0011 1111 1101 1110 */
1812 0x03, 0xf8, 0x3f, 0xde,
1813 /* 1111 1110 1111 1111 1111 1000 0000 0000 */
1814 0xfe, 0xff, 0xf8, 0x00,
1815 /* 0000 0000 0000 0000 0000 0111 1111 1000 */
1816 0x00, 0x00, 0x07, 0xf8,
1817 /* 0000 0000 0000 0000 0000 0000 0000 1 */
1818 0x00, 0x00, 0x00, 0x08,
1819};
1820
1821/* test code for Table B.13 - Standard Huffman table M */
1822const int32_t test_output_M[] = {
1823 /* line 0, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1824 1, /* 0 */
1825 /* line 1, PREFLEN=3, RANGELEN=0, VAL=2, 100 */
1826 2, /* 100 */
1827 /* line 2, PREFLEN=3, RANGELEN=0, VAL=3, 1100 */
1828 3, /* 1100 */
1829 /* line 3, PREFLEN=5, RANGELEN=0, VAL=4, 11100 */
1830 4, /* 11100 */
1831 /* line 4, PREFLEN=4, RANGELEN=1, VAL=5..6, 1101+(VAL-5) */
1832 5, /* 1101 0 */
1833 6, /* 1101 1 */
1834 /* line 5, PREFLEN=3, RANGELEN=3, VAL=7..14, 101+(VAL-7) */
1835 7, /* 101 000 */
1836 8, /* 101 001 */
1837 13, /* 101 110 */
1838 14, /* 101 111 */
1839 /* line 6, PREFLEN=6, RANGELEN=1, VAL=15..16, 111010+(VAL-15) */
1840 15, /* 111010 0 */
1841 16, /* 111010 1 */
1842 /* line 7, PREFLEN=6, RANGELEN=2, VAL=17..20, 111011+(VAL-17) */
1843 17, /* 111011 00 */
1844 18, /* 111011 01 */
1845 19, /* 111011 10 */
1846 20, /* 111011 11 */
1847 /* line 8, PREFLEN=6, RANGELEN=3, VAL=21..28, 111100+(VAL-21) */
1848 21, /* 111100 000 */
1849 22, /* 111100 001 */
1850 27, /* 111100 110 */
1851 28, /* 111100 111 */
1852 /* line 9, PREFLEN=6, RANGELEN=4, VAL=29..44, 111101+(VAL-29) */
1853 29, /* 111101 0000 */
1854 30, /* 111101 0001 */
1855 43, /* 111101 1110 */
1856 44, /* 111101 1111 */
1857 /* line 10, PREFLEN=6, RANGELEN=5, VAL=45..76, 111110+(VAL-45) */
1858 45, /* 111110 00000 */
1859 46, /* 111110 00001 */
1860 75, /* 111110 11110 */
1861 76, /* 111110 11111 */
1862 /* line 11, PREFLEN=7, RANGELEN=6, VAL=77..140, 1111110+(VAL-77) */
1863 77, /* 1111110 000000 */
1864 78, /* 1111110 000001 */
1865 139, /* 1111110 111110 */
1866 140, /* 1111110 111111 */
1867 /* line 12, PREFLEN=7, RANGELEN=32, VAL=141..INF, 1111111+(VAL-141) */
1868 141, /* 1111111 00000000 00000000 00000000 00000000 */
1869 142, /* 1111111 00000000 00000000 00000000 00000001 */
1870};
1871const byte test_input_M[] = {
1872 /* 0100 1100 1110 0110 1011 0111 0100 0101 */
1873 0x4c, 0xe6, 0xb7, 0x45,
1874 /* 0011 0111 0101 1111 1101 0011 1010 1111 */
1875 0x37, 0x5f, 0xd3, 0xaf,
1876 /* 0110 0111 0110 1111 0111 0111 0111 1111 */
1877 0x67, 0x6f, 0x77, 0x7f,
1878 /* 1000 0011 1100 0011 1110 0110 1111 0011 */
1879 0x83, 0xc3, 0xe6, 0xf3,
1880 /* 1111 1010 0001 1110 1000 1111 1011 1101 */
1881 0xfa, 0x1e, 0x8f, 0xbd,
1882 /* 1110 1111 1111 1100 0000 1111 1000 0011 */
1883 0xef, 0xfc, 0x0f, 0x83,
1884 /* 1111 0111 1011 1110 1111 1111 1110 0000 */
1885 0xf7, 0xbe, 0xff, 0xe0,
1886 /* 0011 1111 0000 0011 1111 1011 1110 1111 */
1887 0x3f, 0x03, 0xfb, 0xef,
1888 /* 1101 1111 1111 1111 0000 0000 0000 0000 */
1889 0xdf, 0xff, 0x00, 0x00,
1890 /* 0000 0000 0000 0000 1111 1110 0000 0000 */
1891 0x00, 0x00, 0xfe, 0x00,
1892 /* 0000 0000 0000 0000 0000 001 */
1893 0x00, 0x00, 0x02,
1894};
1895
1896/* test code for Table B.14 - Standard Huffman table N */
1897const int32_t test_output_N[] = {
1898 /* line 0, PREFLEN=3, RANGELEN=0, VAL=-2, 100 */
1899 -2, /* 100 */
1900 /* line 1, PREFLEN=3, RANGELEN=0, VAL=-1, 101 */
1901 -1, /* 101 */
1902 /* line 2, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1903 0, /* 0 */
1904 /* line 3, PREFLEN=3, RANGELEN=0, VAL=1, 110 */
1905 1, /* 110 */
1906 /* line 4, PREFLEN=3, RANGELEN=0, VAL=2, 111 */
1907 2, /* 111 */
1908};
1909const byte test_input_N[] = {
1910 /* 1001 0101 1011 1 */
1911 0x95, 0xb8,
1912};
1913
1914/* test code for Table B.15 - Standard Huffman table O */
1915const int32_t test_output_O[] = {
1916 /* line 0, PREFLEN=7, RANGELEN=4, VAL=-24..-9, 1111100+(VAL+24) */
1917 -24, /* 1111100 0000 */
1918 -23, /* 1111100 0001 */
1919 -10, /* 1111100 1110 */
1920 -9, /* 1111100 1111 */
1921 /* line 1, PREFLEN=6, RANGELEN=2, VAL=-8..-5, 111100+(VAL+8) */
1922 -8, /* 111100 00 */
1923 -7, /* 111100 01 */
1924 -6, /* 111100 10 */
1925 -5, /* 111100 11 */
1926 /* line 2, PREFLEN=5, RANGELEN=1, VAL=-4..-3, 11100+(VAL+4) */
1927 -4, /* 11100 0 */
1928 -3, /* 11100 1 */
1929 /* line 3, PREFLEN=4, RANGELEN=0, VAL=-2, 1100 */
1930 -2, /* 1100 */
1931 /* line 4, PREFLEN=3, RANGELEN=0, VAL=-1, 100 */
1932 -1, /* 100 */
1933 /* line 5, PREFLEN=1, RANGELEN=0, VAL=1, 0 */
1934 0, /* 0 */
1935 /* line 6, PREFLEN=3, RANGELEN=0, VAL=1, 101 */
1936 1, /* 101 */
1937 /* line 7, PREFLEN=4, RANGELEN=0, VAL=2, 1101 */
1938 2, /* 1101 */
1939 /* line 8, PREFLEN=5, RANGELEN=1, VAL=3..4, 11101+(VAL-3) */
1940 3, /* 11101 0 */
1941 4, /* 11101 1 */
1942 /* line 9, PREFLEN=6, RANGELEN=2, VAL=5..8, 111101+(VAL-5) */
1943 5, /* 111101 00 */
1944 6, /* 111101 01 */
1945 7, /* 111101 10 */
1946 8, /* 111101 11 */
1947 /* line 10, PREFLEN=7, RANGELEN=4, VAL=9..24, 1111101+(VAL-9) */
1948 9, /* 1111101 0000 */
1949 10, /* 1111101 0001 */
1950 23, /* 1111101 1110 */
1951 24, /* 1111101 1111 */
1952 /* line 11, PREFLEN=7, RANGELEN=32, VAL=-INF..-25, 1111110+(-25-VAL) */
1953 -25, /* 1111110 00000000 00000000 00000000 00000000 */
1954 -26, /* 1111110 00000000 00000000 00000000 00000001 */
1955 /* line 12, PREFLEN=7, RANGELEN=32, VAL=25..INF, 1111111+(VAL-25) */
1956 25, /* 1111111 00000000 00000000 00000000 00000000 */
1957 26, /* 1111111 00000000 00000000 00000000 00000001 */
1958};
1959const byte test_input_O[] = {
1960 /* 1111 1000 0001 1111 0000 0111 1110 0111 */
1961 0xf8, 0x1f, 0x07, 0xe7,
1962 /* 0111 1100 1111 1111 0000 1111 0001 1111 */
1963 0x7c, 0xff, 0x0f, 0x1f,
1964 /* 0010 1111 0011 1110 0011 1001 1100 1000 */
1965 0x2f, 0x3e, 0x39, 0xc8,
1966 /* 1011 1011 1101 0111 0111 1110 1001 1110 */
1967 0xbb, 0xd7, 0x7e, 0x9e,
1968 /* 1011 1110 1101 1110 1111 1111 0100 0011 */
1969 0xbe, 0xde, 0xff, 0x43,
1970 /* 1110 1000 1111 1101 1110 1111 1011 1111 */
1971 0xe8, 0xfd, 0xef, 0xbf,
1972 /* 1111 1000 0000 0000 0000 0000 0000 0000 */
1973 0xf8, 0x00, 0x00, 0x00,
1974 /* 0000 0011 1111 0000 0000 0000 0000 0000 */
1975 0x03, 0xf0, 0x00, 0x00,
1976 /* 0000 0000 0000 1111 1111 0000 0000 0000 */
1977 0x00, 0x0f, 0xf0, 0x00,
1978 /* 0000 0000 0000 0000 0000 1111 1110 0000 */
1979 0x00, 0x00, 0x0f, 0xe0,
1980 /* 0000 0000 0000 0000 0000 0000 001 */
1981 0x00, 0x00, 0x00, 0x20,
1982};
1983
1984typedef struct test_huffmancodes {
1985 const char *name;
1986 const Jbig2HuffmanParams *params;
1987 const byte *input;
1988 const size_t input_len;
1989 const int32_t *output;
1990 const size_t output_len;
1991} test_huffmancodes_t;
1992
1993#define countof(x) (sizeof((x)) / sizeof((x)[0]))
1994
1995#define DEF_TEST_HUFFMANCODES(x) { \
1996 #x, \
1997 &jbig2_huffman_params_##x, \
1998 test_input_##x, countof(test_input_##x), \
1999 test_output_##x, countof(test_output_##x), \
2000}
2001
2002test_huffmancodes_t tests[] = {
2003 DEF_TEST_HUFFMANCODES(A),
2004 DEF_TEST_HUFFMANCODES(B),
2005 DEF_TEST_HUFFMANCODES(C),
2006 DEF_TEST_HUFFMANCODES(D),
2007 DEF_TEST_HUFFMANCODES(E),
2008 DEF_TEST_HUFFMANCODES(F),
2009 DEF_TEST_HUFFMANCODES(G),
2010 DEF_TEST_HUFFMANCODES(H),
2011 DEF_TEST_HUFFMANCODES(I),
2012 DEF_TEST_HUFFMANCODES(J),
2013 DEF_TEST_HUFFMANCODES(K),
2014 DEF_TEST_HUFFMANCODES(L),
2015 DEF_TEST_HUFFMANCODES(M),
2016 DEF_TEST_HUFFMANCODES(N),
2017 DEF_TEST_HUFFMANCODES(O),
2018};
2019
2020typedef struct test_stream {
2021 Jbig2WordStream ws;
2022 test_huffmancodes_t *h;
2023} test_stream_t;
2024
2025static int
2026test_get_word2(Jbig2WordStream *self, size_t offset, uint32_t *word)
2027{
2028 test_stream_t *st = (test_stream_t *) self;
2029 uint32_t val = 0;
2030 int ret = 0;
2031
2032 if (st == NULL || st->h == NULL || word == NULL)
2033 return -1;
2034 if (offset >= st->h->input_len)
2035 return 0;
2036
2037 if (offset < st->h->input_len) {
2038 val |= (st->h->input[offset] << 24);
2039 ret++;
2040 }
2041 if (offset + 1 < st->h->input_len) {
2042 val |= (st->h->input[offset + 1] << 16);
2043 ret++;
2044 }
2045 if (offset + 2 < st->h->input_len) {
2046 val |= (st->h->input[offset + 2] << 8);
2047 ret++;
2048 }
2049 if (offset + 3 < st->h->input_len) {
2050 val |= st->h->input[offset + 3];
2051 ret++;
2052 }
2053 *word = val;
2054 return ret;
2055}
2056
2057static int test2()
2058{
2059 Jbig2Ctx *ctx;
2060 int success = 0;
2061 int i;
2062
2063 ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
2064 if (ctx == NULL) {
2065 fprintf(stderr, "Failed to allocate jbig2 context\n");
2066 return 0;
2067 }
2068
2069 for (i = 0; i < countof(tests); i++) {
2070 Jbig2HuffmanTable *table;
2071 Jbig2HuffmanState *hs;
2072 test_stream_t st;
2073 int32_t code;
2074 bool oob;
2075 int j;
2076
2077 st.ws.get_next_word = test_get_word2;
2078 st.h = &tests[i];
2079 printf("testing Standard Huffman table %s: ", st.h->name);
2080 table = jbig2_build_huffman_table(ctx, st.h->params);
2081 if (table == NULL) {
2082 fprintf(stderr, "jbig2_build_huffman_table() returned NULL!\n");
2083 jbig2_ctx_free(ctx);
2084 return 0;
2085 }
2086 /* jbig2_dump_huffman_table(table); */
2087 hs = jbig2_huffman_new(ctx, &st.ws);
2088 if (hs == NULL) {
2089 fprintf(stderr, "jbig2_huffman_new() returned NULL!\n");
2090 jbig2_release_huffman_table(ctx, table);
2091 jbig2_ctx_free(ctx);
2092 return 0;
2093 }
2094 for (j = 0; j < st.h->output_len; j++) {
2095 printf("%d...", st.h->output[j]);
2096 code = jbig2_huffman_get(hs, table, &oob);
2097 if (code == st.h->output[j] && !oob) {
2098 printf("ok, ");
2099 } else {
2100 int need_comma = 0;
2101
2102 printf("NG(");
2103 if (code != st.h->output[j]) {
2104 printf("%d", code);
2105 need_comma = 1;
2106 }
2107 if (oob) {
2108 if (need_comma)
2109 printf(",");
2110 printf("OOB");
2111 }
2112 printf("), ");
2113 }
2114 }
2115 if (st.h->params->HTOOB) {
2116 printf("OOB...");
2117 code = jbig2_huffman_get(hs, table, &oob);
2118 if (oob) {
2119 printf("ok");
2120 } else {
2121 printf("NG(%d)", code);
2122 }
2123 }
2124 printf("\n");
2125 jbig2_huffman_free(ctx, hs);
2126 jbig2_release_huffman_table(ctx, table);
2127 }
2128
2129 jbig2_ctx_free(ctx);
2130
2131 if (i == countof(tests))
2132 success = 1;
2133
2134 return success;
2135}
2136
2137int
2138main(int argc, char **argv)
2139{
2140 return test1() && test2() ? 0 : 1;
2141}
2142#endif
2143