4 * Copyright (C) 1995-1997, 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.
8 * This file contains Huffman entropy decoding routines for progressive JPEG.
10 * Much of the complexity here has to do with supporting input suspension.
11 * If the data source module demands suspension, we want to be able to back
12 * up to the start of the current MCU. To do this, we copy state variables
13 * into local working storage, and update them back to the permanent
14 * storage only upon successful completion of an MCU.
17 #define JPEG_INTERNALS
20 #include "jdhuff.h" /* Declarations shared with jdhuff.c */
23 #ifdef D_PROGRESSIVE_SUPPORTED
26 * Expanded entropy decoder object for progressive Huffman decoding.
28 * The savable_state subrecord contains fields that change within an MCU,
29 * but must not be updated permanently until we complete the MCU.
33 unsigned int EOBRUN
; /* remaining EOBs in EOBRUN */
34 int last_dc_val
[MAX_COMPS_IN_SCAN
]; /* last DC coef for each component */
37 /* This macro is to work around compilers with missing or broken
38 * structure assignment. You'll need to fix this code if you have
39 * such a compiler and you change MAX_COMPS_IN_SCAN.
42 #ifndef NO_STRUCT_ASSIGN
43 #define ASSIGN_STATE(dest,src) ((dest) = (src))
45 #if MAX_COMPS_IN_SCAN == 4
46 #define ASSIGN_STATE(dest,src) \
47 ((dest).EOBRUN = (src).EOBRUN, \
48 (dest).last_dc_val[0] = (src).last_dc_val[0], \
49 (dest).last_dc_val[1] = (src).last_dc_val[1], \
50 (dest).last_dc_val[2] = (src).last_dc_val[2], \
51 (dest).last_dc_val[3] = (src).last_dc_val[3])
57 struct jpeg_entropy_decoder pub
; /* public fields */
59 /* These fields are loaded into local variables at start of each MCU.
60 * In case of suspension, we exit WITHOUT updating them.
62 bitread_perm_state bitstate
; /* Bit buffer at start of MCU */
63 savable_state saved
; /* Other state at start of MCU */
65 /* These fields are NOT loaded into local working state. */
66 unsigned int restarts_to_go
; /* MCUs left in this restart interval */
68 /* Pointers to derived tables (these workspaces have image lifespan) */
69 d_derived_tbl
* derived_tbls
[NUM_HUFF_TBLS
];
71 d_derived_tbl
* ac_derived_tbl
; /* active table during an AC scan */
72 } phuff_entropy_decoder
;
74 typedef phuff_entropy_decoder
* phuff_entropy_ptr
;
76 /* Forward declarations */
77 METHODDEF(boolean
) decode_mcu_DC_first
JPP((j_decompress_ptr cinfo
,
78 JBLOCKROW
*MCU_data
));
79 METHODDEF(boolean
) decode_mcu_AC_first
JPP((j_decompress_ptr cinfo
,
80 JBLOCKROW
*MCU_data
));
81 METHODDEF(boolean
) decode_mcu_DC_refine
JPP((j_decompress_ptr cinfo
,
82 JBLOCKROW
*MCU_data
));
83 METHODDEF(boolean
) decode_mcu_AC_refine
JPP((j_decompress_ptr cinfo
,
84 JBLOCKROW
*MCU_data
));
88 * Initialize for a Huffman-compressed scan.
92 start_pass_phuff_decoder (j_decompress_ptr cinfo
)
94 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
95 boolean is_DC_band
, bad
;
98 jpeg_component_info
* compptr
;
100 is_DC_band
= (cinfo
->Ss
== 0);
102 /* Validate scan parameters */
108 /* need not check Ss/Se < 0 since they came from unsigned bytes */
109 if (cinfo
->Ss
> cinfo
->Se
|| cinfo
->Se
>= DCTSIZE2
)
111 /* AC scans may have only one component */
112 if (cinfo
->comps_in_scan
!= 1)
115 if (cinfo
->Ah
!= 0) {
116 /* Successive approximation refinement scan: must have Al = Ah-1. */
117 if (cinfo
->Al
!= cinfo
->Ah
-1)
120 if (cinfo
->Al
> 13) /* need not check for < 0 */
122 /* Arguably the maximum Al value should be less than 13 for 8-bit precision,
123 * but the spec doesn't say so, and we try to be liberal about what we
124 * accept. Note: large Al values could result in out-of-range DC
125 * coefficients during early scans, leading to bizarre displays due to
126 * overflows in the IDCT math. But we won't crash.
129 ERREXIT4(cinfo
, JERR_BAD_PROGRESSION
,
130 cinfo
->Ss
, cinfo
->Se
, cinfo
->Ah
, cinfo
->Al
);
131 /* Update progression status, and verify that scan order is legal.
132 * Note that inter-scan inconsistencies are treated as warnings
133 * not fatal errors ... not clear if this is right way to behave.
135 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
136 int cindex
= cinfo
->cur_comp_info
[ci
]->component_index
;
137 coef_bit_ptr
= & cinfo
->coef_bits
[cindex
][0];
138 if (!is_DC_band
&& coef_bit_ptr
[0] < 0) /* AC without prior DC scan */
139 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, 0);
140 for (coefi
= cinfo
->Ss
; coefi
<= cinfo
->Se
; coefi
++) {
141 int expected
= (coef_bit_ptr
[coefi
] < 0) ? 0 : coef_bit_ptr
[coefi
];
142 if (cinfo
->Ah
!= expected
)
143 WARNMS2(cinfo
, JWRN_BOGUS_PROGRESSION
, cindex
, coefi
);
144 coef_bit_ptr
[coefi
] = cinfo
->Al
;
148 /* Select MCU decoding routine */
149 if (cinfo
->Ah
== 0) {
151 entropy
->pub
.decode_mcu
= decode_mcu_DC_first
;
153 entropy
->pub
.decode_mcu
= decode_mcu_AC_first
;
156 entropy
->pub
.decode_mcu
= decode_mcu_DC_refine
;
158 entropy
->pub
.decode_mcu
= decode_mcu_AC_refine
;
161 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
162 compptr
= cinfo
->cur_comp_info
[ci
];
163 /* Make sure requested tables are present, and compute derived tables.
164 * We may build same derived table more than once, but it's not expensive.
167 if (cinfo
->Ah
== 0) { /* DC refinement needs no table */
168 tbl
= compptr
->dc_tbl_no
;
169 jpeg_make_d_derived_tbl(cinfo
, TRUE
, tbl
,
170 & entropy
->derived_tbls
[tbl
]);
173 tbl
= compptr
->ac_tbl_no
;
174 jpeg_make_d_derived_tbl(cinfo
, FALSE
, tbl
,
175 & entropy
->derived_tbls
[tbl
]);
176 /* remember the single active table */
177 entropy
->ac_derived_tbl
= entropy
->derived_tbls
[tbl
];
179 /* Initialize DC predictions to 0 */
180 entropy
->saved
.last_dc_val
[ci
] = 0;
183 /* Initialize bitread state variables */
184 entropy
->bitstate
.bits_left
= 0;
185 entropy
->bitstate
.get_buffer
= 0; /* unnecessary, but keeps Purify quiet */
186 entropy
->pub
.insufficient_data
= FALSE
;
188 /* Initialize private state variables */
189 entropy
->saved
.EOBRUN
= 0;
191 /* Initialize restart counter */
192 entropy
->restarts_to_go
= cinfo
->restart_interval
;
197 * Figure F.12: extend sign bit.
198 * On some machines, a shift and add will be faster than a table lookup.
204 #define HUFF_EXTEND(x,s) ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
208 #define HUFF_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
210 static const int extend_test
[16] = /* entry n is 2**(n-1) */
211 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
212 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 };
220 #endif /* AVOID_TABLES */
224 * Check for a restart marker & resynchronize decoder.
225 * Returns FALSE if must suspend.
229 process_restart (j_decompress_ptr cinfo
)
231 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
234 /* Throw away any unused bits remaining in bit buffer; */
235 /* include any full bytes in next_marker's count of discarded bytes */
236 cinfo
->marker
->discarded_bytes
+= entropy
->bitstate
.bits_left
/ 8;
237 entropy
->bitstate
.bits_left
= 0;
239 /* Advance past the RSTn marker */
240 if (! (*cinfo
->marker
->read_restart_marker
) (cinfo
))
243 /* Re-initialize DC predictions to 0 */
244 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++)
245 entropy
->saved
.last_dc_val
[ci
] = 0;
246 /* Re-init EOB run count, too */
247 entropy
->saved
.EOBRUN
= 0;
249 /* Reset restart counter */
250 entropy
->restarts_to_go
= cinfo
->restart_interval
;
252 /* Reset out-of-data flag, unless read_restart_marker left us smack up
253 * against a marker. In that case we will end up treating the next data
254 * segment as empty, and we can avoid producing bogus output pixels by
255 * leaving the flag set.
257 if (cinfo
->unread_marker
== 0)
258 entropy
->pub
.insufficient_data
= FALSE
;
265 * Huffman MCU decoding.
266 * Each of these routines decodes and returns one MCU's worth of
267 * Huffman-compressed coefficients.
268 * The coefficients are reordered from zigzag order into natural array order,
269 * but are not dequantized.
271 * The i'th block of the MCU is stored into the block pointed to by
272 * MCU_data[i]. WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
274 * We return FALSE if data source requested suspension. In that case no
275 * changes have been made to permanent state. (Exception: some output
276 * coefficients may already have been assigned. This is harmless for
277 * spectral selection, since we'll just re-assign them on the next call.
278 * Successive approximation AC refinement has to be more careful, however.)
282 * MCU decoding for DC initial scan (either spectral selection,
283 * or first pass of successive approximation).
287 decode_mcu_DC_first (j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
289 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
297 jpeg_component_info
* compptr
;
299 /* Process restart marker if needed; may have to suspend */
300 if (cinfo
->restart_interval
) {
301 if (entropy
->restarts_to_go
== 0)
302 if (! process_restart(cinfo
))
306 /* If we've run out of data, just leave the MCU set to zeroes.
307 * This way, we return uniform gray for the remainder of the segment.
309 if (! entropy
->pub
.insufficient_data
) {
311 /* Load up working state */
312 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
313 ASSIGN_STATE(state
, entropy
->saved
);
315 /* Outer loop handles each block in the MCU */
317 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
318 block
= MCU_data
[blkn
];
319 ci
= cinfo
->MCU_membership
[blkn
];
320 compptr
= cinfo
->cur_comp_info
[ci
];
321 tbl
= entropy
->derived_tbls
[compptr
->dc_tbl_no
];
323 /* Decode a single block's worth of coefficients */
325 /* Section F.2.2.1: decode the DC coefficient difference */
326 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label1
);
328 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
330 s
= HUFF_EXTEND(r
, s
);
333 /* Convert DC difference to actual value, update last_dc_val */
334 s
+= state
.last_dc_val
[ci
];
335 state
.last_dc_val
[ci
] = s
;
336 /* Scale and output the coefficient (assumes jpeg_natural_order[0]=0) */
337 (*block
)[0] = (JCOEF
) (s
<< Al
);
340 /* Completed MCU, so update state */
341 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
342 ASSIGN_STATE(entropy
->saved
, state
);
345 /* Account for restart interval (no-op if not using restarts) */
346 entropy
->restarts_to_go
--;
353 * MCU decoding for AC initial scan (either spectral selection,
354 * or first pass of successive approximation).
358 decode_mcu_AC_first (j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
360 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
363 register int s
, k
, r
;
369 /* Process restart marker if needed; may have to suspend */
370 if (cinfo
->restart_interval
) {
371 if (entropy
->restarts_to_go
== 0)
372 if (! process_restart(cinfo
))
376 /* If we've run out of data, just leave the MCU set to zeroes.
377 * This way, we return uniform gray for the remainder of the segment.
379 if (! entropy
->pub
.insufficient_data
) {
381 /* Load up working state.
382 * We can avoid loading/saving bitread state if in an EOB run.
384 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
386 /* There is always only one block per MCU */
388 if (EOBRUN
> 0) /* if it's a band of zeroes... */
389 EOBRUN
--; /* ...process it now (we do nothing) */
391 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
393 tbl
= entropy
->ac_derived_tbl
;
395 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
396 HUFF_DECODE(s
, br_state
, tbl
, return FALSE
, label2
);
401 CHECK_BIT_BUFFER(br_state
, s
, return FALSE
);
403 s
= HUFF_EXTEND(r
, s
);
404 /* Scale and output coefficient in natural (dezigzagged) order */
405 (*block
)[jpeg_natural_order
[k
]] = (JCOEF
) (s
<< Al
);
407 if (r
== 15) { /* ZRL */
408 k
+= 15; /* skip 15 zeroes in band */
409 } else { /* EOBr, run length is 2^r + appended bits */
411 if (r
) { /* EOBr, r > 0 */
412 CHECK_BIT_BUFFER(br_state
, r
, return FALSE
);
416 EOBRUN
--; /* this band is processed at this moment */
417 break; /* force end-of-band */
422 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
425 /* Completed MCU, so update state */
426 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
429 /* Account for restart interval (no-op if not using restarts) */
430 entropy
->restarts_to_go
--;
437 * MCU decoding for DC successive approximation refinement scan.
438 * Note: we assume such scans can be multi-component, although the spec
439 * is not very clear on the point.
443 decode_mcu_DC_refine (j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
445 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
446 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
451 /* Process restart marker if needed; may have to suspend */
452 if (cinfo
->restart_interval
) {
453 if (entropy
->restarts_to_go
== 0)
454 if (! process_restart(cinfo
))
458 /* Not worth the cycles to check insufficient_data here,
459 * since we will not change the data anyway if we read zeroes.
462 /* Load up working state */
463 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
465 /* Outer loop handles each block in the MCU */
467 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
468 block
= MCU_data
[blkn
];
470 /* Encoded data is simply the next bit of the two's-complement DC value */
471 CHECK_BIT_BUFFER(br_state
, 1, return FALSE
);
474 /* Note: since we use |=, repeating the assignment later is safe */
477 /* Completed MCU, so update state */
478 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
480 /* Account for restart interval (no-op if not using restarts) */
481 entropy
->restarts_to_go
--;
488 * MCU decoding for AC successive approximation refinement scan.
492 decode_mcu_AC_refine (j_decompress_ptr cinfo
, JBLOCKROW
*MCU_data
)
494 phuff_entropy_ptr entropy
= (phuff_entropy_ptr
) cinfo
->entropy
;
496 int p1
= 1 << cinfo
->Al
; /* 1 in the bit position being coded */
497 int m1
= (-1) << cinfo
->Al
; /* -1 in the bit position being coded */
498 register int s
, k
, r
;
505 int newnz_pos
[DCTSIZE2
];
507 /* Process restart marker if needed; may have to suspend */
508 if (cinfo
->restart_interval
) {
509 if (entropy
->restarts_to_go
== 0)
510 if (! process_restart(cinfo
))
514 /* If we've run out of data, don't modify the MCU.
516 if (! entropy
->pub
.insufficient_data
) {
518 /* Load up working state */
519 BITREAD_LOAD_STATE(cinfo
,entropy
->bitstate
);
520 EOBRUN
= entropy
->saved
.EOBRUN
; /* only part of saved state we need */
522 /* There is always only one block per MCU */
524 tbl
= entropy
->ac_derived_tbl
;
526 /* If we are forced to suspend, we must undo the assignments to any newly
527 * nonzero coefficients in the block, because otherwise we'd get confused
528 * next time about which coefficients were already nonzero.
529 * But we need not undo addition of bits to already-nonzero coefficients;
530 * instead, we can test the current bit to see if we already did it.
534 /* initialize coefficient loop counter to start of band */
538 for (; k
<= Se
; k
++) {
539 HUFF_DECODE(s
, br_state
, tbl
, goto undoit
, label3
);
543 if (s
!= 1) /* size of new coef should always be 1 */
544 WARNMS(cinfo
, JWRN_HUFF_BAD_CODE
);
545 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
547 s
= p1
; /* newly nonzero coef is positive */
549 s
= m1
; /* newly nonzero coef is negative */
552 EOBRUN
= 1 << r
; /* EOBr, run length is 2^r + appended bits */
554 CHECK_BIT_BUFFER(br_state
, r
, goto undoit
);
558 break; /* rest of block is handled by EOB logic */
560 /* note s = 0 for processing ZRL */
562 /* Advance over already-nonzero coefs and r still-zero coefs,
563 * appending correction bits to the nonzeroes. A correction bit is 1
564 * if the absolute value of the coefficient must be increased.
567 thiscoef
= *block
+ jpeg_natural_order
[k
];
568 if (*thiscoef
!= 0) {
569 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
571 if ((*thiscoef
& p1
) == 0) { /* do nothing if already set it */
580 break; /* reached target zero coefficient */
585 int pos
= jpeg_natural_order
[k
];
586 /* Output newly nonzero coefficient */
587 (*block
)[pos
] = (JCOEF
) s
;
588 /* Remember its position in case we have to suspend */
589 newnz_pos
[num_newnz
++] = pos
;
595 /* Scan any remaining coefficient positions after the end-of-band
596 * (the last newly nonzero coefficient, if any). Append a correction
597 * bit to each already-nonzero coefficient. A correction bit is 1
598 * if the absolute value of the coefficient must be increased.
600 for (; k
<= Se
; k
++) {
601 thiscoef
= *block
+ jpeg_natural_order
[k
];
602 if (*thiscoef
!= 0) {
603 CHECK_BIT_BUFFER(br_state
, 1, goto undoit
);
605 if ((*thiscoef
& p1
) == 0) { /* do nothing if already changed it */
614 /* Count one block completed in EOB run */
618 /* Completed MCU, so update state */
619 BITREAD_SAVE_STATE(cinfo
,entropy
->bitstate
);
620 entropy
->saved
.EOBRUN
= EOBRUN
; /* only part of saved state we need */
623 /* Account for restart interval (no-op if not using restarts) */
624 entropy
->restarts_to_go
--;
629 /* Re-zero any output coefficients that we made newly nonzero */
630 while (num_newnz
> 0)
631 (*block
)[newnz_pos
[--num_newnz
]] = 0;
638 * Module initialization routine for progressive Huffman entropy decoding.
642 jinit_phuff_decoder (j_decompress_ptr cinfo
)
644 phuff_entropy_ptr entropy
;
648 entropy
= (phuff_entropy_ptr
)
649 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
) cinfo
, JPOOL_IMAGE
,
650 SIZEOF(phuff_entropy_decoder
));
651 cinfo
->entropy
= (struct jpeg_entropy_decoder
*) entropy
;
652 entropy
->pub
.start_pass
= start_pass_phuff_decoder
;
654 /* Mark derived tables unallocated */
655 for (i
= 0; i
< NUM_HUFF_TBLS
; i
++) {
656 entropy
->derived_tbls
[i
] = NULL
;
659 /* Create progression status table */
660 cinfo
->coef_bits
= (int (*)[DCTSIZE2
])
661 (*cinfo
->mem
->alloc_small
) ((j_common_ptr
) cinfo
, JPOOL_IMAGE
,
662 cinfo
->num_components
*DCTSIZE2
*SIZEOF(int));
663 coef_bit_ptr
= & cinfo
->coef_bits
[0][0];
664 for (ci
= 0; ci
< cinfo
->num_components
; ci
++)
665 for (i
= 0; i
< DCTSIZE2
; i
++)
666 *coef_bit_ptr
++ = -1;
669 #endif /* D_PROGRESSIVE_SUPPORTED */