jpeg/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->progressive_mode == 0 || (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->progressive_mode == 0 || 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
 461   /* Emit restart marker if needed */
 462   if (cinfo->restart_interval) {
 463     if (entropy->restarts_to_go == 0) {
 464       emit_restart(cinfo, entropy->next_restart_num);
 465       entropy->restarts_to_go = cinfo->restart_interval;
 466       entropy->next_restart_num++;
 467       entropy->next_restart_num &= 7;
 468     }
 469     entropy->restarts_to_go--;
 470   }
 471
 472   /* Encode the MCU data block */
 473   block = MCU_data[0];
 474   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
 475
 476   /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
 477
 478   /* Establish EOB (end-of-block) index */
 479   for (ke = cinfo->Se; ke > 0; ke--)
 480     /* We must apply the point transform by Al.  For AC coefficients this
 481      * is an integer division with rounding towards 0.  To do this portably
 482      * in C, we shift after obtaining the absolute value.
 483      */
 484     if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
 485       if (v >>= cinfo->Al) break;
 486     } else {
 487       v = -v;
 488       if (v >>= cinfo->Al) break;
 489     }
 490
 491   /* Figure F.5: Encode_AC_Coefficients */
 492   for (k = cinfo->Ss; k <= ke; k++) {
 493     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 494     arith_encode(cinfo, st, 0);         /* EOB decision */
 495     for (;;) {
 496       if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
 497         if (v >>= cinfo->Al) {
 498           arith_encode(cinfo, st + 1, 1);
 499           arith_encode(cinfo, entropy->fixed_bin, 0);
 500           break;
 501         }
 502       } else {
 503         v = -v;
 504         if (v >>= cinfo->Al) {
 505           arith_encode(cinfo, st + 1, 1);
 506           arith_encode(cinfo, entropy->fixed_bin, 1);
 507           break;
 508         }
 509       }
 510       arith_encode(cinfo, st + 1, 0); st += 3; k++;
 511     }
 512     st += 2;
 513     /* Figure F.8: Encoding the magnitude category of v */
 514     m = 0;
 515     if (v -= 1) {
 516       arith_encode(cinfo, st, 1);
 517       m = 1;
 518       v2 = v;
 519       if (v2 >>= 1) {
 520         arith_encode(cinfo, st, 1);
 521         m <<= 1;
 522         st = entropy->ac_stats[tbl] +
 523              (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 524         while (v2 >>= 1) {
 525           arith_encode(cinfo, st, 1);
 526           m <<= 1;
 527           st += 1;
 528         }
 529       }
 530     }
 531     arith_encode(cinfo, st, 0);
 532     /* Figure F.9: Encoding the magnitude bit pattern of v */
 533     st += 14;
 534     while (m >>= 1)
 535       arith_encode(cinfo, st, (m & v) ? 1 : 0);
 536   }
 537   /* Encode EOB decision only if k <= cinfo->Se */
 538   if (k <= cinfo->Se) {
 539     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 540     arith_encode(cinfo, st, 1);
 541   }
 542
 543   return TRUE;
 544 }
 545
 546
 547 /*
 548  * MCU encoding for DC successive approximation refinement scan.
 549  */
 550
 551 METHODDEF(boolean)
 552 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 553 {
 554   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 555   unsigned char *st;
 556   int Al, blkn;
 557
 558   /* Emit restart marker if needed */
 559   if (cinfo->restart_interval) {
 560     if (entropy->restarts_to_go == 0) {
 561       emit_restart(cinfo, entropy->next_restart_num);
 562       entropy->restarts_to_go = cinfo->restart_interval;
 563       entropy->next_restart_num++;
 564       entropy->next_restart_num &= 7;
 565     }
 566     entropy->restarts_to_go--;
 567   }
 568
 569   st = entropy->fixed_bin;      /* use fixed probability estimation */
 570   Al = cinfo->Al;
 571
 572   /* Encode the MCU data blocks */
 573   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 574     /* We simply emit the Al'th bit of the DC coefficient value. */
 575     arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
 576   }
 577
 578   return TRUE;
 579 }
 580
 581
 582 /*
 583  * MCU encoding for AC successive approximation refinement scan.
 584  */
 585
 586 METHODDEF(boolean)
 587 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 588 {
 589   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 590   JBLOCKROW block;
 591   unsigned char *st;
 592   int tbl, k, ke, kex;
 593   int v;
 594
 595   /* Emit restart marker if needed */
 596   if (cinfo->restart_interval) {
 597     if (entropy->restarts_to_go == 0) {
 598       emit_restart(cinfo, entropy->next_restart_num);
 599       entropy->restarts_to_go = cinfo->restart_interval;
 600       entropy->next_restart_num++;
 601       entropy->next_restart_num &= 7;
 602     }
 603     entropy->restarts_to_go--;
 604   }
 605
 606   /* Encode the MCU data block */
 607   block = MCU_data[0];
 608   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
 609
 610   /* Section G.1.3.3: Encoding of AC coefficients */
 611
 612   /* Establish EOB (end-of-block) index */
 613   for (ke = cinfo->Se; ke > 0; ke--)
 614     /* We must apply the point transform by Al.  For AC coefficients this
 615      * is an integer division with rounding towards 0.  To do this portably
 616      * in C, we shift after obtaining the absolute value.
 617      */
 618     if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
 619       if (v >>= cinfo->Al) break;
 620     } else {
 621       v = -v;
 622       if (v >>= cinfo->Al) break;
 623     }
 624
 625   /* Establish EOBx (previous stage end-of-block) index */
 626   for (kex = ke; kex > 0; kex--)
 627     if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) {
 628       if (v >>= cinfo->Ah) break;
 629     } else {
 630       v = -v;
 631       if (v >>= cinfo->Ah) break;
 632     }
 633
 634   /* Figure G.10: Encode_AC_Coefficients_SA */
 635   for (k = cinfo->Ss; k <= ke; k++) {
 636     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 637     if (k > kex)
 638       arith_encode(cinfo, st, 0);       /* EOB decision */
 639     for (;;) {
 640       if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
 641         if (v >>= cinfo->Al) {
 642           if (v >> 1)                   /* previously nonzero coef */
 643             arith_encode(cinfo, st + 2, (v & 1));
 644           else {                        /* newly nonzero coef */
 645             arith_encode(cinfo, st + 1, 1);
 646             arith_encode(cinfo, entropy->fixed_bin, 0);
 647           }
 648           break;
 649         }
 650       } else {
 651         v = -v;
 652         if (v >>= cinfo->Al) {
 653           if (v >> 1)                   /* previously nonzero coef */
 654             arith_encode(cinfo, st + 2, (v & 1));
 655           else {                        /* newly nonzero coef */
 656             arith_encode(cinfo, st + 1, 1);
 657             arith_encode(cinfo, entropy->fixed_bin, 1);
 658           }
 659           break;
 660         }
 661       }
 662       arith_encode(cinfo, st + 1, 0); st += 3; k++;
 663     }
 664   }
 665   /* Encode EOB decision only if k <= cinfo->Se */
 666   if (k <= cinfo->Se) {
 667     st = entropy->ac_stats[tbl] + 3 * (k - 1);
 668     arith_encode(cinfo, st, 1);
 669   }
 670
 671   return TRUE;
 672 }
 673
 674
 675 /*
 676  * Encode and output one MCU's worth of arithmetic-compressed coefficients.
 677  */
 678
 679 METHODDEF(boolean)
 680 encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 681 {
 682   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 683   jpeg_component_info * compptr;
 684   JBLOCKROW block;
 685   unsigned char *st;
 686   int blkn, ci, tbl, k, ke;
 687   int v, v2, m;
 688
 689   /* Emit restart marker if needed */
 690   if (cinfo->restart_interval) {
 691     if (entropy->restarts_to_go == 0) {
 692       emit_restart(cinfo, entropy->next_restart_num);
 693       entropy->restarts_to_go = cinfo->restart_interval;
 694       entropy->next_restart_num++;
 695       entropy->next_restart_num &= 7;
 696     }
 697     entropy->restarts_to_go--;
 698   }
 699
 700   /* Encode the MCU data blocks */
 701   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 702     block = MCU_data[blkn];
 703     ci = cinfo->MCU_membership[blkn];
 704     compptr = cinfo->cur_comp_info[ci];
 705
 706     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
 707
 708     tbl = compptr->dc_tbl_no;
 709
 710     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
 711     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
 712
 713     /* Figure F.4: Encode_DC_DIFF */
 714     if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
 715       arith_encode(cinfo, st, 0);
 716       entropy->dc_context[ci] = 0;      /* zero diff category */
 717     } else {
 718       entropy->last_dc_val[ci] = (*block)[0];
 719       arith_encode(cinfo, st, 1);
 720       /* Figure F.6: Encoding nonzero value v */
 721       /* Figure F.7: Encoding the sign of v */
 722       if (v > 0) {
 723         arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
 724         st += 2;                        /* Table F.4: SP = S0 + 2 */
 725         entropy->dc_context[ci] = 4;    /* small positive diff category */
 726       } else {
 727         v = -v;
 728         arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
 729         st += 3;                        /* Table F.4: SN = S0 + 3 */
 730         entropy->dc_context[ci] = 8;    /* small negative diff category */
 731       }
 732       /* Figure F.8: Encoding the magnitude category of v */
 733       m = 0;
 734       if (v -= 1) {
 735         arith_encode(cinfo, st, 1);
 736         m = 1;
 737         v2 = v;
 738         st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
 739         while (v2 >>= 1) {
 740           arith_encode(cinfo, st, 1);
 741           m <<= 1;
 742           st += 1;
 743         }
 744       }
 745       arith_encode(cinfo, st, 0);
 746       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
 747       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
 748         entropy->dc_context[ci] = 0;    /* zero diff category */
 749       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
 750         entropy->dc_context[ci] += 8;   /* large diff category */
 751       /* Figure F.9: Encoding the magnitude bit pattern of v */
 752       st += 14;
 753       while (m >>= 1)
 754         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 755     }
 756
 757     /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
 758
 759     tbl = compptr->ac_tbl_no;
 760
 761     /* Establish EOB (end-of-block) index */
 762     for (ke = DCTSIZE2 - 1; ke > 0; ke--)
 763       if ((*block)[jpeg_natural_order[ke]]) break;
 764
 765     /* Figure F.5: Encode_AC_Coefficients */
 766     for (k = 1; k <= ke; k++) {
 767       st = entropy->ac_stats[tbl] + 3 * (k - 1);
 768       arith_encode(cinfo, st, 0);       /* EOB decision */
 769       while ((v = (*block)[jpeg_natural_order[k]]) == 0) {
 770         arith_encode(cinfo, st + 1, 0); st += 3; k++;
 771       }
 772       arith_encode(cinfo, st + 1, 1);
 773       /* Figure F.6: Encoding nonzero value v */
 774       /* Figure F.7: Encoding the sign of v */
 775       if (v > 0) {
 776         arith_encode(cinfo, entropy->fixed_bin, 0);
 777       } else {
 778         v = -v;
 779         arith_encode(cinfo, entropy->fixed_bin, 1);
 780       }
 781       st += 2;
 782       /* Figure F.8: Encoding the magnitude category of v */
 783       m = 0;
 784       if (v -= 1) {
 785         arith_encode(cinfo, st, 1);
 786         m = 1;
 787         v2 = v;
 788         if (v2 >>= 1) {
 789           arith_encode(cinfo, st, 1);
 790           m <<= 1;
 791           st = entropy->ac_stats[tbl] +
 792                (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
 793           while (v2 >>= 1) {
 794             arith_encode(cinfo, st, 1);
 795             m <<= 1;
 796             st += 1;
 797           }
 798         }
 799       }
 800       arith_encode(cinfo, st, 0);
 801       /* Figure F.9: Encoding the magnitude bit pattern of v */
 802       st += 14;
 803       while (m >>= 1)
 804         arith_encode(cinfo, st, (m & v) ? 1 : 0);
 805     }
 806     /* Encode EOB decision only if k <= DCTSIZE2 - 1 */
 807     if (k <= DCTSIZE2 - 1) {
 808       st = entropy->ac_stats[tbl] + 3 * (k - 1);
 809       arith_encode(cinfo, st, 1);
 810     }
 811   }
 812
 813   return TRUE;
 814 }
 815
 816
 817 /*
 818  * Initialize for an arithmetic-compressed scan.
 819  */
 820
 821 METHODDEF(void)
 822 start_pass (j_compress_ptr cinfo, boolean gather_statistics)
 823 {
 824   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
 825   int ci, tbl;
 826   jpeg_component_info * compptr;
 827
 828   if (gather_statistics)
 829     /* Make sure to avoid that in the master control logic!
 830      * We are fully adaptive here and need no extra
 831      * statistics gathering pass!
 832      */
 833     ERREXIT(cinfo, JERR_NOT_COMPILED);
 834
 835   /* We assume jcmaster.c already validated the progressive scan parameters. */
 836
 837   /* Select execution routines */
 838   if (cinfo->progressive_mode) {
 839     if (cinfo->Ah == 0) {
 840       if (cinfo->Ss == 0)
 841         entropy->pub.encode_mcu = encode_mcu_DC_first;
 842       else
 843         entropy->pub.encode_mcu = encode_mcu_AC_first;
 844     } else {
 845       if (cinfo->Ss == 0)
 846         entropy->pub.encode_mcu = encode_mcu_DC_refine;
 847       else
 848         entropy->pub.encode_mcu = encode_mcu_AC_refine;
 849     }
 850   } else
 851     entropy->pub.encode_mcu = encode_mcu;
 852
 853   /* Allocate & initialize requested statistics areas */
 854   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 855     compptr = cinfo->cur_comp_info[ci];
 856     /* DC needs no table for refinement scan */
 857     if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
 858       tbl = compptr->dc_tbl_no;
 859       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 860         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 861       if (entropy->dc_stats[tbl] == NULL)
 862         entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 863           ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
 864       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
 865       /* Initialize DC predictions to 0 */
 866       entropy->last_dc_val[ci] = 0;
 867       entropy->dc_context[ci] = 0;
 868     }
 869     /* AC needs no table when not present */
 870     if (cinfo->progressive_mode == 0 || cinfo->Se) {
 871       tbl = compptr->ac_tbl_no;
 872       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
 873         ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
 874       if (entropy->ac_stats[tbl] == NULL)
 875         entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
 876           ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
 877       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
 878 #ifdef CALCULATE_SPECTRAL_CONDITIONING
 879       if (cinfo->progressive_mode)
 880         /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
 881         cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
 882 #endif
 883     }
 884   }
 885
 886   /* Initialize arithmetic encoding variables */
 887   entropy->c = 0;
 888   entropy->a = 0x10000L;
 889   entropy->sc = 0;
 890   entropy->zc = 0;
 891   entropy->ct = 11;
 892   entropy->buffer = -1;  /* empty */
 893
 894   /* Initialize restart stuff */
 895   entropy->restarts_to_go = cinfo->restart_interval;
 896   entropy->next_restart_num = 0;
 897 }
 898
 899
 900 /*
 901  * Module initialization routine for arithmetic entropy encoding.
 902  */
 903
 904 GLOBAL(void)
 905 jinit_arith_encoder (j_compress_ptr cinfo)
 906 {
 907   arith_entropy_ptr entropy;
 908   int i;
 909
 910   entropy = (arith_entropy_ptr)
 911     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 912                                 SIZEOF(arith_entropy_encoder));
 913   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
 914   entropy->pub.start_pass = start_pass;
 915   entropy->pub.finish_pass = finish_pass;
 916
 917   /* Mark tables unallocated */
 918   for (i = 0; i < NUM_ARITH_TBLS; i++) {
 919     entropy->dc_stats[i] = NULL;
 920     entropy->ac_stats[i] = NULL;
 921   }
 922
 923   /* Initialize index for fixed probability estimation */
 924   entropy->fixed_bin[0] = 113;
 925 }