workbench/libs/jpeg/jcarith.c

   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];
  46 } arith_entropy_encoder;
  47
  48 typedef arith_entropy_encoder * arith_entropy_ptr;
  49
  50 /* The following two definitions specify the allocation chunk size
  51  * for the statistics area.
  52  * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
  53  * 49 statistics bins for DC, and 245 statistics bins for AC coding.
  54  *
  55  * We use a compact representation with 1 byte per statistics bin,
  56  * thus the numbers directly represent byte sizes.
  57  * This 1 byte per statistics bin contains the meaning of the MPS
  58  * (more probable symbol) in the highest bit (mask 0x80), and the
  59  * index into the probability estimation state machine table
  60  * in the lower bits (mask 0x7F).
  61  */
  62
  63 #define DC_STAT_BINS 64
  64 #define AC_STAT_BINS 256
  65
  66 /* NOTE: Uncomment the following #define if you want to use the
  67  * given formula for calculating the AC conditioning parameter Kx
  68  * for spectral selection progressive coding in section G.1.3.2
  69  * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
  70  * Although the spec and P&M authors claim that this "has proven
  71  * to give good results for 8 bit precision samples", I'm not
  72  * convinced yet that this is really beneficial.
  73  * Early tests gave only very marginal compression enhancements
  74  * (a few - around 5 or so - bytes even for very large files),
  75  * which would turn out rather negative if we'd suppress the
  76  * DAC (Define Arithmetic Conditioning) marker segments for
  77  * the default parameters in the future.
  78  * Note that currently the marker writing module emits 12-byte
  79  * DAC segments for a full-component scan in a color image.
  80  * This is not worth worrying about IMHO. However, since the
  81  * spec defines the default values to be used if the tables
  82  * are omitted (unlike Huffman tables, which are required
  83  * anyway), one might optimize this behaviour in the future,
  84  * and then it would be disadvantageous to use custom tables if
  85  * they don't provide sufficient gain to exceed the DAC size.
  86  *
  87  * On the other hand, I'd consider it as a reasonable result
  88  * that the conditioning has no significant influence on the
  89  * compression performance. This means that the basic
  90  * statistical model is already rather stable.
  91  *
  92  * Thus, at the moment, we use the default conditioning values
  93  * anyway, and do not use the custom formula.
  94  *
  95 #define CALCULATE_SPECTRAL_CONDITIONING
  96  */
  97
  98 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
  99  * We assume that int right shift is unsigned if INT32 right shift is,
 100  * which should be safe.
 101  */
 102
 103 #ifdef RIGHT_SHIFT_IS_UNSIGNED
 104 #define ISHIFT_TEMPS    int ishift_temp;
 105 #define IRIGHT_SHIFT(x,shft)  \
 106         ((ishift_temp = (x)) < 0 ? \
 107          (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
 108          (ishift_temp >> (shft)))
 109 #else
 110 #define ISHIFT_TEMPS
 111 #define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
 112 #endif
 113
 114
 115 LOCAL(void)
 116 emit_byte (int val, j_compress_ptr cinfo)
 117 /* Write next output byte; we do not support suspension in this module. */
 118 {
 119   struct jpeg_destination_mgr * dest = cinfo->dest;
 120
 121   *dest->next_output_byte++ = (JOCTET) val;
 122   if (--dest->free_in_buffer == 0)
 123     if (! (*dest->empty_output_buffer) (cinfo))
 124       ERREXIT(cinfo, JERR_CANT_SUSPEND);
 125 }
 126
 127
 128 /*
 129  * Finish up at the end of an arithmetic-compressed scan.
 130  */
 131
 132 METHODDEF(void)
 133 finish_pass (j_compress_ptr cinfo)
 134 {
 135   arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
 136   INT32 temp;
 137
 138   /* Section D.1.8: Termination of encoding */
 139
 140   /* Find the e->c in the coding interval with the largest
 141    * number of trailing zero bits */
 142   if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
 143     e->c = temp + 0x8000L;
 144   else
 145     e->c = temp;
 146   /* Send remaining bytes to output */
 147   e->c <<= e->ct;
 148   if (e->c & 0xF8000000L) {
 149     /* One final overflow has to be handled */
 150     if (e->buffer >= 0) {
 151       if (e->zc)
 152         do emit_byte(0x00, cinfo);
 153         while (--e->zc);
 154       emit_byte(e->buffer + 1, cinfo);
 155       if (e->buffer + 1 == 0xFF)
 156         emit_byte(0x00, cinfo);
 157     }
 158     e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
 159     e->sc = 0;
 160   } else {
 161     if (e->buffer == 0)
 162       ++e->zc;
 163     else if (e->buffer >= 0) {
 164       if (e->zc)
 165         do emit_byte(0x00, cinfo);
 166         while (--e->zc);
 167       emit_byte(e->buffer, cinfo);
 168     }
 169     if (e->sc) {
 170       if (e->zc)
 171         do emit_byte(0x00, cinfo);
 172         while (--e->zc);
 173       do {
 174         emit_byte(0xFF, cinfo);
 175         emit_byte(0x00, cinfo);
 176       } while (--e->sc);
 177     }
 178   }
 179   /* Output final bytes only if they are not 0x00 */
 180   if (e->c & 0x7FFF800L) {
 181     if (e->zc)  /* output final pending zero bytes */
 182       do emit_byte(0x00, cinfo);
 183       while (--e->zc);
 184     emit_byte((e->c >> 19) & 0xFF, cinfo);
 185     if (((e->c >> 19) & 0xFF) == 0xFF)
 186       emit_byte(0x00, cinfo);
 187     if (e->c & 0x7F800L) {
 188       emit_byte((e->c >> 11) & 0xFF, cinfo);
 189       if (((e->c >> 11) & 0xFF) == 0xFF)
 190         emit_byte(0x00, cinfo);
 191     }
 192   }
 193 }
 194
 195
 196 /*
 197  * The core arithmetic encoding routine (common in JPEG and JBIG).
 198  * This needs to go as fast as possible.
 199  * Machine-dependent optimization facilities
 200  * are not utilized in this portable implementation.
 201  * However, this code should be fairly efficient and
 202  * may be a good base for further optimizations anyway.
 203  *
 204  * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
 205  *
 206  * Note: I've added full "Pacman" termination support to the
 207  * byte output routines, which is equivalent to the optional
 208  * Discard_final_zeros procedure (Figure D.15) in the spec.
 209  * Thus, we always produce the shortest possible output
 210  * stream compliant to the spec (no trailing zero bytes,
 211  * except for FF stuffing).
 212  *
 213  * I've also introduced a new scheme for accessing
 214  * the probability estimation state machine table,
 215  * derived from Markus Kuhn's JBIG implementation.
 216  */
 217
 218 LOCAL(void)
 219 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val)
 220 {
 221   register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
 222   register unsigned char nl, nm;
 223   register INT32 qe, temp;
 224   register int sv;
 225
 226   /* Fetch values from our compact representation of Table D.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;
 323   jpeg_component_info * compptr;
 324
 325   finish_pass(cinfo);
 326
 327   emit_byte(0xFF, cinfo);
 328   emit_byte(JPEG_RST0 + restart_num, cinfo);
 329
 330   /* Re-initialize statistics areas */
 331   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 332     compptr = cinfo->cur_comp_info[ci];
 333     /* DC needs no table for refinement scan */
 334     if (cinfo->Ss == 0 && cinfo->Ah == 0) {
 335       MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
 336       /* Reset DC predictions to 0 */
 337       entropy->last_dc_val[ci] = 0;
 338       entropy->dc_context[ci] = 0;
 339     }
 340     /* AC needs no table when not present */
 341     if (cinfo->Se) {
 342       MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
 343     }
 344   }
 345
 346   /* Reset arithmetic encoding variables */
 347   entropy->c = 0;
 348   entropy->a = 0x10000L;
 349   entropy->sc = 0;
 350   entropy->zc = 0;
 351   entropy->ct = 11;
 352   entropy->buffer = -1;  /* empty */
 353 }
 354
 355
 356 /*
 357  * MCU encoding for DC initial scan (either spectral selection,
 358  * or first pass of successive approximation).
 359  */
 360
 361 METHODDEF(boolean)
 362 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 363 {
 364   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 365   unsigned char *st;
 366   int blkn, ci, tbl;
 367   int v, v2, m;
 368   ISHIFT_TEMPS
 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)
 451 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 452 {
 453   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 454   const int * natural_order;
 455   JBLOCKROW block;
 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)
 558 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 559 {
 560   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 561   unsigned char *st;
 562   int Al, blkn;
 563
 564   /* Emit restart marker if needed */
 565   if (cinfo->restart_interval) {
 566     if (entropy->restarts_to_go == 0) {
 567       emit_restart(cinfo, entropy->next_restart_num);
 568       entropy->restarts_to_go = cinfo->restart_interval;
 569       entropy->next_restart_num++;
 570       entropy->next_restart_num &= 7;
 571     }
 572     entropy->restarts_to_go--;
 573   }
 574
 575   st = entropy->fixed_bin;      /* use fixed probability estimation */
 576   Al = cinfo->Al;
 577
 578   /* Encode the MCU data blocks */
 579   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 580     /* We simply emit the Al'th bit of the DC coefficient value. */
 581     arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
 582   }
 583
 584   return TRUE;
 585 }
 586
 587
 588 /*
 589  * MCU encoding for AC successive approximation refinement scan.
 590  */
 591
 592 METHODDEF(boolean)
 593 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 594 {
 595   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 596   const int * natural_order;
 597   JBLOCKROW block;
 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)
 692 encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 693 {
 694   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 695   const int * natural_order;
 696   JBLOCKROW block;
 697   unsigned char *st;
 698   int tbl, k, ke;
 699   int v, v2, m;
 700   int blkn, ci;
 701   jpeg_component_info * compptr;
 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;
 845   jpeg_component_info * compptr;
 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)
 882           ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
 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)
 895           ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
 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)
 924 jinit_arith_encoder (j_compress_ptr cinfo)
 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,
 931                                 SIZEOF(arith_entropy_encoder));
 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 }