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