/* * jcarith.c * * Copyright (C) 1997, Guido Vollbeding <guivol@esc.de>. * This file is NOT part of the Independent JPEG Group's software * for legal reasons. * See the accompanying README file for conditions of distribution and use. * * This file contains portable arithmetic entropy encoding routines for JPEG * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81). * * Both sequential and progressive modes are supported in this single module. * * Suspension is not currently supported in this module. */#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 */  INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */  INT32 a;               /* A register, normalized size of coding interval */  INT32 sc;        /* counter for stacked 0xFF values which might overflow */  INT32 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];} 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. * Note that we use one additional AC bin for codings with fixed * probability (0.5), thus the minimum number for AC is 246. * * 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 INT32. * We assume that int right shift is unsigned if INT32 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))#endifLOCAL(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;  INT32 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) & 0xFFFF0000L) < e->c)    e->c = temp + 0x8000L;  else    e->c = temp;  /* Send remaining bytes to output */  e->c <<= e->ct;  if (e->c & 0xF8000000L) {    /* 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) {  extern const INT32 jaritab[];  register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;  register unsigned char nl, nm;  register INT32 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 = jaritab[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);  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {    compptr = cinfo->cur_comp_info[ci];    /* Re-initialize statistics areas */    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;    }    if (cinfo->progressive_mode == 0 || cinfo->Ss) {      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) (((INT32) 1 << cinfo->arith_dc_L[tbl]) >> 1))	entropy->dc_context[ci] = 0;	/* zero diff category */      else if (m > (int) (((INT32) 1 << 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) {