1 /*
2 * jdlhuff.c
3 *
4 * Copyright (C) 1991-1998, Thomas G. Lane.
5 * This file is part of the Independent JPEG Group's software.
6 * For conditions of distribution and use, see the accompanying README file.
7 *
8 * This file contains Huffman entropy decoding routines for lossless JPEG.
9 *
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.
15 */
16
17 #define JPEG_INTERNALS
18 #include "jinclude8.h"
19 #include "jpeglib8.h"
20 #include "jlossls8.h" /* Private declarations for lossless codec */
21 #include "jdhuff8.h" /* Declarations shared with jd*huff.c */
22
23
24 #ifdef D_LOSSLESS_SUPPORTED
25
26 typedef struct {
27 int ci, yoffset, MCU_width;
28 } lhd_output_ptr_info;
29
30 /*
31 * Private entropy decoder object for lossless Huffman decoding.
32 */
33
34 typedef struct {
35 huffd_common_fields; /* Fields shared with other entropy decoders */
36
37 /* Pointers to derived tables (these workspaces have image lifespan) */
38 d_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
39
40 /* Precalculated info set up by start_pass for use in decode_mcus: */
41
42 /* Pointers to derived tables to be used for each data unit within an MCU */
43 d_derived_tbl * cur_tbls[D_MAX_DATA_UNITS_IN_MCU];
44
45 /* Pointers to the proper output difference row for each group of data units
46 * within an MCU. For each component, there are Vi groups of Hi data units.
47 */
48 JDIFFROW output_ptr[D_MAX_DATA_UNITS_IN_MCU];
49
50 /* Number of output pointers in use for the current MCU. This is the sum
51 * of all Vi in the MCU.
52 */
53 int num_output_ptrs;
54
55 /* Information used for positioning the output pointers within the output
56 * difference rows.
57 */
58 lhd_output_ptr_info output_ptr_info[D_MAX_DATA_UNITS_IN_MCU];
59
60 /* Index of the proper output pointer for each data unit within an MCU */
61 int output_ptr_index[D_MAX_DATA_UNITS_IN_MCU];
62
63 } lhuff_entropy_decoder;
64
65 typedef lhuff_entropy_decoder * lhuff_entropy_ptr;
66
67
68 /*
69 * Initialize for a Huffman-compressed scan.
70 */
71
72 METHODDEF(void)
start_pass_lhuff_decoder(j_decompress_ptr cinfo)73 start_pass_lhuff_decoder (j_decompress_ptr cinfo)
74 {
75 j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
76 lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
77 int ci, dctbl, sampn, ptrn, yoffset, xoffset;
78 jpeg_component_info * compptr;
79
80 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
81 compptr = cinfo->cur_comp_info[ci];
82 dctbl = compptr->dc_tbl_no;
83 /* Make sure requested tables are present */
84 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
85 cinfo->dc_huff_tbl_ptrs[dctbl] == NULL)
86 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
87 /* Compute derived values for Huffman tables */
88 /* We may do this more than once for a table, but it's not expensive */
89 jpeg_make_d_derived_tbl(cinfo, TRUE, dctbl,
90 & entropy->derived_tbls[dctbl]);
91 }
92
93 /* Precalculate decoding info for each sample in an MCU of this scan */
94 for (sampn = 0, ptrn = 0; sampn < cinfo->data_units_in_MCU;) {
95 compptr = cinfo->cur_comp_info[cinfo->MCU_membership[sampn]];
96 ci = compptr->component_index;
97 for (yoffset = 0; yoffset < compptr->MCU_height; yoffset++, ptrn++) {
98 /* Precalculate the setup info for each output pointer */
99 entropy->output_ptr_info[ptrn].ci = ci;
100 entropy->output_ptr_info[ptrn].yoffset = yoffset;
101 entropy->output_ptr_info[ptrn].MCU_width = compptr->MCU_width;
102 for (xoffset = 0; xoffset < compptr->MCU_width; xoffset++, sampn++) {
103 /* Precalculate the output pointer index for each sample */
104 entropy->output_ptr_index[sampn] = ptrn;
105 /* Precalculate which table to use for each sample */
106 entropy->cur_tbls[sampn] = entropy->derived_tbls[compptr->dc_tbl_no];
107 }
108 }
109 }
110 entropy->num_output_ptrs = ptrn;
111
112 /* Initialize bitread state variables */
113 entropy->bitstate.bits_left = 0;
114 entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
115 entropy->insufficient_data = FALSE;
116 }
117
118
119 /*
120 * Figure F.12: extend sign bit.
121 * On some machines, a shift and add will be faster than a table lookup.
122 */
123
124 #ifdef AVOID_TABLES
125
126 #define HUFF_EXTEND(x,s) ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
127
128 #else
129
130 #define HUFF_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
131
132 static const int extend_test[16] = /* entry n is 2**(n-1) */
133 { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
134 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
135
136 /*
137 * Originally, a -1 was shifted but since shifting a negative value is
138 * undefined behavior, now "~0U" (bit-wise NOT unsigned int 0) is used,
139 * shifted and casted to an int. The result is the same, of course.
140 */
141 static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
142 { 0, (int)((~0U)<<1) + 1, (int)((~0U)<<2) + 1, (int)((~0U)<<3) + 1, (int)((~0U)<<4) + 1,
143 (int)((~0U)<<5) + 1, (int)((~0U)<<6) + 1, (int)((~0U)<<7) + 1, (int)((~0U)<<8) + 1,
144 (int)((~0U)<<9) + 1, (int)((~0U)<<10) + 1, (int)((~0U)<<11) + 1, (int)((~0U)<<12) + 1,
145 (int)((~0U)<<13) + 1, (int)((~0U)<<14) + 1, (int)((~0U)<<15) + 1 };
146
147 #endif /* AVOID_TABLES */
148
149
150 /*
151 * Check for a restart marker & resynchronize decoder.
152 * Returns FALSE if must suspend.
153 */
154
155 METHODDEF(boolean)
process_restart(j_decompress_ptr cinfo)156 process_restart (j_decompress_ptr cinfo)
157 {
158 j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
159 lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
160 /* int ci; */
161
162 /* Throw away any unused bits remaining in bit buffer; */
163 /* include any full bytes in next_marker's count of discarded bytes */
164 cinfo->marker->discarded_bytes += (unsigned int)entropy->bitstate.bits_left / 8;
165 entropy->bitstate.bits_left = 0;
166
167 /* Advance past the RSTn marker */
168 if (! (*cinfo->marker->read_restart_marker) (cinfo))
169 return FALSE;
170
171 /* Reset out-of-data flag, unless read_restart_marker left us smack up
172 * against a marker. In that case we will end up treating the next data
173 * segment as empty, and we can avoid producing bogus output pixels by
174 * leaving the flag set.
175 */
176 if (cinfo->unread_marker == 0)
177 entropy->insufficient_data = FALSE;
178
179 return TRUE;
180 }
181
182
183 /*
184 * Decode and return nMCU's worth of Huffman-compressed differences.
185 * Each MCU is also disassembled and placed accordingly in diff_buf.
186 *
187 * MCU_col_num specifies the column of the first MCU being requested within
188 * the MCU-row. This tells us where to position the output row pointers in
189 * diff_buf.
190 *
191 * Returns the number of MCUs decoded. This may be less than nMCU if data
192 * source requested suspension. In that case no changes have been made to
193 * permanent state. (Exception: some output differences may already have
194 * been assigned. This is harmless for this module, since we'll just
195 * re-assign them on the next call.)
196 */
197
198 METHODDEF(JDIMENSION)
decode_mcus(j_decompress_ptr cinfo,JDIFFIMAGE diff_buf,JDIMENSION MCU_row_num,JDIMENSION MCU_col_num,JDIMENSION nMCU)199 decode_mcus (j_decompress_ptr cinfo, JDIFFIMAGE diff_buf,
200 JDIMENSION MCU_row_num, JDIMENSION MCU_col_num, JDIMENSION nMCU)
201 {
202 j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
203 lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
204 unsigned int mcu_num;
205 int sampn, ci, yoffset, MCU_width, ptrn;
206 BITREAD_STATE_VARS;
207
208 /* Set output pointer locations based on MCU_col_num */
209 for (ptrn = 0; ptrn < entropy->num_output_ptrs; ptrn++) {
210 ci = entropy->output_ptr_info[ptrn].ci;
211 yoffset = entropy->output_ptr_info[ptrn].yoffset;
212 MCU_width = entropy->output_ptr_info[ptrn].MCU_width;
213 entropy->output_ptr[ptrn] =
214 diff_buf[ci][MCU_row_num + (JDIMENSION)yoffset] + MCU_col_num * (JDIMENSION)MCU_width;
215 }
216
217 /*
218 * If we've run out of data, zero out the buffers and return.
219 * By resetting the undifferencer, the output samples will be CENTERJSAMPLE.
220 *
221 * NB: We should find a way to do this without interacting with the
222 * undifferencer module directly.
223 */
224 if (entropy->insufficient_data) {
225 for (ptrn = 0; ptrn < entropy->num_output_ptrs; ptrn++)
226 jzero_far((void FAR *) entropy->output_ptr[ptrn],
227 nMCU * (size_t)entropy->output_ptr_info[ptrn].MCU_width * SIZEOF(JDIFF));
228
229 (*losslsd->predict_process_restart) (cinfo);
230 }
231
232 else {
233
234 /* Load up working state */
235 BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
236
237 /* Outer loop handles the number of MCU requested */
238
239 for (mcu_num = 0; mcu_num < nMCU; mcu_num++) {
240
241 /* Inner loop handles the samples in the MCU */
242 for (sampn = 0; sampn < cinfo->data_units_in_MCU; sampn++) {
243 d_derived_tbl * dctbl = entropy->cur_tbls[sampn];
244 register int s, r;
245
246 /* Section H.2.2: decode the sample difference */
247 HUFF_DECODE(s, br_state, dctbl, return mcu_num, label1);
248 if (s) {
249 if (s == 16) /* special case: always output 32768 */
250 s = 32768;
251 else { /* normal case: fetch subsequent bits */
252 CHECK_BIT_BUFFER(br_state, s, return mcu_num);
253 r = GET_BITS(s);
254 s = HUFF_EXTEND(r, s);
255 }
256 }
257
258 /* Output the sample difference */
259 *entropy->output_ptr[entropy->output_ptr_index[sampn]]++ = (JDIFF) s;
260 }
261
262 /* Completed MCU, so update state */
263 BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
264 }
265 }
266
267 return nMCU;
268 }
269
270
271 /*
272 * Module initialization routine for lossless Huffman entropy decoding.
273 */
274
275 GLOBAL(void)
jinit_lhuff_decoder(j_decompress_ptr cinfo)276 jinit_lhuff_decoder (j_decompress_ptr cinfo)
277 {
278 j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
279 lhuff_entropy_ptr entropy;
280 int i;
281
282 entropy = (lhuff_entropy_ptr)
283 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
284 SIZEOF(lhuff_entropy_decoder));
285 losslsd->entropy_private = (void *) entropy;
286 losslsd->entropy_start_pass = start_pass_lhuff_decoder;
287 losslsd->entropy_process_restart = process_restart;
288 losslsd->entropy_decode_mcus = decode_mcus;
289
290 /* Mark tables unallocated */
291 for (i = 0; i < NUM_HUFF_TBLS; i++) {
292 entropy->derived_tbls[i] = NULL;
293 }
294 }
295
296 #endif /* D_LOSSLESS_SUPPORTED */
297