8 * Copyright (C) 1995-1998, Thomas G. Lane.
9 * This file is part of the Independent JPEG Group's software.
10 * For conditions of distribution and use, see the accompanying README file.
12 * This file contains Huffman entropy decoding routines for progressive JPEG.
14 * Much of the complexity here has to do with supporting input suspension.
15 * If the data source module demands suspension, we want to be able to back
16 * up to the start of the current MCU. To do this, we copy state variables
17 * into local working storage, and update them back to the permanent
18 * storage only upon successful completion of an MCU.
21 #define JPEG_INTERNALS
24 #include "jlossy.h" /* Private declarations for lossy subsystem */
25 #include "jdhuff.h" /* Declarations shared with jd*huff.c */
28 #ifdef D_PROGRESSIVE_SUPPORTED
31 * Private entropy decoder object for progressive Huffman decoding.
33 * The savable_state subrecord contains fields that change within an MCU,
34 * but must not be updated permanently until we complete the MCU.
38 unsigned int EOBRUN
; /* remaining EOBs in EOBRUN */
39 int last_dc_val
[MAX_COMPS_IN_SCAN
]; /* last DC coef for each component */
42 /* This macro is to work around compilers with missing or broken
43 * structure assignment. You'll need to fix this code if you have
44 * such a compiler and you change MAX_COMPS_IN_SCAN.
47 #ifndef NO_STRUCT_ASSIGN
48 #define ASSIGN_STATE(dest,src) ((dest) = (src))
50 #if MAX_COMPS_IN_SCAN == 4
51 #define ASSIGN_STATE(dest,src) \
52 ((dest).EOBRUN = (src).EOBRUN, \
53 (dest).last_dc_val[0] = (src).last_dc_val[0], \
54 (dest).last_dc_val[1] = (src).last_dc_val[1], \
55 (dest).last_dc_val[2] = (src).last_dc_val[2], \
56 (dest).last_dc_val[3] = (src).last_dc_val[3])
62 huffd_common_fields
; /* Fields shared with other entropy decoders */
64 /* These fields are loaded into local variables at start of each MCU.
65 * In case of suspension, we exit WITHOUT updating them.
67 savable_state saved
; /* Other state at start of MCU */
69 /* These fields are NOT loaded into local working state. */
70 unsigned int restarts_to_go
; /* MCUs left in this restart interval */
72 /* Pointers to derived tables (these workspaces have image lifespan) */
73 d_derived_tbl
* derived_tbls
[NUM_HUFF_TBLS
];
75 d_derived_tbl
* ac_derived_tbl
; /* active table during an AC scan */
76 } phuff_entropy_decoder
;
78 typedef phuff_entropy_decoder
* phuff_entropy_ptr
;
80 /* Forward declarations */
81 METHODDEF(boolean
) decode_mcu_DC_first
JPP((j_decompress_ptr cinfo
,
82 JBLOCKROW
*MCU_data
));
83 METHODDEF(boolean
) decode_mcu_AC_first
JPP((j_decompress_ptr cinfo
,
84 JBLOCKROW
*MCU_data
));
85 METHODDEF(boolean
) decode_mcu_DC_refine
JPP((j_decompress_ptr cinfo
,
86 JBLOCKROW
*MCU_data
));
87 METHODDEF(boolean
) decode_mcu_AC_refine
JPP((j_decompress_ptr cinfo
,
88 JBLOCKROW
*MCU_data
));
92 * Initialize for a Huffman-compressed scan.
96 start_pass_phuff_decoder (j_decompress_ptr cinfo
)
98 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
99 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
100 boolean is_DC_band
, bad
;
103 jpeg_component_info
* compptr
;
105 is_DC_band
= (cinfo
->Ss
== 0);
107 /* Validate scan parameters */
113 /* need not check Ss/Se < 0 since they came from unsigned bytes */
114 if (cinfo
->Ss
> cinfo
->Se
|| cinfo
->Se
>= DCTSIZE2
)
116 /* AC scans may have only one component */
117 if (cinfo
->comps_in_scan
!= 1)
120 if (cinfo
->Ah
!= 0) {
121 /* Successive approximation refinement scan: must have Al = Ah-1. */
122 if (cinfo
->Al
!= cinfo
->Ah
-1)
125 if (cinfo
->Al
> 13) /* need not check for < 0 */
127 /* Arguably the maximum Al value should be less than 13 for 8-bit precision,
128 * but the spec doesn't say so, and we try to be liberal about what we
129 * accept. Note: large Al values could result in out-of-range DC
130 * coefficients during early scans, leading to bizarre displays due to
131 * overflows in the IDCT math. But we won't crash.
134 ERREXIT4(cinfo
, JERR_BAD_PROGRESSION
,
135 cinfo
->Ss
, cinfo
->Se
, cinfo
->Ah
, cinfo
->Al
);
136 /* Update progression status, and verify that scan order is legal.
137 * Note that inter-scan inconsistencies are treated as warnings
138 * not fatal errors ... not clear if this is right way to behave.
140 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
141 int cindex
= cinfo
->cur_comp_info
[ci
]->component_index
;
142 coef_bit_ptr
= & cinfo
->coef_bits
[cindex
][0];
143 if (!is_DC_band
&& coef_bit_ptr
[0] < 0) /* AC without prior DC scan */
144 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, 0);
145 for (coefi
= cinfo
->Ss
; coefi
<= cinfo
->Se
; coefi
++) {
146 int expected
= (coef_bit_ptr
[coefi
] < 0) ? 0 : coef_bit_ptr
[coefi
];
147 if (cinfo
->Ah
!= expected
)
148 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, coefi
);
149 coef_bit_ptr
[coefi
] = cinfo
->Al
;
153 /* Select MCU decoding routine */
154 if (cinfo
->Ah
== 0) {
156 lossyd
->entropy_decode_mcu
= decode_mcu_DC_first
;
158 lossyd
->entropy_decode_mcu
= decode_mcu_AC_first
;
161 lossyd
->entropy_decode_mcu
= decode_mcu_DC_refine
;
163 lossyd
->entropy_decode_mcu
= decode_mcu_AC_refine
;
166 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
167 compptr
= cinfo
->cur_comp_info
[ci
];
168 /* Make sure requested tables are present, and compute derived tables.
169 * We may build same derived table more than once, but it's not expensive.
172 if (cinfo
->Ah
== 0) { /* DC refinement needs no table */
173 tbl
= compptr
->dc_tbl_no
;
174 jpeg_make_d_derived_tbl(cinfo
, TRUE
, tbl
,
175 & entropy
->derived_tbls
[tbl
]);
178 tbl
= compptr
->ac_tbl_no
;
179 jpeg_make_d_derived_tbl(cinfo
, FALSE
, tbl
,
180 & entropy
->derived_tbls
[tbl
]);
181 /* remember the single active table */
182 entropy
->ac_derived_tbl
= entropy
->derived_tbls
[tbl
];
184 /* Initialize DC predictions to 0 */
185 entropy
->saved
.last_dc_val
[ci
] = 0;
188 /* Initialize bitread state variables */
189 entropy
->bitstate
.bits_left
= 0;
190 entropy
->bitstate
.get_buffer
= 0; /* unnecessary, but keeps Purify quiet */
191 entropy
->insufficient_data
= FALSE
;
193 /* Initialize private state variables */
194 entropy
->saved
.EOBRUN
= 0;
196 /* Initialize restart counter */
197 entropy
->restarts_to_go
= cinfo
->restart_interval
;
202 * Figure F.12: extend sign bit.
203 * On some machines, a shift and add will be faster than a table lookup.
208 #define HUFF_EXTEND(x,s) ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
212 #define HUFF_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
214 static const int extend_test
[16] = /* entry n is 2**(n-1) */
215 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
216 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
218 static const int extend_offset
[16] = /* entry n is (-1 << n) + 1 */
219 { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
220 ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
221 ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
222 ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
224 #endif /* AVOID_TABLES */
228 * Check for a restart marker & resynchronize decoder.
229 * Returns FALSE if must suspend.
233 process_restart (j_decompress_ptr cinfo
)
235 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
236 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
239 /* Throw away any unused bits remaining in bit buffer; */
240 /* include any full bytes in next_marker's count of discarded bytes */
241 cinfo
->marker
->discarded_bytes
+= entropy
->bitstate
.bits_left
/ 8;
242 entropy
->bitstate
.bits_left
= 0;
244 /* Advance past the RSTn marker */
245 if (! (*cinfo
->marker
->read_restart_marker
) (cinfo
))
248 /* Re-initialize DC predictions to 0 */
249 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++)
250 entropy
->saved
.last_dc_val
[ci
] = 0;
251 /* Re-init EOB run count, too */
252 entropy
->saved
.EOBRUN
= 0;
254 /* Reset restart counter */
255 entropy
->restarts_to_go
= cinfo
->restart_interval
;
257 /* Reset out-of-data flag, unless read_restart_marker left us smack up
258 * against a marker. In that case we will end up treating the next data
259 * segment as empty, and we can avoid producing bogus output pixels by
260 * leaving the flag set.
262 if (cinfo
->unread_marker
== 0)
263 entropy
->insufficient_data
= FALSE
;
270 * Huffman MCU decoding.
271 * Each of these routines decodes and returns one MCU's worth of
272 * Huffman-compressed coefficients.
273 * The coefficients are reordered from zigzag order into natural array order,
274 * but are not dequantized.
276 * The i'th block of the MCU is stored into the block pointed to by
277 * MCU_data[i]. WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
279 * We return FALSE if data source requested suspension. In that case no
280 * changes have been made to permanent state. (Exception: some output
281 * coefficients may already have been assigned. This is harmless for
282 * spectral selection, since we'll just re-assign them on the next call.
283 * Successive approximation AC refinement has to be more careful, however.)
287 * MCU decoding for DC initial scan (either spectral selection,
288 * or first pass of successive approximation).
292 decode_mcu_DC_first (j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
294 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
295 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
303 jpeg_component_info
* compptr
;
305 /* Process restart marker if needed; may have to suspend */
306 if (cinfo
->restart_interval
) {
307 if (entropy
->restarts_to_go
== 0)
308 if (! process_restart(cinfo
))
312 /* If we've run out of data, just leave the MCU set to zeroes.
313 * This way, we return uniform gray for the remainder of the segment.
315 if (! entropy
->insufficient_data
) {
317 /* Load up working state */
318 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
319 ASSIGN_STATE(state
, entropy
->saved
);
321 /* Outer loop handles each block in the MCU */
323 for (blkn
= 0; blkn
< cinfo
->data_units_in_MCU
; blkn
++) {
324 block
= MCU_data
[blkn
];
325 ci
= cinfo
->MCU_membership
[blkn
];
326 compptr
= cinfo
->cur_comp_info
[ci
];
327 tbl
= entropy
->derived_tbls
[compptr
->dc_tbl_no
];
329 /* Decode a single block's worth of coefficients */
331 /* Section F.2.2.1: decode the DC coefficient difference */
332 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label1
);
334 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
336 s
= HUFF_EXTEND(r
, s
);
339 /* Convert DC difference to actual value, update last_dc_val */
340 s
+= state
.last_dc_val
[ci
];
341 state
.last_dc_val
[ci
] = s
;
342 /* Scale and output the coefficient (assumes jpeg_natural_order[0]=0) */
343 (*block
)[0] = (JCOEF
) (s
<< Al
);
346 /* Completed MCU, so update state */
347 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
348 ASSIGN_STATE(entropy
->saved
, state
);
351 /* Account for restart interval (no-op if not using restarts) */
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 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
367 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
370 register int s
, k
, r
;
376 /* Process restart marker if needed; may have to suspend */
377 if (cinfo
->restart_interval
) {
378 if (entropy
->restarts_to_go
== 0)
379 if (! process_restart(cinfo
))
383 /* If we've run out of data, just leave the MCU set to zeroes.
384 * This way, we return uniform gray for the remainder of the segment.
386 if (! entropy
->insufficient_data
) {
388 /* Load up working state.
389 * We can avoid loading/saving bitread state if in an EOB run.
391 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
393 /* There is always only one block per MCU */
395 if (EOBRUN
> 0) /* if it's a band of zeroes... */
396 EOBRUN
--; /* ...process it now (we do nothing) */
398 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
400 tbl
= entropy
->ac_derived_tbl
;
402 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
403 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label2
);
408 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
410 s
= HUFF_EXTEND(r
, s
);
411 /* Scale and output coefficient in natural (dezigzagged) order */
412 (*block
)[jpeg_natural_order
[k
]] = (JCOEF
) (s
<< Al
);
414 if (r
== 15) { /* ZRL */
415 k
+= 15; /* skip 15 zeroes in band */
416 } else { /* EOBr, run length is 2^r + appended bits */
418 if (r
) { /* EOBr, r > 0 */
419 CHECK_BIT_BUFFER(br_state
, r
, return FALSE
);
423 EOBRUN
--; /* this band is processed at this moment */
424 break; /* force end-of-band */
429 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
432 /* Completed MCU, so update state */
433 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
436 /* Account for restart interval (no-op if not using restarts) */
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 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
453 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
454 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
459 /* Process restart marker if needed; may have to suspend */
460 if (cinfo
->restart_interval
) {
461 if (entropy
->restarts_to_go
== 0)
462 if (! process_restart(cinfo
))
466 /* Not worth the cycles to check insufficient_data here,
467 * since we will not change the data anyway if we read zeroes.
470 /* Load up working state */
471 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
473 /* Outer loop handles each block in the MCU */
475 for (blkn
= 0; blkn
< cinfo
->data_units_in_MCU
; blkn
++) {
476 block
= MCU_data
[blkn
];
478 /* Encoded data is simply the next bit of the two's-complement DC value */
479 CHECK_BIT_BUFFER(br_state
, 1, return FALSE
);
482 /* Note: since we use |=, repeating the assignment later is safe */
485 /* Completed MCU, so update state */
486 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
488 /* Account for restart interval (no-op if not using restarts) */
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 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
503 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) lossyd
->entropy_private
;
505 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
506 int m1
= (-1) << cinfo
->Al
; /* -1 in the bit position being coded */
507 register int s
, k
, r
;
514 int newnz_pos
[DCTSIZE2
];
516 /* Process restart marker if needed; may have to suspend */
517 if (cinfo
->restart_interval
) {
518 if (entropy
->restarts_to_go
== 0)
519 if (! process_restart(cinfo
))
523 /* If we've run out of data, don't modify the MCU.
525 if (! entropy
->insufficient_data
) {
527 /* Load up working state */
528 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
529 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
531 /* There is always only one block per MCU */
533 tbl
= entropy
->ac_derived_tbl
;
535 /* If we are forced to suspend, we must undo the assignments to any newly
536 * nonzero coefficients in the block, because otherwise we'd get confused
537 * next time about which coefficients were already nonzero.
538 * But we need not undo addition of bits to already-nonzero coefficients;
539 * instead, we can test the current bit to see if we already did it.
543 /* initialize coefficient loop counter to start of band */
547 for (; k
<= Se
; k
++) {
548 HUFF_DECODE(s
, br_state
, tbl
, goto undoit
, label3
);
552 if (s
!= 1) /* size of new coef should always be 1 */
553 WARNMS(cinfo
, JWRN_HUFF_BAD_CODE
);
554 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
556 s
= p1
; /* newly nonzero coef is positive */
558 s
= m1
; /* newly nonzero coef is negative */
561 EOBRUN
= 1 << r
; /* EOBr, run length is 2^r + appended bits */
563 CHECK_BIT_BUFFER(br_state
, r
, goto undoit
);
567 break; /* rest of block is handled by EOB logic */
569 /* note s = 0 for processing ZRL */
571 /* Advance over already-nonzero coefs and r still-zero coefs,
572 * appending correction bits to the nonzeroes. A correction bit is 1
573 * if the absolute value of the coefficient must be increased.
576 thiscoef
= *block
+ jpeg_natural_order
[k
];
577 if (*thiscoef
!= 0) {
578 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
580 if ((*thiscoef
& p1
) == 0) { /* do nothing if already set it */
589 break; /* reached target zero coefficient */
594 int pos
= jpeg_natural_order
[k
];
595 /* Output newly nonzero coefficient */
596 (*block
)[pos
] = (JCOEF
) s
;
597 /* Remember its position in case we have to suspend */
598 newnz_pos
[num_newnz
++] = pos
;
604 /* Scan any remaining coefficient positions after the end-of-band
605 * (the last newly nonzero coefficient, if any). Append a correction
606 * bit to each already-nonzero coefficient. A correction bit is 1
607 * if the absolute value of the coefficient must be increased.
609 for (; k
<= Se
; k
++) {
610 thiscoef
= *block
+ jpeg_natural_order
[k
];
611 if (*thiscoef
!= 0) {
612 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
614 if ((*thiscoef
& p1
) == 0) { /* do nothing if already changed it */
623 /* Count one block completed in EOB run */
627 /* Completed MCU, so update state */
628 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
629 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
632 /* Account for restart interval (no-op if not using restarts) */
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 j_lossy_d_ptr lossyd
= (j_lossy_d_ptr
) cinfo
->codec
;
654 phuff_entropy_ptr entropy
;
658 entropy
= (phuff_entropy_ptr
)
659 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
) cinfo
, JPOOL_IMAGE
,
660 SIZEOF(phuff_entropy_decoder
));
661 lossyd
->entropy_private
= (void *) entropy
;
662 lossyd
->entropy_start_pass
= start_pass_phuff_decoder
;
664 /* Mark derived tables unallocated */
665 for (i
= 0; i
< NUM_HUFF_TBLS
; i
++) {
666 entropy
->derived_tbls
[i
] = NULL
;
669 /* Create progression status table */
670 cinfo
->coef_bits
= (int (*)[DCTSIZE2
])
671 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
) cinfo
, JPOOL_IMAGE
,
672 cinfo
->num_components
*DCTSIZE2
*SIZEOF(int));
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 */