ReactOS  0.4.15-dev-449-g64abd9f
jcarith.c
Go to the documentation of this file.
1 /*
2  * jcarith.c
3  *
4  * Developed 1997-2019 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((int) ((e->c >> 19) & 0xFF), cinfo);
185  if (((e->c >> 19) & 0xFF) == 0xFF)
186  emit_byte(0x00, cinfo);
187  if (e->c & 0x7F800L) {
188  emit_byte((int) ((e->c >> 11) & 0xFF), cinfo);
189  if (((e->c >> 11) & 0xFF) == 0xFF)
190  emit_byte(0x00, cinfo);
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  /* New output byte, might overflow later */
284  e->buffer = (int) (temp & 0xFF);
285  } else if (temp == 0xFF) {
286  ++e->sc; /* stack 0xFF byte (which might overflow later) */
287  } else {
288  /* Output all stacked 0xFF bytes, they will not overflow any more */
289  if (e->buffer == 0)
290  ++e->zc;
291  else if (e->buffer >= 0) {
292  if (e->zc)
293  do emit_byte(0x00, cinfo);
294  while (--e->zc);
295  emit_byte(e->buffer, cinfo);
296  }
297  if (e->sc) {
298  if (e->zc)
299  do emit_byte(0x00, cinfo);
300  while (--e->zc);
301  do {
302  emit_byte(0xFF, cinfo);
303  emit_byte(0x00, cinfo);
304  } while (--e->sc);
305  }
306  /* New output byte (can still overflow) */
307  e->buffer = (int) (temp & 0xFF);
308  }
309  e->c &= 0x7FFFFL;
310  e->ct += 8;
311  }
312  } while (e->a < 0x8000L);
313 }
314 
315 
316 /*
317  * Emit a restart marker & resynchronize predictions.
318  */
319 
320 LOCAL(void)
321 emit_restart (j_compress_ptr cinfo, int restart_num)
322 {
323  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
324  int ci;
326 
327  finish_pass(cinfo);
328 
329  emit_byte(0xFF, cinfo);
330  emit_byte(JPEG_RST0 + restart_num, cinfo);
331 
332  /* Re-initialize statistics areas */
333  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
334  compptr = cinfo->cur_comp_info[ci];
335  /* DC needs no table for refinement scan */
336  if (cinfo->Ss == 0 && cinfo->Ah == 0) {
338  /* Reset DC predictions to 0 */
339  entropy->last_dc_val[ci] = 0;
340  entropy->dc_context[ci] = 0;
341  }
342  /* AC needs no table when not present */
343  if (cinfo->Se) {
345  }
346  }
347 
348  /* Reset arithmetic encoding variables */
349  entropy->c = 0;
350  entropy->a = 0x10000L;
351  entropy->sc = 0;
352  entropy->zc = 0;
353  entropy->ct = 11;
354  entropy->buffer = -1; /* empty */
355 }
356 
357 
358 /*
359  * MCU encoding for DC initial scan (either spectral selection,
360  * or first pass of successive approximation).
361  */
362 
363 METHODDEF(boolean)
365 {
366  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
367  unsigned char *st;
368  int blkn, ci, tbl;
369  int v, v2, m;
371 
372  /* Emit restart marker if needed */
373  if (cinfo->restart_interval) {
374  if (entropy->restarts_to_go == 0) {
375  emit_restart(cinfo, entropy->next_restart_num);
376  entropy->restarts_to_go = cinfo->restart_interval;
377  entropy->next_restart_num++;
378  entropy->next_restart_num &= 7;
379  }
380  entropy->restarts_to_go--;
381  }
382 
383  /* Encode the MCU data blocks */
384  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
385  ci = cinfo->MCU_membership[blkn];
386  tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
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) (MCU_data[blkn][0][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)
454 {
455  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
456  const int * natural_order;
458  unsigned char *st;
459  int tbl, k, ke;
460  int v, v2, m;
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  ke = cinfo->Se;
483  do {
484  /* We must apply the point transform by Al. For AC coefficients this
485  * is an integer division with rounding towards 0. To do this portably
486  * in C, we shift after obtaining the absolute value.
487  */
488  if ((v = (*block)[natural_order[ke]]) >= 0) {
489  if (v >>= cinfo->Al) break;
490  } else {
491  v = -v;
492  if (v >>= cinfo->Al) break;
493  }
494  } while (--ke);
495 
496  /* Figure F.5: Encode_AC_Coefficients */
497  for (k = cinfo->Ss - 1; k < ke;) {
498  st = entropy->ac_stats[tbl] + 3 * k;
499  arith_encode(cinfo, st, 0); /* EOB decision */
500  for (;;) {
501  if ((v = (*block)[natural_order[++k]]) >= 0) {
502  if (v >>= cinfo->Al) {
503  arith_encode(cinfo, st + 1, 1);
504  arith_encode(cinfo, entropy->fixed_bin, 0);
505  break;
506  }
507  } else {
508  v = -v;
509  if (v >>= cinfo->Al) {
510  arith_encode(cinfo, st + 1, 1);
511  arith_encode(cinfo, entropy->fixed_bin, 1);
512  break;
513  }
514  }
515  arith_encode(cinfo, st + 1, 0);
516  st += 3;
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;
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  * Note: we assume such scans can be multi-component,
556  * although the spec is not very clear on the point.
557  */
558 
559 METHODDEF(boolean)
561 {
562  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
563  unsigned char *st;
564  int Al, blkn;
565 
566  /* Emit restart marker if needed */
567  if (cinfo->restart_interval) {
568  if (entropy->restarts_to_go == 0) {
569  emit_restart(cinfo, entropy->next_restart_num);
570  entropy->restarts_to_go = cinfo->restart_interval;
571  entropy->next_restart_num++;
572  entropy->next_restart_num &= 7;
573  }
574  entropy->restarts_to_go--;
575  }
576 
577  st = entropy->fixed_bin; /* use fixed probability estimation */
578  Al = cinfo->Al;
579 
580  /* Encode the MCU data blocks */
581  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
582  /* We simply emit the Al'th bit of the DC coefficient value. */
583  arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
584  }
585 
586  return TRUE;
587 }
588 
589 
590 /*
591  * MCU encoding for AC successive approximation refinement scan.
592  */
593 
594 METHODDEF(boolean)
596 {
597  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
598  const int * natural_order;
600  unsigned char *st;
601  int tbl, k, ke, kex;
602  int v;
603 
604  /* Emit restart marker if needed */
605  if (cinfo->restart_interval) {
606  if (entropy->restarts_to_go == 0) {
607  emit_restart(cinfo, entropy->next_restart_num);
608  entropy->restarts_to_go = cinfo->restart_interval;
609  entropy->next_restart_num++;
610  entropy->next_restart_num &= 7;
611  }
612  entropy->restarts_to_go--;
613  }
614 
615  natural_order = cinfo->natural_order;
616 
617  /* Encode the MCU data block */
618  block = MCU_data[0];
619  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
620 
621  /* Section G.1.3.3: Encoding of AC coefficients */
622 
623  /* Establish EOB (end-of-block) index */
624  ke = cinfo->Se;
625  do {
626  /* We must apply the point transform by Al. For AC coefficients this
627  * is an integer division with rounding towards 0. To do this portably
628  * in C, we shift after obtaining the absolute value.
629  */
630  if ((v = (*block)[natural_order[ke]]) >= 0) {
631  if (v >>= cinfo->Al) break;
632  } else {
633  v = -v;
634  if (v >>= cinfo->Al) break;
635  }
636  } while (--ke);
637 
638  /* Establish EOBx (previous stage end-of-block) index */
639  for (kex = ke; kex > 0; kex--)
640  if ((v = (*block)[natural_order[kex]]) >= 0) {
641  if (v >>= cinfo->Ah) break;
642  } else {
643  v = -v;
644  if (v >>= cinfo->Ah) break;
645  }
646 
647  /* Figure G.10: Encode_AC_Coefficients_SA */
648  for (k = cinfo->Ss - 1; k < ke;) {
649  st = entropy->ac_stats[tbl] + 3 * k;
650  if (k >= kex)
651  arith_encode(cinfo, st, 0); /* EOB decision */
652  for (;;) {
653  if ((v = (*block)[natural_order[++k]]) >= 0) {
654  if (v >>= cinfo->Al) {
655  if (v >> 1) /* previously nonzero coef */
656  arith_encode(cinfo, st + 2, (v & 1));
657  else { /* newly nonzero coef */
658  arith_encode(cinfo, st + 1, 1);
659  arith_encode(cinfo, entropy->fixed_bin, 0);
660  }
661  break;
662  }
663  } else {
664  v = -v;
665  if (v >>= cinfo->Al) {
666  if (v >> 1) /* previously nonzero coef */
667  arith_encode(cinfo, st + 2, (v & 1));
668  else { /* newly nonzero coef */
669  arith_encode(cinfo, st + 1, 1);
670  arith_encode(cinfo, entropy->fixed_bin, 1);
671  }
672  break;
673  }
674  }
675  arith_encode(cinfo, st + 1, 0);
676  st += 3;
677  }
678  }
679  /* Encode EOB decision only if k < cinfo->Se */
680  if (k < cinfo->Se) {
681  st = entropy->ac_stats[tbl] + 3 * k;
682  arith_encode(cinfo, st, 1);
683  }
684 
685  return TRUE;
686 }
687 
688 
689 /*
690  * Encode and output one MCU's worth of arithmetic-compressed coefficients.
691  */
692 
693 METHODDEF(boolean)
695 {
696  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
697  const int * natural_order;
699  unsigned char *st;
700  int tbl, k, ke;
701  int v, v2, m;
702  int blkn, ci;
704 
705  /* Emit restart marker if needed */
706  if (cinfo->restart_interval) {
707  if (entropy->restarts_to_go == 0) {
708  emit_restart(cinfo, entropy->next_restart_num);
709  entropy->restarts_to_go = cinfo->restart_interval;
710  entropy->next_restart_num++;
711  entropy->next_restart_num &= 7;
712  }
713  entropy->restarts_to_go--;
714  }
715 
716  natural_order = cinfo->natural_order;
717 
718  /* Encode the MCU data blocks */
719  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
720  block = MCU_data[blkn];
721  ci = cinfo->MCU_membership[blkn];
722  compptr = cinfo->cur_comp_info[ci];
723 
724  /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
725 
726  tbl = compptr->dc_tbl_no;
727 
728  /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
729  st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
730 
731  /* Figure F.4: Encode_DC_DIFF */
732  if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
733  arith_encode(cinfo, st, 0);
734  entropy->dc_context[ci] = 0; /* zero diff category */
735  } else {
736  entropy->last_dc_val[ci] = (*block)[0];
737  arith_encode(cinfo, st, 1);
738  /* Figure F.6: Encoding nonzero value v */
739  /* Figure F.7: Encoding the sign of v */
740  if (v > 0) {
741  arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
742  st += 2; /* Table F.4: SP = S0 + 2 */
743  entropy->dc_context[ci] = 4; /* small positive diff category */
744  } else {
745  v = -v;
746  arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
747  st += 3; /* Table F.4: SN = S0 + 3 */
748  entropy->dc_context[ci] = 8; /* small negative diff category */
749  }
750  /* Figure F.8: Encoding the magnitude category of v */
751  m = 0;
752  if (v -= 1) {
753  arith_encode(cinfo, st, 1);
754  m = 1;
755  v2 = v;
756  st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
757  while (v2 >>= 1) {
758  arith_encode(cinfo, st, 1);
759  m <<= 1;
760  st += 1;
761  }
762  }
763  arith_encode(cinfo, st, 0);
764  /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
765  if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
766  entropy->dc_context[ci] = 0; /* zero diff category */
767  else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
768  entropy->dc_context[ci] += 8; /* large diff category */
769  /* Figure F.9: Encoding the magnitude bit pattern of v */
770  st += 14;
771  while (m >>= 1)
772  arith_encode(cinfo, st, (m & v) ? 1 : 0);
773  }
774 
775  /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
776 
777  if ((ke = cinfo->lim_Se) == 0) continue;
778  tbl = compptr->ac_tbl_no;
779 
780  /* Establish EOB (end-of-block) index */
781  do {
782  if ((*block)[natural_order[ke]]) break;
783  } while (--ke);
784 
785  /* Figure F.5: Encode_AC_Coefficients */
786  for (k = 0; k < ke;) {
787  st = entropy->ac_stats[tbl] + 3 * k;
788  arith_encode(cinfo, st, 0); /* EOB decision */
789  while ((v = (*block)[natural_order[++k]]) == 0) {
790  arith_encode(cinfo, st + 1, 0);
791  st += 3;
792  }
793  arith_encode(cinfo, st + 1, 1);
794  /* Figure F.6: Encoding nonzero value v */
795  /* Figure F.7: Encoding the sign of v */
796  if (v > 0) {
797  arith_encode(cinfo, entropy->fixed_bin, 0);
798  } else {
799  v = -v;
800  arith_encode(cinfo, entropy->fixed_bin, 1);
801  }
802  st += 2;
803  /* Figure F.8: Encoding the magnitude category of v */
804  m = 0;
805  if (v -= 1) {
806  arith_encode(cinfo, st, 1);
807  m = 1;
808  v2 = v;
809  if (v2 >>= 1) {
810  arith_encode(cinfo, st, 1);
811  m <<= 1;
812  st = entropy->ac_stats[tbl] +
813  (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
814  while (v2 >>= 1) {
815  arith_encode(cinfo, st, 1);
816  m <<= 1;
817  st += 1;
818  }
819  }
820  }
821  arith_encode(cinfo, st, 0);
822  /* Figure F.9: Encoding the magnitude bit pattern of v */
823  st += 14;
824  while (m >>= 1)
825  arith_encode(cinfo, st, (m & v) ? 1 : 0);
826  }
827  /* Encode EOB decision only if k < cinfo->lim_Se */
828  if (k < cinfo->lim_Se) {
829  st = entropy->ac_stats[tbl] + 3 * k;
830  arith_encode(cinfo, st, 1);
831  }
832  }
833 
834  return TRUE;
835 }
836 
837 
838 /*
839  * Initialize for an arithmetic-compressed scan.
840  */
841 
842 METHODDEF(void)
843 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
844 {
845  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
846  int ci, tbl;
848 
849  if (gather_statistics)
850  /* Make sure to avoid that in the master control logic!
851  * We are fully adaptive here and need no extra
852  * statistics gathering pass!
853  */
854  ERREXIT(cinfo, JERR_NOT_COMPILED);
855 
856  /* We assume jcmaster.c already validated the progressive scan parameters. */
857 
858  /* Select execution routines */
859  if (cinfo->progressive_mode) {
860  if (cinfo->Ah == 0) {
861  if (cinfo->Ss == 0)
862  entropy->pub.encode_mcu = encode_mcu_DC_first;
863  else
864  entropy->pub.encode_mcu = encode_mcu_AC_first;
865  } else {
866  if (cinfo->Ss == 0)
867  entropy->pub.encode_mcu = encode_mcu_DC_refine;
868  else
869  entropy->pub.encode_mcu = encode_mcu_AC_refine;
870  }
871  } else
872  entropy->pub.encode_mcu = encode_mcu;
873 
874  /* Allocate & initialize requested statistics areas */
875  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
876  compptr = cinfo->cur_comp_info[ci];
877  /* DC needs no table for refinement scan */
878  if (cinfo->Ss == 0 && cinfo->Ah == 0) {
879  tbl = compptr->dc_tbl_no;
880  if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
881  ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
882  if (entropy->dc_stats[tbl] == NULL)
883  entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
885  MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
886  /* Initialize DC predictions to 0 */
887  entropy->last_dc_val[ci] = 0;
888  entropy->dc_context[ci] = 0;
889  }
890  /* AC needs no table when not present */
891  if (cinfo->Se) {
892  tbl = compptr->ac_tbl_no;
893  if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
894  ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
895  if (entropy->ac_stats[tbl] == NULL)
896  entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
898  MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
899 #ifdef CALCULATE_SPECTRAL_CONDITIONING
900  if (cinfo->progressive_mode)
901  /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
902  cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
903 #endif
904  }
905  }
906 
907  /* Initialize arithmetic encoding variables */
908  entropy->c = 0;
909  entropy->a = 0x10000L;
910  entropy->sc = 0;
911  entropy->zc = 0;
912  entropy->ct = 11;
913  entropy->buffer = -1; /* empty */
914 
915  /* Initialize restart stuff */
916  entropy->restarts_to_go = cinfo->restart_interval;
917  entropy->next_restart_num = 0;
918 }
919 
920 
921 /*
922  * Module initialization routine for arithmetic entropy encoding.
923  */
924 
925 GLOBAL(void)
927 {
928  arith_entropy_ptr entropy;
929  int i;
930 
931  entropy = (arith_entropy_ptr) (*cinfo->mem->alloc_small)
933  cinfo->entropy = &entropy->pub;
934  entropy->pub.start_pass = start_pass;
935  entropy->pub.finish_pass = finish_pass;
936 
937  /* Mark tables unallocated */
938  for (i = 0; i < NUM_ARITH_TBLS; i++) {
939  entropy->dc_stats[i] = NULL;
940  entropy->ac_stats[i] = NULL;
941  }
942 
943  /* Initialize index for fixed probability estimation */
944  entropy->fixed_bin[0] = 113;
945 }
static unsigned int block
Definition: xmlmemory.c:118
encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
Definition: jcarith.c:364
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:453
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:560
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:1126
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:926
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:694
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:595
#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:321
#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:843
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
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31