/*

 * jcarith.c

 *

 * This file was part of the Independent JPEG Group's software:

 * Developed 1997-2009 by Guido Vollbeding.

 * libjpeg-turbo Modifications:

 * Copyright (C) 2015, 2018, D. R. Commander.

 * For conditions of distribution and use, see the accompanying README.ijg

 * file.

 *

 * This file contains portable arithmetic entropy encoding routines for JPEG

 * (implementing Recommendation ITU-T T.81 | ISO/IEC 10918-1).

 *

 * Both sequential and progressive modes are supported in this single module.

 *

 * Suspension is not currently supported in this module.

 *

 * NOTE: All referenced figures are from

 * Recommendation ITU-T T.81 (1992) | ISO/IEC 10918-1:1994.

 */

#define JPEG_INTERNALS

#include "jinclude.h"

#include "jpeglib.h"

/* Expanded entropy encoder object for arithmetic encoding. */

typedef struct {

  struct jpeg_entropy_encoder pub; /* public fields */

  JLONG c; /* C register, base of coding interval, layout as in sec. D.1.3 */

  JLONG a;               /* A register, normalized size of coding interval */

  JLONG sc;        /* counter for stacked 0xFF values which might overflow */

  JLONG zc;          /* counter for pending 0x00 output values which might *

                          * be discarded at the end ("Pacman" termination) */

  int ct;  /* bit shift counter, determines when next byte will be written */

  int buffer;                /* buffer for most recent output byte != 0xFF */

  int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */

  int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */

  unsigned int restarts_to_go;  /* MCUs left in this restart interval */

  int next_restart_num;         /* next restart number to write (0-7) */

  /* Pointers to statistics areas (these workspaces have image lifespan) */

  unsigned char *dc_stats[NUM_ARITH_TBLS];

  unsigned char *ac_stats[NUM_ARITH_TBLS];

  /* Statistics bin for coding with fixed probability 0.5 */

  unsigned char fixed_bin[4];

} arith_entropy_encoder;

typedef arith_entropy_encoder *arith_entropy_ptr;

/* The following two definitions specify the allocation chunk size

 * for the statistics area.

 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least

 * 49 statistics bins for DC, and 245 statistics bins for AC coding.

 *

 * We use a compact representation with 1 byte per statistics bin,

 * thus the numbers directly represent byte sizes.

 * This 1 byte per statistics bin contains the meaning of the MPS

 * (more probable symbol) in the highest bit (mask 0x80), and the

 * index into the probability estimation state machine table

 * in the lower bits (mask 0x7F).

 */

#define DC_STAT_BINS  64

#define AC_STAT_BINS  256

/* NOTE: Uncomment the following #define if you want to use the

 * given formula for calculating the AC conditioning parameter Kx

 * for spectral selection progressive coding in section G.1.3.2

 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).

 * Although the spec and P&M authors claim that this "has proven

 * to give good results for 8 bit precision samples", I'm not

 * convinced yet that this is really beneficial.

 * Early tests gave only very marginal compression enhancements

 * (a few - around 5 or so - bytes even for very large files),

 * which would turn out rather negative if we'd suppress the

 * DAC (Define Arithmetic Conditioning) marker segments for

 * the default parameters in the future.

 * Note that currently the marker writing module emits 12-byte

 * DAC segments for a full-component scan in a color image.

 * This is not worth worrying about IMHO. However, since the

 * spec defines the default values to be used if the tables

 * are omitted (unlike Huffman tables, which are required

 * anyway), one might optimize this behaviour in the future,

 * and then it would be disadvantageous to use custom tables if

 * they don't provide sufficient gain to exceed the DAC size.

 *

 * On the other hand, I'd consider it as a reasonable result

 * that the conditioning has no significant influence on the

 * compression performance. This means that the basic

 * statistical model is already rather stable.

 *

 * Thus, at the moment, we use the default conditioning values

 * anyway, and do not use the custom formula.

 *

#define CALCULATE_SPECTRAL_CONDITIONING

 */

/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than JLONG.

 * We assume that int right shift is unsigned if JLONG right shift is,

 * which should be safe.

 */

#ifdef RIGHT_SHIFT_IS_UNSIGNED

#define ISHIFT_TEMPS    int ishift_temp;

#define IRIGHT_SHIFT(x, shft) \

  ((ishift_temp = (x)) < 0 ? \

   (ishift_temp >> (shft)) | ((~0) << (16 - (shft))) : \

   (ishift_temp >> (shft)))

#else

#define ISHIFT_TEMPS

#define IRIGHT_SHIFT(x, shft)   ((x) >> (shft))

#endif

LOCAL(void)

emit_byte(int val, j_compress_ptr cinfo)

/* Write next output byte; we do not support suspension in this module. */

{

  struct jpeg_destination_mgr *dest = cinfo->dest;

  *dest->next_output_byte++ = (JOCTET)val;

  if (--dest->free_in_buffer == 0)

    if (!(*dest->empty_output_buffer) (cinfo))

      ERREXIT(cinfo, JERR_CANT_SUSPEND);

}

/*

 * Finish up at the end of an arithmetic-compressed scan.

 */

METHODDEF(void)

finish_pass(j_compress_ptr cinfo)

{

  arith_entropy_ptr e = (arith_entropy_ptr)cinfo->entropy;

  JLONG temp;

  /* Section D.1.8: Termination of encoding */

  /* Find the e->c in the coding interval with the largest

   * number of trailing zero bits */

  if ((temp = (e->a - 1 + e->c) & 0xFFFF0000UL) < e->c)

    e->c = temp + 0x8000L;

  else

    e->c = temp;

  /* Send remaining bytes to output */

  e->c <<= e->ct;

  if (e->c & 0xF8000000UL) {

    /* One final overflow has to be handled */

    if (e->buffer >= 0) {

      if (e->zc)

        do emit_byte(0x00, cinfo);

        while (--e->zc);

      emit_byte(e->buffer + 1, cinfo);

      if (e->buffer + 1 == 0xFF)

        emit_byte(0x00, cinfo);

    }

    e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */

    e->sc = 0;

  } else {

    if (e->buffer == 0)

      ++e->zc;

    else if (e->buffer >= 0) {

      if (e->zc)

        do emit_byte(0x00, cinfo);

        while (--e->zc);

      emit_byte(e->buffer, cinfo);

    }

    if (e->sc) {

      if (e->zc)

        do emit_byte(0x00, cinfo);

        while (--e->zc);

      do {

        emit_byte(0xFF, cinfo);

        emit_byte(0x00, cinfo);

      } while (--e->sc);

    }

  }

  /* Output final bytes only if they are not 0x00 */

  if (e->c & 0x7FFF800L) {

    if (e->zc)  /* output final pending zero bytes */

      do emit_byte(0x00, cinfo);

      while (--e->zc);

    emit_byte((e->c >> 19) & 0xFF, cinfo);

    if (((e->c >> 19) & 0xFF) == 0xFF)

      emit_byte(0x00, cinfo);

    if (e->c & 0x7F800L) {

      emit_byte((e->c >> 11) & 0xFF, cinfo);

      if (((e->c >> 11) & 0xFF) == 0xFF)

        emit_byte(0x00, cinfo);

    }

  }

}

/*

 * The core arithmetic encoding routine (common in JPEG and JBIG).

 * This needs to go as fast as possible.

 * Machine-dependent optimization facilities

 * are not utilized in this portable implementation.

 * However, this code should be fairly efficient and

 * may be a good base for further optimizations anyway.

 *

 * Parameter 'val' to be encoded may be 0 or 1 (binary decision).

 *

 * Note: I've added full "Pacman" termination support to the

 * byte output routines, which is equivalent to the optional

 * Discard_final_zeros procedure (Figure D.15) in the spec.

 * Thus, we always produce the shortest possible output

 * stream compliant to the spec (no trailing zero bytes,

 * except for FF stuffing).

 *

 * I've also introduced a new scheme for accessing

 * the probability estimation state machine table,

 * derived from Markus Kuhn's JBIG implementation.

 */

LOCAL(void)

arith_encode(j_compress_ptr cinfo, unsigned char *st, int val)

{

  register arith_entropy_ptr e = (arith_entropy_ptr)cinfo->entropy;

  register unsigned char nl, nm;

  register JLONG qe, temp;

  register int sv;

  /* Fetch values from our compact representation of Table D.2:

   * Qe values and probability estimation state machine

   */

  sv = *st;

  qe = jpeg_aritab[sv & 0x7F];  /* => Qe_Value */

  nl = qe & 0xFF;  qe >>= 8;    /* Next_Index_LPS + Switch_MPS */

  nm = qe & 0xFF;  qe >>= 8;    /* Next_Index_MPS */

  /* Encode & estimation procedures per sections D.1.4 & D.1.5 */

  e->a -= qe;

  if (val != (sv >> 7)) {

    /* Encode the less probable symbol */

    if (e->a >= qe) {

      /* If the interval size (qe) for the less probable symbol (LPS)

       * is larger than the interval size for the MPS, then exchange

       * the two symbols for coding efficiency, otherwise code the LPS

       * as usual: */

      e->c += e->a;

      e->a = qe;

    }

    *st = (sv & 0x80) ^ nl;     /* Estimate_after_LPS */

  } else {

    /* Encode the more probable symbol */

    if (e->a >= 0x8000L)

      return;  /* A >= 0x8000 -> ready, no renormalization required */

    if (e->a < qe) {

      /* If the interval size (qe) for the less probable symbol (LPS)

       * is larger than the interval size for the MPS, then exchange

       * the two symbols for coding efficiency: */

      e->c += e->a;

      e->a = qe;

    }

    *st = (sv & 0x80) ^ nm;     /* Estimate_after_MPS */

  }

  /* Renormalization & data output per section D.1.6 */

  do {

    e->a <<= 1;

    e->c <<= 1;

    if (--e->ct == 0) {

      /* Another byte is ready for output */

      temp = e->c >> 19;

      if (temp > 0xFF) {

        /* Handle overflow over all stacked 0xFF bytes */

        if (e->buffer >= 0) {

          if (e->zc)

            do emit_byte(0x00, cinfo);

            while (--e->zc);

          emit_byte(e->buffer + 1, cinfo);

          if (e->buffer + 1 == 0xFF)

            emit_byte(0x00, cinfo);

        }

        e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */

        e->sc = 0;

        /* Note: The 3 spacer bits in the C register guarantee

         * that the new buffer byte can't be 0xFF here

         * (see page 160 in the P&M JPEG book). */

        e->buffer = temp & 0xFF;  /* new output byte, might overflow later */

      } else if (temp == 0xFF) {

        ++e->sc;  /* stack 0xFF byte (which might overflow later) */

      } else {

        /* Output all stacked 0xFF bytes, they will not overflow any more */

        if (e->buffer == 0)

          ++e->zc;

        else if (e->buffer >= 0) {

          if (e->zc)

            do emit_byte(0x00, cinfo);

            while (--e->zc);

          emit_byte(e->buffer, cinfo);

        }

        if (e->sc) {

          if (e->zc)

            do emit_byte(0x00, cinfo);

            while (--e->zc);

          do {

            emit_byte(0xFF, cinfo);

            emit_byte(0x00, cinfo);

          } while (--e->sc);

        }

        e->buffer = temp & 0xFF;  /* new output byte (can still overflow) */

      }

      e->c &= 0x7FFFFL;

      e->ct += 8;

    }

  } while (e->a < 0x8000L);

}

/*

 * Emit a restart marker & resynchronize predictions.

 */

LOCAL(void)

emit_restart(j_compress_ptr cinfo, int restart_num)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  int ci;

  jpeg_component_info *compptr;

  finish_pass(cinfo);

  emit_byte(0xFF, cinfo);

  emit_byte(JPEG_RST0 + restart_num, cinfo);

  /* Re-initialize statistics areas */

  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {

    compptr = cinfo->cur_comp_info[ci];

    /* DC needs no table for refinement scan */

    if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {

      MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);

      /* Reset DC predictions to 0 */

      entropy->last_dc_val[ci] = 0;

      entropy->dc_context[ci] = 0;

    }

    /* AC needs no table when not present */

    if (cinfo->progressive_mode == 0 || cinfo->Se) {

      MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);

    }

  }

  /* Reset arithmetic encoding variables */

  entropy->c = 0;

  entropy->a = 0x10000L;

  entropy->sc = 0;

  entropy->zc = 0;

  entropy->ct = 11;

  entropy->buffer = -1;  /* empty */

}

/*

 * MCU encoding for DC initial scan (either spectral selection,

 * or first pass of successive approximation).

 */

METHODDEF(boolean)

encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  JBLOCKROW block;

  unsigned char *st;

  int blkn, ci, tbl;

  int v, v2, m;

  ISHIFT_TEMPS

  /* Emit restart marker if needed */

  if (cinfo->restart_interval) {

    if (entropy->restarts_to_go == 0) {

      emit_restart(cinfo, entropy->next_restart_num);

      entropy->restarts_to_go = cinfo->restart_interval;

      entropy->next_restart_num++;

      entropy->next_restart_num &= 7;

    }

    entropy->restarts_to_go--;

  }

  /* Encode the MCU data blocks */

  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {

    block = MCU_data[blkn];

    ci = cinfo->MCU_membership[blkn];

    tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;

    /* Compute the DC value after the required point transform by Al.

     * This is simply an arithmetic right shift.

     */

    m = IRIGHT_SHIFT((int)((*block)[0]), cinfo->Al);

    /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */

    /* Table F.4: Point to statistics bin S0 for DC coefficient coding */

    st = entropy->dc_stats[tbl] + entropy->dc_context[ci];

    /* Figure F.4: Encode_DC_DIFF */

    if ((v = m - entropy->last_dc_val[ci]) == 0) {

      arith_encode(cinfo, st, 0);

      entropy->dc_context[ci] = 0;      /* zero diff category */

    } else {

      entropy->last_dc_val[ci] = m;

      arith_encode(cinfo, st, 1);

      /* Figure F.6: Encoding nonzero value v */

      /* Figure F.7: Encoding the sign of v */

      if (v > 0) {

        arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */

        st += 2;                        /* Table F.4: SP = S0 + 2 */

        entropy->dc_context[ci] = 4;    /* small positive diff category */

      } else {

        v = -v;

        arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */

        st += 3;                        /* Table F.4: SN = S0 + 3 */

        entropy->dc_context[ci] = 8;    /* small negative diff category */

      }

      /* Figure F.8: Encoding the magnitude category of v */

      m = 0;

      if (v -= 1) {

        arith_encode(cinfo, st, 1);

        m = 1;

        v2 = v;

        st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */

        while (v2 >>= 1) {

          arith_encode(cinfo, st, 1);

          m <<= 1;

          st += 1;

        }

      }

      arith_encode(cinfo, st, 0);

      /* Section F.1.4.4.1.2: Establish dc_context conditioning category */

      if (m < (int)((1L << cinfo->arith_dc_L[tbl]) >> 1))

        entropy->dc_context[ci] = 0;    /* zero diff category */

      else if (m > (int)((1L << cinfo->arith_dc_U[tbl]) >> 1))

        entropy->dc_context[ci] += 8;   /* large diff category */

      /* Figure F.9: Encoding the magnitude bit pattern of v */

      st += 14;

      while (m >>= 1)

        arith_encode(cinfo, st, (m & v) ? 1 : 0);

    }

  }

  return TRUE;

}

/*

 * MCU encoding for AC initial scan (either spectral selection,

 * or first pass of successive approximation).

 */

METHODDEF(boolean)

encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  JBLOCKROW block;

  unsigned char *st;

  int tbl, k, ke;

  int v, v2, m;

  /* Emit restart marker if needed */

  if (cinfo->restart_interval) {

    if (entropy->restarts_to_go == 0) {

      emit_restart(cinfo, entropy->next_restart_num);

      entropy->restarts_to_go = cinfo->restart_interval;

      entropy->next_restart_num++;

      entropy->next_restart_num &= 7;

    }

    entropy->restarts_to_go--;

  }

  /* Encode the MCU data block */

  block = MCU_data[0];

  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;

  /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */

  /* Establish EOB (end-of-block) index */

  for (ke = cinfo->Se; ke > 0; ke--)

    /* We must apply the point transform by Al.  For AC coefficients this

     * is an integer division with rounding towards 0.  To do this portably

     * in C, we shift after obtaining the absolute value.

     */

    if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {

      if (v >>= cinfo->Al) break;

    } else {

      v = -v;

      if (v >>= cinfo->Al) break;

    }

  /* Figure F.5: Encode_AC_Coefficients */

  for (k = cinfo->Ss; k <= ke; k++) {

    st = entropy->ac_stats[tbl] + 3 * (k - 1);

    arith_encode(cinfo, st, 0);         /* EOB decision */

    for (;;) {

      if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {

        if (v >>= cinfo->Al) {

          arith_encode(cinfo, st + 1, 1);

          arith_encode(cinfo, entropy->fixed_bin, 0);

          break;

        }

      } else {

        v = -v;

        if (v >>= cinfo->Al) {

          arith_encode(cinfo, st + 1, 1);

          arith_encode(cinfo, entropy->fixed_bin, 1);

          break;

        }

      }

      arith_encode(cinfo, st + 1, 0);  st += 3;  k++;

    }

    st += 2;

    /* Figure F.8: Encoding the magnitude category of v */

    m = 0;

    if (v -= 1) {

      arith_encode(cinfo, st, 1);

      m = 1;

      v2 = v;

      if (v2 >>= 1) {

        arith_encode(cinfo, st, 1);

        m <<= 1;

        st = entropy->ac_stats[tbl] +

             (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);

        while (v2 >>= 1) {

          arith_encode(cinfo, st, 1);

          m <<= 1;

          st += 1;

        }

      }

    }

    arith_encode(cinfo, st, 0);

    /* Figure F.9: Encoding the magnitude bit pattern of v */

    st += 14;

    while (m >>= 1)

      arith_encode(cinfo, st, (m & v) ? 1 : 0);

  }

  /* Encode EOB decision only if k <= cinfo->Se */

  if (k <= cinfo->Se) {

    st = entropy->ac_stats[tbl] + 3 * (k - 1);

    arith_encode(cinfo, st, 1);

  }

  return TRUE;

}

/*

 * MCU encoding for DC successive approximation refinement scan.

 */

METHODDEF(boolean)

encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  unsigned char *st;

  int Al, blkn;

  /* Emit restart marker if needed */

  if (cinfo->restart_interval) {

    if (entropy->restarts_to_go == 0) {

      emit_restart(cinfo, entropy->next_restart_num);

      entropy->restarts_to_go = cinfo->restart_interval;

      entropy->next_restart_num++;

      entropy->next_restart_num &= 7;

    }

    entropy->restarts_to_go--;

  }

  st = entropy->fixed_bin;      /* use fixed probability estimation */

  Al = cinfo->Al;

  /* Encode the MCU data blocks */

  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {

    /* We simply emit the Al'th bit of the DC coefficient value. */

    arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);

  }

  return TRUE;

}

/*

 * MCU encoding for AC successive approximation refinement scan.

 */

METHODDEF(boolean)

encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  JBLOCKROW block;

  unsigned char *st;

  int tbl, k, ke, kex;

  int v;

  /* Emit restart marker if needed */

  if (cinfo->restart_interval) {

    if (entropy->restarts_to_go == 0) {

      emit_restart(cinfo, entropy->next_restart_num);

      entropy->restarts_to_go = cinfo->restart_interval;

      entropy->next_restart_num++;

      entropy->next_restart_num &= 7;

    }

    entropy->restarts_to_go--;

  }

  /* Encode the MCU data block */

  block = MCU_data[0];

  tbl = cinfo->cur_comp_info[0]->ac_tbl_no;

  /* Section G.1.3.3: Encoding of AC coefficients */

  /* Establish EOB (end-of-block) index */

  for (ke = cinfo->Se; ke > 0; ke--)

    /* We must apply the point transform by Al.  For AC coefficients this

     * is an integer division with rounding towards 0.  To do this portably

     * in C, we shift after obtaining the absolute value.

     */

    if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {

      if (v >>= cinfo->Al) break;

    } else {

      v = -v;

      if (v >>= cinfo->Al) break;

    }

  /* Establish EOBx (previous stage end-of-block) index */

  for (kex = ke; kex > 0; kex--)

    if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) {

      if (v >>= cinfo->Ah) break;

    } else {

      v = -v;

      if (v >>= cinfo->Ah) break;

    }

  /* Figure G.10: Encode_AC_Coefficients_SA */

  for (k = cinfo->Ss; k <= ke; k++) {

    st = entropy->ac_stats[tbl] + 3 * (k - 1);

    if (k > kex)

      arith_encode(cinfo, st, 0);       /* EOB decision */

    for (;;) {

      if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {

        if (v >>= cinfo->Al) {

          if (v >> 1)                   /* previously nonzero coef */

            arith_encode(cinfo, st + 2, (v & 1));

          else {                        /* newly nonzero coef */

            arith_encode(cinfo, st + 1, 1);

            arith_encode(cinfo, entropy->fixed_bin, 0);

          }

          break;

        }

      } else {

        v = -v;

        if (v >>= cinfo->Al) {

          if (v >> 1)                   /* previously nonzero coef */

            arith_encode(cinfo, st + 2, (v & 1));

          else {                        /* newly nonzero coef */

            arith_encode(cinfo, st + 1, 1);

            arith_encode(cinfo, entropy->fixed_bin, 1);

          }

          break;

        }

      }

      arith_encode(cinfo, st + 1, 0);  st += 3;  k++;

    }

  }

  /* Encode EOB decision only if k <= cinfo->Se */

  if (k <= cinfo->Se) {

    st = entropy->ac_stats[tbl] + 3 * (k - 1);

    arith_encode(cinfo, st, 1);

  }

  return TRUE;

}

/*

 * Encode and output one MCU's worth of arithmetic-compressed coefficients.

 */

METHODDEF(boolean)

encode_mcu(j_compress_ptr cinfo, JBLOCKROW *MCU_data)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  jpeg_component_info *compptr;

  JBLOCKROW block;

  unsigned char *st;

  int blkn, ci, tbl, k, ke;

  int v, v2, m;

  /* Emit restart marker if needed */

  if (cinfo->restart_interval) {

    if (entropy->restarts_to_go == 0) {

      emit_restart(cinfo, entropy->next_restart_num);

      entropy->restarts_to_go = cinfo->restart_interval;

      entropy->next_restart_num++;

      entropy->next_restart_num &= 7;

    }

    entropy->restarts_to_go--;

  }

  /* Encode the MCU data blocks */

  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {

    block = MCU_data[blkn];

    ci = cinfo->MCU_membership[blkn];

    compptr = cinfo->cur_comp_info[ci];

    /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */

    tbl = compptr->dc_tbl_no;

    /* Table F.4: Point to statistics bin S0 for DC coefficient coding */

    st = entropy->dc_stats[tbl] + entropy->dc_context[ci];

    /* Figure F.4: Encode_DC_DIFF */

    if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {

      arith_encode(cinfo, st, 0);

      entropy->dc_context[ci] = 0;      /* zero diff category */

    } else {

      entropy->last_dc_val[ci] = (*block)[0];

      arith_encode(cinfo, st, 1);

      /* Figure F.6: Encoding nonzero value v */

      /* Figure F.7: Encoding the sign of v */

      if (v > 0) {

        arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */

        st += 2;                        /* Table F.4: SP = S0 + 2 */

        entropy->dc_context[ci] = 4;    /* small positive diff category */

      } else {

        v = -v;

        arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */

        st += 3;                        /* Table F.4: SN = S0 + 3 */

        entropy->dc_context[ci] = 8;    /* small negative diff category */

      }

      /* Figure F.8: Encoding the magnitude category of v */

      m = 0;

      if (v -= 1) {

        arith_encode(cinfo, st, 1);

        m = 1;

        v2 = v;

        st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */

        while (v2 >>= 1) {

          arith_encode(cinfo, st, 1);

          m <<= 1;

          st += 1;

        }

      }

      arith_encode(cinfo, st, 0);

      /* Section F.1.4.4.1.2: Establish dc_context conditioning category */

      if (m < (int)((1L << cinfo->arith_dc_L[tbl]) >> 1))

        entropy->dc_context[ci] = 0;    /* zero diff category */

      else if (m > (int)((1L << cinfo->arith_dc_U[tbl]) >> 1))

        entropy->dc_context[ci] += 8;   /* large diff category */

      /* Figure F.9: Encoding the magnitude bit pattern of v */

      st += 14;

      while (m >>= 1)

        arith_encode(cinfo, st, (m & v) ? 1 : 0);

    }

    /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */

    tbl = compptr->ac_tbl_no;

    /* Establish EOB (end-of-block) index */

    for (ke = DCTSIZE2 - 1; ke > 0; ke--)

      if ((*block)[jpeg_natural_order[ke]]) break;

    /* Figure F.5: Encode_AC_Coefficients */

    for (k = 1; k <= ke; k++) {

      st = entropy->ac_stats[tbl] + 3 * (k - 1);

      arith_encode(cinfo, st, 0);       /* EOB decision */

      while ((v = (*block)[jpeg_natural_order[k]]) == 0) {

        arith_encode(cinfo, st + 1, 0);  st += 3;  k++;

      }

      arith_encode(cinfo, st + 1, 1);

      /* Figure F.6: Encoding nonzero value v */

      /* Figure F.7: Encoding the sign of v */

      if (v > 0) {

        arith_encode(cinfo, entropy->fixed_bin, 0);

      } else {

        v = -v;

        arith_encode(cinfo, entropy->fixed_bin, 1);

      }

      st += 2;

      /* Figure F.8: Encoding the magnitude category of v */

      m = 0;

      if (v -= 1) {

        arith_encode(cinfo, st, 1);

        m = 1;

        v2 = v;

        if (v2 >>= 1) {

          arith_encode(cinfo, st, 1);

          m <<= 1;

          st = entropy->ac_stats[tbl] +

               (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);

          while (v2 >>= 1) {

            arith_encode(cinfo, st, 1);

            m <<= 1;

            st += 1;

          }

        }

      }

      arith_encode(cinfo, st, 0);

      /* Figure F.9: Encoding the magnitude bit pattern of v */

      st += 14;

      while (m >>= 1)

        arith_encode(cinfo, st, (m & v) ? 1 : 0);

    }

    /* Encode EOB decision only if k <= DCTSIZE2 - 1 */

    if (k <= DCTSIZE2 - 1) {

      st = entropy->ac_stats[tbl] + 3 * (k - 1);

      arith_encode(cinfo, st, 1);

    }

  }

  return TRUE;

}

/*

 * Initialize for an arithmetic-compressed scan.

 */

METHODDEF(void)

start_pass(j_compress_ptr cinfo, boolean gather_statistics)

{

  arith_entropy_ptr entropy = (arith_entropy_ptr)cinfo->entropy;

  int ci, tbl;

  jpeg_component_info *compptr;

  if (gather_statistics)

    /* Make sure to avoid that in the master control logic!

     * We are fully adaptive here and need no extra

     * statistics gathering pass!

     */

    ERREXIT(cinfo, JERR_NOT_COMPILED);

  /* We assume jcmaster.c already validated the progressive scan parameters. */

  /* Select execution routines */

  if (cinfo->progressive_mode) {

    if (cinfo->Ah == 0) {

      if (cinfo->Ss == 0)

        entropy->pub.encode_mcu = encode_mcu_DC_first;

      else

        entropy->pub.encode_mcu = encode_mcu_AC_first;

    } else {

      if (cinfo->Ss == 0)

        entropy->pub.encode_mcu = encode_mcu_DC_refine;

      else

        entropy->pub.encode_mcu = encode_mcu_AC_refine;

    }

  } else

    entropy->pub.encode_mcu = encode_mcu;

  /* Allocate & initialize requested statistics areas */

  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {

    compptr = cinfo->cur_comp_info[ci];

    /* DC needs no table for refinement scan */

    if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {

      tbl = compptr->dc_tbl_no;

      if (tbl < 0 || tbl >= NUM_ARITH_TBLS)

        ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);

      if (entropy->dc_stats[tbl] == NULL)

        entropy->dc_stats[tbl] = (unsigned char *)(*cinfo->mem->alloc_small)

          ((j_common_ptr)cinfo, JPOOL_IMAGE, DC_STAT_BINS);

      MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);

      /* Initialize DC predictions to 0 */

      entropy->last_dc_val[ci] = 0;

      entropy->dc_context[ci] = 0;

    }

    /* AC needs no table when not present */

    if (cinfo->progressive_mode == 0 || cinfo->Se) {

      tbl = compptr->ac_tbl_no;

      if (tbl < 0 || tbl >= NUM_ARITH_TBLS)