]>
Commit | Line | Data |
---|---|---|
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 | JPEG_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 (((JPEG_INT32) code) >= (((JPEG_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 JPEG_INT32 put_buffer = (JPEG_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 &= (((JPEG_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 | } |