jdhuff.c

   1 /*
   2  * jdhuff.c
   3  *
   4  * This file was part of the Independent JPEG Group's software:
   5  * Copyright (C) 1991-1997, Thomas G. Lane.
   6  * libjpeg-turbo Modifications:
   7  * Copyright (C) 2009-2011, 2016, 2018, D. R. Commander.
   8  * For conditions of distribution and use, see the accompanying README.ijg
   9  * file.
  10  *
  11  * This file contains Huffman entropy decoding routines.
  12  *
  13  * Much of the complexity here has to do with supporting input suspension.
  14  * If the data source module demands suspension, we want to be able to back
  15  * up to the start of the current MCU.  To do this, we copy state variables
  16  * into local working storage, and update them back to the permanent
  17  * storage only upon successful completion of an MCU.
  18  *
  19  * NOTE: All referenced figures are from
  20  * Recommendation ITU-T T.81 (1992) | ISO/IEC 10918-1:1994.
  21  */
  22
  23 #define JPEG_INTERNALS
  24 #include "jinclude.h"
  25 #include "jpeglib.h"
  26 #include "jdhuff.h"             /* Declarations shared with jdphuff.c */
  27 #include "jpegcomp.h"
  28 #include "jstdhuff.c"
  29
  30
  31 /*
  32  * Expanded entropy decoder object for Huffman decoding.
  33  *
  34  * The savable_state subrecord contains fields that change within an MCU,
  35  * but must not be updated permanently until we complete the MCU.
  36  */
  37
  38 typedef struct {
  39   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  40 } savable_state;
  41
  42 /* This macro is to work around compilers with missing or broken
  43  * structure assignment.  You'll need to fix this code if you have
  44  * such a compiler and you change MAX_COMPS_IN_SCAN.
  45  */
  46
  47 #ifndef NO_STRUCT_ASSIGN
  48 #define ASSIGN_STATE(dest, src)  ((dest) = (src))
  49 #else
  50 #if MAX_COMPS_IN_SCAN == 4
  51 #define ASSIGN_STATE(dest, src) \
  52   ((dest).last_dc_val[0] = (src).last_dc_val[0], \
  53    (dest).last_dc_val[1] = (src).last_dc_val[1], \
  54    (dest).last_dc_val[2] = (src).last_dc_val[2], \
  55    (dest).last_dc_val[3] = (src).last_dc_val[3])
  56 #endif
  57 #endif
  58
  59
  60 typedef struct {
  61   struct jpeg_entropy_decoder pub; /* public fields */
  62
  63   /* These fields are loaded into local variables at start of each MCU.
  64    * In case of suspension, we exit WITHOUT updating them.
  65    */
  66   bitread_perm_state bitstate;  /* Bit buffer at start of MCU */
  67   savable_state saved;          /* Other state at start of MCU */
  68
  69   /* These fields are NOT loaded into local working state. */
  70   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  71
  72   /* Pointers to derived tables (these workspaces have image lifespan) */
  73   d_derived_tbl *dc_derived_tbls[NUM_HUFF_TBLS];
  74   d_derived_tbl *ac_derived_tbls[NUM_HUFF_TBLS];
  75
  76   /* Precalculated info set up by start_pass for use in decode_mcu: */
  77
  78   /* Pointers to derived tables to be used for each block within an MCU */
  79   d_derived_tbl *dc_cur_tbls[D_MAX_BLOCKS_IN_MCU];
  80   d_derived_tbl *ac_cur_tbls[D_MAX_BLOCKS_IN_MCU];
  81   /* Whether we care about the DC and AC coefficient values for each block */
  82   boolean dc_needed[D_MAX_BLOCKS_IN_MCU];
  83   boolean ac_needed[D_MAX_BLOCKS_IN_MCU];
  84 } huff_entropy_decoder;
  85
  86 typedef huff_entropy_decoder *huff_entropy_ptr;
  87
  88
  89 /*
  90  * Initialize for a Huffman-compressed scan.
  91  */
  92
  93 METHODDEF(void)
  94 start_pass_huff_decoder(j_decompress_ptr cinfo)
  95 {
  96   huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy;
  97   int ci, blkn, dctbl, actbl;
  98   d_derived_tbl **pdtbl;
  99   jpeg_component_info *compptr;
 100
 101   /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
 102    * This ought to be an error condition, but we make it a warning because
 103    * there are some baseline files out there with all zeroes in these bytes.
 104    */
 105   if (cinfo->Ss != 0 || cinfo->Se != DCTSIZE2 - 1 ||
 106       cinfo->Ah != 0 || cinfo->Al != 0)
 107     WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
 108
 109   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 110     compptr = cinfo->cur_comp_info[ci];
 111     dctbl = compptr->dc_tbl_no;
 112     actbl = compptr->ac_tbl_no;
 113     /* Compute derived values for Huffman tables */
 114     /* We may do this more than once for a table, but it's not expensive */
 115     pdtbl = (d_derived_tbl **)(entropy->dc_derived_tbls) + dctbl;
 116     jpeg_make_d_derived_tbl(cinfo, TRUE, dctbl, pdtbl);
 117     pdtbl = (d_derived_tbl **)(entropy->ac_derived_tbls) + actbl;
 118     jpeg_make_d_derived_tbl(cinfo, FALSE, actbl, pdtbl);
 119     /* Initialize DC predictions to 0 */
 120     entropy->saved.last_dc_val[ci] = 0;
 121   }
 122
 123   /* Precalculate decoding info for each block in an MCU of this scan */
 124   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 125     ci = cinfo->MCU_membership[blkn];
 126     compptr = cinfo->cur_comp_info[ci];
 127     /* Precalculate which table to use for each block */
 128     entropy->dc_cur_tbls[blkn] = entropy->dc_derived_tbls[compptr->dc_tbl_no];
 129     entropy->ac_cur_tbls[blkn] = entropy->ac_derived_tbls[compptr->ac_tbl_no];
 130     /* Decide whether we really care about the coefficient values */
 131     if (compptr->component_needed) {
 132       entropy->dc_needed[blkn] = TRUE;
 133       /* we don't need the ACs if producing a 1/8th-size image */
 134       entropy->ac_needed[blkn] = (compptr->_DCT_scaled_size > 1);
 135     } else {
 136       entropy->dc_needed[blkn] = entropy->ac_needed[blkn] = FALSE;
 137     }
 138   }
 139
 140   /* Initialize bitread state variables */
 141   entropy->bitstate.bits_left = 0;
 142   entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
 143   entropy->pub.insufficient_data = FALSE;
 144
 145   /* Initialize restart counter */
 146   entropy->restarts_to_go = cinfo->restart_interval;
 147 }
 148
 149
 150 /*
 151  * Compute the derived values for a Huffman table.
 152  * This routine also performs some validation checks on the table.
 153  *
 154  * Note this is also used by jdphuff.c.
 155  */
 156
 157 GLOBAL(void)
 158 jpeg_make_d_derived_tbl(j_decompress_ptr cinfo, boolean isDC, int tblno,
 159                         d_derived_tbl **pdtbl)
 160 {
 161   JHUFF_TBL *htbl;
 162   d_derived_tbl *dtbl;
 163   int p, i, l, si, numsymbols;
 164   int lookbits, ctr;
 165   char huffsize[257];
 166   unsigned int huffcode[257];
 167   unsigned int code;
 168
 169   /* Note that huffsize[] and huffcode[] are filled in code-length order,
 170    * paralleling the order of the symbols themselves in htbl->huffval[].
 171    */
 172
 173   /* Find the input Huffman table */
 174   if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
 175     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 176   htbl =
 177     isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
 178   if (htbl == NULL)
 179     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 180
 181   /* Allocate a workspace if we haven't already done so. */
 182   if (*pdtbl == NULL)
 183     *pdtbl = (d_derived_tbl *)
 184       (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
 185                                   sizeof(d_derived_tbl));
 186   dtbl = *pdtbl;
 187   dtbl->pub = htbl;             /* fill in back link */
 188
 189   /* Figure C.1: make table of Huffman code length for each symbol */
 190
 191   p = 0;
 192   for (l = 1; l <= 16; l++) {
 193     i = (int)htbl->bits[l];
 194     if (i < 0 || p + i > 256)   /* protect against table overrun */
 195       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 196     while (i--)
 197       huffsize[p++] = (char)l;
 198   }
 199   huffsize[p] = 0;
 200   numsymbols = p;
 201
 202   /* Figure C.2: generate the codes themselves */
 203   /* We also validate that the counts represent a legal Huffman code tree. */
 204
 205   code = 0;
 206   si = huffsize[0];
 207   p = 0;
 208   while (huffsize[p]) {
 209     while (((int)huffsize[p]) == si) {
 210       huffcode[p++] = code;
 211       code++;
 212     }
 213     /* code is now 1 more than the last code used for codelength si; but
 214      * it must still fit in si bits, since no code is allowed to be all ones.
 215      */
 216     if (((JLONG)code) >= (((JLONG)1) << si))
 217       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 218     code <<= 1;
 219     si++;
 220   }
 221
 222   /* Figure F.15: generate decoding tables for bit-sequential decoding */
 223
 224   p = 0;
 225   for (l = 1; l <= 16; l++) {
 226     if (htbl->bits[l]) {
 227       /* valoffset[l] = huffval[] index of 1st symbol of code length l,
 228        * minus the minimum code of length l
 229        */
 230       dtbl->valoffset[l] = (JLONG)p - (JLONG)huffcode[p];
 231       p += htbl->bits[l];
 232       dtbl->maxcode[l] = huffcode[p - 1]; /* maximum code of length l */
 233     } else {
 234       dtbl->maxcode[l] = -1;    /* -1 if no codes of this length */
 235     }
 236   }
 237   dtbl->valoffset[17] = 0;
 238   dtbl->maxcode[17] = 0xFFFFFL; /* ensures jpeg_huff_decode terminates */
 239
 240   /* Compute lookahead tables to speed up decoding.
 241    * First we set all the table entries to 0, indicating "too long";
 242    * then we iterate through the Huffman codes that are short enough and
 243    * fill in all the entries that correspond to bit sequences starting
 244    * with that code.
 245    */
 246
 247   for (i = 0; i < (1 << HUFF_LOOKAHEAD); i++)
 248     dtbl->lookup[i] = (HUFF_LOOKAHEAD + 1) << HUFF_LOOKAHEAD;
 249
 250   p = 0;
 251   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
 252     for (i = 1; i <= (int)htbl->bits[l]; i++, p++) {
 253       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
 254       /* Generate left-justified code followed by all possible bit sequences */
 255       lookbits = huffcode[p] << (HUFF_LOOKAHEAD - l);
 256       for (ctr = 1 << (HUFF_LOOKAHEAD - l); ctr > 0; ctr--) {
 257         dtbl->lookup[lookbits] = (l << HUFF_LOOKAHEAD) | htbl->huffval[p];
 258         lookbits++;
 259       }
 260     }
 261   }
 262
 263   /* Validate symbols as being reasonable.
 264    * For AC tables, we make no check, but accept all byte values 0..255.
 265    * For DC tables, we require the symbols to be in range 0..15.
 266    * (Tighter bounds could be applied depending on the data depth and mode,
 267    * but this is sufficient to ensure safe decoding.)
 268    */
 269   if (isDC) {
 270     for (i = 0; i < numsymbols; i++) {
 271       int sym = htbl->huffval[i];
 272       if (sym < 0 || sym > 15)
 273         ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 274     }
 275   }
 276 }
 277
 278
 279 /*
 280  * Out-of-line code for bit fetching (shared with jdphuff.c).
 281  * See jdhuff.h for info about usage.
 282  * Note: current values of get_buffer and bits_left are passed as parameters,
 283  * but are returned in the corresponding fields of the state struct.
 284  *
 285  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
 286  * of get_buffer to be used.  (On machines with wider words, an even larger
 287  * buffer could be used.)  However, on some machines 32-bit shifts are
 288  * quite slow and take time proportional to the number of places shifted.
 289  * (This is true with most PC compilers, for instance.)  In this case it may
 290  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
 291  * average shift distance at the cost of more calls to jpeg_fill_bit_buffer.
 292  */
 293
 294 #ifdef SLOW_SHIFT_32
 295 #define MIN_GET_BITS  15        /* minimum allowable value */
 296 #else
 297 #define MIN_GET_BITS  (BIT_BUF_SIZE - 7)
 298 #endif
 299
 300
 301 GLOBAL(boolean)
 302 jpeg_fill_bit_buffer(bitread_working_state *state,
 303                      register bit_buf_type get_buffer, register int bits_left,
 304                      int nbits)
 305 /* Load up the bit buffer to a depth of at least nbits */
 306 {
 307   /* Copy heavily used state fields into locals (hopefully registers) */
 308   register const JOCTET *next_input_byte = state->next_input_byte;
 309   register size_t bytes_in_buffer = state->bytes_in_buffer;
 310   j_decompress_ptr cinfo = state->cinfo;
 311
 312   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
 313   /* (It is assumed that no request will be for more than that many bits.) */
 314   /* We fail to do so only if we hit a marker or are forced to suspend. */
 315
 316   if (cinfo->unread_marker == 0) {      /* cannot advance past a marker */
 317     while (bits_left < MIN_GET_BITS) {
 318       register int c;
 319
 320       /* Attempt to read a byte */
 321       if (bytes_in_buffer == 0) {
 322         if (!(*cinfo->src->fill_input_buffer) (cinfo))
 323           return FALSE;
 324         next_input_byte = cinfo->src->next_input_byte;
 325         bytes_in_buffer = cinfo->src->bytes_in_buffer;
 326       }
 327       bytes_in_buffer--;
 328       c = GETJOCTET(*next_input_byte++);
 329
 330       /* If it's 0xFF, check and discard stuffed zero byte */
 331       if (c == 0xFF) {
 332         /* Loop here to discard any padding FF's on terminating marker,
 333          * so that we can save a valid unread_marker value.  NOTE: we will
 334          * accept multiple FF's followed by a 0 as meaning a single FF data
 335          * byte.  This data pattern is not valid according to the standard.
 336          */
 337         do {
 338           if (bytes_in_buffer == 0) {
 339             if (!(*cinfo->src->fill_input_buffer) (cinfo))
 340               return FALSE;
 341             next_input_byte = cinfo->src->next_input_byte;
 342             bytes_in_buffer = cinfo->src->bytes_in_buffer;
 343           }
 344           bytes_in_buffer--;
 345           c = GETJOCTET(*next_input_byte++);
 346         } while (c == 0xFF);
 347
 348         if (c == 0) {
 349           /* Found FF/00, which represents an FF data byte */
 350           c = 0xFF;
 351         } else {
 352           /* Oops, it's actually a marker indicating end of compressed data.
 353            * Save the marker code for later use.
 354            * Fine point: it might appear that we should save the marker into
 355            * bitread working state, not straight into permanent state.  But
 356            * once we have hit a marker, we cannot need to suspend within the
 357            * current MCU, because we will read no more bytes from the data
 358            * source.  So it is OK to update permanent state right away.
 359            */
 360           cinfo->unread_marker = c;
 361           /* See if we need to insert some fake zero bits. */
 362           goto no_more_bytes;
 363         }
 364       }
 365
 366       /* OK, load c into get_buffer */
 367       get_buffer = (get_buffer << 8) | c;
 368       bits_left += 8;
 369     } /* end while */
 370   } else {
 371 no_more_bytes:
 372     /* We get here if we've read the marker that terminates the compressed
 373      * data segment.  There should be enough bits in the buffer register
 374      * to satisfy the request; if so, no problem.
 375      */
 376     if (nbits > bits_left) {
 377       /* Uh-oh.  Report corrupted data to user and stuff zeroes into
 378        * the data stream, so that we can produce some kind of image.
 379        * We use a nonvolatile flag to ensure that only one warning message
 380        * appears per data segment.
 381        */
 382       if (!cinfo->entropy->insufficient_data) {
 383         WARNMS(cinfo, JWRN_HIT_MARKER);
 384         cinfo->entropy->insufficient_data = TRUE;
 385       }
 386       /* Fill the buffer with zero bits */
 387       get_buffer <<= MIN_GET_BITS - bits_left;
 388       bits_left = MIN_GET_BITS;
 389     }
 390   }
 391
 392   /* Unload the local registers */
 393   state->next_input_byte = next_input_byte;
 394   state->bytes_in_buffer = bytes_in_buffer;
 395   state->get_buffer = get_buffer;
 396   state->bits_left = bits_left;
 397
 398   return TRUE;
 399 }
 400
 401
 402 /* Macro version of the above, which performs much better but does not
 403    handle markers.  We have to hand off any blocks with markers to the
 404    slower routines. */
 405
 406 #define GET_BYTE { \
 407   register int c0, c1; \
 408   c0 = GETJOCTET(*buffer++); \
 409   c1 = GETJOCTET(*buffer); \
 410   /* Pre-execute most common case */ \
 411   get_buffer = (get_buffer << 8) | c0; \
 412   bits_left += 8; \
 413   if (c0 == 0xFF) { \
 414     /* Pre-execute case of FF/00, which represents an FF data byte */ \
 415     buffer++; \
 416     if (c1 != 0) { \
 417       /* Oops, it's actually a marker indicating end of compressed data. */ \
 418       cinfo->unread_marker = c1; \
 419       /* Back out pre-execution and fill the buffer with zero bits */ \
 420       buffer -= 2; \
 421       get_buffer &= ~0xFF; \
 422     } \
 423   } \
 424 }
 425
 426 #if SIZEOF_SIZE_T == 8 || defined(_WIN64)
 427
 428 /* Pre-fetch 48 bytes, because the holding register is 64-bit */
 429 #define FILL_BIT_BUFFER_FAST \
 430   if (bits_left <= 16) { \
 431     GET_BYTE GET_BYTE GET_BYTE GET_BYTE GET_BYTE GET_BYTE \
 432   }
 433
 434 #else
 435
 436 /* Pre-fetch 16 bytes, because the holding register is 32-bit */
 437 #define FILL_BIT_BUFFER_FAST \
 438   if (bits_left <= 16) { \
 439     GET_BYTE GET_BYTE \
 440   }
 441
 442 #endif
 443
 444
 445 /*
 446  * Out-of-line code for Huffman code decoding.
 447  * See jdhuff.h for info about usage.
 448  */
 449
 450 GLOBAL(int)
 451 jpeg_huff_decode(bitread_working_state *state,
 452                  register bit_buf_type get_buffer, register int bits_left,
 453                  d_derived_tbl *htbl, int min_bits)
 454 {
 455   register int l = min_bits;
 456   register JLONG code;
 457
 458   /* HUFF_DECODE has determined that the code is at least min_bits */
 459   /* bits long, so fetch that many bits in one swoop. */
 460
 461   CHECK_BIT_BUFFER(*state, l, return -1);
 462   code = GET_BITS(l);
 463
 464   /* Collect the rest of the Huffman code one bit at a time. */
 465   /* This is per Figure F.16. */
 466
 467   while (code > htbl->maxcode[l]) {
 468     code <<= 1;
 469     CHECK_BIT_BUFFER(*state, 1, return -1);
 470     code |= GET_BITS(1);
 471     l++;
 472   }
 473
 474   /* Unload the local registers */
 475   state->get_buffer = get_buffer;
 476   state->bits_left = bits_left;
 477
 478   /* With garbage input we may reach the sentinel value l = 17. */
 479
 480   if (l > 16) {
 481     WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
 482     return 0;                   /* fake a zero as the safest result */
 483   }
 484
 485   return htbl->pub->huffval[(int)(code + htbl->valoffset[l])];
 486 }
 487
 488
 489 /*
 490  * Figure F.12: extend sign bit.
 491  * On some machines, a shift and add will be faster than a table lookup.
 492  */
 493
 494 #define AVOID_TABLES
 495 #ifdef AVOID_TABLES
 496
 497 #define NEG_1  ((unsigned int)-1)
 498 #define HUFF_EXTEND(x, s) \
 499   ((x) + ((((x) - (1 << ((s) - 1))) >> 31) & (((NEG_1) << (s)) + 1)))
 500
 501 #else
 502
 503 #define HUFF_EXTEND(x, s) \
 504   ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
 505
 506 static const int extend_test[16] = {   /* entry n is 2**(n-1) */
 507   0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
 508   0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000
 509 };
 510
 511 static const int extend_offset[16] = { /* entry n is (-1 << n) + 1 */
 512   0, ((-1) << 1) + 1, ((-1) << 2) + 1, ((-1) << 3) + 1, ((-1) << 4) + 1,
 513   ((-1) << 5) + 1, ((-1) << 6) + 1, ((-1) << 7) + 1, ((-1) << 8) + 1,
 514   ((-1) << 9) + 1, ((-1) << 10) + 1, ((-1) << 11) + 1, ((-1) << 12) + 1,
 515   ((-1) << 13) + 1, ((-1) << 14) + 1, ((-1) << 15) + 1
 516 };
 517
 518 #endif /* AVOID_TABLES */
 519
 520
 521 /*
 522  * Check for a restart marker & resynchronize decoder.
 523  * Returns FALSE if must suspend.
 524  */
 525
 526 LOCAL(boolean)
 527 process_restart(j_decompress_ptr cinfo)
 528 {
 529   huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy;
 530   int ci;
 531
 532   /* Throw away any unused bits remaining in bit buffer; */
 533   /* include any full bytes in next_marker's count of discarded bytes */
 534   cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
 535   entropy->bitstate.bits_left = 0;
 536
 537   /* Advance past the RSTn marker */
 538   if (!(*cinfo->marker->read_restart_marker) (cinfo))
 539     return FALSE;
 540
 541   /* Re-initialize DC predictions to 0 */
 542   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
 543     entropy->saved.last_dc_val[ci] = 0;
 544
 545   /* Reset restart counter */
 546   entropy->restarts_to_go = cinfo->restart_interval;
 547
 548   /* Reset out-of-data flag, unless read_restart_marker left us smack up
 549    * against a marker.  In that case we will end up treating the next data
 550    * segment as empty, and we can avoid producing bogus output pixels by
 551    * leaving the flag set.
 552    */
 553   if (cinfo->unread_marker == 0)
 554     entropy->pub.insufficient_data = FALSE;
 555
 556   return TRUE;
 557 }
 558
 559
 560 LOCAL(boolean)
 561 decode_mcu_slow(j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 562 {
 563   huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy;
 564   BITREAD_STATE_VARS;
 565   int blkn;
 566   savable_state state;
 567   /* Outer loop handles each block in the MCU */
 568
 569   /* Load up working state */
 570   BITREAD_LOAD_STATE(cinfo, entropy->bitstate);
 571   ASSIGN_STATE(state, entropy->saved);
 572
 573   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 574     JBLOCKROW block = MCU_data ? MCU_data[blkn] : NULL;
 575     d_derived_tbl *dctbl = entropy->dc_cur_tbls[blkn];
 576     d_derived_tbl *actbl = entropy->ac_cur_tbls[blkn];
 577     register int s, k, r;
 578
 579     /* Decode a single block's worth of coefficients */
 580
 581     /* Section F.2.2.1: decode the DC coefficient difference */
 582     HUFF_DECODE(s, br_state, dctbl, return FALSE, label1);
 583     if (s) {
 584       CHECK_BIT_BUFFER(br_state, s, return FALSE);
 585       r = GET_BITS(s);
 586       s = HUFF_EXTEND(r, s);
 587     }
 588
 589     if (entropy->dc_needed[blkn]) {
 590       /* Convert DC difference to actual value, update last_dc_val */
 591       int ci = cinfo->MCU_membership[blkn];
 592       s += state.last_dc_val[ci];
 593       state.last_dc_val[ci] = s;
 594       if (block) {
 595         /* Output the DC coefficient (assumes jpeg_natural_order[0] = 0) */
 596         (*block)[0] = (JCOEF)s;
 597       }
 598     }
 599
 600     if (entropy->ac_needed[blkn] && block) {
 601
 602       /* Section F.2.2.2: decode the AC coefficients */
 603       /* Since zeroes are skipped, output area must be cleared beforehand */
 604       for (k = 1; k < DCTSIZE2; k++) {
 605         HUFF_DECODE(s, br_state, actbl, return FALSE, label2);
 606
 607         r = s >> 4;
 608         s &= 15;
 609
 610         if (s) {
 611           k += r;
 612           CHECK_BIT_BUFFER(br_state, s, return FALSE);
 613           r = GET_BITS(s);
 614           s = HUFF_EXTEND(r, s);
 615           /* Output coefficient in natural (dezigzagged) order.
 616            * Note: the extra entries in jpeg_natural_order[] will save us
 617            * if k >= DCTSIZE2, which could happen if the data is corrupted.
 618            */
 619           (*block)[jpeg_natural_order[k]] = (JCOEF)s;
 620         } else {
 621           if (r != 15)
 622             break;
 623           k += 15;
 624         }
 625       }
 626
 627     } else {
 628
 629       /* Section F.2.2.2: decode the AC coefficients */
 630       /* In this path we just discard the values */
 631       for (k = 1; k < DCTSIZE2; k++) {
 632         HUFF_DECODE(s, br_state, actbl, return FALSE, label3);
 633
 634         r = s >> 4;
 635         s &= 15;
 636
 637         if (s) {
 638           k += r;
 639           CHECK_BIT_BUFFER(br_state, s, return FALSE);
 640           DROP_BITS(s);
 641         } else {
 642           if (r != 15)
 643             break;
 644           k += 15;
 645         }
 646       }
 647     }
 648   }
 649
 650   /* Completed MCU, so update state */
 651   BITREAD_SAVE_STATE(cinfo, entropy->bitstate);
 652   ASSIGN_STATE(entropy->saved, state);
 653   return TRUE;
 654 }
 655
 656
 657 LOCAL(boolean)
 658 decode_mcu_fast(j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 659 {
 660   huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy;
 661   BITREAD_STATE_VARS;
 662   JOCTET *buffer;
 663   int blkn;
 664   savable_state state;
 665   /* Outer loop handles each block in the MCU */
 666
 667   /* Load up working state */
 668   BITREAD_LOAD_STATE(cinfo, entropy->bitstate);
 669   buffer = (JOCTET *)br_state.next_input_byte;
 670   ASSIGN_STATE(state, entropy->saved);
 671
 672   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 673     JBLOCKROW block = MCU_data ? MCU_data[blkn] : NULL;
 674     d_derived_tbl *dctbl = entropy->dc_cur_tbls[blkn];
 675     d_derived_tbl *actbl = entropy->ac_cur_tbls[blkn];
 676     register int s, k, r, l;
 677
 678     HUFF_DECODE_FAST(s, l, dctbl);
 679     if (s) {
 680       FILL_BIT_BUFFER_FAST
 681       r = GET_BITS(s);
 682       s = HUFF_EXTEND(r, s);
 683     }
 684
 685     if (entropy->dc_needed[blkn]) {
 686       int ci = cinfo->MCU_membership[blkn];
 687       s += state.last_dc_val[ci];
 688       state.last_dc_val[ci] = s;
 689       if (block)
 690         (*block)[0] = (JCOEF)s;
 691     }
 692
 693     if (entropy->ac_needed[blkn] && block) {
 694
 695       for (k = 1; k < DCTSIZE2; k++) {
 696         HUFF_DECODE_FAST(s, l, actbl);
 697         r = s >> 4;
 698         s &= 15;
 699
 700         if (s) {
 701           k += r;
 702           FILL_BIT_BUFFER_FAST
 703           r = GET_BITS(s);
 704           s = HUFF_EXTEND(r, s);
 705           (*block)[jpeg_natural_order[k]] = (JCOEF)s;
 706         } else {
 707           if (r != 15) break;
 708           k += 15;
 709         }
 710       }
 711
 712     } else {
 713
 714       for (k = 1; k < DCTSIZE2; k++) {
 715         HUFF_DECODE_FAST(s, l, actbl);
 716         r = s >> 4;
 717         s &= 15;
 718
 719         if (s) {
 720           k += r;
 721           FILL_BIT_BUFFER_FAST
 722           DROP_BITS(s);
 723         } else {
 724           if (r != 15) break;
 725           k += 15;
 726         }
 727       }
 728     }
 729   }
 730
 731   if (cinfo->unread_marker != 0) {
 732     cinfo->unread_marker = 0;
 733     return FALSE;
 734   }
 735
 736   br_state.bytes_in_buffer -= (buffer - br_state.next_input_byte);
 737   br_state.next_input_byte = buffer;
 738   BITREAD_SAVE_STATE(cinfo, entropy->bitstate);
 739   ASSIGN_STATE(entropy->saved, state);
 740   return TRUE;
 741 }
 742
 743
 744 /*
 745  * Decode and return one MCU's worth of Huffman-compressed coefficients.
 746  * The coefficients are reordered from zigzag order into natural array order,
 747  * but are not dequantized.
 748  *
 749  * The i'th block of the MCU is stored into the block pointed to by
 750  * MCU_data[i].  WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
 751  * (Wholesale zeroing is usually a little faster than retail...)
 752  *
 753  * Returns FALSE if data source requested suspension.  In that case no
 754  * changes have been made to permanent state.  (Exception: some output
 755  * coefficients may already have been assigned.  This is harmless for
 756  * this module, since we'll just re-assign them on the next call.)
 757  */
 758
 759 #define BUFSIZE  (DCTSIZE2 * 8)
 760
 761 METHODDEF(boolean)
 762 decode_mcu(j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 763 {
 764   huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy;
 765   int usefast = 1;
 766
 767   /* Process restart marker if needed; may have to suspend */
 768   if (cinfo->restart_interval) {
 769     if (entropy->restarts_to_go == 0)
 770       if (!process_restart(cinfo))
 771         return FALSE;
 772     usefast = 0;
 773   }
 774
 775   if (cinfo->src->bytes_in_buffer < BUFSIZE * (size_t)cinfo->blocks_in_MCU ||
 776       cinfo->unread_marker != 0)
 777     usefast = 0;
 778
 779   /* If we've run out of data, just leave the MCU set to zeroes.
 780    * This way, we return uniform gray for the remainder of the segment.
 781    */
 782   if (!entropy->pub.insufficient_data) {
 783
 784     if (usefast) {
 785       if (!decode_mcu_fast(cinfo, MCU_data)) goto use_slow;
 786     } else {
 787 use_slow:
 788       if (!decode_mcu_slow(cinfo, MCU_data)) return FALSE;
 789     }
 790
 791   }
 792
 793   /* Account for restart interval (no-op if not using restarts) */
 794   entropy->restarts_to_go--;
 795
 796   return TRUE;
 797 }
 798
 799
 800 /*
 801  * Module initialization routine for Huffman entropy decoding.
 802  */
 803
 804 GLOBAL(void)
 805 jinit_huff_decoder(j_decompress_ptr cinfo)
 806 {
 807   huff_entropy_ptr entropy;
 808   int i;
 809
 810   /* Motion JPEG frames typically do not include the Huffman tables if they
 811      are the default tables.  Thus, if the tables are not set by the time
 812      the Huffman decoder is initialized (usually within the body of
 813      jpeg_start_decompress()), we set them to default values. */
 814   std_huff_tables((j_common_ptr)cinfo);
 815
 816   entropy = (huff_entropy_ptr)
 817     (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
 818                                 sizeof(huff_entropy_decoder));
 819   cinfo->entropy = (struct jpeg_entropy_decoder *)entropy;
 820   entropy->pub.start_pass = start_pass_huff_decoder;
 821   entropy->pub.decode_mcu = decode_mcu;
 822
 823   /* Mark tables unallocated */
 824   for (i = 0; i < NUM_HUFF_TBLS; i++) {
 825     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
 826   }
 827 }