jcarith.c

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