src/3rdparty/libjpeg/jdarith.c
changeset 30 5dc02b23752f
equal deleted inserted replaced
29:b72c6db6890b 30:5dc02b23752f
       
     1 /*
       
     2  * jdarith.c
       
     3  *
       
     4  * Developed 1997-2009 by Guido Vollbeding.
       
     5  * This file is part of the Independent JPEG Group's software.
       
     6  * For conditions of distribution and use, see the accompanying README file.
       
     7  *
       
     8  * This file contains portable arithmetic entropy decoding routines for JPEG
       
     9  * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81).
       
    10  *
       
    11  * Both sequential and progressive modes are supported in this single module.
       
    12  *
       
    13  * Suspension is not currently supported in this module.
       
    14  */
       
    15 
       
    16 #define JPEG_INTERNALS
       
    17 #include "jinclude.h"
       
    18 #include "jpeglib.h"
       
    19 
       
    20 
       
    21 /* Expanded entropy decoder object for arithmetic decoding. */
       
    22 
       
    23 typedef struct {
       
    24   struct jpeg_entropy_decoder pub; /* public fields */
       
    25 
       
    26   INT32 c;       /* C register, base of coding interval + input bit buffer */
       
    27   INT32 a;               /* A register, normalized size of coding interval */
       
    28   int ct;     /* bit shift counter, # of bits left in bit buffer part of C */
       
    29                                                          /* init: ct = -16 */
       
    30                                                          /* run: ct = 0..7 */
       
    31                                                          /* error: ct = -1 */
       
    32   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
       
    33   int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */
       
    34 
       
    35   unsigned int restarts_to_go;	/* MCUs left in this restart interval */
       
    36 
       
    37   /* Pointers to statistics areas (these workspaces have image lifespan) */
       
    38   unsigned char * dc_stats[NUM_ARITH_TBLS];
       
    39   unsigned char * ac_stats[NUM_ARITH_TBLS];
       
    40 
       
    41   /* Statistics bin for coding with fixed probability 0.5 */
       
    42   unsigned char fixed_bin[4];
       
    43 } arith_entropy_decoder;
       
    44 
       
    45 typedef arith_entropy_decoder * arith_entropy_ptr;
       
    46 
       
    47 /* The following two definitions specify the allocation chunk size
       
    48  * for the statistics area.
       
    49  * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least
       
    50  * 49 statistics bins for DC, and 245 statistics bins for AC coding.
       
    51  *
       
    52  * We use a compact representation with 1 byte per statistics bin,
       
    53  * thus the numbers directly represent byte sizes.
       
    54  * This 1 byte per statistics bin contains the meaning of the MPS
       
    55  * (more probable symbol) in the highest bit (mask 0x80), and the
       
    56  * index into the probability estimation state machine table
       
    57  * in the lower bits (mask 0x7F).
       
    58  */
       
    59 
       
    60 #define DC_STAT_BINS 64
       
    61 #define AC_STAT_BINS 256
       
    62 
       
    63 
       
    64 LOCAL(int)
       
    65 get_byte (j_decompress_ptr cinfo)
       
    66 /* Read next input byte; we do not support suspension in this module. */
       
    67 {
       
    68   struct jpeg_source_mgr * src = cinfo->src;
       
    69 
       
    70   if (src->bytes_in_buffer == 0)
       
    71     if (! (*src->fill_input_buffer) (cinfo))
       
    72       ERREXIT(cinfo, JERR_CANT_SUSPEND);
       
    73   src->bytes_in_buffer--;
       
    74   return GETJOCTET(*src->next_input_byte++);
       
    75 }
       
    76 
       
    77 
       
    78 /*
       
    79  * The core arithmetic decoding routine (common in JPEG and JBIG).
       
    80  * This needs to go as fast as possible.
       
    81  * Machine-dependent optimization facilities
       
    82  * are not utilized in this portable implementation.
       
    83  * However, this code should be fairly efficient and
       
    84  * may be a good base for further optimizations anyway.
       
    85  *
       
    86  * Return value is 0 or 1 (binary decision).
       
    87  *
       
    88  * Note: I've changed the handling of the code base & bit
       
    89  * buffer register C compared to other implementations
       
    90  * based on the standards layout & procedures.
       
    91  * While it also contains both the actual base of the
       
    92  * coding interval (16 bits) and the next-bits buffer,
       
    93  * the cut-point between these two parts is floating
       
    94  * (instead of fixed) with the bit shift counter CT.
       
    95  * Thus, we also need only one (variable instead of
       
    96  * fixed size) shift for the LPS/MPS decision, and
       
    97  * we can get away with any renormalization update
       
    98  * of C (except for new data insertion, of course).
       
    99  *
       
   100  * I've also introduced a new scheme for accessing
       
   101  * the probability estimation state machine table,
       
   102  * derived from Markus Kuhn's JBIG implementation.
       
   103  */
       
   104 
       
   105 LOCAL(int)
       
   106 arith_decode (j_decompress_ptr cinfo, unsigned char *st)
       
   107 {
       
   108   register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy;
       
   109   register unsigned char nl, nm;
       
   110   register INT32 qe, temp;
       
   111   register int sv, data;
       
   112 
       
   113   /* Renormalization & data input per section D.2.6 */
       
   114   while (e->a < 0x8000L) {
       
   115     if (--e->ct < 0) {
       
   116       /* Need to fetch next data byte */
       
   117       if (cinfo->unread_marker)
       
   118 	data = 0;		/* stuff zero data */
       
   119       else {
       
   120 	data = get_byte(cinfo);	/* read next input byte */
       
   121 	if (data == 0xFF) {	/* zero stuff or marker code */
       
   122 	  do data = get_byte(cinfo);
       
   123 	  while (data == 0xFF);	/* swallow extra 0xFF bytes */
       
   124 	  if (data == 0)
       
   125 	    data = 0xFF;	/* discard stuffed zero byte */
       
   126 	  else {
       
   127 	    /* Note: Different from the Huffman decoder, hitting
       
   128 	     * a marker while processing the compressed data
       
   129 	     * segment is legal in arithmetic coding.
       
   130 	     * The convention is to supply zero data
       
   131 	     * then until decoding is complete.
       
   132 	     */
       
   133 	    cinfo->unread_marker = data;
       
   134 	    data = 0;
       
   135 	  }
       
   136 	}
       
   137       }
       
   138       e->c = (e->c << 8) | data; /* insert data into C register */
       
   139       if ((e->ct += 8) < 0)	 /* update bit shift counter */
       
   140 	/* Need more initial bytes */
       
   141 	if (++e->ct == 0)
       
   142 	  /* Got 2 initial bytes -> re-init A and exit loop */
       
   143 	  e->a = 0x8000L; /* => e->a = 0x10000L after loop exit */
       
   144     }
       
   145     e->a <<= 1;
       
   146   }
       
   147 
       
   148   /* Fetch values from our compact representation of Table D.2:
       
   149    * Qe values and probability estimation state machine
       
   150    */
       
   151   sv = *st;
       
   152   qe = jpeg_aritab[sv & 0x7F];	/* => Qe_Value */
       
   153   nl = qe & 0xFF; qe >>= 8;	/* Next_Index_LPS + Switch_MPS */
       
   154   nm = qe & 0xFF; qe >>= 8;	/* Next_Index_MPS */
       
   155 
       
   156   /* Decode & estimation procedures per sections D.2.4 & D.2.5 */
       
   157   temp = e->a - qe;
       
   158   e->a = temp;
       
   159   temp <<= e->ct;
       
   160   if (e->c >= temp) {
       
   161     e->c -= temp;
       
   162     /* Conditional LPS (less probable symbol) exchange */
       
   163     if (e->a < qe) {
       
   164       e->a = qe;
       
   165       *st = (sv & 0x80) ^ nm;	/* Estimate_after_MPS */
       
   166     } else {
       
   167       e->a = qe;
       
   168       *st = (sv & 0x80) ^ nl;	/* Estimate_after_LPS */
       
   169       sv ^= 0x80;		/* Exchange LPS/MPS */
       
   170     }
       
   171   } else if (e->a < 0x8000L) {
       
   172     /* Conditional MPS (more probable symbol) exchange */
       
   173     if (e->a < qe) {
       
   174       *st = (sv & 0x80) ^ nl;	/* Estimate_after_LPS */
       
   175       sv ^= 0x80;		/* Exchange LPS/MPS */
       
   176     } else {
       
   177       *st = (sv & 0x80) ^ nm;	/* Estimate_after_MPS */
       
   178     }
       
   179   }
       
   180 
       
   181   return sv >> 7;
       
   182 }
       
   183 
       
   184 
       
   185 /*
       
   186  * Check for a restart marker & resynchronize decoder.
       
   187  */
       
   188 
       
   189 LOCAL(void)
       
   190 process_restart (j_decompress_ptr cinfo)
       
   191 {
       
   192   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   193   int ci;
       
   194   jpeg_component_info * compptr;
       
   195 
       
   196   /* Advance past the RSTn marker */
       
   197   if (! (*cinfo->marker->read_restart_marker) (cinfo))
       
   198     ERREXIT(cinfo, JERR_CANT_SUSPEND);
       
   199 
       
   200   /* Re-initialize statistics areas */
       
   201   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
       
   202     compptr = cinfo->cur_comp_info[ci];
       
   203     if (! cinfo->progressive_mode || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
       
   204       MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS);
       
   205       /* Reset DC predictions to 0 */
       
   206       entropy->last_dc_val[ci] = 0;
       
   207       entropy->dc_context[ci] = 0;
       
   208     }
       
   209     if ((! cinfo->progressive_mode && cinfo->lim_Se) ||
       
   210 	(cinfo->progressive_mode && cinfo->Ss)) {
       
   211       MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS);
       
   212     }
       
   213   }
       
   214 
       
   215   /* Reset arithmetic decoding variables */
       
   216   entropy->c = 0;
       
   217   entropy->a = 0;
       
   218   entropy->ct = -16;	/* force reading 2 initial bytes to fill C */
       
   219 
       
   220   /* Reset restart counter */
       
   221   entropy->restarts_to_go = cinfo->restart_interval;
       
   222 }
       
   223 
       
   224 
       
   225 /*
       
   226  * Arithmetic MCU decoding.
       
   227  * Each of these routines decodes and returns one MCU's worth of
       
   228  * arithmetic-compressed coefficients.
       
   229  * The coefficients are reordered from zigzag order into natural array order,
       
   230  * but are not dequantized.
       
   231  *
       
   232  * The i'th block of the MCU is stored into the block pointed to by
       
   233  * MCU_data[i].  WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
       
   234  */
       
   235 
       
   236 /*
       
   237  * MCU decoding for DC initial scan (either spectral selection,
       
   238  * or first pass of successive approximation).
       
   239  */
       
   240 
       
   241 METHODDEF(boolean)
       
   242 decode_mcu_DC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
       
   243 {
       
   244   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   245   JBLOCKROW block;
       
   246   unsigned char *st;
       
   247   int blkn, ci, tbl, sign;
       
   248   int v, m;
       
   249 
       
   250   /* Process restart marker if needed */
       
   251   if (cinfo->restart_interval) {
       
   252     if (entropy->restarts_to_go == 0)
       
   253       process_restart(cinfo);
       
   254     entropy->restarts_to_go--;
       
   255   }
       
   256 
       
   257   if (entropy->ct == -1) return TRUE;	/* if error do nothing */
       
   258 
       
   259   /* Outer loop handles each block in the MCU */
       
   260 
       
   261   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
       
   262     block = MCU_data[blkn];
       
   263     ci = cinfo->MCU_membership[blkn];
       
   264     tbl = cinfo->cur_comp_info[ci]->dc_tbl_no;
       
   265 
       
   266     /* Sections F.2.4.1 & F.1.4.4.1: Decoding of DC coefficients */
       
   267 
       
   268     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
       
   269     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
       
   270 
       
   271     /* Figure F.19: Decode_DC_DIFF */
       
   272     if (arith_decode(cinfo, st) == 0)
       
   273       entropy->dc_context[ci] = 0;
       
   274     else {
       
   275       /* Figure F.21: Decoding nonzero value v */
       
   276       /* Figure F.22: Decoding the sign of v */
       
   277       sign = arith_decode(cinfo, st + 1);
       
   278       st += 2; st += sign;
       
   279       /* Figure F.23: Decoding the magnitude category of v */
       
   280       if ((m = arith_decode(cinfo, st)) != 0) {
       
   281 	st = entropy->dc_stats[tbl] + 20;	/* Table F.4: X1 = 20 */
       
   282 	while (arith_decode(cinfo, st)) {
       
   283 	  if ((m <<= 1) == 0x8000) {
       
   284 	    WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   285 	    entropy->ct = -1;			/* magnitude overflow */
       
   286 	    return TRUE;
       
   287 	  }
       
   288 	  st += 1;
       
   289 	}
       
   290       }
       
   291       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
       
   292       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
       
   293 	entropy->dc_context[ci] = 0;		   /* zero diff category */
       
   294       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
       
   295 	entropy->dc_context[ci] = 12 + (sign * 4); /* large diff category */
       
   296       else
       
   297 	entropy->dc_context[ci] = 4 + (sign * 4);  /* small diff category */
       
   298       v = m;
       
   299       /* Figure F.24: Decoding the magnitude bit pattern of v */
       
   300       st += 14;
       
   301       while (m >>= 1)
       
   302 	if (arith_decode(cinfo, st)) v |= m;
       
   303       v += 1; if (sign) v = -v;
       
   304       entropy->last_dc_val[ci] += v;
       
   305     }
       
   306 
       
   307     /* Scale and output the DC coefficient (assumes jpeg_natural_order[0]=0) */
       
   308     (*block)[0] = (JCOEF) (entropy->last_dc_val[ci] << cinfo->Al);
       
   309   }
       
   310 
       
   311   return TRUE;
       
   312 }
       
   313 
       
   314 
       
   315 /*
       
   316  * MCU decoding for AC initial scan (either spectral selection,
       
   317  * or first pass of successive approximation).
       
   318  */
       
   319 
       
   320 METHODDEF(boolean)
       
   321 decode_mcu_AC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
       
   322 {
       
   323   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   324   JBLOCKROW block;
       
   325   unsigned char *st;
       
   326   int tbl, sign, k;
       
   327   int v, m;
       
   328   const int * natural_order;
       
   329 
       
   330   /* Process restart marker if needed */
       
   331   if (cinfo->restart_interval) {
       
   332     if (entropy->restarts_to_go == 0)
       
   333       process_restart(cinfo);
       
   334     entropy->restarts_to_go--;
       
   335   }
       
   336 
       
   337   if (entropy->ct == -1) return TRUE;	/* if error do nothing */
       
   338 
       
   339   natural_order = cinfo->natural_order;
       
   340 
       
   341   /* There is always only one block per MCU */
       
   342   block = MCU_data[0];
       
   343   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
       
   344 
       
   345   /* Sections F.2.4.2 & F.1.4.4.2: Decoding of AC coefficients */
       
   346 
       
   347   /* Figure F.20: Decode_AC_coefficients */
       
   348   for (k = cinfo->Ss; k <= cinfo->Se; k++) {
       
   349     st = entropy->ac_stats[tbl] + 3 * (k - 1);
       
   350     if (arith_decode(cinfo, st)) break;		/* EOB flag */
       
   351     while (arith_decode(cinfo, st + 1) == 0) {
       
   352       st += 3; k++;
       
   353       if (k > cinfo->Se) {
       
   354 	WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   355 	entropy->ct = -1;			/* spectral overflow */
       
   356 	return TRUE;
       
   357       }
       
   358     }
       
   359     /* Figure F.21: Decoding nonzero value v */
       
   360     /* Figure F.22: Decoding the sign of v */
       
   361     sign = arith_decode(cinfo, entropy->fixed_bin);
       
   362     st += 2;
       
   363     /* Figure F.23: Decoding the magnitude category of v */
       
   364     if ((m = arith_decode(cinfo, st)) != 0) {
       
   365       if (arith_decode(cinfo, st)) {
       
   366 	m <<= 1;
       
   367 	st = entropy->ac_stats[tbl] +
       
   368 	     (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
       
   369 	while (arith_decode(cinfo, st)) {
       
   370 	  if ((m <<= 1) == 0x8000) {
       
   371 	    WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   372 	    entropy->ct = -1;			/* magnitude overflow */
       
   373 	    return TRUE;
       
   374 	  }
       
   375 	  st += 1;
       
   376 	}
       
   377       }
       
   378     }
       
   379     v = m;
       
   380     /* Figure F.24: Decoding the magnitude bit pattern of v */
       
   381     st += 14;
       
   382     while (m >>= 1)
       
   383       if (arith_decode(cinfo, st)) v |= m;
       
   384     v += 1; if (sign) v = -v;
       
   385     /* Scale and output coefficient in natural (dezigzagged) order */
       
   386     (*block)[natural_order[k]] = (JCOEF) (v << cinfo->Al);
       
   387   }
       
   388 
       
   389   return TRUE;
       
   390 }
       
   391 
       
   392 
       
   393 /*
       
   394  * MCU decoding for DC successive approximation refinement scan.
       
   395  */
       
   396 
       
   397 METHODDEF(boolean)
       
   398 decode_mcu_DC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
       
   399 {
       
   400   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   401   unsigned char *st;
       
   402   int p1, blkn;
       
   403 
       
   404   /* Process restart marker if needed */
       
   405   if (cinfo->restart_interval) {
       
   406     if (entropy->restarts_to_go == 0)
       
   407       process_restart(cinfo);
       
   408     entropy->restarts_to_go--;
       
   409   }
       
   410 
       
   411   st = entropy->fixed_bin;	/* use fixed probability estimation */
       
   412   p1 = 1 << cinfo->Al;		/* 1 in the bit position being coded */
       
   413 
       
   414   /* Outer loop handles each block in the MCU */
       
   415 
       
   416   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
       
   417     /* Encoded data is simply the next bit of the two's-complement DC value */
       
   418     if (arith_decode(cinfo, st))
       
   419       MCU_data[blkn][0][0] |= p1;
       
   420   }
       
   421 
       
   422   return TRUE;
       
   423 }
       
   424 
       
   425 
       
   426 /*
       
   427  * MCU decoding for AC successive approximation refinement scan.
       
   428  */
       
   429 
       
   430 METHODDEF(boolean)
       
   431 decode_mcu_AC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
       
   432 {
       
   433   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   434   JBLOCKROW block;
       
   435   JCOEFPTR thiscoef;
       
   436   unsigned char *st;
       
   437   int tbl, k, kex;
       
   438   int p1, m1;
       
   439   const int * natural_order;
       
   440 
       
   441   /* Process restart marker if needed */
       
   442   if (cinfo->restart_interval) {
       
   443     if (entropy->restarts_to_go == 0)
       
   444       process_restart(cinfo);
       
   445     entropy->restarts_to_go--;
       
   446   }
       
   447 
       
   448   if (entropy->ct == -1) return TRUE;	/* if error do nothing */
       
   449 
       
   450   natural_order = cinfo->natural_order;
       
   451 
       
   452   /* There is always only one block per MCU */
       
   453   block = MCU_data[0];
       
   454   tbl = cinfo->cur_comp_info[0]->ac_tbl_no;
       
   455 
       
   456   p1 = 1 << cinfo->Al;		/* 1 in the bit position being coded */
       
   457   m1 = (-1) << cinfo->Al;	/* -1 in the bit position being coded */
       
   458 
       
   459   /* Establish EOBx (previous stage end-of-block) index */
       
   460   for (kex = cinfo->Se; kex > 0; kex--)
       
   461     if ((*block)[natural_order[kex]]) break;
       
   462 
       
   463   for (k = cinfo->Ss; k <= cinfo->Se; k++) {
       
   464     st = entropy->ac_stats[tbl] + 3 * (k - 1);
       
   465     if (k > kex)
       
   466       if (arith_decode(cinfo, st)) break;	/* EOB flag */
       
   467     for (;;) {
       
   468       thiscoef = *block + natural_order[k];
       
   469       if (*thiscoef) {				/* previously nonzero coef */
       
   470 	if (arith_decode(cinfo, st + 2)) {
       
   471 	  if (*thiscoef < 0)
       
   472 	    *thiscoef += m1;
       
   473 	  else
       
   474 	    *thiscoef += p1;
       
   475 	}
       
   476 	break;
       
   477       }
       
   478       if (arith_decode(cinfo, st + 1)) {	/* newly nonzero coef */
       
   479 	if (arith_decode(cinfo, entropy->fixed_bin))
       
   480 	  *thiscoef = m1;
       
   481 	else
       
   482 	  *thiscoef = p1;
       
   483 	break;
       
   484       }
       
   485       st += 3; k++;
       
   486       if (k > cinfo->Se) {
       
   487 	WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   488 	entropy->ct = -1;			/* spectral overflow */
       
   489 	return TRUE;
       
   490       }
       
   491     }
       
   492   }
       
   493 
       
   494   return TRUE;
       
   495 }
       
   496 
       
   497 
       
   498 /*
       
   499  * Decode one MCU's worth of arithmetic-compressed coefficients.
       
   500  */
       
   501 
       
   502 METHODDEF(boolean)
       
   503 decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
       
   504 {
       
   505   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   506   jpeg_component_info * compptr;
       
   507   JBLOCKROW block;
       
   508   unsigned char *st;
       
   509   int blkn, ci, tbl, sign, k;
       
   510   int v, m;
       
   511   const int * natural_order;
       
   512 
       
   513   /* Process restart marker if needed */
       
   514   if (cinfo->restart_interval) {
       
   515     if (entropy->restarts_to_go == 0)
       
   516       process_restart(cinfo);
       
   517     entropy->restarts_to_go--;
       
   518   }
       
   519 
       
   520   if (entropy->ct == -1) return TRUE;	/* if error do nothing */
       
   521 
       
   522   natural_order = cinfo->natural_order;
       
   523 
       
   524   /* Outer loop handles each block in the MCU */
       
   525 
       
   526   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
       
   527     block = MCU_data[blkn];
       
   528     ci = cinfo->MCU_membership[blkn];
       
   529     compptr = cinfo->cur_comp_info[ci];
       
   530 
       
   531     /* Sections F.2.4.1 & F.1.4.4.1: Decoding of DC coefficients */
       
   532 
       
   533     tbl = compptr->dc_tbl_no;
       
   534 
       
   535     /* Table F.4: Point to statistics bin S0 for DC coefficient coding */
       
   536     st = entropy->dc_stats[tbl] + entropy->dc_context[ci];
       
   537 
       
   538     /* Figure F.19: Decode_DC_DIFF */
       
   539     if (arith_decode(cinfo, st) == 0)
       
   540       entropy->dc_context[ci] = 0;
       
   541     else {
       
   542       /* Figure F.21: Decoding nonzero value v */
       
   543       /* Figure F.22: Decoding the sign of v */
       
   544       sign = arith_decode(cinfo, st + 1);
       
   545       st += 2; st += sign;
       
   546       /* Figure F.23: Decoding the magnitude category of v */
       
   547       if ((m = arith_decode(cinfo, st)) != 0) {
       
   548 	st = entropy->dc_stats[tbl] + 20;	/* Table F.4: X1 = 20 */
       
   549 	while (arith_decode(cinfo, st)) {
       
   550 	  if ((m <<= 1) == 0x8000) {
       
   551 	    WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   552 	    entropy->ct = -1;			/* magnitude overflow */
       
   553 	    return TRUE;
       
   554 	  }
       
   555 	  st += 1;
       
   556 	}
       
   557       }
       
   558       /* Section F.1.4.4.1.2: Establish dc_context conditioning category */
       
   559       if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1))
       
   560 	entropy->dc_context[ci] = 0;		   /* zero diff category */
       
   561       else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1))
       
   562 	entropy->dc_context[ci] = 12 + (sign * 4); /* large diff category */
       
   563       else
       
   564 	entropy->dc_context[ci] = 4 + (sign * 4);  /* small diff category */
       
   565       v = m;
       
   566       /* Figure F.24: Decoding the magnitude bit pattern of v */
       
   567       st += 14;
       
   568       while (m >>= 1)
       
   569 	if (arith_decode(cinfo, st)) v |= m;
       
   570       v += 1; if (sign) v = -v;
       
   571       entropy->last_dc_val[ci] += v;
       
   572     }
       
   573 
       
   574     (*block)[0] = (JCOEF) entropy->last_dc_val[ci];
       
   575 
       
   576     /* Sections F.2.4.2 & F.1.4.4.2: Decoding of AC coefficients */
       
   577 
       
   578     tbl = compptr->ac_tbl_no;
       
   579 
       
   580     /* Figure F.20: Decode_AC_coefficients */
       
   581     for (k = 1; k <= cinfo->lim_Se; k++) {
       
   582       st = entropy->ac_stats[tbl] + 3 * (k - 1);
       
   583       if (arith_decode(cinfo, st)) break;	/* EOB flag */
       
   584       while (arith_decode(cinfo, st + 1) == 0) {
       
   585 	st += 3; k++;
       
   586 	if (k > cinfo->lim_Se) {
       
   587 	  WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   588 	  entropy->ct = -1;			/* spectral overflow */
       
   589 	  return TRUE;
       
   590 	}
       
   591       }
       
   592       /* Figure F.21: Decoding nonzero value v */
       
   593       /* Figure F.22: Decoding the sign of v */
       
   594       sign = arith_decode(cinfo, entropy->fixed_bin);
       
   595       st += 2;
       
   596       /* Figure F.23: Decoding the magnitude category of v */
       
   597       if ((m = arith_decode(cinfo, st)) != 0) {
       
   598 	if (arith_decode(cinfo, st)) {
       
   599 	  m <<= 1;
       
   600 	  st = entropy->ac_stats[tbl] +
       
   601 	       (k <= cinfo->arith_ac_K[tbl] ? 189 : 217);
       
   602 	  while (arith_decode(cinfo, st)) {
       
   603 	    if ((m <<= 1) == 0x8000) {
       
   604 	      WARNMS(cinfo, JWRN_ARITH_BAD_CODE);
       
   605 	      entropy->ct = -1;			/* magnitude overflow */
       
   606 	      return TRUE;
       
   607 	    }
       
   608 	    st += 1;
       
   609 	  }
       
   610 	}
       
   611       }
       
   612       v = m;
       
   613       /* Figure F.24: Decoding the magnitude bit pattern of v */
       
   614       st += 14;
       
   615       while (m >>= 1)
       
   616 	if (arith_decode(cinfo, st)) v |= m;
       
   617       v += 1; if (sign) v = -v;
       
   618       (*block)[natural_order[k]] = (JCOEF) v;
       
   619     }
       
   620   }
       
   621 
       
   622   return TRUE;
       
   623 }
       
   624 
       
   625 
       
   626 /*
       
   627  * Initialize for an arithmetic-compressed scan.
       
   628  */
       
   629 
       
   630 METHODDEF(void)
       
   631 start_pass (j_decompress_ptr cinfo)
       
   632 {
       
   633   arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy;
       
   634   int ci, tbl;
       
   635   jpeg_component_info * compptr;
       
   636 
       
   637   if (cinfo->progressive_mode) {
       
   638     /* Validate progressive scan parameters */
       
   639     if (cinfo->Ss == 0) {
       
   640       if (cinfo->Se != 0)
       
   641 	goto bad;
       
   642     } else {
       
   643       /* need not check Ss/Se < 0 since they came from unsigned bytes */
       
   644       if (cinfo->Se < cinfo->Ss || cinfo->Se > cinfo->lim_Se)
       
   645 	goto bad;
       
   646       /* AC scans may have only one component */
       
   647       if (cinfo->comps_in_scan != 1)
       
   648 	goto bad;
       
   649     }
       
   650     if (cinfo->Ah != 0) {
       
   651       /* Successive approximation refinement scan: must have Al = Ah-1. */
       
   652       if (cinfo->Ah-1 != cinfo->Al)
       
   653 	goto bad;
       
   654     }
       
   655     if (cinfo->Al > 13) {	/* need not check for < 0 */
       
   656       bad:
       
   657       ERREXIT4(cinfo, JERR_BAD_PROGRESSION,
       
   658 	       cinfo->Ss, cinfo->Se, cinfo->Ah, cinfo->Al);
       
   659     }
       
   660     /* Update progression status, and verify that scan order is legal.
       
   661      * Note that inter-scan inconsistencies are treated as warnings
       
   662      * not fatal errors ... not clear if this is right way to behave.
       
   663      */
       
   664     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
       
   665       int coefi, cindex = cinfo->cur_comp_info[ci]->component_index;
       
   666       int *coef_bit_ptr = & cinfo->coef_bits[cindex][0];
       
   667       if (cinfo->Ss && coef_bit_ptr[0] < 0) /* AC without prior DC scan */
       
   668 	WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, 0);
       
   669       for (coefi = cinfo->Ss; coefi <= cinfo->Se; coefi++) {
       
   670 	int expected = (coef_bit_ptr[coefi] < 0) ? 0 : coef_bit_ptr[coefi];
       
   671 	if (cinfo->Ah != expected)
       
   672 	  WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, coefi);
       
   673 	coef_bit_ptr[coefi] = cinfo->Al;
       
   674       }
       
   675     }
       
   676     /* Select MCU decoding routine */
       
   677     if (cinfo->Ah == 0) {
       
   678       if (cinfo->Ss == 0)
       
   679 	entropy->pub.decode_mcu = decode_mcu_DC_first;
       
   680       else
       
   681 	entropy->pub.decode_mcu = decode_mcu_AC_first;
       
   682     } else {
       
   683       if (cinfo->Ss == 0)
       
   684 	entropy->pub.decode_mcu = decode_mcu_DC_refine;
       
   685       else
       
   686 	entropy->pub.decode_mcu = decode_mcu_AC_refine;
       
   687     }
       
   688   } else {
       
   689     /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
       
   690      * This ought to be an error condition, but we make it a warning.
       
   691      */
       
   692     if (cinfo->Ss != 0 || cinfo->Ah != 0 || cinfo->Al != 0 ||
       
   693 	(cinfo->Se < DCTSIZE2 && cinfo->Se != cinfo->lim_Se))
       
   694       WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
       
   695     /* Select MCU decoding routine */
       
   696     entropy->pub.decode_mcu = decode_mcu;
       
   697   }
       
   698 
       
   699   /* Allocate & initialize requested statistics areas */
       
   700   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
       
   701     compptr = cinfo->cur_comp_info[ci];
       
   702     if (! cinfo->progressive_mode || (cinfo->Ss == 0 && cinfo->Ah == 0)) {
       
   703       tbl = compptr->dc_tbl_no;
       
   704       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
       
   705 	ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
       
   706       if (entropy->dc_stats[tbl] == NULL)
       
   707 	entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
       
   708 	  ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS);
       
   709       MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS);
       
   710       /* Initialize DC predictions to 0 */
       
   711       entropy->last_dc_val[ci] = 0;
       
   712       entropy->dc_context[ci] = 0;
       
   713     }
       
   714     if ((! cinfo->progressive_mode && cinfo->lim_Se) ||
       
   715 	(cinfo->progressive_mode && cinfo->Ss)) {
       
   716       tbl = compptr->ac_tbl_no;
       
   717       if (tbl < 0 || tbl >= NUM_ARITH_TBLS)
       
   718 	ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl);
       
   719       if (entropy->ac_stats[tbl] == NULL)
       
   720 	entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small)
       
   721 	  ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS);
       
   722       MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS);
       
   723     }
       
   724   }
       
   725 
       
   726   /* Initialize arithmetic decoding variables */
       
   727   entropy->c = 0;
       
   728   entropy->a = 0;
       
   729   entropy->ct = -16;	/* force reading 2 initial bytes to fill C */
       
   730 
       
   731   /* Initialize restart counter */
       
   732   entropy->restarts_to_go = cinfo->restart_interval;
       
   733 }
       
   734 
       
   735 
       
   736 /*
       
   737  * Module initialization routine for arithmetic entropy decoding.
       
   738  */
       
   739 
       
   740 GLOBAL(void)
       
   741 jinit_arith_decoder (j_decompress_ptr cinfo)
       
   742 {
       
   743   arith_entropy_ptr entropy;
       
   744   int i;
       
   745 
       
   746   entropy = (arith_entropy_ptr)
       
   747     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
       
   748 				SIZEOF(arith_entropy_decoder));
       
   749   cinfo->entropy = (struct jpeg_entropy_decoder *) entropy;
       
   750   entropy->pub.start_pass = start_pass;
       
   751 
       
   752   /* Mark tables unallocated */
       
   753   for (i = 0; i < NUM_ARITH_TBLS; i++) {
       
   754     entropy->dc_stats[i] = NULL;
       
   755     entropy->ac_stats[i] = NULL;
       
   756   }
       
   757 
       
   758   /* Initialize index for fixed probability estimation */
       
   759   entropy->fixed_bin[0] = 113;
       
   760 
       
   761   if (cinfo->progressive_mode) {
       
   762     /* Create progression status table */
       
   763     int *coef_bit_ptr, ci;
       
   764     cinfo->coef_bits = (int (*)[DCTSIZE2])
       
   765       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
       
   766 				  cinfo->num_components*DCTSIZE2*SIZEOF(int));
       
   767     coef_bit_ptr = & cinfo->coef_bits[0][0];
       
   768     for (ci = 0; ci < cinfo->num_components; ci++) 
       
   769       for (i = 0; i < DCTSIZE2; i++)
       
   770 	*coef_bit_ptr++ = -1;
       
   771   }
       
   772 }