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