|
1 /* |
|
2 * jchuff.c |
|
3 * |
|
4 * Copyright (C) 1991-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. |
|
7 * |
|
8 * This file contains Huffman entropy encoding routines. |
|
9 * |
|
10 * Much of the complexity here has to do with supporting output suspension. |
|
11 * If the data destination module demands suspension, we want to be able to |
|
12 * back up to the start of the current MCU. To do this, we copy state |
|
13 * variables into local working storage, and update them back to the |
|
14 * permanent JPEG objects only upon successful completion of an MCU. |
|
15 */ |
|
16 |
|
17 #define JPEG_INTERNALS |
|
18 #include "jinclude.h" |
|
19 #include "jpeglib.h" |
|
20 #include "jchuff.h" /* Declarations shared with jcphuff.c */ |
|
21 |
|
22 |
|
23 /* Expanded entropy encoder object for Huffman encoding. |
|
24 * |
|
25 * The savable_state subrecord contains fields that change within an MCU, |
|
26 * but must not be updated permanently until we complete the MCU. |
|
27 */ |
|
28 |
|
29 typedef struct { |
|
30 INT32 put_buffer; /* current bit-accumulation buffer */ |
|
31 int put_bits; /* # of bits now in it */ |
|
32 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ |
|
33 } savable_state; |
|
34 |
|
35 /* This macro is to work around compilers with missing or broken |
|
36 * structure assignment. You'll need to fix this code if you have |
|
37 * such a compiler and you change MAX_COMPS_IN_SCAN. |
|
38 */ |
|
39 |
|
40 #ifndef NO_STRUCT_ASSIGN |
|
41 #define ASSIGN_STATE(dest,src) ((dest) = (src)) |
|
42 #else |
|
43 #if MAX_COMPS_IN_SCAN == 4 |
|
44 #define ASSIGN_STATE(dest,src) \ |
|
45 ((dest).put_buffer = (src).put_buffer, \ |
|
46 (dest).put_bits = (src).put_bits, \ |
|
47 (dest).last_dc_val[0] = (src).last_dc_val[0], \ |
|
48 (dest).last_dc_val[1] = (src).last_dc_val[1], \ |
|
49 (dest).last_dc_val[2] = (src).last_dc_val[2], \ |
|
50 (dest).last_dc_val[3] = (src).last_dc_val[3]) |
|
51 #endif |
|
52 #endif |
|
53 |
|
54 |
|
55 typedef struct { |
|
56 struct jpeg_entropy_encoder pub; /* public fields */ |
|
57 |
|
58 savable_state saved; /* Bit buffer & DC state at start of MCU */ |
|
59 |
|
60 /* These fields are NOT loaded into local working state. */ |
|
61 unsigned int restarts_to_go; /* MCUs left in this restart interval */ |
|
62 int next_restart_num; /* next restart number to write (0-7) */ |
|
63 |
|
64 /* Pointers to derived tables (these workspaces have image lifespan) */ |
|
65 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]; |
|
66 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]; |
|
67 |
|
68 #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */ |
|
69 long * dc_count_ptrs[NUM_HUFF_TBLS]; |
|
70 long * ac_count_ptrs[NUM_HUFF_TBLS]; |
|
71 #endif |
|
72 } huff_entropy_encoder; |
|
73 |
|
74 typedef huff_entropy_encoder * huff_entropy_ptr; |
|
75 |
|
76 /* Working state while writing an MCU. |
|
77 * This struct contains all the fields that are needed by subroutines. |
|
78 */ |
|
79 |
|
80 typedef struct { |
|
81 JOCTET * next_output_byte; /* => next byte to write in buffer */ |
|
82 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ |
|
83 savable_state cur; /* Current bit buffer & DC state */ |
|
84 j_compress_ptr cinfo; /* dump_buffer needs access to this */ |
|
85 } working_state; |
|
86 |
|
87 |
|
88 /* Forward declarations */ |
|
89 METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo, |
|
90 JBLOCKROW *MCU_data)); |
|
91 METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo)); |
|
92 #ifdef ENTROPY_OPT_SUPPORTED |
|
93 METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo, |
|
94 JBLOCKROW *MCU_data)); |
|
95 METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo)); |
|
96 #endif |
|
97 |
|
98 |
|
99 /* |
|
100 * Initialize for a Huffman-compressed scan. |
|
101 * If gather_statistics is TRUE, we do not output anything during the scan, |
|
102 * just count the Huffman symbols used and generate Huffman code tables. |
|
103 */ |
|
104 |
|
105 METHODDEF(void) |
|
106 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) |
|
107 { |
|
108 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; |
|
109 int ci, dctbl, actbl; |
|
110 jpeg_component_info * compptr; |
|
111 |
|
112 if (gather_statistics) { |
|
113 #ifdef ENTROPY_OPT_SUPPORTED |
|
114 entropy->pub.encode_mcu = encode_mcu_gather; |
|
115 entropy->pub.finish_pass = finish_pass_gather; |
|
116 #else |
|
117 ERREXIT(cinfo, JERR_NOT_COMPILED); |
|
118 #endif |
|
119 } else { |
|
120 entropy->pub.encode_mcu = encode_mcu_huff; |
|
121 entropy->pub.finish_pass = finish_pass_huff; |
|
122 } |
|
123 |
|
124 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { |
|
125 compptr = cinfo->cur_comp_info[ci]; |
|
126 dctbl = compptr->dc_tbl_no; |
|
127 actbl = compptr->ac_tbl_no; |
|
128 if (gather_statistics) { |
|
129 #ifdef ENTROPY_OPT_SUPPORTED |
|
130 /* Check for invalid table indexes */ |
|
131 /* (make_c_derived_tbl does this in the other path) */ |
|
132 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS) |
|
133 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl); |
|
134 if (actbl < 0 || actbl >= NUM_HUFF_TBLS) |
|
135 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl); |
|
136 /* Allocate and zero the statistics tables */ |
|
137 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ |
|
138 if (entropy->dc_count_ptrs[dctbl] == NULL) |
|
139 entropy->dc_count_ptrs[dctbl] = (long *) |
|
140 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, |
|
141 257 * SIZEOF(long)); |
|
142 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long)); |
|
143 if (entropy->ac_count_ptrs[actbl] == NULL) |
|
144 entropy->ac_count_ptrs[actbl] = (long *) |
|
145 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, |
|
146 257 * SIZEOF(long)); |
|
147 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long)); |
|
148 #endif |
|
149 } else { |
|
150 /* Compute derived values for Huffman tables */ |
|
151 /* We may do this more than once for a table, but it's not expensive */ |
|
152 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl, |
|
153 & entropy->dc_derived_tbls[dctbl]); |
|
154 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl, |
|
155 & entropy->ac_derived_tbls[actbl]); |
|
156 } |
|
157 /* Initialize DC predictions to 0 */ |
|
158 entropy->saved.last_dc_val[ci] = 0; |
|
159 } |
|
160 |
|
161 /* Initialize bit buffer to empty */ |
|
162 entropy->saved.put_buffer = 0; |
|
163 entropy->saved.put_bits = 0; |
|
164 |
|
165 /* Initialize restart stuff */ |
|
166 entropy->restarts_to_go = cinfo->restart_interval; |
|
167 entropy->next_restart_num = 0; |
|
168 } |
|
169 |
|
170 |
|
171 /* |
|
172 * Compute the derived values for a Huffman table. |
|
173 * This routine also performs some validation checks on the table. |
|
174 * |
|
175 * Note this is also used by jcphuff.c. |
|
176 */ |
|
177 |
|
178 GLOBAL(void) |
|
179 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno, |
|
180 c_derived_tbl ** pdtbl) |
|
181 { |
|
182 JHUFF_TBL *htbl; |
|
183 c_derived_tbl *dtbl; |
|
184 int p, i, l, lastp, si, maxsymbol; |
|
185 char huffsize[257]; |
|
186 unsigned int huffcode[257]; |
|
187 unsigned int code; |
|
188 |
|
189 /* Note that huffsize[] and huffcode[] are filled in code-length order, |
|
190 * paralleling the order of the symbols themselves in htbl->huffval[]. |
|
191 */ |
|
192 |
|
193 /* Find the input Huffman table */ |
|
194 if (tblno < 0 || tblno >= NUM_HUFF_TBLS) |
|
195 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); |
|
196 htbl = |
|
197 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno]; |
|
198 if (htbl == NULL) |
|
199 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); |
|
200 |
|
201 /* Allocate a workspace if we haven't already done so. */ |
|
202 if (*pdtbl == NULL) |
|
203 *pdtbl = (c_derived_tbl *) |
|
204 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, |
|
205 SIZEOF(c_derived_tbl)); |
|
206 dtbl = *pdtbl; |
|
207 |
|
208 /* Figure C.1: make table of Huffman code length for each symbol */ |
|
209 |
|
210 p = 0; |
|
211 for (l = 1; l <= 16; l++) { |
|
212 i = (int) htbl->bits[l]; |
|
213 if (i < 0 || p + i > 256) /* protect against table overrun */ |
|
214 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); |
|
215 while (i--) |
|
216 huffsize[p++] = (char) l; |
|
217 } |
|
218 huffsize[p] = 0; |
|
219 lastp = p; |
|
220 |
|
221 /* Figure C.2: generate the codes themselves */ |
|
222 /* We also validate that the counts represent a legal Huffman code tree. */ |
|
223 |
|
224 code = 0; |
|
225 si = huffsize[0]; |
|
226 p = 0; |
|
227 while (huffsize[p]) { |
|
228 while (((int) huffsize[p]) == si) { |
|
229 huffcode[p++] = code; |
|
230 code++; |
|
231 } |
|
232 /* code is now 1 more than the last code used for codelength si; but |
|
233 * it must still fit in si bits, since no code is allowed to be all ones. |
|
234 */ |
|
235 if (((INT32) code) >= (((INT32) 1) << si)) |
|
236 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); |
|
237 code <<= 1; |
|
238 si++; |
|
239 } |
|
240 |
|
241 /* Figure C.3: generate encoding tables */ |
|
242 /* These are code and size indexed by symbol value */ |
|
243 |
|
244 /* Set all codeless symbols to have code length 0; |
|
245 * this lets us detect duplicate VAL entries here, and later |
|
246 * allows emit_bits to detect any attempt to emit such symbols. |
|
247 */ |
|
248 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi)); |
|
249 |
|
250 /* This is also a convenient place to check for out-of-range |
|
251 * and duplicated VAL entries. We allow 0..255 for AC symbols |
|
252 * but only 0..15 for DC. (We could constrain them further |
|
253 * based on data depth and mode, but this seems enough.) |
|
254 */ |
|
255 maxsymbol = isDC ? 15 : 255; |
|
256 |
|
257 for (p = 0; p < lastp; p++) { |
|
258 i = htbl->huffval[p]; |
|
259 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) |
|
260 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); |
|
261 dtbl->ehufco[i] = huffcode[p]; |
|
262 dtbl->ehufsi[i] = huffsize[p]; |
|
263 } |
|
264 } |
|
265 |
|
266 |
|
267 /* Outputting bytes to the file */ |
|
268 |
|
269 /* Emit a byte, taking 'action' if must suspend. */ |
|
270 #define emit_byte(state,val,action) \ |
|
271 { *(state)->next_output_byte++ = (JOCTET) (val); \ |
|
272 if (--(state)->free_in_buffer == 0) \ |
|
273 if (! dump_buffer(state)) \ |
|
274 { action; } } |
|
275 |
|
276 |
|
277 LOCAL(boolean) |
|
278 dump_buffer (working_state * state) |
|
279 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ |
|
280 { |
|
281 struct jpeg_destination_mgr * dest = state->cinfo->dest; |
|
282 |
|
283 if (! (*dest->empty_output_buffer) (state->cinfo)) |
|
284 return FALSE; |
|
285 /* After a successful buffer dump, must reset buffer pointers */ |
|
286 state->next_output_byte = dest->next_output_byte; |
|
287 state->free_in_buffer = dest->free_in_buffer; |
|
288 return TRUE; |
|
289 } |
|
290 |
|
291 |
|
292 /* Outputting bits to the file */ |
|
293 |
|
294 /* Only the right 24 bits of put_buffer are used; the valid bits are |
|
295 * left-justified in this part. At most 16 bits can be passed to emit_bits |
|
296 * in one call, and we never retain more than 7 bits in put_buffer |
|
297 * between calls, so 24 bits are sufficient. |
|
298 */ |
|
299 |
|
300 INLINE |
|
301 LOCAL(boolean) |
|
302 emit_bits (working_state * state, unsigned int code, int size) |
|
303 /* Emit some bits; return TRUE if successful, FALSE if must suspend */ |
|
304 { |
|
305 /* This routine is heavily used, so it's worth coding tightly. */ |
|
306 register INT32 put_buffer = (INT32) code; |
|
307 register int put_bits = state->cur.put_bits; |
|
308 |
|
309 /* if size is 0, caller used an invalid Huffman table entry */ |
|
310 if (size == 0) |
|
311 ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE); |
|
312 |
|
313 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */ |
|
314 |
|
315 put_bits += size; /* new number of bits in buffer */ |
|
316 |
|
317 put_buffer <<= 24 - put_bits; /* align incoming bits */ |
|
318 |
|
319 put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */ |
|
320 |
|
321 while (put_bits >= 8) { |
|
322 int c = (int) ((put_buffer >> 16) & 0xFF); |
|
323 |
|
324 emit_byte(state, c, return FALSE); |
|
325 if (c == 0xFF) { /* need to stuff a zero byte? */ |
|
326 emit_byte(state, 0, return FALSE); |
|
327 } |
|
328 put_buffer <<= 8; |
|
329 put_bits -= 8; |
|
330 } |
|
331 |
|
332 state->cur.put_buffer = put_buffer; /* update state variables */ |
|
333 state->cur.put_bits = put_bits; |
|
334 |
|
335 return TRUE; |
|
336 } |
|
337 |
|
338 |
|
339 LOCAL(boolean) |
|
340 flush_bits (working_state * state) |
|
341 { |
|
342 if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */ |
|
343 return FALSE; |
|
344 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */ |
|
345 state->cur.put_bits = 0; |
|
346 return TRUE; |
|
347 } |
|
348 |
|
349 |
|
350 /* Encode a single block's worth of coefficients */ |
|
351 |
|
352 LOCAL(boolean) |
|
353 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, |
|
354 c_derived_tbl *dctbl, c_derived_tbl *actbl) |
|
355 { |
|
356 register int temp, temp2; |
|
357 register int nbits; |
|
358 register int k, r, i; |
|
359 |
|
360 /* Encode the DC coefficient difference per section F.1.2.1 */ |
|
361 |
|
362 temp = temp2 = block[0] - last_dc_val; |
|
363 |
|
364 if (temp < 0) { |
|
365 temp = -temp; /* temp is abs value of input */ |
|
366 /* For a negative input, want temp2 = bitwise complement of abs(input) */ |
|
367 /* This code assumes we are on a two's complement machine */ |
|
368 temp2--; |
|
369 } |
|
370 |
|
371 /* Find the number of bits needed for the magnitude of the coefficient */ |
|
372 nbits = 0; |
|
373 while (temp) { |
|
374 nbits++; |
|
375 temp >>= 1; |
|
376 } |
|
377 /* Check for out-of-range coefficient values. |
|
378 * Since we're encoding a difference, the range limit is twice as much. |
|
379 */ |
|
380 if (nbits > MAX_COEF_BITS+1) |
|
381 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); |
|
382 |
|
383 /* Emit the Huffman-coded symbol for the number of bits */ |
|
384 if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits])) |
|
385 return FALSE; |
|
386 |
|
387 /* Emit that number of bits of the value, if positive, */ |
|
388 /* or the complement of its magnitude, if negative. */ |
|
389 if (nbits) /* emit_bits rejects calls with size 0 */ |
|
390 if (! emit_bits(state, (unsigned int) temp2, nbits)) |
|
391 return FALSE; |
|
392 |
|
393 /* Encode the AC coefficients per section F.1.2.2 */ |
|
394 |
|
395 r = 0; /* r = run length of zeros */ |
|
396 |
|
397 for (k = 1; k < DCTSIZE2; k++) { |
|
398 if ((temp = block[jpeg_natural_order[k]]) == 0) { |
|
399 r++; |
|
400 } else { |
|
401 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ |
|
402 while (r > 15) { |
|
403 if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0])) |
|
404 return FALSE; |
|
405 r -= 16; |
|
406 } |
|
407 |
|
408 temp2 = temp; |
|
409 if (temp < 0) { |
|
410 temp = -temp; /* temp is abs value of input */ |
|
411 /* This code assumes we are on a two's complement machine */ |
|
412 temp2--; |
|
413 } |
|
414 |
|
415 /* Find the number of bits needed for the magnitude of the coefficient */ |
|
416 nbits = 1; /* there must be at least one 1 bit */ |
|
417 while ((temp >>= 1)) |
|
418 nbits++; |
|
419 /* Check for out-of-range coefficient values */ |
|
420 if (nbits > MAX_COEF_BITS) |
|
421 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); |
|
422 |
|
423 /* Emit Huffman symbol for run length / number of bits */ |
|
424 i = (r << 4) + nbits; |
|
425 if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i])) |
|
426 return FALSE; |
|
427 |
|
428 /* Emit that number of bits of the value, if positive, */ |
|
429 /* or the complement of its magnitude, if negative. */ |
|
430 if (! emit_bits(state, (unsigned int) temp2, nbits)) |
|
431 return FALSE; |
|
432 |
|
433 r = 0; |
|
434 } |
|
435 } |
|
436 |
|
437 /* If the last coef(s) were zero, emit an end-of-block code */ |
|
438 if (r > 0) |
|
439 if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0])) |
|
440 return FALSE; |
|
441 |
|
442 return TRUE; |
|
443 } |
|
444 |
|
445 |
|
446 /* |
|
447 * Emit a restart marker & resynchronize predictions. |
|
448 */ |
|
449 |
|
450 LOCAL(boolean) |
|
451 emit_restart (working_state * state, int restart_num) |
|
452 { |
|
453 int ci; |
|
454 |
|
455 if (! flush_bits(state)) |
|
456 return FALSE; |
|
457 |
|
458 emit_byte(state, 0xFF, return FALSE); |
|
459 emit_byte(state, JPEG_RST0 + restart_num, return FALSE); |
|
460 |
|
461 /* Re-initialize DC predictions to 0 */ |
|
462 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) |
|
463 state->cur.last_dc_val[ci] = 0; |
|
464 |
|
465 /* The restart counter is not updated until we successfully write the MCU. */ |
|
466 |
|
467 return TRUE; |
|
468 } |
|
469 |
|
470 |
|
471 /* |
|
472 * Encode and output one MCU's worth of Huffman-compressed coefficients. |
|
473 */ |
|
474 |
|
475 METHODDEF(boolean) |
|
476 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) |
|
477 { |
|
478 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; |
|
479 working_state state; |
|
480 int blkn, ci; |
|
481 jpeg_component_info * compptr; |
|
482 |
|
483 /* Load up working state */ |
|
484 state.next_output_byte = cinfo->dest->next_output_byte; |
|
485 state.free_in_buffer = cinfo->dest->free_in_buffer; |
|
486 ASSIGN_STATE(state.cur, entropy->saved); |
|
487 state.cinfo = cinfo; |
|
488 |
|
489 /* Emit restart marker if needed */ |
|
490 if (cinfo->restart_interval) { |
|
491 if (entropy->restarts_to_go == 0) |
|
492 if (! emit_restart(&state, entropy->next_restart_num)) |
|
493 return FALSE; |
|
494 } |
|
495 |
|
496 /* Encode the MCU data blocks */ |
|
497 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { |
|
498 ci = cinfo->MCU_membership[blkn]; |
|
499 compptr = cinfo->cur_comp_info[ci]; |
|
500 if (! encode_one_block(&state, |
|
501 MCU_data[blkn][0], state.cur.last_dc_val[ci], |
|
502 entropy->dc_derived_tbls[compptr->dc_tbl_no], |
|
503 entropy->ac_derived_tbls[compptr->ac_tbl_no])) |
|
504 return FALSE; |
|
505 /* Update last_dc_val */ |
|
506 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; |
|
507 } |
|
508 |
|
509 /* Completed MCU, so update state */ |
|
510 cinfo->dest->next_output_byte = state.next_output_byte; |
|
511 cinfo->dest->free_in_buffer = state.free_in_buffer; |
|
512 ASSIGN_STATE(entropy->saved, state.cur); |
|
513 |
|
514 /* Update restart-interval state too */ |
|
515 if (cinfo->restart_interval) { |
|
516 if (entropy->restarts_to_go == 0) { |
|
517 entropy->restarts_to_go = cinfo->restart_interval; |
|
518 entropy->next_restart_num++; |
|
519 entropy->next_restart_num &= 7; |
|
520 } |
|
521 entropy->restarts_to_go--; |
|
522 } |
|
523 |
|
524 return TRUE; |
|
525 } |
|
526 |
|
527 |
|
528 /* |
|
529 * Finish up at the end of a Huffman-compressed scan. |
|
530 */ |
|
531 |
|
532 METHODDEF(void) |
|
533 finish_pass_huff (j_compress_ptr cinfo) |
|
534 { |
|
535 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; |
|
536 working_state state; |
|
537 |
|
538 /* Load up working state ... flush_bits needs it */ |
|
539 state.next_output_byte = cinfo->dest->next_output_byte; |
|
540 state.free_in_buffer = cinfo->dest->free_in_buffer; |
|
541 ASSIGN_STATE(state.cur, entropy->saved); |
|
542 state.cinfo = cinfo; |
|
543 |
|
544 /* Flush out the last data */ |
|
545 if (! flush_bits(&state)) |
|
546 ERREXIT(cinfo, JERR_CANT_SUSPEND); |
|
547 |
|
548 /* Update state */ |
|
549 cinfo->dest->next_output_byte = state.next_output_byte; |
|
550 cinfo->dest->free_in_buffer = state.free_in_buffer; |
|
551 ASSIGN_STATE(entropy->saved, state.cur); |
|
552 } |
|
553 |
|
554 |
|
555 /* |
|
556 * Huffman coding optimization. |
|
557 * |
|
558 * We first scan the supplied data and count the number of uses of each symbol |
|
559 * that is to be Huffman-coded. (This process MUST agree with the code above.) |
|
560 * Then we build a Huffman coding tree for the observed counts. |
|
561 * Symbols which are not needed at all for the particular image are not |
|
562 * assigned any code, which saves space in the DHT marker as well as in |
|
563 * the compressed data. |
|
564 */ |
|
565 |
|
566 #ifdef ENTROPY_OPT_SUPPORTED |
|
567 |
|
568 |
|
569 /* Process a single block's worth of coefficients */ |
|
570 |
|
571 LOCAL(void) |
|
572 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, |
|
573 long dc_counts[], long ac_counts[]) |
|
574 { |
|
575 register int temp; |
|
576 register int nbits; |
|
577 register int k, r; |
|
578 |
|
579 /* Encode the DC coefficient difference per section F.1.2.1 */ |
|
580 |
|
581 temp = block[0] - last_dc_val; |
|
582 if (temp < 0) |
|
583 temp = -temp; |
|
584 |
|
585 /* Find the number of bits needed for the magnitude of the coefficient */ |
|
586 nbits = 0; |
|
587 while (temp) { |
|
588 nbits++; |
|
589 temp >>= 1; |
|
590 } |
|
591 /* Check for out-of-range coefficient values. |
|
592 * Since we're encoding a difference, the range limit is twice as much. |
|
593 */ |
|
594 if (nbits > MAX_COEF_BITS+1) |
|
595 ERREXIT(cinfo, JERR_BAD_DCT_COEF); |
|
596 |
|
597 /* Count the Huffman symbol for the number of bits */ |
|
598 dc_counts[nbits]++; |
|
599 |
|
600 /* Encode the AC coefficients per section F.1.2.2 */ |
|
601 |
|
602 r = 0; /* r = run length of zeros */ |
|
603 |
|
604 for (k = 1; k < DCTSIZE2; k++) { |
|
605 if ((temp = block[jpeg_natural_order[k]]) == 0) { |
|
606 r++; |
|
607 } else { |
|
608 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ |
|
609 while (r > 15) { |
|
610 ac_counts[0xF0]++; |
|
611 r -= 16; |
|
612 } |
|
613 |
|
614 /* Find the number of bits needed for the magnitude of the coefficient */ |
|
615 if (temp < 0) |
|
616 temp = -temp; |
|
617 |
|
618 /* Find the number of bits needed for the magnitude of the coefficient */ |
|
619 nbits = 1; /* there must be at least one 1 bit */ |
|
620 while ((temp >>= 1)) |
|
621 nbits++; |
|
622 /* Check for out-of-range coefficient values */ |
|
623 if (nbits > MAX_COEF_BITS) |
|
624 ERREXIT(cinfo, JERR_BAD_DCT_COEF); |
|
625 |
|
626 /* Count Huffman symbol for run length / number of bits */ |
|
627 ac_counts[(r << 4) + nbits]++; |
|
628 |
|
629 r = 0; |
|
630 } |
|
631 } |
|
632 |
|
633 /* If the last coef(s) were zero, emit an end-of-block code */ |
|
634 if (r > 0) |
|
635 ac_counts[0]++; |
|
636 } |
|
637 |
|
638 |
|
639 /* |
|
640 * Trial-encode one MCU's worth of Huffman-compressed coefficients. |
|
641 * No data is actually output, so no suspension return is possible. |
|
642 */ |
|
643 |
|
644 METHODDEF(boolean) |
|
645 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) |
|
646 { |
|
647 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; |
|
648 int blkn, ci; |
|
649 jpeg_component_info * compptr; |
|
650 |
|
651 /* Take care of restart intervals if needed */ |
|
652 if (cinfo->restart_interval) { |
|
653 if (entropy->restarts_to_go == 0) { |
|
654 /* Re-initialize DC predictions to 0 */ |
|
655 for (ci = 0; ci < cinfo->comps_in_scan; ci++) |
|
656 entropy->saved.last_dc_val[ci] = 0; |
|
657 /* Update restart state */ |
|
658 entropy->restarts_to_go = cinfo->restart_interval; |
|
659 } |
|
660 entropy->restarts_to_go--; |
|
661 } |
|
662 |
|
663 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { |
|
664 ci = cinfo->MCU_membership[blkn]; |
|
665 compptr = cinfo->cur_comp_info[ci]; |
|
666 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], |
|
667 entropy->dc_count_ptrs[compptr->dc_tbl_no], |
|
668 entropy->ac_count_ptrs[compptr->ac_tbl_no]); |
|
669 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; |
|
670 } |
|
671 |
|
672 return TRUE; |
|
673 } |
|
674 |
|
675 |
|
676 /* |
|
677 * Generate the best Huffman code table for the given counts, fill htbl. |
|
678 * Note this is also used by jcphuff.c. |
|
679 * |
|
680 * The JPEG standard requires that no symbol be assigned a codeword of all |
|
681 * one bits (so that padding bits added at the end of a compressed segment |
|
682 * can't look like a valid code). Because of the canonical ordering of |
|
683 * codewords, this just means that there must be an unused slot in the |
|
684 * longest codeword length category. Section K.2 of the JPEG spec suggests |
|
685 * reserving such a slot by pretending that symbol 256 is a valid symbol |
|
686 * with count 1. In theory that's not optimal; giving it count zero but |
|
687 * including it in the symbol set anyway should give a better Huffman code. |
|
688 * But the theoretically better code actually seems to come out worse in |
|
689 * practice, because it produces more all-ones bytes (which incur stuffed |
|
690 * zero bytes in the final file). In any case the difference is tiny. |
|
691 * |
|
692 * The JPEG standard requires Huffman codes to be no more than 16 bits long. |
|
693 * If some symbols have a very small but nonzero probability, the Huffman tree |
|
694 * must be adjusted to meet the code length restriction. We currently use |
|
695 * the adjustment method suggested in JPEG section K.2. This method is *not* |
|
696 * optimal; it may not choose the best possible limited-length code. But |
|
697 * typically only very-low-frequency symbols will be given less-than-optimal |
|
698 * lengths, so the code is almost optimal. Experimental comparisons against |
|
699 * an optimal limited-length-code algorithm indicate that the difference is |
|
700 * microscopic --- usually less than a hundredth of a percent of total size. |
|
701 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. |
|
702 */ |
|
703 |
|
704 GLOBAL(void) |
|
705 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) |
|
706 { |
|
707 #define MAX_CLEN 32 /* assumed maximum initial code length */ |
|
708 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */ |
|
709 int codesize[257]; /* codesize[k] = code length of symbol k */ |
|
710 int others[257]; /* next symbol in current branch of tree */ |
|
711 int c1, c2; |
|
712 int p, i, j; |
|
713 long v; |
|
714 |
|
715 /* This algorithm is explained in section K.2 of the JPEG standard */ |
|
716 |
|
717 MEMZERO(bits, SIZEOF(bits)); |
|
718 MEMZERO(codesize, SIZEOF(codesize)); |
|
719 for (i = 0; i < 257; i++) |
|
720 others[i] = -1; /* init links to empty */ |
|
721 |
|
722 freq[256] = 1; /* make sure 256 has a nonzero count */ |
|
723 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees |
|
724 * that no real symbol is given code-value of all ones, because 256 |
|
725 * will be placed last in the largest codeword category. |
|
726 */ |
|
727 |
|
728 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ |
|
729 |
|
730 for (;;) { |
|
731 /* Find the smallest nonzero frequency, set c1 = its symbol */ |
|
732 /* In case of ties, take the larger symbol number */ |
|
733 c1 = -1; |
|
734 v = 1000000000L; |
|
735 for (i = 0; i <= 256; i++) { |
|
736 if (freq[i] && freq[i] <= v) { |
|
737 v = freq[i]; |
|
738 c1 = i; |
|
739 } |
|
740 } |
|
741 |
|
742 /* Find the next smallest nonzero frequency, set c2 = its symbol */ |
|
743 /* In case of ties, take the larger symbol number */ |
|
744 c2 = -1; |
|
745 v = 1000000000L; |
|
746 for (i = 0; i <= 256; i++) { |
|
747 if (freq[i] && freq[i] <= v && i != c1) { |
|
748 v = freq[i]; |
|
749 c2 = i; |
|
750 } |
|
751 } |
|
752 |
|
753 /* Done if we've merged everything into one frequency */ |
|
754 if (c2 < 0) |
|
755 break; |
|
756 |
|
757 /* Else merge the two counts/trees */ |
|
758 freq[c1] += freq[c2]; |
|
759 freq[c2] = 0; |
|
760 |
|
761 /* Increment the codesize of everything in c1's tree branch */ |
|
762 codesize[c1]++; |
|
763 while (others[c1] >= 0) { |
|
764 c1 = others[c1]; |
|
765 codesize[c1]++; |
|
766 } |
|
767 |
|
768 others[c1] = c2; /* chain c2 onto c1's tree branch */ |
|
769 |
|
770 /* Increment the codesize of everything in c2's tree branch */ |
|
771 codesize[c2]++; |
|
772 while (others[c2] >= 0) { |
|
773 c2 = others[c2]; |
|
774 codesize[c2]++; |
|
775 } |
|
776 } |
|
777 |
|
778 /* Now count the number of symbols of each code length */ |
|
779 for (i = 0; i <= 256; i++) { |
|
780 if (codesize[i]) { |
|
781 /* The JPEG standard seems to think that this can't happen, */ |
|
782 /* but I'm paranoid... */ |
|
783 if (codesize[i] > MAX_CLEN) |
|
784 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); |
|
785 |
|
786 bits[codesize[i]]++; |
|
787 } |
|
788 } |
|
789 |
|
790 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure |
|
791 * Huffman procedure assigned any such lengths, we must adjust the coding. |
|
792 * Here is what the JPEG spec says about how this next bit works: |
|
793 * Since symbols are paired for the longest Huffman code, the symbols are |
|
794 * removed from this length category two at a time. The prefix for the pair |
|
795 * (which is one bit shorter) is allocated to one of the pair; then, |
|
796 * skipping the BITS entry for that prefix length, a code word from the next |
|
797 * shortest nonzero BITS entry is converted into a prefix for two code words |
|
798 * one bit longer. |
|
799 */ |
|
800 |
|
801 for (i = MAX_CLEN; i > 16; i--) { |
|
802 while (bits[i] > 0) { |
|
803 j = i - 2; /* find length of new prefix to be used */ |
|
804 while (bits[j] == 0) |
|
805 j--; |
|
806 |
|
807 bits[i] -= 2; /* remove two symbols */ |
|
808 bits[i-1]++; /* one goes in this length */ |
|
809 bits[j+1] += 2; /* two new symbols in this length */ |
|
810 bits[j]--; /* symbol of this length is now a prefix */ |
|
811 } |
|
812 } |
|
813 |
|
814 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ |
|
815 while (bits[i] == 0) /* find largest codelength still in use */ |
|
816 i--; |
|
817 bits[i]--; |
|
818 |
|
819 /* Return final symbol counts (only for lengths 0..16) */ |
|
820 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits)); |
|
821 |
|
822 /* Return a list of the symbols sorted by code length */ |
|
823 /* It's not real clear to me why we don't need to consider the codelength |
|
824 * changes made above, but the JPEG spec seems to think this works. |
|
825 */ |
|
826 p = 0; |
|
827 for (i = 1; i <= MAX_CLEN; i++) { |
|
828 for (j = 0; j <= 255; j++) { |
|
829 if (codesize[j] == i) { |
|
830 htbl->huffval[p] = (UINT8) j; |
|
831 p++; |
|
832 } |
|
833 } |
|
834 } |
|
835 |
|
836 /* Set sent_table FALSE so updated table will be written to JPEG file. */ |
|
837 htbl->sent_table = FALSE; |
|
838 } |
|
839 |
|
840 |
|
841 /* |
|
842 * Finish up a statistics-gathering pass and create the new Huffman tables. |
|
843 */ |
|
844 |
|
845 METHODDEF(void) |
|
846 finish_pass_gather (j_compress_ptr cinfo) |
|
847 { |
|
848 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; |
|
849 int ci, dctbl, actbl; |
|
850 jpeg_component_info * compptr; |
|
851 JHUFF_TBL **htblptr; |
|
852 boolean did_dc[NUM_HUFF_TBLS]; |
|
853 boolean did_ac[NUM_HUFF_TBLS]; |
|
854 |
|
855 /* It's important not to apply jpeg_gen_optimal_table more than once |
|
856 * per table, because it clobbers the input frequency counts! |
|
857 */ |
|
858 MEMZERO(did_dc, SIZEOF(did_dc)); |
|
859 MEMZERO(did_ac, SIZEOF(did_ac)); |
|
860 |
|
861 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { |
|
862 compptr = cinfo->cur_comp_info[ci]; |
|
863 dctbl = compptr->dc_tbl_no; |
|
864 actbl = compptr->ac_tbl_no; |
|
865 if (! did_dc[dctbl]) { |
|
866 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl]; |
|
867 if (*htblptr == NULL) |
|
868 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); |
|
869 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]); |
|
870 did_dc[dctbl] = TRUE; |
|
871 } |
|
872 if (! did_ac[actbl]) { |
|
873 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl]; |
|
874 if (*htblptr == NULL) |
|
875 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); |
|
876 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]); |
|
877 did_ac[actbl] = TRUE; |
|
878 } |
|
879 } |
|
880 } |
|
881 |
|
882 |
|
883 #endif /* ENTROPY_OPT_SUPPORTED */ |
|
884 |
|
885 |
|
886 /* |
|
887 * Module initialization routine for Huffman entropy encoding. |
|
888 */ |
|
889 |
|
890 GLOBAL(void) |
|
891 jinit_huff_encoder (j_compress_ptr cinfo) |
|
892 { |
|
893 huff_entropy_ptr entropy; |
|
894 int i; |
|
895 |
|
896 entropy = (huff_entropy_ptr) |
|
897 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, |
|
898 SIZEOF(huff_entropy_encoder)); |
|
899 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; |
|
900 entropy->pub.start_pass = start_pass_huff; |
|
901 |
|
902 /* Mark tables unallocated */ |
|
903 for (i = 0; i < NUM_HUFF_TBLS; i++) { |
|
904 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; |
|
905 #ifdef ENTROPY_OPT_SUPPORTED |
|
906 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; |
|
907 #endif |
|
908 } |
|
909 } |