4 * Developed 1997-2020 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((int) ((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((int) ((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 /* New output byte, might overflow later */
284 e
->buffer
= (int) (temp
& 0xFF);
285 } else if (temp
== 0xFF) {
286 ++e
->sc
; /* stack 0xFF byte (which might overflow later) */
288 /* Output all stacked 0xFF bytes, they will not overflow any more */
291 else if (e
->buffer
>= 0) {
293 do emit_byte(0x00, cinfo
);
295 emit_byte(e
->buffer
, cinfo
);
299 do emit_byte(0x00, cinfo
);
302 emit_byte(0xFF, cinfo
);
303 emit_byte(0x00, cinfo
);
306 /* New output byte (can still overflow) */
307 e
->buffer
= (int) (temp
& 0xFF);
312 } while (e
->a
< 0x8000L
);
317 * Emit a restart marker & resynchronize predictions.
321 emit_restart (j_compress_ptr cinfo
, int restart_num
)
323 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
325 jpeg_component_info
* compptr
;
329 emit_byte(0xFF, cinfo
);
330 emit_byte(JPEG_RST0
+ restart_num
, cinfo
);
332 /* Re-initialize statistics areas */
333 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
334 compptr
= cinfo
->cur_comp_info
[ci
];
335 /* DC needs no table for refinement scan */
336 if (cinfo
->Ss
== 0 && cinfo
->Ah
== 0) {
337 MEMZERO(entropy
->dc_stats
[compptr
->dc_tbl_no
], DC_STAT_BINS
);
338 /* Reset DC predictions to 0 */
339 entropy
->last_dc_val
[ci
] = 0;
340 entropy
->dc_context
[ci
] = 0;
342 /* AC needs no table when not present */
344 MEMZERO(entropy
->ac_stats
[compptr
->ac_tbl_no
], AC_STAT_BINS
);
348 /* Reset arithmetic encoding variables */
350 entropy
->a
= 0x10000L
;
354 entropy
->buffer
= -1; /* empty */
359 * MCU encoding for DC initial scan (either spectral selection,
360 * or first pass of successive approximation).
364 encode_mcu_DC_first (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
366 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
372 /* Emit restart marker if needed */
373 if (cinfo
->restart_interval
) {
374 if (entropy
->restarts_to_go
== 0) {
375 emit_restart(cinfo
, entropy
->next_restart_num
);
376 entropy
->restarts_to_go
= cinfo
->restart_interval
;
377 entropy
->next_restart_num
++;
378 entropy
->next_restart_num
&= 7;
380 entropy
->restarts_to_go
--;
383 /* Encode the MCU data blocks */
384 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
385 ci
= cinfo
->MCU_membership
[blkn
];
386 tbl
= cinfo
->cur_comp_info
[ci
]->dc_tbl_no
;
388 /* Compute the DC value after the required point transform by Al.
389 * This is simply an arithmetic right shift.
391 m
= IRIGHT_SHIFT((int) (MCU_data
[blkn
][0][0]), cinfo
->Al
);
393 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
395 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
396 st
= entropy
->dc_stats
[tbl
] + entropy
->dc_context
[ci
];
398 /* Figure F.4: Encode_DC_DIFF */
399 if ((v
= m
- entropy
->last_dc_val
[ci
]) == 0) {
400 arith_encode(cinfo
, st
, 0);
401 entropy
->dc_context
[ci
] = 0; /* zero diff category */
403 entropy
->last_dc_val
[ci
] = m
;
404 arith_encode(cinfo
, st
, 1);
405 /* Figure F.6: Encoding nonzero value v */
406 /* Figure F.7: Encoding the sign of v */
408 arith_encode(cinfo
, st
+ 1, 0); /* Table F.4: SS = S0 + 1 */
409 st
+= 2; /* Table F.4: SP = S0 + 2 */
410 entropy
->dc_context
[ci
] = 4; /* small positive diff category */
413 arith_encode(cinfo
, st
+ 1, 1); /* Table F.4: SS = S0 + 1 */
414 st
+= 3; /* Table F.4: SN = S0 + 3 */
415 entropy
->dc_context
[ci
] = 8; /* small negative diff category */
417 /* Figure F.8: Encoding the magnitude category of v */
420 arith_encode(cinfo
, st
, 1);
423 st
= entropy
->dc_stats
[tbl
] + 20; /* Table F.4: X1 = 20 */
425 arith_encode(cinfo
, st
, 1);
430 arith_encode(cinfo
, st
, 0);
431 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
432 if (m
< (int) ((1L << cinfo
->arith_dc_L
[tbl
]) >> 1))
433 entropy
->dc_context
[ci
] = 0; /* zero diff category */
434 else if (m
> (int) ((1L << cinfo
->arith_dc_U
[tbl
]) >> 1))
435 entropy
->dc_context
[ci
] += 8; /* large diff category */
436 /* Figure F.9: Encoding the magnitude bit pattern of v */
439 arith_encode(cinfo
, st
, (m
& v
) ? 1 : 0);
448 * MCU encoding for AC initial scan (either spectral selection,
449 * or first pass of successive approximation).
453 encode_mcu_AC_first (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
455 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
456 const int * natural_order
;
462 /* Emit restart marker if needed */
463 if (cinfo
->restart_interval
) {
464 if (entropy
->restarts_to_go
== 0) {
465 emit_restart(cinfo
, entropy
->next_restart_num
);
466 entropy
->restarts_to_go
= cinfo
->restart_interval
;
467 entropy
->next_restart_num
++;
468 entropy
->next_restart_num
&= 7;
470 entropy
->restarts_to_go
--;
473 natural_order
= cinfo
->natural_order
;
475 /* Encode the MCU data block */
477 tbl
= cinfo
->cur_comp_info
[0]->ac_tbl_no
;
479 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
481 /* Establish EOB (end-of-block) index */
484 /* We must apply the point transform by Al. For AC coefficients this
485 * is an integer division with rounding towards 0. To do this portably
486 * in C, we shift after obtaining the absolute value.
488 if ((v
= (*block
)[natural_order
[ke
]]) >= 0) {
489 if (v
>>= cinfo
->Al
) break;
492 if (v
>>= cinfo
->Al
) break;
496 /* Figure F.5: Encode_AC_Coefficients */
497 for (k
= cinfo
->Ss
- 1; k
< ke
;) {
498 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
499 arith_encode(cinfo
, st
, 0); /* EOB decision */
501 if ((v
= (*block
)[natural_order
[++k
]]) >= 0) {
502 if (v
>>= cinfo
->Al
) {
503 arith_encode(cinfo
, st
+ 1, 1);
504 arith_encode(cinfo
, entropy
->fixed_bin
, 0);
509 if (v
>>= cinfo
->Al
) {
510 arith_encode(cinfo
, st
+ 1, 1);
511 arith_encode(cinfo
, entropy
->fixed_bin
, 1);
515 arith_encode(cinfo
, st
+ 1, 0);
519 /* Figure F.8: Encoding the magnitude category of v */
522 arith_encode(cinfo
, st
, 1);
526 arith_encode(cinfo
, st
, 1);
528 st
= entropy
->ac_stats
[tbl
] +
529 (k
<= cinfo
->arith_ac_K
[tbl
] ? 189 : 217);
531 arith_encode(cinfo
, st
, 1);
537 arith_encode(cinfo
, st
, 0);
538 /* Figure F.9: Encoding the magnitude bit pattern of v */
541 arith_encode(cinfo
, st
, (m
& v
) ? 1 : 0);
543 /* Encode EOB decision only if k < cinfo->Se */
545 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
546 arith_encode(cinfo
, st
, 1);
554 * MCU encoding for DC successive approximation refinement scan.
555 * Note: we assume such scans can be multi-component,
556 * although the spec is not very clear on the point.
560 encode_mcu_DC_refine (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
562 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
566 /* Emit restart marker if needed */
567 if (cinfo
->restart_interval
) {
568 if (entropy
->restarts_to_go
== 0) {
569 emit_restart(cinfo
, entropy
->next_restart_num
);
570 entropy
->restarts_to_go
= cinfo
->restart_interval
;
571 entropy
->next_restart_num
++;
572 entropy
->next_restart_num
&= 7;
574 entropy
->restarts_to_go
--;
577 st
= entropy
->fixed_bin
; /* use fixed probability estimation */
580 /* Encode the MCU data blocks */
581 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
582 /* We simply emit the Al'th bit of the DC coefficient value. */
583 arith_encode(cinfo
, st
, (MCU_data
[blkn
][0][0] >> Al
) & 1);
591 * MCU encoding for AC successive approximation refinement scan.
595 encode_mcu_AC_refine (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
597 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
598 const int * natural_order
;
604 /* Emit restart marker if needed */
605 if (cinfo
->restart_interval
) {
606 if (entropy
->restarts_to_go
== 0) {
607 emit_restart(cinfo
, entropy
->next_restart_num
);
608 entropy
->restarts_to_go
= cinfo
->restart_interval
;
609 entropy
->next_restart_num
++;
610 entropy
->next_restart_num
&= 7;
612 entropy
->restarts_to_go
--;
615 natural_order
= cinfo
->natural_order
;
617 /* Encode the MCU data block */
619 tbl
= cinfo
->cur_comp_info
[0]->ac_tbl_no
;
621 /* Section G.1.3.3: Encoding of AC coefficients */
623 /* Establish EOB (end-of-block) index */
626 /* We must apply the point transform by Al. For AC coefficients this
627 * is an integer division with rounding towards 0. To do this portably
628 * in C, we shift after obtaining the absolute value.
630 if ((v
= (*block
)[natural_order
[ke
]]) >= 0) {
631 if (v
>>= cinfo
->Al
) break;
634 if (v
>>= cinfo
->Al
) break;
638 /* Establish EOBx (previous stage end-of-block) index */
639 for (kex
= ke
; kex
> 0; kex
--)
640 if ((v
= (*block
)[natural_order
[kex
]]) >= 0) {
641 if (v
>>= cinfo
->Ah
) break;
644 if (v
>>= cinfo
->Ah
) break;
647 /* Figure G.10: Encode_AC_Coefficients_SA */
648 for (k
= cinfo
->Ss
- 1; k
< ke
;) {
649 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
651 arith_encode(cinfo
, st
, 0); /* EOB decision */
653 if ((v
= (*block
)[natural_order
[++k
]]) >= 0) {
654 if (v
>>= cinfo
->Al
) {
655 if (v
>> 1) /* previously nonzero coef */
656 arith_encode(cinfo
, st
+ 2, (v
& 1));
657 else { /* newly nonzero coef */
658 arith_encode(cinfo
, st
+ 1, 1);
659 arith_encode(cinfo
, entropy
->fixed_bin
, 0);
665 if (v
>>= cinfo
->Al
) {
666 if (v
>> 1) /* previously nonzero coef */
667 arith_encode(cinfo
, st
+ 2, (v
& 1));
668 else { /* newly nonzero coef */
669 arith_encode(cinfo
, st
+ 1, 1);
670 arith_encode(cinfo
, entropy
->fixed_bin
, 1);
675 arith_encode(cinfo
, st
+ 1, 0);
679 /* Encode EOB decision only if k < cinfo->Se */
681 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
682 arith_encode(cinfo
, st
, 1);
690 * Encode and output one MCU's worth of arithmetic-compressed coefficients.
694 encode_mcu (j_compress_ptr cinfo
, JBLOCKARRAY MCU_data
)
696 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
697 const int * natural_order
;
703 jpeg_component_info
* compptr
;
705 /* Emit restart marker if needed */
706 if (cinfo
->restart_interval
) {
707 if (entropy
->restarts_to_go
== 0) {
708 emit_restart(cinfo
, entropy
->next_restart_num
);
709 entropy
->restarts_to_go
= cinfo
->restart_interval
;
710 entropy
->next_restart_num
++;
711 entropy
->next_restart_num
&= 7;
713 entropy
->restarts_to_go
--;
716 natural_order
= cinfo
->natural_order
;
718 /* Encode the MCU data blocks */
719 for (blkn
= 0; blkn
< cinfo
->blocks_in_MCU
; blkn
++) {
720 block
= MCU_data
[blkn
];
721 ci
= cinfo
->MCU_membership
[blkn
];
722 compptr
= cinfo
->cur_comp_info
[ci
];
724 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
726 tbl
= compptr
->dc_tbl_no
;
728 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
729 st
= entropy
->dc_stats
[tbl
] + entropy
->dc_context
[ci
];
731 /* Figure F.4: Encode_DC_DIFF */
732 if ((v
= (*block
)[0] - entropy
->last_dc_val
[ci
]) == 0) {
733 arith_encode(cinfo
, st
, 0);
734 entropy
->dc_context
[ci
] = 0; /* zero diff category */
736 entropy
->last_dc_val
[ci
] = (*block
)[0];
737 arith_encode(cinfo
, st
, 1);
738 /* Figure F.6: Encoding nonzero value v */
739 /* Figure F.7: Encoding the sign of v */
741 arith_encode(cinfo
, st
+ 1, 0); /* Table F.4: SS = S0 + 1 */
742 st
+= 2; /* Table F.4: SP = S0 + 2 */
743 entropy
->dc_context
[ci
] = 4; /* small positive diff category */
746 arith_encode(cinfo
, st
+ 1, 1); /* Table F.4: SS = S0 + 1 */
747 st
+= 3; /* Table F.4: SN = S0 + 3 */
748 entropy
->dc_context
[ci
] = 8; /* small negative diff category */
750 /* Figure F.8: Encoding the magnitude category of v */
753 arith_encode(cinfo
, st
, 1);
756 st
= entropy
->dc_stats
[tbl
] + 20; /* Table F.4: X1 = 20 */
758 arith_encode(cinfo
, st
, 1);
763 arith_encode(cinfo
, st
, 0);
764 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
765 if (m
< (int) ((1L << cinfo
->arith_dc_L
[tbl
]) >> 1))
766 entropy
->dc_context
[ci
] = 0; /* zero diff category */
767 else if (m
> (int) ((1L << cinfo
->arith_dc_U
[tbl
]) >> 1))
768 entropy
->dc_context
[ci
] += 8; /* large diff category */
769 /* Figure F.9: Encoding the magnitude bit pattern of v */
772 arith_encode(cinfo
, st
, (m
& v
) ? 1 : 0);
775 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
777 if ((ke
= cinfo
->lim_Se
) == 0) continue;
778 tbl
= compptr
->ac_tbl_no
;
780 /* Establish EOB (end-of-block) index */
782 if ((*block
)[natural_order
[ke
]]) break;
785 /* Figure F.5: Encode_AC_Coefficients */
786 for (k
= 0; k
< ke
;) {
787 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
788 arith_encode(cinfo
, st
, 0); /* EOB decision */
789 while ((v
= (*block
)[natural_order
[++k
]]) == 0) {
790 arith_encode(cinfo
, st
+ 1, 0);
793 arith_encode(cinfo
, st
+ 1, 1);
794 /* Figure F.6: Encoding nonzero value v */
795 /* Figure F.7: Encoding the sign of v */
797 arith_encode(cinfo
, entropy
->fixed_bin
, 0);
800 arith_encode(cinfo
, entropy
->fixed_bin
, 1);
803 /* Figure F.8: Encoding the magnitude category of v */
806 arith_encode(cinfo
, st
, 1);
810 arith_encode(cinfo
, st
, 1);
812 st
= entropy
->ac_stats
[tbl
] +
813 (k
<= cinfo
->arith_ac_K
[tbl
] ? 189 : 217);
815 arith_encode(cinfo
, st
, 1);
821 arith_encode(cinfo
, st
, 0);
822 /* Figure F.9: Encoding the magnitude bit pattern of v */
825 arith_encode(cinfo
, st
, (m
& v
) ? 1 : 0);
827 /* Encode EOB decision only if k < cinfo->lim_Se */
828 if (k
< cinfo
->lim_Se
) {
829 st
= entropy
->ac_stats
[tbl
] + 3 * k
;
830 arith_encode(cinfo
, st
, 1);
839 * Initialize for an arithmetic-compressed scan.
843 start_pass (j_compress_ptr cinfo
, boolean gather_statistics
)
845 arith_entropy_ptr entropy
= (arith_entropy_ptr
) cinfo
->entropy
;
847 jpeg_component_info
* compptr
;
849 if (gather_statistics
)
850 /* Make sure to avoid that in the master control logic!
851 * We are fully adaptive here and need no extra
852 * statistics gathering pass!
854 ERREXIT(cinfo
, JERR_NOT_COMPILED
);
856 /* We assume jcmaster.c already validated the progressive scan parameters. */
858 /* Select execution routines */
859 if (cinfo
->progressive_mode
) {
860 if (cinfo
->Ah
== 0) {
862 entropy
->pub
.encode_mcu
= encode_mcu_DC_first
;
864 entropy
->pub
.encode_mcu
= encode_mcu_AC_first
;
867 entropy
->pub
.encode_mcu
= encode_mcu_DC_refine
;
869 entropy
->pub
.encode_mcu
= encode_mcu_AC_refine
;
872 entropy
->pub
.encode_mcu
= encode_mcu
;
874 /* Allocate & initialize requested statistics areas */
875 for (ci
= 0; ci
< cinfo
->comps_in_scan
; ci
++) {
876 compptr
= cinfo
->cur_comp_info
[ci
];
877 /* DC needs no table for refinement scan */
878 if (cinfo
->Ss
== 0 && cinfo
->Ah
== 0) {
879 tbl
= compptr
->dc_tbl_no
;
880 if (tbl
< 0 || tbl
>= NUM_ARITH_TBLS
)
881 ERREXIT1(cinfo
, JERR_NO_ARITH_TABLE
, tbl
);
882 if (entropy
->dc_stats
[tbl
] == NULL
)
883 entropy
->dc_stats
[tbl
] = (unsigned char *) (*cinfo
->mem
->alloc_small
)
884 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, DC_STAT_BINS
);
885 MEMZERO(entropy
->dc_stats
[tbl
], DC_STAT_BINS
);
886 /* Initialize DC predictions to 0 */
887 entropy
->last_dc_val
[ci
] = 0;
888 entropy
->dc_context
[ci
] = 0;
890 /* AC needs no table when not present */
892 tbl
= compptr
->ac_tbl_no
;
893 if (tbl
< 0 || tbl
>= NUM_ARITH_TBLS
)
894 ERREXIT1(cinfo
, JERR_NO_ARITH_TABLE
, tbl
);
895 if (entropy
->ac_stats
[tbl
] == NULL
)
896 entropy
->ac_stats
[tbl
] = (unsigned char *) (*cinfo
->mem
->alloc_small
)
897 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, AC_STAT_BINS
);
898 MEMZERO(entropy
->ac_stats
[tbl
], AC_STAT_BINS
);
899 #ifdef CALCULATE_SPECTRAL_CONDITIONING
900 if (cinfo
->progressive_mode
)
901 /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
902 cinfo
->arith_ac_K
[tbl
] = cinfo
->Ss
+ ((8 + cinfo
->Se
- cinfo
->Ss
) >> 4);
907 /* Initialize arithmetic encoding variables */
909 entropy
->a
= 0x10000L
;
913 entropy
->buffer
= -1; /* empty */
915 /* Initialize restart stuff */
916 entropy
->restarts_to_go
= cinfo
->restart_interval
;
917 entropy
->next_restart_num
= 0;
922 * Module initialization routine for arithmetic entropy encoding.
926 jinit_arith_encoder (j_compress_ptr cinfo
)
928 arith_entropy_ptr entropy
;
931 entropy
= (arith_entropy_ptr
) (*cinfo
->mem
->alloc_small
)
932 ((j_common_ptr
) cinfo
, JPOOL_IMAGE
, SIZEOF(arith_entropy_encoder
));
933 cinfo
->entropy
= &entropy
->pub
;
934 entropy
->pub
.start_pass
= start_pass
;
935 entropy
->pub
.finish_pass
= finish_pass
;
937 /* Mark tables unallocated */
938 for (i
= 0; i
< NUM_ARITH_TBLS
; i
++) {
939 entropy
->dc_stats
[i
] = NULL
;
940 entropy
->ac_stats
[i
] = NULL
;
943 /* Initialize index for fixed probability estimation */
944 entropy
->fixed_bin
[0] = 113;