/src/ghostpdl/jbig2dec/jbig2_huffman.c

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

Coverage Report

Created: 2026-07-24 07:44