1 /*
2 * jcarith.c
3 *
4 * This file was part of the Independent JPEG Group's software:
5 * Developed 1997-2009 by Guido Vollbeding.
6 * libjpeg-turbo Modifications:
7 * Copyright (C) 2015, 2018, D. R. Commander.
8 * For conditions of distribution and use, see the accompanying README.ijg
9 * file.
10 *
11 * This file contains portable arithmetic entropy encoding routines for JPEG
12 * (implementing Recommendation ITU-T T.81 | ISO/IEC 10918-1).
13 *
14 * Both sequential and progressive modes are supported in this single module.
15 *
16 * Suspension is not currently supported in this module.
17 *
18 * NOTE: All referenced figures are from
19 * Recommendation ITU-T T.81 (1992) | ISO/IEC 10918-1:1994.
20 */
21
22 #define JPEG_INTERNALS
23 #include "jinclude.h"
24 #include "jpeglib.h"
25
26
27 /* Expanded entropy encoder object for arithmetic encoding. */
28
29 typedef struct {
30 struct jpeg_entropy_encoder pub; /* public fields */
31
32 JLONG c; /* C register, base of coding interval, layout as in sec. D.1.3 */
33 JLONG a; /* A register, normalized size of coding interval */
34 JLONG sc; /* counter for stacked 0xFF values which might overflow */
35 JLONG zc; /* counter for pending 0x00 output values which might *
36 * be discarded at the end ("Pacman" termination) */
37 int ct; /* bit shift counter, determines when next byte will be written */
38 int buffer; /* buffer for most recent output byte != 0xFF */
39
40 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
41 int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
42
43 unsigned int restarts_to_go; /* MCUs left in this restart interval */
44 int next_restart_num; /* next restart number to write (0-7) */
45
46 /* Pointers to statistics areas (these workspaces have image lifespan) */
47 unsigned char *dc_stats[NUM_ARITH_TBLS];
48 unsigned char *ac_stats[NUM_ARITH_TBLS];
49
50 /* Statistics bin for coding with fixed probability 0.5 */
51 unsigned char fixed_bin[4];
52 } arith_entropy_encoder;
53
54 typedef arith_entropy_encoder *arith_entropy_ptr;
55
56 /* The following two definitions specify the allocation chunk size
57 * for the statistics area.
58 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
59 * 49 statistics bins for DC, and 245 statistics bins for AC coding.
60 *
61 * We use a compact representation with 1 byte per statistics bin,
62 * thus the numbers directly represent byte sizes.
63 * This 1 byte per statistics bin contains the meaning of the MPS
64 * (more probable symbol) in the highest bit (mask 0x80), and the
65 * index into the probability estimation state machine table
66 * in the lower bits (mask 0x7F).
67 */
68
69 #define DC_STAT_BINS 64
70 #define AC_STAT_BINS 256
71
72 /* NOTE: Uncomment the following #define if you want to use the
73 * given formula for calculating the AC conditioning parameter Kx
74 * for spectral selection progressive coding in section G.1.3.2
75 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
76 * Although the spec and P&M authors claim that this "has proven
77 * to give good results for 8 bit precision samples", I'm not
78 * convinced yet that this is really beneficial.
79 * Early tests gave only very marginal compression enhancements
80 * (a few - around 5 or so - bytes even for very large files),
81 * which would turn out rather negative if we'd suppress the
82 * DAC (Define Arithmetic Conditioning) marker segments for
83 * the default parameters in the future.
84 * Note that currently the marker writing module emits 12-byte
85 * DAC segments for a full-component scan in a color image.
86 * This is not worth worrying about IMHO. However, since the
87 * spec defines the default values to be used if the tables
88 * are omitted (unlike Huffman tables, which are required
89 * anyway), one might optimize this behaviour in the future,
90 * and then it would be disadvantageous to use custom tables if
91 * they don't provide sufficient gain to exceed the DAC size.
92 *
93 * On the other hand, I'd consider it as a reasonable result
94 * that the conditioning has no significant influence on the
95 * compression performance. This means that the basic
96 * statistical model is already rather stable.
97 *
98 * Thus, at the moment, we use the default conditioning values
99 * anyway, and do not use the custom formula.
100 *
101 #define CALCULATE_SPECTRAL_CONDITIONING
102 */
103
104 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than JLONG.
105 * We assume that int right shift is unsigned if JLONG right shift is,
106 * which should be safe.
107 */
108
109 #ifdef RIGHT_SHIFT_IS_UNSIGNED
110 #define ISHIFT_TEMPS int ishift_temp;
111 #define IRIGHT_SHIFT(x, shft) \
112 ((ishift_temp = (x)) < 0 ? \
113 (ishift_temp >> (shft)) | ((~0) << (16 - (shft))) : \
114 (ishift_temp >> (shft)))
115 #else
116 #define ISHIFT_TEMPS
117 #define IRIGHT_SHIFT(x, shft) ((x) >> (shft))
118 #endif
119
120
121 LOCAL(void)
emit_byte(int val,j_compress_ptr cinfo)122 emit_byte(int val, j_compress_ptr cinfo)
123 /* Write next output byte; we do not support suspension in this module. */
124 {
125 struct jpeg_destination_mgr *dest = cinfo->dest;
126
127 *dest->next_output_byte++ = (JOCTET)val;
128 if (--dest->free_in_buffer == 0)
129 if (!(*dest->empty_output_buffer) (cinfo))
130 ERREXIT(cinfo, JERR_CANT_SUSPEND);
131 }
132
133
134 /*
135 * Finish up at the end of an arithmetic-compressed scan.
136 */
137
138 METHODDEF(void)
finish_pass(j_compress_ptr cinfo)139 finish_pass(j_compress_ptr cinfo)
140 {
141 arith_entropy_ptr e = (arith_entropy_ptr)cinfo->entropy;
142 JLONG temp;
143
144 /* Section D.1.8: Termination of encoding */
145
146 /* Find the e->c in the coding interval with the largest
147 * number of trailing zero bits */
148 if ((temp = (e->a - 1 + e->c) & 0xFFFF0000UL) < e->c)
149 e->c = temp + 0x8000L;
150 else
151 e->c = temp;
152 /* Send remaining bytes to output */
153 e->c <<= e->ct;
154 if (e->c & 0xF8000000UL) {
155 /* One final overflow has to be handled */
156 if (e->buffer >= 0) {
157 if (e->zc)
158 do emit_byte(0x00, cinfo);
159 while (--e->zc);
160 emit_byte(e->buffer + 1, cinfo);
161 if (e->buffer + 1 == 0xFF)
162 emit_byte(0x00, cinfo);
163 }
164 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
165 e->sc = 0;
166 } else {
167 if (e->buffer == 0)
168 ++e->zc;
169 else if (e->buffer >= 0) {
170 if (e->zc)
171 do emit_byte(0x00, cinfo);
172 while (--e->zc);
173 emit_byte(e->buffer, cinfo);
174 }
175 if (e->sc) {
176 if (e->zc)
177 do emit_byte(0x00, cinfo);
178 while (--e->zc);
179 do {
180 emit_byte(0xFF, cinfo);
181 emit_byte(0x00, cinfo);
182 } while (--e->sc);
183 }
184 }
185 /* Output final bytes only if they are not 0x00 */
186 if (e->c & 0x7FFF800L) {
187 if (e->zc) /* output final pending zero bytes */
188 do emit_byte(0x00, cinfo);
189 while (--e->zc);
190 emit_byte((e->c >> 19) & 0xFF, cinfo);
191 if (((e->c >> 19) & 0xFF) == 0xFF)
192 emit_byte(0x00, cinfo);
193 if (e->c & 0x7F800L) {
194 emit_byte((e->c >> 11) & 0xFF, cinfo);
195 if (((e->c >> 11) & 0xFF) == 0xFF)
196 emit_byte(0x00, cinfo);
197 }
198 }
199 }
200
201
202 /*
203 * The core arithmetic encoding routine (common in JPEG and JBIG).
204 * This needs to go as fast as possible.
205 * Machine-dependent optimization facilities
206 * are not utilized in this portable implementation.
207 * However, this code should be fairly efficient and
208 * may be a good base for further optimizations anyway.
209 *
210 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
211 *
212 * Note: I've added full "Pacman" termination support to the
213 * byte output routines, which is equivalent to the optional
214 * Discard_final_zeros procedure (Figure D.15) in the spec.
215 * Thus, we always produce the shortest possible output
216 * stream compliant to the spec (no trailing zero bytes,
217 * except for FF stuffing).
218 *
219 * I've also introduced a new scheme for accessing
220 * the probability estimation state machine table,
221 * derived from Markus Kuhn's JBIG implementation.
222 */
223
224 LOCAL(void)
arith_encode(j_compress_ptr cinfo,unsigned char * st,int val)225 arith_encode(j_compress_ptr cinfo, unsigned char *st, int val)
226 {
227 register arith_entropy_ptr e = (arith_entropy_ptr)cinfo->entropy;
228 register unsigned char nl, nm;
229 register JLONG qe, temp;
230 register int sv;
231
232 /* Fetch values from our compact representation of Table D.2:
233 * Qe values and probability estimation state machine
234 */
235 sv = *st;
236 qe = jpeg_aritab[sv & 0x7F]; /* => Qe_Value */
237 nl = qe & 0xFF; qe >>= 8; /* Next_Index_LPS + Switch_MPS */
238 nm = qe & 0xFF; qe >>= 8; /* Next_Index_MPS */
239
240 /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
241 e->a -= qe;
242 if (val != (sv >> 7)) {
243 /* Encode the less probable symbol */
244 if (e->a >= qe) {
245 /* If the interval size (qe) for the less probable symbol (LPS)
246 * is larger than the interval size for the MPS, then exchange
247 * the two symbols for coding efficiency, otherwise code the LPS
248 * as usual: */
249 e->c += e->a;
250 e->a = qe;
251 }
252 *st = (sv & 0x80) ^ nl; /* Estimate_after_LPS */
253 } else {
254 /* Encode the more probable symbol */
255 if (e->a >= 0x8000L)
256 return; /* A >= 0x8000 -> ready, no renormalization required */
257 if (e->a < qe) {
258 /* If the interval size (qe) for the less probable symbol (LPS)
259 * is larger than the interval size for the MPS, then exchange
260 * the two symbols for coding efficiency: */
261 e->c += e->a;
262 e->a = qe;
263 }
264 *st = (sv & 0x80) ^ nm; /* Estimate_after_MPS */
265 }
266
267 /* Renormalization & data output per section D.1.6 */
268 do {
269 e->a <<= 1;
270 e->c <<= 1;
271 if (--e->ct == 0) {
272 /* Another byte is ready for output */
273 temp = e->c >> 19;
274 if (temp > 0xFF) {
275 /* Handle overflow over all stacked 0xFF bytes */
276 if (e->buffer >= 0) {
277 if (e->zc)
278 do emit_byte(0x00, cinfo);
279 while (--e->zc);
280 emit_byte(e->buffer + 1, cinfo);
281 if (e->buffer + 1 == 0xFF)
282 emit_byte(0x00, cinfo);
283 }
284 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
285 e->sc = 0;
286 /* Note: The 3 spacer bits in the C register guarantee
287 * that the new buffer byte can't be 0xFF here
288 * (see page 160 in the P&M JPEG book). */
289 e->buffer = temp & 0xFF; /* new output byte, might overflow later */
290 } else if (temp == 0xFF) {
291 ++e->sc; /* stack 0xFF byte (which might overflow later) */
292 } else {
293 /* Output all stacked 0xFF bytes, they will not overflow any more */
294 if (e->buffer == 0)
295 ++e->zc;
296 else if (e->buffer >= 0) {
297 if (e->zc)
298 do emit_byte(0x00, cinfo);
299 while (--e->zc);
300 emit_byte(e->buffer, cinfo);
301 }
302 if (e->sc) {
303 if (e->zc)
304 do emit_byte(0x00, cinfo);
305 while (--e->zc);
306 do {
307 emit_byte(0xFF, cinfo);
308 emit_byte(0x00, cinfo);
309 } while (--e->sc);
310 }
311 e->buffer = temp & 0xFF; /* new output byte (can still overflow) */
312 }
313 e->c &= 0x7FFFFL;
314 e->ct += 8;
315 }
316 } while (e->a < 0x8000L);
317 }
318
319
320 /*
321 * Emit a restart marker & resynchronize predictions.
322 */
323
324 LOCAL(void)
emit_restart(j_compress_ptr cinfo,int restart_num)325 emit_restart(j_compress_ptr cinfo, int restart_num)
326 {
327 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
328 int ci;
329 jpeg_component_info *compptr;
330
331 finish_pass(cinfo);
332
333 emit_byte(0xFF, cinfo);
334 emit_byte(JPEG_RST0 + restart_num, cinfo);
335
336 /* Re-initialize statistics areas */
337 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
338 compptr = cinfo->cur_comp_info[ci];
339 /* DC needs no table for refinement scan */
340 if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
341 MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
342 /* Reset DC predictions to 0 */
343 entropy->last_dc_val[ci] = 0;
344 entropy->dc_context[ci] = 0;
345 }
346 /* AC needs no table when not present */
347 if (cinfo->progressive_mode == 0 || cinfo->Se) {
348 MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
349 }
350 }
351
352 /* Reset arithmetic encoding variables */
353 entropy->c = 0;
354 entropy->a = 0x10000L;
355 entropy->sc = 0;
356 entropy->zc = 0;
357 entropy->ct = 11;
358 entropy->buffer = -1; /* empty */
359 }
360
361
362 /*
363 * MCU encoding for DC initial scan (either spectral selection,
364 * or first pass of successive approximation).
365 */
366
367 METHODDEF(boolean)
encode_mcu_DC_first(j_compress_ptr cinfo,JBLOCKROW * MCU_data)368 encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
369 {
370 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
371 JBLOCKROW block;
372 unsigned char *st;
373 int blkn, ci, tbl;
374 int v, v2, m;
375 ISHIFT_TEMPS
376
377 /* Emit restart marker if needed */
378 if (cinfo->restart_interval) {
379 if (entropy->restarts_to_go == 0) {
380 emit_restart(cinfo, entropy->next_restart_num);
381 entropy->restarts_to_go = cinfo->restart_interval;
382 entropy->next_restart_num++;
383 entropy->next_restart_num &= 7;
384 }
385 entropy->restarts_to_go--;
386 }
387
388 /* Encode the MCU data blocks */
389 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
390 block = MCU_data[blkn];
391 ci = cinfo->MCU_membership[blkn];
392 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
393
394 /* Compute the DC value after the required point transform by Al.
395 * This is simply an arithmetic right shift.
396 */
397 m = IRIGHT_SHIFT((int)((*block)[0]), cinfo->Al);
398
399 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
400
401 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
402 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
403
404 /* Figure F.4: Encode_DC_DIFF */
405 if ((v = m - entropy->last_dc_val[ci]) == 0) {
406 arith_encode(cinfo, st, 0);
407 entropy->dc_context[ci] = 0; /* zero diff category */
408 } else {
409 entropy->last_dc_val[ci] = m;
410 arith_encode(cinfo, st, 1);
411 /* Figure F.6: Encoding nonzero value v */
412 /* Figure F.7: Encoding the sign of v */
413 if (v > 0) {
414 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
415 st += 2; /* Table F.4: SP = S0 + 2 */
416 entropy->dc_context[ci] = 4; /* small positive diff category */
417 } else {
418 v = -v;
419 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
420 st += 3; /* Table F.4: SN = S0 + 3 */
421 entropy->dc_context[ci] = 8; /* small negative diff category */
422 }
423 /* Figure F.8: Encoding the magnitude category of v */
424 m = 0;
425 if (v -= 1) {
426 arith_encode(cinfo, st, 1);
427 m = 1;
428 v2 = v;
429 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
430 while (v2 >>= 1) {
431 arith_encode(cinfo, st, 1);
432 m <<= 1;
433 st += 1;
434 }
435 }
436 arith_encode(cinfo, st, 0);
437 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
438 if (m < (int)((1L << cinfo->arith_dc_L[tbl]) >> 1))
439 entropy->dc_context[ci] = 0; /* zero diff category */
440 else if (m > (int)((1L << cinfo->arith_dc_U[tbl]) >> 1))
441 entropy->dc_context[ci] += 8; /* large diff category */
442 /* Figure F.9: Encoding the magnitude bit pattern of v */
443 st += 14;
444 while (m >>= 1)
445 arith_encode(cinfo, st, (m & v) ? 1 : 0);
446 }
447 }
448
449 return TRUE;
450 }
451
452
453 /*
454 * MCU encoding for AC initial scan (either spectral selection,
455 * or first pass of successive approximation).
456 */
457
458 METHODDEF(boolean)
encode_mcu_AC_first(j_compress_ptr cinfo,JBLOCKROW * MCU_data)459 encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
460 {
461 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
462 JBLOCKROW block;
463 unsigned char *st;
464 int tbl, k, ke;
465 int v, v2, m;
466
467 /* Emit restart marker if needed */
468 if (cinfo->restart_interval) {
469 if (entropy->restarts_to_go == 0) {
470 emit_restart(cinfo, entropy->next_restart_num);
471 entropy->restarts_to_go = cinfo->restart_interval;
472 entropy->next_restart_num++;
473 entropy->next_restart_num &= 7;
474 }
475 entropy->restarts_to_go--;
476 }
477
478 /* Encode the MCU data block */
479 block = MCU_data[0];
480 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
481
482 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
483
484 /* Establish EOB (end-of-block) index */
485 for (ke = cinfo->Se; ke > 0; ke--)
486 /* We must apply the point transform by Al. For AC coefficients this
487 * is an integer division with rounding towards 0. To do this portably
488 * in C, we shift after obtaining the absolute value.
489 */
490 if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
491 if (v >>= cinfo->Al) break;
492 } else {
493 v = -v;
494 if (v >>= cinfo->Al) break;
495 }
496
497 /* Figure F.5: Encode_AC_Coefficients */
498 for (k = cinfo->Ss; k <= ke; k++) {
499 st = entropy->ac_stats[tbl] + 3 * (k - 1);
500 arith_encode(cinfo, st, 0); /* EOB decision */
501 for (;;) {
502 if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
503 if (v >>= cinfo->Al) {
504 arith_encode(cinfo, st + 1, 1);
505 arith_encode(cinfo, entropy->fixed_bin, 0);
506 break;
507 }
508 } else {
509 v = -v;
510 if (v >>= cinfo->Al) {
511 arith_encode(cinfo, st + 1, 1);
512 arith_encode(cinfo, entropy->fixed_bin, 1);
513 break;
514 }
515 }
516 arith_encode(cinfo, st + 1, 0); st += 3; k++;
517 }
518 st += 2;
519 /* Figure F.8: Encoding the magnitude category of v */
520 m = 0;
521 if (v -= 1) {
522 arith_encode(cinfo, st, 1);
523 m = 1;
524 v2 = v;
525 if (v2 >>= 1) {
526 arith_encode(cinfo, st, 1);
527 m <<= 1;
528 st = entropy->ac_stats[tbl] +
529 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
530 while (v2 >>= 1) {
531 arith_encode(cinfo, st, 1);
532 m <<= 1;
533 st += 1;
534 }
535 }
536 }
537 arith_encode(cinfo, st, 0);
538 /* Figure F.9: Encoding the magnitude bit pattern of v */
539 st += 14;
540 while (m >>= 1)
541 arith_encode(cinfo, st, (m & v) ? 1 : 0);
542 }
543 /* Encode EOB decision only if k <= cinfo->Se */
544 if (k <= cinfo->Se) {
545 st = entropy->ac_stats[tbl] + 3 * (k - 1);
546 arith_encode(cinfo, st, 1);
547 }
548
549 return TRUE;
550 }
551
552
553 /*
554 * MCU encoding for DC successive approximation refinement scan.
555 */
556
557 METHODDEF(boolean)
encode_mcu_DC_refine(j_compress_ptr cinfo,JBLOCKROW * MCU_data)558 encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
559 {
560 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
561 unsigned char *st;
562 int Al, blkn;
563
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;
571 }
572 entropy->restarts_to_go--;
573 }
574
575 st = entropy->fixed_bin; /* use fixed probability estimation */
576 Al = cinfo->Al;
577
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);
582 }
583
584 return TRUE;
585 }
586
587
588 /*
589 * MCU encoding for AC successive approximation refinement scan.
590 */
591
592 METHODDEF(boolean)
encode_mcu_AC_refine(j_compress_ptr cinfo,JBLOCKROW * MCU_data)593 encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
594 {
595 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
596 JBLOCKROW block;
597 unsigned char *st;
598 int tbl, k, ke, kex;
599 int v;
600
601 /* Emit restart marker if needed */
602 if (cinfo->restart_interval) {
603 if (entropy->restarts_to_go == 0) {
604 emit_restart(cinfo, entropy->next_restart_num);
605 entropy->restarts_to_go = cinfo->restart_interval;
606 entropy->next_restart_num++;
607 entropy->next_restart_num &= 7;
608 }
609 entropy->restarts_to_go--;
610 }
611
612 /* Encode the MCU data block */
613 block = MCU_data[0];
614 tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
615
616 /* Section G.1.3.3: Encoding of AC coefficients */
617
618 /* Establish EOB (end-of-block) index */
619 for (ke = cinfo->Se; ke > 0; ke--)
620 /* We must apply the point transform by Al. For AC coefficients this
621 * is an integer division with rounding towards 0. To do this portably
622 * in C, we shift after obtaining the absolute value.
623 */
624 if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
625 if (v >>= cinfo->Al) break;
626 } else {
627 v = -v;
628 if (v >>= cinfo->Al) break;
629 }
630
631 /* Establish EOBx (previous stage end-of-block) index */
632 for (kex = ke; kex > 0; kex--)
633 if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) {
634 if (v >>= cinfo->Ah) break;
635 } else {
636 v = -v;
637 if (v >>= cinfo->Ah) break;
638 }
639
640 /* Figure G.10: Encode_AC_Coefficients_SA */
641 for (k = cinfo->Ss; k <= ke; k++) {
642 st = entropy->ac_stats[tbl] + 3 * (k - 1);
643 if (k > kex)
644 arith_encode(cinfo, st, 0); /* EOB decision */
645 for (;;) {
646 if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
647 if (v >>= cinfo->Al) {
648 if (v >> 1) /* previously nonzero coef */
649 arith_encode(cinfo, st + 2, (v & 1));
650 else { /* newly nonzero coef */
651 arith_encode(cinfo, st + 1, 1);
652 arith_encode(cinfo, entropy->fixed_bin, 0);
653 }
654 break;
655 }
656 } else {
657 v = -v;
658 if (v >>= cinfo->Al) {
659 if (v >> 1) /* previously nonzero coef */
660 arith_encode(cinfo, st + 2, (v & 1));
661 else { /* newly nonzero coef */
662 arith_encode(cinfo, st + 1, 1);
663 arith_encode(cinfo, entropy->fixed_bin, 1);
664 }
665 break;
666 }
667 }
668 arith_encode(cinfo, st + 1, 0); st += 3; k++;
669 }
670 }
671 /* Encode EOB decision only if k <= cinfo->Se */
672 if (k <= cinfo->Se) {
673 st = entropy->ac_stats[tbl] + 3 * (k - 1);
674 arith_encode(cinfo, st, 1);
675 }
676
677 return TRUE;
678 }
679
680
681 /*
682 * Encode and output one MCU's worth of arithmetic-compressed coefficients.
683 */
684
685 METHODDEF(boolean)
encode_mcu(j_compress_ptr cinfo,JBLOCKROW * MCU_data)686 encode_mcu(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
687 {
688 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
689 jpeg_component_info *compptr;
690 JBLOCKROW block;
691 unsigned char *st;
692 int blkn, ci, tbl, k, ke;
693 int v, v2, m;
694
695 /* Emit restart marker if needed */
696 if (cinfo->restart_interval) {
697 if (entropy->restarts_to_go == 0) {
698 emit_restart(cinfo, entropy->next_restart_num);
699 entropy->restarts_to_go = cinfo->restart_interval;
700 entropy->next_restart_num++;
701 entropy->next_restart_num &= 7;
702 }
703 entropy->restarts_to_go--;
704 }
705
706 /* Encode the MCU data blocks */
707 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
708 block = MCU_data[blkn];
709 ci = cinfo->MCU_membership[blkn];
710 compptr = cinfo->cur_comp_info[ci];
711
712 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
713
714 tbl = compptr->dc_tbl_no;
715
716 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
717 st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
718
719 /* Figure F.4: Encode_DC_DIFF */
720 if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
721 arith_encode(cinfo, st, 0);
722 entropy->dc_context[ci] = 0; /* zero diff category */
723 } else {
724 entropy->last_dc_val[ci] = (*block)[0];
725 arith_encode(cinfo, st, 1);
726 /* Figure F.6: Encoding nonzero value v */
727 /* Figure F.7: Encoding the sign of v */
728 if (v > 0) {
729 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
730 st += 2; /* Table F.4: SP = S0 + 2 */
731 entropy->dc_context[ci] = 4; /* small positive diff category */
732 } else {
733 v = -v;
734 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
735 st += 3; /* Table F.4: SN = S0 + 3 */
736 entropy->dc_context[ci] = 8; /* small negative diff category */
737 }
738 /* Figure F.8: Encoding the magnitude category of v */
739 m = 0;
740 if (v -= 1) {
741 arith_encode(cinfo, st, 1);
742 m = 1;
743 v2 = v;
744 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
745 while (v2 >>= 1) {
746 arith_encode(cinfo, st, 1);
747 m <<= 1;
748 st += 1;
749 }
750 }
751 arith_encode(cinfo, st, 0);
752 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
753 if (m < (int)((1L << cinfo->arith_dc_L[tbl]) >> 1))
754 entropy->dc_context[ci] = 0; /* zero diff category */
755 else if (m > (int)((1L << cinfo->arith_dc_U[tbl]) >> 1))
756 entropy->dc_context[ci] += 8; /* large diff category */
757 /* Figure F.9: Encoding the magnitude bit pattern of v */
758 st += 14;
759 while (m >>= 1)
760 arith_encode(cinfo, st, (m & v) ? 1 : 0);
761 }
762
763 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
764
765 tbl = compptr->ac_tbl_no;
766
767 /* Establish EOB (end-of-block) index */
768 for (ke = DCTSIZE2 - 1; ke > 0; ke--)
769 if ((*block)[jpeg_natural_order[ke]]) break;
770
771 /* Figure F.5: Encode_AC_Coefficients */
772 for (k = 1; k <= ke; k++) {
773 st = entropy->ac_stats[tbl] + 3 * (k - 1);
774 arith_encode(cinfo, st, 0); /* EOB decision */
775 while ((v = (*block)[jpeg_natural_order[k]]) == 0) {
776 arith_encode(cinfo, st + 1, 0); st += 3; k++;
777 }
778 arith_encode(cinfo, st + 1, 1);
779 /* Figure F.6: Encoding nonzero value v */
780 /* Figure F.7: Encoding the sign of v */
781 if (v > 0) {
782 arith_encode(cinfo, entropy->fixed_bin, 0);
783 } else {
784 v = -v;
785 arith_encode(cinfo, entropy->fixed_bin, 1);
786 }
787 st += 2;
788 /* Figure F.8: Encoding the magnitude category of v */
789 m = 0;
790 if (v -= 1) {
791 arith_encode(cinfo, st, 1);
792 m = 1;
793 v2 = v;
794 if (v2 >>= 1) {
795 arith_encode(cinfo, st, 1);
796 m <<= 1;
797 st = entropy->ac_stats[tbl] +
798 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
799 while (v2 >>= 1) {
800 arith_encode(cinfo, st, 1);
801 m <<= 1;
802 st += 1;
803 }
804 }
805 }
806 arith_encode(cinfo, st, 0);
807 /* Figure F.9: Encoding the magnitude bit pattern of v */
808 st += 14;
809 while (m >>= 1)
810 arith_encode(cinfo, st, (m & v) ? 1 : 0);
811 }
812 /* Encode EOB decision only if k <= DCTSIZE2 - 1 */
813 if (k <= DCTSIZE2 - 1) {
814 st = entropy->ac_stats[tbl] + 3 * (k - 1);
815 arith_encode(cinfo, st, 1);
816 }
817 }
818
819 return TRUE;
820 }
821
822
823 /*
824 * Initialize for an arithmetic-compressed scan.
825 */
826
827 METHODDEF(void)
start_pass(j_compress_ptr cinfo,boolean gather_statistics)828 start_pass(j_compress_ptr cinfo, boolean gather_statistics)
829 {
830 arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;
831 int ci, tbl;
832 jpeg_component_info *compptr;
833
834 if (gather_statistics)
835 /* Make sure to avoid that in the master control logic!
836 * We are fully adaptive here and need no extra
837 * statistics gathering pass!
838 */
839 ERREXIT(cinfo, JERR_NOT_COMPILED);
840
841 /* We assume jcmaster.c already validated the progressive scan parameters. */
842
843 /* Select execution routines */
844 if (cinfo->progressive_mode) {
845 if (cinfo->Ah == 0) {
846 if (cinfo->Ss == 0)
847 entropy->pub.encode_mcu = encode_mcu_DC_first;
848 else
849 entropy->pub.encode_mcu = encode_mcu_AC_first;
850 } else {
851 if (cinfo->Ss == 0)
852 entropy->pub.encode_mcu = encode_mcu_DC_refine;
853 else
854 entropy->pub.encode_mcu = encode_mcu_AC_refine;
855 }
856 } else
857 entropy->pub.encode_mcu = encode_mcu;
858
859 /* Allocate & initialize requested statistics areas */
860 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
861 compptr = cinfo->cur_comp_info[ci];
862 /* DC needs no table for refinement scan */
863 if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
864 tbl = compptr->dc_tbl_no;
865 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
866 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
867 if (entropy->dc_stats[tbl] == NULL)
868 entropy->dc_stats[tbl] = (unsigned char *)(*cinfo->mem->alloc_small)
869 ((j_common_ptr)cinfo, JPOOL_IMAGE, DC_STAT_BINS);
870 MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
871 /* Initialize DC predictions to 0 */
872 entropy->last_dc_val[ci] = 0;
873 entropy->dc_context[ci] = 0;
874 }
875 /* AC needs no table when not present */
876 if (cinfo->progressive_mode == 0 || cinfo->Se) {
877 tbl = compptr->ac_tbl_no;
878 if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
879 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
880 if (entropy->ac_stats[tbl] == NULL)
881 entropy->ac_stats[tbl] = (unsigned char *)(*cinfo->mem->alloc_small)
882 ((j_common_ptr)cinfo, JPOOL_IMAGE, AC_STAT_BINS);
883 MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
884 #ifdef CALCULATE_SPECTRAL_CONDITIONING
885 if (cinfo->progressive_mode)
886 /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
887 cinfo->arith_ac_K[tbl] = cinfo->Ss +
888 ((8 + cinfo->Se - cinfo->Ss) >> 4);
889 #endif
890 }
891 }
892
893 /* Initialize arithmetic encoding variables */
894 entropy->c = 0;
895 entropy->a = 0x10000L;
896 entropy->sc = 0;
897 entropy->zc = 0;
898 entropy->ct = 11;
899 entropy->buffer = -1; /* empty */
900
901 /* Initialize restart stuff */
902 entropy->restarts_to_go = cinfo->restart_interval;
903 entropy->next_restart_num = 0;
904 }
905
906
907 /*
908 * Module initialization routine for arithmetic entropy encoding.
909 */
910
911 GLOBAL(void)
jinit_arith_encoder(j_compress_ptr cinfo)912 jinit_arith_encoder(j_compress_ptr cinfo)
913 {
914 arith_entropy_ptr entropy;
915 int i;
916
917 entropy = (arith_entropy_ptr)
918 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
919 sizeof(arith_entropy_encoder));
920 cinfo->entropy = (struct jpeg_entropy_encoder *)entropy;
921 entropy->pub.start_pass = start_pass;
922 entropy->pub.finish_pass = finish_pass;
923
924 /* Mark tables unallocated */
925 for (i = 0; i < NUM_ARITH_TBLS; i++) {
926 entropy->dc_stats[i] = NULL;
927 entropy->ac_stats[i] = NULL;
928 }
929
930 /* Initialize index for fixed probability estimation */
931 entropy->fixed_bin[0] = 113;
932 }
933