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-2015 D. R. Commander.
8 * For conditions of distribution and use, see the accompanying README file.
10 * This file contains Huffman entropy encoding routines.
12 * Much of the complexity here has to do with supporting output suspension.
13 * If the data destination module demands suspension, we want to be able to
14 * back up to the start of the current MCU. To do this, we copy state
15 * variables into local working storage, and update them back to the
16 * permanent JPEG objects only upon successful completion of an MCU.
19 #define JPEG_INTERNALS
22 #include "jchuff.h" /* Declarations shared with jcphuff.c */
26 * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be
27 * used for bit counting rather than the lookup table. This will reduce the
28 * memory footprint by 64k, which is important for some mobile applications
29 * that create many isolated instances of libjpeg-turbo (web browsers, for
30 * instance.) This may improve performance on some mobile platforms as well.
31 * This feature is enabled by default only on ARM processors, because some x86
32 * chips have a slow implementation of bsr, and the use of clz/bsr cannot be
33 * shown to have a significant performance impact even on the x86 chips that
34 * have a fast implementation of it. When building for ARMv6, you can
35 * explicitly disable the use of clz/bsr by adding -mthumb to the compiler
36 * flags (this defines __thumb__).
39 /* NOTE: Both GCC and Clang define __GNUC__ */
40 #if defined __GNUC__ && (defined __arm__ || defined __aarch64__)
41 #if !defined __thumb__ || defined __thumb2__
42 #define USE_CLZ_INTRINSIC
46 #ifdef USE_CLZ_INTRINSIC
47 #define JPEG_NBITS_NONZERO(x) (32 - __builtin_clz(x))
48 #define JPEG_NBITS(x) (x ? JPEG_NBITS_NONZERO(x) : 0)
50 #include "jpeg_nbits_table.h"
51 #define JPEG_NBITS(x) (jpeg_nbits_table[x])
52 #define JPEG_NBITS_NONZERO(x) JPEG_NBITS(x)
56 #define min(a,b) ((a)<(b)?(a):(b))
60 /* Expanded entropy encoder object for Huffman encoding.
62 * The savable_state subrecord contains fields that change within an MCU,
63 * but must not be updated permanently until we complete the MCU.
67 size_t put_buffer; /* current bit-accumulation buffer */
68 int put_bits; /* # of bits now in it */
69 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
72 /* This macro is to work around compilers with missing or broken
73 * structure assignment. You'll need to fix this code if you have
74 * such a compiler and you change MAX_COMPS_IN_SCAN.
77 #ifndef NO_STRUCT_ASSIGN
78 #define ASSIGN_STATE(dest,src) ((dest) = (src))
80 #if MAX_COMPS_IN_SCAN == 4
81 #define ASSIGN_STATE(dest,src) \
82 ((dest).put_buffer = (src).put_buffer, \
83 (dest).put_bits = (src).put_bits, \
84 (dest).last_dc_val[0] = (src).last_dc_val[0], \
85 (dest).last_dc_val[1] = (src).last_dc_val[1], \
86 (dest).last_dc_val[2] = (src).last_dc_val[2], \
87 (dest).last_dc_val[3] = (src).last_dc_val[3])
93 struct jpeg_entropy_encoder pub; /* public fields */
95 savable_state saved; /* Bit buffer & DC state at start of MCU */
97 /* These fields are NOT loaded into local working state. */
98 unsigned int restarts_to_go; /* MCUs left in this restart interval */
99 int next_restart_num; /* next restart number to write (0-7) */
101 /* Pointers to derived tables (these workspaces have image lifespan) */
102 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
103 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
105 #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */
106 long * dc_count_ptrs[NUM_HUFF_TBLS];
107 long * ac_count_ptrs[NUM_HUFF_TBLS];
109 } huff_entropy_encoder;
111 typedef huff_entropy_encoder * huff_entropy_ptr;
113 /* Working state while writing an MCU.
114 * This struct contains all the fields that are needed by subroutines.
118 JOCTET * next_output_byte; /* => next byte to write in buffer */
119 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
120 savable_state cur; /* Current bit buffer & DC state */
121 j_compress_ptr cinfo; /* dump_buffer needs access to this */
125 /* Forward declarations */
126 METHODDEF(boolean) encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data);
127 METHODDEF(void) finish_pass_huff (j_compress_ptr cinfo);
128 #ifdef ENTROPY_OPT_SUPPORTED
129 METHODDEF(boolean) encode_mcu_gather (j_compress_ptr cinfo,
130 JBLOCKROW *MCU_data);
131 METHODDEF(void) finish_pass_gather (j_compress_ptr cinfo);
136 * Initialize for a Huffman-compressed scan.
137 * If gather_statistics is TRUE, we do not output anything during the scan,
138 * just count the Huffman symbols used and generate Huffman code tables.
142 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
144 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
145 int ci, dctbl, actbl;
146 jpeg_component_info * compptr;
148 if (gather_statistics) {
149 #ifdef ENTROPY_OPT_SUPPORTED
150 entropy->pub.encode_mcu = encode_mcu_gather;
151 entropy->pub.finish_pass = finish_pass_gather;
153 ERREXIT(cinfo, JERR_NOT_COMPILED);
156 entropy->pub.encode_mcu = encode_mcu_huff;
157 entropy->pub.finish_pass = finish_pass_huff;
160 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
161 compptr = cinfo->cur_comp_info[ci];
162 dctbl = compptr->dc_tbl_no;
163 actbl = compptr->ac_tbl_no;
164 if (gather_statistics) {
165 #ifdef ENTROPY_OPT_SUPPORTED
166 /* Check for invalid table indexes */
167 /* (make_c_derived_tbl does this in the other path) */
168 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
169 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
170 if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
171 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
172 /* Allocate and zero the statistics tables */
173 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
174 if (entropy->dc_count_ptrs[dctbl] == NULL)
175 entropy->dc_count_ptrs[dctbl] = (long *)
176 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
178 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * sizeof(long));
179 if (entropy->ac_count_ptrs[actbl] == NULL)
180 entropy->ac_count_ptrs[actbl] = (long *)
181 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
183 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * sizeof(long));
186 /* Compute derived values for Huffman tables */
187 /* We may do this more than once for a table, but it's not expensive */
188 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
189 & entropy->dc_derived_tbls[dctbl]);
190 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
191 & entropy->ac_derived_tbls[actbl]);
193 /* Initialize DC predictions to 0 */
194 entropy->saved.last_dc_val[ci] = 0;
197 /* Initialize bit buffer to empty */
198 entropy->saved.put_buffer = 0;
199 entropy->saved.put_bits = 0;
201 /* Initialize restart stuff */
202 entropy->restarts_to_go = cinfo->restart_interval;
203 entropy->next_restart_num = 0;
208 * Compute the derived values for a Huffman table.
209 * This routine also performs some validation checks on the table.
211 * Note this is also used by jcphuff.c.
215 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
216 c_derived_tbl ** pdtbl)
220 int p, i, l, lastp, si, maxsymbol;
222 unsigned int huffcode[257];
225 /* Note that huffsize[] and huffcode[] are filled in code-length order,
226 * paralleling the order of the symbols themselves in htbl->huffval[].
229 /* Find the input Huffman table */
230 if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
231 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
233 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
235 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
237 /* Allocate a workspace if we haven't already done so. */
239 *pdtbl = (c_derived_tbl *)
240 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
241 sizeof(c_derived_tbl));
244 /* Figure C.1: make table of Huffman code length for each symbol */
247 for (l = 1; l <= 16; l++) {
248 i = (int) htbl->bits[l];
249 if (i < 0 || p + i > 256) /* protect against table overrun */
250 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
252 huffsize[p++] = (char) l;
257 /* Figure C.2: generate the codes themselves */
258 /* We also validate that the counts represent a legal Huffman code tree. */
263 while (huffsize[p]) {
264 while (((int) huffsize[p]) == si) {
265 huffcode[p++] = code;
268 /* code is now 1 more than the last code used for codelength si; but
269 * it must still fit in si bits, since no code is allowed to be all ones.
271 if (((INT32) code) >= (((INT32) 1) << si))
272 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
277 /* Figure C.3: generate encoding tables */
278 /* These are code and size indexed by symbol value */
280 /* Set all codeless symbols to have code length 0;
281 * this lets us detect duplicate VAL entries here, and later
282 * allows emit_bits to detect any attempt to emit such symbols.
284 MEMZERO(dtbl->ehufsi, sizeof(dtbl->ehufsi));
286 /* This is also a convenient place to check for out-of-range
287 * and duplicated VAL entries. We allow 0..255 for AC symbols
288 * but only 0..15 for DC. (We could constrain them further
289 * based on data depth and mode, but this seems enough.)
291 maxsymbol = isDC ? 15 : 255;
293 for (p = 0; p < lastp; p++) {
294 i = htbl->huffval[p];
295 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
296 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
297 dtbl->ehufco[i] = huffcode[p];
298 dtbl->ehufsi[i] = huffsize[p];
303 /* Outputting bytes to the file */
305 /* Emit a byte, taking 'action' if must suspend. */
306 #define emit_byte(state,val,action) \
307 { *(state)->next_output_byte++ = (JOCTET) (val); \
308 if (--(state)->free_in_buffer == 0) \
309 if (! dump_buffer(state)) \
314 dump_buffer (working_state * state)
315 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
317 struct jpeg_destination_mgr * dest = state->cinfo->dest;
319 if (! (*dest->empty_output_buffer) (state->cinfo))
321 /* After a successful buffer dump, must reset buffer pointers */
322 state->next_output_byte = dest->next_output_byte;
323 state->free_in_buffer = dest->free_in_buffer;
328 /* Outputting bits to the file */
330 /* These macros perform the same task as the emit_bits() function in the
331 * original libjpeg code. In addition to reducing overhead by explicitly
332 * inlining the code, additional performance is achieved by taking into
333 * account the size of the bit buffer and waiting until it is almost full
334 * before emptying it. This mostly benefits 64-bit platforms, since 6
335 * bytes can be stored in a 64-bit bit buffer before it has to be emptied.
338 #define EMIT_BYTE() { \
341 c = (JOCTET)GETJOCTET(put_buffer >> put_bits); \
343 if (c == 0xFF) /* need to stuff a zero byte? */ \
347 #define PUT_BITS(code, size) { \
349 put_buffer = (put_buffer << size) | code; \
352 #define CHECKBUF15() { \
353 if (put_bits > 15) { \
359 #define CHECKBUF31() { \
360 if (put_bits > 31) { \
368 #define CHECKBUF47() { \
369 if (put_bits > 47) { \
379 #if !defined(_WIN32) && !defined(SIZEOF_SIZE_T)
380 #error Cannot determine word size
383 #if SIZEOF_SIZE_T==8 || defined(_WIN64)
385 #define EMIT_BITS(code, size) { \
387 PUT_BITS(code, size) \
390 #define EMIT_CODE(code, size) { \
391 temp2 &= (((INT32) 1)<<nbits) - 1; \
393 PUT_BITS(code, size) \
394 PUT_BITS(temp2, nbits) \
399 #define EMIT_BITS(code, size) { \
400 PUT_BITS(code, size) \
404 #define EMIT_CODE(code, size) { \
405 temp2 &= (((INT32) 1)<<nbits) - 1; \
406 PUT_BITS(code, size) \
408 PUT_BITS(temp2, nbits) \
415 /* Although it is exceedingly rare, it is possible for a Huffman-encoded
416 * coefficient block to be larger than the 128-byte unencoded block. For each
417 * of the 64 coefficients, PUT_BITS is invoked twice, and each invocation can
418 * theoretically store 16 bits (for a maximum of 2048 bits or 256 bytes per
419 * encoded block.) If, for instance, one artificially sets the AC
420 * coefficients to alternating values of 32767 and -32768 (using the JPEG
421 * scanning order-- 1, 8, 16, etc.), then this will produce an encoded block
422 * larger than 200 bytes.
424 #define BUFSIZE (DCTSIZE2 * 4)
426 #define LOAD_BUFFER() { \
427 if (state->free_in_buffer < BUFSIZE) { \
431 else buffer = state->next_output_byte; \
434 #define STORE_BUFFER() { \
436 bytes = buffer - _buffer; \
438 while (bytes > 0) { \
439 bytestocopy = min(bytes, state->free_in_buffer); \
440 MEMCOPY(state->next_output_byte, buffer, bytestocopy); \
441 state->next_output_byte += bytestocopy; \
442 buffer += bytestocopy; \
443 state->free_in_buffer -= bytestocopy; \
444 if (state->free_in_buffer == 0) \
445 if (! dump_buffer(state)) return FALSE; \
446 bytes -= bytestocopy; \
450 state->free_in_buffer -= (buffer - state->next_output_byte); \
451 state->next_output_byte = buffer; \
457 flush_bits (working_state * state)
459 JOCTET _buffer[BUFSIZE], *buffer;
460 size_t put_buffer; int put_bits;
461 size_t bytes, bytestocopy; int localbuf = 0;
463 put_buffer = state->cur.put_buffer;
464 put_bits = state->cur.put_bits;
467 /* fill any partial byte with ones */
469 while (put_bits >= 8) EMIT_BYTE()
471 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
472 state->cur.put_bits = 0;
479 /* Encode a single block's worth of coefficients */
482 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
483 c_derived_tbl *dctbl, c_derived_tbl *actbl)
485 int temp, temp2, temp3;
488 JOCTET _buffer[BUFSIZE], *buffer;
489 size_t put_buffer; int put_bits;
490 int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0];
491 size_t bytes, bytestocopy; int localbuf = 0;
493 put_buffer = state->cur.put_buffer;
494 put_bits = state->cur.put_bits;
497 /* Encode the DC coefficient difference per section F.1.2.1 */
499 temp = temp2 = block[0] - last_dc_val;
501 /* This is a well-known technique for obtaining the absolute value without a
502 * branch. It is derived from an assembly language technique presented in
503 * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by
506 temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
510 /* For a negative input, want temp2 = bitwise complement of abs(input) */
511 /* This code assumes we are on a two's complement machine */
514 /* Find the number of bits needed for the magnitude of the coefficient */
515 nbits = JPEG_NBITS(temp);
517 /* Emit the Huffman-coded symbol for the number of bits */
518 code = dctbl->ehufco[nbits];
519 size = dctbl->ehufsi[nbits];
520 EMIT_BITS(code, size)
522 /* Mask off any extra bits in code */
523 temp2 &= (((INT32) 1)<<nbits) - 1;
525 /* Emit that number of bits of the value, if positive, */
526 /* or the complement of its magnitude, if negative. */
527 EMIT_BITS(temp2, nbits)
529 /* Encode the AC coefficients per section F.1.2.2 */
531 r = 0; /* r = run length of zeros */
533 /* Manually unroll the k loop to eliminate the counter variable. This
534 * improves performance greatly on systems with a limited number of
535 * registers (such as x86.)
537 #define kloop(jpeg_natural_order_of_k) { \
538 if ((temp = block[jpeg_natural_order_of_k]) == 0) { \
542 /* Branch-less absolute value, bitwise complement, etc., same as above */ \
543 temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); \
547 nbits = JPEG_NBITS_NONZERO(temp); \
548 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \
550 EMIT_BITS(code_0xf0, size_0xf0) \
553 /* Emit Huffman symbol for run length / number of bits */ \
554 temp3 = (r << 4) + nbits; \
555 code = actbl->ehufco[temp3]; \
556 size = actbl->ehufsi[temp3]; \
557 EMIT_CODE(code, size) \
562 /* One iteration for each value in jpeg_natural_order[] */
563 kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3);
564 kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18);
565 kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26);
566 kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27);
567 kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21);
568 kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57);
569 kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15);
570 kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58);
571 kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39);
572 kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47);
573 kloop(55); kloop(62); kloop(63);
575 /* If the last coef(s) were zero, emit an end-of-block code */
577 code = actbl->ehufco[0];
578 size = actbl->ehufsi[0];
579 EMIT_BITS(code, size)
582 state->cur.put_buffer = put_buffer;
583 state->cur.put_bits = put_bits;
591 * Emit a restart marker & resynchronize predictions.
595 emit_restart (working_state * state, int restart_num)
599 if (! flush_bits(state))
602 emit_byte(state, 0xFF, return FALSE);
603 emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
605 /* Re-initialize DC predictions to 0 */
606 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
607 state->cur.last_dc_val[ci] = 0;
609 /* The restart counter is not updated until we successfully write the MCU. */
616 * Encode and output one MCU's worth of Huffman-compressed coefficients.
620 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
622 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
625 jpeg_component_info * compptr;
627 /* Load up working state */
628 state.next_output_byte = cinfo->dest->next_output_byte;
629 state.free_in_buffer = cinfo->dest->free_in_buffer;
630 ASSIGN_STATE(state.cur, entropy->saved);
633 /* Emit restart marker if needed */
634 if (cinfo->restart_interval) {
635 if (entropy->restarts_to_go == 0)
636 if (! emit_restart(&state, entropy->next_restart_num))
640 /* Encode the MCU data blocks */
641 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
642 ci = cinfo->MCU_membership[blkn];
643 compptr = cinfo->cur_comp_info[ci];
644 if (! encode_one_block(&state,
645 MCU_data[blkn][0], state.cur.last_dc_val[ci],
646 entropy->dc_derived_tbls[compptr->dc_tbl_no],
647 entropy->ac_derived_tbls[compptr->ac_tbl_no]))
649 /* Update last_dc_val */
650 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
653 /* Completed MCU, so update state */
654 cinfo->dest->next_output_byte = state.next_output_byte;
655 cinfo->dest->free_in_buffer = state.free_in_buffer;
656 ASSIGN_STATE(entropy->saved, state.cur);
658 /* Update restart-interval state too */
659 if (cinfo->restart_interval) {
660 if (entropy->restarts_to_go == 0) {
661 entropy->restarts_to_go = cinfo->restart_interval;
662 entropy->next_restart_num++;
663 entropy->next_restart_num &= 7;
665 entropy->restarts_to_go--;
673 * Finish up at the end of a Huffman-compressed scan.
677 finish_pass_huff (j_compress_ptr cinfo)
679 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
682 /* Load up working state ... flush_bits needs it */
683 state.next_output_byte = cinfo->dest->next_output_byte;
684 state.free_in_buffer = cinfo->dest->free_in_buffer;
685 ASSIGN_STATE(state.cur, entropy->saved);
688 /* Flush out the last data */
689 if (! flush_bits(&state))
690 ERREXIT(cinfo, JERR_CANT_SUSPEND);
693 cinfo->dest->next_output_byte = state.next_output_byte;
694 cinfo->dest->free_in_buffer = state.free_in_buffer;
695 ASSIGN_STATE(entropy->saved, state.cur);
700 * Huffman coding optimization.
702 * We first scan the supplied data and count the number of uses of each symbol
703 * that is to be Huffman-coded. (This process MUST agree with the code above.)
704 * Then we build a Huffman coding tree for the observed counts.
705 * Symbols which are not needed at all for the particular image are not
706 * assigned any code, which saves space in the DHT marker as well as in
707 * the compressed data.
710 #ifdef ENTROPY_OPT_SUPPORTED
713 /* Process a single block's worth of coefficients */
716 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
717 long dc_counts[], long ac_counts[])
723 /* Encode the DC coefficient difference per section F.1.2.1 */
725 temp = block[0] - last_dc_val;
729 /* Find the number of bits needed for the magnitude of the coefficient */
735 /* Check for out-of-range coefficient values.
736 * Since we're encoding a difference, the range limit is twice as much.
738 if (nbits > MAX_COEF_BITS+1)
739 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
741 /* Count the Huffman symbol for the number of bits */
744 /* Encode the AC coefficients per section F.1.2.2 */
746 r = 0; /* r = run length of zeros */
748 for (k = 1; k < DCTSIZE2; k++) {
749 if ((temp = block[jpeg_natural_order[k]]) == 0) {
752 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
758 /* Find the number of bits needed for the magnitude of the coefficient */
762 /* Find the number of bits needed for the magnitude of the coefficient */
763 nbits = 1; /* there must be at least one 1 bit */
766 /* Check for out-of-range coefficient values */
767 if (nbits > MAX_COEF_BITS)
768 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
770 /* Count Huffman symbol for run length / number of bits */
771 ac_counts[(r << 4) + nbits]++;
777 /* If the last coef(s) were zero, emit an end-of-block code */
784 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
785 * No data is actually output, so no suspension return is possible.
789 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
791 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
793 jpeg_component_info * compptr;
795 /* Take care of restart intervals if needed */
796 if (cinfo->restart_interval) {
797 if (entropy->restarts_to_go == 0) {
798 /* Re-initialize DC predictions to 0 */
799 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
800 entropy->saved.last_dc_val[ci] = 0;
801 /* Update restart state */
802 entropy->restarts_to_go = cinfo->restart_interval;
804 entropy->restarts_to_go--;
807 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
808 ci = cinfo->MCU_membership[blkn];
809 compptr = cinfo->cur_comp_info[ci];
810 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
811 entropy->dc_count_ptrs[compptr->dc_tbl_no],
812 entropy->ac_count_ptrs[compptr->ac_tbl_no]);
813 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
821 * Generate the best Huffman code table for the given counts, fill htbl.
822 * Note this is also used by jcphuff.c.
824 * The JPEG standard requires that no symbol be assigned a codeword of all
825 * one bits (so that padding bits added at the end of a compressed segment
826 * can't look like a valid code). Because of the canonical ordering of
827 * codewords, this just means that there must be an unused slot in the
828 * longest codeword length category. Section K.2 of the JPEG spec suggests
829 * reserving such a slot by pretending that symbol 256 is a valid symbol
830 * with count 1. In theory that's not optimal; giving it count zero but
831 * including it in the symbol set anyway should give a better Huffman code.
832 * But the theoretically better code actually seems to come out worse in
833 * practice, because it produces more all-ones bytes (which incur stuffed
834 * zero bytes in the final file). In any case the difference is tiny.
836 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
837 * If some symbols have a very small but nonzero probability, the Huffman tree
838 * must be adjusted to meet the code length restriction. We currently use
839 * the adjustment method suggested in JPEG section K.2. This method is *not*
840 * optimal; it may not choose the best possible limited-length code. But
841 * typically only very-low-frequency symbols will be given less-than-optimal
842 * lengths, so the code is almost optimal. Experimental comparisons against
843 * an optimal limited-length-code algorithm indicate that the difference is
844 * microscopic --- usually less than a hundredth of a percent of total size.
845 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
849 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[])
851 #define MAX_CLEN 32 /* assumed maximum initial code length */
852 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
853 int codesize[257]; /* codesize[k] = code length of symbol k */
854 int others[257]; /* next symbol in current branch of tree */
859 /* This algorithm is explained in section K.2 of the JPEG standard */
861 MEMZERO(bits, sizeof(bits));
862 MEMZERO(codesize, sizeof(codesize));
863 for (i = 0; i < 257; i++)
864 others[i] = -1; /* init links to empty */
866 freq[256] = 1; /* make sure 256 has a nonzero count */
867 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
868 * that no real symbol is given code-value of all ones, because 256
869 * will be placed last in the largest codeword category.
872 /* Huffman's basic algorithm to assign optimal code lengths to symbols */
875 /* Find the smallest nonzero frequency, set c1 = its symbol */
876 /* In case of ties, take the larger symbol number */
879 for (i = 0; i <= 256; i++) {
880 if (freq[i] && freq[i] <= v) {
886 /* Find the next smallest nonzero frequency, set c2 = its symbol */
887 /* In case of ties, take the larger symbol number */
890 for (i = 0; i <= 256; i++) {
891 if (freq[i] && freq[i] <= v && i != c1) {
897 /* Done if we've merged everything into one frequency */
901 /* Else merge the two counts/trees */
902 freq[c1] += freq[c2];
905 /* Increment the codesize of everything in c1's tree branch */
907 while (others[c1] >= 0) {
912 others[c1] = c2; /* chain c2 onto c1's tree branch */
914 /* Increment the codesize of everything in c2's tree branch */
916 while (others[c2] >= 0) {
922 /* Now count the number of symbols of each code length */
923 for (i = 0; i <= 256; i++) {
925 /* The JPEG standard seems to think that this can't happen, */
926 /* but I'm paranoid... */
927 if (codesize[i] > MAX_CLEN)
928 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
934 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
935 * Huffman procedure assigned any such lengths, we must adjust the coding.
936 * Here is what the JPEG spec says about how this next bit works:
937 * Since symbols are paired for the longest Huffman code, the symbols are
938 * removed from this length category two at a time. The prefix for the pair
939 * (which is one bit shorter) is allocated to one of the pair; then,
940 * skipping the BITS entry for that prefix length, a code word from the next
941 * shortest nonzero BITS entry is converted into a prefix for two code words
945 for (i = MAX_CLEN; i > 16; i--) {
946 while (bits[i] > 0) {
947 j = i - 2; /* find length of new prefix to be used */
951 bits[i] -= 2; /* remove two symbols */
952 bits[i-1]++; /* one goes in this length */
953 bits[j+1] += 2; /* two new symbols in this length */
954 bits[j]--; /* symbol of this length is now a prefix */
958 /* Remove the count for the pseudo-symbol 256 from the largest codelength */
959 while (bits[i] == 0) /* find largest codelength still in use */
963 /* Return final symbol counts (only for lengths 0..16) */
964 MEMCOPY(htbl->bits, bits, sizeof(htbl->bits));
966 /* Return a list of the symbols sorted by code length */
967 /* It's not real clear to me why we don't need to consider the codelength
968 * changes made above, but the JPEG spec seems to think this works.
971 for (i = 1; i <= MAX_CLEN; i++) {
972 for (j = 0; j <= 255; j++) {
973 if (codesize[j] == i) {
974 htbl->huffval[p] = (UINT8) j;
980 /* Set sent_table FALSE so updated table will be written to JPEG file. */
981 htbl->sent_table = FALSE;
986 * Finish up a statistics-gathering pass and create the new Huffman tables.
990 finish_pass_gather (j_compress_ptr cinfo)
992 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
993 int ci, dctbl, actbl;
994 jpeg_component_info * compptr;
996 boolean did_dc[NUM_HUFF_TBLS];
997 boolean did_ac[NUM_HUFF_TBLS];
999 /* It's important not to apply jpeg_gen_optimal_table more than once
1000 * per table, because it clobbers the input frequency counts!
1002 MEMZERO(did_dc, sizeof(did_dc));
1003 MEMZERO(did_ac, sizeof(did_ac));
1005 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1006 compptr = cinfo->cur_comp_info[ci];
1007 dctbl = compptr->dc_tbl_no;
1008 actbl = compptr->ac_tbl_no;
1009 if (! did_dc[dctbl]) {
1010 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
1011 if (*htblptr == NULL)
1012 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1013 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
1014 did_dc[dctbl] = TRUE;
1016 if (! did_ac[actbl]) {
1017 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
1018 if (*htblptr == NULL)
1019 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1020 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
1021 did_ac[actbl] = TRUE;
1027 #endif /* ENTROPY_OPT_SUPPORTED */
1031 * Module initialization routine for Huffman entropy encoding.
1035 jinit_huff_encoder (j_compress_ptr cinfo)
1037 huff_entropy_ptr entropy;
1040 entropy = (huff_entropy_ptr)
1041 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1042 sizeof(huff_entropy_encoder));
1043 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1044 entropy->pub.start_pass = start_pass_huff;
1046 /* Mark tables unallocated */
1047 for (i = 0; i < NUM_HUFF_TBLS; i++) {
1048 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1049 #ifdef ENTROPY_OPT_SUPPORTED
1050 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;