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