michael@0: /*
michael@0:  * jcarith.c
michael@0:  *
michael@0:  * Developed 1997-2009 by Guido Vollbeding.
michael@0:  * This file is part of the Independent JPEG Group's software.
michael@0:  * For conditions of distribution and use, see the accompanying README file.
michael@0:  *
michael@0:  * This file contains portable arithmetic entropy encoding routines for JPEG
michael@0:  * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
michael@0:  *
michael@0:  * Both sequential and progressive modes are supported in this single module.
michael@0:  *
michael@0:  * Suspension is not currently supported in this module.
michael@0:  */
michael@0: 
michael@0: #define JPEG_INTERNALS
michael@0: #include "jinclude.h"
michael@0: #include "jpeglib.h"
michael@0: 
michael@0: 
michael@0: /* Expanded entropy encoder object for arithmetic encoding. */
michael@0: 
michael@0: typedef struct {
michael@0:   struct jpeg_entropy_encoder pub; /* public fields */
michael@0: 
michael@0:   INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */
michael@0:   INT32 a;               /* A register, normalized size of coding interval */
michael@0:   INT32 sc;        /* counter for stacked 0xFF values which might overflow */
michael@0:   INT32 zc;          /* counter for pending 0x00 output values which might *
michael@0:                           * be discarded at the end ("Pacman" termination) */
michael@0:   int ct;  /* bit shift counter, determines when next byte will be written */
michael@0:   int buffer;                /* buffer for most recent output byte != 0xFF */
michael@0: 
michael@0:   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
michael@0:   int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
michael@0: 
michael@0:   unsigned int restarts_to_go;	/* MCUs left in this restart interval */
michael@0:   int next_restart_num;		/* next restart number to write (0-7) */
michael@0: 
michael@0:   /* Pointers to statistics areas (these workspaces have image lifespan) */
michael@0:   unsigned char * dc_stats[NUM_ARITH_TBLS];
michael@0:   unsigned char * ac_stats[NUM_ARITH_TBLS];
michael@0: 
michael@0:   /* Statistics bin for coding with fixed probability 0.5 */
michael@0:   unsigned char fixed_bin[4];
michael@0: } arith_entropy_encoder;
michael@0: 
michael@0: typedef arith_entropy_encoder * arith_entropy_ptr;
michael@0: 
michael@0: /* The following two definitions specify the allocation chunk size
michael@0:  * for the statistics area.
michael@0:  * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
michael@0:  * 49 statistics bins for DC, and 245 statistics bins for AC coding.
michael@0:  *
michael@0:  * We use a compact representation with 1 byte per statistics bin,
michael@0:  * thus the numbers directly represent byte sizes.
michael@0:  * This 1 byte per statistics bin contains the meaning of the MPS
michael@0:  * (more probable symbol) in the highest bit (mask 0x80), and the
michael@0:  * index into the probability estimation state machine table
michael@0:  * in the lower bits (mask 0x7F).
michael@0:  */
michael@0: 
michael@0: #define DC_STAT_BINS 64
michael@0: #define AC_STAT_BINS 256
michael@0: 
michael@0: /* NOTE: Uncomment the following #define if you want to use the
michael@0:  * given formula for calculating the AC conditioning parameter Kx
michael@0:  * for spectral selection progressive coding in section G.1.3.2
michael@0:  * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
michael@0:  * Although the spec and P&M authors claim that this "has proven
michael@0:  * to give good results for 8 bit precision samples", I'm not
michael@0:  * convinced yet that this is really beneficial.
michael@0:  * Early tests gave only very marginal compression enhancements
michael@0:  * (a few - around 5 or so - bytes even for very large files),
michael@0:  * which would turn out rather negative if we'd suppress the
michael@0:  * DAC (Define Arithmetic Conditioning) marker segments for
michael@0:  * the default parameters in the future.
michael@0:  * Note that currently the marker writing module emits 12-byte
michael@0:  * DAC segments for a full-component scan in a color image.
michael@0:  * This is not worth worrying about IMHO. However, since the
michael@0:  * spec defines the default values to be used if the tables
michael@0:  * are omitted (unlike Huffman tables, which are required
michael@0:  * anyway), one might optimize this behaviour in the future,
michael@0:  * and then it would be disadvantageous to use custom tables if
michael@0:  * they don't provide sufficient gain to exceed the DAC size.
michael@0:  *
michael@0:  * On the other hand, I'd consider it as a reasonable result
michael@0:  * that the conditioning has no significant influence on the
michael@0:  * compression performance. This means that the basic
michael@0:  * statistical model is already rather stable.
michael@0:  *
michael@0:  * Thus, at the moment, we use the default conditioning values
michael@0:  * anyway, and do not use the custom formula.
michael@0:  *
michael@0: #define CALCULATE_SPECTRAL_CONDITIONING
michael@0:  */
michael@0: 
michael@0: /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
michael@0:  * We assume that int right shift is unsigned if INT32 right shift is,
michael@0:  * which should be safe.
michael@0:  */
michael@0: 
michael@0: #ifdef RIGHT_SHIFT_IS_UNSIGNED
michael@0: #define ISHIFT_TEMPS	int ishift_temp;
michael@0: #define IRIGHT_SHIFT(x,shft)  \
michael@0: 	((ishift_temp = (x)) < 0 ? \
michael@0: 	 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
michael@0: 	 (ishift_temp >> (shft)))
michael@0: #else
michael@0: #define ISHIFT_TEMPS
michael@0: #define IRIGHT_SHIFT(x,shft)	((x) >> (shft))
michael@0: #endif
michael@0: 
michael@0: 
michael@0: LOCAL(void)
michael@0: emit_byte (int val, j_compress_ptr cinfo)
michael@0: /* Write next output byte; we do not support suspension in this module. */
michael@0: {
michael@0:   struct jpeg_destination_mgr * dest = cinfo->dest;
michael@0: 
michael@0:   *dest->next_output_byte++ = (JOCTET) val;
michael@0:   if (--dest->free_in_buffer == 0)
michael@0:     if (! (*dest->empty_output_buffer) (cinfo))
michael@0:       ERREXIT(cinfo, JERR_CANT_SUSPEND);
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Finish up at the end of an arithmetic-compressed scan.
michael@0:  */
michael@0: 
michael@0: METHODDEF(void)
michael@0: finish_pass (j_compress_ptr cinfo)
michael@0: {
michael@0:   arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
michael@0:   INT32 temp;
michael@0: 
michael@0:   /* Section D.1.8: Termination of encoding */
michael@0: 
michael@0:   /* Find the e->c in the coding interval with the largest
michael@0:    * number of trailing zero bits */
michael@0:   if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
michael@0:     e->c = temp + 0x8000L;
michael@0:   else
michael@0:     e->c = temp;
michael@0:   /* Send remaining bytes to output */
michael@0:   e->c <<= e->ct;
michael@0:   if (e->c & 0xF8000000L) {
michael@0:     /* One final overflow has to be handled */
michael@0:     if (e->buffer >= 0) {
michael@0:       if (e->zc)
michael@0: 	do emit_byte(0x00, cinfo);
michael@0: 	while (--e->zc);
michael@0:       emit_byte(e->buffer + 1, cinfo);
michael@0:       if (e->buffer + 1 == 0xFF)
michael@0: 	emit_byte(0x00, cinfo);
michael@0:     }
michael@0:     e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
michael@0:     e->sc = 0;
michael@0:   } else {
michael@0:     if (e->buffer == 0)
michael@0:       ++e->zc;
michael@0:     else if (e->buffer >= 0) {
michael@0:       if (e->zc)
michael@0: 	do emit_byte(0x00, cinfo);
michael@0: 	while (--e->zc);
michael@0:       emit_byte(e->buffer, cinfo);
michael@0:     }
michael@0:     if (e->sc) {
michael@0:       if (e->zc)
michael@0: 	do emit_byte(0x00, cinfo);
michael@0: 	while (--e->zc);
michael@0:       do {
michael@0: 	emit_byte(0xFF, cinfo);
michael@0: 	emit_byte(0x00, cinfo);
michael@0:       } while (--e->sc);
michael@0:     }
michael@0:   }
michael@0:   /* Output final bytes only if they are not 0x00 */
michael@0:   if (e->c & 0x7FFF800L) {
michael@0:     if (e->zc)  /* output final pending zero bytes */
michael@0:       do emit_byte(0x00, cinfo);
michael@0:       while (--e->zc);
michael@0:     emit_byte((e->c >> 19) & 0xFF, cinfo);
michael@0:     if (((e->c >> 19) & 0xFF) == 0xFF)
michael@0:       emit_byte(0x00, cinfo);
michael@0:     if (e->c & 0x7F800L) {
michael@0:       emit_byte((e->c >> 11) & 0xFF, cinfo);
michael@0:       if (((e->c >> 11) & 0xFF) == 0xFF)
michael@0: 	emit_byte(0x00, cinfo);
michael@0:     }
michael@0:   }
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * The core arithmetic encoding routine (common in JPEG and JBIG).
michael@0:  * This needs to go as fast as possible.
michael@0:  * Machine-dependent optimization facilities
michael@0:  * are not utilized in this portable implementation.
michael@0:  * However, this code should be fairly efficient and
michael@0:  * may be a good base for further optimizations anyway.
michael@0:  *
michael@0:  * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
michael@0:  *
michael@0:  * Note: I've added full "Pacman" termination support to the
michael@0:  * byte output routines, which is equivalent to the optional
michael@0:  * Discard_final_zeros procedure (Figure D.15) in the spec.
michael@0:  * Thus, we always produce the shortest possible output
michael@0:  * stream compliant to the spec (no trailing zero bytes,
michael@0:  * except for FF stuffing).
michael@0:  *
michael@0:  * I've also introduced a new scheme for accessing
michael@0:  * the probability estimation state machine table,
michael@0:  * derived from Markus Kuhn's JBIG implementation.
michael@0:  */
michael@0: 
michael@0: LOCAL(void)
michael@0: arith_encode (j_compress_ptr cinfo, unsigned char *st, int val) 
michael@0: {
michael@0:   register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
michael@0:   register unsigned char nl, nm;
michael@0:   register INT32 qe, temp;
michael@0:   register int sv;
michael@0: 
michael@0:   /* Fetch values from our compact representation of Table D.2:
michael@0:    * Qe values and probability estimation state machine
michael@0:    */
michael@0:   sv = *st;
michael@0:   qe = jpeg_aritab[sv & 0x7F];	/* => Qe_Value */
michael@0:   nl = qe & 0xFF; qe >>= 8;	/* Next_Index_LPS + Switch_MPS */
michael@0:   nm = qe & 0xFF; qe >>= 8;	/* Next_Index_MPS */
michael@0: 
michael@0:   /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
michael@0:   e->a -= qe;
michael@0:   if (val != (sv >> 7)) {
michael@0:     /* Encode the less probable symbol */
michael@0:     if (e->a >= qe) {
michael@0:       /* If the interval size (qe) for the less probable symbol (LPS)
michael@0:        * is larger than the interval size for the MPS, then exchange
michael@0:        * the two symbols for coding efficiency, otherwise code the LPS
michael@0:        * as usual: */
michael@0:       e->c += e->a;
michael@0:       e->a = qe;
michael@0:     }
michael@0:     *st = (sv & 0x80) ^ nl;	/* Estimate_after_LPS */
michael@0:   } else {
michael@0:     /* Encode the more probable symbol */
michael@0:     if (e->a >= 0x8000L)
michael@0:       return;  /* A >= 0x8000 -> ready, no renormalization required */
michael@0:     if (e->a < qe) {
michael@0:       /* If the interval size (qe) for the less probable symbol (LPS)
michael@0:        * is larger than the interval size for the MPS, then exchange
michael@0:        * the two symbols for coding efficiency: */
michael@0:       e->c += e->a;
michael@0:       e->a = qe;
michael@0:     }
michael@0:     *st = (sv & 0x80) ^ nm;	/* Estimate_after_MPS */
michael@0:   }
michael@0: 
michael@0:   /* Renormalization & data output per section D.1.6 */
michael@0:   do {
michael@0:     e->a <<= 1;
michael@0:     e->c <<= 1;
michael@0:     if (--e->ct == 0) {
michael@0:       /* Another byte is ready for output */
michael@0:       temp = e->c >> 19;
michael@0:       if (temp > 0xFF) {
michael@0: 	/* Handle overflow over all stacked 0xFF bytes */
michael@0: 	if (e->buffer >= 0) {
michael@0: 	  if (e->zc)
michael@0: 	    do emit_byte(0x00, cinfo);
michael@0: 	    while (--e->zc);
michael@0: 	  emit_byte(e->buffer + 1, cinfo);
michael@0: 	  if (e->buffer + 1 == 0xFF)
michael@0: 	    emit_byte(0x00, cinfo);
michael@0: 	}
michael@0: 	e->zc += e->sc;  /* carry-over converts stacked 0xFF bytes to 0x00 */
michael@0: 	e->sc = 0;
michael@0: 	/* Note: The 3 spacer bits in the C register guarantee
michael@0: 	 * that the new buffer byte can't be 0xFF here
michael@0: 	 * (see page 160 in the P&M JPEG book). */
michael@0: 	e->buffer = temp & 0xFF;  /* new output byte, might overflow later */
michael@0:       } else if (temp == 0xFF) {
michael@0: 	++e->sc;  /* stack 0xFF byte (which might overflow later) */
michael@0:       } else {
michael@0: 	/* Output all stacked 0xFF bytes, they will not overflow any more */
michael@0: 	if (e->buffer == 0)
michael@0: 	  ++e->zc;
michael@0: 	else if (e->buffer >= 0) {
michael@0: 	  if (e->zc)
michael@0: 	    do emit_byte(0x00, cinfo);
michael@0: 	    while (--e->zc);
michael@0: 	  emit_byte(e->buffer, cinfo);
michael@0: 	}
michael@0: 	if (e->sc) {
michael@0: 	  if (e->zc)
michael@0: 	    do emit_byte(0x00, cinfo);
michael@0: 	    while (--e->zc);
michael@0: 	  do {
michael@0: 	    emit_byte(0xFF, cinfo);
michael@0: 	    emit_byte(0x00, cinfo);
michael@0: 	  } while (--e->sc);
michael@0: 	}
michael@0: 	e->buffer = temp & 0xFF;  /* new output byte (can still overflow) */
michael@0:       }
michael@0:       e->c &= 0x7FFFFL;
michael@0:       e->ct += 8;
michael@0:     }
michael@0:   } while (e->a < 0x8000L);
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Emit a restart marker & resynchronize predictions.
michael@0:  */
michael@0: 
michael@0: LOCAL(void)
michael@0: emit_restart (j_compress_ptr cinfo, int restart_num)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   int ci;
michael@0:   jpeg_component_info * compptr;
michael@0: 
michael@0:   finish_pass(cinfo);
michael@0: 
michael@0:   emit_byte(0xFF, cinfo);
michael@0:   emit_byte(JPEG_RST0 + restart_num, cinfo);
michael@0: 
michael@0:   /* Re-initialize statistics areas */
michael@0:   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
michael@0:     compptr = cinfo->cur_comp_info[ci];
michael@0:     /* DC needs no table for refinement scan */
michael@0:     if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
michael@0:       MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
michael@0:       /* Reset DC predictions to 0 */
michael@0:       entropy->last_dc_val[ci] = 0;
michael@0:       entropy->dc_context[ci] = 0;
michael@0:     }
michael@0:     /* AC needs no table when not present */
michael@0:     if (cinfo->progressive_mode == 0 || cinfo->Se) {
michael@0:       MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /* Reset arithmetic encoding variables */
michael@0:   entropy->c = 0;
michael@0:   entropy->a = 0x10000L;
michael@0:   entropy->sc = 0;
michael@0:   entropy->zc = 0;
michael@0:   entropy->ct = 11;
michael@0:   entropy->buffer = -1;  /* empty */
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * MCU encoding for DC initial scan (either spectral selection,
michael@0:  * or first pass of successive approximation).
michael@0:  */
michael@0: 
michael@0: METHODDEF(boolean)
michael@0: encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   JBLOCKROW block;
michael@0:   unsigned char *st;
michael@0:   int blkn, ci, tbl;
michael@0:   int v, v2, m;
michael@0:   ISHIFT_TEMPS
michael@0: 
michael@0:   /* Emit restart marker if needed */
michael@0:   if (cinfo->restart_interval) {
michael@0:     if (entropy->restarts_to_go == 0) {
michael@0:       emit_restart(cinfo, entropy->next_restart_num);
michael@0:       entropy->restarts_to_go = cinfo->restart_interval;
michael@0:       entropy->next_restart_num++;
michael@0:       entropy->next_restart_num &= 7;
michael@0:     }
michael@0:     entropy->restarts_to_go--;
michael@0:   }
michael@0: 
michael@0:   /* Encode the MCU data blocks */
michael@0:   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
michael@0:     block = MCU_data[blkn];
michael@0:     ci = cinfo->MCU_membership[blkn];
michael@0:     tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
michael@0: 
michael@0:     /* Compute the DC value after the required point transform by Al.
michael@0:      * This is simply an arithmetic right shift.
michael@0:      */
michael@0:     m = IRIGHT_SHIFT((int) ((*block)[0]), cinfo->Al);
michael@0: 
michael@0:     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
michael@0: 
michael@0:     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
michael@0:     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
michael@0: 
michael@0:     /* Figure F.4: Encode_DC_DIFF */
michael@0:     if ((v = m - entropy->last_dc_val[ci]) == 0) {
michael@0:       arith_encode(cinfo, st, 0);
michael@0:       entropy->dc_context[ci] = 0;	/* zero diff category */
michael@0:     } else {
michael@0:       entropy->last_dc_val[ci] = m;
michael@0:       arith_encode(cinfo, st, 1);
michael@0:       /* Figure F.6: Encoding nonzero value v */
michael@0:       /* Figure F.7: Encoding the sign of v */
michael@0:       if (v > 0) {
michael@0: 	arith_encode(cinfo, st + 1, 0);	/* Table F.4: SS = S0 + 1 */
michael@0: 	st += 2;			/* Table F.4: SP = S0 + 2 */
michael@0: 	entropy->dc_context[ci] = 4;	/* small positive diff category */
michael@0:       } else {
michael@0: 	v = -v;
michael@0: 	arith_encode(cinfo, st + 1, 1);	/* Table F.4: SS = S0 + 1 */
michael@0: 	st += 3;			/* Table F.4: SN = S0 + 3 */
michael@0: 	entropy->dc_context[ci] = 8;	/* small negative diff category */
michael@0:       }
michael@0:       /* Figure F.8: Encoding the magnitude category of v */
michael@0:       m = 0;
michael@0:       if (v -= 1) {
michael@0: 	arith_encode(cinfo, st, 1);
michael@0: 	m = 1;
michael@0: 	v2 = v;
michael@0: 	st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
michael@0: 	while (v2 >>= 1) {
michael@0: 	  arith_encode(cinfo, st, 1);
michael@0: 	  m <<= 1;
michael@0: 	  st += 1;
michael@0: 	}
michael@0:       }
michael@0:       arith_encode(cinfo, st, 0);
michael@0:       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
michael@0:       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
michael@0: 	entropy->dc_context[ci] = 0;	/* zero diff category */
michael@0:       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
michael@0: 	entropy->dc_context[ci] += 8;	/* large diff category */
michael@0:       /* Figure F.9: Encoding the magnitude bit pattern of v */
michael@0:       st += 14;
michael@0:       while (m >>= 1)
michael@0: 	arith_encode(cinfo, st, (m & v) ? 1 : 0);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * MCU encoding for AC initial scan (either spectral selection,
michael@0:  * or first pass of successive approximation).
michael@0:  */
michael@0: 
michael@0: METHODDEF(boolean)
michael@0: encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   JBLOCKROW block;
michael@0:   unsigned char *st;
michael@0:   int tbl, k, ke;
michael@0:   int v, v2, m;
michael@0: 
michael@0:   /* Emit restart marker if needed */
michael@0:   if (cinfo->restart_interval) {
michael@0:     if (entropy->restarts_to_go == 0) {
michael@0:       emit_restart(cinfo, entropy->next_restart_num);
michael@0:       entropy->restarts_to_go = cinfo->restart_interval;
michael@0:       entropy->next_restart_num++;
michael@0:       entropy->next_restart_num &= 7;
michael@0:     }
michael@0:     entropy->restarts_to_go--;
michael@0:   }
michael@0: 
michael@0:   /* Encode the MCU data block */
michael@0:   block = MCU_data[0];
michael@0:   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
michael@0: 
michael@0:   /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
michael@0: 
michael@0:   /* Establish EOB (end-of-block) index */
michael@0:   for (ke = cinfo->Se; ke > 0; ke--)
michael@0:     /* We must apply the point transform by Al.  For AC coefficients this
michael@0:      * is an integer division with rounding towards 0.  To do this portably
michael@0:      * in C, we shift after obtaining the absolute value.
michael@0:      */
michael@0:     if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
michael@0:       if (v >>= cinfo->Al) break;
michael@0:     } else {
michael@0:       v = -v;
michael@0:       if (v >>= cinfo->Al) break;
michael@0:     }
michael@0: 
michael@0:   /* Figure F.5: Encode_AC_Coefficients */
michael@0:   for (k = cinfo->Ss; k <= ke; k++) {
michael@0:     st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:     arith_encode(cinfo, st, 0);		/* EOB decision */
michael@0:     for (;;) {
michael@0:       if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
michael@0: 	if (v >>= cinfo->Al) {
michael@0: 	  arith_encode(cinfo, st + 1, 1);
michael@0: 	  arith_encode(cinfo, entropy->fixed_bin, 0);
michael@0: 	  break;
michael@0: 	}
michael@0:       } else {
michael@0: 	v = -v;
michael@0: 	if (v >>= cinfo->Al) {
michael@0: 	  arith_encode(cinfo, st + 1, 1);
michael@0: 	  arith_encode(cinfo, entropy->fixed_bin, 1);
michael@0: 	  break;
michael@0: 	}
michael@0:       }
michael@0:       arith_encode(cinfo, st + 1, 0); st += 3; k++;
michael@0:     }
michael@0:     st += 2;
michael@0:     /* Figure F.8: Encoding the magnitude category of v */
michael@0:     m = 0;
michael@0:     if (v -= 1) {
michael@0:       arith_encode(cinfo, st, 1);
michael@0:       m = 1;
michael@0:       v2 = v;
michael@0:       if (v2 >>= 1) {
michael@0: 	arith_encode(cinfo, st, 1);
michael@0: 	m <<= 1;
michael@0: 	st = entropy->ac_stats[tbl] +
michael@0: 	     (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
michael@0: 	while (v2 >>= 1) {
michael@0: 	  arith_encode(cinfo, st, 1);
michael@0: 	  m <<= 1;
michael@0: 	  st += 1;
michael@0: 	}
michael@0:       }
michael@0:     }
michael@0:     arith_encode(cinfo, st, 0);
michael@0:     /* Figure F.9: Encoding the magnitude bit pattern of v */
michael@0:     st += 14;
michael@0:     while (m >>= 1)
michael@0:       arith_encode(cinfo, st, (m & v) ? 1 : 0);
michael@0:   }
michael@0:   /* Encode EOB decision only if k <= cinfo->Se */
michael@0:   if (k <= cinfo->Se) {
michael@0:     st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:     arith_encode(cinfo, st, 1);
michael@0:   }
michael@0: 
michael@0:   return TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * MCU encoding for DC successive approximation refinement scan.
michael@0:  */
michael@0: 
michael@0: METHODDEF(boolean)
michael@0: encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   unsigned char *st;
michael@0:   int Al, blkn;
michael@0: 
michael@0:   /* Emit restart marker if needed */
michael@0:   if (cinfo->restart_interval) {
michael@0:     if (entropy->restarts_to_go == 0) {
michael@0:       emit_restart(cinfo, entropy->next_restart_num);
michael@0:       entropy->restarts_to_go = cinfo->restart_interval;
michael@0:       entropy->next_restart_num++;
michael@0:       entropy->next_restart_num &= 7;
michael@0:     }
michael@0:     entropy->restarts_to_go--;
michael@0:   }
michael@0: 
michael@0:   st = entropy->fixed_bin;	/* use fixed probability estimation */
michael@0:   Al = cinfo->Al;
michael@0: 
michael@0:   /* Encode the MCU data blocks */
michael@0:   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
michael@0:     /* We simply emit the Al'th bit of the DC coefficient value. */
michael@0:     arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
michael@0:   }
michael@0: 
michael@0:   return TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * MCU encoding for AC successive approximation refinement scan.
michael@0:  */
michael@0: 
michael@0: METHODDEF(boolean)
michael@0: encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   JBLOCKROW block;
michael@0:   unsigned char *st;
michael@0:   int tbl, k, ke, kex;
michael@0:   int v;
michael@0: 
michael@0:   /* Emit restart marker if needed */
michael@0:   if (cinfo->restart_interval) {
michael@0:     if (entropy->restarts_to_go == 0) {
michael@0:       emit_restart(cinfo, entropy->next_restart_num);
michael@0:       entropy->restarts_to_go = cinfo->restart_interval;
michael@0:       entropy->next_restart_num++;
michael@0:       entropy->next_restart_num &= 7;
michael@0:     }
michael@0:     entropy->restarts_to_go--;
michael@0:   }
michael@0: 
michael@0:   /* Encode the MCU data block */
michael@0:   block = MCU_data[0];
michael@0:   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
michael@0: 
michael@0:   /* Section G.1.3.3: Encoding of AC coefficients */
michael@0: 
michael@0:   /* Establish EOB (end-of-block) index */
michael@0:   for (ke = cinfo->Se; ke > 0; ke--)
michael@0:     /* We must apply the point transform by Al.  For AC coefficients this
michael@0:      * is an integer division with rounding towards 0.  To do this portably
michael@0:      * in C, we shift after obtaining the absolute value.
michael@0:      */
michael@0:     if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
michael@0:       if (v >>= cinfo->Al) break;
michael@0:     } else {
michael@0:       v = -v;
michael@0:       if (v >>= cinfo->Al) break;
michael@0:     }
michael@0: 
michael@0:   /* Establish EOBx (previous stage end-of-block) index */
michael@0:   for (kex = ke; kex > 0; kex--)
michael@0:     if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) {
michael@0:       if (v >>= cinfo->Ah) break;
michael@0:     } else {
michael@0:       v = -v;
michael@0:       if (v >>= cinfo->Ah) break;
michael@0:     }
michael@0: 
michael@0:   /* Figure G.10: Encode_AC_Coefficients_SA */
michael@0:   for (k = cinfo->Ss; k <= ke; k++) {
michael@0:     st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:     if (k > kex)
michael@0:       arith_encode(cinfo, st, 0);	/* EOB decision */
michael@0:     for (;;) {
michael@0:       if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
michael@0: 	if (v >>= cinfo->Al) {
michael@0: 	  if (v >> 1)			/* previously nonzero coef */
michael@0: 	    arith_encode(cinfo, st + 2, (v & 1));
michael@0: 	  else {			/* newly nonzero coef */
michael@0: 	    arith_encode(cinfo, st + 1, 1);
michael@0: 	    arith_encode(cinfo, entropy->fixed_bin, 0);
michael@0: 	  }
michael@0: 	  break;
michael@0: 	}
michael@0:       } else {
michael@0: 	v = -v;
michael@0: 	if (v >>= cinfo->Al) {
michael@0: 	  if (v >> 1)			/* previously nonzero coef */
michael@0: 	    arith_encode(cinfo, st + 2, (v & 1));
michael@0: 	  else {			/* newly nonzero coef */
michael@0: 	    arith_encode(cinfo, st + 1, 1);
michael@0: 	    arith_encode(cinfo, entropy->fixed_bin, 1);
michael@0: 	  }
michael@0: 	  break;
michael@0: 	}
michael@0:       }
michael@0:       arith_encode(cinfo, st + 1, 0); st += 3; k++;
michael@0:     }
michael@0:   }
michael@0:   /* Encode EOB decision only if k <= cinfo->Se */
michael@0:   if (k <= cinfo->Se) {
michael@0:     st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:     arith_encode(cinfo, st, 1);
michael@0:   }
michael@0: 
michael@0:   return TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Encode and output one MCU's worth of arithmetic-compressed coefficients.
michael@0:  */
michael@0: 
michael@0: METHODDEF(boolean)
michael@0: encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   jpeg_component_info * compptr;
michael@0:   JBLOCKROW block;
michael@0:   unsigned char *st;
michael@0:   int blkn, ci, tbl, k, ke;
michael@0:   int v, v2, m;
michael@0: 
michael@0:   /* Emit restart marker if needed */
michael@0:   if (cinfo->restart_interval) {
michael@0:     if (entropy->restarts_to_go == 0) {
michael@0:       emit_restart(cinfo, entropy->next_restart_num);
michael@0:       entropy->restarts_to_go = cinfo->restart_interval;
michael@0:       entropy->next_restart_num++;
michael@0:       entropy->next_restart_num &= 7;
michael@0:     }
michael@0:     entropy->restarts_to_go--;
michael@0:   }
michael@0: 
michael@0:   /* Encode the MCU data blocks */
michael@0:   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
michael@0:     block = MCU_data[blkn];
michael@0:     ci = cinfo->MCU_membership[blkn];
michael@0:     compptr = cinfo->cur_comp_info[ci];
michael@0: 
michael@0:     /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
michael@0: 
michael@0:     tbl = compptr->dc_tbl_no;
michael@0: 
michael@0:     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
michael@0:     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
michael@0: 
michael@0:     /* Figure F.4: Encode_DC_DIFF */
michael@0:     if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
michael@0:       arith_encode(cinfo, st, 0);
michael@0:       entropy->dc_context[ci] = 0;	/* zero diff category */
michael@0:     } else {
michael@0:       entropy->last_dc_val[ci] = (*block)[0];
michael@0:       arith_encode(cinfo, st, 1);
michael@0:       /* Figure F.6: Encoding nonzero value v */
michael@0:       /* Figure F.7: Encoding the sign of v */
michael@0:       if (v > 0) {
michael@0: 	arith_encode(cinfo, st + 1, 0);	/* Table F.4: SS = S0 + 1 */
michael@0: 	st += 2;			/* Table F.4: SP = S0 + 2 */
michael@0: 	entropy->dc_context[ci] = 4;	/* small positive diff category */
michael@0:       } else {
michael@0: 	v = -v;
michael@0: 	arith_encode(cinfo, st + 1, 1);	/* Table F.4: SS = S0 + 1 */
michael@0: 	st += 3;			/* Table F.4: SN = S0 + 3 */
michael@0: 	entropy->dc_context[ci] = 8;	/* small negative diff category */
michael@0:       }
michael@0:       /* Figure F.8: Encoding the magnitude category of v */
michael@0:       m = 0;
michael@0:       if (v -= 1) {
michael@0: 	arith_encode(cinfo, st, 1);
michael@0: 	m = 1;
michael@0: 	v2 = v;
michael@0: 	st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
michael@0: 	while (v2 >>= 1) {
michael@0: 	  arith_encode(cinfo, st, 1);
michael@0: 	  m <<= 1;
michael@0: 	  st += 1;
michael@0: 	}
michael@0:       }
michael@0:       arith_encode(cinfo, st, 0);
michael@0:       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
michael@0:       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
michael@0: 	entropy->dc_context[ci] = 0;	/* zero diff category */
michael@0:       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
michael@0: 	entropy->dc_context[ci] += 8;	/* large diff category */
michael@0:       /* Figure F.9: Encoding the magnitude bit pattern of v */
michael@0:       st += 14;
michael@0:       while (m >>= 1)
michael@0: 	arith_encode(cinfo, st, (m & v) ? 1 : 0);
michael@0:     }
michael@0: 
michael@0:     /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
michael@0: 
michael@0:     tbl = compptr->ac_tbl_no;
michael@0: 
michael@0:     /* Establish EOB (end-of-block) index */
michael@0:     for (ke = DCTSIZE2 - 1; ke > 0; ke--)
michael@0:       if ((*block)[jpeg_natural_order[ke]]) break;
michael@0: 
michael@0:     /* Figure F.5: Encode_AC_Coefficients */
michael@0:     for (k = 1; k <= ke; k++) {
michael@0:       st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:       arith_encode(cinfo, st, 0);	/* EOB decision */
michael@0:       while ((v = (*block)[jpeg_natural_order[k]]) == 0) {
michael@0: 	arith_encode(cinfo, st + 1, 0); st += 3; k++;
michael@0:       }
michael@0:       arith_encode(cinfo, st + 1, 1);
michael@0:       /* Figure F.6: Encoding nonzero value v */
michael@0:       /* Figure F.7: Encoding the sign of v */
michael@0:       if (v > 0) {
michael@0: 	arith_encode(cinfo, entropy->fixed_bin, 0);
michael@0:       } else {
michael@0: 	v = -v;
michael@0: 	arith_encode(cinfo, entropy->fixed_bin, 1);
michael@0:       }
michael@0:       st += 2;
michael@0:       /* Figure F.8: Encoding the magnitude category of v */
michael@0:       m = 0;
michael@0:       if (v -= 1) {
michael@0: 	arith_encode(cinfo, st, 1);
michael@0: 	m = 1;
michael@0: 	v2 = v;
michael@0: 	if (v2 >>= 1) {
michael@0: 	  arith_encode(cinfo, st, 1);
michael@0: 	  m <<= 1;
michael@0: 	  st = entropy->ac_stats[tbl] +
michael@0: 	       (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
michael@0: 	  while (v2 >>= 1) {
michael@0: 	    arith_encode(cinfo, st, 1);
michael@0: 	    m <<= 1;
michael@0: 	    st += 1;
michael@0: 	  }
michael@0: 	}
michael@0:       }
michael@0:       arith_encode(cinfo, st, 0);
michael@0:       /* Figure F.9: Encoding the magnitude bit pattern of v */
michael@0:       st += 14;
michael@0:       while (m >>= 1)
michael@0: 	arith_encode(cinfo, st, (m & v) ? 1 : 0);
michael@0:     }
michael@0:     /* Encode EOB decision only if k <= DCTSIZE2 - 1 */
michael@0:     if (k <= DCTSIZE2 - 1) {
michael@0:       st = entropy->ac_stats[tbl] + 3 * (k - 1);
michael@0:       arith_encode(cinfo, st, 1);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Initialize for an arithmetic-compressed scan.
michael@0:  */
michael@0: 
michael@0: METHODDEF(void)
michael@0: start_pass (j_compress_ptr cinfo, boolean gather_statistics)
michael@0: {
michael@0:   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
michael@0:   int ci, tbl;
michael@0:   jpeg_component_info * compptr;
michael@0: 
michael@0:   if (gather_statistics)
michael@0:     /* Make sure to avoid that in the master control logic!
michael@0:      * We are fully adaptive here and need no extra
michael@0:      * statistics gathering pass!
michael@0:      */
michael@0:     ERREXIT(cinfo, JERR_NOT_COMPILED);
michael@0: 
michael@0:   /* We assume jcmaster.c already validated the progressive scan parameters. */
michael@0: 
michael@0:   /* Select execution routines */
michael@0:   if (cinfo->progressive_mode) {
michael@0:     if (cinfo->Ah == 0) {
michael@0:       if (cinfo->Ss == 0)
michael@0: 	entropy->pub.encode_mcu = encode_mcu_DC_first;
michael@0:       else
michael@0: 	entropy->pub.encode_mcu = encode_mcu_AC_first;
michael@0:     } else {
michael@0:       if (cinfo->Ss == 0)
michael@0: 	entropy->pub.encode_mcu = encode_mcu_DC_refine;
michael@0:       else
michael@0: 	entropy->pub.encode_mcu = encode_mcu_AC_refine;
michael@0:     }
michael@0:   } else
michael@0:     entropy->pub.encode_mcu = encode_mcu;
michael@0: 
michael@0:   /* Allocate & initialize requested statistics areas */
michael@0:   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
michael@0:     compptr = cinfo->cur_comp_info[ci];
michael@0:     /* DC needs no table for refinement scan */
michael@0:     if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
michael@0:       tbl = compptr->dc_tbl_no;
michael@0:       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
michael@0: 	ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
michael@0:       if (entropy->dc_stats[tbl] == NULL)
michael@0: 	entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
michael@0: 	  ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
michael@0:       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
michael@0:       /* Initialize DC predictions to 0 */
michael@0:       entropy->last_dc_val[ci] = 0;
michael@0:       entropy->dc_context[ci] = 0;
michael@0:     }
michael@0:     /* AC needs no table when not present */
michael@0:     if (cinfo->progressive_mode == 0 || cinfo->Se) {
michael@0:       tbl = compptr->ac_tbl_no;
michael@0:       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
michael@0: 	ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
michael@0:       if (entropy->ac_stats[tbl] == NULL)
michael@0: 	entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
michael@0: 	  ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
michael@0:       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
michael@0: #ifdef CALCULATE_SPECTRAL_CONDITIONING
michael@0:       if (cinfo->progressive_mode)
michael@0: 	/* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
michael@0: 	cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
michael@0: #endif
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /* Initialize arithmetic encoding variables */
michael@0:   entropy->c = 0;
michael@0:   entropy->a = 0x10000L;
michael@0:   entropy->sc = 0;
michael@0:   entropy->zc = 0;
michael@0:   entropy->ct = 11;
michael@0:   entropy->buffer = -1;  /* empty */
michael@0: 
michael@0:   /* Initialize restart stuff */
michael@0:   entropy->restarts_to_go = cinfo->restart_interval;
michael@0:   entropy->next_restart_num = 0;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * Module initialization routine for arithmetic entropy encoding.
michael@0:  */
michael@0: 
michael@0: GLOBAL(void)
michael@0: jinit_arith_encoder (j_compress_ptr cinfo)
michael@0: {
michael@0:   arith_entropy_ptr entropy;
michael@0:   int i;
michael@0: 
michael@0:   entropy = (arith_entropy_ptr)
michael@0:     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
michael@0: 				SIZEOF(arith_entropy_encoder));
michael@0:   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
michael@0:   entropy->pub.start_pass = start_pass;
michael@0:   entropy->pub.finish_pass = finish_pass;
michael@0: 
michael@0:   /* Mark tables unallocated */
michael@0:   for (i = 0; i < NUM_ARITH_TBLS; i++) {
michael@0:     entropy->dc_stats[i] = NULL;
michael@0:     entropy->ac_stats[i] = NULL;
michael@0:   }
michael@0: 
michael@0:   /* Initialize index for fixed probability estimation */
michael@0:   entropy->fixed_bin[0] = 113;
michael@0: }