]> git.jsancho.org Git - lugaru.git/blob - Dependencies/libjpeg/jcarith.c
Slightly squash pack stuff
[lugaru.git] / Dependencies / libjpeg / jcarith.c
1 /*
2  * jcarith.c
3  *
4  * Developed 1997-2009 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.
7  *
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).
10  *
11  * Both sequential and progressive modes are supported in this single module.
12  *
13  * Suspension is not currently supported in this module.
14  */
15
16 #define JPEG_INTERNALS
17 #include "jinclude.h"
18 #include "jpeglib.h"
19
20
21 /* Expanded entropy encoder object for arithmetic encoding. */
22
23 typedef struct {
24   struct jpeg_entropy_encoder pub; /* public fields */
25
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 */
33
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 */
36
37   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
38   int next_restart_num;         /* next restart number to write (0-7) */
39
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];
43
44   /* Statistics bin for coding with fixed probability 0.5 */
45   unsigned char fixed_bin[4];
46 } arith_entropy_encoder;
47
48 typedef arith_entropy_encoder * arith_entropy_ptr;
49
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.
54  *
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).
61  */
62
63 #define DC_STAT_BINS 64
64 #define AC_STAT_BINS 256
65
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.
86  *
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.
91  *
92  * Thus, at the moment, we use the default conditioning values
93  * anyway, and do not use the custom formula.
94  *
95 #define CALCULATE_SPECTRAL_CONDITIONING
96  */
97
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.
101  */
102
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)))
109 #else
110 #define ISHIFT_TEMPS
111 #define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
112 #endif
113
114
115 LOCAL(void)
116 emit_byte (int val, j_compress_ptr cinfo)
117 /* Write next output byte; we do not support suspension in this module. */
118 {
119   struct jpeg_destination_mgr * dest = cinfo->dest;
120
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);
125 }
126
127
128 /*
129  * Finish up at the end of an arithmetic-compressed scan.
130  */
131
132 METHODDEF(void)
133 finish_pass (j_compress_ptr cinfo)
134 {
135   arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
136   INT32 temp;
137
138   /* Section D.1.8: Termination of encoding */
139
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;
144   else
145     e->c = temp;
146   /* Send remaining bytes to output */
147   e->c <<= e->ct;
148   if (e->c & 0xF8000000L) {
149     /* One final overflow has to be handled */
150     if (e->buffer >= 0) {
151       if (e->zc)
152         do emit_byte(0x00, cinfo);
153         while (--e->zc);
154       emit_byte(e->buffer + 1, cinfo);
155       if (e->buffer + 1 == 0xFF)
156         emit_byte(0x00, cinfo);
157     }
158     e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
159     e->sc = 0;
160   } else {
161     if (e->buffer == 0)
162       ++e->zc;
163     else if (e->buffer >= 0) {
164       if (e->zc)
165         do emit_byte(0x00, cinfo);
166         while (--e->zc);
167       emit_byte(e->buffer, cinfo);
168     }
169     if (e->sc) {
170       if (e->zc)
171         do emit_byte(0x00, cinfo);
172         while (--e->zc);
173       do {
174         emit_byte(0xFF, cinfo);
175         emit_byte(0x00, cinfo);
176       } while (--e->sc);
177     }
178   }
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);
183       while (--e->zc);
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);
191     }
192   }
193 }
194
195
196 /*
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.
203  *
204  * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
205  *
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).
212  *
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.
216  */
217
218 LOCAL(void)
219 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val) 
220 {
221   register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
222   register unsigned char nl, nm;
223   register INT32 qe, temp;
224   register int sv;
225
226   /* Fetch values from our compact representation of Table D.2:
227    * Qe values and probability estimation state machine
228    */
229   sv = *st;
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 */
233
234   /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
235   e->a -= qe;
236   if (val != (sv >> 7)) {
237     /* Encode the less probable symbol */
238     if (e->a >= qe) {
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
242        * as usual: */
243       e->c += e->a;
244       e->a = qe;
245     }
246     *st = (sv & 0x80) ^ nl;     /* Estimate_after_LPS */
247   } else {
248     /* Encode the more probable symbol */
249     if (e->a >= 0x8000L)
250       return;  /* A >= 0x8000 -> ready, no renormalization required */
251     if (e->a < qe) {
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: */
255       e->c += e->a;
256       e->a = qe;
257     }
258     *st = (sv & 0x80) ^ nm;     /* Estimate_after_MPS */
259   }
260
261   /* Renormalization & data output per section D.1.6 */
262   do {
263     e->a <<= 1;
264     e->c <<= 1;
265     if (--e->ct == 0) {
266       /* Another byte is ready for output */
267       temp = e->c >> 19;
268       if (temp > 0xFF) {
269         /* Handle overflow over all stacked 0xFF bytes */
270         if (e->buffer >= 0) {
271           if (e->zc)
272             do emit_byte(0x00, cinfo);
273             while (--e->zc);
274           emit_byte(e->buffer + 1, cinfo);
275           if (e->buffer + 1 == 0xFF)
276             emit_byte(0x00, cinfo);
277         }
278         e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
279         e->sc = 0;
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) */
286       } else {
287         /* Output all stacked 0xFF bytes, they will not overflow any more */
288         if (e->buffer == 0)
289           ++e->zc;
290         else if (e->buffer >= 0) {
291           if (e->zc)
292             do emit_byte(0x00, cinfo);
293             while (--e->zc);
294           emit_byte(e->buffer, cinfo);
295         }
296         if (e->sc) {
297           if (e->zc)
298             do emit_byte(0x00, cinfo);
299             while (--e->zc);
300           do {
301             emit_byte(0xFF, cinfo);
302             emit_byte(0x00, cinfo);
303           } while (--e->sc);
304         }
305         e->buffer = temp & 0xFF;  /* new output byte (can still overflow) */
306       }
307       e->c &= 0x7FFFFL;
308       e->ct += 8;
309     }
310   } while (e->a < 0x8000L);
311 }
312
313
314 /*
315  * Emit a restart marker & resynchronize predictions.
316  */
317
318 LOCAL(void)
319 emit_restart (j_compress_ptr cinfo, int restart_num)
320 {
321   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
322   int ci;
323   jpeg_component_info * compptr;
324
325   finish_pass(cinfo);
326
327   emit_byte(0xFF, cinfo);
328   emit_byte(JPEG_RST0 + restart_num, cinfo);
329
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;
339     }
340     /* AC needs no table when not present */
341     if (cinfo->Se) {
342       MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
343     }
344   }
345
346   /* Reset arithmetic encoding variables */
347   entropy->c = 0;
348   entropy->a = 0x10000L;
349   entropy->sc = 0;
350   entropy->zc = 0;
351   entropy->ct = 11;
352   entropy->buffer = -1;  /* empty */
353 }
354
355
356 /*
357  * MCU encoding for DC initial scan (either spectral selection,
358  * or first pass of successive approximation).
359  */
360
361 METHODDEF(boolean)
362 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
363 {
364   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
365   JBLOCKROW block;
366   unsigned char *st;
367   int blkn, ci, tbl;
368   int v, v2, m;
369   ISHIFT_TEMPS
370
371   /* Emit restart marker if needed */
372   if (cinfo->restart_interval) {
373     if (entropy->restarts_to_go == 0) {
374       emit_restart(cinfo, entropy->next_restart_num);
375       entropy->restarts_to_go = cinfo->restart_interval;
376       entropy->next_restart_num++;
377       entropy->next_restart_num &= 7;
378     }
379     entropy->restarts_to_go--;
380   }
381
382   /* Encode the MCU data blocks */
383   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
384     block = MCU_data[blkn];
385     ci = cinfo->MCU_membership[blkn];
386     tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
387
388     /* Compute the DC value after the required point transform by Al.
389      * This is simply an arithmetic right shift.
390      */
391     m = IRIGHT_SHIFT((int) ((*block)[0]), cinfo->Al);
392
393     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
394
395     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
396     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
397
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 */
402     } else {
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 */
407       if (v > 0) {
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 */
411       } else {
412         v = -v;
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 */
416       }
417       /* Figure F.8: Encoding the magnitude category of v */
418       m = 0;
419       if (v -= 1) {
420         arith_encode(cinfo, st, 1);
421         m = 1;
422         v2 = v;
423         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
424         while (v2 >>= 1) {
425           arith_encode(cinfo, st, 1);
426           m <<= 1;
427           st += 1;
428         }
429       }
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 */
437       st += 14;
438       while (m >>= 1)
439         arith_encode(cinfo, st, (m & v) ? 1 : 0);
440     }
441   }
442
443   return TRUE;
444 }
445
446
447 /*
448  * MCU encoding for AC initial scan (either spectral selection,
449  * or first pass of successive approximation).
450  */
451
452 METHODDEF(boolean)
453 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
454 {
455   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
456   JBLOCKROW block;
457   unsigned char *st;
458   int tbl, k, ke;
459   int v, v2, m;
460   const int * natural_order;
461
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;
469     }
470     entropy->restarts_to_go--;
471   }
472
473   natural_order = cinfo->natural_order;
474
475   /* Encode the MCU data block */
476   block = MCU_data[0];
477   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
478
479   /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
480
481   /* Establish EOB (end-of-block) index */
482   for (ke = cinfo->Se; ke > 0; ke--)
483     /* We must apply the point transform by Al.  For AC coefficients this
484      * is an integer division with rounding towards 0.  To do this portably
485      * in C, we shift after obtaining the absolute value.
486      */
487     if ((v = (*block)[natural_order[ke]]) >= 0) {
488       if (v >>= cinfo->Al) break;
489     } else {
490       v = -v;
491       if (v >>= cinfo->Al) break;
492     }
493
494   /* Figure F.5: Encode_AC_Coefficients */
495   for (k = cinfo->Ss; k <= ke; k++) {
496     st = entropy->ac_stats[tbl] + 3 * (k - 1);
497     arith_encode(cinfo, st, 0);         /* EOB decision */
498     for (;;) {
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);
503           break;
504         }
505       } else {
506         v = -v;
507         if (v >>= cinfo->Al) {
508           arith_encode(cinfo, st + 1, 1);
509           arith_encode(cinfo, entropy->fixed_bin, 1);
510           break;
511         }
512       }
513       arith_encode(cinfo, st + 1, 0); st += 3; k++;
514     }
515     st += 2;
516     /* Figure F.8: Encoding the magnitude category of v */
517     m = 0;
518     if (v -= 1) {
519       arith_encode(cinfo, st, 1);
520       m = 1;
521       v2 = v;
522       if (v2 >>= 1) {
523         arith_encode(cinfo, st, 1);
524         m <<= 1;
525         st = entropy->ac_stats[tbl] +
526              (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
527         while (v2 >>= 1) {
528           arith_encode(cinfo, st, 1);
529           m <<= 1;
530           st += 1;
531         }
532       }
533     }
534     arith_encode(cinfo, st, 0);
535     /* Figure F.9: Encoding the magnitude bit pattern of v */
536     st += 14;
537     while (m >>= 1)
538       arith_encode(cinfo, st, (m & v) ? 1 : 0);
539   }
540   /* Encode EOB decision only if k <= cinfo->Se */
541   if (k <= cinfo->Se) {
542     st = entropy->ac_stats[tbl] + 3 * (k - 1);
543     arith_encode(cinfo, st, 1);
544   }
545
546   return TRUE;
547 }
548
549
550 /*
551  * MCU encoding for DC successive approximation refinement scan.
552  */
553
554 METHODDEF(boolean)
555 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
556 {
557   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
558   unsigned char *st;
559   int Al, blkn;
560
561   /* Emit restart marker if needed */
562   if (cinfo->restart_interval) {
563     if (entropy->restarts_to_go == 0) {
564       emit_restart(cinfo, entropy->next_restart_num);
565       entropy->restarts_to_go = cinfo->restart_interval;
566       entropy->next_restart_num++;
567       entropy->next_restart_num &= 7;
568     }
569     entropy->restarts_to_go--;
570   }
571
572   st = entropy->fixed_bin;      /* use fixed probability estimation */
573   Al = cinfo->Al;
574
575   /* Encode the MCU data blocks */
576   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
577     /* We simply emit the Al'th bit of the DC coefficient value. */
578     arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
579   }
580
581   return TRUE;
582 }
583
584
585 /*
586  * MCU encoding for AC successive approximation refinement scan.
587  */
588
589 METHODDEF(boolean)
590 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
591 {
592   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
593   JBLOCKROW block;
594   unsigned char *st;
595   int tbl, k, ke, kex;
596   int v;
597   const int * natural_order;
598
599   /* Emit restart marker if needed */
600   if (cinfo->restart_interval) {
601     if (entropy->restarts_to_go == 0) {
602       emit_restart(cinfo, entropy->next_restart_num);
603       entropy->restarts_to_go = cinfo->restart_interval;
604       entropy->next_restart_num++;
605       entropy->next_restart_num &= 7;
606     }
607     entropy->restarts_to_go--;
608   }
609
610   natural_order = cinfo->natural_order;
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)[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)[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)[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)
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   const int * natural_order;
695
696   /* Emit restart marker if needed */
697   if (cinfo->restart_interval) {
698     if (entropy->restarts_to_go == 0) {
699       emit_restart(cinfo, entropy->next_restart_num);
700       entropy->restarts_to_go = cinfo->restart_interval;
701       entropy->next_restart_num++;
702       entropy->next_restart_num &= 7;
703     }
704     entropy->restarts_to_go--;
705   }
706
707   natural_order = cinfo->natural_order;
708
709   /* Encode the MCU data blocks */
710   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
711     block = MCU_data[blkn];
712     ci = cinfo->MCU_membership[blkn];
713     compptr = cinfo->cur_comp_info[ci];
714
715     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
716
717     tbl = compptr->dc_tbl_no;
718
719     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
720     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
721
722     /* Figure F.4: Encode_DC_DIFF */
723     if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
724       arith_encode(cinfo, st, 0);
725       entropy->dc_context[ci] = 0;      /* zero diff category */
726     } else {
727       entropy->last_dc_val[ci] = (*block)[0];
728       arith_encode(cinfo, st, 1);
729       /* Figure F.6: Encoding nonzero value v */
730       /* Figure F.7: Encoding the sign of v */
731       if (v > 0) {
732         arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
733         st += 2;                        /* Table F.4: SP = S0 + 2 */
734         entropy->dc_context[ci] = 4;    /* small positive diff category */
735       } else {
736         v = -v;
737         arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
738         st += 3;                        /* Table F.4: SN = S0 + 3 */
739         entropy->dc_context[ci] = 8;    /* small negative diff category */
740       }
741       /* Figure F.8: Encoding the magnitude category of v */
742       m = 0;
743       if (v -= 1) {
744         arith_encode(cinfo, st, 1);
745         m = 1;
746         v2 = v;
747         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
748         while (v2 >>= 1) {
749           arith_encode(cinfo, st, 1);
750           m <<= 1;
751           st += 1;
752         }
753       }
754       arith_encode(cinfo, st, 0);
755       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
756       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
757         entropy->dc_context[ci] = 0;    /* zero diff category */
758       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
759         entropy->dc_context[ci] += 8;   /* large diff category */
760       /* Figure F.9: Encoding the magnitude bit pattern of v */
761       st += 14;
762       while (m >>= 1)
763         arith_encode(cinfo, st, (m & v) ? 1 : 0);
764     }
765
766     /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
767
768     tbl = compptr->ac_tbl_no;
769
770     /* Establish EOB (end-of-block) index */
771     for (ke = cinfo->lim_Se; ke > 0; ke--)
772       if ((*block)[natural_order[ke]]) break;
773
774     /* Figure F.5: Encode_AC_Coefficients */
775     for (k = 1; k <= ke; k++) {
776       st = entropy->ac_stats[tbl] + 3 * (k - 1);
777       arith_encode(cinfo, st, 0);       /* EOB decision */
778       while ((v = (*block)[natural_order[k]]) == 0) {
779         arith_encode(cinfo, st + 1, 0); st += 3; k++;
780       }
781       arith_encode(cinfo, st + 1, 1);
782       /* Figure F.6: Encoding nonzero value v */
783       /* Figure F.7: Encoding the sign of v */
784       if (v > 0) {
785         arith_encode(cinfo, entropy->fixed_bin, 0);
786       } else {
787         v = -v;
788         arith_encode(cinfo, entropy->fixed_bin, 1);
789       }
790       st += 2;
791       /* Figure F.8: Encoding the magnitude category of v */
792       m = 0;
793       if (v -= 1) {
794         arith_encode(cinfo, st, 1);
795         m = 1;
796         v2 = v;
797         if (v2 >>= 1) {
798           arith_encode(cinfo, st, 1);
799           m <<= 1;
800           st = entropy->ac_stats[tbl] +
801                (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
802           while (v2 >>= 1) {
803             arith_encode(cinfo, st, 1);
804             m <<= 1;
805             st += 1;
806           }
807         }
808       }
809       arith_encode(cinfo, st, 0);
810       /* Figure F.9: Encoding the magnitude bit pattern of v */
811       st += 14;
812       while (m >>= 1)
813         arith_encode(cinfo, st, (m & v) ? 1 : 0);
814     }
815     /* Encode EOB decision only if k <= cinfo->lim_Se */
816     if (k <= cinfo->lim_Se) {
817       st = entropy->ac_stats[tbl] + 3 * (k - 1);
818       arith_encode(cinfo, st, 1);
819     }
820   }
821
822   return TRUE;
823 }
824
825
826 /*
827  * Initialize for an arithmetic-compressed scan.
828  */
829
830 METHODDEF(void)
831 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
832 {
833   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
834   int ci, tbl;
835   jpeg_component_info * compptr;
836
837   if (gather_statistics)
838     /* Make sure to avoid that in the master control logic!
839      * We are fully adaptive here and need no extra
840      * statistics gathering pass!
841      */
842     ERREXIT(cinfo, JERR_NOT_COMPILED);
843
844   /* We assume jcmaster.c already validated the progressive scan parameters. */
845
846   /* Select execution routines */
847   if (cinfo->progressive_mode) {
848     if (cinfo->Ah == 0) {
849       if (cinfo->Ss == 0)
850         entropy->pub.encode_mcu = encode_mcu_DC_first;
851       else
852         entropy->pub.encode_mcu = encode_mcu_AC_first;
853     } else {
854       if (cinfo->Ss == 0)
855         entropy->pub.encode_mcu = encode_mcu_DC_refine;
856       else
857         entropy->pub.encode_mcu = encode_mcu_AC_refine;
858     }
859   } else
860     entropy->pub.encode_mcu = encode_mcu;
861
862   /* Allocate & initialize requested statistics areas */
863   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
864     compptr = cinfo->cur_comp_info[ci];
865     /* DC needs no table for refinement scan */
866     if (cinfo->Ss == 0 && cinfo->Ah == 0) {
867       tbl = compptr->dc_tbl_no;
868       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
869         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
870       if (entropy->dc_stats[tbl] == NULL)
871         entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
872           ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
873       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
874       /* Initialize DC predictions to 0 */
875       entropy->last_dc_val[ci] = 0;
876       entropy->dc_context[ci] = 0;
877     }
878     /* AC needs no table when not present */
879     if (cinfo->Se) {
880       tbl = compptr->ac_tbl_no;
881       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
882         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
883       if (entropy->ac_stats[tbl] == NULL)
884         entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
885           ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
886       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
887 #ifdef CALCULATE_SPECTRAL_CONDITIONING
888       if (cinfo->progressive_mode)
889         /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
890         cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
891 #endif
892     }
893   }
894
895   /* Initialize arithmetic encoding variables */
896   entropy->c = 0;
897   entropy->a = 0x10000L;
898   entropy->sc = 0;
899   entropy->zc = 0;
900   entropy->ct = 11;
901   entropy->buffer = -1;  /* empty */
902
903   /* Initialize restart stuff */
904   entropy->restarts_to_go = cinfo->restart_interval;
905   entropy->next_restart_num = 0;
906 }
907
908
909 /*
910  * Module initialization routine for arithmetic entropy encoding.
911  */
912
913 GLOBAL(void)
914 jinit_arith_encoder (j_compress_ptr cinfo)
915 {
916   arith_entropy_ptr entropy;
917   int i;
918
919   entropy = (arith_entropy_ptr)
920     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
921                                 SIZEOF(arith_entropy_encoder));
922   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
923   entropy->pub.start_pass = start_pass;
924   entropy->pub.finish_pass = finish_pass;
925
926   /* Mark tables unallocated */
927   for (i = 0; i < NUM_ARITH_TBLS; i++) {
928     entropy->dc_stats[i] = NULL;
929     entropy->ac_stats[i] = NULL;
930   }
931
932   /* Initialize index for fixed probability estimation */
933   entropy->fixed_bin[0] = 113;
934 }