source: trunk/libjpeg/jcarith.c @ 289

Last change on this file since 289 was 289, checked in by rbri, 11 years ago

+ missing files

  • Property svn:eol-style set to native
File size: 27.4 KB
Line 
1/*
2 * jcarith.c
3 *
4 * Developed 1997 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
23typedef 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} arith_entropy_encoder;
44
45typedef arith_entropy_encoder * arith_entropy_ptr;
46
47/* The following two definitions specify the allocation chunk size
48 * for the statistics area.
49 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
50 * 49 statistics bins for DC, and 245 statistics bins for AC coding.
51 * Note that we use one additional AC bin for codings with fixed
52 * probability (0.5), thus the minimum number for AC is 246.
53 *
54 * We use a compact representation with 1 byte per statistics bin,
55 * thus the numbers directly represent byte sizes.
56 * This 1 byte per statistics bin contains the meaning of the MPS
57 * (more probable symbol) in the highest bit (mask 0x80), and the
58 * index into the probability estimation state machine table
59 * in the lower bits (mask 0x7F).
60 */
61
62#define DC_STAT_BINS 64
63#define AC_STAT_BINS 256
64
65/* NOTE: Uncomment the following #define if you want to use the
66 * given formula for calculating the AC conditioning parameter Kx
67 * for spectral selection progressive coding in section G.1.3.2
68 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
69 * Although the spec and P&M authors claim that this "has proven
70 * to give good results for 8 bit precision samples", I'm not
71 * convinced yet that this is really beneficial.
72 * Early tests gave only very marginal compression enhancements
73 * (a few - around 5 or so - bytes even for very large files),
74 * which would turn out rather negative if we'd suppress the
75 * DAC (Define Arithmetic Conditioning) marker segments for
76 * the default parameters in the future.
77 * Note that currently the marker writing module emits 12-byte
78 * DAC segments for a full-component scan in a color image.
79 * This is not worth worrying about IMHO. However, since the
80 * spec defines the default values to be used if the tables
81 * are omitted (unlike Huffman tables, which are required
82 * anyway), one might optimize this behaviour in the future,
83 * and then it would be disadvantageous to use custom tables if
84 * they don't provide sufficient gain to exceed the DAC size.
85 *
86 * On the other hand, I'd consider it as a reasonable result
87 * that the conditioning has no significant influence on the
88 * compression performance. This means that the basic
89 * statistical model is already rather stable.
90 *
91 * Thus, at the moment, we use the default conditioning values
92 * anyway, and do not use the custom formula.
93 *
94#define CALCULATE_SPECTRAL_CONDITIONING
95 */
96
97/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
98 * We assume that int right shift is unsigned if INT32 right shift is,
99 * which should be safe.
100 */
101
102#ifdef RIGHT_SHIFT_IS_UNSIGNED
103#define ISHIFT_TEMPS    int ishift_temp;
104#define IRIGHT_SHIFT(x,shft)  \
105        ((ishift_temp = (x)) < 0 ? \
106         (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
107         (ishift_temp >> (shft)))
108#else
109#define ISHIFT_TEMPS
110#define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
111#endif
112
113
114LOCAL(void)
115emit_byte (int val, j_compress_ptr cinfo)
116/* Write next output byte; we do not support suspension in this module. */
117{
118  struct jpeg_destination_mgr * dest = cinfo->dest;
119
120  *dest->next_output_byte++ = (JOCTET) val;
121  if (--dest->free_in_buffer == 0)
122    if (! (*dest->empty_output_buffer) (cinfo))
123      ERREXIT(cinfo, JERR_CANT_SUSPEND);
124}
125
126
127/*
128 * Finish up at the end of an arithmetic-compressed scan.
129 */
130
131METHODDEF(void)
132finish_pass (j_compress_ptr cinfo)
133{
134  arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
135  INT32 temp;
136
137  /* Section D.1.8: Termination of encoding */
138
139  /* Find the e->c in the coding interval with the largest
140   * number of trailing zero bits */
141  if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
142    e->c = temp + 0x8000L;
143  else
144    e->c = temp;
145  /* Send remaining bytes to output */
146  e->c <<= e->ct;
147  if (e->c & 0xF8000000L) {
148    /* One final overflow has to be handled */
149    if (e->buffer >= 0) {
150      if (e->zc)
151        do emit_byte(0x00, cinfo);
152        while (--e->zc);
153      emit_byte(e->buffer + 1, cinfo);
154      if (e->buffer + 1 == 0xFF)
155        emit_byte(0x00, cinfo);
156    }
157    e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
158    e->sc = 0;
159  } else {
160    if (e->buffer == 0)
161      ++e->zc;
162    else if (e->buffer >= 0) {
163      if (e->zc)
164        do emit_byte(0x00, cinfo);
165        while (--e->zc);
166      emit_byte(e->buffer, cinfo);
167    }
168    if (e->sc) {
169      if (e->zc)
170        do emit_byte(0x00, cinfo);
171        while (--e->zc);
172      do {
173        emit_byte(0xFF, cinfo);
174        emit_byte(0x00, cinfo);
175      } while (--e->sc);
176    }
177  }
178  /* Output final bytes only if they are not 0x00 */
179  if (e->c & 0x7FFF800L) {
180    if (e->zc)  /* output final pending zero bytes */
181      do emit_byte(0x00, cinfo);
182      while (--e->zc);
183    emit_byte((e->c >> 19) & 0xFF, cinfo);
184    if (((e->c >> 19) & 0xFF) == 0xFF)
185      emit_byte(0x00, cinfo);
186    if (e->c & 0x7F800L) {
187      emit_byte((e->c >> 11) & 0xFF, cinfo);
188      if (((e->c >> 11) & 0xFF) == 0xFF)
189        emit_byte(0x00, cinfo);
190    }
191  }
192}
193
194
195/*
196 * The core arithmetic encoding routine (common in JPEG and JBIG).
197 * This needs to go as fast as possible.
198 * Machine-dependent optimization facilities
199 * are not utilized in this portable implementation.
200 * However, this code should be fairly efficient and
201 * may be a good base for further optimizations anyway.
202 *
203 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
204 *
205 * Note: I've added full "Pacman" termination support to the
206 * byte output routines, which is equivalent to the optional
207 * Discard_final_zeros procedure (Figure D.15) in the spec.
208 * Thus, we always produce the shortest possible output
209 * stream compliant to the spec (no trailing zero bytes,
210 * except for FF stuffing).
211 *
212 * I've also introduced a new scheme for accessing
213 * the probability estimation state machine table,
214 * derived from Markus Kuhn's JBIG implementation.
215 */
216
217LOCAL(void)
218arith_encode (j_compress_ptr cinfo, unsigned char *st, int val) 
219{
220  extern const INT32 jaritab[];
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 = jaritab[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
318LOCAL(void)
319emit_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  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
331    compptr = cinfo->cur_comp_info[ci];
332    /* Re-initialize statistics areas */
333    if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
334      MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
335      /* Reset DC predictions to 0 */
336      entropy->last_dc_val[ci] = 0;
337      entropy->dc_context[ci] = 0;
338    }
339    if (cinfo->progressive_mode == 0 || cinfo->Ss) {
340      MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
341    }
342  }
343
344  /* Reset arithmetic encoding variables */
345  entropy->c = 0;
346  entropy->a = 0x10000L;
347  entropy->sc = 0;
348  entropy->zc = 0;
349  entropy->ct = 11;
350  entropy->buffer = -1;  /* empty */
351}
352
353
354/*
355 * MCU encoding for DC initial scan (either spectral selection,
356 * or first pass of successive approximation).
357 */
358
359METHODDEF(boolean)
360encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
361{
362  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
363  JBLOCKROW block;
364  unsigned char *st;
365  int blkn, ci, tbl;
366  int v, v2, m;
367  ISHIFT_TEMPS
368
369  /* Emit restart marker if needed */
370  if (cinfo->restart_interval) {
371    if (entropy->restarts_to_go == 0) {
372      emit_restart(cinfo, entropy->next_restart_num);
373      entropy->restarts_to_go = cinfo->restart_interval;
374      entropy->next_restart_num++;
375      entropy->next_restart_num &= 7;
376    }
377    entropy->restarts_to_go--;
378  }
379
380  /* Encode the MCU data blocks */
381  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
382    block = MCU_data[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) ((*block)[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) (((INT32) 1 << cinfo->arith_dc_L[tbl]) >> 1))
431        entropy->dc_context[ci] = 0;    /* zero diff category */
432      else if (m > (int) (((INT32) 1 << 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
450METHODDEF(boolean)
451encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
452{
453  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
454  JBLOCKROW block;
455  unsigned char *st;
456  int tbl, k, ke;
457  int v, v2, m;
458
459  /* Emit restart marker if needed */
460  if (cinfo->restart_interval) {
461    if (entropy->restarts_to_go == 0) {
462      emit_restart(cinfo, entropy->next_restart_num);
463      entropy->restarts_to_go = cinfo->restart_interval;
464      entropy->next_restart_num++;
465      entropy->next_restart_num &= 7;
466    }
467    entropy->restarts_to_go--;
468  }
469
470  /* Encode the MCU data block */
471  block = MCU_data[0];
472  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
473
474  /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
475
476  /* Establish EOB (end-of-block) index */
477  for (ke = cinfo->Se + 1; ke > 1; ke--)
478    /* We must apply the point transform by Al.  For AC coefficients this
479     * is an integer division with rounding towards 0.  To do this portably
480     * in C, we shift after obtaining the absolute value.
481     */
482    if ((v = (*block)[jpeg_natural_order[ke - 1]]) >= 0) {
483      if (v >>= cinfo->Al) break;
484    } else {
485      v = -v;
486      if (v >>= cinfo->Al) break;
487    }
488
489  /* Figure F.5: Encode_AC_Coefficients */
490  for (k = cinfo->Ss; k < ke; k++) {
491    st = entropy->ac_stats[tbl] + 3 * (k - 1);
492    arith_encode(cinfo, st, 0);         /* EOB decision */
493    entropy->ac_stats[tbl][245] = 0;
494    for (;;) {
495      if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
496        if (v >>= cinfo->Al) {
497          arith_encode(cinfo, st + 1, 1);
498          arith_encode(cinfo, entropy->ac_stats[tbl] + 245, 0);
499          break;
500        }
501      } else {
502        v = -v;
503        if (v >>= cinfo->Al) {
504          arith_encode(cinfo, st + 1, 1);
505          arith_encode(cinfo, entropy->ac_stats[tbl] + 245, 1);
506          break;
507        }
508      }
509      arith_encode(cinfo, st + 1, 0); st += 3; k++;
510    }
511    st += 2;
512    /* Figure F.8: Encoding the magnitude category of v */
513    m = 0;
514    if (v -= 1) {
515      arith_encode(cinfo, st, 1);
516      m = 1;
517      v2 = v;
518      if (v2 >>= 1) {
519        arith_encode(cinfo, st, 1);
520        m <<= 1;
521        st = entropy->ac_stats[tbl] +
522             (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
523        while (v2 >>= 1) {
524          arith_encode(cinfo, st, 1);
525          m <<= 1;
526          st += 1;
527        }
528      }
529    }
530    arith_encode(cinfo, st, 0);
531    /* Figure F.9: Encoding the magnitude bit pattern of v */
532    st += 14;
533    while (m >>= 1)
534      arith_encode(cinfo, st, (m & v) ? 1 : 0);
535  }
536  /* Encode EOB decision only if k <= cinfo->Se */
537  if (k <= cinfo->Se) {
538    st = entropy->ac_stats[tbl] + 3 * (k - 1);
539    arith_encode(cinfo, st, 1);
540  }
541
542  return TRUE;
543}
544
545
546/*
547 * MCU encoding for DC successive approximation refinement scan.
548 */
549
550METHODDEF(boolean)
551encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
552{
553  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
554  unsigned char st[4];
555  int Al, blkn;
556
557  /* Emit restart marker if needed */
558  if (cinfo->restart_interval) {
559    if (entropy->restarts_to_go == 0) {
560      emit_restart(cinfo, entropy->next_restart_num);
561      entropy->restarts_to_go = cinfo->restart_interval;
562      entropy->next_restart_num++;
563      entropy->next_restart_num &= 7;
564    }
565    entropy->restarts_to_go--;
566  }
567
568  Al = cinfo->Al;
569
570  /* Encode the MCU data blocks */
571  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
572    st[0] = 0;  /* use fixed probability estimation */
573    /* We simply emit the Al'th bit of the DC coefficient value. */
574    arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
575  }
576
577  return TRUE;
578}
579
580
581/*
582 * MCU encoding for AC successive approximation refinement scan.
583 */
584
585METHODDEF(boolean)
586encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
587{
588  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
589  JBLOCKROW block;
590  unsigned char *st;
591  int tbl, k, ke, kex;
592  int v;
593
594  /* Emit restart marker if needed */
595  if (cinfo->restart_interval) {
596    if (entropy->restarts_to_go == 0) {
597      emit_restart(cinfo, entropy->next_restart_num);
598      entropy->restarts_to_go = cinfo->restart_interval;
599      entropy->next_restart_num++;
600      entropy->next_restart_num &= 7;
601    }
602    entropy->restarts_to_go--;
603  }
604
605  /* Encode the MCU data block */
606  block = MCU_data[0];
607  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
608
609  /* Section G.1.3.3: Encoding of AC coefficients */
610
611  /* Establish EOB (end-of-block) index */
612  for (ke = cinfo->Se + 1; ke > 1; ke--)
613    /* We must apply the point transform by Al.  For AC coefficients this
614     * is an integer division with rounding towards 0.  To do this portably
615     * in C, we shift after obtaining the absolute value.
616     */
617    if ((v = (*block)[jpeg_natural_order[ke - 1]]) >= 0) {
618      if (v >>= cinfo->Al) break;
619    } else {
620      v = -v;
621      if (v >>= cinfo->Al) break;
622    }
623
624  /* Establish EOBx (previous stage end-of-block) index */
625  for (kex = ke; kex > 1; kex--)
626    if ((v = (*block)[jpeg_natural_order[kex - 1]]) >= 0) {
627      if (v >>= cinfo->Ah) break;
628    } else {
629      v = -v;
630      if (v >>= cinfo->Ah) break;
631    }
632
633  /* Figure G.10: Encode_AC_Coefficients_SA */
634  for (k = cinfo->Ss; k < ke; k++) {
635    st = entropy->ac_stats[tbl] + 3 * (k - 1);
636    if (k >= kex)
637      arith_encode(cinfo, st, 0);       /* EOB decision */
638    entropy->ac_stats[tbl][245] = 0;
639    for (;;) {
640      if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
641        if (v >>= cinfo->Al) {
642          if (v >> 1)           /* previously nonzero coef */
643            arith_encode(cinfo, st + 2, (v & 1));
644          else {                /* newly nonzero coef */
645            arith_encode(cinfo, st + 1, 1);
646            arith_encode(cinfo, entropy->ac_stats[tbl] + 245, 0);
647          }
648          break;
649        }
650      } else {
651        v = -v;
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->ac_stats[tbl] + 245, 1);
658          }
659          break;
660        }
661      }
662      arith_encode(cinfo, st + 1, 0); st += 3; k++;
663    }
664  }
665  /* Encode EOB decision only if k <= cinfo->Se */
666  if (k <= cinfo->Se) {
667    st = entropy->ac_stats[tbl] + 3 * (k - 1);
668    arith_encode(cinfo, st, 1);
669  }
670
671  return TRUE;
672}
673
674
675/*
676 * Encode and output one MCU's worth of arithmetic-compressed coefficients.
677 */
678
679METHODDEF(boolean)
680encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
681{
682  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
683  jpeg_component_info * compptr;
684  JBLOCKROW block;
685  unsigned char *st;
686  int blkn, ci, tbl, k, ke;
687  int v, v2, m;
688
689  /* Emit restart marker if needed */
690  if (cinfo->restart_interval) {
691    if (entropy->restarts_to_go == 0) {
692      emit_restart(cinfo, entropy->next_restart_num);
693      entropy->restarts_to_go = cinfo->restart_interval;
694      entropy->next_restart_num++;
695      entropy->next_restart_num &= 7;
696    }
697    entropy->restarts_to_go--;
698  }
699
700  /* Encode the MCU data blocks */
701  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
702    block = MCU_data[blkn];
703    ci = cinfo->MCU_membership[blkn];
704    compptr = cinfo->cur_comp_info[ci];
705
706    /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
707
708    tbl = compptr->dc_tbl_no;
709
710    /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
711    st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
712
713    /* Figure F.4: Encode_DC_DIFF */
714    if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
715      arith_encode(cinfo, st, 0);
716      entropy->dc_context[ci] = 0;      /* zero diff category */
717    } else {
718      entropy->last_dc_val[ci] = (*block)[0];
719      arith_encode(cinfo, st, 1);
720      /* Figure F.6: Encoding nonzero value v */
721      /* Figure F.7: Encoding the sign of v */
722      if (v > 0) {
723        arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
724        st += 2;                        /* Table F.4: SP = S0 + 2 */
725        entropy->dc_context[ci] = 4;    /* small positive diff category */
726      } else {
727        v = -v;
728        arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
729        st += 3;                        /* Table F.4: SN = S0 + 3 */
730        entropy->dc_context[ci] = 8;    /* small negative diff category */
731      }
732      /* Figure F.8: Encoding the magnitude category of v */
733      m = 0;
734      if (v -= 1) {
735        arith_encode(cinfo, st, 1);
736        m = 1;
737        v2 = v;
738        st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
739        while (v2 >>= 1) {
740          arith_encode(cinfo, st, 1);
741          m <<= 1;
742          st += 1;
743        }
744      }
745      arith_encode(cinfo, st, 0);
746      /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
747      if (m < (int) (((INT32) 1 << cinfo->arith_dc_L[tbl]) >> 1))
748        entropy->dc_context[ci] = 0;    /* zero diff category */
749      else if (m > (int) (((INT32) 1 << cinfo->arith_dc_U[tbl]) >> 1))
750        entropy->dc_context[ci] += 8;   /* large diff category */
751      /* Figure F.9: Encoding the magnitude bit pattern of v */
752      st += 14;
753      while (m >>= 1)
754        arith_encode(cinfo, st, (m & v) ? 1 : 0);
755    }
756
757    /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
758
759    tbl = compptr->ac_tbl_no;
760
761    /* Establish EOB (end-of-block) index */
762    for (ke = DCTSIZE2; ke > 1; ke--)
763      if ((*block)[jpeg_natural_order[ke - 1]]) break;
764
765    /* Figure F.5: Encode_AC_Coefficients */
766    for (k = 1; k < ke; k++) {
767      st = entropy->ac_stats[tbl] + 3 * (k - 1);
768      arith_encode(cinfo, st, 0);       /* EOB decision */
769      while ((v = (*block)[jpeg_natural_order[k]]) == 0) {
770        arith_encode(cinfo, st + 1, 0); st += 3; k++;
771      }
772      arith_encode(cinfo, st + 1, 1);
773      /* Figure F.6: Encoding nonzero value v */
774      /* Figure F.7: Encoding the sign of v */
775      entropy->ac_stats[tbl][245] = 0;
776      if (v > 0) {
777        arith_encode(cinfo, entropy->ac_stats[tbl] + 245, 0);
778      } else {
779        v = -v;
780        arith_encode(cinfo, entropy->ac_stats[tbl] + 245, 1);
781      }
782      st += 2;
783      /* Figure F.8: Encoding the magnitude category of v */
784      m = 0;
785      if (v -= 1) {
786        arith_encode(cinfo, st, 1);
787        m = 1;
788        v2 = v;
789        if (v2 >>= 1) {
790          arith_encode(cinfo, st, 1);
791          m <<= 1;
792          st = entropy->ac_stats[tbl] +
793               (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
794          while (v2 >>= 1) {
795            arith_encode(cinfo, st, 1);
796            m <<= 1;
797            st += 1;
798          }
799        }
800      }
801      arith_encode(cinfo, st, 0);
802      /* Figure F.9: Encoding the magnitude bit pattern of v */
803      st += 14;
804      while (m >>= 1)
805        arith_encode(cinfo, st, (m & v) ? 1 : 0);
806    }
807    /* Encode EOB decision only if k < DCTSIZE2 */
808    if (k < DCTSIZE2) {
809      st = entropy->ac_stats[tbl] + 3 * (k - 1);
810      arith_encode(cinfo, st, 1);
811    }
812  }
813
814  return TRUE;
815}
816
817
818/*
819 * Initialize for an arithmetic-compressed scan.
820 */
821
822METHODDEF(void)
823start_pass (j_compress_ptr cinfo, boolean gather_statistics)
824{
825  arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
826  int ci, tbl;
827  jpeg_component_info * compptr;
828
829  if (gather_statistics)
830    /* Make sure to avoid that in the master control logic!
831     * We are fully adaptive here and need no extra
832     * statistics gathering pass!
833     */
834    ERREXIT(cinfo, JERR_NOT_COMPILED);
835
836  /* We assume jcmaster.c already validated the progressive scan parameters. */
837
838  /* Select execution routines */
839  if (cinfo->progressive_mode) {
840    if (cinfo->Ah == 0) {
841      if (cinfo->Ss == 0)
842        entropy->pub.encode_mcu = encode_mcu_DC_first;
843      else
844        entropy->pub.encode_mcu = encode_mcu_AC_first;
845    } else {
846      if (cinfo->Ss == 0)
847        entropy->pub.encode_mcu = encode_mcu_DC_refine;
848      else
849        entropy->pub.encode_mcu = encode_mcu_AC_refine;
850    }
851  } else
852    entropy->pub.encode_mcu = encode_mcu;
853
854  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
855    compptr = cinfo->cur_comp_info[ci];
856    /* Allocate & initialize requested statistics areas */
857    if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
858      tbl = compptr->dc_tbl_no;
859      if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
860        ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
861      if (entropy->dc_stats[tbl] == NULL)
862        entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
863          ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
864      MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
865      /* Initialize DC predictions to 0 */
866      entropy->last_dc_val[ci] = 0;
867      entropy->dc_context[ci] = 0;
868    }
869    if (cinfo->progressive_mode == 0 || cinfo->Ss) {
870      tbl = compptr->ac_tbl_no;
871      if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
872        ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
873      if (entropy->ac_stats[tbl] == NULL)
874        entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
875          ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
876      MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
877#ifdef CALCULATE_SPECTRAL_CONDITIONING
878      if (cinfo->progressive_mode)
879        /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
880        cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
881#endif
882    }
883  }
884
885  /* Initialize arithmetic encoding variables */
886  entropy->c = 0;
887  entropy->a = 0x10000L;
888  entropy->sc = 0;
889  entropy->zc = 0;
890  entropy->ct = 11;
891  entropy->buffer = -1;  /* empty */
892
893  /* Initialize restart stuff */
894  entropy->restarts_to_go = cinfo->restart_interval;
895  entropy->next_restart_num = 0;
896}
897
898
899/*
900 * Module initialization routine for arithmetic entropy encoding.
901 */
902
903GLOBAL(void)
904jinit_arith_encoder (j_compress_ptr cinfo)
905{
906  arith_entropy_ptr entropy;
907  int i;
908
909  entropy = (arith_entropy_ptr)
910    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
911                                SIZEOF(arith_entropy_encoder));
912  cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
913  entropy->pub.start_pass = start_pass;
914  entropy->pub.finish_pass = finish_pass;
915
916  /* Mark tables unallocated */
917  for (i = 0; i < NUM_ARITH_TBLS; i++) {
918    entropy->dc_stats[i] = NULL;
919    entropy->ac_stats[i] = NULL;
920  }
921}
Note: See TracBrowser for help on using the repository browser.