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