jdhuff.c

00001 /*
00002  * jdhuff.c
00003  *
00004  * Copyright (C) 1991-1997, Thomas G. Lane.
00005  * Modified 2006-2013 by Guido Vollbeding.
00006  * This file is part of the Independent JPEG Group's software.
00007  * For conditions of distribution and use, see the accompanying README file.
00008  *
00009  * This file contains Huffman entropy decoding routines.
00010  * Both sequential and progressive modes are supported in this single module.
00011  *
00012  * Much of the complexity here has to do with supporting input suspension.
00013  * If the data source module demands suspension, we want to be able to back
00014  * up to the start of the current MCU.  To do this, we copy state variables
00015  * into local working storage, and update them back to the permanent
00016  * storage only upon successful completion of an MCU.
00017  */
00018 
00019 #define JPEG_INTERNALS
00020 #include "jinclude.h"
00021 #include "jpeglib.h"
00022 
00023 
00024 /* Derived data constructed for each Huffman table */
00025 
00026 #define HUFF_LOOKAHEAD  8   /* # of bits of lookahead */
00027 
00028 typedef struct {
00029   /* Basic tables: (element [0] of each array is unused) */
00030   INT32 maxcode[18];        /* largest code of length k (-1 if none) */
00031   /* (maxcode[17] is a sentinel to ensure jpeg_huff_decode terminates) */
00032   INT32 valoffset[17];      /* huffval[] offset for codes of length k */
00033   /* valoffset[k] = huffval[] index of 1st symbol of code length k, less
00034    * the smallest code of length k; so given a code of length k, the
00035    * corresponding symbol is huffval[code + valoffset[k]]
00036    */
00037 
00038   /* Link to public Huffman table (needed only in jpeg_huff_decode) */
00039   JHUFF_TBL *pub;
00040 
00041   /* Lookahead tables: indexed by the next HUFF_LOOKAHEAD bits of
00042    * the input data stream.  If the next Huffman code is no more
00043    * than HUFF_LOOKAHEAD bits long, we can obtain its length and
00044    * the corresponding symbol directly from these tables.
00045    */
00046   int look_nbits[1<<HUFF_LOOKAHEAD]; /* # bits, or 0 if too long */
00047   UINT8 look_sym[1<<HUFF_LOOKAHEAD]; /* symbol, or unused */
00048 } d_derived_tbl;
00049 
00050 
00051 /*
00052  * Fetching the next N bits from the input stream is a time-critical operation
00053  * for the Huffman decoders.  We implement it with a combination of inline
00054  * macros and out-of-line subroutines.  Note that N (the number of bits
00055  * demanded at one time) never exceeds 15 for JPEG use.
00056  *
00057  * We read source bytes into get_buffer and dole out bits as needed.
00058  * If get_buffer already contains enough bits, they are fetched in-line
00059  * by the macros CHECK_BIT_BUFFER and GET_BITS.  When there aren't enough
00060  * bits, jpeg_fill_bit_buffer is called; it will attempt to fill get_buffer
00061  * as full as possible (not just to the number of bits needed; this
00062  * prefetching reduces the overhead cost of calling jpeg_fill_bit_buffer).
00063  * Note that jpeg_fill_bit_buffer may return FALSE to indicate suspension.
00064  * On TRUE return, jpeg_fill_bit_buffer guarantees that get_buffer contains
00065  * at least the requested number of bits --- dummy zeroes are inserted if
00066  * necessary.
00067  */
00068 
00069 typedef INT32 bit_buf_type; /* type of bit-extraction buffer */
00070 #define BIT_BUF_SIZE  32    /* size of buffer in bits */
00071 
00072 /* If long is > 32 bits on your machine, and shifting/masking longs is
00073  * reasonably fast, making bit_buf_type be long and setting BIT_BUF_SIZE
00074  * appropriately should be a win.  Unfortunately we can't define the size
00075  * with something like  #define BIT_BUF_SIZE (sizeof(bit_buf_type)*8)
00076  * because not all machines measure sizeof in 8-bit bytes.
00077  */
00078 
00079 typedef struct {        /* Bitreading state saved across MCUs */
00080   bit_buf_type get_buffer;  /* current bit-extraction buffer */
00081   int bits_left;        /* # of unused bits in it */
00082 } bitread_perm_state;
00083 
00084 typedef struct {        /* Bitreading working state within an MCU */
00085   /* Current data source location */
00086   /* We need a copy, rather than munging the original, in case of suspension */
00087   const JOCTET * next_input_byte; /* => next byte to read from source */
00088   size_t bytes_in_buffer;   /* # of bytes remaining in source buffer */
00089   /* Bit input buffer --- note these values are kept in register variables,
00090    * not in this struct, inside the inner loops.
00091    */
00092   bit_buf_type get_buffer;  /* current bit-extraction buffer */
00093   int bits_left;        /* # of unused bits in it */
00094   /* Pointer needed by jpeg_fill_bit_buffer. */
00095   j_decompress_ptr cinfo;   /* back link to decompress master record */
00096 } bitread_working_state;
00097 
00098 /* Macros to declare and load/save bitread local variables. */
00099 #define BITREAD_STATE_VARS  \
00100     register bit_buf_type get_buffer;  \
00101     register int bits_left;  \
00102     bitread_working_state br_state
00103 
00104 #define BITREAD_LOAD_STATE(cinfop,permstate)  \
00105     br_state.cinfo = cinfop; \
00106     br_state.next_input_byte = cinfop->src->next_input_byte; \
00107     br_state.bytes_in_buffer = cinfop->src->bytes_in_buffer; \
00108     get_buffer = permstate.get_buffer; \
00109     bits_left = permstate.bits_left;
00110 
00111 #define BITREAD_SAVE_STATE(cinfop,permstate)  \
00112     cinfop->src->next_input_byte = br_state.next_input_byte; \
00113     cinfop->src->bytes_in_buffer = br_state.bytes_in_buffer; \
00114     permstate.get_buffer = get_buffer; \
00115     permstate.bits_left = bits_left
00116 
00117 /*
00118  * These macros provide the in-line portion of bit fetching.
00119  * Use CHECK_BIT_BUFFER to ensure there are N bits in get_buffer
00120  * before using GET_BITS, PEEK_BITS, or DROP_BITS.
00121  * The variables get_buffer and bits_left are assumed to be locals,
00122  * but the state struct might not be (jpeg_huff_decode needs this).
00123  *  CHECK_BIT_BUFFER(state,n,action);
00124  *      Ensure there are N bits in get_buffer; if suspend, take action.
00125  *      val = GET_BITS(n);
00126  *      Fetch next N bits.
00127  *      val = PEEK_BITS(n);
00128  *      Fetch next N bits without removing them from the buffer.
00129  *  DROP_BITS(n);
00130  *      Discard next N bits.
00131  * The value N should be a simple variable, not an expression, because it
00132  * is evaluated multiple times.
00133  */
00134 
00135 #define CHECK_BIT_BUFFER(state,nbits,action) \
00136     { if (bits_left < (nbits)) {  \
00137         if (! jpeg_fill_bit_buffer(&(state),get_buffer,bits_left,nbits))  \
00138           { action; }  \
00139         get_buffer = (state).get_buffer; bits_left = (state).bits_left; } }
00140 
00141 #define GET_BITS(nbits) \
00142     (((int) (get_buffer >> (bits_left -= (nbits)))) & BIT_MASK(nbits))
00143 
00144 #define PEEK_BITS(nbits) \
00145     (((int) (get_buffer >> (bits_left -  (nbits)))) & BIT_MASK(nbits))
00146 
00147 #define DROP_BITS(nbits) \
00148     (bits_left -= (nbits))
00149 
00150 
00151 /*
00152  * Code for extracting next Huffman-coded symbol from input bit stream.
00153  * Again, this is time-critical and we make the main paths be macros.
00154  *
00155  * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
00156  * without looping.  Usually, more than 95% of the Huffman codes will be 8
00157  * or fewer bits long.  The few overlength codes are handled with a loop,
00158  * which need not be inline code.
00159  *
00160  * Notes about the HUFF_DECODE macro:
00161  * 1. Near the end of the data segment, we may fail to get enough bits
00162  *    for a lookahead.  In that case, we do it the hard way.
00163  * 2. If the lookahead table contains no entry, the next code must be
00164  *    more than HUFF_LOOKAHEAD bits long.
00165  * 3. jpeg_huff_decode returns -1 if forced to suspend.
00166  */
00167 
00168 #define HUFF_DECODE(result,state,htbl,failaction,slowlabel) \
00169 { register int nb, look; \
00170   if (bits_left < HUFF_LOOKAHEAD) { \
00171     if (! jpeg_fill_bit_buffer(&state,get_buffer,bits_left, 0)) {failaction;} \
00172     get_buffer = state.get_buffer; bits_left = state.bits_left; \
00173     if (bits_left < HUFF_LOOKAHEAD) { \
00174       nb = 1; goto slowlabel; \
00175     } \
00176   } \
00177   look = PEEK_BITS(HUFF_LOOKAHEAD); \
00178   if ((nb = htbl->look_nbits[look]) != 0) { \
00179     DROP_BITS(nb); \
00180     result = htbl->look_sym[look]; \
00181   } else { \
00182     nb = HUFF_LOOKAHEAD+1; \
00183 slowlabel: \
00184     if ((result=jpeg_huff_decode(&state,get_buffer,bits_left,htbl,nb)) < 0) \
00185     { failaction; } \
00186     get_buffer = state.get_buffer; bits_left = state.bits_left; \
00187   } \
00188 }
00189 
00190 
00191 /*
00192  * Expanded entropy decoder object for Huffman decoding.
00193  *
00194  * The savable_state subrecord contains fields that change within an MCU,
00195  * but must not be updated permanently until we complete the MCU.
00196  */
00197 
00198 typedef struct {
00199   unsigned int EOBRUN;          /* remaining EOBs in EOBRUN */
00200   int last_dc_val[MAX_COMPS_IN_SCAN];   /* last DC coef for each component */
00201 } savable_state;
00202 
00203 /* This macro is to work around compilers with missing or broken
00204  * structure assignment.  You'll need to fix this code if you have
00205  * such a compiler and you change MAX_COMPS_IN_SCAN.
00206  */
00207 
00208 #ifndef NO_STRUCT_ASSIGN
00209 #define ASSIGN_STATE(dest,src)  ((dest) = (src))
00210 #else
00211 #if MAX_COMPS_IN_SCAN == 4
00212 #define ASSIGN_STATE(dest,src)  \
00213     ((dest).EOBRUN = (src).EOBRUN, \
00214      (dest).last_dc_val[0] = (src).last_dc_val[0], \
00215      (dest).last_dc_val[1] = (src).last_dc_val[1], \
00216      (dest).last_dc_val[2] = (src).last_dc_val[2], \
00217      (dest).last_dc_val[3] = (src).last_dc_val[3])
00218 #endif
00219 #endif
00220 
00221 
00222 typedef struct {
00223   struct jpeg_entropy_decoder pub; /* public fields */
00224 
00225   /* These fields are loaded into local variables at start of each MCU.
00226    * In case of suspension, we exit WITHOUT updating them.
00227    */
00228   bitread_perm_state bitstate;  /* Bit buffer at start of MCU */
00229   savable_state saved;      /* Other state at start of MCU */
00230 
00231   /* These fields are NOT loaded into local working state. */
00232   boolean insufficient_data;    /* set TRUE after emitting warning */
00233   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
00234 
00235   /* Following two fields used only in progressive mode */
00236 
00237   /* Pointers to derived tables (these workspaces have image lifespan) */
00238   d_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
00239 
00240   d_derived_tbl * ac_derived_tbl; /* active table during an AC scan */
00241 
00242   /* Following fields used only in sequential mode */
00243 
00244   /* Pointers to derived tables (these workspaces have image lifespan) */
00245   d_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
00246   d_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
00247 
00248   /* Precalculated info set up by start_pass for use in decode_mcu: */
00249 
00250   /* Pointers to derived tables to be used for each block within an MCU */
00251   d_derived_tbl * dc_cur_tbls[D_MAX_BLOCKS_IN_MCU];
00252   d_derived_tbl * ac_cur_tbls[D_MAX_BLOCKS_IN_MCU];
00253   /* Whether we care about the DC and AC coefficient values for each block */
00254   int coef_limit[D_MAX_BLOCKS_IN_MCU];
00255 } huff_entropy_decoder;
00256 
00257 typedef huff_entropy_decoder * huff_entropy_ptr;
00258 
00259 
00260 static const int jpeg_zigzag_order[8][8] = {
00261   {  0,  1,  5,  6, 14, 15, 27, 28 },
00262   {  2,  4,  7, 13, 16, 26, 29, 42 },
00263   {  3,  8, 12, 17, 25, 30, 41, 43 },
00264   {  9, 11, 18, 24, 31, 40, 44, 53 },
00265   { 10, 19, 23, 32, 39, 45, 52, 54 },
00266   { 20, 22, 33, 38, 46, 51, 55, 60 },
00267   { 21, 34, 37, 47, 50, 56, 59, 61 },
00268   { 35, 36, 48, 49, 57, 58, 62, 63 }
00269 };
00270 
00271 static const int jpeg_zigzag_order7[7][7] = {
00272   {  0,  1,  5,  6, 14, 15, 27 },
00273   {  2,  4,  7, 13, 16, 26, 28 },
00274   {  3,  8, 12, 17, 25, 29, 38 },
00275   {  9, 11, 18, 24, 30, 37, 39 },
00276   { 10, 19, 23, 31, 36, 40, 45 },
00277   { 20, 22, 32, 35, 41, 44, 46 },
00278   { 21, 33, 34, 42, 43, 47, 48 }
00279 };
00280 
00281 static const int jpeg_zigzag_order6[6][6] = {
00282   {  0,  1,  5,  6, 14, 15 },
00283   {  2,  4,  7, 13, 16, 25 },
00284   {  3,  8, 12, 17, 24, 26 },
00285   {  9, 11, 18, 23, 27, 32 },
00286   { 10, 19, 22, 28, 31, 33 },
00287   { 20, 21, 29, 30, 34, 35 }
00288 };
00289 
00290 static const int jpeg_zigzag_order5[5][5] = {
00291   {  0,  1,  5,  6, 14 },
00292   {  2,  4,  7, 13, 15 },
00293   {  3,  8, 12, 16, 21 },
00294   {  9, 11, 17, 20, 22 },
00295   { 10, 18, 19, 23, 24 }
00296 };
00297 
00298 static const int jpeg_zigzag_order4[4][4] = {
00299   { 0,  1,  5,  6 },
00300   { 2,  4,  7, 12 },
00301   { 3,  8, 11, 13 },
00302   { 9, 10, 14, 15 }
00303 };
00304 
00305 static const int jpeg_zigzag_order3[3][3] = {
00306   { 0, 1, 5 },
00307   { 2, 4, 6 },
00308   { 3, 7, 8 }
00309 };
00310 
00311 static const int jpeg_zigzag_order2[2][2] = {
00312   { 0, 1 },
00313   { 2, 3 }
00314 };
00315 
00316 
00317 /*
00318  * Compute the derived values for a Huffman table.
00319  * This routine also performs some validation checks on the table.
00320  */
00321 
00322 LOCAL(void)
00323 jpeg_make_d_derived_tbl (j_decompress_ptr cinfo, boolean isDC, int tblno,
00324              d_derived_tbl ** pdtbl)
00325 {
00326   JHUFF_TBL *htbl;
00327   d_derived_tbl *dtbl;
00328   int p, i, l, si, numsymbols;
00329   int lookbits, ctr;
00330   char huffsize[257];
00331   unsigned int huffcode[257];
00332   unsigned int code;
00333 
00334   /* Note that huffsize[] and huffcode[] are filled in code-length order,
00335    * paralleling the order of the symbols themselves in htbl->huffval[].
00336    */
00337 
00338   /* Find the input Huffman table */
00339   if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
00340     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
00341   htbl =
00342     isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
00343   if (htbl == NULL)
00344     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
00345 
00346   /* Allocate a workspace if we haven't already done so. */
00347   if (*pdtbl == NULL)
00348     *pdtbl = (d_derived_tbl *)
00349       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
00350                   SIZEOF(d_derived_tbl));
00351   dtbl = *pdtbl;
00352   dtbl->pub = htbl;     /* fill in back link */
00353   
00354   /* Figure C.1: make table of Huffman code length for each symbol */
00355 
00356   p = 0;
00357   for (l = 1; l <= 16; l++) {
00358     i = (int) htbl->bits[l];
00359     if (i < 0 || p + i > 256)   /* protect against table overrun */
00360       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
00361     while (i--)
00362       huffsize[p++] = (char) l;
00363   }
00364   huffsize[p] = 0;
00365   numsymbols = p;
00366   
00367   /* Figure C.2: generate the codes themselves */
00368   /* We also validate that the counts represent a legal Huffman code tree. */
00369   
00370   code = 0;
00371   si = huffsize[0];
00372   p = 0;
00373   while (huffsize[p]) {
00374     while (((int) huffsize[p]) == si) {
00375       huffcode[p++] = code;
00376       code++;
00377     }
00378     /* code is now 1 more than the last code used for codelength si; but
00379      * it must still fit in si bits, since no code is allowed to be all ones.
00380      */
00381     if (((INT32) code) >= (((INT32) 1) << si))
00382       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
00383     code <<= 1;
00384     si++;
00385   }
00386 
00387   /* Figure F.15: generate decoding tables for bit-sequential decoding */
00388 
00389   p = 0;
00390   for (l = 1; l <= 16; l++) {
00391     if (htbl->bits[l]) {
00392       /* valoffset[l] = huffval[] index of 1st symbol of code length l,
00393        * minus the minimum code of length l
00394        */
00395       dtbl->valoffset[l] = (INT32) p - (INT32) huffcode[p];
00396       p += htbl->bits[l];
00397       dtbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
00398     } else {
00399       dtbl->maxcode[l] = -1;    /* -1 if no codes of this length */
00400     }
00401   }
00402   dtbl->maxcode[17] = 0xFFFFFL; /* ensures jpeg_huff_decode terminates */
00403 
00404   /* Compute lookahead tables to speed up decoding.
00405    * First we set all the table entries to 0, indicating "too long";
00406    * then we iterate through the Huffman codes that are short enough and
00407    * fill in all the entries that correspond to bit sequences starting
00408    * with that code.
00409    */
00410 
00411   MEMZERO(dtbl->look_nbits, SIZEOF(dtbl->look_nbits));
00412 
00413   p = 0;
00414   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
00415     for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
00416       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
00417       /* Generate left-justified code followed by all possible bit sequences */
00418       lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
00419       for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
00420     dtbl->look_nbits[lookbits] = l;
00421     dtbl->look_sym[lookbits] = htbl->huffval[p];
00422     lookbits++;
00423       }
00424     }
00425   }
00426 
00427   /* Validate symbols as being reasonable.
00428    * For AC tables, we make no check, but accept all byte values 0..255.
00429    * For DC tables, we require the symbols to be in range 0..15.
00430    * (Tighter bounds could be applied depending on the data depth and mode,
00431    * but this is sufficient to ensure safe decoding.)
00432    */
00433   if (isDC) {
00434     for (i = 0; i < numsymbols; i++) {
00435       int sym = htbl->huffval[i];
00436       if (sym < 0 || sym > 15)
00437     ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
00438     }
00439   }
00440 }
00441 
00442 
00443 /*
00444  * Out-of-line code for bit fetching.
00445  * Note: current values of get_buffer and bits_left are passed as parameters,
00446  * but are returned in the corresponding fields of the state struct.
00447  *
00448  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
00449  * of get_buffer to be used.  (On machines with wider words, an even larger
00450  * buffer could be used.)  However, on some machines 32-bit shifts are
00451  * quite slow and take time proportional to the number of places shifted.
00452  * (This is true with most PC compilers, for instance.)  In this case it may
00453  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
00454  * average shift distance at the cost of more calls to jpeg_fill_bit_buffer.
00455  */
00456 
00457 #ifdef SLOW_SHIFT_32
00458 #define MIN_GET_BITS  15    /* minimum allowable value */
00459 #else
00460 #define MIN_GET_BITS  (BIT_BUF_SIZE-7)
00461 #endif
00462 
00463 
00464 LOCAL(boolean)
00465 jpeg_fill_bit_buffer (bitread_working_state * state,
00466               register bit_buf_type get_buffer, register int bits_left,
00467               int nbits)
00468 /* Load up the bit buffer to a depth of at least nbits */
00469 {
00470   /* Copy heavily used state fields into locals (hopefully registers) */
00471   register const JOCTET * next_input_byte = state->next_input_byte;
00472   register size_t bytes_in_buffer = state->bytes_in_buffer;
00473   j_decompress_ptr cinfo = state->cinfo;
00474 
00475   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
00476   /* (It is assumed that no request will be for more than that many bits.) */
00477   /* We fail to do so only if we hit a marker or are forced to suspend. */
00478 
00479   if (cinfo->unread_marker == 0) {  /* cannot advance past a marker */
00480     while (bits_left < MIN_GET_BITS) {
00481       register int c;
00482 
00483       /* Attempt to read a byte */
00484       if (bytes_in_buffer == 0) {
00485     if (! (*cinfo->src->fill_input_buffer) (cinfo))
00486       return FALSE;
00487     next_input_byte = cinfo->src->next_input_byte;
00488     bytes_in_buffer = cinfo->src->bytes_in_buffer;
00489       }
00490       bytes_in_buffer--;
00491       c = GETJOCTET(*next_input_byte++);
00492 
00493       /* If it's 0xFF, check and discard stuffed zero byte */
00494       if (c == 0xFF) {
00495     /* Loop here to discard any padding FF's on terminating marker,
00496      * so that we can save a valid unread_marker value.  NOTE: we will
00497      * accept multiple FF's followed by a 0 as meaning a single FF data
00498      * byte.  This data pattern is not valid according to the standard.
00499      */
00500     do {
00501       if (bytes_in_buffer == 0) {
00502         if (! (*cinfo->src->fill_input_buffer) (cinfo))
00503           return FALSE;
00504         next_input_byte = cinfo->src->next_input_byte;
00505         bytes_in_buffer = cinfo->src->bytes_in_buffer;
00506       }
00507       bytes_in_buffer--;
00508       c = GETJOCTET(*next_input_byte++);
00509     } while (c == 0xFF);
00510 
00511     if (c == 0) {
00512       /* Found FF/00, which represents an FF data byte */
00513       c = 0xFF;
00514     } else {
00515       /* Oops, it's actually a marker indicating end of compressed data.
00516        * Save the marker code for later use.
00517        * Fine point: it might appear that we should save the marker into
00518        * bitread working state, not straight into permanent state.  But
00519        * once we have hit a marker, we cannot need to suspend within the
00520        * current MCU, because we will read no more bytes from the data
00521        * source.  So it is OK to update permanent state right away.
00522        */
00523       cinfo->unread_marker = c;
00524       /* See if we need to insert some fake zero bits. */
00525       goto no_more_bytes;
00526     }
00527       }
00528 
00529       /* OK, load c into get_buffer */
00530       get_buffer = (get_buffer << 8) | c;
00531       bits_left += 8;
00532     } /* end while */
00533   } else {
00534   no_more_bytes:
00535     /* We get here if we've read the marker that terminates the compressed
00536      * data segment.  There should be enough bits in the buffer register
00537      * to satisfy the request; if so, no problem.
00538      */
00539     if (nbits > bits_left) {
00540       /* Uh-oh.  Report corrupted data to user and stuff zeroes into
00541        * the data stream, so that we can produce some kind of image.
00542        * We use a nonvolatile flag to ensure that only one warning message
00543        * appears per data segment.
00544        */
00545       if (! ((huff_entropy_ptr) cinfo->entropy)->insufficient_data) {
00546     WARNMS(cinfo, JWRN_HIT_MARKER);
00547     ((huff_entropy_ptr) cinfo->entropy)->insufficient_data = TRUE;
00548       }
00549       /* Fill the buffer with zero bits */
00550       get_buffer <<= MIN_GET_BITS - bits_left;
00551       bits_left = MIN_GET_BITS;
00552     }
00553   }
00554 
00555   /* Unload the local registers */
00556   state->next_input_byte = next_input_byte;
00557   state->bytes_in_buffer = bytes_in_buffer;
00558   state->get_buffer = get_buffer;
00559   state->bits_left = bits_left;
00560 
00561   return TRUE;
00562 }
00563 
00564 
00565 /*
00566  * Figure F.12: extend sign bit.
00567  * On some machines, a shift and sub will be faster than a table lookup.
00568  */
00569 
00570 #ifdef AVOID_TABLES
00571 
00572 #define BIT_MASK(nbits)   ((1<<(nbits))-1)
00573 #define HUFF_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) - ((1<<(s))-1) : (x))
00574 
00575 #else
00576 
00577 #define BIT_MASK(nbits)   bmask[nbits]
00578 #define HUFF_EXTEND(x,s)  ((x) <= bmask[(s) - 1] ? (x) - bmask[s] : (x))
00579 
00580 static const int bmask[16] =    /* bmask[n] is mask for n rightmost bits */
00581   { 0, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF,
00582     0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF };
00583 
00584 #endif /* AVOID_TABLES */
00585 
00586 
00587 /*
00588  * Out-of-line code for Huffman code decoding.
00589  */
00590 
00591 LOCAL(int)
00592 jpeg_huff_decode (bitread_working_state * state,
00593           register bit_buf_type get_buffer, register int bits_left,
00594           d_derived_tbl * htbl, int min_bits)
00595 {
00596   register int l = min_bits;
00597   register INT32 code;
00598 
00599   /* HUFF_DECODE has determined that the code is at least min_bits */
00600   /* bits long, so fetch that many bits in one swoop. */
00601 
00602   CHECK_BIT_BUFFER(*state, l, return -1);
00603   code = GET_BITS(l);
00604 
00605   /* Collect the rest of the Huffman code one bit at a time. */
00606   /* This is per Figure F.16 in the JPEG spec. */
00607 
00608   while (code > htbl->maxcode[l]) {
00609     code <<= 1;
00610     CHECK_BIT_BUFFER(*state, 1, return -1);
00611     code |= GET_BITS(1);
00612     l++;
00613   }
00614 
00615   /* Unload the local registers */
00616   state->get_buffer = get_buffer;
00617   state->bits_left = bits_left;
00618 
00619   /* With garbage input we may reach the sentinel value l = 17. */
00620 
00621   if (l > 16) {
00622     WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
00623     return 0;           /* fake a zero as the safest result */
00624   }
00625 
00626   return htbl->pub->huffval[ (int) (code + htbl->valoffset[l]) ];
00627 }
00628 
00629 
00630 /*
00631  * Finish up at the end of a Huffman-compressed scan.
00632  */
00633 
00634 METHODDEF(void)
00635 finish_pass_huff (j_decompress_ptr cinfo)
00636 {
00637   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00638 
00639   /* Throw away any unused bits remaining in bit buffer; */
00640   /* include any full bytes in next_marker's count of discarded bytes */
00641   cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
00642   entropy->bitstate.bits_left = 0;
00643 }
00644 
00645 
00646 /*
00647  * Check for a restart marker & resynchronize decoder.
00648  * Returns FALSE if must suspend.
00649  */
00650 
00651 LOCAL(boolean)
00652 process_restart (j_decompress_ptr cinfo)
00653 {
00654   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00655   int ci;
00656 
00657   finish_pass_huff(cinfo);
00658 
00659   /* Advance past the RSTn marker */
00660   if (! (*cinfo->marker->read_restart_marker) (cinfo))
00661     return FALSE;
00662 
00663   /* Re-initialize DC predictions to 0 */
00664   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
00665     entropy->saved.last_dc_val[ci] = 0;
00666   /* Re-init EOB run count, too */
00667   entropy->saved.EOBRUN = 0;
00668 
00669   /* Reset restart counter */
00670   entropy->restarts_to_go = cinfo->restart_interval;
00671 
00672   /* Reset out-of-data flag, unless read_restart_marker left us smack up
00673    * against a marker.  In that case we will end up treating the next data
00674    * segment as empty, and we can avoid producing bogus output pixels by
00675    * leaving the flag set.
00676    */
00677   if (cinfo->unread_marker == 0)
00678     entropy->insufficient_data = FALSE;
00679 
00680   return TRUE;
00681 }
00682 
00683 
00684 /*
00685  * Huffman MCU decoding.
00686  * Each of these routines decodes and returns one MCU's worth of
00687  * Huffman-compressed coefficients. 
00688  * The coefficients are reordered from zigzag order into natural array order,
00689  * but are not dequantized.
00690  *
00691  * The i'th block of the MCU is stored into the block pointed to by
00692  * MCU_data[i].  WE ASSUME THIS AREA IS INITIALLY ZEROED BY THE CALLER.
00693  * (Wholesale zeroing is usually a little faster than retail...)
00694  *
00695  * We return FALSE if data source requested suspension.  In that case no
00696  * changes have been made to permanent state.  (Exception: some output
00697  * coefficients may already have been assigned.  This is harmless for
00698  * spectral selection, since we'll just re-assign them on the next call.
00699  * Successive approximation AC refinement has to be more careful, however.)
00700  */
00701 
00702 /*
00703  * MCU decoding for DC initial scan (either spectral selection,
00704  * or first pass of successive approximation).
00705  */
00706 
00707 METHODDEF(boolean)
00708 decode_mcu_DC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
00709 {   
00710   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00711   int Al = cinfo->Al;
00712   register int s, r;
00713   int blkn, ci;
00714   JBLOCKROW block;
00715   BITREAD_STATE_VARS;
00716   savable_state state;
00717   d_derived_tbl * tbl;
00718   jpeg_component_info * compptr;
00719 
00720   /* Process restart marker if needed; may have to suspend */
00721   if (cinfo->restart_interval) {
00722     if (entropy->restarts_to_go == 0)
00723       if (! process_restart(cinfo))
00724     return FALSE;
00725   }
00726 
00727   /* If we've run out of data, just leave the MCU set to zeroes.
00728    * This way, we return uniform gray for the remainder of the segment.
00729    */
00730   if (! entropy->insufficient_data) {
00731 
00732     /* Load up working state */
00733     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
00734     ASSIGN_STATE(state, entropy->saved);
00735 
00736     /* Outer loop handles each block in the MCU */
00737 
00738     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
00739       block = MCU_data[blkn];
00740       ci = cinfo->MCU_membership[blkn];
00741       compptr = cinfo->cur_comp_info[ci];
00742       tbl = entropy->derived_tbls[compptr->dc_tbl_no];
00743 
00744       /* Decode a single block's worth of coefficients */
00745 
00746       /* Section F.2.2.1: decode the DC coefficient difference */
00747       HUFF_DECODE(s, br_state, tbl, return FALSE, label1);
00748       if (s) {
00749     CHECK_BIT_BUFFER(br_state, s, return FALSE);
00750     r = GET_BITS(s);
00751     s = HUFF_EXTEND(r, s);
00752       }
00753 
00754       /* Convert DC difference to actual value, update last_dc_val */
00755       s += state.last_dc_val[ci];
00756       state.last_dc_val[ci] = s;
00757       /* Scale and output the coefficient (assumes jpeg_natural_order[0]=0) */
00758       (*block)[0] = (JCOEF) (s << Al);
00759     }
00760 
00761     /* Completed MCU, so update state */
00762     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
00763     ASSIGN_STATE(entropy->saved, state);
00764   }
00765 
00766   /* Account for restart interval (no-op if not using restarts) */
00767   entropy->restarts_to_go--;
00768 
00769   return TRUE;
00770 }
00771 
00772 
00773 /*
00774  * MCU decoding for AC initial scan (either spectral selection,
00775  * or first pass of successive approximation).
00776  */
00777 
00778 METHODDEF(boolean)
00779 decode_mcu_AC_first (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
00780 {   
00781   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00782   register int s, k, r;
00783   unsigned int EOBRUN;
00784   int Se, Al;
00785   const int * natural_order;
00786   JBLOCKROW block;
00787   BITREAD_STATE_VARS;
00788   d_derived_tbl * tbl;
00789 
00790   /* Process restart marker if needed; may have to suspend */
00791   if (cinfo->restart_interval) {
00792     if (entropy->restarts_to_go == 0)
00793       if (! process_restart(cinfo))
00794     return FALSE;
00795   }
00796 
00797   /* If we've run out of data, just leave the MCU set to zeroes.
00798    * This way, we return uniform gray for the remainder of the segment.
00799    */
00800   if (! entropy->insufficient_data) {
00801 
00802     Se = cinfo->Se;
00803     Al = cinfo->Al;
00804     natural_order = cinfo->natural_order;
00805 
00806     /* Load up working state.
00807      * We can avoid loading/saving bitread state if in an EOB run.
00808      */
00809     EOBRUN = entropy->saved.EOBRUN; /* only part of saved state we need */
00810 
00811     /* There is always only one block per MCU */
00812 
00813     if (EOBRUN)         /* if it's a band of zeroes... */
00814       EOBRUN--;         /* ...process it now (we do nothing) */
00815     else {
00816       BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
00817       block = MCU_data[0];
00818       tbl = entropy->ac_derived_tbl;
00819 
00820       for (k = cinfo->Ss; k <= Se; k++) {
00821     HUFF_DECODE(s, br_state, tbl, return FALSE, label2);
00822     r = s >> 4;
00823     s &= 15;
00824     if (s) {
00825       k += r;
00826       CHECK_BIT_BUFFER(br_state, s, return FALSE);
00827       r = GET_BITS(s);
00828       s = HUFF_EXTEND(r, s);
00829       /* Scale and output coefficient in natural (dezigzagged) order */
00830       (*block)[natural_order[k]] = (JCOEF) (s << Al);
00831     } else {
00832       if (r != 15) {    /* EOBr, run length is 2^r + appended bits */
00833         if (r) {        /* EOBr, r > 0 */
00834           EOBRUN = 1 << r;
00835           CHECK_BIT_BUFFER(br_state, r, return FALSE);
00836           r = GET_BITS(r);
00837           EOBRUN += r;
00838           EOBRUN--;     /* this band is processed at this moment */
00839         }
00840         break;      /* force end-of-band */
00841       }
00842       k += 15;      /* ZRL: skip 15 zeroes in band */
00843     }
00844       }
00845 
00846       BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
00847     }
00848 
00849     /* Completed MCU, so update state */
00850     entropy->saved.EOBRUN = EOBRUN; /* only part of saved state we need */
00851   }
00852 
00853   /* Account for restart interval (no-op if not using restarts) */
00854   entropy->restarts_to_go--;
00855 
00856   return TRUE;
00857 }
00858 
00859 
00860 /*
00861  * MCU decoding for DC successive approximation refinement scan.
00862  * Note: we assume such scans can be multi-component,
00863  * although the spec is not very clear on the point.
00864  */
00865 
00866 METHODDEF(boolean)
00867 decode_mcu_DC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
00868 {   
00869   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00870   int p1, blkn;
00871   BITREAD_STATE_VARS;
00872 
00873   /* Process restart marker if needed; may have to suspend */
00874   if (cinfo->restart_interval) {
00875     if (entropy->restarts_to_go == 0)
00876       if (! process_restart(cinfo))
00877     return FALSE;
00878   }
00879 
00880   /* Not worth the cycles to check insufficient_data here,
00881    * since we will not change the data anyway if we read zeroes.
00882    */
00883 
00884   /* Load up working state */
00885   BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
00886 
00887   p1 = 1 << cinfo->Al;      /* 1 in the bit position being coded */
00888 
00889   /* Outer loop handles each block in the MCU */
00890 
00891   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
00892     /* Encoded data is simply the next bit of the two's-complement DC value */
00893     CHECK_BIT_BUFFER(br_state, 1, return FALSE);
00894     if (GET_BITS(1))
00895       MCU_data[blkn][0][0] |= p1;
00896     /* Note: since we use |=, repeating the assignment later is safe */
00897   }
00898 
00899   /* Completed MCU, so update state */
00900   BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
00901 
00902   /* Account for restart interval (no-op if not using restarts) */
00903   entropy->restarts_to_go--;
00904 
00905   return TRUE;
00906 }
00907 
00908 
00909 /*
00910  * MCU decoding for AC successive approximation refinement scan.
00911  */
00912 
00913 METHODDEF(boolean)
00914 decode_mcu_AC_refine (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
00915 {   
00916   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
00917   register int s, k, r;
00918   unsigned int EOBRUN;
00919   int Se, p1, m1;
00920   const int * natural_order;
00921   JBLOCKROW block;
00922   JCOEFPTR thiscoef;
00923   BITREAD_STATE_VARS;
00924   d_derived_tbl * tbl;
00925   int num_newnz;
00926   int newnz_pos[DCTSIZE2];
00927 
00928   /* Process restart marker if needed; may have to suspend */
00929   if (cinfo->restart_interval) {
00930     if (entropy->restarts_to_go == 0)
00931       if (! process_restart(cinfo))
00932     return FALSE;
00933   }
00934 
00935   /* If we've run out of data, don't modify the MCU.
00936    */
00937   if (! entropy->insufficient_data) {
00938 
00939     Se = cinfo->Se;
00940     p1 = 1 << cinfo->Al;    /* 1 in the bit position being coded */
00941     m1 = (-1) << cinfo->Al; /* -1 in the bit position being coded */
00942     natural_order = cinfo->natural_order;
00943 
00944     /* Load up working state */
00945     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
00946     EOBRUN = entropy->saved.EOBRUN; /* only part of saved state we need */
00947 
00948     /* There is always only one block per MCU */
00949     block = MCU_data[0];
00950     tbl = entropy->ac_derived_tbl;
00951 
00952     /* If we are forced to suspend, we must undo the assignments to any newly
00953      * nonzero coefficients in the block, because otherwise we'd get confused
00954      * next time about which coefficients were already nonzero.
00955      * But we need not undo addition of bits to already-nonzero coefficients;
00956      * instead, we can test the current bit to see if we already did it.
00957      */
00958     num_newnz = 0;
00959 
00960     /* initialize coefficient loop counter to start of band */
00961     k = cinfo->Ss;
00962 
00963     if (EOBRUN == 0) {
00964       do {
00965     HUFF_DECODE(s, br_state, tbl, goto undoit, label3);
00966     r = s >> 4;
00967     s &= 15;
00968     if (s) {
00969       if (s != 1)       /* size of new coef should always be 1 */
00970         WARNMS(cinfo, JWRN_HUFF_BAD_CODE);
00971       CHECK_BIT_BUFFER(br_state, 1, goto undoit);
00972       if (GET_BITS(1))
00973         s = p1;     /* newly nonzero coef is positive */
00974       else
00975         s = m1;     /* newly nonzero coef is negative */
00976     } else {
00977       if (r != 15) {
00978         EOBRUN = 1 << r;    /* EOBr, run length is 2^r + appended bits */
00979         if (r) {
00980           CHECK_BIT_BUFFER(br_state, r, goto undoit);
00981           r = GET_BITS(r);
00982           EOBRUN += r;
00983         }
00984         break;      /* rest of block is handled by EOB logic */
00985       }
00986       /* note s = 0 for processing ZRL */
00987     }
00988     /* Advance over already-nonzero coefs and r still-zero coefs,
00989      * appending correction bits to the nonzeroes.  A correction bit is 1
00990      * if the absolute value of the coefficient must be increased.
00991      */
00992     do {
00993       thiscoef = *block + natural_order[k];
00994       if (*thiscoef) {
00995         CHECK_BIT_BUFFER(br_state, 1, goto undoit);
00996         if (GET_BITS(1)) {
00997           if ((*thiscoef & p1) == 0) { /* do nothing if already set it */
00998         if (*thiscoef >= 0)
00999           *thiscoef += p1;
01000         else
01001           *thiscoef += m1;
01002           }
01003         }
01004       } else {
01005         if (--r < 0)
01006           break;        /* reached target zero coefficient */
01007       }
01008       k++;
01009     } while (k <= Se);
01010     if (s) {
01011       int pos = natural_order[k];
01012       /* Output newly nonzero coefficient */
01013       (*block)[pos] = (JCOEF) s;
01014       /* Remember its position in case we have to suspend */
01015       newnz_pos[num_newnz++] = pos;
01016     }
01017     k++;
01018       } while (k <= Se);
01019     }
01020 
01021     if (EOBRUN) {
01022       /* Scan any remaining coefficient positions after the end-of-band
01023        * (the last newly nonzero coefficient, if any).  Append a correction
01024        * bit to each already-nonzero coefficient.  A correction bit is 1
01025        * if the absolute value of the coefficient must be increased.
01026        */
01027       do {
01028     thiscoef = *block + natural_order[k];
01029     if (*thiscoef) {
01030       CHECK_BIT_BUFFER(br_state, 1, goto undoit);
01031       if (GET_BITS(1)) {
01032         if ((*thiscoef & p1) == 0) { /* do nothing if already changed it */
01033           if (*thiscoef >= 0)
01034         *thiscoef += p1;
01035           else
01036         *thiscoef += m1;
01037         }
01038       }
01039     }
01040     k++;
01041       } while (k <= Se);
01042       /* Count one block completed in EOB run */
01043       EOBRUN--;
01044     }
01045 
01046     /* Completed MCU, so update state */
01047     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
01048     entropy->saved.EOBRUN = EOBRUN; /* only part of saved state we need */
01049   }
01050 
01051   /* Account for restart interval (no-op if not using restarts) */
01052   entropy->restarts_to_go--;
01053 
01054   return TRUE;
01055 
01056 undoit:
01057   /* Re-zero any output coefficients that we made newly nonzero */
01058   while (num_newnz)
01059     (*block)[newnz_pos[--num_newnz]] = 0;
01060 
01061   return FALSE;
01062 }
01063 
01064 
01065 /*
01066  * Decode one MCU's worth of Huffman-compressed coefficients,
01067  * partial blocks.
01068  */
01069 
01070 METHODDEF(boolean)
01071 decode_mcu_sub (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
01072 {
01073   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
01074   const int * natural_order;
01075   int Se, blkn;
01076   BITREAD_STATE_VARS;
01077   savable_state state;
01078 
01079   /* Process restart marker if needed; may have to suspend */
01080   if (cinfo->restart_interval) {
01081     if (entropy->restarts_to_go == 0)
01082       if (! process_restart(cinfo))
01083     return FALSE;
01084   }
01085 
01086   /* If we've run out of data, just leave the MCU set to zeroes.
01087    * This way, we return uniform gray for the remainder of the segment.
01088    */
01089   if (! entropy->insufficient_data) {
01090 
01091     natural_order = cinfo->natural_order;
01092     Se = cinfo->lim_Se;
01093 
01094     /* Load up working state */
01095     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
01096     ASSIGN_STATE(state, entropy->saved);
01097 
01098     /* Outer loop handles each block in the MCU */
01099 
01100     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
01101       JBLOCKROW block = MCU_data[blkn];
01102       d_derived_tbl * htbl;
01103       register int s, k, r;
01104       int coef_limit, ci;
01105 
01106       /* Decode a single block's worth of coefficients */
01107 
01108       /* Section F.2.2.1: decode the DC coefficient difference */
01109       htbl = entropy->dc_cur_tbls[blkn];
01110       HUFF_DECODE(s, br_state, htbl, return FALSE, label1);
01111 
01112       htbl = entropy->ac_cur_tbls[blkn];
01113       k = 1;
01114       coef_limit = entropy->coef_limit[blkn];
01115       if (coef_limit) {
01116     /* Convert DC difference to actual value, update last_dc_val */
01117     if (s) {
01118       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01119       r = GET_BITS(s);
01120       s = HUFF_EXTEND(r, s);
01121     }
01122     ci = cinfo->MCU_membership[blkn];
01123     s += state.last_dc_val[ci];
01124     state.last_dc_val[ci] = s;
01125     /* Output the DC coefficient */
01126     (*block)[0] = (JCOEF) s;
01127 
01128     /* Section F.2.2.2: decode the AC coefficients */
01129     /* Since zeroes are skipped, output area must be cleared beforehand */
01130     for (; k < coef_limit; k++) {
01131       HUFF_DECODE(s, br_state, htbl, return FALSE, label2);
01132 
01133       r = s >> 4;
01134       s &= 15;
01135 
01136       if (s) {
01137         k += r;
01138         CHECK_BIT_BUFFER(br_state, s, return FALSE);
01139         r = GET_BITS(s);
01140         s = HUFF_EXTEND(r, s);
01141         /* Output coefficient in natural (dezigzagged) order.
01142          * Note: the extra entries in natural_order[] will save us
01143          * if k > Se, which could happen if the data is corrupted.
01144          */
01145         (*block)[natural_order[k]] = (JCOEF) s;
01146       } else {
01147         if (r != 15)
01148           goto EndOfBlock;
01149         k += 15;
01150       }
01151     }
01152       } else {
01153     if (s) {
01154       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01155       DROP_BITS(s);
01156     }
01157       }
01158 
01159       /* Section F.2.2.2: decode the AC coefficients */
01160       /* In this path we just discard the values */
01161       for (; k <= Se; k++) {
01162     HUFF_DECODE(s, br_state, htbl, return FALSE, label3);
01163 
01164     r = s >> 4;
01165     s &= 15;
01166 
01167     if (s) {
01168       k += r;
01169       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01170       DROP_BITS(s);
01171     } else {
01172       if (r != 15)
01173         break;
01174       k += 15;
01175     }
01176       }
01177 
01178       EndOfBlock: ;
01179     }
01180 
01181     /* Completed MCU, so update state */
01182     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
01183     ASSIGN_STATE(entropy->saved, state);
01184   }
01185 
01186   /* Account for restart interval (no-op if not using restarts) */
01187   entropy->restarts_to_go--;
01188 
01189   return TRUE;
01190 }
01191 
01192 
01193 /*
01194  * Decode one MCU's worth of Huffman-compressed coefficients,
01195  * full-size blocks.
01196  */
01197 
01198 METHODDEF(boolean)
01199 decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
01200 {
01201   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
01202   int blkn;
01203   BITREAD_STATE_VARS;
01204   savable_state state;
01205 
01206   /* Process restart marker if needed; may have to suspend */
01207   if (cinfo->restart_interval) {
01208     if (entropy->restarts_to_go == 0)
01209       if (! process_restart(cinfo))
01210     return FALSE;
01211   }
01212 
01213   /* If we've run out of data, just leave the MCU set to zeroes.
01214    * This way, we return uniform gray for the remainder of the segment.
01215    */
01216   if (! entropy->insufficient_data) {
01217 
01218     /* Load up working state */
01219     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
01220     ASSIGN_STATE(state, entropy->saved);
01221 
01222     /* Outer loop handles each block in the MCU */
01223 
01224     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
01225       JBLOCKROW block = MCU_data[blkn];
01226       d_derived_tbl * htbl;
01227       register int s, k, r;
01228       int coef_limit, ci;
01229 
01230       /* Decode a single block's worth of coefficients */
01231 
01232       /* Section F.2.2.1: decode the DC coefficient difference */
01233       htbl = entropy->dc_cur_tbls[blkn];
01234       HUFF_DECODE(s, br_state, htbl, return FALSE, label1);
01235 
01236       htbl = entropy->ac_cur_tbls[blkn];
01237       k = 1;
01238       coef_limit = entropy->coef_limit[blkn];
01239       if (coef_limit) {
01240     /* Convert DC difference to actual value, update last_dc_val */
01241     if (s) {
01242       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01243       r = GET_BITS(s);
01244       s = HUFF_EXTEND(r, s);
01245     }
01246     ci = cinfo->MCU_membership[blkn];
01247     s += state.last_dc_val[ci];
01248     state.last_dc_val[ci] = s;
01249     /* Output the DC coefficient */
01250     (*block)[0] = (JCOEF) s;
01251 
01252     /* Section F.2.2.2: decode the AC coefficients */
01253     /* Since zeroes are skipped, output area must be cleared beforehand */
01254     for (; k < coef_limit; k++) {
01255       HUFF_DECODE(s, br_state, htbl, return FALSE, label2);
01256 
01257       r = s >> 4;
01258       s &= 15;
01259 
01260       if (s) {
01261         k += r;
01262         CHECK_BIT_BUFFER(br_state, s, return FALSE);
01263         r = GET_BITS(s);
01264         s = HUFF_EXTEND(r, s);
01265         /* Output coefficient in natural (dezigzagged) order.
01266          * Note: the extra entries in jpeg_natural_order[] will save us
01267          * if k >= DCTSIZE2, which could happen if the data is corrupted.
01268          */
01269         (*block)[jpeg_natural_order[k]] = (JCOEF) s;
01270       } else {
01271         if (r != 15)
01272           goto EndOfBlock;
01273         k += 15;
01274       }
01275     }
01276       } else {
01277     if (s) {
01278       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01279       DROP_BITS(s);
01280     }
01281       }
01282 
01283       /* Section F.2.2.2: decode the AC coefficients */
01284       /* In this path we just discard the values */
01285       for (; k < DCTSIZE2; k++) {
01286     HUFF_DECODE(s, br_state, htbl, return FALSE, label3);
01287 
01288     r = s >> 4;
01289     s &= 15;
01290 
01291     if (s) {
01292       k += r;
01293       CHECK_BIT_BUFFER(br_state, s, return FALSE);
01294       DROP_BITS(s);
01295     } else {
01296       if (r != 15)
01297         break;
01298       k += 15;
01299     }
01300       }
01301 
01302       EndOfBlock: ;
01303     }
01304 
01305     /* Completed MCU, so update state */
01306     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
01307     ASSIGN_STATE(entropy->saved, state);
01308   }
01309 
01310   /* Account for restart interval (no-op if not using restarts) */
01311   entropy->restarts_to_go--;
01312 
01313   return TRUE;
01314 }
01315 
01316 
01317 /*
01318  * Initialize for a Huffman-compressed scan.
01319  */
01320 
01321 METHODDEF(void)
01322 start_pass_huff_decoder (j_decompress_ptr cinfo)
01323 {
01324   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
01325   int ci, blkn, tbl, i;
01326   jpeg_component_info * compptr;
01327 
01328   if (cinfo->progressive_mode) {
01329     /* Validate progressive scan parameters */
01330     if (cinfo->Ss == 0) {
01331       if (cinfo->Se != 0)
01332     goto bad;
01333     } else {
01334       /* need not check Ss/Se < 0 since they came from unsigned bytes */
01335       if (cinfo->Se < cinfo->Ss || cinfo->Se > cinfo->lim_Se)
01336     goto bad;
01337       /* AC scans may have only one component */
01338       if (cinfo->comps_in_scan != 1)
01339     goto bad;
01340     }
01341     if (cinfo->Ah != 0) {
01342       /* Successive approximation refinement scan: must have Al = Ah-1. */
01343       if (cinfo->Ah-1 != cinfo->Al)
01344     goto bad;
01345     }
01346     if (cinfo->Al > 13) {   /* need not check for < 0 */
01347       /* Arguably the maximum Al value should be less than 13 for 8-bit precision,
01348        * but the spec doesn't say so, and we try to be liberal about what we
01349        * accept.  Note: large Al values could result in out-of-range DC
01350        * coefficients during early scans, leading to bizarre displays due to
01351        * overflows in the IDCT math.  But we won't crash.
01352        */
01353       bad:
01354       ERREXIT4(cinfo, JERR_BAD_PROGRESSION,
01355            cinfo->Ss, cinfo->Se, cinfo->Ah, cinfo->Al);
01356     }
01357     /* Update progression status, and verify that scan order is legal.
01358      * Note that inter-scan inconsistencies are treated as warnings
01359      * not fatal errors ... not clear if this is right way to behave.
01360      */
01361     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
01362       int coefi, cindex = cinfo->cur_comp_info[ci]->component_index;
01363       int *coef_bit_ptr = & cinfo->coef_bits[cindex][0];
01364       if (cinfo->Ss && coef_bit_ptr[0] < 0) /* AC without prior DC scan */
01365     WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, 0);
01366       for (coefi = cinfo->Ss; coefi <= cinfo->Se; coefi++) {
01367     int expected = (coef_bit_ptr[coefi] < 0) ? 0 : coef_bit_ptr[coefi];
01368     if (cinfo->Ah != expected)
01369       WARNMS2(cinfo, JWRN_BOGUS_PROGRESSION, cindex, coefi);
01370     coef_bit_ptr[coefi] = cinfo->Al;
01371       }
01372     }
01373 
01374     /* Select MCU decoding routine */
01375     if (cinfo->Ah == 0) {
01376       if (cinfo->Ss == 0)
01377     entropy->pub.decode_mcu = decode_mcu_DC_first;
01378       else
01379     entropy->pub.decode_mcu = decode_mcu_AC_first;
01380     } else {
01381       if (cinfo->Ss == 0)
01382     entropy->pub.decode_mcu = decode_mcu_DC_refine;
01383       else
01384     entropy->pub.decode_mcu = decode_mcu_AC_refine;
01385     }
01386 
01387     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
01388       compptr = cinfo->cur_comp_info[ci];
01389       /* Make sure requested tables are present, and compute derived tables.
01390        * We may build same derived table more than once, but it's not expensive.
01391        */
01392       if (cinfo->Ss == 0) {
01393     if (cinfo->Ah == 0) {   /* DC refinement needs no table */
01394       tbl = compptr->dc_tbl_no;
01395       jpeg_make_d_derived_tbl(cinfo, TRUE, tbl,
01396                   & entropy->derived_tbls[tbl]);
01397     }
01398       } else {
01399     tbl = compptr->ac_tbl_no;
01400     jpeg_make_d_derived_tbl(cinfo, FALSE, tbl,
01401                 & entropy->derived_tbls[tbl]);
01402     /* remember the single active table */
01403     entropy->ac_derived_tbl = entropy->derived_tbls[tbl];
01404       }
01405       /* Initialize DC predictions to 0 */
01406       entropy->saved.last_dc_val[ci] = 0;
01407     }
01408 
01409     /* Initialize private state variables */
01410     entropy->saved.EOBRUN = 0;
01411   } else {
01412     /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
01413      * This ought to be an error condition, but we make it a warning because
01414      * there are some baseline files out there with all zeroes in these bytes.
01415      */
01416     if (cinfo->Ss != 0 || cinfo->Ah != 0 || cinfo->Al != 0 ||
01417     ((cinfo->is_baseline || cinfo->Se < DCTSIZE2) &&
01418     cinfo->Se != cinfo->lim_Se))
01419       WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
01420 
01421     /* Select MCU decoding routine */
01422     /* We retain the hard-coded case for full-size blocks.
01423      * This is not necessary, but it appears that this version is slightly
01424      * more performant in the given implementation.
01425      * With an improved implementation we would prefer a single optimized
01426      * function.
01427      */
01428     if (cinfo->lim_Se != DCTSIZE2-1)
01429       entropy->pub.decode_mcu = decode_mcu_sub;
01430     else
01431       entropy->pub.decode_mcu = decode_mcu;
01432 
01433     for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
01434       compptr = cinfo->cur_comp_info[ci];
01435       /* Compute derived values for Huffman tables */
01436       /* We may do this more than once for a table, but it's not expensive */
01437       tbl = compptr->dc_tbl_no;
01438       jpeg_make_d_derived_tbl(cinfo, TRUE, tbl,
01439                   & entropy->dc_derived_tbls[tbl]);
01440       if (cinfo->lim_Se) {  /* AC needs no table when not present */
01441     tbl = compptr->ac_tbl_no;
01442     jpeg_make_d_derived_tbl(cinfo, FALSE, tbl,
01443                 & entropy->ac_derived_tbls[tbl]);
01444       }
01445       /* Initialize DC predictions to 0 */
01446       entropy->saved.last_dc_val[ci] = 0;
01447     }
01448 
01449     /* Precalculate decoding info for each block in an MCU of this scan */
01450     for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
01451       ci = cinfo->MCU_membership[blkn];
01452       compptr = cinfo->cur_comp_info[ci];
01453       /* Precalculate which table to use for each block */
01454       entropy->dc_cur_tbls[blkn] = entropy->dc_derived_tbls[compptr->dc_tbl_no];
01455       entropy->ac_cur_tbls[blkn] = entropy->ac_derived_tbls[compptr->ac_tbl_no];
01456       /* Decide whether we really care about the coefficient values */
01457       if (compptr->component_needed) {
01458     ci = compptr->DCT_v_scaled_size;
01459     i = compptr->DCT_h_scaled_size;
01460     switch (cinfo->lim_Se) {
01461     case (1*1-1):
01462       entropy->coef_limit[blkn] = 1;
01463       break;
01464     case (2*2-1):
01465       if (ci <= 0 || ci > 2) ci = 2;
01466       if (i <= 0 || i > 2) i = 2;
01467       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order2[ci - 1][i - 1];
01468       break;
01469     case (3*3-1):
01470       if (ci <= 0 || ci > 3) ci = 3;
01471       if (i <= 0 || i > 3) i = 3;
01472       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order3[ci - 1][i - 1];
01473       break;
01474     case (4*4-1):
01475       if (ci <= 0 || ci > 4) ci = 4;
01476       if (i <= 0 || i > 4) i = 4;
01477       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order4[ci - 1][i - 1];
01478       break;
01479     case (5*5-1):
01480       if (ci <= 0 || ci > 5) ci = 5;
01481       if (i <= 0 || i > 5) i = 5;
01482       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order5[ci - 1][i - 1];
01483       break;
01484     case (6*6-1):
01485       if (ci <= 0 || ci > 6) ci = 6;
01486       if (i <= 0 || i > 6) i = 6;
01487       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order6[ci - 1][i - 1];
01488       break;
01489     case (7*7-1):
01490       if (ci <= 0 || ci > 7) ci = 7;
01491       if (i <= 0 || i > 7) i = 7;
01492       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order7[ci - 1][i - 1];
01493       break;
01494     default:
01495       if (ci <= 0 || ci > 8) ci = 8;
01496       if (i <= 0 || i > 8) i = 8;
01497       entropy->coef_limit[blkn] = 1 + jpeg_zigzag_order[ci - 1][i - 1];
01498       break;
01499     }
01500       } else {
01501     entropy->coef_limit[blkn] = 0;
01502       }
01503     }
01504   }
01505 
01506   /* Initialize bitread state variables */
01507   entropy->bitstate.bits_left = 0;
01508   entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
01509   entropy->insufficient_data = FALSE;
01510 
01511   /* Initialize restart counter */
01512   entropy->restarts_to_go = cinfo->restart_interval;
01513 }
01514 
01515 
01516 /*
01517  * Module initialization routine for Huffman entropy decoding.
01518  */
01519 
01520 GLOBAL(void)
01521 jinit_huff_decoder (j_decompress_ptr cinfo)
01522 {
01523   huff_entropy_ptr entropy;
01524   int i;
01525 
01526   entropy = (huff_entropy_ptr)
01527     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
01528                 SIZEOF(huff_entropy_decoder));
01529   cinfo->entropy = &entropy->pub;
01530   entropy->pub.start_pass = start_pass_huff_decoder;
01531   entropy->pub.finish_pass = finish_pass_huff;
01532 
01533   if (cinfo->progressive_mode) {
01534     /* Create progression status table */
01535     int *coef_bit_ptr, ci;
01536     cinfo->coef_bits = (int (*)[DCTSIZE2])
01537       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
01538                   cinfo->num_components*DCTSIZE2*SIZEOF(int));
01539     coef_bit_ptr = & cinfo->coef_bits[0][0];
01540     for (ci = 0; ci < cinfo->num_components; ci++)
01541       for (i = 0; i < DCTSIZE2; i++)
01542     *coef_bit_ptr++ = -1;
01543 
01544     /* Mark derived tables unallocated */
01545     for (i = 0; i < NUM_HUFF_TBLS; i++) {
01546       entropy->derived_tbls[i] = NULL;
01547     }
01548   } else {
01549     /* Mark tables unallocated */
01550     for (i = 0; i < NUM_HUFF_TBLS; i++) {
01551       entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
01552     }
01553   }
01554 }