4 * Developed 1997-2013 by Guido Vollbeding.
5 * This file is part of the Independent JPEG Group's software.
6 * For conditions of distribution and use, see the accompanying README file.
8 * This file contains portable arithmetic entropy encoding routines for JPEG
9 * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
11 * Both sequential and progressive modes are supported in this single module.
13 * Suspension is not currently supported in this module.
16 #define JPEG_INTERNALS
21 /* Expanded entropy encoder object for arithmetic encoding. */
24 struct jpeg_entropy_encoder pub; /* public fields */
26 INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */
27 INT32 a; /* A register, normalized size of coding interval */
28 INT32 sc; /* counter for stacked 0xFF values which might overflow */
29 INT32 zc; /* counter for pending 0x00 output values which might *
30 * be discarded at the end ("Pacman" termination) */
31 int ct; /* bit shift counter, determines when next byte will be written */
32 int buffer; /* buffer for most recent output byte != 0xFF */
34 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
35 int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
37 unsigned int restarts_to_go; /* MCUs left in this restart interval */
38 int next_restart_num; /* next restart number to write (0-7) */
40 /* Pointers to statistics areas (these workspaces have image lifespan) */
41 unsigned char * dc_stats[NUM_ARITH_TBLS];
42 unsigned char * ac_stats[NUM_ARITH_TBLS];
44 /* Statistics bin for coding with fixed probability 0.5 */
45 unsigned char fixed_bin[4];
46 } arith_entropy_encoder;
48 typedef arith_entropy_encoder * arith_entropy_ptr;
50 /* The following two definitions specify the allocation chunk size
51 * for the statistics area.
52 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
53 * 49 statistics bins for DC, and 245 statistics bins for AC coding.
55 * We use a compact representation with 1 byte per statistics bin,
56 * thus the numbers directly represent byte sizes.
57 * This 1 byte per statistics bin contains the meaning of the MPS
58 * (more probable symbol) in the highest bit (mask 0x80), and the
59 * index into the probability estimation state machine table
60 * in the lower bits (mask 0x7F).
63 #define DC_STAT_BINS 64
64 #define AC_STAT_BINS 256
66 /* NOTE: Uncomment the following #define if you want to use the
67 * given formula for calculating the AC conditioning parameter Kx
68 * for spectral selection progressive coding in section G.1.3.2
69 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
70 * Although the spec and P&M authors claim that this "has proven
71 * to give good results for 8 bit precision samples", I'm not
72 * convinced yet that this is really beneficial.
73 * Early tests gave only very marginal compression enhancements
74 * (a few - around 5 or so - bytes even for very large files),
75 * which would turn out rather negative if we'd suppress the
76 * DAC (Define Arithmetic Conditioning) marker segments for
77 * the default parameters in the future.
78 * Note that currently the marker writing module emits 12-byte
79 * DAC segments for a full-component scan in a color image.
80 * This is not worth worrying about IMHO. However, since the
81 * spec defines the default values to be used if the tables
82 * are omitted (unlike Huffman tables, which are required
83 * anyway), one might optimize this behaviour in the future,
84 * and then it would be disadvantageous to use custom tables if
85 * they don't provide sufficient gain to exceed the DAC size.
87 * On the other hand, I'd consider it as a reasonable result
88 * that the conditioning has no significant influence on the
89 * compression performance. This means that the basic
90 * statistical model is already rather stable.
92 * Thus, at the moment, we use the default conditioning values
93 * anyway, and do not use the custom formula.
95 #define CALCULATE_SPECTRAL_CONDITIONING
98 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
99 * We assume that int right shift is unsigned if INT32 right shift is,
100 * which should be safe.
103 #ifdef RIGHT_SHIFT_IS_UNSIGNED
104 #define ISHIFT_TEMPS int ishift_temp;
105 #define IRIGHT_SHIFT(x,shft) \
106 ((ishift_temp = (x)) < 0 ? \
107 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
108 (ishift_temp >> (shft)))
111 #define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
116 emit_byte (int val, j_compress_ptr cinfo)
117 /* Write next output byte; we do not support suspension in this module. */
119 struct jpeg_destination_mgr * dest = cinfo->dest;
121 *dest->next_output_byte++ = (JOCTET) val;
122 if (--dest->free_in_buffer == 0)
123 if (! (*dest->empty_output_buffer) (cinfo))
124 ERREXIT(cinfo, JERR_CANT_SUSPEND);
129 * Finish up at the end of an arithmetic-compressed scan.
133 finish_pass (j_compress_ptr cinfo)
135 arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
138 /* Section D.1.8: Termination of encoding */
140 /* Find the e->c in the coding interval with the largest
141 * number of trailing zero bits */
142 if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
143 e->c = temp + 0x8000L;
146 /* Send remaining bytes to output */
148 if (e->c & 0xF8000000L) {
149 /* One final overflow has to be handled */
150 if (e->buffer >= 0) {
152 do emit_byte(0x00, cinfo);
154 emit_byte(e->buffer + 1, cinfo);
155 if (e->buffer + 1 == 0xFF)
156 emit_byte(0x00, cinfo);
158 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
163 else if (e->buffer >= 0) {
165 do emit_byte(0x00, cinfo);
167 emit_byte(e->buffer, cinfo);
171 do emit_byte(0x00, cinfo);
174 emit_byte(0xFF, cinfo);
175 emit_byte(0x00, cinfo);
179 /* Output final bytes only if they are not 0x00 */
180 if (e->c & 0x7FFF800L) {
181 if (e->zc) /* output final pending zero bytes */
182 do emit_byte(0x00, cinfo);
184 emit_byte((e->c >> 19) & 0xFF, cinfo);
185 if (((e->c >> 19) & 0xFF) == 0xFF)
186 emit_byte(0x00, cinfo);
187 if (e->c & 0x7F800L) {
188 emit_byte((e->c >> 11) & 0xFF, cinfo);
189 if (((e->c >> 11) & 0xFF) == 0xFF)
190 emit_byte(0x00, cinfo);
197 * The core arithmetic encoding routine (common in JPEG and JBIG).
198 * This needs to go as fast as possible.
199 * Machine-dependent optimization facilities
200 * are not utilized in this portable implementation.
201 * However, this code should be fairly efficient and
202 * may be a good base for further optimizations anyway.
204 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
206 * Note: I've added full "Pacman" termination support to the
207 * byte output routines, which is equivalent to the optional
208 * Discard_final_zeros procedure (Figure D.15) in the spec.
209 * Thus, we always produce the shortest possible output
210 * stream compliant to the spec (no trailing zero bytes,
211 * except for FF stuffing).
213 * I've also introduced a new scheme for accessing
214 * the probability estimation state machine table,
215 * derived from Markus Kuhn's JBIG implementation.
219 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val)
221 register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
222 register unsigned char nl, nm;
223 register INT32 qe, temp;
226 /* Fetch values from our compact representation of Table D.3(D.2):
227 * Qe values and probability estimation state machine
230 qe = jpeg_aritab[sv & 0x7F]; /* => Qe_Value */
231 nl = qe & 0xFF; qe >>= 8; /* Next_Index_LPS + Switch_MPS */
232 nm = qe & 0xFF; qe >>= 8; /* Next_Index_MPS */
234 /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
236 if (val != (sv >> 7)) {
237 /* Encode the less probable symbol */
239 /* If the interval size (qe) for the less probable symbol (LPS)
240 * is larger than the interval size for the MPS, then exchange
241 * the two symbols for coding efficiency, otherwise code the LPS
246 *st = (sv & 0x80) ^ nl; /* Estimate_after_LPS */
248 /* Encode the more probable symbol */
250 return; /* A >= 0x8000 -> ready, no renormalization required */
252 /* If the interval size (qe) for the less probable symbol (LPS)
253 * is larger than the interval size for the MPS, then exchange
254 * the two symbols for coding efficiency: */
258 *st = (sv & 0x80) ^ nm; /* Estimate_after_MPS */
261 /* Renormalization & data output per section D.1.6 */
266 /* Another byte is ready for output */
269 /* Handle overflow over all stacked 0xFF bytes */
270 if (e->buffer >= 0) {
272 do emit_byte(0x00, cinfo);
274 emit_byte(e->buffer + 1, cinfo);
275 if (e->buffer + 1 == 0xFF)
276 emit_byte(0x00, cinfo);
278 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
280 /* Note: The 3 spacer bits in the C register guarantee
281 * that the new buffer byte can't be 0xFF here
282 * (see page 160 in the P&M JPEG book). */
283 e->buffer = temp & 0xFF; /* new output byte, might overflow later */
284 } else if (temp == 0xFF) {
285 ++e->sc; /* stack 0xFF byte (which might overflow later) */
287 /* Output all stacked 0xFF bytes, they will not overflow any more */
290 else if (e->buffer >= 0) {
292 do emit_byte(0x00, cinfo);
294 emit_byte(e->buffer, cinfo);
298 do emit_byte(0x00, cinfo);
301 emit_byte(0xFF, cinfo);
302 emit_byte(0x00, cinfo);
305 e->buffer = temp & 0xFF; /* new output byte (can still overflow) */
310 } while (e->a < 0x8000L);
315 * Emit a restart marker & resynchronize predictions.
319 emit_restart (j_compress_ptr cinfo, int restart_num)
321 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
323 jpeg_component_info * compptr;
327 emit_byte(0xFF, cinfo);
328 emit_byte(JPEG_RST0 + restart_num, cinfo);
330 /* Re-initialize statistics areas */
331 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
332 compptr = cinfo->cur_comp_info[ci];
333 /* DC needs no table for refinement scan */
334 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
335 MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
336 /* Reset DC predictions to 0 */
337 entropy->last_dc_val[ci] = 0;
338 entropy->dc_context[ci] = 0;
340 /* AC needs no table when not present */
342 MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
346 /* Reset arithmetic encoding variables */
348 entropy->a = 0x10000L;
352 entropy->buffer = -1; /* empty */
357 * MCU encoding for DC initial scan (either spectral selection,
358 * or first pass of successive approximation).
362 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
364 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
370 /* Emit restart marker if needed */
371 if (cinfo->restart_interval) {
372 if (entropy->restarts_to_go == 0) {
373 emit_restart(cinfo, entropy->next_restart_num);
374 entropy->restarts_to_go = cinfo->restart_interval;
375 entropy->next_restart_num++;
376 entropy->next_restart_num &= 7;
378 entropy->restarts_to_go--;
381 /* Encode the MCU data blocks */
382 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
383 ci = cinfo->MCU_membership[blkn];
384 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
386 /* Compute the DC value after the required point transform by Al.
387 * This is simply an arithmetic right shift.
389 m = IRIGHT_SHIFT((int) (MCU_data[blkn][0][0]), cinfo->Al);
391 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
393 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
394 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
396 /* Figure F.4: Encode_DC_DIFF */
397 if ((v = m - entropy->last_dc_val[ci]) == 0) {
398 arith_encode(cinfo, st, 0);
399 entropy->dc_context[ci] = 0; /* zero diff category */
401 entropy->last_dc_val[ci] = m;
402 arith_encode(cinfo, st, 1);
403 /* Figure F.6: Encoding nonzero value v */
404 /* Figure F.7: Encoding the sign of v */
406 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
407 st += 2; /* Table F.4: SP = S0 + 2 */
408 entropy->dc_context[ci] = 4; /* small positive diff category */
411 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
412 st += 3; /* Table F.4: SN = S0 + 3 */
413 entropy->dc_context[ci] = 8; /* small negative diff category */
415 /* Figure F.8: Encoding the magnitude category of v */
418 arith_encode(cinfo, st, 1);
421 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
423 arith_encode(cinfo, st, 1);
428 arith_encode(cinfo, st, 0);
429 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
430 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
431 entropy->dc_context[ci] = 0; /* zero diff category */
432 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
433 entropy->dc_context[ci] += 8; /* large diff category */
434 /* Figure F.9: Encoding the magnitude bit pattern of v */
437 arith_encode(cinfo, st, (m & v) ? 1 : 0);
446 * MCU encoding for AC initial scan (either spectral selection,
447 * or first pass of successive approximation).
451 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
453 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
454 const int * natural_order;
460 /* Emit restart marker if needed */
461 if (cinfo->restart_interval) {
462 if (entropy->restarts_to_go == 0) {
463 emit_restart(cinfo, entropy->next_restart_num);
464 entropy->restarts_to_go = cinfo->restart_interval;
465 entropy->next_restart_num++;
466 entropy->next_restart_num &= 7;
468 entropy->restarts_to_go--;
471 natural_order = cinfo->natural_order;
473 /* Encode the MCU data block */
475 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
477 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
479 /* Establish EOB (end-of-block) index */
482 /* We must apply the point transform by Al. For AC coefficients this
483 * is an integer division with rounding towards 0. To do this portably
484 * in C, we shift after obtaining the absolute value.
486 if ((v = (*block)[natural_order[ke]]) >= 0) {
487 if (v >>= cinfo->Al) break;
490 if (v >>= cinfo->Al) break;
494 /* Figure F.5: Encode_AC_Coefficients */
495 for (k = cinfo->Ss - 1; k < ke;) {
496 st = entropy->ac_stats[tbl] + 3 * k;
497 arith_encode(cinfo, st, 0); /* EOB decision */
499 if ((v = (*block)[natural_order[++k]]) >= 0) {
500 if (v >>= cinfo->Al) {
501 arith_encode(cinfo, st + 1, 1);
502 arith_encode(cinfo, entropy->fixed_bin, 0);
507 if (v >>= cinfo->Al) {
508 arith_encode(cinfo, st + 1, 1);
509 arith_encode(cinfo, entropy->fixed_bin, 1);
513 arith_encode(cinfo, st + 1, 0);
517 /* Figure F.8: Encoding the magnitude category of v */
520 arith_encode(cinfo, st, 1);
524 arith_encode(cinfo, st, 1);
526 st = entropy->ac_stats[tbl] +
527 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
529 arith_encode(cinfo, st, 1);
535 arith_encode(cinfo, st, 0);
536 /* Figure F.9: Encoding the magnitude bit pattern of v */
539 arith_encode(cinfo, st, (m & v) ? 1 : 0);
541 /* Encode EOB decision only if k < cinfo->Se */
543 st = entropy->ac_stats[tbl] + 3 * k;
544 arith_encode(cinfo, st, 1);
552 * MCU encoding for DC successive approximation refinement scan.
553 * Note: we assume such scans can be multi-component,
554 * although the spec is not very clear on the point.
558 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
560 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
564 /* Emit restart marker if needed */
565 if (cinfo->restart_interval) {
566 if (entropy->restarts_to_go == 0) {
567 emit_restart(cinfo, entropy->next_restart_num);
568 entropy->restarts_to_go = cinfo->restart_interval;
569 entropy->next_restart_num++;
570 entropy->next_restart_num &= 7;
572 entropy->restarts_to_go--;
575 st = entropy->fixed_bin; /* use fixed probability estimation */
578 /* Encode the MCU data blocks */
579 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
580 /* We simply emit the Al'th bit of the DC coefficient value. */
581 arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
589 * MCU encoding for AC successive approximation refinement scan.
593 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
595 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
596 const int * natural_order;
602 /* Emit restart marker if needed */
603 if (cinfo->restart_interval) {
604 if (entropy->restarts_to_go == 0) {
605 emit_restart(cinfo, entropy->next_restart_num);
606 entropy->restarts_to_go = cinfo->restart_interval;
607 entropy->next_restart_num++;
608 entropy->next_restart_num &= 7;
610 entropy->restarts_to_go--;
613 natural_order = cinfo->natural_order;
615 /* Encode the MCU data block */
617 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
619 /* Section G.1.3.3: Encoding of AC coefficients */
621 /* Establish EOB (end-of-block) index */
624 /* We must apply the point transform by Al. For AC coefficients this
625 * is an integer division with rounding towards 0. To do this portably
626 * in C, we shift after obtaining the absolute value.
628 if ((v = (*block)[natural_order[ke]]) >= 0) {
629 if (v >>= cinfo->Al) break;
632 if (v >>= cinfo->Al) break;
636 /* Establish EOBx (previous stage end-of-block) index */
637 for (kex = ke; kex > 0; kex--)
638 if ((v = (*block)[natural_order[kex]]) >= 0) {
639 if (v >>= cinfo->Ah) break;
642 if (v >>= cinfo->Ah) break;
645 /* Figure G.10: Encode_AC_Coefficients_SA */
646 for (k = cinfo->Ss - 1; k < ke;) {
647 st = entropy->ac_stats[tbl] + 3 * k;
649 arith_encode(cinfo, st, 0); /* EOB decision */
651 if ((v = (*block)[natural_order[++k]]) >= 0) {
652 if (v >>= cinfo->Al) {
653 if (v >> 1) /* previously nonzero coef */
654 arith_encode(cinfo, st + 2, (v & 1));
655 else { /* newly nonzero coef */
656 arith_encode(cinfo, st + 1, 1);
657 arith_encode(cinfo, entropy->fixed_bin, 0);
663 if (v >>= cinfo->Al) {
664 if (v >> 1) /* previously nonzero coef */
665 arith_encode(cinfo, st + 2, (v & 1));
666 else { /* newly nonzero coef */
667 arith_encode(cinfo, st + 1, 1);
668 arith_encode(cinfo, entropy->fixed_bin, 1);
673 arith_encode(cinfo, st + 1, 0);
677 /* Encode EOB decision only if k < cinfo->Se */
679 st = entropy->ac_stats[tbl] + 3 * k;
680 arith_encode(cinfo, st, 1);
688 * Encode and output one MCU's worth of arithmetic-compressed coefficients.
692 encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
694 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
695 const int * natural_order;
701 jpeg_component_info * compptr;
703 /* Emit restart marker if needed */
704 if (cinfo->restart_interval) {
705 if (entropy->restarts_to_go == 0) {
706 emit_restart(cinfo, entropy->next_restart_num);
707 entropy->restarts_to_go = cinfo->restart_interval;
708 entropy->next_restart_num++;
709 entropy->next_restart_num &= 7;
711 entropy->restarts_to_go--;
714 natural_order = cinfo->natural_order;
716 /* Encode the MCU data blocks */
717 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
718 block = MCU_data[blkn];
719 ci = cinfo->MCU_membership[blkn];
720 compptr = cinfo->cur_comp_info[ci];
722 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
724 tbl = compptr->dc_tbl_no;
726 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
727 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
729 /* Figure F.4: Encode_DC_DIFF */
730 if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
731 arith_encode(cinfo, st, 0);
732 entropy->dc_context[ci] = 0; /* zero diff category */
734 entropy->last_dc_val[ci] = (*block)[0];
735 arith_encode(cinfo, st, 1);
736 /* Figure F.6: Encoding nonzero value v */
737 /* Figure F.7: Encoding the sign of v */
739 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
740 st += 2; /* Table F.4: SP = S0 + 2 */
741 entropy->dc_context[ci] = 4; /* small positive diff category */
744 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
745 st += 3; /* Table F.4: SN = S0 + 3 */
746 entropy->dc_context[ci] = 8; /* small negative diff category */
748 /* Figure F.8: Encoding the magnitude category of v */
751 arith_encode(cinfo, st, 1);
754 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
756 arith_encode(cinfo, st, 1);
761 arith_encode(cinfo, st, 0);
762 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
763 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
764 entropy->dc_context[ci] = 0; /* zero diff category */
765 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
766 entropy->dc_context[ci] += 8; /* large diff category */
767 /* Figure F.9: Encoding the magnitude bit pattern of v */
770 arith_encode(cinfo, st, (m & v) ? 1 : 0);
773 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
775 if ((ke = cinfo->lim_Se) == 0) continue;
776 tbl = compptr->ac_tbl_no;
778 /* Establish EOB (end-of-block) index */
780 if ((*block)[natural_order[ke]]) break;
783 /* Figure F.5: Encode_AC_Coefficients */
784 for (k = 0; k < ke;) {
785 st = entropy->ac_stats[tbl] + 3 * k;
786 arith_encode(cinfo, st, 0); /* EOB decision */
787 while ((v = (*block)[natural_order[++k]]) == 0) {
788 arith_encode(cinfo, st + 1, 0);
791 arith_encode(cinfo, st + 1, 1);
792 /* Figure F.6: Encoding nonzero value v */
793 /* Figure F.7: Encoding the sign of v */
795 arith_encode(cinfo, entropy->fixed_bin, 0);
798 arith_encode(cinfo, entropy->fixed_bin, 1);
801 /* Figure F.8: Encoding the magnitude category of v */
804 arith_encode(cinfo, st, 1);
808 arith_encode(cinfo, st, 1);
810 st = entropy->ac_stats[tbl] +
811 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
813 arith_encode(cinfo, st, 1);
819 arith_encode(cinfo, st, 0);
820 /* Figure F.9: Encoding the magnitude bit pattern of v */
823 arith_encode(cinfo, st, (m & v) ? 1 : 0);
825 /* Encode EOB decision only if k < cinfo->lim_Se */
826 if (k < cinfo->lim_Se) {
827 st = entropy->ac_stats[tbl] + 3 * k;
828 arith_encode(cinfo, st, 1);
837 * Initialize for an arithmetic-compressed scan.
841 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
843 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
845 jpeg_component_info * compptr;
847 if (gather_statistics)
848 /* Make sure to avoid that in the master control logic!
849 * We are fully adaptive here and need no extra
850 * statistics gathering pass!
852 ERREXIT(cinfo, JERR_NOT_COMPILED);
854 /* We assume jcmaster.c already validated the progressive scan parameters. */
856 /* Select execution routines */
857 if (cinfo->progressive_mode) {
858 if (cinfo->Ah == 0) {
860 entropy->pub.encode_mcu = encode_mcu_DC_first;
862 entropy->pub.encode_mcu = encode_mcu_AC_first;
865 entropy->pub.encode_mcu = encode_mcu_DC_refine;
867 entropy->pub.encode_mcu = encode_mcu_AC_refine;
870 entropy->pub.encode_mcu = encode_mcu;
872 /* Allocate & initialize requested statistics areas */
873 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
874 compptr = cinfo->cur_comp_info[ci];
875 /* DC needs no table for refinement scan */
876 if (cinfo->Ss == 0 && cinfo->Ah == 0) {
877 tbl = compptr->dc_tbl_no;
878 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
879 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
880 if (entropy->dc_stats[tbl] == NULL)
881 entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
882 ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
883 MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
884 /* Initialize DC predictions to 0 */
885 entropy->last_dc_val[ci] = 0;
886 entropy->dc_context[ci] = 0;
888 /* AC needs no table when not present */
890 tbl = compptr->ac_tbl_no;
891 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
892 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
893 if (entropy->ac_stats[tbl] == NULL)
894 entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
895 ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
896 MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
897 #ifdef CALCULATE_SPECTRAL_CONDITIONING
898 if (cinfo->progressive_mode)
899 /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
900 cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
905 /* Initialize arithmetic encoding variables */
907 entropy->a = 0x10000L;
911 entropy->buffer = -1; /* empty */
913 /* Initialize restart stuff */
914 entropy->restarts_to_go = cinfo->restart_interval;
915 entropy->next_restart_num = 0;
920 * Module initialization routine for arithmetic entropy encoding.
924 jinit_arith_encoder (j_compress_ptr cinfo)
926 arith_entropy_ptr entropy;
929 entropy = (arith_entropy_ptr)
930 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
931 SIZEOF(arith_entropy_encoder));
932 cinfo->entropy = &entropy->pub;
933 entropy->pub.start_pass = start_pass;
934 entropy->pub.finish_pass = finish_pass;
936 /* Mark tables unallocated */
937 for (i = 0; i < NUM_ARITH_TBLS; i++) {
938 entropy->dc_stats[i] = NULL;
939 entropy->ac_stats[i] = NULL;
942 /* Initialize index for fixed probability estimation */
943 entropy->fixed_bin[0] = 113;