blob: f6b6e0087e06d48260bf45491659b3728e869e7f [file] [log] [blame]
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +00001/*
2 * jdhuff.c
3 *
Thomas G. Lane5ead57a1998-03-27 00:00:00 +00004 * Copyright (C) 1991-1997, Thomas G. Lane.
DRC36a6eec2010-10-08 08:05:44 +00005 * Copyright (C) 2010, D. R. Commander.
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +00006 * This file is part of the Independent JPEG Group's software.
7 * For conditions of distribution and use, see the accompanying README file.
8 *
9 * This file contains Huffman entropy decoding routines.
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000010 *
11 * Much of the complexity here has to do with supporting input suspension.
12 * If the data source module demands suspension, we want to be able to back
13 * up to the start of the current MCU. To do this, we copy state variables
Thomas G. Lanebc79e061995-08-02 00:00:00 +000014 * into local working storage, and update them back to the permanent
15 * storage only upon successful completion of an MCU.
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +000016 */
17
DRC36a6eec2010-10-08 08:05:44 +000018/* Performance enhancements:
DRCe2816642009-09-28 00:33:02 +000019 * Copyright (C)2007 Sun Microsystems, Inc.
DRC0fbb28e2010-07-30 17:15:52 +000020 * Copyright (C)2009-2010 D. R. Commander
DRCe2816642009-09-28 00:33:02 +000021 *
22 * This library is free software and may be redistributed and/or modified under
23 * the terms of the wxWindows Library License, Version 3.1 or (at your option)
24 * any later version. The full license is in the LICENSE.txt file included
25 * with this distribution.
26 *
27 * This library is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * wxWindows Library License for more details.
31 */
32
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000033#define JPEG_INTERNALS
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +000034#include "jinclude.h"
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000035#include "jpeglib.h"
Thomas G. Lanebc79e061995-08-02 00:00:00 +000036#include "jdhuff.h" /* Declarations shared with jdphuff.c */
DRC36a6eec2010-10-08 08:05:44 +000037#include "jpegcomp.h"
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +000038
39
Thomas G. Lanebc79e061995-08-02 00:00:00 +000040/*
41 * Expanded entropy decoder object for Huffman decoding.
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000042 *
43 * The savable_state subrecord contains fields that change within an MCU,
44 * but must not be updated permanently until we complete the MCU.
45 */
46
47typedef struct {
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000048 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
49} savable_state;
50
51/* This macro is to work around compilers with missing or broken
52 * structure assignment. You'll need to fix this code if you have
53 * such a compiler and you change MAX_COMPS_IN_SCAN.
54 */
55
56#ifndef NO_STRUCT_ASSIGN
57#define ASSIGN_STATE(dest,src) ((dest) = (src))
58#else
59#if MAX_COMPS_IN_SCAN == 4
60#define ASSIGN_STATE(dest,src) \
Thomas G. Lanebc79e061995-08-02 00:00:00 +000061 ((dest).last_dc_val[0] = (src).last_dc_val[0], \
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000062 (dest).last_dc_val[1] = (src).last_dc_val[1], \
63 (dest).last_dc_val[2] = (src).last_dc_val[2], \
64 (dest).last_dc_val[3] = (src).last_dc_val[3])
65#endif
66#endif
67
68
69typedef struct {
70 struct jpeg_entropy_decoder pub; /* public fields */
71
Thomas G. Lanebc79e061995-08-02 00:00:00 +000072 /* These fields are loaded into local variables at start of each MCU.
73 * In case of suspension, we exit WITHOUT updating them.
74 */
75 bitread_perm_state bitstate; /* Bit buffer at start of MCU */
76 savable_state saved; /* Other state at start of MCU */
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000077
78 /* These fields are NOT loaded into local working state. */
79 unsigned int restarts_to_go; /* MCUs left in this restart interval */
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000080
81 /* Pointers to derived tables (these workspaces have image lifespan) */
Thomas G. Lanebc79e061995-08-02 00:00:00 +000082 d_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
83 d_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
Thomas G. Lane5ead57a1998-03-27 00:00:00 +000084
85 /* Precalculated info set up by start_pass for use in decode_mcu: */
86
87 /* Pointers to derived tables to be used for each block within an MCU */
88 d_derived_tbl * dc_cur_tbls[D_MAX_BLOCKS_IN_MCU];
89 d_derived_tbl * ac_cur_tbls[D_MAX_BLOCKS_IN_MCU];
90 /* Whether we care about the DC and AC coefficient values for each block */
91 boolean dc_needed[D_MAX_BLOCKS_IN_MCU];
92 boolean ac_needed[D_MAX_BLOCKS_IN_MCU];
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000093} huff_entropy_decoder;
94
95typedef huff_entropy_decoder * huff_entropy_ptr;
96
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +000097
98/*
99 * Initialize for a Huffman-compressed scan.
100 */
101
Thomas G. Lane489583f1996-02-07 00:00:00 +0000102METHODDEF(void)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000103start_pass_huff_decoder (j_decompress_ptr cinfo)
104{
105 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000106 int ci, blkn, dctbl, actbl;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000107 jpeg_component_info * compptr;
108
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000109 /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
110 * This ought to be an error condition, but we make it a warning because
111 * there are some baseline files out there with all zeroes in these bytes.
112 */
113 if (cinfo->Ss != 0 || cinfo->Se != DCTSIZE2-1 ||
114 cinfo->Ah != 0 || cinfo->Al != 0)
115 WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
116
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000117 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
118 compptr = cinfo->cur_comp_info[ci];
119 dctbl = compptr->dc_tbl_no;
120 actbl = compptr->ac_tbl_no;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000121 /* Compute derived values for Huffman tables */
122 /* We may do this more than once for a table, but it's not expensive */
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000123 jpeg_make_d_derived_tbl(cinfo, TRUE, dctbl,
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000124 & entropy->dc_derived_tbls[dctbl]);
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000125 jpeg_make_d_derived_tbl(cinfo, FALSE, actbl,
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000126 & entropy->ac_derived_tbls[actbl]);
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000127 /* Initialize DC predictions to 0 */
128 entropy->saved.last_dc_val[ci] = 0;
129 }
130
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000131 /* Precalculate decoding info for each block in an MCU of this scan */
132 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
133 ci = cinfo->MCU_membership[blkn];
134 compptr = cinfo->cur_comp_info[ci];
135 /* Precalculate which table to use for each block */
136 entropy->dc_cur_tbls[blkn] = entropy->dc_derived_tbls[compptr->dc_tbl_no];
137 entropy->ac_cur_tbls[blkn] = entropy->ac_derived_tbls[compptr->ac_tbl_no];
138 /* Decide whether we really care about the coefficient values */
139 if (compptr->component_needed) {
140 entropy->dc_needed[blkn] = TRUE;
141 /* we don't need the ACs if producing a 1/8th-size image */
DRC49967cd2010-10-09 19:57:51 +0000142 entropy->ac_needed[blkn] = (compptr->_DCT_scaled_size > 1);
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000143 } else {
144 entropy->dc_needed[blkn] = entropy->ac_needed[blkn] = FALSE;
145 }
146 }
147
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000148 /* Initialize bitread state variables */
149 entropy->bitstate.bits_left = 0;
150 entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000151 entropy->pub.insufficient_data = FALSE;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000152
153 /* Initialize restart counter */
154 entropy->restarts_to_go = cinfo->restart_interval;
155}
156
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000157
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000158/*
159 * Compute the derived values for a Huffman table.
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000160 * This routine also performs some validation checks on the table.
161 *
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000162 * Note this is also used by jdphuff.c.
163 */
164
Thomas G. Lane489583f1996-02-07 00:00:00 +0000165GLOBAL(void)
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000166jpeg_make_d_derived_tbl (j_decompress_ptr cinfo, boolean isDC, int tblno,
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000167 d_derived_tbl ** pdtbl)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000168{
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000169 JHUFF_TBL *htbl;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000170 d_derived_tbl *dtbl;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000171 int p, i, l, si, numsymbols;
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000172 int lookbits, ctr;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000173 char huffsize[257];
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000174 unsigned int huffcode[257];
175 unsigned int code;
176
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000177 /* Note that huffsize[] and huffcode[] are filled in code-length order,
178 * paralleling the order of the symbols themselves in htbl->huffval[].
179 */
180
181 /* Find the input Huffman table */
182 if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
183 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
184 htbl =
185 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
186 if (htbl == NULL)
187 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
188
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000189 /* Allocate a workspace if we haven't already done so. */
190 if (*pdtbl == NULL)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000191 *pdtbl = (d_derived_tbl *)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000192 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000193 SIZEOF(d_derived_tbl));
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000194 dtbl = *pdtbl;
195 dtbl->pub = htbl; /* fill in back link */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000196
Thomas G. Lane4a6b7301992-03-17 00:00:00 +0000197 /* Figure C.1: make table of Huffman code length for each symbol */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000198
199 p = 0;
200 for (l = 1; l <= 16; l++) {
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000201 i = (int) htbl->bits[l];
202 if (i < 0 || p + i > 256) /* protect against table overrun */
203 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
204 while (i--)
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000205 huffsize[p++] = (char) l;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000206 }
207 huffsize[p] = 0;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000208 numsymbols = p;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000209
Thomas G. Lane4a6b7301992-03-17 00:00:00 +0000210 /* Figure C.2: generate the codes themselves */
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000211 /* We also validate that the counts represent a legal Huffman code tree. */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000212
213 code = 0;
214 si = huffsize[0];
215 p = 0;
216 while (huffsize[p]) {
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000217 while (((int) huffsize[p]) == si) {
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000218 huffcode[p++] = code;
219 code++;
220 }
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000221 /* code is now 1 more than the last code used for codelength si; but
222 * it must still fit in si bits, since no code is allowed to be all ones.
223 */
224 if (((INT32) code) >= (((INT32) 1) << si))
225 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000226 code <<= 1;
227 si++;
228 }
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000229
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000230 /* Figure F.15: generate decoding tables for bit-sequential decoding */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000231
232 p = 0;
233 for (l = 1; l <= 16; l++) {
234 if (htbl->bits[l]) {
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000235 /* valoffset[l] = huffval[] index of 1st symbol of code length l,
236 * minus the minimum code of length l
237 */
238 dtbl->valoffset[l] = (INT32) p - (INT32) huffcode[p];
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000239 p += htbl->bits[l];
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000240 dtbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000241 } else {
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000242 dtbl->maxcode[l] = -1; /* -1 if no codes of this length */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000243 }
244 }
DRC0fbb28e2010-07-30 17:15:52 +0000245 dtbl->valoffset[17] = 0;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000246 dtbl->maxcode[17] = 0xFFFFFL; /* ensures jpeg_huff_decode terminates */
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000247
248 /* Compute lookahead tables to speed up decoding.
249 * First we set all the table entries to 0, indicating "too long";
250 * then we iterate through the Huffman codes that are short enough and
251 * fill in all the entries that correspond to bit sequences starting
252 * with that code.
253 */
254
DRCe2816642009-09-28 00:33:02 +0000255 for (i = 0; i < (1 << HUFF_LOOKAHEAD); i++)
256 dtbl->lookup[i] = (HUFF_LOOKAHEAD + 1) << HUFF_LOOKAHEAD;
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000257
258 p = 0;
259 for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
260 for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
261 /* l = current code's length, p = its index in huffcode[] & huffval[]. */
262 /* Generate left-justified code followed by all possible bit sequences */
263 lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
264 for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
DRCe2816642009-09-28 00:33:02 +0000265 dtbl->lookup[lookbits] = (l << HUFF_LOOKAHEAD) | htbl->huffval[p];
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000266 lookbits++;
267 }
268 }
269 }
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000270
271 /* Validate symbols as being reasonable.
272 * For AC tables, we make no check, but accept all byte values 0..255.
273 * For DC tables, we require the symbols to be in range 0..15.
274 * (Tighter bounds could be applied depending on the data depth and mode,
275 * but this is sufficient to ensure safe decoding.)
276 */
277 if (isDC) {
278 for (i = 0; i < numsymbols; i++) {
279 int sym = htbl->huffval[i];
280 if (sym < 0 || sym > 15)
281 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
282 }
283 }
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000284}
285
286
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000287/*
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000288 * Out-of-line code for bit fetching (shared with jdphuff.c).
289 * See jdhuff.h for info about usage.
290 * Note: current values of get_buffer and bits_left are passed as parameters,
291 * but are returned in the corresponding fields of the state struct.
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000292 *
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000293 * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
294 * of get_buffer to be used. (On machines with wider words, an even larger
295 * buffer could be used.) However, on some machines 32-bit shifts are
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000296 * quite slow and take time proportional to the number of places shifted.
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000297 * (This is true with most PC compilers, for instance.) In this case it may
298 * be a win to set MIN_GET_BITS to the minimum value of 15. This reduces the
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000299 * average shift distance at the cost of more calls to jpeg_fill_bit_buffer.
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000300 */
301
302#ifdef SLOW_SHIFT_32
303#define MIN_GET_BITS 15 /* minimum allowable value */
304#else
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000305#define MIN_GET_BITS (BIT_BUF_SIZE-7)
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000306#endif
307
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000308
Thomas G. Lane489583f1996-02-07 00:00:00 +0000309GLOBAL(boolean)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000310jpeg_fill_bit_buffer (bitread_working_state * state,
311 register bit_buf_type get_buffer, register int bits_left,
312 int nbits)
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000313/* Load up the bit buffer to a depth of at least nbits */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000314{
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000315 /* Copy heavily used state fields into locals (hopefully registers) */
316 register const JOCTET * next_input_byte = state->next_input_byte;
317 register size_t bytes_in_buffer = state->bytes_in_buffer;
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000318 j_decompress_ptr cinfo = state->cinfo;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000319
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000320 /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000321 /* (It is assumed that no request will be for more than that many bits.) */
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000322 /* We fail to do so only if we hit a marker or are forced to suspend. */
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000323
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000324 if (cinfo->unread_marker == 0) { /* cannot advance past a marker */
325 while (bits_left < MIN_GET_BITS) {
326 register int c;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000327
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000328 /* Attempt to read a byte */
329 if (bytes_in_buffer == 0) {
330 if (! (*cinfo->src->fill_input_buffer) (cinfo))
331 return FALSE;
332 next_input_byte = cinfo->src->next_input_byte;
333 bytes_in_buffer = cinfo->src->bytes_in_buffer;
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000334 }
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000335 bytes_in_buffer--;
336 c = GETJOCTET(*next_input_byte++);
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000337
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000338 /* If it's 0xFF, check and discard stuffed zero byte */
339 if (c == 0xFF) {
340 /* Loop here to discard any padding FF's on terminating marker,
341 * so that we can save a valid unread_marker value. NOTE: we will
342 * accept multiple FF's followed by a 0 as meaning a single FF data
343 * byte. This data pattern is not valid according to the standard.
344 */
345 do {
346 if (bytes_in_buffer == 0) {
347 if (! (*cinfo->src->fill_input_buffer) (cinfo))
348 return FALSE;
349 next_input_byte = cinfo->src->next_input_byte;
350 bytes_in_buffer = cinfo->src->bytes_in_buffer;
351 }
352 bytes_in_buffer--;
353 c = GETJOCTET(*next_input_byte++);
354 } while (c == 0xFF);
355
356 if (c == 0) {
357 /* Found FF/00, which represents an FF data byte */
358 c = 0xFF;
359 } else {
360 /* Oops, it's actually a marker indicating end of compressed data.
361 * Save the marker code for later use.
362 * Fine point: it might appear that we should save the marker into
363 * bitread working state, not straight into permanent state. But
364 * once we have hit a marker, we cannot need to suspend within the
365 * current MCU, because we will read no more bytes from the data
366 * source. So it is OK to update permanent state right away.
367 */
368 cinfo->unread_marker = c;
369 /* See if we need to insert some fake zero bits. */
370 goto no_more_bytes;
371 }
372 }
373
374 /* OK, load c into get_buffer */
375 get_buffer = (get_buffer << 8) | c;
376 bits_left += 8;
377 } /* end while */
378 } else {
379 no_more_bytes:
380 /* We get here if we've read the marker that terminates the compressed
381 * data segment. There should be enough bits in the buffer register
382 * to satisfy the request; if so, no problem.
383 */
384 if (nbits > bits_left) {
385 /* Uh-oh. Report corrupted data to user and stuff zeroes into
386 * the data stream, so that we can produce some kind of image.
387 * We use a nonvolatile flag to ensure that only one warning message
388 * appears per data segment.
389 */
390 if (! cinfo->entropy->insufficient_data) {
391 WARNMS(cinfo, JWRN_HIT_MARKER);
392 cinfo->entropy->insufficient_data = TRUE;
393 }
394 /* Fill the buffer with zero bits */
395 get_buffer <<= MIN_GET_BITS - bits_left;
396 bits_left = MIN_GET_BITS;
397 }
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000398 }
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000399
400 /* Unload the local registers */
401 state->next_input_byte = next_input_byte;
402 state->bytes_in_buffer = bytes_in_buffer;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000403 state->get_buffer = get_buffer;
404 state->bits_left = bits_left;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000405
406 return TRUE;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000407}
408
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000409
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000410/*
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000411 * Out-of-line code for Huffman code decoding.
412 * See jdhuff.h for info about usage.
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000413 */
414
Thomas G. Lane489583f1996-02-07 00:00:00 +0000415GLOBAL(int)
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000416jpeg_huff_decode (bitread_working_state * state,
417 register bit_buf_type get_buffer, register int bits_left,
418 d_derived_tbl * htbl, int min_bits)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000419{
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000420 register int l = min_bits;
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000421 register INT32 code;
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000422
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000423 /* HUFF_DECODE has determined that the code is at least min_bits */
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000424 /* bits long, so fetch that many bits in one swoop. */
425
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000426 CHECK_BIT_BUFFER(*state, l, return -1);
427 code = GET_BITS(l);
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000428
429 /* Collect the rest of the Huffman code one bit at a time. */
430 /* This is per Figure F.16 in the JPEG spec. */
431
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000432 while (code > htbl->maxcode[l]) {
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000433 code <<= 1;
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000434 CHECK_BIT_BUFFER(*state, 1, return -1);
435 code |= GET_BITS(1);
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000436 l++;
437 }
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000438
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000439 /* Unload the local registers */
440 state->get_buffer = get_buffer;
441 state->bits_left = bits_left;
442
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000443 /* With garbage input we may reach the sentinel value l = 17. */
444
445 if (l > 16) {
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000446 WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000447 return 0; /* fake a zero as the safest result */
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000448 }
449
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000450 return htbl->pub->huffval[ (int) (code + htbl->valoffset[l]) ];
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000451}
452
453
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000454/*
455 * Figure F.12: extend sign bit.
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000456 * On some machines, a shift and add will be faster than a table lookup.
457 */
458
DRCe2816642009-09-28 00:33:02 +0000459#define AVOID_TABLES
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000460#ifdef AVOID_TABLES
461
DRCe2816642009-09-28 00:33:02 +0000462#define HUFF_EXTEND(x,s) ((x) + ((((x) - (1<<((s)-1))) >> 31) & (((-1)<<(s)) + 1)))
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000463
464#else
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000465
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000466#define HUFF_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
Thomas G. Lanebd543f01991-12-13 00:00:00 +0000467
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000468static const int extend_test[16] = /* entry n is 2**(n-1) */
469 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
470 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000471
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000472static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
473 { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
474 ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
475 ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
476 ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000477
Thomas G. Lanecc7150e1993-02-18 00:00:00 +0000478#endif /* AVOID_TABLES */
479
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000480
481/*
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000482 * Check for a restart marker & resynchronize decoder.
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000483 * Returns FALSE if must suspend.
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000484 */
485
Thomas G. Lane489583f1996-02-07 00:00:00 +0000486LOCAL(boolean)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000487process_restart (j_decompress_ptr cinfo)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000488{
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000489 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
490 int ci;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000491
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000492 /* Throw away any unused bits remaining in bit buffer; */
493 /* include any full bytes in next_marker's count of discarded bytes */
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000494 cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
495 entropy->bitstate.bits_left = 0;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000496
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000497 /* Advance past the RSTn marker */
498 if (! (*cinfo->marker->read_restart_marker) (cinfo))
499 return FALSE;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000500
501 /* Re-initialize DC predictions to 0 */
502 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000503 entropy->saved.last_dc_val[ci] = 0;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000504
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000505 /* Reset restart counter */
506 entropy->restarts_to_go = cinfo->restart_interval;
507
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000508 /* Reset out-of-data flag, unless read_restart_marker left us smack up
509 * against a marker. In that case we will end up treating the next data
510 * segment as empty, and we can avoid producing bogus output pixels by
511 * leaving the flag set.
512 */
513 if (cinfo->unread_marker == 0)
514 entropy->pub.insufficient_data = FALSE;
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000515
516 return TRUE;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000517}
518
519
DRCe2816642009-09-28 00:33:02 +0000520LOCAL(boolean)
521decode_mcu_slow (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
522{
523 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
524 BITREAD_STATE_VARS;
525 int blkn;
526 savable_state state;
527 /* Outer loop handles each block in the MCU */
528
529 /* Load up working state */
530 BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
531 ASSIGN_STATE(state, entropy->saved);
532
533 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
534 JBLOCKROW block = MCU_data[blkn];
535 d_derived_tbl * dctbl = entropy->dc_cur_tbls[blkn];
536 d_derived_tbl * actbl = entropy->ac_cur_tbls[blkn];
537 register int s, k, r;
538
539 /* Decode a single block's worth of coefficients */
540
541 /* Section F.2.2.1: decode the DC coefficient difference */
542 HUFF_DECODE(s, br_state, dctbl, return FALSE, label1);
543 if (s) {
544 CHECK_BIT_BUFFER(br_state, s, return FALSE);
545 r = GET_BITS(s);
546 s = HUFF_EXTEND(r, s);
547 }
548
549 if (entropy->dc_needed[blkn]) {
550 /* Convert DC difference to actual value, update last_dc_val */
551 int ci = cinfo->MCU_membership[blkn];
552 s += state.last_dc_val[ci];
553 state.last_dc_val[ci] = s;
554 /* Output the DC coefficient (assumes jpeg_natural_order[0] = 0) */
555 (*block)[0] = (JCOEF) s;
556 }
557
558 if (entropy->ac_needed[blkn]) {
559
560 /* Section F.2.2.2: decode the AC coefficients */
561 /* Since zeroes are skipped, output area must be cleared beforehand */
562 for (k = 1; k < DCTSIZE2; k++) {
563 HUFF_DECODE(s, br_state, actbl, return FALSE, label2);
564
565 r = s >> 4;
566 s &= 15;
567
568 if (s) {
569 k += r;
570 CHECK_BIT_BUFFER(br_state, s, return FALSE);
571 r = GET_BITS(s);
572 s = HUFF_EXTEND(r, s);
573 /* Output coefficient in natural (dezigzagged) order.
574 * Note: the extra entries in jpeg_natural_order[] will save us
575 * if k >= DCTSIZE2, which could happen if the data is corrupted.
576 */
577 (*block)[jpeg_natural_order[k]] = (JCOEF) s;
578 } else {
579 if (r != 15)
580 break;
581 k += 15;
582 }
583 }
584
585 } else {
586
587 /* Section F.2.2.2: decode the AC coefficients */
588 /* In this path we just discard the values */
589 for (k = 1; k < DCTSIZE2; k++) {
590 HUFF_DECODE(s, br_state, actbl, return FALSE, label3);
591
592 r = s >> 4;
593 s &= 15;
594
595 if (s) {
596 k += r;
597 CHECK_BIT_BUFFER(br_state, s, return FALSE);
598 DROP_BITS(s);
599 } else {
600 if (r != 15)
601 break;
602 k += 15;
603 }
604 }
605 }
606 }
607
608 /* Completed MCU, so update state */
609 BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
610 ASSIGN_STATE(entropy->saved, state);
611 return TRUE;
612}
613
614
615/***************************************************************/
616
617#define ADD_BYTE { \
618 int val0 = *(buffer++); \
619 int val1 = *(buffer); \
620 \
621 bits_left += 8; \
622 get_buffer = (get_buffer << 8) | (val0); \
623 if (val0 == 0xFF) { \
624 buffer++; \
625 if (val1 != 0) { \
DRCfe6a2ee2011-03-18 05:49:26 +0000626 cinfo->unread_marker = val1; \
DRCe2816642009-09-28 00:33:02 +0000627 buffer -= 2; \
628 get_buffer &= ~0xFF; \
629 } \
630 } \
631}
632
633/***************************************************************/
634
DRC830d5fc2010-04-20 21:13:26 +0000635#if __WORDSIZE == 64 || defined(_WIN64)
DRCe2816642009-09-28 00:33:02 +0000636
637#define ENSURE_SHORT \
638 if (bits_left < 16) { \
639 ADD_BYTE ADD_BYTE ADD_BYTE ADD_BYTE ADD_BYTE ADD_BYTE \
640 }
641
642#else
643
644#define ENSURE_SHORT if (bits_left < 16) { ADD_BYTE ADD_BYTE }
645
646#endif
647
648/***************************************************************/
649
650#define HUFF_DECODE_FAST(symbol, size, htbl) { \
651 ENSURE_SHORT \
652 symbol = PEEK_BITS(HUFF_LOOKAHEAD); \
653 symbol = htbl->lookup[symbol]; \
654 size = symbol >> 8; \
655 bits_left -= size; \
656 symbol = symbol & ((1 << HUFF_LOOKAHEAD) - 1); \
657 if (size == HUFF_LOOKAHEAD + 1) { \
658 symbol = (get_buffer >> bits_left) & ((1 << (size)) - 1); \
659 while (symbol > htbl->maxcode[size]) { \
660 symbol <<= 1; \
661 symbol |= GET_BITS(1); \
662 size++; \
663 } \
DRCfa1d1832011-01-26 05:35:20 +0000664 symbol = htbl->pub->huffval[ (int) (symbol + htbl->valoffset[size]) & 0xFF ]; \
DRCe2816642009-09-28 00:33:02 +0000665 } \
666}
667
668/***************************************************************/
669
670LOCAL(boolean)
671decode_mcu_fast (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
672{
673 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
674 BITREAD_STATE_VARS;
675 JOCTET *buffer;
676 int blkn;
677 savable_state state;
678 /* Outer loop handles each block in the MCU */
679
680 /* Load up working state */
681 BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
682 buffer = (JOCTET *) br_state.next_input_byte;
683 ASSIGN_STATE(state, entropy->saved);
684
685 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
686 JBLOCKROW block = MCU_data[blkn];
687 d_derived_tbl * dctbl = entropy->dc_cur_tbls[blkn];
688 d_derived_tbl * actbl = entropy->ac_cur_tbls[blkn];
689 register int s, k, r, l;
690
691 HUFF_DECODE_FAST(s, l, dctbl);
692 if (s) {
693 ENSURE_SHORT
694 r = GET_BITS(s);
695 s = HUFF_EXTEND(r, s);
696 }
697
698 if (entropy->dc_needed[blkn]) {
699 int ci = cinfo->MCU_membership[blkn];
700 s += state.last_dc_val[ci];
701 state.last_dc_val[ci] = s;
702 (*block)[0] = (JCOEF) s;
703 }
704
705 if (entropy->ac_needed[blkn]) {
706
707 for (k = 1; k < DCTSIZE2; k++) {
708 HUFF_DECODE_FAST(s, l, actbl);
709 r = s >> 4;
710 s &= 15;
711
712 if (s) {
713 k += r;
714 ENSURE_SHORT
715 r = GET_BITS(s);
716 s = HUFF_EXTEND(r, s);
717 (*block)[jpeg_natural_order[k]] = (JCOEF) s;
718 } else {
719 if (r != 15) break;
720 k += 15;
721 }
722 }
723
724 } else {
725
726 for (k = 1; k < DCTSIZE2; k++) {
727 HUFF_DECODE_FAST(s, l, actbl);
728 r = s >> 4;
729 s &= 15;
730
731 if (s) {
732 k += r;
733 ENSURE_SHORT
734 DROP_BITS(s);
735 } else {
736 if (r != 15) break;
737 k += 15;
738 }
739 }
740 }
741 }
742
DRCfe6a2ee2011-03-18 05:49:26 +0000743 if (cinfo->unread_marker != 0 && ! cinfo->entropy->insufficient_data) {
744 WARNMS(cinfo, JWRN_HIT_MARKER);
745 cinfo->entropy->insufficient_data = TRUE;
746 }
747
DRCe2816642009-09-28 00:33:02 +0000748 br_state.bytes_in_buffer -= (buffer - br_state.next_input_byte);
749 br_state.next_input_byte = buffer;
750 BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
751 ASSIGN_STATE(entropy->saved, state);
752 return TRUE;
753}
754
755
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000756/*
757 * Decode and return one MCU's worth of Huffman-compressed coefficients.
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000758 * The coefficients are reordered from zigzag order into natural array order,
759 * but are not dequantized.
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000760 *
761 * The i'th block of the MCU is stored into the block pointed to by
762 * MCU_data[i]. WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
763 * (Wholesale zeroing is usually a little faster than retail...)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000764 *
765 * Returns FALSE if data source requested suspension. In that case no
766 * changes have been made to permanent state. (Exception: some output
767 * coefficients may already have been assigned. This is harmless for
Thomas G. Lanebc79e061995-08-02 00:00:00 +0000768 * this module, since we'll just re-assign them on the next call.)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000769 */
770
DRCe2816642009-09-28 00:33:02 +0000771#define BUFSIZE (DCTSIZE2 * 2)
772
Thomas G. Lane489583f1996-02-07 00:00:00 +0000773METHODDEF(boolean)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000774decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000775{
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000776 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
DRC97f8ec42010-03-20 22:38:53 +0000777 int usefast = 1;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000778
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000779 /* Process restart marker if needed; may have to suspend */
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000780 if (cinfo->restart_interval) {
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000781 if (entropy->restarts_to_go == 0)
782 if (! process_restart(cinfo))
783 return FALSE;
DRC97f8ec42010-03-20 22:38:53 +0000784 usefast = 0;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000785 }
786
DRC97f8ec42010-03-20 22:38:53 +0000787 if (cinfo->src->bytes_in_buffer < BUFSIZE * cinfo->blocks_in_MCU)
788 usefast = 0;
789
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000790 /* If we've run out of data, just leave the MCU set to zeroes.
791 * This way, we return uniform gray for the remainder of the segment.
792 */
793 if (! entropy->pub.insufficient_data) {
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000794
DRC97f8ec42010-03-20 22:38:53 +0000795 if (usefast) {
DRCe2816642009-09-28 00:33:02 +0000796 if (!decode_mcu_fast(cinfo, MCU_data)) return FALSE;
797 }
798 else {
799 if (!decode_mcu_slow(cinfo, MCU_data)) return FALSE;
Thomas G. Lane88aeed41992-12-10 00:00:00 +0000800 }
Thomas G. Lane5ead57a1998-03-27 00:00:00 +0000801
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000802 }
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000803
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000804 /* Account for restart interval (no-op if not using restarts) */
805 entropy->restarts_to_go--;
806
807 return TRUE;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000808}
809
810
811/*
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000812 * Module initialization routine for Huffman entropy decoding.
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000813 */
814
Thomas G. Lane489583f1996-02-07 00:00:00 +0000815GLOBAL(void)
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000816jinit_huff_decoder (j_decompress_ptr cinfo)
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000817{
Thomas G. Lane36a4ccc1994-09-24 00:00:00 +0000818 huff_entropy_ptr entropy;
819 int i;
820
821 entropy = (huff_entropy_ptr)
822 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
823 SIZEOF(huff_entropy_decoder));
824 cinfo->entropy = (struct jpeg_entropy_decoder *) entropy;
825 entropy->pub.start_pass = start_pass_huff_decoder;
826 entropy->pub.decode_mcu = decode_mcu;
827
828 /* Mark tables unallocated */
829 for (i = 0; i < NUM_HUFF_TBLS; i++) {
830 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
Thomas G. Lane2cbeb8a1991-10-07 00:00:00 +0000831 }
832}