Dependencies/libjpeg/jcarith.c

   1 /*
   2  * jcarith.c
   3  *
   4  * Developed 1997-2009 by Guido Vollbeding.
   5  * This file is part of the Independent JPEG Group's software.
   6  * For conditions of distribution and use, see the accompanying README file.
   7  *
   8  * This file contains portable arithmetic entropy encoding routines for JPEG
   9  * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
  10  *
  11  * Both sequential and progressive modes are supported in this single module.
  12  *
  13  * Suspension is not currently supported in this module.
  14  */
  15
  16 #define JPEG_INTERNALS
  17 #include "jinclude.h"
  18 #include "jpeglib.h"
  19
  20
  21 /* Expanded entropy encoder object for arithmetic encoding. */
  22
  23 typedef struct {
  24   struct jpeg_entropy_encoder pub; /* public fields */
  25
  26   INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */
  27   INT32 a;               /* A register, normalized size of coding interval */
  28   INT32 sc;        /* counter for stacked 0xFF values which might overflow */
  29   INT32 zc;          /* counter for pending 0x00 output values which might *
  30                           * be discarded at the end ("Pacman" termination) */
  31   int ct;  /* bit shift counter, determines when next byte will be written */
  32   int buffer;                /* buffer for most recent output byte != 0xFF */
  33
  34   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  35   int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
  36
  37   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  38   int next_restart_num;         /* next restart number to write (0-7) */
  39
  40   /* Pointers to statistics areas (these workspaces have image lifespan) */
  41   unsigned char * dc_stats[NUM_ARITH_TBLS];
  42   unsigned char * ac_stats[NUM_ARITH_TBLS];
  43
  44   /* Statistics bin for coding with fixed probability 0.5 */
  45   unsigned char fixed_bin[4];
  46 } arith_entropy_encoder;
  47
  48 typedef arith_entropy_encoder * arith_entropy_ptr;
  49
  50 /* The following two definitions specify the allocation chunk size
  51  * for the statistics area.
  52  * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
  53  * 49 statistics bins for DC, and 245 statistics bins for AC coding.
  54  *
  55  * We use a compact representation with 1 byte per statistics bin,
  56  * thus the numbers directly represent byte sizes.
  57  * This 1 byte per statistics bin contains the meaning of the MPS
  58  * (more probable symbol) in the highest bit (mask 0x80), and the
  59  * index into the probability estimation state machine table
  60  * in the lower bits (mask 0x7F).
  61  */
  62
  63 #define DC_STAT_BINS 64
  64 #define AC_STAT_BINS 256
  65
  66 /* NOTE: Uncomment the following #define if you want to use the
  67  * given formula for calculating the AC conditioning parameter Kx
  68  * for spectral selection progressive coding in section G.1.3.2
  69  * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
  70  * Although the spec and P&M authors claim that this "has proven
  71  * to give good results for 8 bit precision samples", I'm not
  72  * convinced yet that this is really beneficial.
  73  * Early tests gave only very marginal compression enhancements
  74  * (a few - around 5 or so - bytes even for very large files),
  75  * which would turn out rather negative if we'd suppress the
  76  * DAC (Define Arithmetic Conditioning) marker segments for
  77  * the default parameters in the future.
  78  * Note that currently the marker writing module emits 12-byte
  79  * DAC segments for a full-component scan in a color image.
  80  * This is not worth worrying about IMHO. However, since the
  81  * spec defines the default values to be used if the tables
  82  * are omitted (unlike Huffman tables, which are required
  83  * anyway), one might optimize this behaviour in the future,
  84  * and then it would be disadvantageous to use custom tables if
  85  * they don't provide sufficient gain to exceed the DAC size.
  86  *
  87  * On the other hand, I'd consider it as a reasonable result
  88  * that the conditioning has no significant influence on the
  89  * compression performance. This means that the basic
  90  * statistical model is already rather stable.
  91  *
  92  * Thus, at the moment, we use the default conditioning values
  93  * anyway, and do not use the custom formula.
  94  *
  95 #define CALCULATE_SPECTRAL_CONDITIONING
  96  */
  97
  98 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
  99  * We assume that int right shift is unsigned if INT32 right shift is,
 100  * which should be safe.
 101  */
 102
 103 #ifdef RIGHT_SHIFT_IS_UNSIGNED
 104 #define ISHIFT_TEMPS    int ishift_temp;
 105 #define IRIGHT_SHIFT(x,shft)  \
 106         ((ishift_temp = (x)) < 0 ? \
 107          (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
 108          (ishift_temp >> (shft)))
 109 #else
 110 #define ISHIFT_TEMPS
 111 #define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
 112 #endif
 113
 114
 115 LOCAL(void)
 116 emit_byte (int val, j_compress_ptr cinfo)
 117 /* Write next output byte; we do not support suspension in this module. */
 118 {
 119   struct jpeg_destination_mgr * dest = cinfo->dest;
 120
 121   *dest->next_output_byte++ = (JOCTET) val;
 122   if (--dest->free_in_buffer == 0)
 123     if (! (*dest->empty_output_buffer) (cinfo))
 124       ERREXIT(cinfo, JERR_CANT_SUSPEND);
 125 }
 126
 127
 128 /*
 129  * Finish up at the end of an arithmetic-compressed scan.
 130  */
 131
 132 METHODDEF(void)
 133 finish_pass (j_compress_ptr cinfo)
 134 {
 135   arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
 136   INT32 temp;
 137
 138   /* Section D.1.8: Termination of encoding */
 139
 140   /* Find the e->c in the coding interval with the largest
 141    * number of trailing zero bits */
 142   if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
 143     e->c = temp + 0x8000L;
 144   else
 145     e->c = temp;
 146   /* Send remaining bytes to output */
 147   e->c <<= e->ct;
 148   if (e->c & 0xF8000000L) {
 149     /* One final overflow has to be handled */
 150     if (e->buffer >= 0) {
 151       if (e->zc)
 152         do emit_byte(0x00, cinfo);
 153         while (--e->zc);
 154       emit_byte(e->buffer + 1, cinfo);
 155       if (e->buffer + 1 == 0xFF)
 156         emit_byte(0x00, cinfo);
 157     }
 158     e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
 159     e->sc = 0;
 160   } else {
 161     if (e->buffer == 0)
 162       ++e->zc;
 163     else if (e->buffer >= 0) {
 164       if (e->zc)
 165         do emit_byte(0x00, cinfo);
 166         while (--e->zc);
 167       emit_byte(e->buffer, cinfo);
 168     }
 169     if (e->sc) {
 170       if (e->zc)
 171         do emit_byte(0x00, cinfo);
 172         while (--e->zc);
 173       do {
 174         emit_byte(0xFF, cinfo);
 175         emit_byte(0x00, cinfo);
 176       } while (--e->sc);
 177     }
 178   }
 179   /* Output final bytes only if they are not 0x00 */
 180   if (e->c & 0x7FFF800L) {
 181     if (e->zc)  /* output final pending zero bytes */
 182       do emit_byte(0x00, cinfo);
 183       while (--e->zc);
 184     emit_byte((e->c >> 19) & 0xFF, cinfo);
 185     if (((e->c >> 19) & 0xFF) == 0xFF)
 186       emit_byte(0x00, cinfo);
 187     if (e->c & 0x7F800L) {
 188       emit_byte((e->c >> 11) & 0xFF, cinfo);
 189       if (((e->c >> 11) & 0xFF) == 0xFF)
 190         emit_byte(0x00, cinfo);
 191     }
 192   }
 193 }
 194
 195
 196 /*
 197  * The core arithmetic encoding routine (common in JPEG and JBIG).
 198  * This needs to go as fast as possible.
 199  * Machine-dependent optimization facilities
 200  * are not utilized in this portable implementation.
 201  * However, this code should be fairly efficient and
 202  * may be a good base for further optimizations anyway.
 203  *
 204  * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
 205  *
 206  * Note: I've added full "Pacman" termination support to the
 207  * byte output routines, which is equivalent to the optional
 208  * Discard_final_zeros procedure (Figure D.15) in the spec.
 209  * Thus, we always produce the shortest possible output
 210  * stream compliant to the spec (no trailing zero bytes,
 211  * except for FF stuffing).
 212  *
 213  * I've also introduced a new scheme for accessing
 214  * the probability estimation state machine table,
 215  * derived from Markus Kuhn's JBIG implementation.
 216  */
 217
 218 LOCAL(void)
 219 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val)
 220 {
 221   register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
 222   register unsigned char nl, nm;
 223   register INT32 qe, temp;
 224   register int sv;
 225
 226   /* Fetch values from our compact representation of Table D.2:
 227    * Qe values and probability estimation state machine
 228    */
 229   sv = *st;
 230   qe = jpeg_aritab[sv & 0x7F];  /* => Qe_Value */
 231   nl = qe & 0xFF; qe >>= 8;     /* Next_Index_LPS + Switch_MPS */
 232   nm = qe & 0xFF; qe >>= 8;     /* Next_Index_MPS */
 233
 234   /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
 235   e->a -= qe;
 236   if (val != (sv >> 7)) {
 237     /* Encode the less probable symbol */
 238     if (e->a >= qe) {
 239       /* If the interval size (qe) for the less probable symbol (LPS)
 240        * is larger than the interval size for the MPS, then exchange
 241        * the two symbols for coding efficiency, otherwise code the LPS
 242        * as usual: */
 243       e->c += e->a;
 244       e->a = qe;
 245     }
 246     *st = (sv & 0x80) ^ nl;     /* Estimate_after_LPS */
 247   } else {
 248     /* Encode the more probable symbol */
 249     if (e->a >= 0x8000L)
 250       return;  /* A >= 0x8000 -> ready, no renormalization required */
 251     if (e->a < qe) {
 252       /* If the interval size (qe) for the less probable symbol (LPS)
 253        * is larger than the interval size for the MPS, then exchange
 254        * the two symbols for coding efficiency: */
 255       e->c += e->a;
 256       e->a = qe;
 257     }
 258     *st = (sv & 0x80) ^ nm;     /* Estimate_after_MPS */
 259   }
 260
 261   /* Renormalization & data output per section D.1.6 */
 262   do {
 263     e->a <<= 1;
 264     e->c <<= 1;
 265     if (--e->ct == 0) {
 266       /* Another byte is ready for output */
 267       temp = e->c >> 19;
 268       if (temp > 0xFF) {
 269         /* Handle overflow over all stacked 0xFF bytes */
 270         if (e->buffer >= 0) {
 271           if (e->zc)
 272             do emit_byte(0x00, cinfo);
 273             while (--e->zc);
 274           emit_byte(e->buffer + 1, cinfo);
 275           if (e->buffer + 1 == 0xFF)
 276             emit_byte(0x00, cinfo);
 277         }
 278         e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
 279         e->sc = 0;
 280         /* Note: The 3 spacer bits in the C register guarantee
 281          * that the new buffer byte can't be 0xFF here
 282          * (see page 160 in the P&M JPEG book). */
 283         e->buffer = temp & 0xFF;  /* new output byte, might overflow later */
 284       } else if (temp == 0xFF) {
 285         ++e->sc;  /* stack 0xFF byte (which might overflow later) */
 286       } else {
 287         /* Output all stacked 0xFF bytes, they will not overflow any more */
 288         if (e->buffer == 0)
 289           ++e->zc;
 290         else if (e->buffer >= 0) {
 291           if (e->zc)
 292             do emit_byte(0x00, cinfo);
 293             while (--e->zc);
 294           emit_byte(e->buffer, cinfo);
 295         }
 296         if (e->sc) {
 297           if (e->zc)
 298             do emit_byte(0x00, cinfo);
 299             while (--e->zc);
 300           do {
 301             emit_byte(0xFF, cinfo);
 302             emit_byte(0x00, cinfo);
 303           } while (--e->sc);
 304         }
 305         e->buffer = temp & 0xFF;  /* new output byte (can still overflow) */
 306       }
 307       e->c &= 0x7FFFFL;
 308       e->ct += 8;
 309     }
 310   } while (e->a < 0x8000L);
 311 }
 312
 313
 314 /*
 315  * Emit a restart marker & resynchronize predictions.
 316  */
 317
 318 LOCAL(void)
 319 emit_restart (j_compress_ptr cinfo, int restart_num)
 320 {
 321   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 322   int ci;
 323   jpeg_component_info * compptr;
 324
 325   finish_pass(cinfo);
 326
 327   emit_byte(0xFF, cinfo);
 328   emit_byte(JPEG_RST0 + restart_num, cinfo);
 329
 330   /* Re-initialize statistics areas */
 331   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 332     compptr = cinfo->cur_comp_info[ci];
 333     /* DC needs no table for refinement scan */
 334     if (cinfo->Ss == 0 && cinfo->Ah == 0) {
 335       MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
 336       /* Reset DC predictions to 0 */
 337       entropy->last_dc_val[ci] = 0;
 338       entropy->dc_context[ci] = 0;
 339     }
 340     /* AC needs no table when not present */
 341     if (cinfo->Se) {
 342       MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
 343     }
 344   }
 345
 346   /* Reset arithmetic encoding variables */
 347   entropy->c = 0;
 348   entropy->a = 0x10000L;
 349   entropy->sc = 0;
 350   entropy->zc = 0;
 351   entropy->ct = 11;
 352   entropy->buffer = -1;  /* empty */
 353 }
 354
 355
 356 /*
 357  * MCU encoding for DC initial scan (either spectral selection,
 358  * or first pass of successive approximation).
 359  */
 360
 361 METHODDEF(boolean)
 362 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 363 {
 364   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 365   JBLOCKROW block;
 366   unsigned char *st;
 367   int blkn, ci, tbl;
 368   int v, v2, m;
 369   ISHIFT_TEMPS
 370
 371   /* Emit restart marker if needed */
 372   if (cinfo->restart_interval) {
 373     if (entropy->restarts_to_go == 0) {
 374       emit_restart(cinfo, entropy->next_restart_num);
 375       entropy->restarts_to_go = cinfo->restart_interval;
 376       entropy->next_restart_num++;
 377       entropy->next_restart_num &= 7;
 378     }
 379     entropy->restarts_to_go--;
 380   }
 381
 382   /* Encode the MCU data blocks */
 383   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 384     block = MCU_data[blkn];
 385     ci = cinfo->MCU_membership[blkn];
 386     tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
 387
 388     /* Compute the DC value after the required point transform by Al.
 389      * This is simply an arithmetic right shift.
 390      */
 391     m = IRIGHT_SHIFT((int) ((*block)[0]), cinfo->Al);
 392
 393     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
 394
 395     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
 396     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
 397
 398     /* Figure F.4: Encode_DC_DIFF */
 399     if ((v = m - entropy->last_dc_val[ci]) == 0) {
 400       arith_encode(cinfo, st, 0);
 401       entropy->dc_context[ci] = 0;      /* zero diff category */
 402     } else {
 403       entropy->last_dc_val[ci] = m;
 404       arith_encode(cinfo, st, 1);
 405       /* Figure F.6: Encoding nonzero value v */
 406       /* Figure F.7: Encoding the sign of v */
 407       if (v > 0) {
 408         arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
 409         st += 2;                        /* Table F.4: SP = S0 + 2 */
 410         entropy->dc_context[ci] = 4;    /* small positive diff category */
 411       } else {
 412         v = -v;
 413         arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
 414         st += 3;                        /* Table F.4: SN = S0 + 3 */
 415         entropy->dc_context[ci] = 8;    /* small negative diff category */
 416       }
 417       /* Figure F.8: Encoding the magnitude category of v */
 418       m = 0;
 419       if (v -= 1) {
 420         arith_encode(cinfo, st, 1);
 421         m = 1;
 422         v2 = v;
 423         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
 424         while (v2 >>= 1) {
 425           arith_encode(cinfo, st, 1);
 426           m <<= 1;
 427           st += 1;
 428         }
 429       }
 430       arith_encode(cinfo, st, 0);
 431       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
 432       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
 433         entropy->dc_context[ci] = 0;    /* zero diff category */
 434       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
 435         entropy->dc_context[ci] += 8;   /* large diff category */
 436       /* Figure F.9: Encoding the magnitude bit pattern of v */
 437       st += 14;
 438       while (m >>= 1)
 439         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 440     }
 441   }
 442
 443   return TRUE;
 444 }
 445
 446
 447 /*
 448  * MCU encoding for AC initial scan (either spectral selection,
 449  * or first pass of successive approximation).
 450  */
 451
 452 METHODDEF(boolean)
 453 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 454 {
 455   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 456   JBLOCKROW block;
 457   unsigned char *st;
 458   int tbl, k, ke;
 459   int v, v2, m;
 460   const int * natural_order;
 461
 462   /* Emit restart marker if needed */
 463   if (cinfo->restart_interval) {
 464     if (entropy->restarts_to_go == 0) {
 465       emit_restart(cinfo, entropy->next_restart_num);
 466       entropy->restarts_to_go = cinfo->restart_interval;
 467       entropy->next_restart_num++;
 468       entropy->next_restart_num &= 7;
 469     }
 470     entropy->restarts_to_go--;
 471   }
 472
 473   natural_order = cinfo->natural_order;
 474
 475   /* Encode the MCU data block */
 476   block = MCU_data[0];
 477   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
 478
 479   /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
 480
 481   /* Establish EOB (end-of-block) index */
 482   for (ke = cinfo->Se; ke > 0; ke--)
 483     /* We must apply the point transform by Al.  For AC coefficients this
 484      * is an integer division with rounding towards 0.  To do this portably
 485      * in C, we shift after obtaining the absolute value.
 486      */
 487     if ((v = (*block)[natural_order[ke]]) >= 0) {
 488       if (v >>= cinfo->Al) break;
 489     } else {
 490       v = -v;
 491       if (v >>= cinfo->Al) break;
 492     }
 493
 494   /* Figure F.5: Encode_AC_Coefficients */
 495   for (k = cinfo->Ss; k <= ke; k++) {
 496     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 497     arith_encode(cinfo, st, 0);         /* EOB decision */
 498     for (;;) {
 499       if ((v = (*block)[natural_order[k]]) >= 0) {
 500         if (v >>= cinfo->Al) {
 501           arith_encode(cinfo, st + 1, 1);
 502           arith_encode(cinfo, entropy->fixed_bin, 0);
 503           break;
 504         }
 505       } else {
 506         v = -v;
 507         if (v >>= cinfo->Al) {
 508           arith_encode(cinfo, st + 1, 1);
 509           arith_encode(cinfo, entropy->fixed_bin, 1);
 510           break;
 511         }
 512       }
 513       arith_encode(cinfo, st + 1, 0); st += 3; k++;
 514     }
 515     st += 2;
 516     /* Figure F.8: Encoding the magnitude category of v */
 517     m = 0;
 518     if (v -= 1) {
 519       arith_encode(cinfo, st, 1);
 520       m = 1;
 521       v2 = v;
 522       if (v2 >>= 1) {
 523         arith_encode(cinfo, st, 1);
 524         m <<= 1;
 525         st = entropy->ac_stats[tbl] +
 526              (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 527         while (v2 >>= 1) {
 528           arith_encode(cinfo, st, 1);
 529           m <<= 1;
 530           st += 1;
 531         }
 532       }
 533     }
 534     arith_encode(cinfo, st, 0);
 535     /* Figure F.9: Encoding the magnitude bit pattern of v */
 536     st += 14;
 537     while (m >>= 1)
 538       arith_encode(cinfo, st, (m & v) ? 1 : 0);
 539   }
 540   /* Encode EOB decision only if k <= cinfo->Se */
 541   if (k <= cinfo->Se) {
 542     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 543     arith_encode(cinfo, st, 1);
 544   }
 545
 546   return TRUE;
 547 }
 548
 549
 550 /*
 551  * MCU encoding for DC successive approximation refinement scan.
 552  */
 553
 554 METHODDEF(boolean)
 555 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 556 {
 557   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 558   unsigned char *st;
 559   int Al, blkn;
 560
 561   /* Emit restart marker if needed */
 562   if (cinfo->restart_interval) {
 563     if (entropy->restarts_to_go == 0) {
 564       emit_restart(cinfo, entropy->next_restart_num);
 565       entropy->restarts_to_go = cinfo->restart_interval;
 566       entropy->next_restart_num++;
 567       entropy->next_restart_num &= 7;
 568     }
 569     entropy->restarts_to_go--;
 570   }
 571
 572   st = entropy->fixed_bin;      /* use fixed probability estimation */
 573   Al = cinfo->Al;
 574
 575   /* Encode the MCU data blocks */
 576   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 577     /* We simply emit the Al'th bit of the DC coefficient value. */
 578     arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
 579   }
 580
 581   return TRUE;
 582 }
 583
 584
 585 /*
 586  * MCU encoding for AC successive approximation refinement scan.
 587  */
 588
 589 METHODDEF(boolean)
 590 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 591 {
 592   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 593   JBLOCKROW block;
 594   unsigned char *st;
 595   int tbl, k, ke, kex;
 596   int v;
 597   const int * natural_order;
 598
 599   /* Emit restart marker if needed */
 600   if (cinfo->restart_interval) {
 601     if (entropy->restarts_to_go == 0) {
 602       emit_restart(cinfo, entropy->next_restart_num);
 603       entropy->restarts_to_go = cinfo->restart_interval;
 604       entropy->next_restart_num++;
 605       entropy->next_restart_num &= 7;
 606     }
 607     entropy->restarts_to_go--;
 608   }
 609
 610   natural_order = cinfo->natural_order;
 611
 612   /* Encode the MCU data block */
 613   block = MCU_data[0];
 614   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
 615
 616   /* Section G.1.3.3: Encoding of AC coefficients */
 617
 618   /* Establish EOB (end-of-block) index */
 619   for (ke = cinfo->Se; ke > 0; ke--)
 620     /* We must apply the point transform by Al.  For AC coefficients this
 621      * is an integer division with rounding towards 0.  To do this portably
 622      * in C, we shift after obtaining the absolute value.
 623      */
 624     if ((v = (*block)[natural_order[ke]]) >= 0) {
 625       if (v >>= cinfo->Al) break;
 626     } else {
 627       v = -v;
 628       if (v >>= cinfo->Al) break;
 629     }
 630
 631   /* Establish EOBx (previous stage end-of-block) index */
 632   for (kex = ke; kex > 0; kex--)
 633     if ((v = (*block)[natural_order[kex]]) >= 0) {
 634       if (v >>= cinfo->Ah) break;
 635     } else {
 636       v = -v;
 637       if (v >>= cinfo->Ah) break;
 638     }
 639
 640   /* Figure G.10: Encode_AC_Coefficients_SA */
 641   for (k = cinfo->Ss; k <= ke; k++) {
 642     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 643     if (k > kex)
 644       arith_encode(cinfo, st, 0);       /* EOB decision */
 645     for (;;) {
 646       if ((v = (*block)[natural_order[k]]) >= 0) {
 647         if (v >>= cinfo->Al) {
 648           if (v >> 1)                   /* previously nonzero coef */
 649             arith_encode(cinfo, st + 2, (v & 1));
 650           else {                        /* newly nonzero coef */
 651             arith_encode(cinfo, st + 1, 1);
 652             arith_encode(cinfo, entropy->fixed_bin, 0);
 653           }
 654           break;
 655         }
 656       } else {
 657         v = -v;
 658         if (v >>= cinfo->Al) {
 659           if (v >> 1)                   /* previously nonzero coef */
 660             arith_encode(cinfo, st + 2, (v & 1));
 661           else {                        /* newly nonzero coef */
 662             arith_encode(cinfo, st + 1, 1);
 663             arith_encode(cinfo, entropy->fixed_bin, 1);
 664           }
 665           break;
 666         }
 667       }
 668       arith_encode(cinfo, st + 1, 0); st += 3; k++;
 669     }
 670   }
 671   /* Encode EOB decision only if k <= cinfo->Se */
 672   if (k <= cinfo->Se) {
 673     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 674     arith_encode(cinfo, st, 1);
 675   }
 676
 677   return TRUE;
 678 }
 679
 680
 681 /*
 682  * Encode and output one MCU's worth of arithmetic-compressed coefficients.
 683  */
 684
 685 METHODDEF(boolean)
 686 encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 687 {
 688   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 689   jpeg_component_info * compptr;
 690   JBLOCKROW block;
 691   unsigned char *st;
 692   int blkn, ci, tbl, k, ke;
 693   int v, v2, m;
 694   const int * natural_order;
 695
 696   /* Emit restart marker if needed */
 697   if (cinfo->restart_interval) {
 698     if (entropy->restarts_to_go == 0) {
 699       emit_restart(cinfo, entropy->next_restart_num);
 700       entropy->restarts_to_go = cinfo->restart_interval;
 701       entropy->next_restart_num++;
 702       entropy->next_restart_num &= 7;
 703     }
 704     entropy->restarts_to_go--;
 705   }
 706
 707   natural_order = cinfo->natural_order;
 708
 709   /* Encode the MCU data blocks */
 710   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 711     block = MCU_data[blkn];
 712     ci = cinfo->MCU_membership[blkn];
 713     compptr = cinfo->cur_comp_info[ci];
 714
 715     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
 716
 717     tbl = compptr->dc_tbl_no;
 718
 719     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
 720     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
 721
 722     /* Figure F.4: Encode_DC_DIFF */
 723     if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
 724       arith_encode(cinfo, st, 0);
 725       entropy->dc_context[ci] = 0;      /* zero diff category */
 726     } else {
 727       entropy->last_dc_val[ci] = (*block)[0];
 728       arith_encode(cinfo, st, 1);
 729       /* Figure F.6: Encoding nonzero value v */
 730       /* Figure F.7: Encoding the sign of v */
 731       if (v > 0) {
 732         arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
 733         st += 2;                        /* Table F.4: SP = S0 + 2 */
 734         entropy->dc_context[ci] = 4;    /* small positive diff category */
 735       } else {
 736         v = -v;
 737         arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
 738         st += 3;                        /* Table F.4: SN = S0 + 3 */
 739         entropy->dc_context[ci] = 8;    /* small negative diff category */
 740       }
 741       /* Figure F.8: Encoding the magnitude category of v */
 742       m = 0;
 743       if (v -= 1) {
 744         arith_encode(cinfo, st, 1);
 745         m = 1;
 746         v2 = v;
 747         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
 748         while (v2 >>= 1) {
 749           arith_encode(cinfo, st, 1);
 750           m <<= 1;
 751           st += 1;
 752         }
 753       }
 754       arith_encode(cinfo, st, 0);
 755       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
 756       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
 757         entropy->dc_context[ci] = 0;    /* zero diff category */
 758       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
 759         entropy->dc_context[ci] += 8;   /* large diff category */
 760       /* Figure F.9: Encoding the magnitude bit pattern of v */
 761       st += 14;
 762       while (m >>= 1)
 763         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 764     }
 765
 766     /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
 767
 768     tbl = compptr->ac_tbl_no;
 769
 770     /* Establish EOB (end-of-block) index */
 771     for (ke = cinfo->lim_Se; ke > 0; ke--)
 772       if ((*block)[natural_order[ke]]) break;
 773
 774     /* Figure F.5: Encode_AC_Coefficients */
 775     for (k = 1; k <= ke; k++) {
 776       st = entropy->ac_stats[tbl] + 3 * (k - 1);
 777       arith_encode(cinfo, st, 0);       /* EOB decision */
 778       while ((v = (*block)[natural_order[k]]) == 0) {
 779         arith_encode(cinfo, st + 1, 0); st += 3; k++;
 780       }
 781       arith_encode(cinfo, st + 1, 1);
 782       /* Figure F.6: Encoding nonzero value v */
 783       /* Figure F.7: Encoding the sign of v */
 784       if (v > 0) {
 785         arith_encode(cinfo, entropy->fixed_bin, 0);
 786       } else {
 787         v = -v;
 788         arith_encode(cinfo, entropy->fixed_bin, 1);
 789       }
 790       st += 2;
 791       /* Figure F.8: Encoding the magnitude category of v */
 792       m = 0;
 793       if (v -= 1) {
 794         arith_encode(cinfo, st, 1);
 795         m = 1;
 796         v2 = v;
 797         if (v2 >>= 1) {
 798           arith_encode(cinfo, st, 1);
 799           m <<= 1;
 800           st = entropy->ac_stats[tbl] +
 801                (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 802           while (v2 >>= 1) {
 803             arith_encode(cinfo, st, 1);
 804             m <<= 1;
 805             st += 1;
 806           }
 807         }
 808       }
 809       arith_encode(cinfo, st, 0);
 810       /* Figure F.9: Encoding the magnitude bit pattern of v */
 811       st += 14;
 812       while (m >>= 1)
 813         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 814     }
 815     /* Encode EOB decision only if k <= cinfo->lim_Se */
 816     if (k <= cinfo->lim_Se) {
 817       st = entropy->ac_stats[tbl] + 3 * (k - 1);
 818       arith_encode(cinfo, st, 1);
 819     }
 820   }
 821
 822   return TRUE;
 823 }
 824
 825
 826 /*
 827  * Initialize for an arithmetic-compressed scan.
 828  */
 829
 830 METHODDEF(void)
 831 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
 832 {
 833   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 834   int ci, tbl;
 835   jpeg_component_info * compptr;
 836
 837   if (gather_statistics)
 838     /* Make sure to avoid that in the master control logic!
 839      * We are fully adaptive here and need no extra
 840      * statistics gathering pass!
 841      */
 842     ERREXIT(cinfo, JERR_NOT_COMPILED);
 843
 844   /* We assume jcmaster.c already validated the progressive scan parameters. */
 845
 846   /* Select execution routines */
 847   if (cinfo->progressive_mode) {
 848     if (cinfo->Ah == 0) {
 849       if (cinfo->Ss == 0)
 850         entropy->pub.encode_mcu = encode_mcu_DC_first;
 851       else
 852         entropy->pub.encode_mcu = encode_mcu_AC_first;
 853     } else {
 854       if (cinfo->Ss == 0)
 855         entropy->pub.encode_mcu = encode_mcu_DC_refine;
 856       else
 857         entropy->pub.encode_mcu = encode_mcu_AC_refine;
 858     }
 859   } else
 860     entropy->pub.encode_mcu = encode_mcu;
 861
 862   /* Allocate & initialize requested statistics areas */
 863   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 864     compptr = cinfo->cur_comp_info[ci];
 865     /* DC needs no table for refinement scan */
 866     if (cinfo->Ss == 0 && cinfo->Ah == 0) {
 867       tbl = compptr->dc_tbl_no;
 868       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 869         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 870       if (entropy->dc_stats[tbl] == NULL)
 871         entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 872           ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
 873       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
 874       /* Initialize DC predictions to 0 */
 875       entropy->last_dc_val[ci] = 0;
 876       entropy->dc_context[ci] = 0;
 877     }
 878     /* AC needs no table when not present */
 879     if (cinfo->Se) {
 880       tbl = compptr->ac_tbl_no;
 881       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 882         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 883       if (entropy->ac_stats[tbl] == NULL)
 884         entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 885           ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
 886       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
 887 #ifdef CALCULATE_SPECTRAL_CONDITIONING
 888       if (cinfo->progressive_mode)
 889         /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
 890         cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
 891 #endif
 892     }
 893   }
 894
 895   /* Initialize arithmetic encoding variables */
 896   entropy->c = 0;
 897   entropy->a = 0x10000L;
 898   entropy->sc = 0;
 899   entropy->zc = 0;
 900   entropy->ct = 11;
 901   entropy->buffer = -1;  /* empty */
 902
 903   /* Initialize restart stuff */
 904   entropy->restarts_to_go = cinfo->restart_interval;
 905   entropy->next_restart_num = 0;
 906 }
 907
 908
 909 /*
 910  * Module initialization routine for arithmetic entropy encoding.
 911  */
 912
 913 GLOBAL(void)
 914 jinit_arith_encoder (j_compress_ptr cinfo)
 915 {
 916   arith_entropy_ptr entropy;
 917   int i;
 918
 919   entropy = (arith_entropy_ptr)
 920     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 921                                 SIZEOF(arith_entropy_encoder));
 922   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
 923   entropy->pub.start_pass = start_pass;
 924   entropy->pub.finish_pass = finish_pass;
 925
 926   /* Mark tables unallocated */
 927   for (i = 0; i < NUM_ARITH_TBLS; i++) {
 928     entropy->dc_stats[i] = NULL;
 929     entropy->ac_stats[i] = NULL;
 930   }
 931
 932   /* Initialize index for fixed probability estimation */
 933   entropy->fixed_bin[0] = 113;
 934 }