4 * This file was part of the Independent JPEG Group's software:
5 * Copyright (C) 1995-1997, Thomas G. Lane.
6 * libjpeg-turbo Modifications:
7 * Copyright (C) 2015-2016, 2018-2022, D. R. Commander.
8 * For conditions of distribution and use, see the accompanying README.ijg
11 * This file contains Huffman entropy decoding routines for progressive JPEG.
13 * Much of the complexity here has to do with supporting input suspension.
14 * If the data source module demands suspension, we want to be able to back
15 * up to the start of the current MCU. To do this, we copy state variables
16 * into local working storage, and update them back to the permanent
17 * storage only upon successful completion of an MCU.
19 * NOTE: All referenced figures are from
20 * Recommendation ITU-T T.81 (1992) | ISO/IEC 10918-1:1994.
23 #define JPEG_INTERNALS
26 #include "jdhuff.h" /* Declarations shared with jdhuff.c */
30 #ifdef D_PROGRESSIVE_SUPPORTED
33 * Expanded entropy decoder object for progressive Huffman decoding.
35 * The savable_state subrecord contains fields that change within an MCU,
36 * but must not be updated permanently until we complete the MCU.
40 unsigned int EOBRUN
; /* remaining EOBs in EOBRUN */
41 int last_dc_val
[MAX_COMPS_IN_SCAN
]; /* last DC coef for each component */
45 struct jpeg_entropy_decoder pub
; /* public fields */
47 /* These fields are loaded into local variables at start of each MCU.
48 * In case of suspension, we exit WITHOUT updating them.
50 bitread_perm_state bitstate
; /* Bit buffer at start of MCU */
51 savable_state saved
; /* Other state at start of MCU */
53 /* These fields are NOT loaded into local working state. */
54 unsigned int restarts_to_go
; /* MCUs left in this restart interval */
56 /* Pointers to derived tables (these workspaces have image lifespan) */
57 d_derived_tbl
*derived_tbls
[NUM_HUFF_TBLS
];
59 d_derived_tbl
*ac_derived_tbl
; /* active table during an AC scan */
60 } phuff_entropy_decoder
;
62 typedef phuff_entropy_decoder
*phuff_entropy_ptr
;
64 /* Forward declarations */
65 METHODDEF(boolean
) decode_mcu_DC_first(j_decompress_ptr cinfo
,
67 METHODDEF(boolean
) decode_mcu_AC_first(j_decompress_ptr cinfo
,
69 METHODDEF(boolean
) decode_mcu_DC_refine(j_decompress_ptr cinfo
,
71 METHODDEF(boolean
) decode_mcu_AC_refine(j_decompress_ptr cinfo
,
76 * Initialize for a Huffman-compressed scan.
80 start_pass_phuff_decoder(j_decompress_ptr cinfo
)
82 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
83 boolean is_DC_band
, bad
;
85 d_derived_tbl
**pdtbl
;
86 int *coef_bit_ptr
, *prev_coef_bit_ptr
;
87 jpeg_component_info
*compptr
;
89 is_DC_band
= (cinfo
->Ss
== 0);
91 /* Validate scan parameters */
97 /* need not check Ss/Se < 0 since they came from unsigned bytes */
98 if (cinfo
->Ss
> cinfo
->Se
|| cinfo
->Se
>= DCTSIZE2
)
100 /* AC scans may have only one component */
101 if (cinfo
->comps_in_scan
!= 1)
104 if (cinfo
->Ah
!= 0) {
105 /* Successive approximation refinement scan: must have Al = Ah-1. */
106 if (cinfo
->Al
!= cinfo
->Ah
- 1)
109 if (cinfo
->Al
> 13) /* need not check for < 0 */
111 /* Arguably the maximum Al value should be less than 13 for 8-bit precision,
112 * but the spec doesn't say so, and we try to be liberal about what we
113 * accept. Note: large Al values could result in out-of-range DC
114 * coefficients during early scans, leading to bizarre displays due to
115 * overflows in the IDCT math. But we won't crash.
118 ERREXIT4(cinfo
, JERR_BAD_PROGRESSION
,
119 cinfo
->Ss
, cinfo
->Se
, cinfo
->Ah
, cinfo
->Al
);
120 /* Update progression status, and verify that scan order is legal.
121 * Note that inter-scan inconsistencies are treated as warnings
122 * not fatal errors ... not clear if this is right way to behave.
124 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
125 int cindex
= cinfo
->cur_comp_info
[ci
]->component_index
;
126 coef_bit_ptr
= &cinfo
->coef_bits
[cindex
][0];
127 prev_coef_bit_ptr
= &cinfo
->coef_bits
[cindex
+ cinfo
->num_components
][0];
128 if (!is_DC_band
&& coef_bit_ptr
[0] < 0) /* AC without prior DC scan */
129 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, 0);
130 for (coefi
= MIN(cinfo
->Ss
, 1); coefi
<= MAX(cinfo
->Se
, 9); coefi
++) {
131 if (cinfo
->input_scan_number
> 1)
132 prev_coef_bit_ptr
[coefi
] = coef_bit_ptr
[coefi
];
134 prev_coef_bit_ptr
[coefi
] = 0;
136 for (coefi
= cinfo
->Ss
; coefi
<= cinfo
->Se
; coefi
++) {
137 int expected
= (coef_bit_ptr
[coefi
] < 0) ? 0 : coef_bit_ptr
[coefi
];
138 if (cinfo
->Ah
!= expected
)
139 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, coefi
);
140 coef_bit_ptr
[coefi
] = cinfo
->Al
;
144 /* Select MCU decoding routine */
145 if (cinfo
->Ah
== 0) {
147 entropy
->pub
.decode_mcu
= decode_mcu_DC_first
;
149 entropy
->pub
.decode_mcu
= decode_mcu_AC_first
;
152 entropy
->pub
.decode_mcu
= decode_mcu_DC_refine
;
154 entropy
->pub
.decode_mcu
= decode_mcu_AC_refine
;
157 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
158 compptr
= cinfo
->cur_comp_info
[ci
];
159 /* Make sure requested tables are present, and compute derived tables.
160 * We may build same derived table more than once, but it's not expensive.
163 if (cinfo
->Ah
== 0) { /* DC refinement needs no table */
164 tbl
= compptr
->dc_tbl_no
;
165 pdtbl
= (d_derived_tbl
**)(entropy
->derived_tbls
) + tbl
;
166 jpeg_make_d_derived_tbl(cinfo
, TRUE
, tbl
, pdtbl
);
169 tbl
= compptr
->ac_tbl_no
;
170 pdtbl
= (d_derived_tbl
**)(entropy
->derived_tbls
) + tbl
;
171 jpeg_make_d_derived_tbl(cinfo
, FALSE
, tbl
, pdtbl
);
172 /* remember the single active table */
173 entropy
->ac_derived_tbl
= entropy
->derived_tbls
[tbl
];
175 /* Initialize DC predictions to 0 */
176 entropy
->saved
.last_dc_val
[ci
] = 0;
179 /* Initialize bitread state variables */
180 entropy
->bitstate
.bits_left
= 0;
181 entropy
->bitstate
.get_buffer
= 0; /* unnecessary, but keeps Purify quiet */
182 entropy
->pub
.insufficient_data
= FALSE
;
184 /* Initialize private state variables */
185 entropy
->saved
.EOBRUN
= 0;
187 /* Initialize restart counter */
188 entropy
->restarts_to_go
= cinfo
->restart_interval
;
193 * Figure F.12: extend sign bit.
194 * On some machines, a shift and add will be faster than a table lookup.
200 #define NEG_1 ((unsigned)-1)
201 #define HUFF_EXTEND(x, s) \
202 ((x) < (1 << ((s) - 1)) ? (x) + (((NEG_1) << (s)) + 1) : (x))
206 #define HUFF_EXTEND(x, s) \
207 ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
209 static const int extend_test
[16] = { /* entry n is 2**(n-1) */
210 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
211 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000
214 static const int extend_offset
[16] = { /* entry n is (-1 << n) + 1 */
215 0, ((-1) << 1) + 1, ((-1) << 2) + 1, ((-1) << 3) + 1, ((-1) << 4) + 1,
216 ((-1) << 5) + 1, ((-1) << 6) + 1, ((-1) << 7) + 1, ((-1) << 8) + 1,
217 ((-1) << 9) + 1, ((-1) << 10) + 1, ((-1) << 11) + 1, ((-1) << 12) + 1,
218 ((-1) << 13) + 1, ((-1) << 14) + 1, ((-1) << 15) + 1
221 #endif /* AVOID_TABLES */
225 * Check for a restart marker & resynchronize decoder.
226 * Returns FALSE if must suspend.
230 process_restart(j_decompress_ptr cinfo
)
232 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
235 /* Throw away any unused bits remaining in bit buffer; */
236 /* include any full bytes in next_marker's count of discarded bytes */
237 cinfo
->marker
->discarded_bytes
+= entropy
->bitstate
.bits_left
/ 8;
238 entropy
->bitstate
.bits_left
= 0;
240 /* Advance past the RSTn marker */
241 if (!(*cinfo
->marker
->read_restart_marker
) (cinfo
))
244 /* Re-initialize DC predictions to 0 */
245 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++)
246 entropy
->saved
.last_dc_val
[ci
] = 0;
247 /* Re-init EOB run count, too */
248 entropy
->saved
.EOBRUN
= 0;
250 /* Reset restart counter */
251 entropy
->restarts_to_go
= cinfo
->restart_interval
;
253 /* Reset out-of-data flag, unless read_restart_marker left us smack up
254 * against a marker. In that case we will end up treating the next data
255 * segment as empty, and we can avoid producing bogus output pixels by
256 * leaving the flag set.
258 if (cinfo
->unread_marker
== 0)
259 entropy
->pub
.insufficient_data
= FALSE
;
266 * Huffman MCU decoding.
267 * Each of these routines decodes and returns one MCU's worth of
268 * Huffman-compressed coefficients.
269 * The coefficients are reordered from zigzag order into natural array order,
270 * but are not dequantized.
272 * The i'th block of the MCU is stored into the block pointed to by
273 * MCU_data[i]. WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
275 * We return FALSE if data source requested suspension. In that case no
276 * changes have been made to permanent state. (Exception: some output
277 * coefficients may already have been assigned. This is harmless for
278 * spectral selection, since we'll just re-assign them on the next call.
279 * Successive approximation AC refinement has to be more careful, however.)
283 * MCU decoding for DC initial scan (either spectral selection,
284 * or first pass of successive approximation).
288 decode_mcu_DC_first(j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
290 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
298 jpeg_component_info
*compptr
;
300 /* Process restart marker if needed; may have to suspend */
301 if (cinfo
->restart_interval
) {
302 if (entropy
->restarts_to_go
== 0)
303 if (!process_restart(cinfo
))
307 /* If we've run out of data, just leave the MCU set to zeroes.
308 * This way, we return uniform gray for the remainder of the segment.
310 if (!entropy
->pub
.insufficient_data
) {
312 /* Load up working state */
313 BITREAD_LOAD_STATE(cinfo
, entropy
->bitstate
);
314 state
= entropy
->saved
;
316 /* Outer loop handles each block in the MCU */
318 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
319 block
= MCU_data
[blkn
];
320 ci
= cinfo
->MCU_membership
[blkn
];
321 compptr
= cinfo
->cur_comp_info
[ci
];
322 tbl
= entropy
->derived_tbls
[compptr
->dc_tbl_no
];
324 /* Decode a single block's worth of coefficients */
326 /* Section F.2.2.1: decode the DC coefficient difference */
327 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label1
);
329 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
331 s
= HUFF_EXTEND(r
, s
);
334 /* Convert DC difference to actual value, update last_dc_val */
335 if ((state
.last_dc_val
[ci
] >= 0 &&
336 s
> INT_MAX
- state
.last_dc_val
[ci
]) ||
337 (state
.last_dc_val
[ci
] < 0 && s
< INT_MIN
- state
.last_dc_val
[ci
]))
338 ERREXIT(cinfo
, JERR_BAD_DCT_COEF
);
339 s
+= state
.last_dc_val
[ci
];
340 state
.last_dc_val
[ci
] = s
;
341 /* Scale and output the coefficient (assumes jpeg_natural_order[0]=0) */
342 (*block
)[0] = (JCOEF
)LEFT_SHIFT(s
, Al
);
345 /* Completed MCU, so update state */
346 BITREAD_SAVE_STATE(cinfo
, entropy
->bitstate
);
347 entropy
->saved
= state
;
350 /* Account for restart interval (no-op if not using restarts) */
351 if (cinfo
->restart_interval
)
352 entropy
->restarts_to_go
--;
359 * MCU decoding for AC initial scan (either spectral selection,
360 * or first pass of successive approximation).
364 decode_mcu_AC_first(j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
366 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
369 register int s
, k
, r
;
375 /* Process restart marker if needed; may have to suspend */
376 if (cinfo
->restart_interval
) {
377 if (entropy
->restarts_to_go
== 0)
378 if (!process_restart(cinfo
))
382 /* If we've run out of data, just leave the MCU set to zeroes.
383 * This way, we return uniform gray for the remainder of the segment.
385 if (!entropy
->pub
.insufficient_data
) {
387 /* Load up working state.
388 * We can avoid loading/saving bitread state if in an EOB run.
390 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
392 /* There is always only one block per MCU */
394 if (EOBRUN
> 0) /* if it's a band of zeroes... */
395 EOBRUN
--; /* ...process it now (we do nothing) */
397 BITREAD_LOAD_STATE(cinfo
, entropy
->bitstate
);
399 tbl
= entropy
->ac_derived_tbl
;
401 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
402 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label2
);
407 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
409 s
= HUFF_EXTEND(r
, s
);
410 /* Scale and output coefficient in natural (dezigzagged) order */
411 (*block
)[jpeg_natural_order
[k
]] = (JCOEF
)LEFT_SHIFT(s
, Al
);
413 if (r
== 15) { /* ZRL */
414 k
+= 15; /* skip 15 zeroes in band */
415 } else { /* EOBr, run length is 2^r + appended bits */
417 if (r
) { /* EOBr, r > 0 */
418 CHECK_BIT_BUFFER(br_state
, r
, return FALSE
);
422 EOBRUN
--; /* this band is processed at this moment */
423 break; /* force end-of-band */
428 BITREAD_SAVE_STATE(cinfo
, entropy
->bitstate
);
431 /* Completed MCU, so update state */
432 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
435 /* Account for restart interval (no-op if not using restarts) */
436 if (cinfo
->restart_interval
)
437 entropy
->restarts_to_go
--;
444 * MCU decoding for DC successive approximation refinement scan.
445 * Note: we assume such scans can be multi-component, although the spec
446 * is not very clear on the point.
450 decode_mcu_DC_refine(j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
452 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
453 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
458 /* Process restart marker if needed; may have to suspend */
459 if (cinfo
->restart_interval
) {
460 if (entropy
->restarts_to_go
== 0)
461 if (!process_restart(cinfo
))
465 /* Not worth the cycles to check insufficient_data here,
466 * since we will not change the data anyway if we read zeroes.
469 /* Load up working state */
470 BITREAD_LOAD_STATE(cinfo
, entropy
->bitstate
);
472 /* Outer loop handles each block in the MCU */
474 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
475 block
= MCU_data
[blkn
];
477 /* Encoded data is simply the next bit of the two's-complement DC value */
478 CHECK_BIT_BUFFER(br_state
, 1, return FALSE
);
481 /* Note: since we use |=, repeating the assignment later is safe */
484 /* Completed MCU, so update state */
485 BITREAD_SAVE_STATE(cinfo
, entropy
->bitstate
);
487 /* Account for restart interval (no-op if not using restarts) */
488 if (cinfo
->restart_interval
)
489 entropy
->restarts_to_go
--;
496 * MCU decoding for AC successive approximation refinement scan.
500 decode_mcu_AC_refine(j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
502 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
)cinfo
->entropy
;
504 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
505 int m1
= (NEG_1
) << cinfo
->Al
; /* -1 in the bit position being coded */
506 register int s
, k
, r
;
513 int newnz_pos
[DCTSIZE2
];
515 /* Process restart marker if needed; may have to suspend */
516 if (cinfo
->restart_interval
) {
517 if (entropy
->restarts_to_go
== 0)
518 if (!process_restart(cinfo
))
522 /* If we've run out of data, don't modify the MCU.
524 if (!entropy
->pub
.insufficient_data
) {
526 /* Load up working state */
527 BITREAD_LOAD_STATE(cinfo
, entropy
->bitstate
);
528 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
530 /* There is always only one block per MCU */
532 tbl
= entropy
->ac_derived_tbl
;
534 /* If we are forced to suspend, we must undo the assignments to any newly
535 * nonzero coefficients in the block, because otherwise we'd get confused
536 * next time about which coefficients were already nonzero.
537 * But we need not undo addition of bits to already-nonzero coefficients;
538 * instead, we can test the current bit to see if we already did it.
542 /* initialize coefficient loop counter to start of band */
546 for (; k
<= Se
; k
++) {
547 HUFF_DECODE(s
, br_state
, tbl
, goto undoit
, label3
);
551 if (s
!= 1) /* size of new coef should always be 1 */
552 WARNMS(cinfo
, JWRN_HUFF_BAD_CODE
);
553 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
555 s
= p1
; /* newly nonzero coef is positive */
557 s
= m1
; /* newly nonzero coef is negative */
560 EOBRUN
= 1 << r
; /* EOBr, run length is 2^r + appended bits */
562 CHECK_BIT_BUFFER(br_state
, r
, goto undoit
);
566 break; /* rest of block is handled by EOB logic */
568 /* note s = 0 for processing ZRL */
570 /* Advance over already-nonzero coefs and r still-zero coefs,
571 * appending correction bits to the nonzeroes. A correction bit is 1
572 * if the absolute value of the coefficient must be increased.
575 thiscoef
= *block
+ jpeg_natural_order
[k
];
576 if (*thiscoef
!= 0) {
577 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
579 if ((*thiscoef
& p1
) == 0) { /* do nothing if already set it */
581 *thiscoef
+= (JCOEF
)p1
;
583 *thiscoef
+= (JCOEF
)m1
;
588 break; /* reached target zero coefficient */
593 int pos
= jpeg_natural_order
[k
];
594 /* Output newly nonzero coefficient */
595 (*block
)[pos
] = (JCOEF
)s
;
596 /* Remember its position in case we have to suspend */
597 newnz_pos
[num_newnz
++] = pos
;
603 /* Scan any remaining coefficient positions after the end-of-band
604 * (the last newly nonzero coefficient, if any). Append a correction
605 * bit to each already-nonzero coefficient. A correction bit is 1
606 * if the absolute value of the coefficient must be increased.
608 for (; k
<= Se
; k
++) {
609 thiscoef
= *block
+ jpeg_natural_order
[k
];
610 if (*thiscoef
!= 0) {
611 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
613 if ((*thiscoef
& p1
) == 0) { /* do nothing if already changed it */
615 *thiscoef
+= (JCOEF
)p1
;
617 *thiscoef
+= (JCOEF
)m1
;
622 /* Count one block completed in EOB run */
626 /* Completed MCU, so update state */
627 BITREAD_SAVE_STATE(cinfo
, entropy
->bitstate
);
628 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
631 /* Account for restart interval (no-op if not using restarts) */
632 if (cinfo
->restart_interval
)
633 entropy
->restarts_to_go
--;
638 /* Re-zero any output coefficients that we made newly nonzero */
639 while (num_newnz
> 0)
640 (*block
)[newnz_pos
[--num_newnz
]] = 0;
647 * Module initialization routine for progressive Huffman entropy decoding.
651 jinit_phuff_decoder(j_decompress_ptr cinfo
)
653 phuff_entropy_ptr entropy
;
657 entropy
= (phuff_entropy_ptr
)
658 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
)cinfo
, JPOOL_IMAGE
,
659 sizeof(phuff_entropy_decoder
));
660 cinfo
->entropy
= (struct jpeg_entropy_decoder
*)entropy
;
661 entropy
->pub
.start_pass
= start_pass_phuff_decoder
;
663 /* Mark derived tables unallocated */
664 for (i
= 0; i
< NUM_HUFF_TBLS
; i
++) {
665 entropy
->derived_tbls
[i
] = NULL
;
668 /* Create progression status table */
669 cinfo
->coef_bits
= (int (*)[DCTSIZE2
])
670 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
)cinfo
, JPOOL_IMAGE
,
671 cinfo
->num_components
* 2 * DCTSIZE2
*
673 coef_bit_ptr
= &cinfo
->coef_bits
[0][0];
674 for (ci
= 0; ci
< cinfo
->num_components
; ci
++)
675 for (i
= 0; i
< DCTSIZE2
; i
++)
676 *coef_bit_ptr
++ = -1;
679 #endif /* D_PROGRESSIVE_SUPPORTED */