ReactOS  0.4.14-dev-77-gd9e7c48
jcarith.c
Go to the documentation of this file.
1 /*
2  * jcarith.c
3  *
4  * Developed 1997-2013 by Guido Vollbeding.
5  * This file is part of the Independent JPEG Group's software.
6  * For conditions of distribution and use, see the accompanying README file.
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];
47 
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)
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)
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.3(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;
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) {
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) {
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)
363 {
364  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
365  unsigned char *st;
366  int blkn, ci, tbl;
367  int v, v2, m;
369 
370  /* Emit restart marker if needed */
371  if (cinfo->restart_interval) {
372  if (entropy->restarts_to_go == 0) {
373  emit_restart(cinfo, entropy->next_restart_num);
374  entropy->restarts_to_go = cinfo->restart_interval;
375  entropy->next_restart_num++;
376  entropy->next_restart_num &= 7;
377  }
378  entropy->restarts_to_go--;
379  }
380 
381  /* Encode the MCU data blocks */
382  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
383  ci = cinfo->MCU_membership[blkn];
384  tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
385 
386  /* Compute the DC value after the required point transform by Al.
387  * This is simply an arithmetic right shift.
388  */
389  m = IRIGHT_SHIFT((int) (MCU_data[blkn][0][0]), cinfo->Al);
390 
391  /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
392 
393  /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
394  st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
395 
396  /* Figure F.4: Encode_DC_DIFF */
397  if ((v = m - entropy->last_dc_val[ci]) == 0) {
398  arith_encode(cinfo, st, 0);
399  entropy->dc_context[ci] = 0; /* zero diff category */
400  } else {
401  entropy->last_dc_val[ci] = m;
402  arith_encode(cinfo, st, 1);
403  /* Figure F.6: Encoding nonzero value v */
404  /* Figure F.7: Encoding the sign of v */
405  if (v > 0) {
406  arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
407  st += 2; /* Table F.4: SP = S0 + 2 */
408  entropy->dc_context[ci] = 4; /* small positive diff category */
409  } else {
410  v = -v;
411  arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
412  st += 3; /* Table F.4: SN = S0 + 3 */
413  entropy->dc_context[ci] = 8; /* small negative diff category */
414  }
415  /* Figure F.8: Encoding the magnitude category of v */
416  m = 0;
417  if (v -= 1) {
418  arith_encode(cinfo, st, 1);
419  m = 1;
420  v2 = v;
421  st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
422  while (v2 >>= 1) {
423  arith_encode(cinfo, st, 1);
424  m <<= 1;
425  st += 1;
426  }
427  }
428  arith_encode(cinfo, st, 0);
429  /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
430  if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
431  entropy->dc_context[ci] = 0; /* zero diff category */
432  else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
433  entropy->dc_context[ci] += 8; /* large diff category */
434  /* Figure F.9: Encoding the magnitude bit pattern of v */
435  st += 14;
436  while (m >>= 1)
437  arith_encode(cinfo, st, (m & v) ? 1 : 0);
438  }
439  }
440 
441  return TRUE;
442 }
443 
444 
445 /*
446  * MCU encoding for AC initial scan (either spectral selection,
447  * or first pass of successive approximation).
448  */
449 
450 METHODDEF(boolean)
452 {
453  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
454  const int * natural_order;
456  unsigned char *st;
457  int tbl, k, ke;
458  int v, v2, m;
459 
460  /* Emit restart marker if needed */
461  if (cinfo->restart_interval) {
462  if (entropy->restarts_to_go == 0) {
463  emit_restart(cinfo, entropy->next_restart_num);
464  entropy->restarts_to_go = cinfo->restart_interval;
465  entropy->next_restart_num++;
466  entropy->next_restart_num &= 7;
467  }
468  entropy->restarts_to_go--;
469  }
470 
471  natural_order = cinfo->natural_order;
472 
473  /* Encode the MCU data block */
474  block = MCU_data[0];
475  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
476 
477  /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
478 
479  /* Establish EOB (end-of-block) index */
480  ke = cinfo->Se;
481  do {
482  /* We must apply the point transform by Al. For AC coefficients this
483  * is an integer division with rounding towards 0. To do this portably
484  * in C, we shift after obtaining the absolute value.
485  */
486  if ((v = (*block)[natural_order[ke]]) >= 0) {
487  if (v >>= cinfo->Al) break;
488  } else {
489  v = -v;
490  if (v >>= cinfo->Al) break;
491  }
492  } while (--ke);
493 
494  /* Figure F.5: Encode_AC_Coefficients */
495  for (k = cinfo->Ss - 1; k < ke;) {
496  st = entropy->ac_stats[tbl] + 3 * k;
497  arith_encode(cinfo, st, 0); /* EOB decision */
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);
514  st += 3;
515  }
516  st += 2;
517  /* Figure F.8: Encoding the magnitude category of v */
518  m = 0;
519  if (v -= 1) {
520  arith_encode(cinfo, st, 1);
521  m = 1;
522  v2 = v;
523  if (v2 >>= 1) {
524  arith_encode(cinfo, st, 1);
525  m <<= 1;
526  st = entropy->ac_stats[tbl] +
527  (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
528  while (v2 >>= 1) {
529  arith_encode(cinfo, st, 1);
530  m <<= 1;
531  st += 1;
532  }
533  }
534  }
535  arith_encode(cinfo, st, 0);
536  /* Figure F.9: Encoding the magnitude bit pattern of v */
537  st += 14;
538  while (m >>= 1)
539  arith_encode(cinfo, st, (m & v) ? 1 : 0);
540  }
541  /* Encode EOB decision only if k < cinfo->Se */
542  if (k < cinfo->Se) {
543  st = entropy->ac_stats[tbl] + 3 * k;
544  arith_encode(cinfo, st, 1);
545  }
546 
547  return TRUE;
548 }
549 
550 
551 /*
552  * MCU encoding for DC successive approximation refinement scan.
553  * Note: we assume such scans can be multi-component,
554  * although the spec is not very clear on the point.
555  */
556 
557 METHODDEF(boolean)
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)
594 {
595  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
596  const int * natural_order;
598  unsigned char *st;
599  int tbl, k, ke, kex;
600  int v;
601 
602  /* Emit restart marker if needed */
603  if (cinfo->restart_interval) {
604  if (entropy->restarts_to_go == 0) {
605  emit_restart(cinfo, entropy->next_restart_num);
606  entropy->restarts_to_go = cinfo->restart_interval;
607  entropy->next_restart_num++;
608  entropy->next_restart_num &= 7;
609  }
610  entropy->restarts_to_go--;
611  }
612 
613  natural_order = cinfo->natural_order;
614 
615  /* Encode the MCU data block */
616  block = MCU_data[0];
617  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
618 
619  /* Section G.1.3.3: Encoding of AC coefficients */
620 
621  /* Establish EOB (end-of-block) index */
622  ke = cinfo->Se;
623  do {
624  /* We must apply the point transform by Al. For AC coefficients this
625  * is an integer division with rounding towards 0. To do this portably
626  * in C, we shift after obtaining the absolute value.
627  */
628  if ((v = (*block)[natural_order[ke]]) >= 0) {
629  if (v >>= cinfo->Al) break;
630  } else {
631  v = -v;
632  if (v >>= cinfo->Al) break;
633  }
634  } while (--ke);
635 
636  /* Establish EOBx (previous stage end-of-block) index */
637  for (kex = ke; kex > 0; kex--)
638  if ((v = (*block)[natural_order[kex]]) >= 0) {
639  if (v >>= cinfo->Ah) break;
640  } else {
641  v = -v;
642  if (v >>= cinfo->Ah) break;
643  }
644 
645  /* Figure G.10: Encode_AC_Coefficients_SA */
646  for (k = cinfo->Ss - 1; k < ke;) {
647  st = entropy->ac_stats[tbl] + 3 * k;
648  if (k >= kex)
649  arith_encode(cinfo, st, 0); /* EOB decision */
650  for (;;) {
651  if ((v = (*block)[natural_order[++k]]) >= 0) {
652  if (v >>= cinfo->Al) {
653  if (v >> 1) /* previously nonzero coef */
654  arith_encode(cinfo, st + 2, (v & 1));
655  else { /* newly nonzero coef */
656  arith_encode(cinfo, st + 1, 1);
657  arith_encode(cinfo, entropy->fixed_bin, 0);
658  }
659  break;
660  }
661  } else {
662  v = -v;
663  if (v >>= cinfo->Al) {
664  if (v >> 1) /* previously nonzero coef */
665  arith_encode(cinfo, st + 2, (v & 1));
666  else { /* newly nonzero coef */
667  arith_encode(cinfo, st + 1, 1);
668  arith_encode(cinfo, entropy->fixed_bin, 1);
669  }
670  break;
671  }
672  }
673  arith_encode(cinfo, st + 1, 0);
674  st += 3;
675  }
676  }
677  /* Encode EOB decision only if k < cinfo->Se */
678  if (k < cinfo->Se) {
679  st = entropy->ac_stats[tbl] + 3 * k;
680  arith_encode(cinfo, st, 1);
681  }
682 
683  return TRUE;
684 }
685 
686 
687 /*
688  * Encode and output one MCU's worth of arithmetic-compressed coefficients.
689  */
690 
691 METHODDEF(boolean)
693 {
694  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
695  const int * natural_order;
697  unsigned char *st;
698  int tbl, k, ke;
699  int v, v2, m;
700  int blkn, ci;
702 
703  /* Emit restart marker if needed */
704  if (cinfo->restart_interval) {
705  if (entropy->restarts_to_go == 0) {
706  emit_restart(cinfo, entropy->next_restart_num);
707  entropy->restarts_to_go = cinfo->restart_interval;
708  entropy->next_restart_num++;
709  entropy->next_restart_num &= 7;
710  }
711  entropy->restarts_to_go--;
712  }
713 
714  natural_order = cinfo->natural_order;
715 
716  /* Encode the MCU data blocks */
717  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
718  block = MCU_data[blkn];
719  ci = cinfo->MCU_membership[blkn];
720  compptr = cinfo->cur_comp_info[ci];
721 
722  /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
723 
724  tbl = compptr->dc_tbl_no;
725 
726  /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
727  st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
728 
729  /* Figure F.4: Encode_DC_DIFF */
730  if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
731  arith_encode(cinfo, st, 0);
732  entropy->dc_context[ci] = 0; /* zero diff category */
733  } else {
734  entropy->last_dc_val[ci] = (*block)[0];
735  arith_encode(cinfo, st, 1);
736  /* Figure F.6: Encoding nonzero value v */
737  /* Figure F.7: Encoding the sign of v */
738  if (v > 0) {
739  arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
740  st += 2; /* Table F.4: SP = S0 + 2 */
741  entropy->dc_context[ci] = 4; /* small positive diff category */
742  } else {
743  v = -v;
744  arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
745  st += 3; /* Table F.4: SN = S0 + 3 */
746  entropy->dc_context[ci] = 8; /* small negative diff category */
747  }
748  /* Figure F.8: Encoding the magnitude category of v */
749  m = 0;
750  if (v -= 1) {
751  arith_encode(cinfo, st, 1);
752  m = 1;
753  v2 = v;
754  st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
755  while (v2 >>= 1) {
756  arith_encode(cinfo, st, 1);
757  m <<= 1;
758  st += 1;
759  }
760  }
761  arith_encode(cinfo, st, 0);
762  /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
763  if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
764  entropy->dc_context[ci] = 0; /* zero diff category */
765  else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
766  entropy->dc_context[ci] += 8; /* large diff category */
767  /* Figure F.9: Encoding the magnitude bit pattern of v */
768  st += 14;
769  while (m >>= 1)
770  arith_encode(cinfo, st, (m & v) ? 1 : 0);
771  }
772 
773  /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
774 
775  if ((ke = cinfo->lim_Se) == 0) continue;
776  tbl = compptr->ac_tbl_no;
777 
778  /* Establish EOB (end-of-block) index */
779  do {
780  if ((*block)[natural_order[ke]]) break;
781  } while (--ke);
782 
783  /* Figure F.5: Encode_AC_Coefficients */
784  for (k = 0; k < ke;) {
785  st = entropy->ac_stats[tbl] + 3 * k;
786  arith_encode(cinfo, st, 0); /* EOB decision */
787  while ((v = (*block)[natural_order[++k]]) == 0) {
788  arith_encode(cinfo, st + 1, 0);
789  st += 3;
790  }
791  arith_encode(cinfo, st + 1, 1);
792  /* Figure F.6: Encoding nonzero value v */
793  /* Figure F.7: Encoding the sign of v */
794  if (v > 0) {
795  arith_encode(cinfo, entropy->fixed_bin, 0);
796  } else {
797  v = -v;
798  arith_encode(cinfo, entropy->fixed_bin, 1);
799  }
800  st += 2;
801  /* Figure F.8: Encoding the magnitude category of v */
802  m = 0;
803  if (v -= 1) {
804  arith_encode(cinfo, st, 1);
805  m = 1;
806  v2 = v;
807  if (v2 >>= 1) {
808  arith_encode(cinfo, st, 1);
809  m <<= 1;
810  st = entropy->ac_stats[tbl] +
811  (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
812  while (v2 >>= 1) {
813  arith_encode(cinfo, st, 1);
814  m <<= 1;
815  st += 1;
816  }
817  }
818  }
819  arith_encode(cinfo, st, 0);
820  /* Figure F.9: Encoding the magnitude bit pattern of v */
821  st += 14;
822  while (m >>= 1)
823  arith_encode(cinfo, st, (m & v) ? 1 : 0);
824  }
825  /* Encode EOB decision only if k < cinfo->lim_Se */
826  if (k < cinfo->lim_Se) {
827  st = entropy->ac_stats[tbl] + 3 * k;
828  arith_encode(cinfo, st, 1);
829  }
830  }
831 
832  return TRUE;
833 }
834 
835 
836 /*
837  * Initialize for an arithmetic-compressed scan.
838  */
839 
840 METHODDEF(void)
841 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
842 {
843  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
844  int ci, tbl;
846 
847  if (gather_statistics)
848  /* Make sure to avoid that in the master control logic!
849  * We are fully adaptive here and need no extra
850  * statistics gathering pass!
851  */
852  ERREXIT(cinfo, JERR_NOT_COMPILED);
853 
854  /* We assume jcmaster.c already validated the progressive scan parameters. */
855 
856  /* Select execution routines */
857  if (cinfo->progressive_mode) {
858  if (cinfo->Ah == 0) {
859  if (cinfo->Ss == 0)
860  entropy->pub.encode_mcu = encode_mcu_DC_first;
861  else
862  entropy->pub.encode_mcu = encode_mcu_AC_first;
863  } else {
864  if (cinfo->Ss == 0)
865  entropy->pub.encode_mcu = encode_mcu_DC_refine;
866  else
867  entropy->pub.encode_mcu = encode_mcu_AC_refine;
868  }
869  } else
870  entropy->pub.encode_mcu = encode_mcu;
871 
872  /* Allocate & initialize requested statistics areas */
873  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
874  compptr = cinfo->cur_comp_info[ci];
875  /* DC needs no table for refinement scan */
876  if (cinfo->Ss == 0 && cinfo->Ah == 0) {
877  tbl = compptr->dc_tbl_no;
878  if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
879  ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
880  if (entropy->dc_stats[tbl] == NULL)
881  entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
883  MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
884  /* Initialize DC predictions to 0 */
885  entropy->last_dc_val[ci] = 0;
886  entropy->dc_context[ci] = 0;
887  }
888  /* AC needs no table when not present */
889  if (cinfo->Se) {
890  tbl = compptr->ac_tbl_no;
891  if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
892  ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
893  if (entropy->ac_stats[tbl] == NULL)
894  entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
896  MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
897 #ifdef CALCULATE_SPECTRAL_CONDITIONING
898  if (cinfo->progressive_mode)
899  /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
900  cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
901 #endif
902  }
903  }
904 
905  /* Initialize arithmetic encoding variables */
906  entropy->c = 0;
907  entropy->a = 0x10000L;
908  entropy->sc = 0;
909  entropy->zc = 0;
910  entropy->ct = 11;
911  entropy->buffer = -1; /* empty */
912 
913  /* Initialize restart stuff */
914  entropy->restarts_to_go = cinfo->restart_interval;
915  entropy->next_restart_num = 0;
916 }
917 
918 
919 /*
920  * Module initialization routine for arithmetic entropy encoding.
921  */
922 
923 GLOBAL(void)
925 {
926  arith_entropy_ptr entropy;
927  int i;
928 
929  entropy = (arith_entropy_ptr)
930  (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
932  cinfo->entropy = &entropy->pub;
933  entropy->pub.start_pass = start_pass;
934  entropy->pub.finish_pass = finish_pass;
935 
936  /* Mark tables unallocated */
937  for (i = 0; i < NUM_ARITH_TBLS; i++) {
938  entropy->dc_stats[i] = NULL;
939  entropy->ac_stats[i] = NULL;
940  }
941 
942  /* Initialize index for fixed probability estimation */
943  entropy->fixed_bin[0] = 113;
944 }
static unsigned int block
Definition: xmlmemory.c:118
encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:362
arith_encode(j_compress_ptr cinfo, unsigned char *st, int val)
Definition: jcarith.c:219
#define DC_STAT_BINS
Definition: jcarith.c:63
#define TRUE
Definition: types.h:120
#define ERREXIT(msg)
Definition: rdjpgcom.c:72
emit_byte(int val, j_compress_ptr cinfo)
Definition: jcarith.c:116
encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:451
struct jpeg_common_struct * j_common_ptr
Definition: jpeglib.h:284
unsigned char fixed_bin[4]
Definition: jcarith.c:45
struct jpeg_entropy_encoder pub
Definition: jcarith.c:24
#define MEMZERO(addr, type, size)
Definition: svc_dg.c:324
encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:558
const GLfloat * m
Definition: glext.h:10848
jpeg_component_info * compptr
Definition: jdct.h:238
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define SIZEOF(_ar)
Definition: calc.h:97
#define JPOOL_IMAGE
Definition: jpeglib.h:808
finish_pass(j_compress_ptr cinfo)
Definition: jcarith.c:133
unsigned char * ac_stats[NUM_ARITH_TBLS]
Definition: jcarith.c:42
#define e
Definition: ke_i.h:82
#define JPEG_RST0
Definition: jpeglib.h:1123
smooth NULL
Definition: ftsmooth.c:416
unsigned char * dc_stats[NUM_ARITH_TBLS]
Definition: jcarith.c:41
#define LOCAL(type)
Definition: jmorecfg.h:289
GLuint GLfloat * val
Definition: glext.h:7180
if(!(yy_init))
Definition: macro.lex.yy.c:714
jinit_arith_encoder(j_compress_ptr cinfo)
Definition: jcarith.c:924
JBLOCK FAR * JBLOCKROW
Definition: jpeglib.h:80
arith_entropy_encoder * arith_entropy_ptr
Definition: jcarith.c:48
encode_mcu(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:692
unsigned int restarts_to_go
Definition: jcarith.c:37
#define IRIGHT_SHIFT(x, shft)
Definition: jcarith.c:111
static const WCHAR L[]
Definition: oid.c:1250
#define ERREXIT1(cinfo, code, p1)
Definition: jerror.h:212
encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:593
#define ISHIFT_TEMPS
Definition: jcarith.c:110
int last_dc_val[MAX_COMPS_IN_SCAN]
Definition: jcarith.c:34
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
#define GLOBAL(type)
Definition: jmorecfg.h:291
#define METHODDEF(type)
Definition: jmorecfg.h:287
const GLdouble * v
Definition: gl.h:2040
static calc_node_t temp
Definition: rpn_ieee.c:38
int dc_context[MAX_COMPS_IN_SCAN]
Definition: jcarith.c:35
emit_restart(j_compress_ptr cinfo, int restart_num)
Definition: jcarith.c:319
#define NUM_ARITH_TBLS
Definition: jpeglib.h:54
signed int INT32
char JOCTET
Definition: jmorecfg.h:167
static char * dest
Definition: rtl.c:135
start_pass(j_compress_ptr cinfo, boolean gather_statistics)
Definition: jcarith.c:841
const INT32 jpeg_aritab[113+1]
Definition: jaricom.c:31
#define AC_STAT_BINS
Definition: jcarith.c:64
int k
Definition: mpi.c:3369
#define MAX_COMPS_IN_SCAN
Definition: jpeglib.h:55