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