4 * Copyright (C) 1991-1997, Thomas G. Lane.
5 * Modified 2006-2023 by Guido Vollbeding.
6 * This file is part of the Independent JPEG Group's software.
7 * For conditions of distribution and use, see the accompanying README file.
9 * This file contains Huffman entropy encoding routines.
10 * Both sequential and progressive modes are supported in this single module.
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.
18 * We do not support output suspension for the progressive JPEG mode, since
19 * the library currently does not allow multiple-scan files to be written
20 * with output suspension.
23 #define JPEG_INTERNALS
28 /* The legal range of a DCT coefficient is
29 * -1024 .. +1023 for 8-bit sample data precision;
30 * -16384 .. +16383 for 12-bit sample data precision.
31 * Hence the magnitude should always fit in sample data precision + 2 bits.
34 /* Derived data constructed for each Huffman table */
37 unsigned int ehufco
[256]; /* code for each symbol */
38 char ehufsi
[256]; /* length of code for each symbol */
39 /* If no code has been allocated for a symbol S, ehufsi[S] contains 0 */
43 /* Expanded entropy encoder object for Huffman encoding.
45 * The savable_state subrecord contains fields that change within an MCU,
46 * but must not be updated permanently until we complete the MCU.
50 INT32 put_buffer
; /* current bit-accumulation buffer */
51 int put_bits
; /* # of bits now in it */
52 int last_dc_val
[MAX_COMPS_IN_SCAN
]; /* last DC coef for each component */
55 /* This macro is to work around compilers with missing or broken
56 * structure assignment. You'll need to fix this code if you have
57 * such a compiler and you change MAX_COMPS_IN_SCAN.
60 #ifndef NO_STRUCT_ASSIGN
61 #define ASSIGN_STATE(dest,src) ((dest) = (src))
63 #if MAX_COMPS_IN_SCAN == 4
64 #define ASSIGN_STATE(dest,src) \
65 ((dest).put_buffer = (src).put_buffer, \
66 (dest).put_bits = (src).put_bits, \
67 (dest).last_dc_val[0] = (src).last_dc_val[0], \
68 (dest).last_dc_val[1] = (src).last_dc_val[1], \
69 (dest).last_dc_val[2] = (src).last_dc_val[2], \
70 (dest).last_dc_val[3] = (src).last_dc_val[3])
76 struct jpeg_entropy_encoder pub
; /* public fields */
78 savable_state saved
; /* Bit buffer & DC state at start of MCU */
80 /* These fields are NOT loaded into local working state. */
81 unsigned int restarts_to_go
; /* MCUs left in this restart interval */
82 int next_restart_num
; /* next restart number to write (0-7) */
84 /* Pointers to derived tables (these workspaces have image lifespan) */
85 c_derived_tbl
* dc_derived_tbls
[NUM_HUFF_TBLS
];
86 c_derived_tbl
* ac_derived_tbls
[NUM_HUFF_TBLS
];
88 /* Statistics tables for optimization */
89 long * dc_count_ptrs
[NUM_HUFF_TBLS
];
90 long * ac_count_ptrs
[NUM_HUFF_TBLS
];
92 /* Following fields used only in progressive mode */
94 /* Mode flag: TRUE for optimization, FALSE for actual data output */
95 boolean gather_statistics
;
97 /* next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
99 JOCTET
* next_output_byte
; /* => next byte to write in buffer */
100 size_t free_in_buffer
; /* # of byte spaces remaining in buffer */
101 j_compress_ptr cinfo
; /* link to cinfo (needed for dump_buffer) */
103 /* Coding status for AC components */
104 int ac_tbl_no
; /* the table number of the single component */
105 unsigned int EOBRUN
; /* run length of EOBs */
106 unsigned int BE
; /* # of buffered correction bits before MCU */
107 char * bit_buffer
; /* buffer for correction bits (1 per char) */
108 /* packing correction bits tightly would save some space but cost time... */
109 } huff_entropy_encoder
;
111 typedef huff_entropy_encoder
* huff_entropy_ptr
;
113 /* Working state while writing an MCU (sequential mode).
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 */
124 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
125 * buffer can hold. Larger sizes may slightly improve compression, but
126 * 1000 is already well into the realm of overkill.
127 * The minimum safe size is 64 bits.
130 #define MAX_CORR_BITS 1000 /* Max # of correction bits I can buffer */
132 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
133 * We assume that int right shift is unsigned if INT32 right shift is,
134 * which should be safe.
137 #ifdef RIGHT_SHIFT_IS_UNSIGNED
138 #define ISHIFT_TEMPS int ishift_temp;
139 #define IRIGHT_SHIFT(x,shft) \
140 ((ishift_temp = (x)) < 0 ? \
141 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
142 (ishift_temp >> (shft)))
145 #define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
150 * Compute the derived values for a Huffman table.
151 * This routine also performs some validation checks on the table.
155 jpeg_make_c_derived_tbl (j_compress_ptr cinfo
, boolean isDC
, int tblno
,
156 c_derived_tbl
** pdtbl
)
160 int p
, i
, l
, lastp
, si
, maxsymbol
;
162 unsigned int huffcode
[257];
165 /* Note that huffsize[] and huffcode[] are filled in code-length order,
166 * paralleling the order of the symbols themselves in htbl->huffval[].
169 /* Find the input Huffman table */
170 if (tblno
< 0 || tblno
>= NUM_HUFF_TBLS
)
171 ERREXIT1(cinfo
, JERR_NO_HUFF_TABLE
, tblno
);
173 isDC
? cinfo
->dc_huff_tbl_ptrs
[tblno
] : cinfo
->ac_huff_tbl_ptrs
[tblno
];
175 htbl
= jpeg_std_huff_table((j_common_ptr
) cinfo
, isDC
, tblno
);
177 /* Allocate a workspace if we haven't already done so. */
179 *pdtbl
= (c_derived_tbl
*) (*cinfo
->mem
->alloc_small
)
180 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, SIZEOF(c_derived_tbl
));
183 /* Figure C.1: make table of Huffman code length for each symbol */
186 for (l
= 1; l
<= 16; l
++) {
187 i
= (int) htbl
->bits
[l
];
188 if (i
< 0 || p
+ i
> 256) /* protect against table overrun */
189 ERREXIT(cinfo
, JERR_BAD_HUFF_TABLE
);
191 huffsize
[p
++] = (char) l
;
196 /* Figure C.2: generate the codes themselves */
197 /* We also validate that the counts represent a legal Huffman code tree. */
202 while (huffsize
[p
]) {
203 while (((int) huffsize
[p
]) == si
) {
204 huffcode
[p
++] = code
;
207 /* code is now 1 more than the last code used for codelength si; but
208 * it must still fit in si bits, since no code is allowed to be all ones.
210 if (((INT32
) code
) >= (((INT32
) 1) << si
))
211 ERREXIT(cinfo
, JERR_BAD_HUFF_TABLE
);
216 /* Figure C.3: generate encoding tables */
217 /* These are code and size indexed by symbol value */
219 /* Set all codeless symbols to have code length 0;
220 * this lets us detect duplicate VAL entries here, and later
221 * allows emit_bits to detect any attempt to emit such symbols.
223 MEMZERO(dtbl
->ehufsi
, SIZEOF(dtbl
->ehufsi
));
225 /* This is also a convenient place to check for out-of-range
226 * and duplicated VAL entries. We allow 0..255 for AC symbols
227 * but only 0..15 for DC. (We could constrain them further
228 * based on data depth and mode, but this seems enough.)
230 maxsymbol
= isDC
? 15 : 255;
232 for (p
= 0; p
< lastp
; p
++) {
233 i
= htbl
->huffval
[p
];
234 if (i
< 0 || i
> maxsymbol
|| dtbl
->ehufsi
[i
])
235 ERREXIT(cinfo
, JERR_BAD_HUFF_TABLE
);
236 dtbl
->ehufco
[i
] = huffcode
[p
];
237 dtbl
->ehufsi
[i
] = huffsize
[p
];
242 /* Outputting bytes to the file.
243 * NB: these must be called only when actually outputting,
244 * that is, entropy->gather_statistics == FALSE.
247 /* Emit a byte, taking 'action' if must suspend. */
248 #define emit_byte_s(state,val,action) \
249 { *(state)->next_output_byte++ = (JOCTET) (val); \
250 if (--(state)->free_in_buffer == 0) \
251 if (! dump_buffer_s(state)) \
255 #define emit_byte_e(entropy,val) \
256 { *(entropy)->next_output_byte++ = (JOCTET) (val); \
257 if (--(entropy)->free_in_buffer == 0) \
258 dump_buffer_e(entropy); }
262 dump_buffer_s (working_state
* state
)
263 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
265 struct jpeg_destination_mgr
* dest
= state
->cinfo
->dest
;
267 if (! (*dest
->empty_output_buffer
) (state
->cinfo
))
269 /* After a successful buffer dump, must reset buffer pointers */
270 state
->next_output_byte
= dest
->next_output_byte
;
271 state
->free_in_buffer
= dest
->free_in_buffer
;
277 dump_buffer_e (huff_entropy_ptr entropy
)
278 /* Empty the output buffer; we do not support suspension in this case. */
280 struct jpeg_destination_mgr
* dest
= entropy
->cinfo
->dest
;
282 if (! (*dest
->empty_output_buffer
) (entropy
->cinfo
))
283 ERREXIT(entropy
->cinfo
, JERR_CANT_SUSPEND
);
284 /* After a successful buffer dump, must reset buffer pointers */
285 entropy
->next_output_byte
= dest
->next_output_byte
;
286 entropy
->free_in_buffer
= dest
->free_in_buffer
;
290 /* Outputting bits to the file */
292 /* Only the right 24 bits of put_buffer are used; the valid bits are
293 * left-justified in this part. At most 16 bits can be passed to emit_bits
294 * in one call, and we never retain more than 7 bits in put_buffer
295 * between calls, so 24 bits are sufficient.
300 emit_bits_s (working_state
* state
, unsigned int code
, int size
)
301 /* Emit some bits; return TRUE if successful, FALSE if must suspend */
303 /* This routine is heavily used, so it's worth coding tightly. */
304 register INT32 put_buffer
;
305 register int put_bits
;
307 /* if size is 0, caller used an invalid Huffman table entry */
309 ERREXIT(state
->cinfo
, JERR_HUFF_MISSING_CODE
);
311 /* mask off any extra bits in code */
312 put_buffer
= ((INT32
) code
) & ((((INT32
) 1) << size
) - 1);
314 /* new number of bits in buffer */
315 put_bits
= size
+ state
->cur
.put_bits
;
317 put_buffer
<<= 24 - put_bits
; /* align incoming bits */
319 /* and merge with old buffer contents */
320 put_buffer
|= state
->cur
.put_buffer
;
322 while (put_bits
>= 8) {
323 int c
= (int) ((put_buffer
>> 16) & 0xFF);
325 emit_byte_s(state
, c
, return FALSE
);
326 if (c
== 0xFF) { /* need to stuff a zero byte? */
327 emit_byte_s(state
, 0, return FALSE
);
333 state
->cur
.put_buffer
= put_buffer
; /* update state variables */
334 state
->cur
.put_bits
= put_bits
;
342 emit_bits_e (huff_entropy_ptr entropy
, unsigned int code
, int size
)
343 /* Emit some bits, unless we are in gather mode */
345 /* This routine is heavily used, so it's worth coding tightly. */
346 register INT32 put_buffer
;
347 register int put_bits
;
349 /* if size is 0, caller used an invalid Huffman table entry */
351 ERREXIT(entropy
->cinfo
, JERR_HUFF_MISSING_CODE
);
353 if (entropy
->gather_statistics
)
354 return; /* do nothing if we're only getting stats */
356 /* mask off any extra bits in code */
357 put_buffer
= ((INT32
) code
) & ((((INT32
) 1) << size
) - 1);
359 /* new number of bits in buffer */
360 put_bits
= size
+ entropy
->saved
.put_bits
;
362 put_buffer
<<= 24 - put_bits
; /* align incoming bits */
364 /* and merge with old buffer contents */
365 put_buffer
|= entropy
->saved
.put_buffer
;
367 while (put_bits
>= 8) {
368 int c
= (int) ((put_buffer
>> 16) & 0xFF);
370 emit_byte_e(entropy
, c
);
371 if (c
== 0xFF) { /* need to stuff a zero byte? */
372 emit_byte_e(entropy
, 0);
378 entropy
->saved
.put_buffer
= put_buffer
; /* update variables */
379 entropy
->saved
.put_bits
= put_bits
;
384 flush_bits_s (working_state
* state
)
386 if (! emit_bits_s(state
, 0x7F, 7)) /* fill any partial byte with ones */
388 state
->cur
.put_buffer
= 0; /* and reset bit-buffer to empty */
389 state
->cur
.put_bits
= 0;
395 flush_bits_e (huff_entropy_ptr entropy
)
397 emit_bits_e(entropy
, 0x7F, 7); /* fill any partial byte with ones */
398 entropy
->saved
.put_buffer
= 0; /* and reset bit-buffer to empty */
399 entropy
->saved
.put_bits
= 0;
404 * Emit (or just count) a Huffman symbol.
409 emit_dc_symbol (huff_entropy_ptr entropy
, int tbl_no
, int symbol
)
411 if (entropy
->gather_statistics
)
412 entropy
->dc_count_ptrs
[tbl_no
][symbol
]++;
414 c_derived_tbl
* tbl
= entropy
->dc_derived_tbls
[tbl_no
];
415 emit_bits_e(entropy
, tbl
->ehufco
[symbol
], tbl
->ehufsi
[symbol
]);
422 emit_ac_symbol (huff_entropy_ptr entropy
, int tbl_no
, int symbol
)
424 if (entropy
->gather_statistics
)
425 entropy
->ac_count_ptrs
[tbl_no
][symbol
]++;
427 c_derived_tbl
* tbl
= entropy
->ac_derived_tbls
[tbl_no
];
428 emit_bits_e(entropy
, tbl
->ehufco
[symbol
], tbl
->ehufsi
[symbol
]);
434 * Emit bits from a correction bit buffer.
438 emit_buffered_bits (huff_entropy_ptr entropy
, char * bufstart
,
441 if (entropy
->gather_statistics
)
442 return; /* no real work */
445 emit_bits_e(entropy
, (unsigned int) (*bufstart
), 1);
453 * Emit any pending EOBRUN symbol.
457 emit_eobrun (huff_entropy_ptr entropy
)
459 register int temp
, nbits
;
461 if (entropy
->EOBRUN
> 0) { /* if there is any pending EOBRUN */
462 temp
= entropy
->EOBRUN
;
466 /* safety check: shouldn't happen given limited correction-bit buffer */
468 ERREXIT(entropy
->cinfo
, JERR_HUFF_MISSING_CODE
);
470 emit_ac_symbol(entropy
, entropy
->ac_tbl_no
, nbits
<< 4);
472 emit_bits_e(entropy
, entropy
->EOBRUN
, nbits
);
476 /* Emit any buffered correction bits */
477 emit_buffered_bits(entropy
, entropy
->bit_buffer
, entropy
->BE
);
484 * Emit a restart marker & resynchronize predictions.
488 emit_restart_s (working_state
* state
, int restart_num
)
492 if (! flush_bits_s(state
))
495 emit_byte_s(state
, 0xFF, return FALSE
);
496 emit_byte_s(state
, JPEG_RST0
+ restart_num
, return FALSE
);
498 /* Re-initialize DC predictions to 0 */
499 for (ci
= 0; ci
< state
->cinfo
->comps_in_scan
; ci
++)
500 state
->cur
.last_dc_val
[ci
] = 0;
502 /* The restart counter is not updated until we successfully write the MCU. */
509 emit_restart_e (huff_entropy_ptr entropy
, int restart_num
)
513 emit_eobrun(entropy
);
515 if (! entropy
->gather_statistics
) {
516 flush_bits_e(entropy
);
517 emit_byte_e(entropy
, 0xFF);
518 emit_byte_e(entropy
, JPEG_RST0
+ restart_num
);
521 if (entropy
->cinfo
->Ss
== 0) {
522 /* Re-initialize DC predictions to 0 */
523 for (ci
= 0; ci
< entropy
->cinfo
->comps_in_scan
; ci
++)
524 entropy
->saved
.last_dc_val
[ci
] = 0;
526 /* Re-initialize all AC-related fields to 0 */
534 * MCU encoding for DC initial scan (either spectral selection,
535 * or first pass of successive approximation).
539 encode_mcu_DC_first (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
541 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
542 register int temp
, temp2
;
548 entropy
->next_output_byte
= cinfo
->dest
->next_output_byte
;
549 entropy
->free_in_buffer
= cinfo
->dest
->free_in_buffer
;
551 /* Emit restart marker if needed */
552 if (cinfo
->restart_interval
)
553 if (entropy
->restarts_to_go
== 0)
554 emit_restart_e(entropy
, entropy
->next_restart_num
);
556 /* Since we're encoding a difference, the range limit is twice as much. */
557 max_coef_bits
= cinfo
->data_precision
+ 3;
559 /* Encode the MCU data blocks */
560 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
561 ci
= cinfo
->MCU_membership
[blkn
];
562 tbl
= cinfo
->cur_comp_info
[ci
]->dc_tbl_no
;
564 /* Compute the DC value after the required point transform by Al.
565 * This is simply an arithmetic right shift.
567 temp
= IRIGHT_SHIFT((int) (MCU_data
[blkn
][0][0]), cinfo
->Al
);
569 /* DC differences are figured on the point-transformed values. */
570 if ((temp2
= temp
- entropy
->saved
.last_dc_val
[ci
]) == 0) {
571 /* Count/emit the Huffman-coded symbol for the number of bits */
572 emit_dc_symbol(entropy
, tbl
, 0);
577 entropy
->saved
.last_dc_val
[ci
] = temp
;
579 /* Encode the DC coefficient difference per section G.1.2.1 */
580 if ((temp
= temp2
) < 0) {
581 temp
= -temp
; /* temp is abs value of input */
582 /* For a negative input, want temp2 = bitwise complement of abs(input) */
583 /* This code assumes we are on a two's complement machine */
587 /* Find the number of bits needed for the magnitude of the coefficient */
589 do nbits
++; /* there must be at least one 1 bit */
590 while ((temp
>>= 1));
591 /* Check for out-of-range coefficient values */
592 if (nbits
> max_coef_bits
)
593 ERREXIT(cinfo
, JERR_BAD_DCT_COEF
);
595 /* Count/emit the Huffman-coded symbol for the number of bits */
596 emit_dc_symbol(entropy
, tbl
, nbits
);
598 /* Emit that number of bits of the value, if positive, */
599 /* or the complement of its magnitude, if negative. */
600 emit_bits_e(entropy
, (unsigned int) temp2
, nbits
);
603 cinfo
->dest
->next_output_byte
= entropy
->next_output_byte
;
604 cinfo
->dest
->free_in_buffer
= entropy
->free_in_buffer
;
606 /* Update restart-interval state too */
607 if (cinfo
->restart_interval
) {
608 if (entropy
->restarts_to_go
== 0) {
609 entropy
->restarts_to_go
= cinfo
->restart_interval
;
610 entropy
->next_restart_num
++;
611 entropy
->next_restart_num
&= 7;
613 entropy
->restarts_to_go
--;
621 * MCU encoding for AC initial scan (either spectral selection,
622 * or first pass of successive approximation).
626 encode_mcu_AC_first (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
628 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
629 const int * natural_order
;
631 register int temp
, temp2
;
634 int Se
, Al
, max_coef_bits
;
636 entropy
->next_output_byte
= cinfo
->dest
->next_output_byte
;
637 entropy
->free_in_buffer
= cinfo
->dest
->free_in_buffer
;
639 /* Emit restart marker if needed */
640 if (cinfo
->restart_interval
)
641 if (entropy
->restarts_to_go
== 0)
642 emit_restart_e(entropy
, entropy
->next_restart_num
);
646 natural_order
= cinfo
->natural_order
;
647 max_coef_bits
= cinfo
->data_precision
+ 2;
649 /* Encode the MCU data block */
652 /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
654 r
= 0; /* r = run length of zeros */
656 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
657 if ((temp
= (*block
)[natural_order
[k
]]) == 0) {
661 /* We must apply the point transform by Al. For AC coefficients this
662 * is an integer division with rounding towards 0. To do this portably
663 * in C, we shift after obtaining the absolute value; so the code is
664 * interwoven with finding the abs value (temp) and output bits (temp2).
667 temp
= -temp
; /* temp is abs value of input */
668 /* Apply the point transform, and watch out for case */
669 /* that nonzero coef is zero after point transform. */
670 if ((temp
>>= Al
) == 0) {
674 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
677 /* Apply the point transform, and watch out for case */
678 /* that nonzero coef is zero after point transform. */
679 if ((temp
>>= Al
) == 0) {
686 /* Emit any pending EOBRUN */
687 if (entropy
->EOBRUN
> 0)
688 emit_eobrun(entropy
);
689 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
691 emit_ac_symbol(entropy
, entropy
->ac_tbl_no
, 0xF0);
695 /* Find the number of bits needed for the magnitude of the coefficient */
697 do nbits
++; /* there must be at least one 1 bit */
698 while ((temp
>>= 1));
699 /* Check for out-of-range coefficient values */
700 if (nbits
> max_coef_bits
)
701 ERREXIT(cinfo
, JERR_BAD_DCT_COEF
);
703 /* Count/emit Huffman symbol for run length / number of bits */
704 emit_ac_symbol(entropy
, entropy
->ac_tbl_no
, (r
<< 4) + nbits
);
706 /* Emit that number of bits of the value, if positive, */
707 /* or the complement of its magnitude, if negative. */
708 emit_bits_e(entropy
, (unsigned int) temp2
, nbits
);
710 r
= 0; /* reset zero run length */
713 if (r
> 0) { /* If there are trailing zeroes, */
714 entropy
->EOBRUN
++; /* count an EOB */
715 if (entropy
->EOBRUN
== 0x7FFF)
716 emit_eobrun(entropy
); /* force it out to avoid overflow */
719 cinfo
->dest
->next_output_byte
= entropy
->next_output_byte
;
720 cinfo
->dest
->free_in_buffer
= entropy
->free_in_buffer
;
722 /* Update restart-interval state too */
723 if (cinfo
->restart_interval
) {
724 if (entropy
->restarts_to_go
== 0) {
725 entropy
->restarts_to_go
= cinfo
->restart_interval
;
726 entropy
->next_restart_num
++;
727 entropy
->next_restart_num
&= 7;
729 entropy
->restarts_to_go
--;
737 * MCU encoding for DC successive approximation refinement scan.
738 * Note: we assume such scans can be multi-component,
739 * although the spec is not very clear on the point.
743 encode_mcu_DC_refine (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
745 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
748 entropy
->next_output_byte
= cinfo
->dest
->next_output_byte
;
749 entropy
->free_in_buffer
= cinfo
->dest
->free_in_buffer
;
751 /* Emit restart marker if needed */
752 if (cinfo
->restart_interval
)
753 if (entropy
->restarts_to_go
== 0)
754 emit_restart_e(entropy
, entropy
->next_restart_num
);
758 /* Encode the MCU data blocks */
759 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
760 /* We simply emit the Al'th bit of the DC coefficient value. */
761 emit_bits_e(entropy
, (unsigned int) (MCU_data
[blkn
][0][0] >> Al
), 1);
764 cinfo
->dest
->next_output_byte
= entropy
->next_output_byte
;
765 cinfo
->dest
->free_in_buffer
= entropy
->free_in_buffer
;
767 /* Update restart-interval state too */
768 if (cinfo
->restart_interval
) {
769 if (entropy
->restarts_to_go
== 0) {
770 entropy
->restarts_to_go
= cinfo
->restart_interval
;
771 entropy
->next_restart_num
++;
772 entropy
->next_restart_num
&= 7;
774 entropy
->restarts_to_go
--;
782 * MCU encoding for AC successive approximation refinement scan.
786 encode_mcu_AC_refine (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
788 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
789 const int * natural_order
;
797 int absvalues
[DCTSIZE2
];
799 entropy
->next_output_byte
= cinfo
->dest
->next_output_byte
;
800 entropy
->free_in_buffer
= cinfo
->dest
->free_in_buffer
;
802 /* Emit restart marker if needed */
803 if (cinfo
->restart_interval
)
804 if (entropy
->restarts_to_go
== 0)
805 emit_restart_e(entropy
, entropy
->next_restart_num
);
809 natural_order
= cinfo
->natural_order
;
811 /* Encode the MCU data block */
814 /* It is convenient to make a pre-pass to determine the transformed
815 * coefficients' absolute values and the EOB position.
818 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
819 temp
= (*block
)[natural_order
[k
]];
820 /* We must apply the point transform by Al. For AC coefficients this
821 * is an integer division with rounding towards 0. To do this portably
822 * in C, we shift after obtaining the absolute value.
825 temp
= -temp
; /* temp is abs value of input */
826 temp
>>= Al
; /* apply the point transform */
827 absvalues
[k
] = temp
; /* save abs value for main pass */
829 EOB
= k
; /* EOB = index of last newly-nonzero coef */
832 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
834 r
= 0; /* r = run length of zeros */
835 BR
= 0; /* BR = count of buffered bits added now */
836 BR_buffer
= entropy
->bit_buffer
+ entropy
->BE
; /* Append bits to buffer */
838 for (k
= cinfo
->Ss
; k
<= Se
; k
++) {
839 if ((temp
= absvalues
[k
]) == 0) {
844 /* Emit any required ZRLs, but not if they can be folded into EOB */
845 while (r
> 15 && k
<= EOB
) {
846 /* emit any pending EOBRUN and the BE correction bits */
847 emit_eobrun(entropy
);
849 emit_ac_symbol(entropy
, entropy
->ac_tbl_no
, 0xF0);
851 /* Emit buffered correction bits that must be associated with ZRL */
852 emit_buffered_bits(entropy
, BR_buffer
, BR
);
853 BR_buffer
= entropy
->bit_buffer
; /* BE bits are gone now */
857 /* If the coef was previously nonzero, it only needs a correction bit.
858 * NOTE: a straight translation of the spec's figure G.7 would suggest
859 * that we also need to test r > 15. But if r > 15, we can only get here
860 * if k > EOB, which implies that this coefficient is not 1.
863 /* The correction bit is the next bit of the absolute value. */
864 BR_buffer
[BR
++] = (char) (temp
& 1);
868 /* Emit any pending EOBRUN and the BE correction bits */
869 emit_eobrun(entropy
);
871 /* Count/emit Huffman symbol for run length / number of bits */
872 emit_ac_symbol(entropy
, entropy
->ac_tbl_no
, (r
<< 4) + 1);
874 /* Emit output bit for newly-nonzero coef */
875 temp
= ((*block
)[natural_order
[k
]] < 0) ? 0 : 1;
876 emit_bits_e(entropy
, (unsigned int) temp
, 1);
878 /* Emit buffered correction bits that must be associated with this code */
879 emit_buffered_bits(entropy
, BR_buffer
, BR
);
880 BR_buffer
= entropy
->bit_buffer
; /* BE bits are gone now */
882 r
= 0; /* reset zero run length */
885 if (r
> 0 || BR
> 0) { /* If there are trailing zeroes, */
886 entropy
->EOBRUN
++; /* count an EOB */
887 entropy
->BE
+= BR
; /* concat my correction bits to older ones */
888 /* We force out the EOB if we risk either:
889 * 1. overflow of the EOB counter;
890 * 2. overflow of the correction bit buffer during the next MCU.
892 if (entropy
->EOBRUN
== 0x7FFF || entropy
->BE
> (MAX_CORR_BITS
-DCTSIZE2
+1))
893 emit_eobrun(entropy
);
896 cinfo
->dest
->next_output_byte
= entropy
->next_output_byte
;
897 cinfo
->dest
->free_in_buffer
= entropy
->free_in_buffer
;
899 /* Update restart-interval state too */
900 if (cinfo
->restart_interval
) {
901 if (entropy
->restarts_to_go
== 0) {
902 entropy
->restarts_to_go
= cinfo
->restart_interval
;
903 entropy
->next_restart_num
++;
904 entropy
->next_restart_num
&= 7;
906 entropy
->restarts_to_go
--;
913 /* Encode a single block's worth of coefficients */
916 encode_one_block (working_state
* state
, JCOEFPTR block
, int last_dc_val
,
917 c_derived_tbl
*dctbl
, c_derived_tbl
*actbl
)
919 register int temp
, temp2
;
922 int Se
= state
->cinfo
->lim_Se
;
923 int max_coef_bits
= state
->cinfo
->data_precision
+ 3;
924 const int * natural_order
= state
->cinfo
->natural_order
;
926 /* Encode the DC coefficient difference per section F.1.2.1 */
928 if ((temp
= block
[0] - last_dc_val
) == 0) {
929 /* Emit the Huffman-coded symbol for the number of bits */
930 if (! emit_bits_s(state
, dctbl
->ehufco
[0], dctbl
->ehufsi
[0]))
933 if ((temp2
= temp
) < 0) {
934 temp
= -temp
; /* temp is abs value of input */
935 /* For a negative input, want temp2 = bitwise complement of abs(input) */
936 /* This code assumes we are on a two's complement machine */
940 /* Find the number of bits needed for the magnitude of the coefficient */
942 do nbits
++; /* there must be at least one 1 bit */
943 while ((temp
>>= 1));
944 /* Check for out-of-range coefficient values.
945 * Since we're encoding a difference, the range limit is twice as much.
947 if (nbits
> max_coef_bits
)
948 ERREXIT(state
->cinfo
, JERR_BAD_DCT_COEF
);
950 /* Emit the Huffman-coded symbol for the number of bits */
951 if (! emit_bits_s(state
, dctbl
->ehufco
[nbits
], dctbl
->ehufsi
[nbits
]))
954 /* Emit that number of bits of the value, if positive, */
955 /* or the complement of its magnitude, if negative. */
956 if (! emit_bits_s(state
, (unsigned int) temp2
, nbits
))
960 /* Encode the AC coefficients per section F.1.2.2 */
962 r
= 0; /* r = run length of zeros */
964 for (k
= 1; k
<= Se
; k
++) {
965 if ((temp
= block
[natural_order
[k
]]) == 0) {
970 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
972 if (! emit_bits_s(state
, actbl
->ehufco
[0xF0], actbl
->ehufsi
[0xF0]))
977 if ((temp2
= temp
) < 0) {
978 temp
= -temp
; /* temp is abs value of input */
979 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
980 /* This code assumes we are on a two's complement machine */
984 /* Find the number of bits needed for the magnitude of the coefficient */
986 do nbits
++; /* there must be at least one 1 bit */
987 while ((temp
>>= 1));
988 /* Check for out-of-range coefficient values.
989 * Use ">=" instead of ">" so can use the
990 * same one larger limit from DC check here.
992 if (nbits
>= max_coef_bits
)
993 ERREXIT(state
->cinfo
, JERR_BAD_DCT_COEF
);
995 /* Emit Huffman symbol for run length / number of bits */
996 temp
= (r
<< 4) + nbits
;
997 if (! emit_bits_s(state
, actbl
->ehufco
[temp
], actbl
->ehufsi
[temp
]))
1000 /* Emit that number of bits of the value, if positive, */
1001 /* or the complement of its magnitude, if negative. */
1002 if (! emit_bits_s(state
, (unsigned int) temp2
, nbits
))
1005 r
= 0; /* reset zero run length */
1008 /* If the last coef(s) were zero, emit an end-of-block code */
1010 if (! emit_bits_s(state
, actbl
->ehufco
[0], actbl
->ehufsi
[0]))
1018 * Encode and output one MCU's worth of Huffman-compressed coefficients.
1022 encode_mcu_huff (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
1024 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
1025 working_state state
;
1027 jpeg_component_info
* compptr
;
1029 /* Load up working state */
1030 state
.next_output_byte
= cinfo
->dest
->next_output_byte
;
1031 state
.free_in_buffer
= cinfo
->dest
->free_in_buffer
;
1032 ASSIGN_STATE(state
.cur
, entropy
->saved
);
1033 state
.cinfo
= cinfo
;
1035 /* Emit restart marker if needed */
1036 if (cinfo
->restart_interval
) {
1037 if (entropy
->restarts_to_go
== 0)
1038 if (! emit_restart_s(&state
, entropy
->next_restart_num
))
1042 /* Encode the MCU data blocks */
1043 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
1044 ci
= cinfo
->MCU_membership
[blkn
];
1045 compptr
= cinfo
->cur_comp_info
[ci
];
1046 if (! encode_one_block(&state
,
1047 MCU_data
[blkn
][0], state
.cur
.last_dc_val
[ci
],
1048 entropy
->dc_derived_tbls
[compptr
->dc_tbl_no
],
1049 entropy
->ac_derived_tbls
[compptr
->ac_tbl_no
]))
1051 /* Update last_dc_val */
1052 state
.cur
.last_dc_val
[ci
] = MCU_data
[blkn
][0][0];
1055 /* Completed MCU, so update state */
1056 cinfo
->dest
->next_output_byte
= state
.next_output_byte
;
1057 cinfo
->dest
->free_in_buffer
= state
.free_in_buffer
;
1058 ASSIGN_STATE(entropy
->saved
, state
.cur
);
1060 /* Update restart-interval state too */
1061 if (cinfo
->restart_interval
) {
1062 if (entropy
->restarts_to_go
== 0) {
1063 entropy
->restarts_to_go
= cinfo
->restart_interval
;
1064 entropy
->next_restart_num
++;
1065 entropy
->next_restart_num
&= 7;
1067 entropy
->restarts_to_go
--;
1075 * Finish up at the end of a Huffman-compressed scan.
1079 finish_pass_huff (j_compress_ptr cinfo
)
1081 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
1082 working_state state
;
1084 if (cinfo
->progressive_mode
) {
1085 entropy
->next_output_byte
= cinfo
->dest
->next_output_byte
;
1086 entropy
->free_in_buffer
= cinfo
->dest
->free_in_buffer
;
1088 /* Flush out any buffered data */
1089 emit_eobrun(entropy
);
1090 flush_bits_e(entropy
);
1092 cinfo
->dest
->next_output_byte
= entropy
->next_output_byte
;
1093 cinfo
->dest
->free_in_buffer
= entropy
->free_in_buffer
;
1095 /* Load up working state ... flush_bits needs it */
1096 state
.next_output_byte
= cinfo
->dest
->next_output_byte
;
1097 state
.free_in_buffer
= cinfo
->dest
->free_in_buffer
;
1098 ASSIGN_STATE(state
.cur
, entropy
->saved
);
1099 state
.cinfo
= cinfo
;
1101 /* Flush out the last data */
1102 if (! flush_bits_s(&state
))
1103 ERREXIT(cinfo
, JERR_CANT_SUSPEND
);
1106 cinfo
->dest
->next_output_byte
= state
.next_output_byte
;
1107 cinfo
->dest
->free_in_buffer
= state
.free_in_buffer
;
1108 ASSIGN_STATE(entropy
->saved
, state
.cur
);
1114 * Huffman coding optimization.
1116 * We first scan the supplied data and count the number of uses of each symbol
1117 * that is to be Huffman-coded. (This process MUST agree with the code above.)
1118 * Then we build a Huffman coding tree for the observed counts.
1119 * Symbols which are not needed at all for the particular image are not
1120 * assigned any code, which saves space in the DHT marker as well as in
1121 * the compressed data.
1125 /* Process a single block's worth of coefficients */
1128 htest_one_block (j_compress_ptr cinfo
, JCOEFPTR block
, int last_dc_val
,
1129 long dc_counts
[], long ac_counts
[])
1134 int Se
= cinfo
->lim_Se
;
1135 int max_coef_bits
= cinfo
->data_precision
+ 3;
1136 const int * natural_order
= cinfo
->natural_order
;
1138 /* Encode the DC coefficient difference per section F.1.2.1 */
1140 if ((temp
= block
[0] - last_dc_val
) == 0) {
1141 /* Count the Huffman symbol for the number of bits */
1145 temp
= -temp
; /* temp is abs value of input */
1147 /* Find the number of bits needed for the magnitude of the coefficient */
1149 do nbits
++; /* there must be at least one 1 bit */
1150 while ((temp
>>= 1));
1151 /* Check for out-of-range coefficient values.
1152 * Since we're encoding a difference, the range limit is twice as much.
1154 if (nbits
> max_coef_bits
)
1155 ERREXIT(cinfo
, JERR_BAD_DCT_COEF
);
1157 /* Count the Huffman symbol for the number of bits */
1161 /* Encode the AC coefficients per section F.1.2.2 */
1163 r
= 0; /* r = run length of zeros */
1165 for (k
= 1; k
<= Se
; k
++) {
1166 if ((temp
= block
[natural_order
[k
]]) == 0) {
1171 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
1178 temp
= -temp
; /* temp is abs value of input */
1180 /* Find the number of bits needed for the magnitude of the coefficient */
1182 do nbits
++; /* there must be at least one 1 bit */
1183 while ((temp
>>= 1));
1184 /* Check for out-of-range coefficient values.
1185 * Use ">=" instead of ">" so can use the
1186 * same one larger limit from DC check here.
1188 if (nbits
>= max_coef_bits
)
1189 ERREXIT(cinfo
, JERR_BAD_DCT_COEF
);
1191 /* Count Huffman symbol for run length / number of bits */
1192 ac_counts
[(r
<< 4) + nbits
]++;
1194 r
= 0; /* reset zero run length */
1197 /* If the last coef(s) were zero, emit an end-of-block code */
1204 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
1205 * No data is actually output, so no suspension return is possible.
1209 encode_mcu_gather (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
1211 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
1213 jpeg_component_info
* compptr
;
1215 /* Take care of restart intervals if needed */
1216 if (cinfo
->restart_interval
) {
1217 if (entropy
->restarts_to_go
== 0) {
1218 /* Re-initialize DC predictions to 0 */
1219 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++)
1220 entropy
->saved
.last_dc_val
[ci
] = 0;
1221 /* Update restart state */
1222 entropy
->restarts_to_go
= cinfo
->restart_interval
;
1224 entropy
->restarts_to_go
--;
1227 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
1228 ci
= cinfo
->MCU_membership
[blkn
];
1229 compptr
= cinfo
->cur_comp_info
[ci
];
1230 htest_one_block(cinfo
, MCU_data
[blkn
][0], entropy
->saved
.last_dc_val
[ci
],
1231 entropy
->dc_count_ptrs
[compptr
->dc_tbl_no
],
1232 entropy
->ac_count_ptrs
[compptr
->ac_tbl_no
]);
1233 entropy
->saved
.last_dc_val
[ci
] = MCU_data
[blkn
][0][0];
1241 * Generate the best Huffman code table for the given counts, fill htbl.
1243 * The JPEG standard requires that no symbol be assigned a codeword of all
1244 * one bits (so that padding bits added at the end of a compressed segment
1245 * can't look like a valid code). Because of the canonical ordering of
1246 * codewords, this just means that there must be an unused slot in the
1247 * longest codeword length category. Section K.2 of the JPEG spec suggests
1248 * reserving such a slot by pretending that symbol 256 is a valid symbol
1249 * with count 1. In theory that's not optimal; giving it count zero but
1250 * including it in the symbol set anyway should give a better Huffman code.
1251 * But the theoretically better code actually seems to come out worse in
1252 * practice, because it produces more all-ones bytes (which incur stuffed
1253 * zero bytes in the final file). In any case the difference is tiny.
1255 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
1256 * If some symbols have a very small but nonzero probability, the Huffman tree
1257 * must be adjusted to meet the code length restriction. We currently use
1258 * the adjustment method suggested in JPEG section K.2. This method is *not*
1259 * optimal; it may not choose the best possible limited-length code. But
1260 * typically only very-low-frequency symbols will be given less-than-optimal
1261 * lengths, so the code is almost optimal. Experimental comparisons against
1262 * an optimal limited-length-code algorithm indicate that the difference is
1263 * microscopic --- usually less than a hundredth of a percent of total size.
1264 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
1268 jpeg_gen_optimal_table (j_compress_ptr cinfo
, JHUFF_TBL
* htbl
, long freq
[])
1270 #define MAX_CLEN 32 /* assumed maximum initial code length */
1271 UINT8 bits
[MAX_CLEN
+1]; /* bits[k] = # of symbols with code length k */
1272 int codesize
[257]; /* codesize[k] = code length of symbol k */
1273 int others
[257]; /* next symbol in current branch of tree */
1278 freq
[256] = 1; /* make sure 256 has a nonzero count */
1279 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
1280 * that no real symbol is given code-value of all ones, because 256
1281 * will be placed last in the largest codeword category.
1282 * In the symbol list build procedure this element serves as sentinel
1283 * for the zero run loop.
1286 #ifndef DONT_USE_FANCY_HUFF_OPT
1288 /* Build list of symbols sorted in order of descending frequency */
1289 /* This approach has several benefits (thank to John Korejwa for the idea):
1291 * If a codelength category is split during the length limiting procedure
1292 * below, the feature that more frequent symbols are assigned shorter
1293 * codewords remains valid for the adjusted code.
1295 * To reduce consecutive ones in a Huffman data stream (thus reducing the
1296 * number of stuff bytes in JPEG) it is preferable to follow 0 branches
1297 * (and avoid 1 branches) as much as possible. This is easily done by
1298 * assigning symbols to leaves of the Huffman tree in order of decreasing
1299 * frequency, with no secondary sort based on codelengths.
1301 * The symbol list can be built independently from the assignment of code
1302 * lengths by the Huffman procedure below.
1303 * Note: The symbol list build procedure must be performed first, because
1304 * the Huffman procedure assigning the codelengths clobbers the frequency
1308 /* Here we use the others array as a linked list of nonzero frequencies
1309 * to be sorted. Already sorted elements are removed from the list.
1314 /* This item does not correspond to a valid symbol frequency and is used
1315 * as starting index.
1320 if (freq
[i
] == 0) /* skip zero frequencies */
1324 others
[j
] = i
; /* this symbol value */
1325 j
= i
; /* previous symbol value */
1327 others
[j
] = -1; /* mark end of list */
1332 while ((c1
= others
[256]) >= 0) {
1334 i
= c1
; /* first symbol value */
1335 j
= 256; /* pseudo symbol value for starting index */
1336 while ((c2
= others
[c1
]) >= 0) {
1339 i
= c2
; /* this symbol value */
1340 j
= c1
; /* previous symbol value */
1344 others
[j
] = others
[i
]; /* remove this symbol i from list */
1348 #endif /* DONT_USE_FANCY_HUFF_OPT */
1350 /* This algorithm is explained in section K.2 of the JPEG standard */
1352 MEMZERO(bits
, SIZEOF(bits
));
1353 MEMZERO(codesize
, SIZEOF(codesize
));
1354 for (i
= 0; i
< 257; i
++)
1355 others
[i
] = -1; /* init links to empty */
1357 /* Huffman's basic algorithm to assign optimal code lengths to symbols */
1360 /* Find the smallest nonzero frequency, set c1 = its symbol */
1361 /* In case of ties, take the larger symbol number */
1364 for (i
= 0; i
<= 256; i
++) {
1365 if (freq
[i
] && freq
[i
] <= v
) {
1371 /* Find the next smallest nonzero frequency, set c2 = its symbol */
1372 /* In case of ties, take the larger symbol number */
1375 for (i
= 0; i
<= 256; i
++) {
1376 if (freq
[i
] && freq
[i
] <= v
&& i
!= c1
) {
1382 /* Done if we've merged everything into one frequency */
1386 /* Else merge the two counts/trees */
1387 freq
[c1
] += freq
[c2
];
1390 /* Increment the codesize of everything in c1's tree branch */
1392 while (others
[c1
] >= 0) {
1397 others
[c1
] = c2
; /* chain c2 onto c1's tree branch */
1399 /* Increment the codesize of everything in c2's tree branch */
1401 while (others
[c2
] >= 0) {
1407 /* Now count the number of symbols of each code length */
1408 for (i
= 0; i
<= 256; i
++) {
1410 /* The JPEG standard seems to think that this can't happen, */
1411 /* but I'm paranoid... */
1412 if (codesize
[i
] > MAX_CLEN
)
1413 ERREXIT(cinfo
, JERR_HUFF_CLEN_OUTOFBOUNDS
);
1415 bits
[codesize
[i
]]++;
1419 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
1420 * Huffman procedure assigned any such lengths, we must adjust the coding.
1421 * Here is what the JPEG spec says about how this next bit works:
1422 * Since symbols are paired for the longest Huffman code, the symbols are
1423 * removed from this length category two at a time. The prefix for the pair
1424 * (which is one bit shorter) is allocated to one of the pair; then,
1425 * skipping the BITS entry for that prefix length, a code word from the next
1426 * shortest nonzero BITS entry is converted into a prefix for two code words
1430 for (i
= MAX_CLEN
; i
> 16; i
--) {
1431 while (bits
[i
] > 0) {
1432 j
= i
- 2; /* find length of new prefix to be used */
1433 while (bits
[j
] == 0) {
1435 ERREXIT(cinfo
, JERR_HUFF_CLEN_OUTOFBOUNDS
);
1439 bits
[i
] -= 2; /* remove two symbols */
1440 bits
[i
-1]++; /* one goes in this length */
1441 bits
[j
+1] += 2; /* two new symbols in this length */
1442 bits
[j
]--; /* symbol of this length is now a prefix */
1446 /* Remove the count for the pseudo-symbol 256 from the largest codelength */
1447 while (bits
[i
] == 0) /* find largest codelength still in use */
1451 /* Return final symbol counts (only for lengths 0..16) */
1452 MEMCOPY(htbl
->bits
, bits
, SIZEOF(htbl
->bits
));
1454 #ifdef DONT_USE_FANCY_HUFF_OPT
1456 /* Return a list of the symbols sorted by code length */
1457 /* Note: Due to the codelength changes made above, it can happen
1458 * that more frequent symbols are assigned longer codewords.
1461 for (i
= 1; i
<= MAX_CLEN
; i
++) {
1462 for (j
= 0; j
<= 255; j
++) {
1463 if (codesize
[j
] == i
) {
1469 #endif /* DONT_USE_FANCY_HUFF_OPT */
1471 /* Set sent_table FALSE so updated table will be written to JPEG file. */
1472 htbl
->sent_table
= FALSE
;
1477 * Finish up a statistics-gathering pass and create the new Huffman tables.
1481 finish_pass_gather (j_compress_ptr cinfo
)
1483 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
1485 jpeg_component_info
* compptr
;
1486 JHUFF_TBL
**htblptr
;
1487 boolean did_dc
[NUM_HUFF_TBLS
];
1488 boolean did_ac
[NUM_HUFF_TBLS
];
1490 if (cinfo
->progressive_mode
)
1491 /* Flush out buffered data (all we care about is counting the EOB symbol) */
1492 emit_eobrun(entropy
);
1494 /* It's important not to apply jpeg_gen_optimal_table more than once
1495 * per table, because it clobbers the input frequency counts!
1497 MEMZERO(did_dc
, SIZEOF(did_dc
));
1498 MEMZERO(did_ac
, SIZEOF(did_ac
));
1500 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
1501 compptr
= cinfo
->cur_comp_info
[ci
];
1502 /* DC needs no table for refinement scan */
1503 if (cinfo
->Ss
== 0 && cinfo
->Ah
== 0) {
1504 tbl
= compptr
->dc_tbl_no
;
1505 if (! did_dc
[tbl
]) {
1506 htblptr
= & cinfo
->dc_huff_tbl_ptrs
[tbl
];
1507 if (*htblptr
== NULL
)
1508 *htblptr
= jpeg_alloc_huff_table((j_common_ptr
) cinfo
);
1509 jpeg_gen_optimal_table(cinfo
, *htblptr
, entropy
->dc_count_ptrs
[tbl
]);
1513 /* AC needs no table when not present */
1515 tbl
= compptr
->ac_tbl_no
;
1516 if (! did_ac
[tbl
]) {
1517 htblptr
= & cinfo
->ac_huff_tbl_ptrs
[tbl
];
1518 if (*htblptr
== NULL
)
1519 *htblptr
= jpeg_alloc_huff_table((j_common_ptr
) cinfo
);
1520 jpeg_gen_optimal_table(cinfo
, *htblptr
, entropy
->ac_count_ptrs
[tbl
]);
1529 * Initialize for a Huffman-compressed scan.
1530 * If gather_statistics is TRUE, we do not output anything during the scan,
1531 * just count the Huffman symbols used and generate Huffman code tables.
1535 start_pass_huff (j_compress_ptr cinfo
, boolean gather_statistics
)
1537 huff_entropy_ptr entropy
= (huff_entropy_ptr
) cinfo
->entropy
;
1539 jpeg_component_info
* compptr
;
1541 if (gather_statistics
)
1542 entropy
->pub
.finish_pass
= finish_pass_gather
;
1544 entropy
->pub
.finish_pass
= finish_pass_huff
;
1546 if (cinfo
->progressive_mode
) {
1547 entropy
->cinfo
= cinfo
;
1548 entropy
->gather_statistics
= gather_statistics
;
1550 /* We assume jcmaster.c already validated the scan parameters. */
1552 /* Select execution routine */
1553 if (cinfo
->Ah
== 0) {
1555 entropy
->pub
.encode_mcu
= encode_mcu_DC_first
;
1557 entropy
->pub
.encode_mcu
= encode_mcu_AC_first
;
1560 entropy
->pub
.encode_mcu
= encode_mcu_DC_refine
;
1562 entropy
->pub
.encode_mcu
= encode_mcu_AC_refine
;
1563 /* AC refinement needs a correction bit buffer */
1564 if (entropy
->bit_buffer
== NULL
)
1565 entropy
->bit_buffer
= (char *) (*cinfo
->mem
->alloc_small
)
1566 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, MAX_CORR_BITS
* SIZEOF(char));
1570 /* Initialize AC stuff */
1571 entropy
->ac_tbl_no
= cinfo
->cur_comp_info
[0]->ac_tbl_no
;
1572 entropy
->EOBRUN
= 0;
1575 if (gather_statistics
)
1576 entropy
->pub
.encode_mcu
= encode_mcu_gather
;
1578 entropy
->pub
.encode_mcu
= encode_mcu_huff
;
1581 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
1582 compptr
= cinfo
->cur_comp_info
[ci
];
1583 /* DC needs no table for refinement scan */
1584 if (cinfo
->Ss
== 0 && cinfo
->Ah
== 0) {
1585 tbl
= compptr
->dc_tbl_no
;
1586 if (gather_statistics
) {
1587 /* Check for invalid table index */
1588 /* (make_c_derived_tbl does this in the other path) */
1589 if (tbl
< 0 || tbl
>= NUM_HUFF_TBLS
)
1590 ERREXIT1(cinfo
, JERR_NO_HUFF_TABLE
, tbl
);
1591 /* Allocate and zero the statistics tables */
1592 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
1593 if (entropy
->dc_count_ptrs
[tbl
] == NULL
)
1594 entropy
->dc_count_ptrs
[tbl
] = (long *) (*cinfo
->mem
->alloc_small
)
1595 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, 257 * SIZEOF(long));
1596 MEMZERO(entropy
->dc_count_ptrs
[tbl
], 257 * SIZEOF(long));
1598 /* Compute derived values for Huffman tables */
1599 /* We may do this more than once for a table, but it's not expensive */
1600 jpeg_make_c_derived_tbl(cinfo
, TRUE
, tbl
,
1601 & entropy
->dc_derived_tbls
[tbl
]);
1603 /* Initialize DC predictions to 0 */
1604 entropy
->saved
.last_dc_val
[ci
] = 0;
1606 /* AC needs no table when not present */
1608 tbl
= compptr
->ac_tbl_no
;
1609 if (gather_statistics
) {
1610 if (tbl
< 0 || tbl
>= NUM_HUFF_TBLS
)
1611 ERREXIT1(cinfo
, JERR_NO_HUFF_TABLE
, tbl
);
1612 if (entropy
->ac_count_ptrs
[tbl
] == NULL
)
1613 entropy
->ac_count_ptrs
[tbl
] = (long *) (*cinfo
->mem
->alloc_small
)
1614 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, 257 * SIZEOF(long));
1615 MEMZERO(entropy
->ac_count_ptrs
[tbl
], 257 * SIZEOF(long));
1617 jpeg_make_c_derived_tbl(cinfo
, FALSE
, tbl
,
1618 & entropy
->ac_derived_tbls
[tbl
]);
1623 /* Initialize bit buffer to empty */
1624 entropy
->saved
.put_buffer
= 0;
1625 entropy
->saved
.put_bits
= 0;
1627 /* Initialize restart stuff */
1628 entropy
->restarts_to_go
= cinfo
->restart_interval
;
1629 entropy
->next_restart_num
= 0;
1634 * Module initialization routine for Huffman entropy encoding.
1638 jinit_huff_encoder (j_compress_ptr cinfo
)
1640 huff_entropy_ptr entropy
;
1643 entropy
= (huff_entropy_ptr
) (*cinfo
->mem
->alloc_small
)
1644 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, SIZEOF(huff_entropy_encoder
));
1645 cinfo
->entropy
= &entropy
->pub
;
1646 entropy
->pub
.start_pass
= start_pass_huff
;
1648 /* Mark tables unallocated */
1649 for (i
= 0; i
< NUM_HUFF_TBLS
; i
++) {
1650 entropy
->dc_derived_tbls
[i
] = entropy
->ac_derived_tbls
[i
] = NULL
;
1651 entropy
->dc_count_ptrs
[i
] = entropy
->ac_count_ptrs
[i
] = NULL
;
1654 if (cinfo
->progressive_mode
)
1655 entropy
->bit_buffer
= NULL
; /* needed only in AC refinement scan */