/*
 * 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, 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 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 */

	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) & 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) {
	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)
				ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
			if (entropy->ac_stats[tbl] == NULL)
				entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
						((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
			MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
#ifdef CALCULATE_SPECTRAL_CONDITIONING
			if (cinfo->progressive_mode)
			  /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
			  cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
#endif
		}
	}

	/* Initialize arithmetic encoding variables */
	entropy->c = 0;
	entropy->a = 0x10000L;
	entropy->sc = 0;
	entropy->zc = 0;
	entropy->ct = 11;
	entropy->buffer = -1;  /* empty */

	/* Initialize restart stuff */
	entropy->restarts_to_go = cinfo->restart_interval;
	entropy->next_restart_num = 0;
}


/*
 * Module initialization routine for arithmetic entropy encoding.
 */

GLOBAL(void)
jinit_arith_encoder(j_compress_ptr cinfo) {
	arith_entropy_ptr entropy;
	int i;

	entropy = (arith_entropy_ptr)
			(*cinfo->mem->alloc_small)((j_common_ptr) cinfo, JPOOL_IMAGE,
			                           sizeof(arith_entropy_encoder));
	cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
	entropy->pub.start_pass = start_pass;
	entropy->pub.finish_pass = finish_pass;

	/* Mark tables unallocated */
	for (i = 0; i < NUM_ARITH_TBLS; i++) {
		entropy->dc_stats[i] = NULL;
		entropy->ac_stats[i] = NULL;
	}

	/* Initialize index for fixed probability estimation */
	entropy->fixed_bin[0] = 113;
}
