1 /*
2 * jdhuff.c
3 *
4 * Copyright (C) 1991, 1992, 1993, Thomas G. Lane.
5 * This file is part of the Independent JPEG Group's software.
6 * For conditions of distribution and use, see the accompanying README file.
7 *
8 * This file contains Huffman entropy decoding routines.
9 * These routines are invoked via the methods entropy_decode
10 * and entropy_decode_init/term.
11 */
12
13 #include "jinclude.h"
14
15
16 /* Static variables to avoid passing 'round extra parameters */
17
18 static decompress_info_ptr dcinfo;
19
20 static INT32 get_buffer; /* current bit-extraction buffer */
21 static int bits_left; /* # of unused bits in it */
22 static boolean printed_eod; /* flag to suppress multiple end-of-data msgs */
23
24 LOCAL void
fix_huff_tbl(HUFF_TBL * htbl)25 fix_huff_tbl (HUFF_TBL * htbl)
26 /* Compute derived values for a Huffman table */
27 {
28 int p, i, l, si;
29 int lookbits, ctr;
30 char huffsize[257];
31 UINT16 huffcode[257];
32 UINT16 code;
33
34 /* Figure C.1: make table of Huffman code length for each symbol */
35 /* Note that this is in code-length order. */
36
37 p = 0;
38 for (l = 1; l <= 16; l++) {
39 for (i = 1; i <= (int) htbl->bits[l]; i++)
40 huffsize[p++] = (char) l;
41 }
42 huffsize[p] = 0;
43
44 /* Figure C.2: generate the codes themselves */
45 /* Note that this is in code-length order. */
46
47 code = 0;
48 si = huffsize[0];
49 p = 0;
50 while (huffsize[p]) {
51 while (((int) huffsize[p]) == si) {
52 huffcode[p++] = code;
53 code++;
54 }
55 code <<= 1;
56 si++;
57 }
58
59 /* Figure F.15: generate decoding tables for bit-sequential decoding */
60
61 p = 0;
62 for (l = 1; l <= 16; l++) {
63 if (htbl->bits[l]) {
64 htbl->priv.dec.valptr[l] = p; /* huffval[] index of 1st symbol of code length l */
65 htbl->priv.dec.mincode[l] = huffcode[p]; /* minimum code of length l */
66 p += htbl->bits[l];
67 htbl->priv.dec.maxcode[l] = huffcode[p-1]; /* maximum code of length l */
68 } else {
69 htbl->priv.dec.maxcode[l] = -1; /* -1 if no codes of this length */
70 }
71 }
72 htbl->priv.dec.maxcode[17] = 0xFFFFFL; /* ensures huff_DECODE terminates */
73
74 /* Compute lookahead tables to speed up decoding.
75 * First we set all the table entries to 0, indicating "too long";
76 * then we iterate through the Huffman codes that are short enough and
77 * fill in all the entries that correspond to bit sequences starting
78 * with that code.
79 */
80
81 MEMZERO(htbl->priv.dec.look_nbits, SIZEOF(htbl->priv.dec.look_nbits));
82
83 p = 0;
84 for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
85 for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
86 /* l = current code's length, p = its index in huffcode[] & huffval[]. */
87 /* Generate left-justified code followed by all possible bit sequences */
88 lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
89 for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
90 htbl->priv.dec.look_nbits[lookbits] = l;
91 htbl->priv.dec.look_sym[lookbits] = htbl->huffval[p];
92 lookbits++;
93 }
94 }
95 }
96 }
97
98
99 /*
100 * Code for extracting the next N bits from the input stream.
101 * (N never exceeds 15 for JPEG data.)
102 * This needs to go as fast as possible!
103 *
104 * We read source bytes into get_buffer and dole out bits as needed.
105 * If get_buffer already contains enough bits, they are fetched in-line
106 * by the macros check_bit_buffer and get_bits. When there aren't enough
107 * bits, fill_bit_buffer is called; it will attempt to fill get_buffer to
108 * the "high water mark" (not just to the number of bits needed; this reduces
109 * the function-call overhead cost of entering fill_bit_buffer).
110 * On return, fill_bit_buffer guarantees that get_buffer contains at least
111 * the requested number of bits --- dummy zeroes are inserted if necessary.
112 *
113 * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
114 * of get_buffer to be used. (On machines with wider words, an even larger
115 * buffer could be used.) However, on some machines 32-bit shifts are
116 * relatively slow and take time proportional to the number of places shifted.
117 * (This is true with most PC compilers, for instance.) In this case it may
118 * be a win to set MIN_GET_BITS to the minimum value of 15. This reduces the
119 * average shift distance at the cost of more calls to fill_bit_buffer.
120 */
121
122 #ifdef SLOW_SHIFT_32
123 #define MIN_GET_BITS 15 /* minimum allowable value */
124 #else
125 #define MIN_GET_BITS 25 /* max value for 32-bit get_buffer */
126 #endif
127
128
129 LOCAL void
fill_bit_buffer(int nbits)130 fill_bit_buffer (int nbits)
131 /* Load up the bit buffer to a depth of at least nbits */
132 {
133 /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
134 /* (It is assumed that no request will be for more than that many bits.) */
135 while (bits_left < MIN_GET_BITS) {
136 register int c = JGETC(dcinfo);
137
138 /* If it's 0xFF, check and discard stuffed zero byte */
139 if (c == 0xFF) {
140 int c2 = JGETC(dcinfo);
141 if (c2 != 0) {
142 /* Oops, it's actually a marker indicating end of compressed data. */
143 /* Better put it back for use later */
144 JUNGETC(c2,dcinfo);
145 JUNGETC(c,dcinfo);
146 /* There should be enough bits still left in the data segment; */
147 /* if so, just break out of the while loop. */
148 if (bits_left >= nbits)
149 break;
150 /* Uh-oh. Report corrupted data to user and stuff zeroes into
151 * the data stream, so that we can produce some kind of image.
152 * Note that this will be repeated for each byte demanded for the
153 * rest of the segment; this is a bit slow but not unreasonably so.
154 * The main thing is to avoid getting a zillion warnings, hence
155 * we use a flag to ensure that only one warning appears.
156 */
157 if (! printed_eod) {
158 WARNMS(dcinfo->emethods, "Corrupt JPEG data: premature end of data segment");
159 printed_eod = TRUE;
160 }
161 c = 0; /* insert a zero byte into bit buffer */
162 }
163 }
164
165 /* OK, load c into get_buffer */
166 get_buffer = (get_buffer << 8) | c;
167 bits_left += 8;
168 }
169 }
170
171
172 /*
173 * These macros provide the in-line portion of bit fetching.
174 * Correct usage is:
175 * check_bit_buffer(n); ensure there are N bits in get_buffer
176 * val = get_bits(n); fetch N bits
177 * The value n should be a simple variable, not an expression, because it
178 * is evaluated multiple times.
179 * peek_bits() fetches next N bits without removing them from the buffer.
180 */
181
182 #define check_bit_buffer(nbits) \
183 { if (bits_left < (nbits)) fill_bit_buffer(nbits); }
184
185 #define get_bits(nbits) \
186 (((int) (get_buffer >> (bits_left -= (nbits)))) & ((1<<(nbits))-1))
187
188 #define peek_bits(nbits) \
189 (((int) (get_buffer >> (bits_left - (nbits)))) & ((1<<(nbits))-1))
190
191
192 /*
193 * Routines to extract next Huffman-coded symbol from input bit stream.
194 * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
195 * without looping. Usually, more than 95% of the Huffman codes will be 8
196 * or fewer bits long. The few overlength codes are handled with a loop.
197 * The primary case is made a macro for speed reasons; the secondary
198 * routine slow_DECODE is rarely entered and need not be inline code.
199 *
200 * Notes about the huff_DECODE macro:
201 * 1. The first if-test is coded to call fill_bit_buffer only when necessary.
202 * 2. If the lookahead succeeds, we need only decrement bits_left to remove
203 * the proper number of bits from get_buffer.
204 * 3. If the lookahead table contains no entry, the next code must be
205 * more than HUFF_LOOKAHEAD bits long.
206 * 4. Near the end of the data segment, we may fail to get enough bits
207 * for a lookahead. In that case, we do it the hard way.
208 */
209
210 #define huff_DECODE(htbl,result) \
211 { register int nb, look; \
212 if (bits_left >= HUFF_LOOKAHEAD || \
213 (fill_bit_buffer(0), bits_left >= HUFF_LOOKAHEAD)) { \
214 look = peek_bits(HUFF_LOOKAHEAD); \
215 if ((nb = htbl->priv.dec.look_nbits[look]) != 0) { \
216 bits_left -= nb; \
217 result = htbl->priv.dec.look_sym[look]; \
218 } else \
219 result = slow_DECODE(htbl, HUFF_LOOKAHEAD+1); \
220 } else \
221 result = slow_DECODE(htbl, 1); \
222 }
223
224
225 LOCAL int
slow_DECODE(HUFF_TBL * htbl,int min_bits)226 slow_DECODE (HUFF_TBL * htbl, int min_bits)
227 {
228 register int l = min_bits;
229 register INT32 code;
230
231 /* huff_DECODE has determined that the code is at least min_bits */
232 /* bits long, so fetch that many bits in one swoop. */
233
234 check_bit_buffer(l);
235 code = get_bits(l);
236
237 /* Collect the rest of the Huffman code one bit at a time. */
238 /* This is per Figure F.16 in the JPEG spec. */
239
240 while (code > htbl->priv.dec.maxcode[l]) {
241 code <<= 1;
242 check_bit_buffer(1);
243 code |= get_bits(1);
244 l++;
245 }
246
247 /* With garbage input we may reach the sentinel value l = 17. */
248
249 if (l > 16) {
250 WARNMS(dcinfo->emethods, "Corrupt JPEG data: bad Huffman code");
251 return 0; /* fake a zero as the safest result */
252 }
253
254 return htbl->huffval[ htbl->priv.dec.valptr[l] +
255 ((int) (code - htbl->priv.dec.mincode[l])) ];
256 }
257
258
259 /* Figure F.12: extend sign bit.
260 * On some machines, a shift and add will be faster than a table lookup.
261 */
262
263 #ifdef AVOID_TABLES
264
265 #define huff_EXTEND(x,s) ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
266
267 #else
268
269 #define huff_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
270
271 static const int extend_test[16] = /* entry n is 2**(n-1) */
272 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
273 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
274
275 static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
276 { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
277 ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
278 ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
279 ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
280
281 #endif /* AVOID_TABLES */
282
283
284 /*
285 * Initialize for a Huffman-compressed scan.
286 * This is invoked after reading the SOS marker.
287 */
288
289 METHODDEF void
decoder_init(decompress_info_ptr cinfo)290 decoder_init (decompress_info_ptr cinfo)
291 {
292 short ci;
293 jpeg_component_info * compptr;
294
295 /* Initialize static variables */
296 dcinfo = cinfo;
297 bits_left = 0;
298 printed_eod = FALSE;
299
300 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
301 compptr = cinfo->cur_comp_info[ci];
302 /* Make sure requested tables are present */
303 if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
304 cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
305 ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
306 /* Compute derived values for Huffman tables */
307 /* We may do this more than once for same table, but it's not a big deal */
308 fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
309 fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
310 /* Initialize DC predictions to 0 */
311 cinfo->last_dc_val[ci] = 0;
312 }
313
314 /* Initialize restart stuff */
315 cinfo->restarts_to_go = cinfo->restart_interval;
316 cinfo->next_restart_num = 0;
317 }
318
319
320 /*
321 * Check for a restart marker & resynchronize decoder.
322 */
323
324 LOCAL void
process_restart(decompress_info_ptr cinfo)325 process_restart (decompress_info_ptr cinfo)
326 {
327 int c, nbytes;
328 short ci;
329
330 /* Throw away any unused bits remaining in bit buffer */
331 nbytes = bits_left / 8; /* count any full bytes loaded into buffer */
332 bits_left = 0;
333 printed_eod = FALSE; /* next segment can get another warning */
334
335 /* Scan for next JPEG marker */
336 do {
337 do { /* skip any non-FF bytes */
338 nbytes++;
339 c = JGETC(cinfo);
340 } while (c != 0xFF);
341 do { /* skip any duplicate FFs */
342 /* we don't increment nbytes here since extra FFs are legal */
343 c = JGETC(cinfo);
344 } while (c == 0xFF);
345 } while (c == 0); /* repeat if it was a stuffed FF/00 */
346
347 if (nbytes != 1)
348 WARNMS2(cinfo->emethods,
349 "Corrupt JPEG data: %d extraneous bytes before marker 0x%02x",
350 nbytes-1, c);
351
352 if (c != (RST0 + cinfo->next_restart_num)) {
353 /* Uh-oh, the restart markers have been messed up too. */
354 /* Let the file-format module try to figure out how to resync. */
355 (*cinfo->methods->resync_to_restart) (cinfo, c);
356 } else
357 TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num);
358
359 /* Re-initialize DC predictions to 0 */
360 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
361 cinfo->last_dc_val[ci] = 0;
362
363 /* Update restart state */
364 cinfo->restarts_to_go = cinfo->restart_interval;
365 cinfo->next_restart_num = (cinfo->next_restart_num + 1) & 7;
366 }
367
368
369 /* ZAG[i] is the natural-order position of the i'th element of zigzag order.
370 * If the incoming data is corrupted, decode_mcu could attempt to
371 * reference values beyond the end of the array. To avoid a wild store,
372 * we put some extra zeroes after the real entries.
373 */
374
375 static const short ZAG[DCTSIZE2+16] = {
376 0, 1, 8, 16, 9, 2, 3, 10,
377 17, 24, 32, 25, 18, 11, 4, 5,
378 12, 19, 26, 33, 40, 48, 41, 34,
379 27, 20, 13, 6, 7, 14, 21, 28,
380 35, 42, 49, 56, 57, 50, 43, 36,
381 29, 22, 15, 23, 30, 37, 44, 51,
382 58, 59, 52, 45, 38, 31, 39, 46,
383 53, 60, 61, 54, 47, 55, 62, 63,
384 0, 0, 0, 0, 0, 0, 0, 0, /* extra entries in case k>63 below */
385 0, 0, 0, 0, 0, 0, 0, 0
386 };
387
388
389 /*
390 * Decode and return one MCU's worth of Huffman-compressed coefficients.
391 * This routine also handles quantization descaling and zigzag reordering
392 * of coefficient values.
393 *
394 * The i'th block of the MCU is stored into the block pointed to by
395 * MCU_data[i]. WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
396 * (Wholesale zeroing is usually a little faster than retail...)
397 */
398
399 METHODDEF void
decode_mcu(decompress_info_ptr cinfo,JBLOCKROW * MCU_data)400 decode_mcu (decompress_info_ptr cinfo, JBLOCKROW *MCU_data)
401 {
402 register int s, k, r;
403 short blkn, ci;
404 register JBLOCKROW block;
405 register QUANT_TBL_PTR quanttbl;
406 HUFF_TBL *dctbl;
407 HUFF_TBL *actbl;
408 jpeg_component_info * compptr;
409
410 /* Account for restart interval, process restart marker if needed */
411 if (cinfo->restart_interval) {
412 if (cinfo->restarts_to_go == 0)
413 process_restart(cinfo);
414 cinfo->restarts_to_go--;
415 }
416
417 /* Outer loop handles each block in the MCU */
418
419 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
420 block = MCU_data[blkn];
421 ci = cinfo->MCU_membership[blkn];
422 compptr = cinfo->cur_comp_info[ci];
423 quanttbl = cinfo->quant_tbl_ptrs[compptr->quant_tbl_no];
424 actbl = cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no];
425 dctbl = cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no];
426
427 /* Decode a single block's worth of coefficients */
428
429 /* Section F.2.2.1: decode the DC coefficient difference */
430 huff_DECODE(dctbl, s);
431 if (s) {
432 check_bit_buffer(s);
433 r = get_bits(s);
434 s = huff_EXTEND(r, s);
435 }
436
437 /* Convert DC difference to actual value, update last_dc_val */
438 s += cinfo->last_dc_val[ci];
439 cinfo->last_dc_val[ci] = (JCOEF) s;
440 /* Descale and output the DC coefficient (assumes ZAG[0] = 0) */
441 (*block)[0] = (JCOEF) (((JCOEF) s) * quanttbl[0]);
442
443 /* Section F.2.2.2: decode the AC coefficients */
444 /* Since zero values are skipped, output area must be zeroed beforehand */
445 for (k = 1; k < DCTSIZE2; k++) {
446 huff_DECODE(actbl, s);
447
448 r = s >> 4;
449 s &= 15;
450
451 if (s) {
452 k += r;
453 check_bit_buffer(s);
454 r = get_bits(s);
455 s = huff_EXTEND(r, s);
456 /* Descale coefficient and output in natural (dezigzagged) order */
457 (*block)[ZAG[k]] = (JCOEF) (((JCOEF) s) * quanttbl[k]);
458 } else {
459 if (r != 15)
460 break;
461 k += 15;
462 }
463 }
464 }
465 }
466
467
468 /*
469 * Finish up at the end of a Huffman-compressed scan.
470 */
471
472 METHODDEF void
decoder_term(decompress_info_ptr cinfo)473 decoder_term (decompress_info_ptr cinfo)
474 {
475 /* No work needed */
476 }
477
478
479 /*
480 * The method selection routine for Huffman entropy decoding.
481 */
482
483 GLOBAL void
jseldhuffman(decompress_info_ptr cinfo)484 jseldhuffman (decompress_info_ptr cinfo)
485 {
486 if (! cinfo->arith_code) {
487 cinfo->methods->entropy_decode_init = decoder_init;
488 cinfo->methods->entropy_decode = decode_mcu;
489 cinfo->methods->entropy_decode_term = decoder_term;
490 }
491 }
492