1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libjpeg/jcarith.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,925 @@
1.4 +/*
1.5 + * jcarith.c
1.6 + *
1.7 + * Developed 1997-2009 by Guido Vollbeding.
1.8 + * This file is part of the Independent JPEG Group's software.
1.9 + * For conditions of distribution and use, see the accompanying README file.
1.10 + *
1.11 + * This file contains portable arithmetic entropy encoding routines for JPEG
1.12 + * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
1.13 + *
1.14 + * Both sequential and progressive modes are supported in this single module.
1.15 + *
1.16 + * Suspension is not currently supported in this module.
1.17 + */
1.18 +
1.19 +#define JPEG_INTERNALS
1.20 +#include "jinclude.h"
1.21 +#include "jpeglib.h"
1.22 +
1.23 +
1.24 +/* Expanded entropy encoder object for arithmetic encoding. */
1.25 +
1.26 +typedef struct {
1.27 + struct jpeg_entropy_encoder pub; /* public fields */
1.28 +
1.29 + INT32 c; /* C register, base of coding interval, layout as in sec. D.1.3 */
1.30 + INT32 a; /* A register, normalized size of coding interval */
1.31 + INT32 sc; /* counter for stacked 0xFF values which might overflow */
1.32 + INT32 zc; /* counter for pending 0x00 output values which might *
1.33 + * be discarded at the end ("Pacman" termination) */
1.34 + int ct; /* bit shift counter, determines when next byte will be written */
1.35 + int buffer; /* buffer for most recent output byte != 0xFF */
1.36 +
1.37 + int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
1.38 + int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
1.39 +
1.40 + unsigned int restarts_to_go; /* MCUs left in this restart interval */
1.41 + int next_restart_num; /* next restart number to write (0-7) */
1.42 +
1.43 + /* Pointers to statistics areas (these workspaces have image lifespan) */
1.44 + unsigned char * dc_stats[NUM_ARITH_TBLS];
1.45 + unsigned char * ac_stats[NUM_ARITH_TBLS];
1.46 +
1.47 + /* Statistics bin for coding with fixed probability 0.5 */
1.48 + unsigned char fixed_bin[4];
1.49 +} arith_entropy_encoder;
1.50 +
1.51 +typedef arith_entropy_encoder * arith_entropy_ptr;
1.52 +
1.53 +/* The following two definitions specify the allocation chunk size
1.54 + * for the statistics area.
1.55 + * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
1.56 + * 49 statistics bins for DC, and 245 statistics bins for AC coding.
1.57 + *
1.58 + * We use a compact representation with 1 byte per statistics bin,
1.59 + * thus the numbers directly represent byte sizes.
1.60 + * This 1 byte per statistics bin contains the meaning of the MPS
1.61 + * (more probable symbol) in the highest bit (mask 0x80), and the
1.62 + * index into the probability estimation state machine table
1.63 + * in the lower bits (mask 0x7F).
1.64 + */
1.65 +
1.66 +#define DC_STAT_BINS 64
1.67 +#define AC_STAT_BINS 256
1.68 +
1.69 +/* NOTE: Uncomment the following #define if you want to use the
1.70 + * given formula for calculating the AC conditioning parameter Kx
1.71 + * for spectral selection progressive coding in section G.1.3.2
1.72 + * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4).
1.73 + * Although the spec and P&M authors claim that this "has proven
1.74 + * to give good results for 8 bit precision samples", I'm not
1.75 + * convinced yet that this is really beneficial.
1.76 + * Early tests gave only very marginal compression enhancements
1.77 + * (a few - around 5 or so - bytes even for very large files),
1.78 + * which would turn out rather negative if we'd suppress the
1.79 + * DAC (Define Arithmetic Conditioning) marker segments for
1.80 + * the default parameters in the future.
1.81 + * Note that currently the marker writing module emits 12-byte
1.82 + * DAC segments for a full-component scan in a color image.
1.83 + * This is not worth worrying about IMHO. However, since the
1.84 + * spec defines the default values to be used if the tables
1.85 + * are omitted (unlike Huffman tables, which are required
1.86 + * anyway), one might optimize this behaviour in the future,
1.87 + * and then it would be disadvantageous to use custom tables if
1.88 + * they don't provide sufficient gain to exceed the DAC size.
1.89 + *
1.90 + * On the other hand, I'd consider it as a reasonable result
1.91 + * that the conditioning has no significant influence on the
1.92 + * compression performance. This means that the basic
1.93 + * statistical model is already rather stable.
1.94 + *
1.95 + * Thus, at the moment, we use the default conditioning values
1.96 + * anyway, and do not use the custom formula.
1.97 + *
1.98 +#define CALCULATE_SPECTRAL_CONDITIONING
1.99 + */
1.100 +
1.101 +/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
1.102 + * We assume that int right shift is unsigned if INT32 right shift is,
1.103 + * which should be safe.
1.104 + */
1.105 +
1.106 +#ifdef RIGHT_SHIFT_IS_UNSIGNED
1.107 +#define ISHIFT_TEMPS int ishift_temp;
1.108 +#define IRIGHT_SHIFT(x,shft) \
1.109 + ((ishift_temp = (x)) < 0 ? \
1.110 + (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
1.111 + (ishift_temp >> (shft)))
1.112 +#else
1.113 +#define ISHIFT_TEMPS
1.114 +#define IRIGHT_SHIFT(x,shft) ((x) >> (shft))
1.115 +#endif
1.116 +
1.117 +
1.118 +LOCAL(void)
1.119 +emit_byte (int val, j_compress_ptr cinfo)
1.120 +/* Write next output byte; we do not support suspension in this module. */
1.121 +{
1.122 + struct jpeg_destination_mgr * dest = cinfo->dest;
1.123 +
1.124 + *dest->next_output_byte++ = (JOCTET) val;
1.125 + if (--dest->free_in_buffer == 0)
1.126 + if (! (*dest->empty_output_buffer) (cinfo))
1.127 + ERREXIT(cinfo, JERR_CANT_SUSPEND);
1.128 +}
1.129 +
1.130 +
1.131 +/*
1.132 + * Finish up at the end of an arithmetic-compressed scan.
1.133 + */
1.134 +
1.135 +METHODDEF(void)
1.136 +finish_pass (j_compress_ptr cinfo)
1.137 +{
1.138 + arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
1.139 + INT32 temp;
1.140 +
1.141 + /* Section D.1.8: Termination of encoding */
1.142 +
1.143 + /* Find the e->c in the coding interval with the largest
1.144 + * number of trailing zero bits */
1.145 + if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c)
1.146 + e->c = temp + 0x8000L;
1.147 + else
1.148 + e->c = temp;
1.149 + /* Send remaining bytes to output */
1.150 + e->c <<= e->ct;
1.151 + if (e->c & 0xF8000000L) {
1.152 + /* One final overflow has to be handled */
1.153 + if (e->buffer >= 0) {
1.154 + if (e->zc)
1.155 + do emit_byte(0x00, cinfo);
1.156 + while (--e->zc);
1.157 + emit_byte(e->buffer + 1, cinfo);
1.158 + if (e->buffer + 1 == 0xFF)
1.159 + emit_byte(0x00, cinfo);
1.160 + }
1.161 + e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
1.162 + e->sc = 0;
1.163 + } else {
1.164 + if (e->buffer == 0)
1.165 + ++e->zc;
1.166 + else if (e->buffer >= 0) {
1.167 + if (e->zc)
1.168 + do emit_byte(0x00, cinfo);
1.169 + while (--e->zc);
1.170 + emit_byte(e->buffer, cinfo);
1.171 + }
1.172 + if (e->sc) {
1.173 + if (e->zc)
1.174 + do emit_byte(0x00, cinfo);
1.175 + while (--e->zc);
1.176 + do {
1.177 + emit_byte(0xFF, cinfo);
1.178 + emit_byte(0x00, cinfo);
1.179 + } while (--e->sc);
1.180 + }
1.181 + }
1.182 + /* Output final bytes only if they are not 0x00 */
1.183 + if (e->c & 0x7FFF800L) {
1.184 + if (e->zc) /* output final pending zero bytes */
1.185 + do emit_byte(0x00, cinfo);
1.186 + while (--e->zc);
1.187 + emit_byte((e->c >> 19) & 0xFF, cinfo);
1.188 + if (((e->c >> 19) & 0xFF) == 0xFF)
1.189 + emit_byte(0x00, cinfo);
1.190 + if (e->c & 0x7F800L) {
1.191 + emit_byte((e->c >> 11) & 0xFF, cinfo);
1.192 + if (((e->c >> 11) & 0xFF) == 0xFF)
1.193 + emit_byte(0x00, cinfo);
1.194 + }
1.195 + }
1.196 +}
1.197 +
1.198 +
1.199 +/*
1.200 + * The core arithmetic encoding routine (common in JPEG and JBIG).
1.201 + * This needs to go as fast as possible.
1.202 + * Machine-dependent optimization facilities
1.203 + * are not utilized in this portable implementation.
1.204 + * However, this code should be fairly efficient and
1.205 + * may be a good base for further optimizations anyway.
1.206 + *
1.207 + * Parameter 'val' to be encoded may be 0 or 1 (binary decision).
1.208 + *
1.209 + * Note: I've added full "Pacman" termination support to the
1.210 + * byte output routines, which is equivalent to the optional
1.211 + * Discard_final_zeros procedure (Figure D.15) in the spec.
1.212 + * Thus, we always produce the shortest possible output
1.213 + * stream compliant to the spec (no trailing zero bytes,
1.214 + * except for FF stuffing).
1.215 + *
1.216 + * I've also introduced a new scheme for accessing
1.217 + * the probability estimation state machine table,
1.218 + * derived from Markus Kuhn's JBIG implementation.
1.219 + */
1.220 +
1.221 +LOCAL(void)
1.222 +arith_encode (j_compress_ptr cinfo, unsigned char *st, int val)
1.223 +{
1.224 + register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
1.225 + register unsigned char nl, nm;
1.226 + register INT32 qe, temp;
1.227 + register int sv;
1.228 +
1.229 + /* Fetch values from our compact representation of Table D.2:
1.230 + * Qe values and probability estimation state machine
1.231 + */
1.232 + sv = *st;
1.233 + qe = jpeg_aritab[sv & 0x7F]; /* => Qe_Value */
1.234 + nl = qe & 0xFF; qe >>= 8; /* Next_Index_LPS + Switch_MPS */
1.235 + nm = qe & 0xFF; qe >>= 8; /* Next_Index_MPS */
1.236 +
1.237 + /* Encode & estimation procedures per sections D.1.4 & D.1.5 */
1.238 + e->a -= qe;
1.239 + if (val != (sv >> 7)) {
1.240 + /* Encode the less probable symbol */
1.241 + if (e->a >= qe) {
1.242 + /* If the interval size (qe) for the less probable symbol (LPS)
1.243 + * is larger than the interval size for the MPS, then exchange
1.244 + * the two symbols for coding efficiency, otherwise code the LPS
1.245 + * as usual: */
1.246 + e->c += e->a;
1.247 + e->a = qe;
1.248 + }
1.249 + *st = (sv & 0x80) ^ nl; /* Estimate_after_LPS */
1.250 + } else {
1.251 + /* Encode the more probable symbol */
1.252 + if (e->a >= 0x8000L)
1.253 + return; /* A >= 0x8000 -> ready, no renormalization required */
1.254 + if (e->a < qe) {
1.255 + /* If the interval size (qe) for the less probable symbol (LPS)
1.256 + * is larger than the interval size for the MPS, then exchange
1.257 + * the two symbols for coding efficiency: */
1.258 + e->c += e->a;
1.259 + e->a = qe;
1.260 + }
1.261 + *st = (sv & 0x80) ^ nm; /* Estimate_after_MPS */
1.262 + }
1.263 +
1.264 + /* Renormalization & data output per section D.1.6 */
1.265 + do {
1.266 + e->a <<= 1;
1.267 + e->c <<= 1;
1.268 + if (--e->ct == 0) {
1.269 + /* Another byte is ready for output */
1.270 + temp = e->c >> 19;
1.271 + if (temp > 0xFF) {
1.272 + /* Handle overflow over all stacked 0xFF bytes */
1.273 + if (e->buffer >= 0) {
1.274 + if (e->zc)
1.275 + do emit_byte(0x00, cinfo);
1.276 + while (--e->zc);
1.277 + emit_byte(e->buffer + 1, cinfo);
1.278 + if (e->buffer + 1 == 0xFF)
1.279 + emit_byte(0x00, cinfo);
1.280 + }
1.281 + e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */
1.282 + e->sc = 0;
1.283 + /* Note: The 3 spacer bits in the C register guarantee
1.284 + * that the new buffer byte can't be 0xFF here
1.285 + * (see page 160 in the P&M JPEG book). */
1.286 + e->buffer = temp & 0xFF; /* new output byte, might overflow later */
1.287 + } else if (temp == 0xFF) {
1.288 + ++e->sc; /* stack 0xFF byte (which might overflow later) */
1.289 + } else {
1.290 + /* Output all stacked 0xFF bytes, they will not overflow any more */
1.291 + if (e->buffer == 0)
1.292 + ++e->zc;
1.293 + else if (e->buffer >= 0) {
1.294 + if (e->zc)
1.295 + do emit_byte(0x00, cinfo);
1.296 + while (--e->zc);
1.297 + emit_byte(e->buffer, cinfo);
1.298 + }
1.299 + if (e->sc) {
1.300 + if (e->zc)
1.301 + do emit_byte(0x00, cinfo);
1.302 + while (--e->zc);
1.303 + do {
1.304 + emit_byte(0xFF, cinfo);
1.305 + emit_byte(0x00, cinfo);
1.306 + } while (--e->sc);
1.307 + }
1.308 + e->buffer = temp & 0xFF; /* new output byte (can still overflow) */
1.309 + }
1.310 + e->c &= 0x7FFFFL;
1.311 + e->ct += 8;
1.312 + }
1.313 + } while (e->a < 0x8000L);
1.314 +}
1.315 +
1.316 +
1.317 +/*
1.318 + * Emit a restart marker & resynchronize predictions.
1.319 + */
1.320 +
1.321 +LOCAL(void)
1.322 +emit_restart (j_compress_ptr cinfo, int restart_num)
1.323 +{
1.324 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.325 + int ci;
1.326 + jpeg_component_info * compptr;
1.327 +
1.328 + finish_pass(cinfo);
1.329 +
1.330 + emit_byte(0xFF, cinfo);
1.331 + emit_byte(JPEG_RST0 + restart_num, cinfo);
1.332 +
1.333 + /* Re-initialize statistics areas */
1.334 + for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1.335 + compptr = cinfo->cur_comp_info[ci];
1.336 + /* DC needs no table for refinement scan */
1.337 + if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
1.338 + MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
1.339 + /* Reset DC predictions to 0 */
1.340 + entropy->last_dc_val[ci] = 0;
1.341 + entropy->dc_context[ci] = 0;
1.342 + }
1.343 + /* AC needs no table when not present */
1.344 + if (cinfo->progressive_mode == 0 || cinfo->Se) {
1.345 + MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
1.346 + }
1.347 + }
1.348 +
1.349 + /* Reset arithmetic encoding variables */
1.350 + entropy->c = 0;
1.351 + entropy->a = 0x10000L;
1.352 + entropy->sc = 0;
1.353 + entropy->zc = 0;
1.354 + entropy->ct = 11;
1.355 + entropy->buffer = -1; /* empty */
1.356 +}
1.357 +
1.358 +
1.359 +/*
1.360 + * MCU encoding for DC initial scan (either spectral selection,
1.361 + * or first pass of successive approximation).
1.362 + */
1.363 +
1.364 +METHODDEF(boolean)
1.365 +encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.366 +{
1.367 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.368 + JBLOCKROW block;
1.369 + unsigned char *st;
1.370 + int blkn, ci, tbl;
1.371 + int v, v2, m;
1.372 + ISHIFT_TEMPS
1.373 +
1.374 + /* Emit restart marker if needed */
1.375 + if (cinfo->restart_interval) {
1.376 + if (entropy->restarts_to_go == 0) {
1.377 + emit_restart(cinfo, entropy->next_restart_num);
1.378 + entropy->restarts_to_go = cinfo->restart_interval;
1.379 + entropy->next_restart_num++;
1.380 + entropy->next_restart_num &= 7;
1.381 + }
1.382 + entropy->restarts_to_go--;
1.383 + }
1.384 +
1.385 + /* Encode the MCU data blocks */
1.386 + for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1.387 + block = MCU_data[blkn];
1.388 + ci = cinfo->MCU_membership[blkn];
1.389 + tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
1.390 +
1.391 + /* Compute the DC value after the required point transform by Al.
1.392 + * This is simply an arithmetic right shift.
1.393 + */
1.394 + m = IRIGHT_SHIFT((int) ((*block)[0]), cinfo->Al);
1.395 +
1.396 + /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
1.397 +
1.398 + /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
1.399 + st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
1.400 +
1.401 + /* Figure F.4: Encode_DC_DIFF */
1.402 + if ((v = m - entropy->last_dc_val[ci]) == 0) {
1.403 + arith_encode(cinfo, st, 0);
1.404 + entropy->dc_context[ci] = 0; /* zero diff category */
1.405 + } else {
1.406 + entropy->last_dc_val[ci] = m;
1.407 + arith_encode(cinfo, st, 1);
1.408 + /* Figure F.6: Encoding nonzero value v */
1.409 + /* Figure F.7: Encoding the sign of v */
1.410 + if (v > 0) {
1.411 + arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
1.412 + st += 2; /* Table F.4: SP = S0 + 2 */
1.413 + entropy->dc_context[ci] = 4; /* small positive diff category */
1.414 + } else {
1.415 + v = -v;
1.416 + arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
1.417 + st += 3; /* Table F.4: SN = S0 + 3 */
1.418 + entropy->dc_context[ci] = 8; /* small negative diff category */
1.419 + }
1.420 + /* Figure F.8: Encoding the magnitude category of v */
1.421 + m = 0;
1.422 + if (v -= 1) {
1.423 + arith_encode(cinfo, st, 1);
1.424 + m = 1;
1.425 + v2 = v;
1.426 + st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
1.427 + while (v2 >>= 1) {
1.428 + arith_encode(cinfo, st, 1);
1.429 + m <<= 1;
1.430 + st += 1;
1.431 + }
1.432 + }
1.433 + arith_encode(cinfo, st, 0);
1.434 + /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
1.435 + if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
1.436 + entropy->dc_context[ci] = 0; /* zero diff category */
1.437 + else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
1.438 + entropy->dc_context[ci] += 8; /* large diff category */
1.439 + /* Figure F.9: Encoding the magnitude bit pattern of v */
1.440 + st += 14;
1.441 + while (m >>= 1)
1.442 + arith_encode(cinfo, st, (m & v) ? 1 : 0);
1.443 + }
1.444 + }
1.445 +
1.446 + return TRUE;
1.447 +}
1.448 +
1.449 +
1.450 +/*
1.451 + * MCU encoding for AC initial scan (either spectral selection,
1.452 + * or first pass of successive approximation).
1.453 + */
1.454 +
1.455 +METHODDEF(boolean)
1.456 +encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.457 +{
1.458 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.459 + JBLOCKROW block;
1.460 + unsigned char *st;
1.461 + int tbl, k, ke;
1.462 + int v, v2, m;
1.463 +
1.464 + /* Emit restart marker if needed */
1.465 + if (cinfo->restart_interval) {
1.466 + if (entropy->restarts_to_go == 0) {
1.467 + emit_restart(cinfo, entropy->next_restart_num);
1.468 + entropy->restarts_to_go = cinfo->restart_interval;
1.469 + entropy->next_restart_num++;
1.470 + entropy->next_restart_num &= 7;
1.471 + }
1.472 + entropy->restarts_to_go--;
1.473 + }
1.474 +
1.475 + /* Encode the MCU data block */
1.476 + block = MCU_data[0];
1.477 + tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
1.478 +
1.479 + /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
1.480 +
1.481 + /* Establish EOB (end-of-block) index */
1.482 + for (ke = cinfo->Se; ke > 0; ke--)
1.483 + /* We must apply the point transform by Al. For AC coefficients this
1.484 + * is an integer division with rounding towards 0. To do this portably
1.485 + * in C, we shift after obtaining the absolute value.
1.486 + */
1.487 + if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
1.488 + if (v >>= cinfo->Al) break;
1.489 + } else {
1.490 + v = -v;
1.491 + if (v >>= cinfo->Al) break;
1.492 + }
1.493 +
1.494 + /* Figure F.5: Encode_AC_Coefficients */
1.495 + for (k = cinfo->Ss; k <= ke; k++) {
1.496 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.497 + arith_encode(cinfo, st, 0); /* EOB decision */
1.498 + for (;;) {
1.499 + if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
1.500 + if (v >>= cinfo->Al) {
1.501 + arith_encode(cinfo, st + 1, 1);
1.502 + arith_encode(cinfo, entropy->fixed_bin, 0);
1.503 + break;
1.504 + }
1.505 + } else {
1.506 + v = -v;
1.507 + if (v >>= cinfo->Al) {
1.508 + arith_encode(cinfo, st + 1, 1);
1.509 + arith_encode(cinfo, entropy->fixed_bin, 1);
1.510 + break;
1.511 + }
1.512 + }
1.513 + arith_encode(cinfo, st + 1, 0); st += 3; k++;
1.514 + }
1.515 + st += 2;
1.516 + /* Figure F.8: Encoding the magnitude category of v */
1.517 + m = 0;
1.518 + if (v -= 1) {
1.519 + arith_encode(cinfo, st, 1);
1.520 + m = 1;
1.521 + v2 = v;
1.522 + if (v2 >>= 1) {
1.523 + arith_encode(cinfo, st, 1);
1.524 + m <<= 1;
1.525 + st = entropy->ac_stats[tbl] +
1.526 + (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
1.527 + while (v2 >>= 1) {
1.528 + arith_encode(cinfo, st, 1);
1.529 + m <<= 1;
1.530 + st += 1;
1.531 + }
1.532 + }
1.533 + }
1.534 + arith_encode(cinfo, st, 0);
1.535 + /* Figure F.9: Encoding the magnitude bit pattern of v */
1.536 + st += 14;
1.537 + while (m >>= 1)
1.538 + arith_encode(cinfo, st, (m & v) ? 1 : 0);
1.539 + }
1.540 + /* Encode EOB decision only if k <= cinfo->Se */
1.541 + if (k <= cinfo->Se) {
1.542 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.543 + arith_encode(cinfo, st, 1);
1.544 + }
1.545 +
1.546 + return TRUE;
1.547 +}
1.548 +
1.549 +
1.550 +/*
1.551 + * MCU encoding for DC successive approximation refinement scan.
1.552 + */
1.553 +
1.554 +METHODDEF(boolean)
1.555 +encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.556 +{
1.557 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.558 + unsigned char *st;
1.559 + int Al, blkn;
1.560 +
1.561 + /* Emit restart marker if needed */
1.562 + if (cinfo->restart_interval) {
1.563 + if (entropy->restarts_to_go == 0) {
1.564 + emit_restart(cinfo, entropy->next_restart_num);
1.565 + entropy->restarts_to_go = cinfo->restart_interval;
1.566 + entropy->next_restart_num++;
1.567 + entropy->next_restart_num &= 7;
1.568 + }
1.569 + entropy->restarts_to_go--;
1.570 + }
1.571 +
1.572 + st = entropy->fixed_bin; /* use fixed probability estimation */
1.573 + Al = cinfo->Al;
1.574 +
1.575 + /* Encode the MCU data blocks */
1.576 + for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1.577 + /* We simply emit the Al'th bit of the DC coefficient value. */
1.578 + arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1);
1.579 + }
1.580 +
1.581 + return TRUE;
1.582 +}
1.583 +
1.584 +
1.585 +/*
1.586 + * MCU encoding for AC successive approximation refinement scan.
1.587 + */
1.588 +
1.589 +METHODDEF(boolean)
1.590 +encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.591 +{
1.592 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.593 + JBLOCKROW block;
1.594 + unsigned char *st;
1.595 + int tbl, k, ke, kex;
1.596 + int v;
1.597 +
1.598 + /* Emit restart marker if needed */
1.599 + if (cinfo->restart_interval) {
1.600 + if (entropy->restarts_to_go == 0) {
1.601 + emit_restart(cinfo, entropy->next_restart_num);
1.602 + entropy->restarts_to_go = cinfo->restart_interval;
1.603 + entropy->next_restart_num++;
1.604 + entropy->next_restart_num &= 7;
1.605 + }
1.606 + entropy->restarts_to_go--;
1.607 + }
1.608 +
1.609 + /* Encode the MCU data block */
1.610 + block = MCU_data[0];
1.611 + tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
1.612 +
1.613 + /* Section G.1.3.3: Encoding of AC coefficients */
1.614 +
1.615 + /* Establish EOB (end-of-block) index */
1.616 + for (ke = cinfo->Se; ke > 0; ke--)
1.617 + /* We must apply the point transform by Al. For AC coefficients this
1.618 + * is an integer division with rounding towards 0. To do this portably
1.619 + * in C, we shift after obtaining the absolute value.
1.620 + */
1.621 + if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) {
1.622 + if (v >>= cinfo->Al) break;
1.623 + } else {
1.624 + v = -v;
1.625 + if (v >>= cinfo->Al) break;
1.626 + }
1.627 +
1.628 + /* Establish EOBx (previous stage end-of-block) index */
1.629 + for (kex = ke; kex > 0; kex--)
1.630 + if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) {
1.631 + if (v >>= cinfo->Ah) break;
1.632 + } else {
1.633 + v = -v;
1.634 + if (v >>= cinfo->Ah) break;
1.635 + }
1.636 +
1.637 + /* Figure G.10: Encode_AC_Coefficients_SA */
1.638 + for (k = cinfo->Ss; k <= ke; k++) {
1.639 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.640 + if (k > kex)
1.641 + arith_encode(cinfo, st, 0); /* EOB decision */
1.642 + for (;;) {
1.643 + if ((v = (*block)[jpeg_natural_order[k]]) >= 0) {
1.644 + if (v >>= cinfo->Al) {
1.645 + if (v >> 1) /* previously nonzero coef */
1.646 + arith_encode(cinfo, st + 2, (v & 1));
1.647 + else { /* newly nonzero coef */
1.648 + arith_encode(cinfo, st + 1, 1);
1.649 + arith_encode(cinfo, entropy->fixed_bin, 0);
1.650 + }
1.651 + break;
1.652 + }
1.653 + } else {
1.654 + v = -v;
1.655 + if (v >>= cinfo->Al) {
1.656 + if (v >> 1) /* previously nonzero coef */
1.657 + arith_encode(cinfo, st + 2, (v & 1));
1.658 + else { /* newly nonzero coef */
1.659 + arith_encode(cinfo, st + 1, 1);
1.660 + arith_encode(cinfo, entropy->fixed_bin, 1);
1.661 + }
1.662 + break;
1.663 + }
1.664 + }
1.665 + arith_encode(cinfo, st + 1, 0); st += 3; k++;
1.666 + }
1.667 + }
1.668 + /* Encode EOB decision only if k <= cinfo->Se */
1.669 + if (k <= cinfo->Se) {
1.670 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.671 + arith_encode(cinfo, st, 1);
1.672 + }
1.673 +
1.674 + return TRUE;
1.675 +}
1.676 +
1.677 +
1.678 +/*
1.679 + * Encode and output one MCU's worth of arithmetic-compressed coefficients.
1.680 + */
1.681 +
1.682 +METHODDEF(boolean)
1.683 +encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.684 +{
1.685 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.686 + jpeg_component_info * compptr;
1.687 + JBLOCKROW block;
1.688 + unsigned char *st;
1.689 + int blkn, ci, tbl, k, ke;
1.690 + int v, v2, m;
1.691 +
1.692 + /* Emit restart marker if needed */
1.693 + if (cinfo->restart_interval) {
1.694 + if (entropy->restarts_to_go == 0) {
1.695 + emit_restart(cinfo, entropy->next_restart_num);
1.696 + entropy->restarts_to_go = cinfo->restart_interval;
1.697 + entropy->next_restart_num++;
1.698 + entropy->next_restart_num &= 7;
1.699 + }
1.700 + entropy->restarts_to_go--;
1.701 + }
1.702 +
1.703 + /* Encode the MCU data blocks */
1.704 + for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1.705 + block = MCU_data[blkn];
1.706 + ci = cinfo->MCU_membership[blkn];
1.707 + compptr = cinfo->cur_comp_info[ci];
1.708 +
1.709 + /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */
1.710 +
1.711 + tbl = compptr->dc_tbl_no;
1.712 +
1.713 + /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
1.714 + st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
1.715 +
1.716 + /* Figure F.4: Encode_DC_DIFF */
1.717 + if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) {
1.718 + arith_encode(cinfo, st, 0);
1.719 + entropy->dc_context[ci] = 0; /* zero diff category */
1.720 + } else {
1.721 + entropy->last_dc_val[ci] = (*block)[0];
1.722 + arith_encode(cinfo, st, 1);
1.723 + /* Figure F.6: Encoding nonzero value v */
1.724 + /* Figure F.7: Encoding the sign of v */
1.725 + if (v > 0) {
1.726 + arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */
1.727 + st += 2; /* Table F.4: SP = S0 + 2 */
1.728 + entropy->dc_context[ci] = 4; /* small positive diff category */
1.729 + } else {
1.730 + v = -v;
1.731 + arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */
1.732 + st += 3; /* Table F.4: SN = S0 + 3 */
1.733 + entropy->dc_context[ci] = 8; /* small negative diff category */
1.734 + }
1.735 + /* Figure F.8: Encoding the magnitude category of v */
1.736 + m = 0;
1.737 + if (v -= 1) {
1.738 + arith_encode(cinfo, st, 1);
1.739 + m = 1;
1.740 + v2 = v;
1.741 + st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */
1.742 + while (v2 >>= 1) {
1.743 + arith_encode(cinfo, st, 1);
1.744 + m <<= 1;
1.745 + st += 1;
1.746 + }
1.747 + }
1.748 + arith_encode(cinfo, st, 0);
1.749 + /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
1.750 + if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
1.751 + entropy->dc_context[ci] = 0; /* zero diff category */
1.752 + else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
1.753 + entropy->dc_context[ci] += 8; /* large diff category */
1.754 + /* Figure F.9: Encoding the magnitude bit pattern of v */
1.755 + st += 14;
1.756 + while (m >>= 1)
1.757 + arith_encode(cinfo, st, (m & v) ? 1 : 0);
1.758 + }
1.759 +
1.760 + /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */
1.761 +
1.762 + tbl = compptr->ac_tbl_no;
1.763 +
1.764 + /* Establish EOB (end-of-block) index */
1.765 + for (ke = DCTSIZE2 - 1; ke > 0; ke--)
1.766 + if ((*block)[jpeg_natural_order[ke]]) break;
1.767 +
1.768 + /* Figure F.5: Encode_AC_Coefficients */
1.769 + for (k = 1; k <= ke; k++) {
1.770 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.771 + arith_encode(cinfo, st, 0); /* EOB decision */
1.772 + while ((v = (*block)[jpeg_natural_order[k]]) == 0) {
1.773 + arith_encode(cinfo, st + 1, 0); st += 3; k++;
1.774 + }
1.775 + arith_encode(cinfo, st + 1, 1);
1.776 + /* Figure F.6: Encoding nonzero value v */
1.777 + /* Figure F.7: Encoding the sign of v */
1.778 + if (v > 0) {
1.779 + arith_encode(cinfo, entropy->fixed_bin, 0);
1.780 + } else {
1.781 + v = -v;
1.782 + arith_encode(cinfo, entropy->fixed_bin, 1);
1.783 + }
1.784 + st += 2;
1.785 + /* Figure F.8: Encoding the magnitude category of v */
1.786 + m = 0;
1.787 + if (v -= 1) {
1.788 + arith_encode(cinfo, st, 1);
1.789 + m = 1;
1.790 + v2 = v;
1.791 + if (v2 >>= 1) {
1.792 + arith_encode(cinfo, st, 1);
1.793 + m <<= 1;
1.794 + st = entropy->ac_stats[tbl] +
1.795 + (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
1.796 + while (v2 >>= 1) {
1.797 + arith_encode(cinfo, st, 1);
1.798 + m <<= 1;
1.799 + st += 1;
1.800 + }
1.801 + }
1.802 + }
1.803 + arith_encode(cinfo, st, 0);
1.804 + /* Figure F.9: Encoding the magnitude bit pattern of v */
1.805 + st += 14;
1.806 + while (m >>= 1)
1.807 + arith_encode(cinfo, st, (m & v) ? 1 : 0);
1.808 + }
1.809 + /* Encode EOB decision only if k <= DCTSIZE2 - 1 */
1.810 + if (k <= DCTSIZE2 - 1) {
1.811 + st = entropy->ac_stats[tbl] + 3 * (k - 1);
1.812 + arith_encode(cinfo, st, 1);
1.813 + }
1.814 + }
1.815 +
1.816 + return TRUE;
1.817 +}
1.818 +
1.819 +
1.820 +/*
1.821 + * Initialize for an arithmetic-compressed scan.
1.822 + */
1.823 +
1.824 +METHODDEF(void)
1.825 +start_pass (j_compress_ptr cinfo, boolean gather_statistics)
1.826 +{
1.827 + arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
1.828 + int ci, tbl;
1.829 + jpeg_component_info * compptr;
1.830 +
1.831 + if (gather_statistics)
1.832 + /* Make sure to avoid that in the master control logic!
1.833 + * We are fully adaptive here and need no extra
1.834 + * statistics gathering pass!
1.835 + */
1.836 + ERREXIT(cinfo, JERR_NOT_COMPILED);
1.837 +
1.838 + /* We assume jcmaster.c already validated the progressive scan parameters. */
1.839 +
1.840 + /* Select execution routines */
1.841 + if (cinfo->progressive_mode) {
1.842 + if (cinfo->Ah == 0) {
1.843 + if (cinfo->Ss == 0)
1.844 + entropy->pub.encode_mcu = encode_mcu_DC_first;
1.845 + else
1.846 + entropy->pub.encode_mcu = encode_mcu_AC_first;
1.847 + } else {
1.848 + if (cinfo->Ss == 0)
1.849 + entropy->pub.encode_mcu = encode_mcu_DC_refine;
1.850 + else
1.851 + entropy->pub.encode_mcu = encode_mcu_AC_refine;
1.852 + }
1.853 + } else
1.854 + entropy->pub.encode_mcu = encode_mcu;
1.855 +
1.856 + /* Allocate & initialize requested statistics areas */
1.857 + for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1.858 + compptr = cinfo->cur_comp_info[ci];
1.859 + /* DC needs no table for refinement scan */
1.860 + if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
1.861 + tbl = compptr->dc_tbl_no;
1.862 + if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
1.863 + ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
1.864 + if (entropy->dc_stats[tbl] == NULL)
1.865 + entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
1.866 + ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
1.867 + MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
1.868 + /* Initialize DC predictions to 0 */
1.869 + entropy->last_dc_val[ci] = 0;
1.870 + entropy->dc_context[ci] = 0;
1.871 + }
1.872 + /* AC needs no table when not present */
1.873 + if (cinfo->progressive_mode == 0 || cinfo->Se) {
1.874 + tbl = compptr->ac_tbl_no;
1.875 + if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
1.876 + ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
1.877 + if (entropy->ac_stats[tbl] == NULL)
1.878 + entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
1.879 + ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
1.880 + MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
1.881 +#ifdef CALCULATE_SPECTRAL_CONDITIONING
1.882 + if (cinfo->progressive_mode)
1.883 + /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */
1.884 + cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4);
1.885 +#endif
1.886 + }
1.887 + }
1.888 +
1.889 + /* Initialize arithmetic encoding variables */
1.890 + entropy->c = 0;
1.891 + entropy->a = 0x10000L;
1.892 + entropy->sc = 0;
1.893 + entropy->zc = 0;
1.894 + entropy->ct = 11;
1.895 + entropy->buffer = -1; /* empty */
1.896 +
1.897 + /* Initialize restart stuff */
1.898 + entropy->restarts_to_go = cinfo->restart_interval;
1.899 + entropy->next_restart_num = 0;
1.900 +}
1.901 +
1.902 +
1.903 +/*
1.904 + * Module initialization routine for arithmetic entropy encoding.
1.905 + */
1.906 +
1.907 +GLOBAL(void)
1.908 +jinit_arith_encoder (j_compress_ptr cinfo)
1.909 +{
1.910 + arith_entropy_ptr entropy;
1.911 + int i;
1.912 +
1.913 + entropy = (arith_entropy_ptr)
1.914 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1.915 + SIZEOF(arith_entropy_encoder));
1.916 + cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1.917 + entropy->pub.start_pass = start_pass;
1.918 + entropy->pub.finish_pass = finish_pass;
1.919 +
1.920 + /* Mark tables unallocated */
1.921 + for (i = 0; i < NUM_ARITH_TBLS; i++) {
1.922 + entropy->dc_stats[i] = NULL;
1.923 + entropy->ac_stats[i] = NULL;
1.924 + }
1.925 +
1.926 + /* Initialize index for fixed probability estimation */
1.927 + entropy->fixed_bin[0] = 113;
1.928 +}
