workbench/libs/jpeg/jcarith.c

   1 /*
   2  * jcarith.c
   3  *
   4  * Developed 1997-2012 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   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   ke = cinfo->Se;
 483   do {
 484     /* We must apply the point transform by Al.  For AC coefficients this
 485      * is an integer division with rounding towards 0.  To do this portably
 486      * in C, we shift after obtaining the absolute value.
 487      */
 488     if ((v = (*block)[natural_order[ke]]) >= 0) {
 489       if (v >>= cinfo->Al) break;
 490     } else {
 491       v = -v;
 492       if (v >>= cinfo->Al) break;
 493     }
 494   } while (--ke);
 495
 496   /* Figure F.5: Encode_AC_Coefficients */
 497   for (k = cinfo->Ss - 1; k < ke;) {
 498     st = entropy->ac_stats[tbl] + 3 * k;
 499     arith_encode(cinfo, st, 0);         /* EOB decision */
 500     for (;;) {
 501       if ((v = (*block)[natural_order[++k]]) >= 0) {
 502         if (v >>= cinfo->Al) {
 503           arith_encode(cinfo, st + 1, 1);
 504           arith_encode(cinfo, entropy->fixed_bin, 0);
 505           break;
 506         }
 507       } else {
 508         v = -v;
 509         if (v >>= cinfo->Al) {
 510           arith_encode(cinfo, st + 1, 1);
 511           arith_encode(cinfo, entropy->fixed_bin, 1);
 512           break;
 513         }
 514       }
 515       arith_encode(cinfo, st + 1, 0);
 516       st += 3;
 517     }
 518     st += 2;
 519     /* Figure F.8: Encoding the magnitude category of v */
 520     m = 0;
 521     if (v -= 1) {
 522       arith_encode(cinfo, st, 1);
 523       m = 1;
 524       v2 = v;
 525       if (v2 >>= 1) {
 526         arith_encode(cinfo, st, 1);
 527         m <<= 1;
 528         st = entropy->ac_stats[tbl] +
 529              (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 530         while (v2 >>= 1) {
 531           arith_encode(cinfo, st, 1);
 532           m <<= 1;
 533           st += 1;
 534         }
 535       }
 536     }
 537     arith_encode(cinfo, st, 0);
 538     /* Figure F.9: Encoding the magnitude bit pattern of v */
 539     st += 14;
 540     while (m >>= 1)
 541       arith_encode(cinfo, st, (m & v) ? 1 : 0);
 542   }
 543   /* Encode EOB decision only if k < cinfo->Se */
 544   if (k < cinfo->Se) {
 545     st = entropy->ac_stats[tbl] + 3 * k;
 546     arith_encode(cinfo, st, 1);
 547   }
 548
 549   return TRUE;
 550 }
 551
 552
 553 /*
 554  * MCU encoding for DC successive approximation refinement scan.
 555  */
 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   JBLOCKROW block;
 597   unsigned char *st;
 598   int tbl, k, ke, kex;
 599   int v;
 600   const int * natural_order;
 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   jpeg_component_info * compptr;
 696   JBLOCKROW block;
 697   unsigned char *st;
 698   int blkn, ci, tbl, k, ke;
 699   int v, v2, m;
 700   const int * natural_order;
 701
 702   /* Emit restart marker if needed */
 703   if (cinfo->restart_interval) {
 704     if (entropy->restarts_to_go == 0) {
 705       emit_restart(cinfo, entropy->next_restart_num);
 706       entropy->restarts_to_go = cinfo->restart_interval;
 707       entropy->next_restart_num++;
 708       entropy->next_restart_num &= 7;
 709     }
 710     entropy->restarts_to_go--;
 711   }
 712
 713   natural_order = cinfo->natural_order;
 714
 715   /* Encode the MCU data blocks */
 716   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 717     block = MCU_data[blkn];
 718     ci = cinfo->MCU_membership[blkn];
 719     compptr = cinfo->cur_comp_info[ci];
 720
 721     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
 722
 723     tbl = compptr->dc_tbl_no;
 724
 725     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
 726     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
 727
 728     /* Figure F.4: Encode_DC_DIFF */
 729     if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
 730       arith_encode(cinfo, st, 0);
 731       entropy->dc_context[ci] = 0;      /* zero diff category */
 732     } else {
 733       entropy->last_dc_val[ci] = (*block)[0];
 734       arith_encode(cinfo, st, 1);
 735       /* Figure F.6: Encoding nonzero value v */
 736       /* Figure F.7: Encoding the sign of v */
 737       if (v > 0) {
 738         arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
 739         st += 2;                        /* Table F.4: SP = S0 + 2 */
 740         entropy->dc_context[ci] = 4;    /* small positive diff category */
 741       } else {
 742         v = -v;
 743         arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
 744         st += 3;                        /* Table F.4: SN = S0 + 3 */
 745         entropy->dc_context[ci] = 8;    /* small negative diff category */
 746       }
 747       /* Figure F.8: Encoding the magnitude category of v */
 748       m = 0;
 749       if (v -= 1) {
 750         arith_encode(cinfo, st, 1);
 751         m = 1;
 752         v2 = v;
 753         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
 754         while (v2 >>= 1) {
 755           arith_encode(cinfo, st, 1);
 756           m <<= 1;
 757           st += 1;
 758         }
 759       }
 760       arith_encode(cinfo, st, 0);
 761       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
 762       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
 763         entropy->dc_context[ci] = 0;    /* zero diff category */
 764       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
 765         entropy->dc_context[ci] += 8;   /* large diff category */
 766       /* Figure F.9: Encoding the magnitude bit pattern of v */
 767       st += 14;
 768       while (m >>= 1)
 769         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 770     }
 771
 772     /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
 773
 774     if ((ke = cinfo->lim_Se) == 0) continue;
 775     tbl = compptr->ac_tbl_no;
 776
 777     /* Establish EOB (end-of-block) index */
 778     do {
 779       if ((*block)[natural_order[ke]]) break;
 780     } while (--ke);
 781
 782     /* Figure F.5: Encode_AC_Coefficients */
 783     for (k = 0; k < ke;) {
 784       st = entropy->ac_stats[tbl] + 3 * k;
 785       arith_encode(cinfo, st, 0);       /* EOB decision */
 786       while ((v = (*block)[natural_order[++k]]) == 0) {
 787         arith_encode(cinfo, st + 1, 0);
 788         st += 3;
 789       }
 790       arith_encode(cinfo, st + 1, 1);
 791       /* Figure F.6: Encoding nonzero value v */
 792       /* Figure F.7: Encoding the sign of v */
 793       if (v > 0) {
 794         arith_encode(cinfo, entropy->fixed_bin, 0);
 795       } else {
 796         v = -v;
 797         arith_encode(cinfo, entropy->fixed_bin, 1);
 798       }
 799       st += 2;
 800       /* Figure F.8: Encoding the magnitude category of v */
 801       m = 0;
 802       if (v -= 1) {
 803         arith_encode(cinfo, st, 1);
 804         m = 1;
 805         v2 = v;
 806         if (v2 >>= 1) {
 807           arith_encode(cinfo, st, 1);
 808           m <<= 1;
 809           st = entropy->ac_stats[tbl] +
 810                (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 811           while (v2 >>= 1) {
 812             arith_encode(cinfo, st, 1);
 813             m <<= 1;
 814             st += 1;
 815           }
 816         }
 817       }
 818       arith_encode(cinfo, st, 0);
 819       /* Figure F.9: Encoding the magnitude bit pattern of v */
 820       st += 14;
 821       while (m >>= 1)
 822         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 823     }
 824     /* Encode EOB decision only if k < cinfo->lim_Se */
 825     if (k < cinfo->lim_Se) {
 826       st = entropy->ac_stats[tbl] + 3 * k;
 827       arith_encode(cinfo, st, 1);
 828     }
 829   }
 830
 831   return TRUE;
 832 }
 833
 834
 835 /*
 836  * Initialize for an arithmetic-compressed scan.
 837  */
 838
 839 METHODDEF(void)
 840 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
 841 {
 842   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 843   int ci, tbl;
 844   jpeg_component_info * compptr;
 845
 846   if (gather_statistics)
 847     /* Make sure to avoid that in the master control logic!
 848      * We are fully adaptive here and need no extra
 849      * statistics gathering pass!
 850      */
 851     ERREXIT(cinfo, JERR_NOT_COMPILED);
 852
 853   /* We assume jcmaster.c already validated the progressive scan parameters. */
 854
 855   /* Select execution routines */
 856   if (cinfo->progressive_mode) {
 857     if (cinfo->Ah == 0) {
 858       if (cinfo->Ss == 0)
 859         entropy->pub.encode_mcu = encode_mcu_DC_first;
 860       else
 861         entropy->pub.encode_mcu = encode_mcu_AC_first;
 862     } else {
 863       if (cinfo->Ss == 0)
 864         entropy->pub.encode_mcu = encode_mcu_DC_refine;
 865       else
 866         entropy->pub.encode_mcu = encode_mcu_AC_refine;
 867     }
 868   } else
 869     entropy->pub.encode_mcu = encode_mcu;
 870
 871   /* Allocate & initialize requested statistics areas */
 872   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 873     compptr = cinfo->cur_comp_info[ci];
 874     /* DC needs no table for refinement scan */
 875     if (cinfo->Ss == 0 && cinfo->Ah == 0) {
 876       tbl = compptr->dc_tbl_no;
 877       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 878         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 879       if (entropy->dc_stats[tbl] == NULL)
 880         entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 881           ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
 882       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
 883       /* Initialize DC predictions to 0 */
 884       entropy->last_dc_val[ci] = 0;
 885       entropy->dc_context[ci] = 0;
 886     }
 887     /* AC needs no table when not present */
 888     if (cinfo->Se) {
 889       tbl = compptr->ac_tbl_no;
 890       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 891         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 892       if (entropy->ac_stats[tbl] == NULL)
 893         entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 894           ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
 895       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
 896 #ifdef CALCULATE_SPECTRAL_CONDITIONING
 897       if (cinfo->progressive_mode)
 898         /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
 899         cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
 900 #endif
 901     }
 902   }
 903
 904   /* Initialize arithmetic encoding variables */
 905   entropy->c = 0;
 906   entropy->a = 0x10000L;
 907   entropy->sc = 0;
 908   entropy->zc = 0;
 909   entropy->ct = 11;
 910   entropy->buffer = -1;  /* empty */
 911
 912   /* Initialize restart stuff */
 913   entropy->restarts_to_go = cinfo->restart_interval;
 914   entropy->next_restart_num = 0;
 915 }
 916
 917
 918 /*
 919  * Module initialization routine for arithmetic entropy encoding.
 920  */
 921
 922 GLOBAL(void)
 923 jinit_arith_encoder (j_compress_ptr cinfo)
 924 {
 925   arith_entropy_ptr entropy;
 926   int i;
 927
 928   entropy = (arith_entropy_ptr)
 929     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 930                                 SIZEOF(arith_entropy_encoder));
 931   cinfo->entropy = &entropy->pub;
 932   entropy->pub.start_pass = start_pass;
 933   entropy->pub.finish_pass = finish_pass;
 934
 935   /* Mark tables unallocated */
 936   for (i = 0; i < NUM_ARITH_TBLS; i++) {
 937     entropy->dc_stats[i] = NULL;
 938     entropy->ac_stats[i] = NULL;
 939   }
 940
 941   /* Initialize index for fixed probability estimation */
 942   entropy->fixed_bin[0] = 113;
 943 }