1 /*
   2  * jdhuff.c
   3  *
   4  * Copyright (C) 1991-1997, Thomas G. Lane.
   5  * Modified 2006-2016 by Guido Vollbeding.
   6  * This file is part of the Independent JPEG Group's software.
   7  * For conditions of distribution and use, see the accompanying README file.
   8  *
   9  * This file contains Huffman entropy decoding routines.
  10  * Both sequential and progressive modes are supported in this single module.
  11  *
  12  * Much of the complexity here has to do with supporting input suspension.
  13  * If the data source module demands suspension, we want to be able to back
  14  * up to the start of the current MCU.  To do this, we copy state variables
  15  * into local working storage, and update them back to the permanent
  16  * storage only upon successful completion of an MCU.
  17  */
  18 
  19 #define JPEG_INTERNALS
  20 #include "jinclude.h"
  21 #include "jpeglib.h"
  22 
  23 
  24 /* Derived data constructed for each Huffman table */
  25 
  26 #define HUFF_LOOKAHEAD  8       /* # of bits of lookahead */
  27 
  28 typedef struct {
  29   /* Basic tables: (element [0] of each array is unused) */
  30   INT32 maxcode[18];            /* largest code of length k (-1 if none) */
  31   /* (maxcode[17] is a sentinel to ensure jpeg_huff_decode terminates) */
  32   INT32 valoffset[17];          /* huffval[] offset for codes of length k */
  33   /* valoffset[k] = huffval[] index of 1st symbol of code length k, less
  34    * the smallest code of length k; so given a code of length k, the
  35    * corresponding symbol is huffval[code + valoffset[k]]
  36    */
  37 
  38   /* Link to public Huffman table (needed only in jpeg_huff_decode) */
  39   JHUFF_TBL *pub;
  40 
  41   /* Lookahead tables: indexed by the next HUFF_LOOKAHEAD bits of
  42    * the input data stream.  If the next Huffman code is no more
  43    * than HUFF_LOOKAHEAD bits long, we can obtain its length and
  44    * the corresponding symbol directly from these tables.
  45    */
  46   int look_nbits[1<<HUFF_LOOKAHEAD]; /* # bits, or 0 if too long */
  47   UINT8 look_sym[1<<HUFF_LOOKAHEAD]; /* symbol, or unused */
  48 } d_derived_tbl;
  49 
  50 
  51 /*
  52  * Fetching the next N bits from the input stream is a time-critical operation
  53  * for the Huffman decoders.  We implement it with a combination of inline
  54  * macros and out-of-line subroutines.  Note that N (the number of bits
  55  * demanded at one time) never exceeds 15 for JPEG use.
  56  *
  57  * We read source bytes into get_buffer and dole out bits as needed.
  58  * If get_buffer already contains enough bits, they are fetched in-line
  59  * by the macros CHECK_BIT_BUFFER and GET_BITS.  When there aren't enough
  60  * bits, jpeg_fill_bit_buffer is called; it will attempt to fill get_buffer
  61  * as full as possible (not just to the number of bits needed; this
  62  * prefetching reduces the overhead cost of calling jpeg_fill_bit_buffer).
  63  * Note that jpeg_fill_bit_buffer may return FALSE to indicate suspension.
  64  * On TRUE return, jpeg_fill_bit_buffer guarantees that get_buffer contains
  65  * at least the requested number of bits --- dummy zeroes are inserted if
  66  * necessary.
  67  */
  68 
  69 typedef INT32 bit_buf_type;     /* type of bit-extraction buffer */
  70 #define BIT_BUF_SIZE  32        /* size of buffer in bits */
  71 
  72 /* If long is > 32 bits on your machine, and shifting/masking longs is
  73  * reasonably fast, making bit_buf_type be long and setting BIT_BUF_SIZE
  74  * appropriately should be a win.  Unfortunately we can't define the size
  75  * with something like  #define BIT_BUF_SIZE (sizeof(bit_buf_type)*8)
  76  * because not all machines measure sizeof in 8-bit bytes.
  77  */
  78 
  79 typedef struct {                /* Bitreading state saved across MCUs */
  80   bit_buf_type get_buffer;      /* current bit-extraction buffer */
  81   int bits_left;                /* # of unused bits in it */
  82 } bitread_perm_state;
  83 
  84 typedef struct {                /* Bitreading working state within an MCU */
  85   /* Current data source location */
  86   /* We need a copy, rather than munging the original, in case of suspension */
  87   const JOCTET * next_input_byte; /* => next byte to read from source */
  88   size_t bytes_in_buffer;       /* # of bytes remaining in source buffer */
  89   /* Bit input buffer --- note these values are kept in register variables,
  90    * not in this struct, inside the inner loops.
  91    */
  92   bit_buf_type get_buffer;      /* current bit-extraction buffer */
  93   int bits_left;                /* # of unused bits in it */
  94   /* Pointer needed by jpeg_fill_bit_buffer. */
  95   j_decompress_ptr cinfo;       /* back link to decompress master record */
  96 } bitread_working_state;
  97 
  98 /* Macros to declare and load/save bitread local variables. */
  99 #define BITREAD_STATE_VARS  \
 100         register bit_buf_type get_buffer;  \
 101         register int bits_left;  \
 102         bitread_working_state br_state
 103 
 104 #define BITREAD_LOAD_STATE(cinfop,permstate)  \
 105         br_state.cinfo = cinfop; \
 106         br_state.next_input_byte = cinfop->src->next_input_byte; \
 107         br_state.bytes_in_buffer = cinfop->src->bytes_in_buffer; \
 108         get_buffer = permstate.get_buffer; \
 109         bits_left = permstate.bits_left;
 110 
 111 #define BITREAD_SAVE_STATE(cinfop,permstate)  \
 112         cinfop->src->next_input_byte = br_state.next_input_byte; \
 113         cinfop->src->bytes_in_buffer = br_state.bytes_in_buffer; \
 114         permstate.get_buffer = get_buffer; \
 115         permstate.bits_left = bits_left
 116 
 117 /*
 118  * These macros provide the in-line portion of bit fetching.
 119  * Use CHECK_BIT_BUFFER to ensure there are N bits in get_buffer
 120  * before using GET_BITS, PEEK_BITS, or DROP_BITS.
 121  * The variables get_buffer and bits_left are assumed to be locals,
 122  * but the state struct might not be (jpeg_huff_decode needs this).
 123  *      CHECK_BIT_BUFFER(state,n,action);
 124  *              Ensure there are N bits in get_buffer; if suspend, take action.
 125  *      val = GET_BITS(n);
 126  *              Fetch next N bits.
 127  *      val = PEEK_BITS(n);
 128  *              Fetch next N bits without removing them from the buffer.
 129  *      DROP_BITS(n);
 130  *              Discard next N bits.
 131  * The value N should be a simple variable, not an expression, because it
 132  * is evaluated multiple times.
 133  */
 134 
 135 #define CHECK_BIT_BUFFER(state,nbits,action) \
 136         { if (bits_left < (nbits)) {  \
 137             if (! jpeg_fill_bit_buffer(&(state),get_buffer,bits_left,nbits))  \
 138               { action; }  \
 139             get_buffer = (state).get_buffer; bits_left = (state).bits_left; } }
 140 
 141 #define GET_BITS(nbits) \
 142         (((int) (get_buffer >> (bits_left -= (nbits)))) & BIT_MASK(nbits))
 143 
 144 #define PEEK_BITS(nbits) \
 145         (((int) (get_buffer >> (bits_left -  (nbits)))) & BIT_MASK(nbits))
 146 
 147 #define DROP_BITS(nbits) \
 148         (bits_left -= (nbits))
 149 
 150 
 151 /*
 152  * Code for extracting next Huffman-coded symbol from input bit stream.
 153  * Again, this is time-critical and we make the main paths be macros.
 154  *
 155  * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
 156  * without looping.  Usually, more than 95% of the Huffman codes will be 8
 157  * or fewer bits long.  The few overlength codes are handled with a loop,
 158  * which need not be inline code.
 159  *
 160  * Notes about the HUFF_DECODE macro:
 161  * 1. Near the end of the data segment, we may fail to get enough bits
 162  *    for a lookahead.  In that case, we do it the hard way.
 163  * 2. If the lookahead table contains no entry, the next code must be
 164  *    more than HUFF_LOOKAHEAD bits long.
 165  * 3. jpeg_huff_decode returns -1 if forced to suspend.
 166  */
 167 
 168 #define HUFF_DECODE(result,state,htbl,failaction,slowlabel) \
 169 { register int nb, look; \
 170   if (bits_left < HUFF_LOOKAHEAD) { \
 171     if (! jpeg_fill_bit_buffer(&state,get_buffer,bits_left, 0)) {failaction;} \
 172     get_buffer = state.get_buffer; bits_left = state.bits_left; \
 173     if (bits_left < HUFF_LOOKAHEAD) { \
 174       nb = 1; goto slowlabel; \
 175     } \
 176   } \
 177   look = PEEK_BITS(HUFF_LOOKAHEAD); \
 178   if ((nb = htbl->look_nbits[look]) != 0) { \
 179     DROP_BITS(nb); \
 180     result = htbl->look_sym[look]; \
 181   } else { \
 182     nb = HUFF_LOOKAHEAD+1; \
 183 slowlabel: \
 184     if ((result=jpeg_huff_decode(&state,get_buffer,bits_left,htbl,nb)) < 0) \
 185         { failaction; } \
 186     get_buffer = state.get_buffer; bits_left = state.bits_left; \
 187   } \
 188 }
 189 
 190 
 191 /*
 192  * Expanded entropy decoder object for Huffman decoding.
 193  *
 194  * The savable_state subrecord contains fields that change within an MCU,
 195  * but must not be updated permanently until we complete the MCU.
 196  */
 197 
 198 typedef struct {
 199   unsigned int EOBRUN;                  /* remaining EOBs in EOBRUN */
 200   int last_dc_val[MAX_COMPS_IN_SCAN];   /* last DC coef for each component */
 201 } savable_state;
 202 
 203 /* This macro is to work around compilers with missing or broken
 204  * structure assignment.  You'll need to fix this code if you have
 205  * such a compiler and you change MAX_COMPS_IN_SCAN.
 206  */
 207 
 208 #ifndef NO_STRUCT_ASSIGN
 209 #define ASSIGN_STATE(dest,src)  ((dest) = (src))
 210 #else
 211 #if MAX_COMPS_IN_SCAN == 4
 212 #define ASSIGN_STATE(dest,src)  \
 213         ((dest).EOBRUN = (src).EOBRUN, \
 214          (dest).last_dc_val[0] = (src).last_dc_val[0], \
 215          (dest).last_dc_val[1] = (src).last_dc_val[1], \
 216          (dest).last_dc_val[2] = (src).last_dc_val[2], \
 217          (dest).last_dc_val[3] = (src).last_dc_val[3])
 218 #endif
 219 #endif
 220 
 221 
 222 typedef struct {
 223   struct jpeg_entropy_decoder pub; /* public fields */
 224 
 225   /* These fields are loaded into local variables at start of each MCU.
 226    * In case of suspension, we exit WITHOUT updating them.
 227    */
 228   bitread_perm_state bitstate;  /* Bit buffer at start of MCU */
 229   savable_state saved;          /* Other state at start of MCU */
 230 
 231   /* These fields are NOT loaded into local working state. */
 232   boolean insufficient_data;    /* set TRUE after emitting warning */
 233   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
 234 
 235   /* Following two fields used only in progressive mode */
 236 
 237   /* Pointers to derived tables (these workspaces have image lifespan) */
 238   d_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
 239 
 240   d_derived_tbl * ac_derived_tbl; /* active table during an AC scan */
 241 
 242   /* Following fields used only in sequential mode */
 243 
 244   /* Pointers to derived tables (these workspaces have image lifespan) */
 245   d_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
 246   d_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
 247 
 248   /* Precalculated info set up by start_pass for use in decode_mcu: */
 249 
 250   /* Pointers to derived tables to be used for each block within an MCU */
 251   d_derived_tbl * dc_cur_tbls[D_MAX_BLOCKS_IN_MCU];
 252   d_derived_tbl * ac_cur_tbls[D_MAX_BLOCKS_IN_MCU];
 253   /* Whether we care about the DC and AC coefficient values for each block */
 254   int coef_limit[D_MAX_BLOCKS_IN_MCU];
 255 } huff_entropy_decoder;
 256 
 257 typedef huff_entropy_decoder * huff_entropy_ptr;
 258 
 259 
 260 static const int jpeg_zigzag_order[8][8] = {
 261   {  0,  1,  5,  6, 14, 15, 27, 28 },
 262   {  2,  4,  7, 13, 16, 26, 29, 42 },
 263   {  3,  8, 12, 17, 25, 30, 41, 43 },
 264   {  9, 11, 18, 24, 31, 40, 44, 53 },
 265   { 10, 19, 23, 32, 39, 45, 52, 54 },
 266   { 20, 22, 33, 38, 46, 51, 55, 60 },
 267   { 21, 34, 37, 47, 50, 56, 59, 61 },
 268   { 35, 36, 48, 49, 57, 58, 62, 63 }
 269 };
 270 
 271 static const int jpeg_zigzag_order7[7][7] = {
 272   {  0,  1,  5,  6, 14, 15, 27 },
 273   {  2,  4,  7, 13, 16, 26, 28 },
 274   {  3,  8, 12, 17, 25, 29, 38 },
 275   {  9, 11, 18, 24, 30, 37, 39 },
 276   { 10, 19, 23, 31, 36, 40, 45 },
 277   { 20, 22, 32, 35, 41, 44, 46 },
 278   { 21, 33, 34, 42, 43, 47, 48 }
 279 };
 280 
 281 static const int jpeg_zigzag_order6[6][6] = {
 282   {  0,  1,  5,  6, 14, 15 },
 283   {  2,  4,  7, 13, 16, 25 },
 284   {  3,  8, 12, 17, 24, 26 },
 285   {  9, 11, 18, 23, 27, 32 },
 286   { 10, 19, 22, 28, 31, 33 },
 287   { 20, 21, 29, 30, 34, 35 }
 288 };
 289 
 290 static const int jpeg_zigzag_order5[5][5] = {
 291   {  0,  1,  5,  6, 14 },
 292   {  2,  4,  7, 13, 15 },
 293   {  3,  8, 12, 16, 21 },
 294   {  9, 11, 17, 20, 22 },
 295   { 10, 18, 19, 23, 24 }
 296 };
 297 
 298 static const int jpeg_zigzag_order4[4][4] = {
 299   { 0,  1,  5,  6 },
 300   { 2,  4,  7, 12 },
 301   { 3,  8, 11, 13 },
 302   { 9, 10, 14, 15 }
 303 };
 304 
 305 static const int jpeg_zigzag_order3[3][3] = {
 306   { 0, 1, 5 },
 307   { 2, 4, 6 },
 308   { 3, 7, 8 }
 309 };
 310 
 311 static const int jpeg_zigzag_order2[2][2] = {
 312   { 0, 1 },
 313   { 2, 3 }
 314 };
 315 
 316 
 317 /*
 318  * Compute the derived values for a Huffman table.
 319  * This routine also performs some validation checks on the table.
 320  */
 321 
 322 LOCAL(void)
 323 jpeg_make_d_derived_tbl (j_decompress_ptr cinfo, boolean isDC, int tblno,
 324                          d_derived_tbl ** pdtbl)
 325 {
 326   JHUFF_TBL *htbl;
 327   d_derived_tbl *dtbl;
 328   int p, i, l, si, numsymbols;
 329   int lookbits, ctr;
 330   char huffsize[257];
 331   unsigned int huffcode[257];
 332   unsigned int code;
 333 
 334   /* Note that huffsize[] and huffcode[] are filled in code-length order,
 335    * paralleling the order of the symbols themselves in htbl->huffval[].
 336    */
 337 
 338   /* Find the input Huffman table */
 339   if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
 340     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 341   htbl =
 342     isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
 343   if (htbl == NULL)
 344     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 345 
 346   /* Allocate a workspace if we haven't already done so. */
 347   if (*pdtbl == NULL)
 348     *pdtbl = (d_derived_tbl *)
 349       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 350                                   SIZEOF(d_derived_tbl));
 351   dtbl = *pdtbl;
 352   dtbl->pub = htbl;          /* fill in back link */
 353   
 354   /* Figure C.1: make table of Huffman code length for each symbol */
 355 
 356   p = 0;
 357   for (l = 1; l <= 16; l++) {
 358     i = (int) htbl->bits[l];
 359     if (i < 0 || p + i > 256)     /* protect against table overrun */
 360       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 361     while (i--)
 362       huffsize[p++] = (char) l;
 363   }
 364   huffsize[p] = 0;
 365   numsymbols = p;
 366   
 367   /* Figure C.2: generate the codes themselves */
 368   /* We also validate that the counts represent a legal Huffman code tree. */
 369   
 370   code = 0;
 371   si = huffsize[0];
 372   p = 0;
 373   while (huffsize[p]) {
 374     while (((int) huffsize[p]) == si) {
 375       huffcode[p++] = code;
 376       code++;
 377     }
 378     /* code is now 1 more than the last code used for codelength si; but
 379      * it must still fit in si bits, since no code is allowed to be all ones.
 380      */
 381     if (((INT32) code) >= (((INT32) 1) << si))
 382       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 383     code <<= 1;
 384     si++;
 385   }
 386 
 387   /* Figure F.15: generate decoding tables for bit-sequential decoding */
 388 
 389   p = 0;
 390   for (l = 1; l <= 16; l++) {
 391     if (htbl->bits[l]) {
 392       /* valoffset[l] = huffval[] index of 1st symbol of code length l,
 393        * minus the minimum code of length l
 394        */
 395       dtbl->valoffset[l] = (INT32) p - (INT32) huffcode[p];
 396       p += htbl->bits[l];
 397       dtbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
 398     } else {
 399       dtbl->maxcode[l] = -1; /* -1 if no codes of this length */
 400     }
 401   }
 402   dtbl->maxcode[17] = 0xFFFFFL; /* ensures jpeg_huff_decode terminates */
 403 
 404   /* Compute lookahead tables to speed up decoding.
 405    * First we set all the table entries to 0, indicating "too long";
 406    * then we iterate through the Huffman codes that are short enough and
 407    * fill in all the entries that correspond to bit sequences starting
 408    * with that code.
 409    */
 410 
 411   MEMZERO(dtbl->look_nbits, SIZEOF(dtbl->look_nbits));
 412 
 413   p = 0;
 414   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
 415     for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
 416       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
 417       /* Generate left-justified code followed by all possible bit sequences */
 418       lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
 419       for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
 420         dtbl->look_nbits[lookbits] = l;
 421         dtbl->look_sym[lookbits] = htbl->huffval[p];
 422         lookbits++;
 423       }
 424     }
 425   }
 426 
 427   /* Validate symbols as being reasonable.
 428    * For AC tables, we make no check, but accept all byte values 0..255.
 429    * For DC tables, we require the symbols to be in range 0..15.
 430    * (Tighter bounds could be applied depending on the data depth and mode,
 431    * but this is sufficient to ensure safe decoding.)
 432    */
 433   if (isDC) {
 434     for (i = 0; i < numsymbols; i++) {
 435       int sym = htbl->huffval[i];
 436       if (sym < 0 || sym > 15)
 437         ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 438     }
 439   }
 440 }
 441 
 442 
 443 /*
 444  * Out-of-line code for bit fetching.
 445  * Note: current values of get_buffer and bits_left are passed as parameters,
 446  * but are returned in the corresponding fields of the state struct.
 447  *
 448  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
 449  * of get_buffer to be used.  (On machines with wider words, an even larger
 450  * buffer could be used.)  However, on some machines 32-bit shifts are
 451  * quite slow and take time proportional to the number of places shifted.
 452  * (This is true with most PC compilers, for instance.)  In this case it may
 453  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
 454  * average shift distance at the cost of more calls to jpeg_fill_bit_buffer.
 455  */
 456 
 457 #ifdef SLOW_SHIFT_32
 458 #define MIN_GET_BITS  15        /* minimum allowable value */
 459 #else
 460 #define MIN_GET_BITS  (BIT_BUF_SIZE-7)
 461 #endif
 462 
 463 
 464 LOCAL(boolean)
 465 jpeg_fill_bit_buffer (bitread_working_state * state,
 466                       register bit_buf_type get_buffer, register int bits_left,
 467                       int nbits)
 468 /* Load up the bit buffer to a depth of at least nbits */
 469 {
 470   /* Copy heavily used state fields into locals (hopefully registers) */
 471   register const JOCTET * next_input_byte = state->next_input_byte;
 472   register size_t bytes_in_buffer = state->bytes_in_buffer;
 473   j_decompress_ptr cinfo = state->cinfo;
 474 
 475   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
 476   /* (It is assumed that no request will be for more than that many bits.) */
 477   /* We fail to do so only if we hit a marker or are forced to suspend. */
 478 
 479   if (cinfo->unread_marker == 0) {   /* cannot advance past a marker */
 480     while (bits_left < MIN_GET_BITS) {
 481       register int c;
 482 
 483       /* Attempt to read a byte */
 484       if (bytes_in_buffer == 0) {
 485         if (! (*cinfo->src->fill_input_buffer) (cinfo))
 486           return FALSE;
 487         next_input_byte = cinfo->src->next_input_byte;
 488         bytes_in_buffer = cinfo->src->bytes_in_buffer;
 489       }
 490       bytes_in_buffer--;
 491       c = GETJOCTET(*next_input_byte++);
 492 
 493       /* If it's 0xFF, check and discard stuffed zero byte */
 494       if (c == 0xFF) {
 495         /* Loop here to discard any padding FF's on terminating marker,
 496          * so that we can save a valid unread_marker value.  NOTE: we will
 497          * accept multiple FF's followed by a 0 as meaning a single FF data
 498          * byte.  This data pattern is not valid according to the standard.
 499          */
 500         do {
 501           if (bytes_in_buffer == 0) {
 502             if (! (*cinfo->src->fill_input_buffer) (cinfo))
 503               return FALSE;
 504             next_input_byte = cinfo->src->next_input_byte;
 505             bytes_in_buffer = cinfo->src->bytes_in_buffer;
 506           }
 507           bytes_in_buffer--;
 508           c = GETJOCTET(*next_input_byte++);
 509         } while (c == 0xFF);
 510 
 511         if (c == 0) {
 512           /* Found FF/00, which represents an FF data byte */
 513           c = 0xFF;
 514         } else {
 515           /* Oops, it's actually a marker indicating end of compressed data.
 516            * Save the marker code for later use.
 517            * Fine point: it might appear that we should save the marker into
 518            * bitread working state, not straight into permanent state.  But
 519            * once we have hit a marker, we cannot need to suspend within the
 520            * current MCU, because we will read no more bytes from the data
 521            * source.  So it is OK to update permanent state right away.
 522            */
 523           cinfo->unread_marker = c;
 524           /* See if we need to insert some fake zero bits. */
 525           goto no_more_bytes;
 526         }
 527       }
 528 
 529       /* OK, load c into get_buffer */
 530       get_buffer = (get_buffer << 8) | c;
 531       bits_left += 8;
 532     } /* end while */
 533   } else {
 534   no_more_bytes:
 535     /* We get here if we've read the marker that terminates the compressed
 536      * data segment.  There should be enough bits in the buffer register
 537      * to satisfy the request; if so, no problem.
 538      */
 539     if (nbits > bits_left) {
 540       /* Uh-oh.  Report corrupted data to user and stuff zeroes into
 541        * the data stream, so that we can produce some kind of image.
 542        * We use a nonvolatile flag to ensure that only one warning message
 543        * appears per data segment.
 544        */
 545       if (! ((huff_entropy_ptr) cinfo->entropy)->insufficient_data) {
 546         WARNMS(cinfo, JWRN_HIT_MARKER);
 547         ((huff_entropy_ptr) cinfo->entropy)->insufficient_data = TRUE;
 548       }
 549       /* Fill the buffer with zero bits */
 550       get_buffer <<= MIN_GET_BITS - bits_left;
 551       bits_left = MIN_GET_BITS;
 552     }
 553   }
 554 
 555   /* Unload the local registers */
 556   state->next_input_byte = next_input_byte;
 557   state->bytes_in_buffer = bytes_in_buffer;
 558   state->get_buffer = get_buffer;
 559   state->bits_left = bits_left;
 560 
 561   return TRUE;
 562 }
 563 
 564 
 565 /*
 566  * Figure F.12: extend sign bit.
 567  * On some machines, a shift and sub will be faster than a table lookup.
 568  */
 569 
 570 #ifdef AVOID_TABLES
 571 
 572 #define BIT_MASK(nbits)   ((1<<(nbits))-1)
 573 #define HUFF_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) - ((1<<(s))-1) : (x))
 574 
 575 #else
 576 
 577 #define BIT_MASK(nbits)   bmask[nbits]
 578 #define HUFF_EXTEND(x,s)  ((x) <= bmask[(s) - 1] ? (x) - bmask[s] : (x))
 579 
 580 static const int bmask[16] =    /* bmask[n] is mask for n rightmost bits */
 581   { 0, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF,
 582     0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF };
 583 
 584 #endif /* AVOID_TABLES */
 585 
 586 
 587 /*
 588  * Out-of-line code for Huffman code decoding.
 589  */
 590 
 591 LOCAL(int)
 592 jpeg_huff_decode (bitread_working_state * state,
 593                   register bit_buf_type get_buffer, register int bits_left,
 594                   d_derived_tbl * htbl, int min_bits)
 595 {
 596   register int l = min_bits;
 597   register INT32 code;
 598 
 599   /* HUFF_DECODE has determined that the code is at least min_bits */
 600   /* bits long, so fetch that many bits in one swoop. */
 601 
 602   CHECK_BIT_BUFFER(*state, l, return -1);
 603   code = GET_BITS(l);
 604 
 605   /* Collect the rest of the Huffman code one bit at a time. */
 606   /* This is per Figure F.16 in the JPEG spec. */
 607 
 608   while (code > htbl->maxcode[l]) {
 609     code <<= 1;
 610     CHECK_BIT_BUFFER(*state, 1, return -1);
 611     code |= GET_BITS(1);
 612     l++;
 613   }
 614 
 615   /* Unload the local registers */
 616   state->get_buffer = get_buffer;
 617   state->bits_left = bits_left;
 618 
 619   /* With garbage input we may reach the sentinel value l = 17. */
 620 
 621   if (l > 16) {
 622     WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
 623     return 0;                   /* fake a zero as the safest result */
 624   }
 625 
 626   return htbl->pub->huffval[ (int) (code + htbl->valoffset[l]) ];
 627 }
 628 
 629 
 630 /*
 631  * Finish up at the end of a Huffman-compressed scan.
 632  */
 633 
 634 METHODDEF(void)
 635 finish_pass_huff (j_decompress_ptr cinfo)
 636 {
 637   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 638 
 639   /* Throw away any unused bits remaining in bit buffer; */
 640   /* include any full bytes in next_marker's count of discarded bytes */
 641   cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
 642   entropy->bitstate.bits_left = 0;
 643 }
 644 
 645 
 646 /*
 647  * Check for a restart marker & resynchronize decoder.
 648  * Returns FALSE if must suspend.
 649  */
 650 
 651 LOCAL(boolean)
 652 process_restart (j_decompress_ptr cinfo)
 653 {
 654   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 655   int ci;
 656 
 657   finish_pass_huff(cinfo);
 658 
 659   /* Advance past the RSTn marker */
 660   if (! (*cinfo->marker->read_restart_marker) (cinfo))
 661     return FALSE;
 662 
 663   /* Re-initialize DC predictions to 0 */
 664   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
 665     entropy->saved.last_dc_val[ci] = 0;
 666   /* Re-init EOB run count, too */
 667   entropy->saved.EOBRUN = 0;
 668 
 669   /* Reset restart counter */
 670   entropy->restarts_to_go = cinfo->restart_interval;
 671 
 672   /* Reset out-of-data flag, unless read_restart_marker left us smack up
 673    * against a marker.  In that case we will end up treating the next data
 674    * segment as empty, and we can avoid producing bogus output pixels by
 675    * leaving the flag set.
 676    */
 677   if (cinfo->unread_marker == 0)
 678     entropy->insufficient_data = FALSE;
 679 
 680   return TRUE;
 681 }
 682 
 683 
 684 /*
 685  * Huffman MCU decoding.
 686  * Each of these routines decodes and returns one MCU's worth of
 687  * Huffman-compressed coefficients. 
 688  * The coefficients are reordered from zigzag order into natural array order,
 689  * but are not dequantized.
 690  *
 691  * The i'th block of the MCU is stored into the block pointed to by
 692  * MCU_data[i].  WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
 693  * (Wholesale zeroing is usually a little faster than retail...)
 694  *
 695  * We return FALSE if data source requested suspension.  In that case no
 696  * changes have been made to permanent state.  (Exception: some output
 697  * coefficients may already have been assigned.  This is harmless for
 698  * spectral selection, since we'll just re-assign them on the next call.
 699  * Successive approximation AC refinement has to be more careful, however.)
 700  */
 701 
 702 /*
 703  * MCU decoding for DC initial scan (either spectral selection,
 704  * or first pass of successive approximation).
 705  */
 706 
 707 METHODDEF(boolean)
 708 decode_mcu_DC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 709 {   
 710   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 711   int Al = cinfo->Al;
 712   register int s, r;
 713   int blkn, ci;
 714   JBLOCKROW block;
 715   BITREAD_STATE_VARS;
 716   savable_state state;
 717   d_derived_tbl * tbl;
 718   jpeg_component_info * compptr;
 719 
 720   /* Process restart marker if needed; may have to suspend */
 721   if (cinfo->restart_interval) {
 722     if (entropy->restarts_to_go == 0)
 723       if (! process_restart(cinfo))
 724         return FALSE;
 725   }
 726 
 727   /* If we've run out of data, just leave the MCU set to zeroes.
 728    * This way, we return uniform gray for the remainder of the segment.
 729    */
 730   if (! entropy->insufficient_data) {
 731 
 732     /* Load up working state */
 733     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 734     ASSIGN_STATE(state, entropy->saved);
 735 
 736     /* Outer loop handles each block in the MCU */
 737 
 738     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 739       block = MCU_data[blkn];
 740       ci = cinfo->MCU_membership[blkn];
 741       compptr = cinfo->cur_comp_info[ci];
 742       tbl = entropy->derived_tbls[compptr->dc_tbl_no];
 743 
 744       /* Decode a single block's worth of coefficients */
 745 
 746       /* Section F.2.2.1: decode the DC coefficient difference */
 747       HUFF_DECODE(s, br_state, tbl, return FALSE, label1);
 748       if (s) {
 749         CHECK_BIT_BUFFER(br_state, s, return FALSE);
 750         r = GET_BITS(s);
 751         s = HUFF_EXTEND(r, s);
 752       }
 753 
 754       /* Convert DC difference to actual value, update last_dc_val */
 755       s += state.last_dc_val[ci];
 756       state.last_dc_val[ci] = s;
 757       /* Scale and output the coefficient (assumes jpeg_natural_order[0]=0) */
 758       (*block)[0] = (JCOEF) (s << Al);
 759     }
 760 
 761     /* Completed MCU, so update state */
 762     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
 763     ASSIGN_STATE(entropy->saved, state);
 764   }
 765 
 766   /* Account for restart interval (no-op if not using restarts) */
 767   entropy->restarts_to_go--;
 768 
 769   return TRUE;
 770 }
 771 
 772 
 773 /*
 774  * MCU decoding for AC initial scan (either spectral selection,
 775  * or first pass of successive approximation).
 776  */
 777 
 778 METHODDEF(boolean)
 779 decode_mcu_AC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 780 {   
 781   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 782   register int s, k, r;
 783   unsigned int EOBRUN;
 784   int Se, Al;
 785   const int * natural_order;
 786   JBLOCKROW block;
 787   BITREAD_STATE_VARS;
 788   d_derived_tbl * tbl;
 789 
 790   /* Process restart marker if needed; may have to suspend */
 791   if (cinfo->restart_interval) {
 792     if (entropy->restarts_to_go == 0)
 793       if (! process_restart(cinfo))
 794         return FALSE;
 795   }
 796 
 797   /* If we've run out of data, just leave the MCU set to zeroes.
 798    * This way, we return uniform gray for the remainder of the segment.
 799    */
 800   if (! entropy->insufficient_data) {
 801 
 802     /* Load up working state.
 803      * We can avoid loading/saving bitread state if in an EOB run.
 804      */
 805     EOBRUN = entropy->saved.EOBRUN;  /* only part of saved state we need */
 806 
 807     /* There is always only one block per MCU */
 808 
 809     if (EOBRUN)                 /* if it's a band of zeroes... */
 810       EOBRUN--;                 /* ...process it now (we do nothing) */
 811     else {
 812       BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 813       Se = cinfo->Se;
 814       Al = cinfo->Al;
 815       natural_order = cinfo->natural_order;
 816       block = MCU_data[0];
 817       tbl = entropy->ac_derived_tbl;
 818 
 819       for (k = cinfo->Ss; k <= Se; k++) {
 820         HUFF_DECODE(s, br_state, tbl, return FALSE, label2);
 821         r = s >> 4;
 822         s &= 15;
 823         if (s) {
 824           k += r;
 825           CHECK_BIT_BUFFER(br_state, s, return FALSE);
 826           r = GET_BITS(s);
 827           s = HUFF_EXTEND(r, s);
 828           /* Scale and output coefficient in natural (dezigzagged) order */
 829           (*block)[natural_order[k]] = (JCOEF) (s << Al);
 830         } else {
 831           if (r != 15) {        /* EOBr, run length is 2^r + appended bits */
 832             if (r) {            /* EOBr, r > 0 */
 833               EOBRUN = 1 << r;
 834               CHECK_BIT_BUFFER(br_state, r, return FALSE);
 835               r = GET_BITS(r);
 836               EOBRUN += r;
 837               EOBRUN--;         /* this band is processed at this moment */
 838             }
 839             break;              /* force end-of-band */
 840           }
 841           k += 15;              /* ZRL: skip 15 zeroes in band */
 842         }
 843       }
 844 
 845       BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
 846     }
 847 
 848     /* Completed MCU, so update state */
 849     entropy->saved.EOBRUN = EOBRUN;  /* only part of saved state we need */
 850   }
 851 
 852   /* Account for restart interval (no-op if not using restarts) */
 853   entropy->restarts_to_go--;
 854 
 855   return TRUE;
 856 }
 857 
 858 
 859 /*
 860  * MCU decoding for DC successive approximation refinement scan.
 861  * Note: we assume such scans can be multi-component,
 862  * although the spec is not very clear on the point.
 863  */
 864 
 865 METHODDEF(boolean)
 866 decode_mcu_DC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 867 {   
 868   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 869   int p1, blkn;
 870   BITREAD_STATE_VARS;
 871 
 872   /* Process restart marker if needed; may have to suspend */
 873   if (cinfo->restart_interval) {
 874     if (entropy->restarts_to_go == 0)
 875       if (! process_restart(cinfo))
 876         return FALSE;
 877   }
 878 
 879   /* Not worth the cycles to check insufficient_data here,
 880    * since we will not change the data anyway if we read zeroes.
 881    */
 882 
 883   /* Load up working state */
 884   BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 885 
 886   p1 = 1 << cinfo->Al;         /* 1 in the bit position being coded */
 887 
 888   /* Outer loop handles each block in the MCU */
 889 
 890   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 891     /* Encoded data is simply the next bit of the two's-complement DC value */
 892     CHECK_BIT_BUFFER(br_state, 1, return FALSE);
 893     if (GET_BITS(1))
 894       MCU_data[blkn][0][0] |= p1;
 895     /* Note: since we use |=, repeating the assignment later is safe */
 896   }
 897 
 898   /* Completed MCU, so update state */
 899   BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
 900 
 901   /* Account for restart interval (no-op if not using restarts) */
 902   entropy->restarts_to_go--;
 903 
 904   return TRUE;
 905 }
 906 
 907 
 908 /*
 909  * MCU decoding for AC successive approximation refinement scan.
 910  */
 911 
 912 METHODDEF(boolean)
 913 decode_mcu_AC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 914 {   
 915   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 916   register int s, k, r;
 917   unsigned int EOBRUN;
 918   int Se, p1, m1;
 919   const int * natural_order;
 920   JBLOCKROW block;
 921   JCOEFPTR thiscoef;
 922   BITREAD_STATE_VARS;
 923   d_derived_tbl * tbl;
 924   int num_newnz;
 925   int newnz_pos[DCTSIZE2];
 926 
 927   /* Process restart marker if needed; may have to suspend */
 928   if (cinfo->restart_interval) {
 929     if (entropy->restarts_to_go == 0)
 930       if (! process_restart(cinfo))
 931         return FALSE;
 932   }
 933 
 934   /* If we've run out of data, don't modify the MCU.
 935    */
 936   if (! entropy->insufficient_data) {
 937 
 938     Se = cinfo->Se;
 939     p1 = 1 << cinfo->Al;       /* 1 in the bit position being coded */
 940     m1 = (-1) << cinfo->Al;    /* -1 in the bit position being coded */
 941     natural_order = cinfo->natural_order;
 942 
 943     /* Load up working state */
 944     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 945     EOBRUN = entropy->saved.EOBRUN; /* only part of saved state we need */
 946 
 947     /* There is always only one block per MCU */
 948     block = MCU_data[0];
 949     tbl = entropy->ac_derived_tbl;
 950 
 951     /* If we are forced to suspend, we must undo the assignments to any newly
 952      * nonzero coefficients in the block, because otherwise we'd get confused
 953      * next time about which coefficients were already nonzero.
 954      * But we need not undo addition of bits to already-nonzero coefficients;
 955      * instead, we can test the current bit to see if we already did it.
 956      */
 957     num_newnz = 0;
 958 
 959     /* initialize coefficient loop counter to start of band */
 960     k = cinfo->Ss;
 961 
 962     if (EOBRUN == 0) {
 963       do {
 964         HUFF_DECODE(s, br_state, tbl, goto undoit, label3);
 965         r = s >> 4;
 966         s &= 15;
 967         if (s) {
 968           if (s != 1)           /* size of new coef should always be 1 */
 969             WARNMS(cinfo, JWRN_HUFF_BAD_CODE);
 970           CHECK_BIT_BUFFER(br_state, 1, goto undoit);
 971           if (GET_BITS(1))
 972             s = p1;             /* newly nonzero coef is positive */
 973           else
 974             s = m1;             /* newly nonzero coef is negative */
 975         } else {
 976           if (r != 15) {
 977             EOBRUN = 1 << r;      /* EOBr, run length is 2^r + appended bits */
 978             if (r) {
 979               CHECK_BIT_BUFFER(br_state, r, goto undoit);
 980               r = GET_BITS(r);
 981               EOBRUN += r;
 982             }
 983             break;              /* rest of block is handled by EOB logic */
 984           }
 985           /* note s = 0 for processing ZRL */
 986         }
 987         /* Advance over already-nonzero coefs and r still-zero coefs,
 988          * appending correction bits to the nonzeroes.  A correction bit is 1
 989          * if the absolute value of the coefficient must be increased.
 990          */
 991         do {
 992           thiscoef = *block + natural_order[k];
 993           if (*thiscoef) {
 994             CHECK_BIT_BUFFER(br_state, 1, goto undoit);
 995             if (GET_BITS(1)) {
 996               if ((*thiscoef & p1) == 0) { /* do nothing if already set it */
 997                 if (*thiscoef >= 0)
 998                   *thiscoef += p1;
 999                 else
1000                   *thiscoef += m1;
1001               }
1002             }
1003           } else {
1004             if (--r < 0)
1005               break;            /* reached target zero coefficient */
1006           }
1007           k++;
1008         } while (k <= Se);
1009         if (s) {
1010           int pos = natural_order[k];
1011           /* Output newly nonzero coefficient */
1012           (*block)[pos] = (JCOEF) s;
1013           /* Remember its position in case we have to suspend */
1014           newnz_pos[num_newnz++] = pos;
1015         }
1016         k++;
1017       } while (k <= Se);
1018     }
1019 
1020     if (EOBRUN) {
1021       /* Scan any remaining coefficient positions after the end-of-band
1022        * (the last newly nonzero coefficient, if any).  Append a correction
1023        * bit to each already-nonzero coefficient.  A correction bit is 1
1024        * if the absolute value of the coefficient must be increased.
1025        */
1026       do {
1027         thiscoef = *block + natural_order[k];
1028         if (*thiscoef) {
1029           CHECK_BIT_BUFFER(br_state, 1, goto undoit);
1030           if (GET_BITS(1)) {
1031             if ((*thiscoef & p1) == 0) { /* do nothing if already changed it */
1032               if (*thiscoef >= 0)
1033                 *thiscoef += p1;
1034               else
1035                 *thiscoef += m1;
1036             }
1037           }
1038         }
1039         k++;
1040       } while (k <= Se);
1041       /* Count one block completed in EOB run */
1042       EOBRUN--;
1043     }
1044 
1045     /* Completed MCU, so update state */
1046     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
1047     entropy->saved.EOBRUN = EOBRUN; /* only part of saved state we need */
1048   }
1049 
1050   /* Account for restart interval (no-op if not using restarts) */
1051   entropy->restarts_to_go--;
1052 
1053   return TRUE;
1054 
1055 undoit:
1056   /* Re-zero any output coefficients that we made newly nonzero */
1057   while (num_newnz)
1058     (*block)[newnz_pos[--num_newnz]] = 0;
1059 
1060   return FALSE;
1061 }
1062 
1063 
1064 /*
1065  * Decode one MCU's worth of Huffman-compressed coefficients,
1066  * partial blocks.
1067  */
1068 
1069 METHODDEF(boolean)
1070 decode_mcu_sub (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
1071 {
1072   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1073   const int * natural_order;
1074   int Se, blkn;
1075   BITREAD_STATE_VARS;
1076   savable_state state;
1077 
1078   /* Process restart marker if needed; may have to suspend */
1079   if (cinfo->restart_interval) {
1080     if (entropy->restarts_to_go == 0)
1081       if (! process_restart(cinfo))
1082         return FALSE;
1083   }
1084 
1085   /* If we've run out of data, just leave the MCU set to zeroes.
1086    * This way, we return uniform gray for the remainder of the segment.
1087    */
1088   if (! entropy->insufficient_data) {
1089 
1090     natural_order = cinfo->natural_order;
1091     Se = cinfo->lim_Se;
1092 
1093     /* Load up working state */
1094     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
1095     ASSIGN_STATE(state, entropy->saved);
1096 
1097     /* Outer loop handles each block in the MCU */
1098 
1099     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1100       JBLOCKROW block = MCU_data[blkn];
1101       d_derived_tbl * htbl;
1102       register int s, k, r;
1103       int coef_limit, ci;
1104 
1105       /* Decode a single block's worth of coefficients */
1106 
1107       /* Section F.2.2.1: decode the DC coefficient difference */
1108       htbl = entropy->dc_cur_tbls[blkn];
1109       HUFF_DECODE(s, br_state, htbl, return FALSE, label1);
1110 
1111       htbl = entropy->ac_cur_tbls[blkn];
1112       k = 1;
1113       coef_limit = entropy->coef_limit[blkn];
1114       if (coef_limit) {
1115         /* Convert DC difference to actual value, update last_dc_val */
1116         if (s) {
1117           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1118           r = GET_BITS(s);
1119           s = HUFF_EXTEND(r, s);
1120         }
1121         ci = cinfo->MCU_membership[blkn];
1122         s += state.last_dc_val[ci];
1123         state.last_dc_val[ci] = s;
1124         /* Output the DC coefficient */
1125         (*block)[0] = (JCOEF) s;
1126 
1127         /* Section F.2.2.2: decode the AC coefficients */
1128         /* Since zeroes are skipped, output area must be cleared beforehand */
1129         for (; k < coef_limit; k++) {
1130           HUFF_DECODE(s, br_state, htbl, return FALSE, label2);
1131 
1132           r = s >> 4;
1133           s &= 15;
1134 
1135           if (s) {
1136             k += r;
1137             CHECK_BIT_BUFFER(br_state, s, return FALSE);
1138             r = GET_BITS(s);
1139             s = HUFF_EXTEND(r, s);
1140             /* Output coefficient in natural (dezigzagged) order.
1141              * Note: the extra entries in natural_order[] will save us
1142              * if k > Se, which could happen if the data is corrupted.
1143              */
1144             (*block)[natural_order[k]] = (JCOEF) s;
1145           } else {
1146             if (r != 15)
1147               goto EndOfBlock;
1148             k += 15;
1149           }
1150         }
1151       } else {
1152         if (s) {
1153           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1154           DROP_BITS(s);
1155         }
1156       }
1157 
1158       /* Section F.2.2.2: decode the AC coefficients */
1159       /* In this path we just discard the values */
1160       for (; k <= Se; k++) {
1161         HUFF_DECODE(s, br_state, htbl, return FALSE, label3);
1162 
1163         r = s >> 4;
1164         s &= 15;
1165 
1166         if (s) {
1167           k += r;
1168           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1169           DROP_BITS(s);
1170         } else {
1171           if (r != 15)
1172             break;
1173           k += 15;
1174         }
1175       }
1176 
1177       EndOfBlock: ;
1178     }
1179 
1180     /* Completed MCU, so update state */
1181     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
1182     ASSIGN_STATE(entropy->saved, state);
1183   }
1184 
1185   /* Account for restart interval (no-op if not using restarts) */
1186   entropy->restarts_to_go--;
1187 
1188   return TRUE;
1189 }
1190 
1191 
1192 /*
1193  * Decode one MCU's worth of Huffman-compressed coefficients,
1194  * full-size blocks.
1195  */
1196 
1197 METHODDEF(boolean)
1198 decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
1199 {
1200   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1201   int blkn;
1202   BITREAD_STATE_VARS;
1203   savable_state state;
1204 
1205   /* Process restart marker if needed; may have to suspend */
1206   if (cinfo->restart_interval) {
1207     if (entropy->restarts_to_go == 0)
1208       if (! process_restart(cinfo))
1209         return FALSE;
1210   }
1211 
1212   /* If we've run out of data, just leave the MCU set to zeroes.
1213    * This way, we return uniform gray for the remainder of the segment.
1214    */
1215   if (! entropy->insufficient_data) {
1216 
1217     /* Load up working state */
1218     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
1219     ASSIGN_STATE(state, entropy->saved);
1220 
1221     /* Outer loop handles each block in the MCU */
1222 
1223     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1224       JBLOCKROW block = MCU_data[blkn];
1225       d_derived_tbl * htbl;
1226       register int s, k, r;
1227       int coef_limit, ci;
1228 
1229       /* Decode a single block's worth of coefficients */
1230 
1231       /* Section F.2.2.1: decode the DC coefficient difference */
1232       htbl = entropy->dc_cur_tbls[blkn];
1233       HUFF_DECODE(s, br_state, htbl, return FALSE, label1);
1234 
1235       htbl = entropy->ac_cur_tbls[blkn];
1236       k = 1;
1237       coef_limit = entropy->coef_limit[blkn];
1238       if (coef_limit) {
1239         /* Convert DC difference to actual value, update last_dc_val */
1240         if (s) {
1241           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1242           r = GET_BITS(s);
1243           s = HUFF_EXTEND(r, s);
1244         }
1245         ci = cinfo->MCU_membership[blkn];
1246         s += state.last_dc_val[ci];
1247         state.last_dc_val[ci] = s;
1248         /* Output the DC coefficient */
1249         (*block)[0] = (JCOEF) s;
1250 
1251         /* Section F.2.2.2: decode the AC coefficients */
1252         /* Since zeroes are skipped, output area must be cleared beforehand */
1253         for (; k < coef_limit; k++) {
1254           HUFF_DECODE(s, br_state, htbl, return FALSE, label2);
1255 
1256           r = s >> 4;
1257           s &= 15;
1258 
1259           if (s) {
1260             k += r;
1261             CHECK_BIT_BUFFER(br_state, s, return FALSE);
1262             r = GET_BITS(s);
1263             s = HUFF_EXTEND(r, s);
1264             /* Output coefficient in natural (dezigzagged) order.
1265              * Note: the extra entries in jpeg_natural_order[] will save us
1266              * if k >= DCTSIZE2, which could happen if the data is corrupted.
1267              */
1268             (*block)[jpeg_natural_order[k]] = (JCOEF) s;
1269           } else {
1270             if (r != 15)
1271               goto EndOfBlock;
1272             k += 15;
1273           }
1274         }
1275       } else {
1276         if (s) {
1277           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1278           DROP_BITS(s);
1279         }
1280       }
1281 
1282       /* Section F.2.2.2: decode the AC coefficients */
1283       /* In this path we just discard the values */
1284       for (; k < DCTSIZE2; k++) {
1285         HUFF_DECODE(s, br_state, htbl, return FALSE, label3);
1286 
1287         r = s >> 4;
1288         s &= 15;
1289 
1290         if (s) {
1291           k += r;
1292           CHECK_BIT_BUFFER(br_state, s, return FALSE);
1293           DROP_BITS(s);
1294         } else {
1295           if (r != 15)
1296             break;
1297           k += 15;
1298         }
1299       }
1300 
1301       EndOfBlock: ;
1302     }
1303 
1304     /* Completed MCU, so update state */
1305     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
1306     ASSIGN_STATE(entropy->saved, state);
1307   }
1308 
1309   /* Account for restart interval (no-op if not using restarts) */
1310   entropy->restarts_to_go--;
1311 
1312   return TRUE;
1313 }
1314 
1315 
1316 /*
1317  * Initialize for a Huffman-compressed scan.
1318  */
1319 
1320 METHODDEF(void)
1321 start_pass_huff_decoder (j_decompress_ptr cinfo)
1322 {
1323   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1324   int ci, blkn, tbl, i;
1325   jpeg_component_info * compptr;
1326 
1327   if (cinfo->progressive_mode) {
1328     /* Validate progressive scan parameters */
1329     if (cinfo->Ss == 0) {
1330       if (cinfo->Se != 0)
1331         goto bad;
1332     } else {
1333       /* need not check Ss/Se < 0 since they came from unsigned bytes */
1334       if (cinfo->Se < cinfo->Ss || cinfo->Se > cinfo->lim_Se)
1335         goto bad;
1336       /* AC scans may have only one component */
1337       if (cinfo->comps_in_scan != 1)
1338         goto bad;
1339     }
1340     if (cinfo->Ah != 0) {
1341       /* Successive approximation refinement scan: must have Al = Ah-1. */
1342       if (cinfo->Ah-1 != cinfo->Al)
1343         goto bad;
1344     }
1345     if (cinfo->Al > 13) { /* need not check for < 0 */
1346       /* Arguably the maximum Al value should be less than 13 for 8-bit precision,
1347        * but the spec doesn't say so, and we try to be liberal about what we
1348        * accept.  Note: large Al values could result in out-of-range DC
1349        * coefficients during early scans, leading to bizarre displays due to
1350        * overflows in the IDCT math.  But we won't crash.
1351        */
1352       bad:
1353       ERREXIT4(cinfo, JERR_BAD_PROGRESSION,
1354                cinfo->Ss, cinfo->Se, cinfo->Ah, cinfo->Al);
1355     }
1356     /* Update progression status, and verify that scan order is legal.
1357      * Note that inter-scan inconsistencies are treated as warnings
1358      * not fatal errors ... not clear if this is right way to behave.
1359      */
1360     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1361       int coefi, cindex = cinfo->cur_comp_info[ci]->component_index;
1362       int *coef_bit_ptr = & cinfo->coef_bits[cindex][0];
1363       if (cinfo->Ss && coef_bit_ptr[0] < 0) /* AC without prior DC scan */
1364         WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, 0);
1365       for (coefi = cinfo->Ss; coefi <= cinfo->Se; coefi++) {
1366         int expected = (coef_bit_ptr[coefi] < 0) ? 0 : coef_bit_ptr[coefi];
1367         if (cinfo->Ah != expected)
1368           WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, coefi);
1369         coef_bit_ptr[coefi] = cinfo->Al;
1370       }
1371     }
1372 
1373     /* Select MCU decoding routine */
1374     if (cinfo->Ah == 0) {
1375       if (cinfo->Ss == 0)
1376         entropy->pub.decode_mcu = decode_mcu_DC_first;
1377       else
1378         entropy->pub.decode_mcu = decode_mcu_AC_first;
1379     } else {
1380       if (cinfo->Ss == 0)
1381         entropy->pub.decode_mcu = decode_mcu_DC_refine;
1382       else
1383         entropy->pub.decode_mcu = decode_mcu_AC_refine;
1384     }
1385 
1386     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1387       compptr = cinfo->cur_comp_info[ci];
1388       /* Make sure requested tables are present, and compute derived tables.
1389        * We may build same derived table more than once, but it's not expensive.
1390        */
1391       if (cinfo->Ss == 0) {
1392         if (cinfo->Ah == 0) {        /* DC refinement needs no table */
1393           tbl = compptr->dc_tbl_no;
1394           jpeg_make_d_derived_tbl(cinfo, TRUE, tbl,
1395                                   & entropy->derived_tbls[tbl]);
1396         }
1397       } else {
1398         tbl = compptr->ac_tbl_no;
1399         jpeg_make_d_derived_tbl(cinfo, FALSE, tbl,
1400                                 & entropy->derived_tbls[tbl]);
1401         /* remember the single active table */
1402         entropy->ac_derived_tbl = entropy->derived_tbls[tbl];
1403       }
1404       /* Initialize DC predictions to 0 */
1405       entropy->saved.last_dc_val[ci] = 0;
1406     }
1407 
1408     /* Initialize private state variables */
1409     entropy->saved.EOBRUN = 0;
1410   } else {
1411     /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
1412      * This ought to be an error condition, but we make it a warning because
1413      * there are some baseline files out there with all zeroes in these bytes.
1414      */
1415     if (cinfo->Ss != 0 || cinfo->Ah != 0 || cinfo->Al != 0 ||
1416         ((cinfo->is_baseline || cinfo->Se < DCTSIZE2) &&
1417         cinfo->Se != cinfo->lim_Se))
1418       WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
1419 
1420     /* Select MCU decoding routine */
1421     /* We retain the hard-coded case for full-size blocks.
1422      * This is not necessary, but it appears that this version is slightly
1423      * more performant in the given implementation.
1424      * With an improved implementation we would prefer a single optimized
1425      * function.
1426      */
1427     if (cinfo->lim_Se != DCTSIZE2-1)
1428       entropy->pub.decode_mcu = decode_mcu_sub;
1429     else
1430       entropy->pub.decode_mcu = decode_mcu;
1431 
1432     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1433       compptr = cinfo->cur_comp_info[ci];
1434       /* Compute derived values for Huffman tables */
1435       /* We may do this more than once for a table, but it's not expensive */
1436       tbl = compptr->dc_tbl_no;
1437       jpeg_make_d_derived_tbl(cinfo, TRUE, tbl,
1438                               & entropy->dc_derived_tbls[tbl]);
1439       if (cinfo->lim_Se) {   /* AC needs no table when not present */
1440         tbl = compptr->ac_tbl_no;
1441         jpeg_make_d_derived_tbl(cinfo, FALSE, tbl,
1442                                 & entropy->ac_derived_tbls[tbl]);
1443       }
1444       /* Initialize DC predictions to 0 */
1445       entropy->saved.last_dc_val[ci] = 0;
1446     }
1447 
1448     /* Precalculate decoding info for each block in an MCU of this scan */
1449     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1450       ci = cinfo->MCU_membership[blkn];
1451       compptr = cinfo->cur_comp_info[ci];
1452       /* Precalculate which table to use for each block */
1453       entropy->dc_cur_tbls[blkn] = entropy->dc_derived_tbls[compptr->dc_tbl_no];
1454       entropy->ac_cur_tbls[blkn] = entropy->ac_derived_tbls[compptr->ac_tbl_no];
1455       /* Decide whether we really care about the coefficient values */
1456       if (compptr->component_needed) {
1457         ci = compptr->DCT_v_scaled_size;
1458         i = compptr->DCT_h_scaled_size;
1459         switch (cinfo->lim_Se) {
1460         case (1*1-1):
1461           entropy->coef_limit[blkn] = 1;
1462           break;
1463         case (2*2-1):
1464           if (ci <= 0 || ci > 2) ci = 2;
1465           if (i <= 0 || i > 2) i = 2;
1466           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order2[ci - 1][i - 1];
1467           break;
1468         case (3*3-1):
1469           if (ci <= 0 || ci > 3) ci = 3;
1470           if (i <= 0 || i > 3) i = 3;
1471           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order3[ci - 1][i - 1];
1472           break;
1473         case (4*4-1):
1474           if (ci <= 0 || ci > 4) ci = 4;
1475           if (i <= 0 || i > 4) i = 4;
1476           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order4[ci - 1][i - 1];
1477           break;
1478         case (5*5-1):
1479           if (ci <= 0 || ci > 5) ci = 5;
1480           if (i <= 0 || i > 5) i = 5;
1481           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order5[ci - 1][i - 1];
1482           break;
1483         case (6*6-1):
1484           if (ci <= 0 || ci > 6) ci = 6;
1485           if (i <= 0 || i > 6) i = 6;
1486           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order6[ci - 1][i - 1];
1487           break;
1488         case (7*7-1):
1489           if (ci <= 0 || ci > 7) ci = 7;
1490           if (i <= 0 || i > 7) i = 7;
1491           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order7[ci - 1][i - 1];
1492           break;
1493         default:
1494           if (ci <= 0 || ci > 8) ci = 8;
1495           if (i <= 0 || i > 8) i = 8;
1496           entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order[ci - 1][i - 1];
1497           break;
1498         }
1499       } else {
1500         entropy->coef_limit[blkn] = 0;
1501       }
1502     }
1503   }
1504 
1505   /* Initialize bitread state variables */
1506   entropy->bitstate.bits_left = 0;
1507   entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
1508   entropy->insufficient_data = FALSE;
1509 
1510   /* Initialize restart counter */
1511   entropy->restarts_to_go = cinfo->restart_interval;
1512 }
1513 
1514 
1515 /*
1516  * Module initialization routine for Huffman entropy decoding.
1517  */
1518 
1519 GLOBAL(void)
1520 jinit_huff_decoder (j_decompress_ptr cinfo)
1521 {
1522   huff_entropy_ptr entropy;
1523   int i;
1524 
1525   entropy = (huff_entropy_ptr)
1526     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1527                                 SIZEOF(huff_entropy_decoder));
1528   cinfo->entropy = &entropy->pub;
1529   entropy->pub.start_pass = start_pass_huff_decoder;
1530   entropy->pub.finish_pass = finish_pass_huff;
1531 
1532   if (cinfo->progressive_mode) {
1533     /* Create progression status table */
1534     int *coef_bit_ptr, ci;
1535     cinfo->coef_bits = (int (*)[DCTSIZE2])
1536       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1537                                   cinfo->num_components*DCTSIZE2*SIZEOF(int));
1538     coef_bit_ptr = & cinfo->coef_bits[0][0];
1539     for (ci = 0; ci < cinfo->num_components; ci++)
1540       for (i = 0; i < DCTSIZE2; i++)
1541         *coef_bit_ptr++ = -1;
1542 
1543     /* Mark derived tables unallocated */
1544     for (i = 0; i < NUM_HUFF_TBLS; i++) {
1545       entropy->derived_tbls[i] = NULL;
1546     }
1547   } else {
1548     /* Mark tables unallocated */
1549     for (i = 0; i < NUM_HUFF_TBLS; i++) {
1550       entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1551     }
1552   }
1553 }