ReactOS 0.4.15-dev-8109-gd7be748
jchuff.c
Go to the documentation of this file.
1/*
2 * jchuff.c
3 *
4 * Copyright (C) 1991-1997, Thomas G. Lane.
5 * Modified 2006-2019 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.
8 *
9 * This file contains Huffman entropy encoding routines.
10 * Both sequential and progressive modes are supported in this single module.
11 *
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.
17 *
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.
21 */
22
23#define JPEG_INTERNALS
24#include "jinclude.h"
25#include "jpeglib.h"
26
27
28/* The legal range of a DCT coefficient is
29 * -1024 .. +1023 for 8-bit data;
30 * -16384 .. +16383 for 12-bit data.
31 * Hence the magnitude should always fit in 10 or 14 bits respectively.
32 */
33
34#if BITS_IN_JSAMPLE == 8
35#define MAX_COEF_BITS 10
36#else
37#define MAX_COEF_BITS 14
38#endif
39
40/* Derived data constructed for each Huffman table */
41
42typedef struct {
43 unsigned int ehufco[256]; /* code for each symbol */
44 char ehufsi[256]; /* length of code for each symbol */
45 /* If no code has been allocated for a symbol S, ehufsi[S] contains 0 */
47
48
49/* Expanded entropy encoder object for Huffman encoding.
50 *
51 * The savable_state subrecord contains fields that change within an MCU,
52 * but must not be updated permanently until we complete the MCU.
53 */
54
55typedef struct {
56 INT32 put_buffer; /* current bit-accumulation buffer */
57 int put_bits; /* # of bits now in it */
58 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
60
61/* This macro is to work around compilers with missing or broken
62 * structure assignment. You'll need to fix this code if you have
63 * such a compiler and you change MAX_COMPS_IN_SCAN.
64 */
65
66#ifndef NO_STRUCT_ASSIGN
67#define ASSIGN_STATE(dest,src) ((dest) = (src))
68#else
69#if MAX_COMPS_IN_SCAN == 4
70#define ASSIGN_STATE(dest,src) \
71 ((dest).put_buffer = (src).put_buffer, \
72 (dest).put_bits = (src).put_bits, \
73 (dest).last_dc_val[0] = (src).last_dc_val[0], \
74 (dest).last_dc_val[1] = (src).last_dc_val[1], \
75 (dest).last_dc_val[2] = (src).last_dc_val[2], \
76 (dest).last_dc_val[3] = (src).last_dc_val[3])
77#endif
78#endif
79
80
81typedef struct {
82 struct jpeg_entropy_encoder pub; /* public fields */
83
84 savable_state saved; /* Bit buffer & DC state at start of MCU */
85
86 /* These fields are NOT loaded into local working state. */
87 unsigned int restarts_to_go; /* MCUs left in this restart interval */
88 int next_restart_num; /* next restart number to write (0-7) */
89
90 /* Pointers to derived tables (these workspaces have image lifespan) */
91 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
92 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
93
94 /* Statistics tables for optimization */
95 long * dc_count_ptrs[NUM_HUFF_TBLS];
96 long * ac_count_ptrs[NUM_HUFF_TBLS];
97
98 /* Following fields used only in progressive mode */
99
100 /* Mode flag: TRUE for optimization, FALSE for actual data output */
102
103 /* next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
104 */
105 JOCTET * next_output_byte; /* => next byte to write in buffer */
106 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
107 j_compress_ptr cinfo; /* link to cinfo (needed for dump_buffer) */
108
109 /* Coding status for AC components */
110 int ac_tbl_no; /* the table number of the single component */
111 unsigned int EOBRUN; /* run length of EOBs */
112 unsigned int BE; /* # of buffered correction bits before MCU */
113 char * bit_buffer; /* buffer for correction bits (1 per char) */
114 /* packing correction bits tightly would save some space but cost time... */
116
118
119/* Working state while writing an MCU (sequential mode).
120 * This struct contains all the fields that are needed by subroutines.
121 */
122
123typedef struct {
124 JOCTET * next_output_byte; /* => next byte to write in buffer */
125 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
126 savable_state cur; /* Current bit buffer & DC state */
127 j_compress_ptr cinfo; /* dump_buffer needs access to this */
129
130/* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
131 * buffer can hold. Larger sizes may slightly improve compression, but
132 * 1000 is already well into the realm of overkill.
133 * The minimum safe size is 64 bits.
134 */
135
136#define MAX_CORR_BITS 1000 /* Max # of correction bits I can buffer */
137
138/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
139 * We assume that int right shift is unsigned if INT32 right shift is,
140 * which should be safe.
141 */
142
143#ifdef RIGHT_SHIFT_IS_UNSIGNED
144#define ISHIFT_TEMPS int ishift_temp;
145#define IRIGHT_SHIFT(x,shft) \
146 ((ishift_temp = (x)) < 0 ? \
147 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
148 (ishift_temp >> (shft)))
149#else
150#define ISHIFT_TEMPS
151#define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
152#endif
153
154
155/*
156 * Compute the derived values for a Huffman table.
157 * This routine also performs some validation checks on the table.
158 */
159
160LOCAL(void)
162 c_derived_tbl ** pdtbl)
163{
164 JHUFF_TBL *htbl;
165 c_derived_tbl *dtbl;
166 int p, i, l, lastp, si, maxsymbol;
167 char huffsize[257];
168 unsigned int huffcode[257];
169 unsigned int code;
170
171 /* Note that huffsize[] and huffcode[] are filled in code-length order,
172 * paralleling the order of the symbols themselves in htbl->huffval[].
173 */
174
175 /* Find the input Huffman table */
176 if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
177 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
178 htbl =
179 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
180 if (htbl == NULL)
181 htbl = jpeg_std_huff_table((j_common_ptr) cinfo, isDC, tblno);
182
183 /* Allocate a workspace if we haven't already done so. */
184 if (*pdtbl == NULL)
185 *pdtbl = (c_derived_tbl *) (*cinfo->mem->alloc_small)
187 dtbl = *pdtbl;
188
189 /* Figure C.1: make table of Huffman code length for each symbol */
190
191 p = 0;
192 for (l = 1; l <= 16; l++) {
193 i = (int) htbl->bits[l];
194 if (i < 0 || p + i > 256) /* protect against table overrun */
195 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
196 while (i--)
197 huffsize[p++] = (char) l;
198 }
199 huffsize[p] = 0;
200 lastp = p;
201
202 /* Figure C.2: generate the codes themselves */
203 /* We also validate that the counts represent a legal Huffman code tree. */
204
205 code = 0;
206 si = huffsize[0];
207 p = 0;
208 while (huffsize[p]) {
209 while (((int) huffsize[p]) == si) {
210 huffcode[p++] = code;
211 code++;
212 }
213 /* code is now 1 more than the last code used for codelength si; but
214 * it must still fit in si bits, since no code is allowed to be all ones.
215 */
216 if (((INT32) code) >= (((INT32) 1) << si))
217 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
218 code <<= 1;
219 si++;
220 }
221
222 /* Figure C.3: generate encoding tables */
223 /* These are code and size indexed by symbol value */
224
225 /* Set all codeless symbols to have code length 0;
226 * this lets us detect duplicate VAL entries here, and later
227 * allows emit_bits to detect any attempt to emit such symbols.
228 */
229 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
230
231 /* This is also a convenient place to check for out-of-range
232 * and duplicated VAL entries. We allow 0..255 for AC symbols
233 * but only 0..15 for DC. (We could constrain them further
234 * based on data depth and mode, but this seems enough.)
235 */
236 maxsymbol = isDC ? 15 : 255;
237
238 for (p = 0; p < lastp; p++) {
239 i = htbl->huffval[p];
240 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
241 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
242 dtbl->ehufco[i] = huffcode[p];
243 dtbl->ehufsi[i] = huffsize[p];
244 }
245}
246
247
248/* Outputting bytes to the file.
249 * NB: these must be called only when actually outputting,
250 * that is, entropy->gather_statistics == FALSE.
251 */
252
253/* Emit a byte, taking 'action' if must suspend. */
254#define emit_byte_s(state,val,action) \
255 { *(state)->next_output_byte++ = (JOCTET) (val); \
256 if (--(state)->free_in_buffer == 0) \
257 if (! dump_buffer_s(state)) \
258 { action; } }
259
260/* Emit a byte */
261#define emit_byte_e(entropy,val) \
262 { *(entropy)->next_output_byte++ = (JOCTET) (val); \
263 if (--(entropy)->free_in_buffer == 0) \
264 dump_buffer_e(entropy); }
265
266
267LOCAL(boolean)
269/* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
270{
271 struct jpeg_destination_mgr * dest = state->cinfo->dest;
272
273 if (! (*dest->empty_output_buffer) (state->cinfo))
274 return FALSE;
275 /* After a successful buffer dump, must reset buffer pointers */
276 state->next_output_byte = dest->next_output_byte;
277 state->free_in_buffer = dest->free_in_buffer;
278 return TRUE;
279}
280
281
282LOCAL(void)
284/* Empty the output buffer; we do not support suspension in this case. */
285{
286 struct jpeg_destination_mgr * dest = entropy->cinfo->dest;
287
288 if (! (*dest->empty_output_buffer) (entropy->cinfo))
289 ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
290 /* After a successful buffer dump, must reset buffer pointers */
291 entropy->next_output_byte = dest->next_output_byte;
292 entropy->free_in_buffer = dest->free_in_buffer;
293}
294
295
296/* Outputting bits to the file */
297
298/* Only the right 24 bits of put_buffer are used; the valid bits are
299 * left-justified in this part. At most 16 bits can be passed to emit_bits
300 * in one call, and we never retain more than 7 bits in put_buffer
301 * between calls, so 24 bits are sufficient.
302 */
303
304INLINE
305LOCAL(boolean)
307/* Emit some bits; return TRUE if successful, FALSE if must suspend */
308{
309 /* This routine is heavily used, so it's worth coding tightly. */
310 register INT32 put_buffer;
311 register int put_bits;
312
313 /* if size is 0, caller used an invalid Huffman table entry */
314 if (size == 0)
315 ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
316
317 /* mask off any extra bits in code */
318 put_buffer = ((INT32) code) & ((((INT32) 1) << size) - 1);
319
320 /* new number of bits in buffer */
321 put_bits = size + state->cur.put_bits;
322
323 put_buffer <<= 24 - put_bits; /* align incoming bits */
324
325 /* and merge with old buffer contents */
326 put_buffer |= state->cur.put_buffer;
327
328 while (put_bits >= 8) {
329 int c = (int) ((put_buffer >> 16) & 0xFF);
330
331 emit_byte_s(state, c, return FALSE);
332 if (c == 0xFF) { /* need to stuff a zero byte? */
333 emit_byte_s(state, 0, return FALSE);
334 }
335 put_buffer <<= 8;
336 put_bits -= 8;
337 }
338
339 state->cur.put_buffer = put_buffer; /* update state variables */
340 state->cur.put_bits = put_bits;
341
342 return TRUE;
343}
344
345
346INLINE
347LOCAL(void)
348emit_bits_e (huff_entropy_ptr entropy, unsigned int code, int size)
349/* Emit some bits, unless we are in gather mode */
350{
351 /* This routine is heavily used, so it's worth coding tightly. */
352 register INT32 put_buffer;
353 register int put_bits;
354
355 /* if size is 0, caller used an invalid Huffman table entry */
356 if (size == 0)
357 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
358
359 if (entropy->gather_statistics)
360 return; /* do nothing if we're only getting stats */
361
362 /* mask off any extra bits in code */
363 put_buffer = ((INT32) code) & ((((INT32) 1) << size) - 1);
364
365 /* new number of bits in buffer */
366 put_bits = size + entropy->saved.put_bits;
367
368 put_buffer <<= 24 - put_bits; /* align incoming bits */
369
370 /* and merge with old buffer contents */
371 put_buffer |= entropy->saved.put_buffer;
372
373 while (put_bits >= 8) {
374 int c = (int) ((put_buffer >> 16) & 0xFF);
375
376 emit_byte_e(entropy, c);
377 if (c == 0xFF) { /* need to stuff a zero byte? */
378 emit_byte_e(entropy, 0);
379 }
380 put_buffer <<= 8;
381 put_bits -= 8;
382 }
383
384 entropy->saved.put_buffer = put_buffer; /* update variables */
385 entropy->saved.put_bits = put_bits;
386}
387
388
389LOCAL(boolean)
391{
392 if (! emit_bits_s(state, 0x7F, 7)) /* fill any partial byte with ones */
393 return FALSE;
394 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
395 state->cur.put_bits = 0;
396 return TRUE;
397}
398
399
400LOCAL(void)
402{
403 emit_bits_e(entropy, 0x7F, 7); /* fill any partial byte with ones */
404 entropy->saved.put_buffer = 0; /* and reset bit-buffer to empty */
405 entropy->saved.put_bits = 0;
406}
407
408
409/*
410 * Emit (or just count) a Huffman symbol.
411 */
412
413INLINE
414LOCAL(void)
415emit_dc_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol)
416{
417 if (entropy->gather_statistics)
418 entropy->dc_count_ptrs[tbl_no][symbol]++;
419 else {
420 c_derived_tbl * tbl = entropy->dc_derived_tbls[tbl_no];
421 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
422 }
423}
424
425
426INLINE
427LOCAL(void)
428emit_ac_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol)
429{
430 if (entropy->gather_statistics)
431 entropy->ac_count_ptrs[tbl_no][symbol]++;
432 else {
433 c_derived_tbl * tbl = entropy->ac_derived_tbls[tbl_no];
434 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
435 }
436}
437
438
439/*
440 * Emit bits from a correction bit buffer.
441 */
442
443LOCAL(void)
444emit_buffered_bits (huff_entropy_ptr entropy, char * bufstart,
445 unsigned int nbits)
446{
447 if (entropy->gather_statistics)
448 return; /* no real work */
449
450 while (nbits > 0) {
451 emit_bits_e(entropy, (unsigned int) (*bufstart), 1);
452 bufstart++;
453 nbits--;
454 }
455}
456
457
458/*
459 * Emit any pending EOBRUN symbol.
460 */
461
462LOCAL(void)
464{
465 register int temp, nbits;
466
467 if (entropy->EOBRUN > 0) { /* if there is any pending EOBRUN */
468 temp = entropy->EOBRUN;
469 nbits = 0;
470 while ((temp >>= 1))
471 nbits++;
472 /* safety check: shouldn't happen given limited correction-bit buffer */
473 if (nbits > 14)
474 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
475
476 emit_ac_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
477 if (nbits)
478 emit_bits_e(entropy, entropy->EOBRUN, nbits);
479
480 entropy->EOBRUN = 0;
481
482 /* Emit any buffered correction bits */
483 emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
484 entropy->BE = 0;
485 }
486}
487
488
489/*
490 * Emit a restart marker & resynchronize predictions.
491 */
492
493LOCAL(boolean)
495{
496 int ci;
497
498 if (! flush_bits_s(state))
499 return FALSE;
500
501 emit_byte_s(state, 0xFF, return FALSE);
502 emit_byte_s(state, JPEG_RST0 + restart_num, return FALSE);
503
504 /* Re-initialize DC predictions to 0 */
505 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
506 state->cur.last_dc_val[ci] = 0;
507
508 /* The restart counter is not updated until we successfully write the MCU. */
509
510 return TRUE;
511}
512
513
514LOCAL(void)
515emit_restart_e (huff_entropy_ptr entropy, int restart_num)
516{
517 int ci;
518
519 emit_eobrun(entropy);
520
521 if (! entropy->gather_statistics) {
522 flush_bits_e(entropy);
523 emit_byte_e(entropy, 0xFF);
524 emit_byte_e(entropy, JPEG_RST0 + restart_num);
525 }
526
527 if (entropy->cinfo->Ss == 0) {
528 /* Re-initialize DC predictions to 0 */
529 for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
530 entropy->saved.last_dc_val[ci] = 0;
531 } else {
532 /* Re-initialize all AC-related fields to 0 */
533 entropy->EOBRUN = 0;
534 entropy->BE = 0;
535 }
536}
537
538
539/*
540 * MCU encoding for DC initial scan (either spectral selection,
541 * or first pass of successive approximation).
542 */
543
544METHODDEF(boolean)
546{
547 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
548 register int temp, temp2;
549 register int nbits;
550 int blkn, ci, tbl;
552
553 entropy->next_output_byte = cinfo->dest->next_output_byte;
554 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
555
556 /* Emit restart marker if needed */
557 if (cinfo->restart_interval)
558 if (entropy->restarts_to_go == 0)
559 emit_restart_e(entropy, entropy->next_restart_num);
560
561 /* Encode the MCU data blocks */
562 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
563 ci = cinfo->MCU_membership[blkn];
564 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
565
566 /* Compute the DC value after the required point transform by Al.
567 * This is simply an arithmetic right shift.
568 */
569 temp = IRIGHT_SHIFT((int) (MCU_data[blkn][0][0]), cinfo->Al);
570
571 /* DC differences are figured on the point-transformed values. */
572 temp2 = temp - entropy->saved.last_dc_val[ci];
573 entropy->saved.last_dc_val[ci] = temp;
574
575 /* Encode the DC coefficient difference per section G.1.2.1 */
576 temp = temp2;
577 if (temp < 0) {
578 temp = -temp; /* temp is abs value of input */
579 /* For a negative input, want temp2 = bitwise complement of abs(input) */
580 /* This code assumes we are on a two's complement machine */
581 temp2--;
582 }
583
584 /* Find the number of bits needed for the magnitude of the coefficient */
585 nbits = 0;
586 while (temp) {
587 nbits++;
588 temp >>= 1;
589 }
590 /* Check for out-of-range coefficient values.
591 * Since we're encoding a difference, the range limit is twice as much.
592 */
593 if (nbits > MAX_COEF_BITS+1)
594 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
595
596 /* Count/emit the Huffman-coded symbol for the number of bits */
597 emit_dc_symbol(entropy, tbl, nbits);
598
599 /* Emit that number of bits of the value, if positive, */
600 /* or the complement of its magnitude, if negative. */
601 if (nbits) /* emit_bits rejects calls with size 0 */
602 emit_bits_e(entropy, (unsigned int) temp2, nbits);
603 }
604
605 cinfo->dest->next_output_byte = entropy->next_output_byte;
606 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
607
608 /* Update restart-interval state too */
609 if (cinfo->restart_interval) {
610 if (entropy->restarts_to_go == 0) {
611 entropy->restarts_to_go = cinfo->restart_interval;
612 entropy->next_restart_num++;
613 entropy->next_restart_num &= 7;
614 }
615 entropy->restarts_to_go--;
616 }
617
618 return TRUE;
619}
620
621
622/*
623 * MCU encoding for AC initial scan (either spectral selection,
624 * or first pass of successive approximation).
625 */
626
627METHODDEF(boolean)
629{
630 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
631 const int * natural_order;
633 register int temp, temp2;
634 register int nbits;
635 register int r, k;
636 int Se, Al;
637
638 entropy->next_output_byte = cinfo->dest->next_output_byte;
639 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
640
641 /* Emit restart marker if needed */
642 if (cinfo->restart_interval)
643 if (entropy->restarts_to_go == 0)
644 emit_restart_e(entropy, entropy->next_restart_num);
645
646 Se = cinfo->Se;
647 Al = cinfo->Al;
648 natural_order = cinfo->natural_order;
649
650 /* Encode the MCU data block */
651 block = MCU_data[0];
652
653 /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
654
655 r = 0; /* r = run length of zeros */
656
657 for (k = cinfo->Ss; k <= Se; k++) {
658 if ((temp = (*block)[natural_order[k]]) == 0) {
659 r++;
660 continue;
661 }
662 /* We must apply the point transform by Al. For AC coefficients this
663 * is an integer division with rounding towards 0. To do this portably
664 * in C, we shift after obtaining the absolute value; so the code is
665 * interwoven with finding the abs value (temp) and output bits (temp2).
666 */
667 if (temp < 0) {
668 temp = -temp; /* temp is abs value of input */
669 temp >>= Al; /* apply the point transform */
670 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
671 temp2 = ~temp;
672 } else {
673 temp >>= Al; /* apply the point transform */
674 temp2 = temp;
675 }
676 /* Watch out for case that nonzero coef is zero after point transform */
677 if (temp == 0) {
678 r++;
679 continue;
680 }
681
682 /* Emit any pending EOBRUN */
683 if (entropy->EOBRUN > 0)
684 emit_eobrun(entropy);
685 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
686 while (r > 15) {
687 emit_ac_symbol(entropy, entropy->ac_tbl_no, 0xF0);
688 r -= 16;
689 }
690
691 /* Find the number of bits needed for the magnitude of the coefficient */
692 nbits = 1; /* there must be at least one 1 bit */
693 while ((temp >>= 1))
694 nbits++;
695 /* Check for out-of-range coefficient values */
696 if (nbits > MAX_COEF_BITS)
697 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
698
699 /* Count/emit Huffman symbol for run length / number of bits */
700 emit_ac_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
701
702 /* Emit that number of bits of the value, if positive, */
703 /* or the complement of its magnitude, if negative. */
704 emit_bits_e(entropy, (unsigned int) temp2, nbits);
705
706 r = 0; /* reset zero run length */
707 }
708
709 if (r > 0) { /* If there are trailing zeroes, */
710 entropy->EOBRUN++; /* count an EOB */
711 if (entropy->EOBRUN == 0x7FFF)
712 emit_eobrun(entropy); /* force it out to avoid overflow */
713 }
714
715 cinfo->dest->next_output_byte = entropy->next_output_byte;
716 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
717
718 /* Update restart-interval state too */
719 if (cinfo->restart_interval) {
720 if (entropy->restarts_to_go == 0) {
721 entropy->restarts_to_go = cinfo->restart_interval;
722 entropy->next_restart_num++;
723 entropy->next_restart_num &= 7;
724 }
725 entropy->restarts_to_go--;
726 }
727
728 return TRUE;
729}
730
731
732/*
733 * MCU encoding for DC successive approximation refinement scan.
734 * Note: we assume such scans can be multi-component,
735 * although the spec is not very clear on the point.
736 */
737
738METHODDEF(boolean)
740{
741 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
742 int Al, blkn;
743
744 entropy->next_output_byte = cinfo->dest->next_output_byte;
745 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
746
747 /* Emit restart marker if needed */
748 if (cinfo->restart_interval)
749 if (entropy->restarts_to_go == 0)
750 emit_restart_e(entropy, entropy->next_restart_num);
751
752 Al = cinfo->Al;
753
754 /* Encode the MCU data blocks */
755 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
756 /* We simply emit the Al'th bit of the DC coefficient value. */
757 emit_bits_e(entropy, (unsigned int) (MCU_data[blkn][0][0] >> Al), 1);
758 }
759
760 cinfo->dest->next_output_byte = entropy->next_output_byte;
761 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
762
763 /* Update restart-interval state too */
764 if (cinfo->restart_interval) {
765 if (entropy->restarts_to_go == 0) {
766 entropy->restarts_to_go = cinfo->restart_interval;
767 entropy->next_restart_num++;
768 entropy->next_restart_num &= 7;
769 }
770 entropy->restarts_to_go--;
771 }
772
773 return TRUE;
774}
775
776
777/*
778 * MCU encoding for AC successive approximation refinement scan.
779 */
780
781METHODDEF(boolean)
783{
784 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
785 const int * natural_order;
787 register int temp;
788 register int r, k;
789 int Se, Al;
790 int EOB;
791 char *BR_buffer;
792 unsigned int BR;
793 int absvalues[DCTSIZE2];
794
795 entropy->next_output_byte = cinfo->dest->next_output_byte;
796 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
797
798 /* Emit restart marker if needed */
799 if (cinfo->restart_interval)
800 if (entropy->restarts_to_go == 0)
801 emit_restart_e(entropy, entropy->next_restart_num);
802
803 Se = cinfo->Se;
804 Al = cinfo->Al;
805 natural_order = cinfo->natural_order;
806
807 /* Encode the MCU data block */
808 block = MCU_data[0];
809
810 /* It is convenient to make a pre-pass to determine the transformed
811 * coefficients' absolute values and the EOB position.
812 */
813 EOB = 0;
814 for (k = cinfo->Ss; k <= Se; k++) {
815 temp = (*block)[natural_order[k]];
816 /* We must apply the point transform by Al. For AC coefficients this
817 * is an integer division with rounding towards 0. To do this portably
818 * in C, we shift after obtaining the absolute value.
819 */
820 if (temp < 0)
821 temp = -temp; /* temp is abs value of input */
822 temp >>= Al; /* apply the point transform */
823 absvalues[k] = temp; /* save abs value for main pass */
824 if (temp == 1)
825 EOB = k; /* EOB = index of last newly-nonzero coef */
826 }
827
828 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
829
830 r = 0; /* r = run length of zeros */
831 BR = 0; /* BR = count of buffered bits added now */
832 BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
833
834 for (k = cinfo->Ss; k <= Se; k++) {
835 if ((temp = absvalues[k]) == 0) {
836 r++;
837 continue;
838 }
839
840 /* Emit any required ZRLs, but not if they can be folded into EOB */
841 while (r > 15 && k <= EOB) {
842 /* emit any pending EOBRUN and the BE correction bits */
843 emit_eobrun(entropy);
844 /* Emit ZRL */
845 emit_ac_symbol(entropy, entropy->ac_tbl_no, 0xF0);
846 r -= 16;
847 /* Emit buffered correction bits that must be associated with ZRL */
848 emit_buffered_bits(entropy, BR_buffer, BR);
849 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
850 BR = 0;
851 }
852
853 /* If the coef was previously nonzero, it only needs a correction bit.
854 * NOTE: a straight translation of the spec's figure G.7 would suggest
855 * that we also need to test r > 15. But if r > 15, we can only get here
856 * if k > EOB, which implies that this coefficient is not 1.
857 */
858 if (temp > 1) {
859 /* The correction bit is the next bit of the absolute value. */
860 BR_buffer[BR++] = (char) (temp & 1);
861 continue;
862 }
863
864 /* Emit any pending EOBRUN and the BE correction bits */
865 emit_eobrun(entropy);
866
867 /* Count/emit Huffman symbol for run length / number of bits */
868 emit_ac_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
869
870 /* Emit output bit for newly-nonzero coef */
871 temp = ((*block)[natural_order[k]] < 0) ? 0 : 1;
872 emit_bits_e(entropy, (unsigned int) temp, 1);
873
874 /* Emit buffered correction bits that must be associated with this code */
875 emit_buffered_bits(entropy, BR_buffer, BR);
876 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
877 BR = 0;
878 r = 0; /* reset zero run length */
879 }
880
881 if (r > 0 || BR > 0) { /* If there are trailing zeroes, */
882 entropy->EOBRUN++; /* count an EOB */
883 entropy->BE += BR; /* concat my correction bits to older ones */
884 /* We force out the EOB if we risk either:
885 * 1. overflow of the EOB counter;
886 * 2. overflow of the correction bit buffer during the next MCU.
887 */
888 if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
889 emit_eobrun(entropy);
890 }
891
892 cinfo->dest->next_output_byte = entropy->next_output_byte;
893 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
894
895 /* Update restart-interval state too */
896 if (cinfo->restart_interval) {
897 if (entropy->restarts_to_go == 0) {
898 entropy->restarts_to_go = cinfo->restart_interval;
899 entropy->next_restart_num++;
900 entropy->next_restart_num &= 7;
901 }
902 entropy->restarts_to_go--;
903 }
904
905 return TRUE;
906}
907
908
909/* Encode a single block's worth of coefficients */
910
911LOCAL(boolean)
913 c_derived_tbl *dctbl, c_derived_tbl *actbl)
914{
915 register int temp, temp2;
916 register int nbits;
917 register int r, k;
918 int Se = state->cinfo->lim_Se;
919 const int * natural_order = state->cinfo->natural_order;
920
921 /* Encode the DC coefficient difference per section F.1.2.1 */
922
923 temp = temp2 = block[0] - last_dc_val;
924
925 if (temp < 0) {
926 temp = -temp; /* temp is abs value of input */
927 /* For a negative input, want temp2 = bitwise complement of abs(input) */
928 /* This code assumes we are on a two's complement machine */
929 temp2--;
930 }
931
932 /* Find the number of bits needed for the magnitude of the coefficient */
933 nbits = 0;
934 while (temp) {
935 nbits++;
936 temp >>= 1;
937 }
938 /* Check for out-of-range coefficient values.
939 * Since we're encoding a difference, the range limit is twice as much.
940 */
941 if (nbits > MAX_COEF_BITS+1)
942 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
943
944 /* Emit the Huffman-coded symbol for the number of bits */
945 if (! emit_bits_s(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
946 return FALSE;
947
948 /* Emit that number of bits of the value, if positive, */
949 /* or the complement of its magnitude, if negative. */
950 if (nbits) /* emit_bits rejects calls with size 0 */
951 if (! emit_bits_s(state, (unsigned int) temp2, nbits))
952 return FALSE;
953
954 /* Encode the AC coefficients per section F.1.2.2 */
955
956 r = 0; /* r = run length of zeros */
957
958 for (k = 1; k <= Se; k++) {
959 if ((temp2 = block[natural_order[k]]) == 0) {
960 r++;
961 } else {
962 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
963 while (r > 15) {
964 if (! emit_bits_s(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0]))
965 return FALSE;
966 r -= 16;
967 }
968
969 temp = temp2;
970 if (temp < 0) {
971 temp = -temp; /* temp is abs value of input */
972 /* This code assumes we are on a two's complement machine */
973 temp2--;
974 }
975
976 /* Find the number of bits needed for the magnitude of the coefficient */
977 nbits = 1; /* there must be at least one 1 bit */
978 while ((temp >>= 1))
979 nbits++;
980 /* Check for out-of-range coefficient values */
981 if (nbits > MAX_COEF_BITS)
982 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
983
984 /* Emit Huffman symbol for run length / number of bits */
985 temp = (r << 4) + nbits;
986 if (! emit_bits_s(state, actbl->ehufco[temp], actbl->ehufsi[temp]))
987 return FALSE;
988
989 /* Emit that number of bits of the value, if positive, */
990 /* or the complement of its magnitude, if negative. */
991 if (! emit_bits_s(state, (unsigned int) temp2, nbits))
992 return FALSE;
993
994 r = 0;
995 }
996 }
997
998 /* If the last coef(s) were zero, emit an end-of-block code */
999 if (r > 0)
1000 if (! emit_bits_s(state, actbl->ehufco[0], actbl->ehufsi[0]))
1001 return FALSE;
1002
1003 return TRUE;
1004}
1005
1006
1007/*
1008 * Encode and output one MCU's worth of Huffman-compressed coefficients.
1009 */
1010
1011METHODDEF(boolean)
1013{
1014 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1016 int blkn, ci;
1018
1019 /* Load up working state */
1020 state.next_output_byte = cinfo->dest->next_output_byte;
1021 state.free_in_buffer = cinfo->dest->free_in_buffer;
1022 ASSIGN_STATE(state.cur, entropy->saved);
1023 state.cinfo = cinfo;
1024
1025 /* Emit restart marker if needed */
1026 if (cinfo->restart_interval) {
1027 if (entropy->restarts_to_go == 0)
1028 if (! emit_restart_s(&state, entropy->next_restart_num))
1029 return FALSE;
1030 }
1031
1032 /* Encode the MCU data blocks */
1033 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1034 ci = cinfo->MCU_membership[blkn];
1035 compptr = cinfo->cur_comp_info[ci];
1036 if (! encode_one_block(&state,
1037 MCU_data[blkn][0], state.cur.last_dc_val[ci],
1039 entropy->ac_derived_tbls[compptr->ac_tbl_no]))
1040 return FALSE;
1041 /* Update last_dc_val */
1042 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
1043 }
1044
1045 /* Completed MCU, so update state */
1046 cinfo->dest->next_output_byte = state.next_output_byte;
1047 cinfo->dest->free_in_buffer = state.free_in_buffer;
1048 ASSIGN_STATE(entropy->saved, state.cur);
1049
1050 /* Update restart-interval state too */
1051 if (cinfo->restart_interval) {
1052 if (entropy->restarts_to_go == 0) {
1053 entropy->restarts_to_go = cinfo->restart_interval;
1054 entropy->next_restart_num++;
1055 entropy->next_restart_num &= 7;
1056 }
1057 entropy->restarts_to_go--;
1058 }
1059
1060 return TRUE;
1061}
1062
1063
1064/*
1065 * Finish up at the end of a Huffman-compressed scan.
1066 */
1067
1068METHODDEF(void)
1070{
1071 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1073
1074 if (cinfo->progressive_mode) {
1075 entropy->next_output_byte = cinfo->dest->next_output_byte;
1076 entropy->free_in_buffer = cinfo->dest->free_in_buffer;
1077
1078 /* Flush out any buffered data */
1079 emit_eobrun(entropy);
1080 flush_bits_e(entropy);
1081
1082 cinfo->dest->next_output_byte = entropy->next_output_byte;
1083 cinfo->dest->free_in_buffer = entropy->free_in_buffer;
1084 } else {
1085 /* Load up working state ... flush_bits needs it */
1086 state.next_output_byte = cinfo->dest->next_output_byte;
1087 state.free_in_buffer = cinfo->dest->free_in_buffer;
1088 ASSIGN_STATE(state.cur, entropy->saved);
1089 state.cinfo = cinfo;
1090
1091 /* Flush out the last data */
1092 if (! flush_bits_s(&state))
1093 ERREXIT(cinfo, JERR_CANT_SUSPEND);
1094
1095 /* Update state */
1096 cinfo->dest->next_output_byte = state.next_output_byte;
1097 cinfo->dest->free_in_buffer = state.free_in_buffer;
1098 ASSIGN_STATE(entropy->saved, state.cur);
1099 }
1100}
1101
1102
1103/*
1104 * Huffman coding optimization.
1105 *
1106 * We first scan the supplied data and count the number of uses of each symbol
1107 * that is to be Huffman-coded. (This process MUST agree with the code above.)
1108 * Then we build a Huffman coding tree for the observed counts.
1109 * Symbols which are not needed at all for the particular image are not
1110 * assigned any code, which saves space in the DHT marker as well as in
1111 * the compressed data.
1112 */
1113
1114
1115/* Process a single block's worth of coefficients */
1116
1117LOCAL(void)
1119 long dc_counts[], long ac_counts[])
1120{
1121 register int temp;
1122 register int nbits;
1123 register int r, k;
1124 int Se = cinfo->lim_Se;
1125 const int * natural_order = cinfo->natural_order;
1126
1127 /* Encode the DC coefficient difference per section F.1.2.1 */
1128
1129 temp = block[0] - last_dc_val;
1130 if (temp < 0)
1131 temp = -temp;
1132
1133 /* Find the number of bits needed for the magnitude of the coefficient */
1134 nbits = 0;
1135 while (temp) {
1136 nbits++;
1137 temp >>= 1;
1138 }
1139 /* Check for out-of-range coefficient values.
1140 * Since we're encoding a difference, the range limit is twice as much.
1141 */
1142 if (nbits > MAX_COEF_BITS+1)
1143 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
1144
1145 /* Count the Huffman symbol for the number of bits */
1146 dc_counts[nbits]++;
1147
1148 /* Encode the AC coefficients per section F.1.2.2 */
1149
1150 r = 0; /* r = run length of zeros */
1151
1152 for (k = 1; k <= Se; k++) {
1153 if ((temp = block[natural_order[k]]) == 0) {
1154 r++;
1155 } else {
1156 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
1157 while (r > 15) {
1158 ac_counts[0xF0]++;
1159 r -= 16;
1160 }
1161
1162 /* Find the number of bits needed for the magnitude of the coefficient */
1163 if (temp < 0)
1164 temp = -temp;
1165
1166 /* Find the number of bits needed for the magnitude of the coefficient */
1167 nbits = 1; /* there must be at least one 1 bit */
1168 while ((temp >>= 1))
1169 nbits++;
1170 /* Check for out-of-range coefficient values */
1171 if (nbits > MAX_COEF_BITS)
1172 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
1173
1174 /* Count Huffman symbol for run length / number of bits */
1175 ac_counts[(r << 4) + nbits]++;
1176
1177 r = 0;
1178 }
1179 }
1180
1181 /* If the last coef(s) were zero, emit an end-of-block code */
1182 if (r > 0)
1183 ac_counts[0]++;
1184}
1185
1186
1187/*
1188 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
1189 * No data is actually output, so no suspension return is possible.
1190 */
1191
1192METHODDEF(boolean)
1194{
1195 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1196 int blkn, ci;
1198
1199 /* Take care of restart intervals if needed */
1200 if (cinfo->restart_interval) {
1201 if (entropy->restarts_to_go == 0) {
1202 /* Re-initialize DC predictions to 0 */
1203 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
1204 entropy->saved.last_dc_val[ci] = 0;
1205 /* Update restart state */
1206 entropy->restarts_to_go = cinfo->restart_interval;
1207 }
1208 entropy->restarts_to_go--;
1209 }
1210
1211 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1212 ci = cinfo->MCU_membership[blkn];
1213 compptr = cinfo->cur_comp_info[ci];
1214 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
1215 entropy->dc_count_ptrs[compptr->dc_tbl_no],
1216 entropy->ac_count_ptrs[compptr->ac_tbl_no]);
1217 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
1218 }
1219
1220 return TRUE;
1221}
1222
1223
1224/*
1225 * Generate the best Huffman code table for the given counts, fill htbl.
1226 *
1227 * The JPEG standard requires that no symbol be assigned a codeword of all
1228 * one bits (so that padding bits added at the end of a compressed segment
1229 * can't look like a valid code). Because of the canonical ordering of
1230 * codewords, this just means that there must be an unused slot in the
1231 * longest codeword length category. Section K.2 of the JPEG spec suggests
1232 * reserving such a slot by pretending that symbol 256 is a valid symbol
1233 * with count 1. In theory that's not optimal; giving it count zero but
1234 * including it in the symbol set anyway should give a better Huffman code.
1235 * But the theoretically better code actually seems to come out worse in
1236 * practice, because it produces more all-ones bytes (which incur stuffed
1237 * zero bytes in the final file). In any case the difference is tiny.
1238 *
1239 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
1240 * If some symbols have a very small but nonzero probability, the Huffman tree
1241 * must be adjusted to meet the code length restriction. We currently use
1242 * the adjustment method suggested in JPEG section K.2. This method is *not*
1243 * optimal; it may not choose the best possible limited-length code. But
1244 * typically only very-low-frequency symbols will be given less-than-optimal
1245 * lengths, so the code is almost optimal. Experimental comparisons against
1246 * an optimal limited-length-code algorithm indicate that the difference is
1247 * microscopic --- usually less than a hundredth of a percent of total size.
1248 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
1249 */
1250
1251LOCAL(void)
1253{
1254#define MAX_CLEN 32 /* assumed maximum initial code length */
1255 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
1256 int codesize[257]; /* codesize[k] = code length of symbol k */
1257 int others[257]; /* next symbol in current branch of tree */
1258 int c1, c2, i, j;
1259 UINT8 *p;
1260 long v;
1261
1262 freq[256] = 1; /* make sure 256 has a nonzero count */
1263 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
1264 * that no real symbol is given code-value of all ones, because 256
1265 * will be placed last in the largest codeword category.
1266 * In the symbol list build procedure this element serves as sentinel
1267 * for the zero run loop.
1268 */
1269
1270#ifndef DONT_USE_FANCY_HUFF_OPT
1271
1272 /* Build list of symbols sorted in order of descending frequency */
1273 /* This approach has several benefits (thank to John Korejwa for the idea):
1274 * 1.
1275 * If a codelength category is split during the length limiting procedure
1276 * below, the feature that more frequent symbols are assigned shorter
1277 * codewords remains valid for the adjusted code.
1278 * 2.
1279 * To reduce consecutive ones in a Huffman data stream (thus reducing the
1280 * number of stuff bytes in JPEG) it is preferable to follow 0 branches
1281 * (and avoid 1 branches) as much as possible. This is easily done by
1282 * assigning symbols to leaves of the Huffman tree in order of decreasing
1283 * frequency, with no secondary sort based on codelengths.
1284 * 3.
1285 * The symbol list can be built independently from the assignment of code
1286 * lengths by the Huffman procedure below.
1287 * Note: The symbol list build procedure must be performed first, because
1288 * the Huffman procedure assigning the codelengths clobbers the frequency
1289 * counts!
1290 */
1291
1292 /* Here we use the others array as a linked list of nonzero frequencies
1293 * to be sorted. Already sorted elements are removed from the list.
1294 */
1295
1296 /* Building list */
1297
1298 /* This item does not correspond to a valid symbol frequency and is used
1299 * as starting index.
1300 */
1301 j = 256;
1302
1303 for (i = 0;; i++) {
1304 if (freq[i] == 0) /* skip zero frequencies */
1305 continue;
1306 if (i > 255)
1307 break;
1308 others[j] = i; /* this symbol value */
1309 j = i; /* previous symbol value */
1310 }
1311 others[j] = -1; /* mark end of list */
1312
1313 /* Sorting list */
1314
1315 p = htbl->huffval;
1316 while ((c1 = others[256]) >= 0) {
1317 v = freq[c1];
1318 i = c1; /* first symbol value */
1319 j = 256; /* pseudo symbol value for starting index */
1320 while ((c2 = others[c1]) >= 0) {
1321 if (freq[c2] > v) {
1322 v = freq[c2];
1323 i = c2; /* this symbol value */
1324 j = c1; /* previous symbol value */
1325 }
1326 c1 = c2;
1327 }
1328 others[j] = others[i]; /* remove this symbol i from list */
1329 *p++ = (UINT8) i;
1330 }
1331
1332#endif /* DONT_USE_FANCY_HUFF_OPT */
1333
1334 /* This algorithm is explained in section K.2 of the JPEG standard */
1335
1337 MEMZERO(codesize, SIZEOF(codesize));
1338 for (i = 0; i < 257; i++)
1339 others[i] = -1; /* init links to empty */
1340
1341 /* Huffman's basic algorithm to assign optimal code lengths to symbols */
1342
1343 for (;;) {
1344 /* Find the smallest nonzero frequency, set c1 = its symbol */
1345 /* In case of ties, take the larger symbol number */
1346 c1 = -1;
1347 v = 1000000000L;
1348 for (i = 0; i <= 256; i++) {
1349 if (freq[i] && freq[i] <= v) {
1350 v = freq[i];
1351 c1 = i;
1352 }
1353 }
1354
1355 /* Find the next smallest nonzero frequency, set c2 = its symbol */
1356 /* In case of ties, take the larger symbol number */
1357 c2 = -1;
1358 v = 1000000000L;
1359 for (i = 0; i <= 256; i++) {
1360 if (freq[i] && freq[i] <= v && i != c1) {
1361 v = freq[i];
1362 c2 = i;
1363 }
1364 }
1365
1366 /* Done if we've merged everything into one frequency */
1367 if (c2 < 0)
1368 break;
1369
1370 /* Else merge the two counts/trees */
1371 freq[c1] += freq[c2];
1372 freq[c2] = 0;
1373
1374 /* Increment the codesize of everything in c1's tree branch */
1375 codesize[c1]++;
1376 while (others[c1] >= 0) {
1377 c1 = others[c1];
1378 codesize[c1]++;
1379 }
1380
1381 others[c1] = c2; /* chain c2 onto c1's tree branch */
1382
1383 /* Increment the codesize of everything in c2's tree branch */
1384 codesize[c2]++;
1385 while (others[c2] >= 0) {
1386 c2 = others[c2];
1387 codesize[c2]++;
1388 }
1389 }
1390
1391 /* Now count the number of symbols of each code length */
1392 for (i = 0; i <= 256; i++) {
1393 if (codesize[i]) {
1394 /* The JPEG standard seems to think that this can't happen, */
1395 /* but I'm paranoid... */
1396 if (codesize[i] > MAX_CLEN)
1397 ERREXIT(cinfo, JERR_HUFF_CLEN_OUTOFBOUNDS);
1398
1399 bits[codesize[i]]++;
1400 }
1401 }
1402
1403 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
1404 * Huffman procedure assigned any such lengths, we must adjust the coding.
1405 * Here is what the JPEG spec says about how this next bit works:
1406 * Since symbols are paired for the longest Huffman code, the symbols are
1407 * removed from this length category two at a time. The prefix for the pair
1408 * (which is one bit shorter) is allocated to one of the pair; then,
1409 * skipping the BITS entry for that prefix length, a code word from the next
1410 * shortest nonzero BITS entry is converted into a prefix for two code words
1411 * one bit longer.
1412 */
1413
1414 for (i = MAX_CLEN; i > 16; i--) {
1415 while (bits[i] > 0) {
1416 j = i - 2; /* find length of new prefix to be used */
1417 while (bits[j] == 0) {
1418 if (j == 0)
1419 ERREXIT(cinfo, JERR_HUFF_CLEN_OUTOFBOUNDS);
1420 j--;
1421 }
1422
1423 bits[i] -= 2; /* remove two symbols */
1424 bits[i-1]++; /* one goes in this length */
1425 bits[j+1] += 2; /* two new symbols in this length */
1426 bits[j]--; /* symbol of this length is now a prefix */
1427 }
1428 }
1429
1430 /* Remove the count for the pseudo-symbol 256 from the largest codelength */
1431 while (bits[i] == 0) /* find largest codelength still in use */
1432 i--;
1433 bits[i]--;
1434
1435 /* Return final symbol counts (only for lengths 0..16) */
1436 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
1437
1438#ifdef DONT_USE_FANCY_HUFF_OPT
1439
1440 /* Return a list of the symbols sorted by code length */
1441 /* Note: Due to the codelength changes made above, it can happen
1442 * that more frequent symbols are assigned longer codewords.
1443 */
1444 p = htbl->huffval;
1445 for (i = 1; i <= MAX_CLEN; i++) {
1446 for (j = 0; j <= 255; j++) {
1447 if (codesize[j] == i) {
1448 *p++ = (UINT8) j;
1449 }
1450 }
1451 }
1452
1453#endif /* DONT_USE_FANCY_HUFF_OPT */
1454
1455 /* Set sent_table FALSE so updated table will be written to JPEG file. */
1456 htbl->sent_table = FALSE;
1457}
1458
1459
1460/*
1461 * Finish up a statistics-gathering pass and create the new Huffman tables.
1462 */
1463
1464METHODDEF(void)
1466{
1467 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1468 int ci, tbl;
1470 JHUFF_TBL **htblptr;
1471 boolean did_dc[NUM_HUFF_TBLS];
1472 boolean did_ac[NUM_HUFF_TBLS];
1473
1474 if (cinfo->progressive_mode)
1475 /* Flush out buffered data (all we care about is counting the EOB symbol) */
1476 emit_eobrun(entropy);
1477
1478 /* It's important not to apply jpeg_gen_optimal_table more than once
1479 * per table, because it clobbers the input frequency counts!
1480 */
1481 MEMZERO(did_dc, SIZEOF(did_dc));
1482 MEMZERO(did_ac, SIZEOF(did_ac));
1483
1484 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1485 compptr = cinfo->cur_comp_info[ci];
1486 /* DC needs no table for refinement scan */
1487 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
1488 tbl = compptr->dc_tbl_no;
1489 if (! did_dc[tbl]) {
1490 htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
1491 if (*htblptr == NULL)
1492 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1493 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[tbl]);
1494 did_dc[tbl] = TRUE;
1495 }
1496 }
1497 /* AC needs no table when not present */
1498 if (cinfo->Se) {
1499 tbl = compptr->ac_tbl_no;
1500 if (! did_ac[tbl]) {
1501 htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
1502 if (*htblptr == NULL)
1503 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1504 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[tbl]);
1505 did_ac[tbl] = TRUE;
1506 }
1507 }
1508 }
1509}
1510
1511
1512/*
1513 * Initialize for a Huffman-compressed scan.
1514 * If gather_statistics is TRUE, we do not output anything during the scan,
1515 * just count the Huffman symbols used and generate Huffman code tables.
1516 */
1517
1518METHODDEF(void)
1519start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
1520{
1521 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1522 int ci, tbl;
1524
1525 if (gather_statistics)
1526 entropy->pub.finish_pass = finish_pass_gather;
1527 else
1528 entropy->pub.finish_pass = finish_pass_huff;
1529
1530 if (cinfo->progressive_mode) {
1531 entropy->cinfo = cinfo;
1532 entropy->gather_statistics = gather_statistics;
1533
1534 /* We assume jcmaster.c already validated the scan parameters. */
1535
1536 /* Select execution routine */
1537 if (cinfo->Ah == 0) {
1538 if (cinfo->Ss == 0)
1539 entropy->pub.encode_mcu = encode_mcu_DC_first;
1540 else
1541 entropy->pub.encode_mcu = encode_mcu_AC_first;
1542 } else {
1543 if (cinfo->Ss == 0)
1544 entropy->pub.encode_mcu = encode_mcu_DC_refine;
1545 else {
1546 entropy->pub.encode_mcu = encode_mcu_AC_refine;
1547 /* AC refinement needs a correction bit buffer */
1548 if (entropy->bit_buffer == NULL)
1549 entropy->bit_buffer = (char *) (*cinfo->mem->alloc_small)
1550 ((j_common_ptr) cinfo, JPOOL_IMAGE, MAX_CORR_BITS * SIZEOF(char));
1551 }
1552 }
1553
1554 /* Initialize AC stuff */
1555 entropy->ac_tbl_no = cinfo->cur_comp_info[0]->ac_tbl_no;
1556 entropy->EOBRUN = 0;
1557 entropy->BE = 0;
1558 } else {
1559 if (gather_statistics)
1560 entropy->pub.encode_mcu = encode_mcu_gather;
1561 else
1562 entropy->pub.encode_mcu = encode_mcu_huff;
1563 }
1564
1565 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1566 compptr = cinfo->cur_comp_info[ci];
1567 /* DC needs no table for refinement scan */
1568 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
1569 tbl = compptr->dc_tbl_no;
1570 if (gather_statistics) {
1571 /* Check for invalid table index */
1572 /* (make_c_derived_tbl does this in the other path) */
1573 if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
1574 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
1575 /* Allocate and zero the statistics tables */
1576 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
1577 if (entropy->dc_count_ptrs[tbl] == NULL)
1578 entropy->dc_count_ptrs[tbl] = (long *) (*cinfo->mem->alloc_small)
1579 ((j_common_ptr) cinfo, JPOOL_IMAGE, 257 * SIZEOF(long));
1580 MEMZERO(entropy->dc_count_ptrs[tbl], 257 * SIZEOF(long));
1581 } else {
1582 /* Compute derived values for Huffman tables */
1583 /* We may do this more than once for a table, but it's not expensive */
1584 jpeg_make_c_derived_tbl(cinfo, TRUE, tbl,
1585 & entropy->dc_derived_tbls[tbl]);
1586 }
1587 /* Initialize DC predictions to 0 */
1588 entropy->saved.last_dc_val[ci] = 0;
1589 }
1590 /* AC needs no table when not present */
1591 if (cinfo->Se) {
1592 tbl = compptr->ac_tbl_no;
1593 if (gather_statistics) {
1594 if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
1595 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
1596 if (entropy->ac_count_ptrs[tbl] == NULL)
1597 entropy->ac_count_ptrs[tbl] = (long *) (*cinfo->mem->alloc_small)
1598 ((j_common_ptr) cinfo, JPOOL_IMAGE, 257 * SIZEOF(long));
1599 MEMZERO(entropy->ac_count_ptrs[tbl], 257 * SIZEOF(long));
1600 } else {
1601 jpeg_make_c_derived_tbl(cinfo, FALSE, tbl,
1602 & entropy->ac_derived_tbls[tbl]);
1603 }
1604 }
1605 }
1606
1607 /* Initialize bit buffer to empty */
1608 entropy->saved.put_buffer = 0;
1609 entropy->saved.put_bits = 0;
1610
1611 /* Initialize restart stuff */
1612 entropy->restarts_to_go = cinfo->restart_interval;
1613 entropy->next_restart_num = 0;
1614}
1615
1616
1617/*
1618 * Module initialization routine for Huffman entropy encoding.
1619 */
1620
1621GLOBAL(void)
1623{
1624 huff_entropy_ptr entropy;
1625 int i;
1626
1627 entropy = (huff_entropy_ptr) (*cinfo->mem->alloc_small)
1629 cinfo->entropy = &entropy->pub;
1630 entropy->pub.start_pass = start_pass_huff;
1631
1632 /* Mark tables unallocated */
1633 for (i = 0; i < NUM_HUFF_TBLS; i++) {
1634 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1635 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
1636 }
1637
1638 if (cinfo->progressive_mode)
1639 entropy->bit_buffer = NULL; /* needed only in AC refinement scan */
1640}
signed int INT32
unsigned char UINT8
static int state
Definition: maze.c:121
r l[0]
Definition: byte_order.h:168
#define SIZEOF(_ar)
Definition: calc.h:97
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
unsigned char
Definition: typeof.h:29
const GLdouble * v
Definition: gl.h:2040
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLsizeiptr size
Definition: glext.h:5919
const GLubyte * c
Definition: glext.h:8905
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
GLfloat GLfloat p
Definition: glext.h:8902
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
htest_one_block(j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, long dc_counts[], long ac_counts[])
Definition: jchuff.c:1118
INLINE emit_ac_symbol(huff_entropy_ptr entropy, int tbl_no, int symbol)
Definition: jchuff.c:428
#define ASSIGN_STATE(dest, src)
Definition: jchuff.c:67
encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:628
#define ISHIFT_TEMPS
Definition: jchuff.c:150
dump_buffer_e(huff_entropy_ptr entropy)
Definition: jchuff.c:283
encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:545
encode_mcu_gather(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:1193
#define MAX_COEF_BITS
Definition: jchuff.c:37
#define emit_byte_e(entropy, val)
Definition: jchuff.c:261
jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[])
Definition: jchuff.c:1252
encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:1012
encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:739
jpeg_make_c_derived_tbl(j_compress_ptr cinfo, boolean isDC, int tblno, c_derived_tbl **pdtbl)
Definition: jchuff.c:161
jinit_huff_encoder(j_compress_ptr cinfo)
Definition: jchuff.c:1622
dump_buffer_s(working_state *state)
Definition: jchuff.c:268
emit_restart_e(huff_entropy_ptr entropy, int restart_num)
Definition: jchuff.c:515
#define IRIGHT_SHIFT(x, shft)
Definition: jchuff.c:151
#define MAX_CLEN
#define emit_byte_s(state, val, action)
Definition: jchuff.c:254
finish_pass_gather(j_compress_ptr cinfo)
Definition: jchuff.c:1465
INLINE emit_bits_e(huff_entropy_ptr entropy, unsigned int code, int size)
Definition: jchuff.c:348
INLINE emit_bits_s(working_state *state, unsigned int code, int size)
Definition: jchuff.c:306
flush_bits_s(working_state *state)
Definition: jchuff.c:390
INLINE emit_dc_symbol(huff_entropy_ptr entropy, int tbl_no, int symbol)
Definition: jchuff.c:415
finish_pass_huff(j_compress_ptr cinfo)
Definition: jchuff.c:1069
emit_buffered_bits(huff_entropy_ptr entropy, char *bufstart, unsigned int nbits)
Definition: jchuff.c:444
emit_eobrun(huff_entropy_ptr entropy)
Definition: jchuff.c:463
flush_bits_e(huff_entropy_ptr entropy)
Definition: jchuff.c:401
encode_one_block(working_state *state, JCOEFPTR block, int last_dc_val, c_derived_tbl *dctbl, c_derived_tbl *actbl)
Definition: jchuff.c:912
#define MAX_CORR_BITS
Definition: jchuff.c:136
start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics)
Definition: jchuff.c:1519
emit_restart_s(working_state *state, int restart_num)
Definition: jchuff.c:494
encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jchuff.c:782
huff_entropy_encoder * huff_entropy_ptr
Definition: jchuff.c:117
jpeg_std_huff_table(j_common_ptr cinfo, boolean isDC, int tblno)
Definition: jcomapi.c:117
jpeg_alloc_huff_table(j_common_ptr cinfo)
Definition: jcomapi.c:99
jpeg_component_info * compptr
Definition: jdct.h:238
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
#define MEMCOPY(dest, src, size)
Definition: jinclude.h:69
char JOCTET
Definition: jmorecfg.h:167
#define LOCAL(type)
Definition: jmorecfg.h:289
#define METHODDEF(type)
Definition: jmorecfg.h:287
#define GLOBAL(type)
Definition: jmorecfg.h:291
JBLOCK FAR * JBLOCKROW
Definition: jpeglib.h:80
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
boolean isDC
Definition: jpeglib.h:1010
#define NUM_HUFF_TBLS
Definition: jpeglib.h:53
JCOEF FAR * JCOEFPTR
Definition: jpeglib.h:84
#define JPEG_RST0
Definition: jpeglib.h:1126
boolean int tblno
Definition: jpeglib.h:1010
#define JPOOL_IMAGE
Definition: jpeglib.h:808
#define MAX_COMPS_IN_SCAN
Definition: jpeglib.h:55
#define DCTSIZE2
Definition: jpeglib.h:51
if(dx< 0)
Definition: linetemp.h:194
static char * dest
Definition: rtl.c:135
int k
Definition: mpi.c:3369
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
#define INLINE
Definition: rosdhcp.h:56
static calc_node_t temp
Definition: rpn_ieee.c:38
UINT8 bits[17]
Definition: jpeglib.h:111
UINT8 huffval[256]
Definition: jpeglib.h:113
unsigned int ehufco[256]
Definition: jchuff.c:43
char ehufsi[256]
Definition: jchuff.c:44
Definition: inflate.c:139
c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]
Definition: jchuff.c:92
struct jpeg_entropy_encoder pub
Definition: jchuff.c:82
j_compress_ptr cinfo
Definition: jchuff.c:107
unsigned int BE
Definition: jchuff.c:112
c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]
Definition: jchuff.c:91
unsigned int restarts_to_go
Definition: jchuff.c:87
savable_state saved
Definition: jchuff.c:84
boolean gather_statistics
Definition: jchuff.c:101
long * ac_count_ptrs[NUM_HUFF_TBLS]
Definition: jchuff.c:96
JOCTET * next_output_byte
Definition: jchuff.c:105
long * dc_count_ptrs[NUM_HUFF_TBLS]
Definition: jchuff.c:95
unsigned int EOBRUN
Definition: jchuff.c:111
size_t free_in_buffer
Definition: jchuff.c:106
INT32 put_buffer
Definition: jchuff.c:56
int put_bits
Definition: jchuff.c:57
int last_dc_val[MAX_COMPS_IN_SCAN]
Definition: jchuff.c:58
size_t free_in_buffer
Definition: jchuff.c:125
savable_state cur
Definition: jchuff.c:126
JOCTET * next_output_byte
Definition: jchuff.c:124
j_compress_ptr cinfo
Definition: jchuff.c:127
#define MEMZERO(addr, type, size)
Definition: svc_dg.c:324
static unsigned int block
Definition: xmlmemory.c:101