Line data Source code
1 : /*
2 : * jchuff.c
3 : *
4 : * This file was part of the Independent JPEG Group's software:
5 : * Copyright (C) 1991-1997, Thomas G. Lane.
6 : * libjpeg-turbo Modifications:
7 : * Copyright (C) 2009-2011, 2014-2016, D. R. Commander.
8 : * Copyright (C) 2015, Matthieu Darbois.
9 : * For conditions of distribution and use, see the accompanying README.ijg
10 : * 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 "jsimd.h"
25 : #include "jconfigint.h"
26 : #include <limits.h>
27 :
28 : /*
29 : * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be
30 : * used for bit counting rather than the lookup table. This will reduce the
31 : * memory footprint by 64k, which is important for some mobile applications
32 : * that create many isolated instances of libjpeg-turbo (web browsers, for
33 : * instance.) This may improve performance on some mobile platforms as well.
34 : * This feature is enabled by default only on ARM processors, because some x86
35 : * chips have a slow implementation of bsr, and the use of clz/bsr cannot be
36 : * shown to have a significant performance impact even on the x86 chips that
37 : * have a fast implementation of it. When building for ARMv6, you can
38 : * explicitly disable the use of clz/bsr by adding -mthumb to the compiler
39 : * flags (this defines __thumb__).
40 : */
41 :
42 : /* NOTE: Both GCC and Clang define __GNUC__ */
43 : #if defined __GNUC__ && (defined __arm__ || defined __aarch64__)
44 : #if !defined __thumb__ || defined __thumb2__
45 : #define USE_CLZ_INTRINSIC
46 : #endif
47 : #endif
48 :
49 : #ifdef USE_CLZ_INTRINSIC
50 : #define JPEG_NBITS_NONZERO(x) (32 - __builtin_clz(x))
51 : #define JPEG_NBITS(x) (x ? JPEG_NBITS_NONZERO(x) : 0)
52 : #else
53 : #include "jpeg_nbits_table.h"
54 : #define JPEG_NBITS(x) (jpeg_nbits_table[x])
55 : #define JPEG_NBITS_NONZERO(x) JPEG_NBITS(x)
56 : #endif
57 :
58 : #ifndef min
59 : #define min(a,b) ((a)<(b)?(a):(b))
60 : #endif
61 :
62 :
63 : /* Expanded entropy encoder object for Huffman encoding.
64 : *
65 : * The savable_state subrecord contains fields that change within an MCU,
66 : * but must not be updated permanently until we complete the MCU.
67 : */
68 :
69 : typedef struct {
70 : size_t put_buffer; /* current bit-accumulation buffer */
71 : int put_bits; /* # of bits now in it */
72 : int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
73 : } savable_state;
74 :
75 : /* This macro is to work around compilers with missing or broken
76 : * structure assignment. You'll need to fix this code if you have
77 : * such a compiler and you change MAX_COMPS_IN_SCAN.
78 : */
79 :
80 : #ifndef NO_STRUCT_ASSIGN
81 : #define ASSIGN_STATE(dest,src) ((dest) = (src))
82 : #else
83 : #if MAX_COMPS_IN_SCAN == 4
84 : #define ASSIGN_STATE(dest,src) \
85 : ((dest).put_buffer = (src).put_buffer, \
86 : (dest).put_bits = (src).put_bits, \
87 : (dest).last_dc_val[0] = (src).last_dc_val[0], \
88 : (dest).last_dc_val[1] = (src).last_dc_val[1], \
89 : (dest).last_dc_val[2] = (src).last_dc_val[2], \
90 : (dest).last_dc_val[3] = (src).last_dc_val[3])
91 : #endif
92 : #endif
93 :
94 :
95 : typedef struct {
96 : struct jpeg_entropy_encoder pub; /* public fields */
97 :
98 : savable_state saved; /* Bit buffer & DC state at start of MCU */
99 :
100 : /* These fields are NOT loaded into local working state. */
101 : unsigned int restarts_to_go; /* MCUs left in this restart interval */
102 : int next_restart_num; /* next restart number to write (0-7) */
103 :
104 : /* Pointers to derived tables (these workspaces have image lifespan) */
105 : c_derived_tbl *dc_derived_tbls[NUM_HUFF_TBLS];
106 : c_derived_tbl *ac_derived_tbls[NUM_HUFF_TBLS];
107 :
108 : #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */
109 : long *dc_count_ptrs[NUM_HUFF_TBLS];
110 : long *ac_count_ptrs[NUM_HUFF_TBLS];
111 : #endif
112 :
113 : int simd;
114 : } huff_entropy_encoder;
115 :
116 : typedef huff_entropy_encoder *huff_entropy_ptr;
117 :
118 : /* Working state while writing an MCU.
119 : * This struct contains all the fields that are needed by subroutines.
120 : */
121 :
122 : typedef struct {
123 : JOCTET *next_output_byte; /* => next byte to write in buffer */
124 : size_t free_in_buffer; /* # of byte spaces remaining in buffer */
125 : savable_state cur; /* Current bit buffer & DC state */
126 : j_compress_ptr cinfo; /* dump_buffer needs access to this */
127 : } working_state;
128 :
129 :
130 : /* Forward declarations */
131 : METHODDEF(boolean) encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data);
132 : METHODDEF(void) finish_pass_huff (j_compress_ptr cinfo);
133 : #ifdef ENTROPY_OPT_SUPPORTED
134 : METHODDEF(boolean) encode_mcu_gather (j_compress_ptr cinfo,
135 : JBLOCKROW *MCU_data);
136 : METHODDEF(void) finish_pass_gather (j_compress_ptr cinfo);
137 : #endif
138 :
139 :
140 : /*
141 : * Initialize for a Huffman-compressed scan.
142 : * If gather_statistics is TRUE, we do not output anything during the scan,
143 : * just count the Huffman symbols used and generate Huffman code tables.
144 : */
145 :
146 : METHODDEF(void)
147 0 : start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
148 : {
149 0 : huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
150 : int ci, dctbl, actbl;
151 : jpeg_component_info *compptr;
152 :
153 0 : if (gather_statistics) {
154 : #ifdef ENTROPY_OPT_SUPPORTED
155 0 : entropy->pub.encode_mcu = encode_mcu_gather;
156 0 : entropy->pub.finish_pass = finish_pass_gather;
157 : #else
158 : ERREXIT(cinfo, JERR_NOT_COMPILED);
159 : #endif
160 : } else {
161 0 : entropy->pub.encode_mcu = encode_mcu_huff;
162 0 : entropy->pub.finish_pass = finish_pass_huff;
163 : }
164 :
165 0 : entropy->simd = jsimd_can_huff_encode_one_block();
166 :
167 0 : for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
168 0 : compptr = cinfo->cur_comp_info[ci];
169 0 : dctbl = compptr->dc_tbl_no;
170 0 : actbl = compptr->ac_tbl_no;
171 0 : if (gather_statistics) {
172 : #ifdef ENTROPY_OPT_SUPPORTED
173 : /* Check for invalid table indexes */
174 : /* (make_c_derived_tbl does this in the other path) */
175 0 : if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
176 0 : ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
177 0 : if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
178 0 : ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
179 : /* Allocate and zero the statistics tables */
180 : /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
181 0 : if (entropy->dc_count_ptrs[dctbl] == NULL)
182 0 : entropy->dc_count_ptrs[dctbl] = (long *)
183 0 : (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
184 : 257 * sizeof(long));
185 0 : MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * sizeof(long));
186 0 : if (entropy->ac_count_ptrs[actbl] == NULL)
187 0 : entropy->ac_count_ptrs[actbl] = (long *)
188 0 : (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
189 : 257 * sizeof(long));
190 0 : MEMZERO(entropy->ac_count_ptrs[actbl], 257 * sizeof(long));
191 : #endif
192 : } else {
193 : /* Compute derived values for Huffman tables */
194 : /* We may do this more than once for a table, but it's not expensive */
195 0 : jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
196 : & entropy->dc_derived_tbls[dctbl]);
197 0 : jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
198 : & entropy->ac_derived_tbls[actbl]);
199 : }
200 : /* Initialize DC predictions to 0 */
201 0 : entropy->saved.last_dc_val[ci] = 0;
202 : }
203 :
204 : /* Initialize bit buffer to empty */
205 0 : entropy->saved.put_buffer = 0;
206 0 : entropy->saved.put_bits = 0;
207 :
208 : /* Initialize restart stuff */
209 0 : entropy->restarts_to_go = cinfo->restart_interval;
210 0 : entropy->next_restart_num = 0;
211 0 : }
212 :
213 :
214 : /*
215 : * Compute the derived values for a Huffman table.
216 : * This routine also performs some validation checks on the table.
217 : *
218 : * Note this is also used by jcphuff.c.
219 : */
220 :
221 : GLOBAL(void)
222 0 : jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
223 : c_derived_tbl **pdtbl)
224 : {
225 : JHUFF_TBL *htbl;
226 : c_derived_tbl *dtbl;
227 : int p, i, l, lastp, si, maxsymbol;
228 : char huffsize[257];
229 : unsigned int huffcode[257];
230 : unsigned int code;
231 :
232 : /* Note that huffsize[] and huffcode[] are filled in code-length order,
233 : * paralleling the order of the symbols themselves in htbl->huffval[].
234 : */
235 :
236 : /* Find the input Huffman table */
237 0 : if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
238 0 : ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
239 0 : htbl =
240 0 : isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
241 0 : if (htbl == NULL)
242 0 : ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
243 :
244 : /* Allocate a workspace if we haven't already done so. */
245 0 : if (*pdtbl == NULL)
246 0 : *pdtbl = (c_derived_tbl *)
247 0 : (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
248 : sizeof(c_derived_tbl));
249 0 : dtbl = *pdtbl;
250 :
251 : /* Figure C.1: make table of Huffman code length for each symbol */
252 :
253 0 : p = 0;
254 0 : for (l = 1; l <= 16; l++) {
255 0 : i = (int) htbl->bits[l];
256 0 : if (i < 0 || p + i > 256) /* protect against table overrun */
257 0 : ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
258 0 : while (i--)
259 0 : huffsize[p++] = (char) l;
260 : }
261 0 : huffsize[p] = 0;
262 0 : lastp = p;
263 :
264 : /* Figure C.2: generate the codes themselves */
265 : /* We also validate that the counts represent a legal Huffman code tree. */
266 :
267 0 : code = 0;
268 0 : si = huffsize[0];
269 0 : p = 0;
270 0 : while (huffsize[p]) {
271 0 : while (((int) huffsize[p]) == si) {
272 0 : huffcode[p++] = code;
273 0 : code++;
274 : }
275 : /* code is now 1 more than the last code used for codelength si; but
276 : * it must still fit in si bits, since no code is allowed to be all ones.
277 : */
278 0 : if (((JLONG) code) >= (((JLONG) 1) << si))
279 0 : ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
280 0 : code <<= 1;
281 0 : si++;
282 : }
283 :
284 : /* Figure C.3: generate encoding tables */
285 : /* These are code and size indexed by symbol value */
286 :
287 : /* Set all codeless symbols to have code length 0;
288 : * this lets us detect duplicate VAL entries here, and later
289 : * allows emit_bits to detect any attempt to emit such symbols.
290 : */
291 0 : MEMZERO(dtbl->ehufsi, sizeof(dtbl->ehufsi));
292 :
293 : /* This is also a convenient place to check for out-of-range
294 : * and duplicated VAL entries. We allow 0..255 for AC symbols
295 : * but only 0..15 for DC. (We could constrain them further
296 : * based on data depth and mode, but this seems enough.)
297 : */
298 0 : maxsymbol = isDC ? 15 : 255;
299 :
300 0 : for (p = 0; p < lastp; p++) {
301 0 : i = htbl->huffval[p];
302 0 : if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
303 0 : ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
304 0 : dtbl->ehufco[i] = huffcode[p];
305 0 : dtbl->ehufsi[i] = huffsize[p];
306 : }
307 0 : }
308 :
309 :
310 : /* Outputting bytes to the file */
311 :
312 : /* Emit a byte, taking 'action' if must suspend. */
313 : #define emit_byte(state,val,action) \
314 : { *(state)->next_output_byte++ = (JOCTET) (val); \
315 : if (--(state)->free_in_buffer == 0) \
316 : if (! dump_buffer(state)) \
317 : { action; } }
318 :
319 :
320 : LOCAL(boolean)
321 0 : dump_buffer (working_state *state)
322 : /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
323 : {
324 0 : struct jpeg_destination_mgr *dest = state->cinfo->dest;
325 :
326 0 : if (! (*dest->empty_output_buffer) (state->cinfo))
327 0 : return FALSE;
328 : /* After a successful buffer dump, must reset buffer pointers */
329 0 : state->next_output_byte = dest->next_output_byte;
330 0 : state->free_in_buffer = dest->free_in_buffer;
331 0 : return TRUE;
332 : }
333 :
334 :
335 : /* Outputting bits to the file */
336 :
337 : /* These macros perform the same task as the emit_bits() function in the
338 : * original libjpeg code. In addition to reducing overhead by explicitly
339 : * inlining the code, additional performance is achieved by taking into
340 : * account the size of the bit buffer and waiting until it is almost full
341 : * before emptying it. This mostly benefits 64-bit platforms, since 6
342 : * bytes can be stored in a 64-bit bit buffer before it has to be emptied.
343 : */
344 :
345 : #define EMIT_BYTE() { \
346 : JOCTET c; \
347 : put_bits -= 8; \
348 : c = (JOCTET)GETJOCTET(put_buffer >> put_bits); \
349 : *buffer++ = c; \
350 : if (c == 0xFF) /* need to stuff a zero byte? */ \
351 : *buffer++ = 0; \
352 : }
353 :
354 : #define PUT_BITS(code, size) { \
355 : put_bits += size; \
356 : put_buffer = (put_buffer << size) | code; \
357 : }
358 :
359 : #define CHECKBUF15() { \
360 : if (put_bits > 15) { \
361 : EMIT_BYTE() \
362 : EMIT_BYTE() \
363 : } \
364 : }
365 :
366 : #define CHECKBUF31() { \
367 : if (put_bits > 31) { \
368 : EMIT_BYTE() \
369 : EMIT_BYTE() \
370 : EMIT_BYTE() \
371 : EMIT_BYTE() \
372 : } \
373 : }
374 :
375 : #define CHECKBUF47() { \
376 : if (put_bits > 47) { \
377 : EMIT_BYTE() \
378 : EMIT_BYTE() \
379 : EMIT_BYTE() \
380 : EMIT_BYTE() \
381 : EMIT_BYTE() \
382 : EMIT_BYTE() \
383 : } \
384 : }
385 :
386 : #if !defined(_WIN32) && !defined(SIZEOF_SIZE_T)
387 : #error Cannot determine word size
388 : #endif
389 :
390 : #if SIZEOF_SIZE_T==8 || defined(_WIN64)
391 :
392 : #define EMIT_BITS(code, size) { \
393 : CHECKBUF47() \
394 : PUT_BITS(code, size) \
395 : }
396 :
397 : #define EMIT_CODE(code, size) { \
398 : temp2 &= (((JLONG) 1)<<nbits) - 1; \
399 : CHECKBUF31() \
400 : PUT_BITS(code, size) \
401 : PUT_BITS(temp2, nbits) \
402 : }
403 :
404 : #else
405 :
406 : #define EMIT_BITS(code, size) { \
407 : PUT_BITS(code, size) \
408 : CHECKBUF15() \
409 : }
410 :
411 : #define EMIT_CODE(code, size) { \
412 : temp2 &= (((JLONG) 1)<<nbits) - 1; \
413 : PUT_BITS(code, size) \
414 : CHECKBUF15() \
415 : PUT_BITS(temp2, nbits) \
416 : CHECKBUF15() \
417 : }
418 :
419 : #endif
420 :
421 :
422 : /* Although it is exceedingly rare, it is possible for a Huffman-encoded
423 : * coefficient block to be larger than the 128-byte unencoded block. For each
424 : * of the 64 coefficients, PUT_BITS is invoked twice, and each invocation can
425 : * theoretically store 16 bits (for a maximum of 2048 bits or 256 bytes per
426 : * encoded block.) If, for instance, one artificially sets the AC
427 : * coefficients to alternating values of 32767 and -32768 (using the JPEG
428 : * scanning order-- 1, 8, 16, etc.), then this will produce an encoded block
429 : * larger than 200 bytes.
430 : */
431 : #define BUFSIZE (DCTSIZE2 * 4)
432 :
433 : #define LOAD_BUFFER() { \
434 : if (state->free_in_buffer < BUFSIZE) { \
435 : localbuf = 1; \
436 : buffer = _buffer; \
437 : } \
438 : else buffer = state->next_output_byte; \
439 : }
440 :
441 : #define STORE_BUFFER() { \
442 : if (localbuf) { \
443 : bytes = buffer - _buffer; \
444 : buffer = _buffer; \
445 : while (bytes > 0) { \
446 : bytestocopy = min(bytes, state->free_in_buffer); \
447 : MEMCOPY(state->next_output_byte, buffer, bytestocopy); \
448 : state->next_output_byte += bytestocopy; \
449 : buffer += bytestocopy; \
450 : state->free_in_buffer -= bytestocopy; \
451 : if (state->free_in_buffer == 0) \
452 : if (! dump_buffer(state)) return FALSE; \
453 : bytes -= bytestocopy; \
454 : } \
455 : } \
456 : else { \
457 : state->free_in_buffer -= (buffer - state->next_output_byte); \
458 : state->next_output_byte = buffer; \
459 : } \
460 : }
461 :
462 :
463 : LOCAL(boolean)
464 0 : flush_bits (working_state *state)
465 : {
466 : JOCTET _buffer[BUFSIZE], *buffer;
467 : size_t put_buffer; int put_bits;
468 0 : size_t bytes, bytestocopy; int localbuf = 0;
469 :
470 0 : put_buffer = state->cur.put_buffer;
471 0 : put_bits = state->cur.put_bits;
472 0 : LOAD_BUFFER()
473 :
474 : /* fill any partial byte with ones */
475 0 : PUT_BITS(0x7F, 7)
476 0 : while (put_bits >= 8) EMIT_BYTE()
477 :
478 0 : state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
479 0 : state->cur.put_bits = 0;
480 0 : STORE_BUFFER()
481 :
482 0 : return TRUE;
483 : }
484 :
485 :
486 : /* Encode a single block's worth of coefficients */
487 :
488 : LOCAL(boolean)
489 0 : encode_one_block_simd (working_state *state, JCOEFPTR block, int last_dc_val,
490 : c_derived_tbl *dctbl, c_derived_tbl *actbl)
491 : {
492 : JOCTET _buffer[BUFSIZE], *buffer;
493 0 : size_t bytes, bytestocopy; int localbuf = 0;
494 :
495 0 : LOAD_BUFFER()
496 :
497 0 : buffer = jsimd_huff_encode_one_block(state, buffer, block, last_dc_val,
498 : dctbl, actbl);
499 :
500 0 : STORE_BUFFER()
501 :
502 0 : return TRUE;
503 : }
504 :
505 : LOCAL(boolean)
506 0 : encode_one_block (working_state *state, JCOEFPTR block, int last_dc_val,
507 : c_derived_tbl *dctbl, c_derived_tbl *actbl)
508 : {
509 : int temp, temp2, temp3;
510 : int nbits;
511 : int r, code, size;
512 : JOCTET _buffer[BUFSIZE], *buffer;
513 : size_t put_buffer; int put_bits;
514 0 : int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0];
515 0 : size_t bytes, bytestocopy; int localbuf = 0;
516 :
517 0 : put_buffer = state->cur.put_buffer;
518 0 : put_bits = state->cur.put_bits;
519 0 : LOAD_BUFFER()
520 :
521 : /* Encode the DC coefficient difference per section F.1.2.1 */
522 :
523 0 : temp = temp2 = block[0] - last_dc_val;
524 :
525 : /* This is a well-known technique for obtaining the absolute value without a
526 : * branch. It is derived from an assembly language technique presented in
527 : * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by
528 : * Agner Fog.
529 : */
530 0 : temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
531 0 : temp ^= temp3;
532 0 : temp -= temp3;
533 :
534 : /* For a negative input, want temp2 = bitwise complement of abs(input) */
535 : /* This code assumes we are on a two's complement machine */
536 0 : temp2 += temp3;
537 :
538 : /* Find the number of bits needed for the magnitude of the coefficient */
539 0 : nbits = JPEG_NBITS(temp);
540 :
541 : /* Emit the Huffman-coded symbol for the number of bits */
542 0 : code = dctbl->ehufco[nbits];
543 0 : size = dctbl->ehufsi[nbits];
544 0 : EMIT_BITS(code, size)
545 :
546 : /* Mask off any extra bits in code */
547 0 : temp2 &= (((JLONG) 1)<<nbits) - 1;
548 :
549 : /* Emit that number of bits of the value, if positive, */
550 : /* or the complement of its magnitude, if negative. */
551 0 : EMIT_BITS(temp2, nbits)
552 :
553 : /* Encode the AC coefficients per section F.1.2.2 */
554 :
555 0 : r = 0; /* r = run length of zeros */
556 :
557 : /* Manually unroll the k loop to eliminate the counter variable. This
558 : * improves performance greatly on systems with a limited number of
559 : * registers (such as x86.)
560 : */
561 : #define kloop(jpeg_natural_order_of_k) { \
562 : if ((temp = block[jpeg_natural_order_of_k]) == 0) { \
563 : r++; \
564 : } else { \
565 : temp2 = temp; \
566 : /* Branch-less absolute value, bitwise complement, etc., same as above */ \
567 : temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); \
568 : temp ^= temp3; \
569 : temp -= temp3; \
570 : temp2 += temp3; \
571 : nbits = JPEG_NBITS_NONZERO(temp); \
572 : /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \
573 : while (r > 15) { \
574 : EMIT_BITS(code_0xf0, size_0xf0) \
575 : r -= 16; \
576 : } \
577 : /* Emit Huffman symbol for run length / number of bits */ \
578 : temp3 = (r << 4) + nbits; \
579 : code = actbl->ehufco[temp3]; \
580 : size = actbl->ehufsi[temp3]; \
581 : EMIT_CODE(code, size) \
582 : r = 0; \
583 : } \
584 : }
585 :
586 : /* One iteration for each value in jpeg_natural_order[] */
587 0 : kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3);
588 0 : kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18);
589 0 : kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26);
590 0 : kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27);
591 0 : kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21);
592 0 : kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57);
593 0 : kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15);
594 0 : kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58);
595 0 : kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39);
596 0 : kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47);
597 0 : kloop(55); kloop(62); kloop(63);
598 :
599 : /* If the last coef(s) were zero, emit an end-of-block code */
600 0 : if (r > 0) {
601 0 : code = actbl->ehufco[0];
602 0 : size = actbl->ehufsi[0];
603 0 : EMIT_BITS(code, size)
604 : }
605 :
606 0 : state->cur.put_buffer = put_buffer;
607 0 : state->cur.put_bits = put_bits;
608 0 : STORE_BUFFER()
609 :
610 0 : return TRUE;
611 : }
612 :
613 :
614 : /*
615 : * Emit a restart marker & resynchronize predictions.
616 : */
617 :
618 : LOCAL(boolean)
619 0 : emit_restart (working_state *state, int restart_num)
620 : {
621 : int ci;
622 :
623 0 : if (! flush_bits(state))
624 0 : return FALSE;
625 :
626 0 : emit_byte(state, 0xFF, return FALSE);
627 0 : emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
628 :
629 : /* Re-initialize DC predictions to 0 */
630 0 : for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
631 0 : state->cur.last_dc_val[ci] = 0;
632 :
633 : /* The restart counter is not updated until we successfully write the MCU. */
634 :
635 0 : return TRUE;
636 : }
637 :
638 :
639 : /*
640 : * Encode and output one MCU's worth of Huffman-compressed coefficients.
641 : */
642 :
643 : METHODDEF(boolean)
644 0 : encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
645 : {
646 0 : huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
647 : working_state state;
648 : int blkn, ci;
649 : jpeg_component_info *compptr;
650 :
651 : /* Load up working state */
652 0 : state.next_output_byte = cinfo->dest->next_output_byte;
653 0 : state.free_in_buffer = cinfo->dest->free_in_buffer;
654 0 : ASSIGN_STATE(state.cur, entropy->saved);
655 0 : state.cinfo = cinfo;
656 :
657 : /* Emit restart marker if needed */
658 0 : if (cinfo->restart_interval) {
659 0 : if (entropy->restarts_to_go == 0)
660 0 : if (! emit_restart(&state, entropy->next_restart_num))
661 0 : return FALSE;
662 : }
663 :
664 : /* Encode the MCU data blocks */
665 0 : if (entropy->simd) {
666 0 : for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
667 0 : ci = cinfo->MCU_membership[blkn];
668 0 : compptr = cinfo->cur_comp_info[ci];
669 0 : if (! encode_one_block_simd(&state,
670 0 : MCU_data[blkn][0], state.cur.last_dc_val[ci],
671 0 : entropy->dc_derived_tbls[compptr->dc_tbl_no],
672 0 : entropy->ac_derived_tbls[compptr->ac_tbl_no]))
673 0 : return FALSE;
674 : /* Update last_dc_val */
675 0 : state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
676 : }
677 : } else {
678 0 : for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
679 0 : ci = cinfo->MCU_membership[blkn];
680 0 : compptr = cinfo->cur_comp_info[ci];
681 0 : if (! encode_one_block(&state,
682 0 : MCU_data[blkn][0], state.cur.last_dc_val[ci],
683 0 : entropy->dc_derived_tbls[compptr->dc_tbl_no],
684 0 : entropy->ac_derived_tbls[compptr->ac_tbl_no]))
685 0 : return FALSE;
686 : /* Update last_dc_val */
687 0 : state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
688 : }
689 : }
690 :
691 : /* Completed MCU, so update state */
692 0 : cinfo->dest->next_output_byte = state.next_output_byte;
693 0 : cinfo->dest->free_in_buffer = state.free_in_buffer;
694 0 : ASSIGN_STATE(entropy->saved, state.cur);
695 :
696 : /* Update restart-interval state too */
697 0 : if (cinfo->restart_interval) {
698 0 : if (entropy->restarts_to_go == 0) {
699 0 : entropy->restarts_to_go = cinfo->restart_interval;
700 0 : entropy->next_restart_num++;
701 0 : entropy->next_restart_num &= 7;
702 : }
703 0 : entropy->restarts_to_go--;
704 : }
705 :
706 0 : return TRUE;
707 : }
708 :
709 :
710 : /*
711 : * Finish up at the end of a Huffman-compressed scan.
712 : */
713 :
714 : METHODDEF(void)
715 0 : finish_pass_huff (j_compress_ptr cinfo)
716 : {
717 0 : huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
718 : working_state state;
719 :
720 : /* Load up working state ... flush_bits needs it */
721 0 : state.next_output_byte = cinfo->dest->next_output_byte;
722 0 : state.free_in_buffer = cinfo->dest->free_in_buffer;
723 0 : ASSIGN_STATE(state.cur, entropy->saved);
724 0 : state.cinfo = cinfo;
725 :
726 : /* Flush out the last data */
727 0 : if (! flush_bits(&state))
728 0 : ERREXIT(cinfo, JERR_CANT_SUSPEND);
729 :
730 : /* Update state */
731 0 : cinfo->dest->next_output_byte = state.next_output_byte;
732 0 : cinfo->dest->free_in_buffer = state.free_in_buffer;
733 0 : ASSIGN_STATE(entropy->saved, state.cur);
734 0 : }
735 :
736 :
737 : /*
738 : * Huffman coding optimization.
739 : *
740 : * We first scan the supplied data and count the number of uses of each symbol
741 : * that is to be Huffman-coded. (This process MUST agree with the code above.)
742 : * Then we build a Huffman coding tree for the observed counts.
743 : * Symbols which are not needed at all for the particular image are not
744 : * assigned any code, which saves space in the DHT marker as well as in
745 : * the compressed data.
746 : */
747 :
748 : #ifdef ENTROPY_OPT_SUPPORTED
749 :
750 :
751 : /* Process a single block's worth of coefficients */
752 :
753 : LOCAL(void)
754 0 : htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
755 : long dc_counts[], long ac_counts[])
756 : {
757 : register int temp;
758 : register int nbits;
759 : register int k, r;
760 :
761 : /* Encode the DC coefficient difference per section F.1.2.1 */
762 :
763 0 : temp = block[0] - last_dc_val;
764 0 : if (temp < 0)
765 0 : temp = -temp;
766 :
767 : /* Find the number of bits needed for the magnitude of the coefficient */
768 0 : nbits = 0;
769 0 : while (temp) {
770 0 : nbits++;
771 0 : temp >>= 1;
772 : }
773 : /* Check for out-of-range coefficient values.
774 : * Since we're encoding a difference, the range limit is twice as much.
775 : */
776 0 : if (nbits > MAX_COEF_BITS+1)
777 0 : ERREXIT(cinfo, JERR_BAD_DCT_COEF);
778 :
779 : /* Count the Huffman symbol for the number of bits */
780 0 : dc_counts[nbits]++;
781 :
782 : /* Encode the AC coefficients per section F.1.2.2 */
783 :
784 0 : r = 0; /* r = run length of zeros */
785 :
786 0 : for (k = 1; k < DCTSIZE2; k++) {
787 0 : if ((temp = block[jpeg_natural_order[k]]) == 0) {
788 0 : r++;
789 : } else {
790 : /* if run length > 15, must emit special run-length-16 codes (0xF0) */
791 0 : while (r > 15) {
792 0 : ac_counts[0xF0]++;
793 0 : r -= 16;
794 : }
795 :
796 : /* Find the number of bits needed for the magnitude of the coefficient */
797 0 : if (temp < 0)
798 0 : temp = -temp;
799 :
800 : /* Find the number of bits needed for the magnitude of the coefficient */
801 0 : nbits = 1; /* there must be at least one 1 bit */
802 0 : while ((temp >>= 1))
803 0 : nbits++;
804 : /* Check for out-of-range coefficient values */
805 0 : if (nbits > MAX_COEF_BITS)
806 0 : ERREXIT(cinfo, JERR_BAD_DCT_COEF);
807 :
808 : /* Count Huffman symbol for run length / number of bits */
809 0 : ac_counts[(r << 4) + nbits]++;
810 :
811 0 : r = 0;
812 : }
813 : }
814 :
815 : /* If the last coef(s) were zero, emit an end-of-block code */
816 0 : if (r > 0)
817 0 : ac_counts[0]++;
818 0 : }
819 :
820 :
821 : /*
822 : * Trial-encode one MCU's worth of Huffman-compressed coefficients.
823 : * No data is actually output, so no suspension return is possible.
824 : */
825 :
826 : METHODDEF(boolean)
827 0 : encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
828 : {
829 0 : huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
830 : int blkn, ci;
831 : jpeg_component_info *compptr;
832 :
833 : /* Take care of restart intervals if needed */
834 0 : if (cinfo->restart_interval) {
835 0 : if (entropy->restarts_to_go == 0) {
836 : /* Re-initialize DC predictions to 0 */
837 0 : for (ci = 0; ci < cinfo->comps_in_scan; ci++)
838 0 : entropy->saved.last_dc_val[ci] = 0;
839 : /* Update restart state */
840 0 : entropy->restarts_to_go = cinfo->restart_interval;
841 : }
842 0 : entropy->restarts_to_go--;
843 : }
844 :
845 0 : for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
846 0 : ci = cinfo->MCU_membership[blkn];
847 0 : compptr = cinfo->cur_comp_info[ci];
848 0 : htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
849 0 : entropy->dc_count_ptrs[compptr->dc_tbl_no],
850 0 : entropy->ac_count_ptrs[compptr->ac_tbl_no]);
851 0 : entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
852 : }
853 :
854 0 : return TRUE;
855 : }
856 :
857 :
858 : /*
859 : * Generate the best Huffman code table for the given counts, fill htbl.
860 : * Note this is also used by jcphuff.c.
861 : *
862 : * The JPEG standard requires that no symbol be assigned a codeword of all
863 : * one bits (so that padding bits added at the end of a compressed segment
864 : * can't look like a valid code). Because of the canonical ordering of
865 : * codewords, this just means that there must be an unused slot in the
866 : * longest codeword length category. Section K.2 of the JPEG spec suggests
867 : * reserving such a slot by pretending that symbol 256 is a valid symbol
868 : * with count 1. In theory that's not optimal; giving it count zero but
869 : * including it in the symbol set anyway should give a better Huffman code.
870 : * But the theoretically better code actually seems to come out worse in
871 : * practice, because it produces more all-ones bytes (which incur stuffed
872 : * zero bytes in the final file). In any case the difference is tiny.
873 : *
874 : * The JPEG standard requires Huffman codes to be no more than 16 bits long.
875 : * If some symbols have a very small but nonzero probability, the Huffman tree
876 : * must be adjusted to meet the code length restriction. We currently use
877 : * the adjustment method suggested in JPEG section K.2. This method is *not*
878 : * optimal; it may not choose the best possible limited-length code. But
879 : * typically only very-low-frequency symbols will be given less-than-optimal
880 : * lengths, so the code is almost optimal. Experimental comparisons against
881 : * an optimal limited-length-code algorithm indicate that the difference is
882 : * microscopic --- usually less than a hundredth of a percent of total size.
883 : * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
884 : */
885 :
886 : GLOBAL(void)
887 0 : jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[])
888 : {
889 : #define MAX_CLEN 32 /* assumed maximum initial code length */
890 : UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
891 : int codesize[257]; /* codesize[k] = code length of symbol k */
892 : int others[257]; /* next symbol in current branch of tree */
893 : int c1, c2;
894 : int p, i, j;
895 : long v;
896 :
897 : /* This algorithm is explained in section K.2 of the JPEG standard */
898 :
899 0 : MEMZERO(bits, sizeof(bits));
900 0 : MEMZERO(codesize, sizeof(codesize));
901 0 : for (i = 0; i < 257; i++)
902 0 : others[i] = -1; /* init links to empty */
903 :
904 0 : freq[256] = 1; /* make sure 256 has a nonzero count */
905 : /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
906 : * that no real symbol is given code-value of all ones, because 256
907 : * will be placed last in the largest codeword category.
908 : */
909 :
910 : /* Huffman's basic algorithm to assign optimal code lengths to symbols */
911 :
912 : for (;;) {
913 : /* Find the smallest nonzero frequency, set c1 = its symbol */
914 : /* In case of ties, take the larger symbol number */
915 0 : c1 = -1;
916 0 : v = 1000000000L;
917 0 : for (i = 0; i <= 256; i++) {
918 0 : if (freq[i] && freq[i] <= v) {
919 0 : v = freq[i];
920 0 : c1 = i;
921 : }
922 : }
923 :
924 : /* Find the next smallest nonzero frequency, set c2 = its symbol */
925 : /* In case of ties, take the larger symbol number */
926 0 : c2 = -1;
927 0 : v = 1000000000L;
928 0 : for (i = 0; i <= 256; i++) {
929 0 : if (freq[i] && freq[i] <= v && i != c1) {
930 0 : v = freq[i];
931 0 : c2 = i;
932 : }
933 : }
934 :
935 : /* Done if we've merged everything into one frequency */
936 0 : if (c2 < 0)
937 0 : break;
938 :
939 : /* Else merge the two counts/trees */
940 0 : freq[c1] += freq[c2];
941 0 : freq[c2] = 0;
942 :
943 : /* Increment the codesize of everything in c1's tree branch */
944 0 : codesize[c1]++;
945 0 : while (others[c1] >= 0) {
946 0 : c1 = others[c1];
947 0 : codesize[c1]++;
948 : }
949 :
950 0 : others[c1] = c2; /* chain c2 onto c1's tree branch */
951 :
952 : /* Increment the codesize of everything in c2's tree branch */
953 0 : codesize[c2]++;
954 0 : while (others[c2] >= 0) {
955 0 : c2 = others[c2];
956 0 : codesize[c2]++;
957 : }
958 : }
959 :
960 : /* Now count the number of symbols of each code length */
961 0 : for (i = 0; i <= 256; i++) {
962 0 : if (codesize[i]) {
963 : /* The JPEG standard seems to think that this can't happen, */
964 : /* but I'm paranoid... */
965 0 : if (codesize[i] > MAX_CLEN)
966 0 : ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
967 :
968 0 : bits[codesize[i]]++;
969 : }
970 : }
971 :
972 : /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
973 : * Huffman procedure assigned any such lengths, we must adjust the coding.
974 : * Here is what the JPEG spec says about how this next bit works:
975 : * Since symbols are paired for the longest Huffman code, the symbols are
976 : * removed from this length category two at a time. The prefix for the pair
977 : * (which is one bit shorter) is allocated to one of the pair; then,
978 : * skipping the BITS entry for that prefix length, a code word from the next
979 : * shortest nonzero BITS entry is converted into a prefix for two code words
980 : * one bit longer.
981 : */
982 :
983 0 : for (i = MAX_CLEN; i > 16; i--) {
984 0 : while (bits[i] > 0) {
985 0 : j = i - 2; /* find length of new prefix to be used */
986 0 : while (bits[j] == 0)
987 0 : j--;
988 :
989 0 : bits[i] -= 2; /* remove two symbols */
990 0 : bits[i-1]++; /* one goes in this length */
991 0 : bits[j+1] += 2; /* two new symbols in this length */
992 0 : bits[j]--; /* symbol of this length is now a prefix */
993 : }
994 : }
995 :
996 : /* Remove the count for the pseudo-symbol 256 from the largest codelength */
997 0 : while (bits[i] == 0) /* find largest codelength still in use */
998 0 : i--;
999 0 : bits[i]--;
1000 :
1001 : /* Return final symbol counts (only for lengths 0..16) */
1002 0 : MEMCOPY(htbl->bits, bits, sizeof(htbl->bits));
1003 :
1004 : /* Return a list of the symbols sorted by code length */
1005 : /* It's not real clear to me why we don't need to consider the codelength
1006 : * changes made above, but the JPEG spec seems to think this works.
1007 : */
1008 0 : p = 0;
1009 0 : for (i = 1; i <= MAX_CLEN; i++) {
1010 0 : for (j = 0; j <= 255; j++) {
1011 0 : if (codesize[j] == i) {
1012 0 : htbl->huffval[p] = (UINT8) j;
1013 0 : p++;
1014 : }
1015 : }
1016 : }
1017 :
1018 : /* Set sent_table FALSE so updated table will be written to JPEG file. */
1019 0 : htbl->sent_table = FALSE;
1020 0 : }
1021 :
1022 :
1023 : /*
1024 : * Finish up a statistics-gathering pass and create the new Huffman tables.
1025 : */
1026 :
1027 : METHODDEF(void)
1028 0 : finish_pass_gather (j_compress_ptr cinfo)
1029 : {
1030 0 : huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1031 : int ci, dctbl, actbl;
1032 : jpeg_component_info *compptr;
1033 : JHUFF_TBL **htblptr;
1034 : boolean did_dc[NUM_HUFF_TBLS];
1035 : boolean did_ac[NUM_HUFF_TBLS];
1036 :
1037 : /* It's important not to apply jpeg_gen_optimal_table more than once
1038 : * per table, because it clobbers the input frequency counts!
1039 : */
1040 0 : MEMZERO(did_dc, sizeof(did_dc));
1041 0 : MEMZERO(did_ac, sizeof(did_ac));
1042 :
1043 0 : for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1044 0 : compptr = cinfo->cur_comp_info[ci];
1045 0 : dctbl = compptr->dc_tbl_no;
1046 0 : actbl = compptr->ac_tbl_no;
1047 0 : if (! did_dc[dctbl]) {
1048 0 : htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
1049 0 : if (*htblptr == NULL)
1050 0 : *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1051 0 : jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
1052 0 : did_dc[dctbl] = TRUE;
1053 : }
1054 0 : if (! did_ac[actbl]) {
1055 0 : htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
1056 0 : if (*htblptr == NULL)
1057 0 : *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1058 0 : jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
1059 0 : did_ac[actbl] = TRUE;
1060 : }
1061 : }
1062 0 : }
1063 :
1064 :
1065 : #endif /* ENTROPY_OPT_SUPPORTED */
1066 :
1067 :
1068 : /*
1069 : * Module initialization routine for Huffman entropy encoding.
1070 : */
1071 :
1072 : GLOBAL(void)
1073 0 : jinit_huff_encoder (j_compress_ptr cinfo)
1074 : {
1075 : huff_entropy_ptr entropy;
1076 : int i;
1077 :
1078 0 : entropy = (huff_entropy_ptr)
1079 0 : (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1080 : sizeof(huff_entropy_encoder));
1081 0 : cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1082 0 : entropy->pub.start_pass = start_pass_huff;
1083 :
1084 : /* Mark tables unallocated */
1085 0 : for (i = 0; i < NUM_HUFF_TBLS; i++) {
1086 0 : entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1087 : #ifdef ENTROPY_OPT_SUPPORTED
1088 0 : entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
1089 : #endif
1090 : }
1091 0 : }
|
