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