home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / DOS / GRAFISCH / JPGSRC5A / JDHUFF.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  23KB  |  688 lines
  1. /*
  2.  * jdhuff.c
  3.  *
  4.  * Copyright (C) 1991-1994, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy decoding routines.
  9.  *
  10.  * Much of the complexity here has to do with supporting input suspension.
  11.  * If the data source module demands suspension, we want to be able to back
  12.  * up to the start of the current MCU.  To do this, we copy state variables
  13.  * into local working storage, and update them back to the permanent JPEG
  14.  * objects only upon successful completion of an MCU.
  15.  */
  16.  
  17. #define JPEG_INTERNALS
  18. #include "jinclude.h"
  19. #include "jpeglib.h"
  20.  
  21.  
  22. /* Derived data constructed for each Huffman table */
  23.  
  24. #define HUFF_LOOKAHEAD    8    /* # of bits of lookahead */
  25.  
  26. typedef struct {
  27.   /* Basic tables: (element [0] of each array is unused) */
  28.   INT32 mincode[17];        /* smallest code of length k */
  29.   INT32 maxcode[18];        /* largest code of length k (-1 if none) */
  30.   /* (maxcode[17] is a sentinel to ensure huff_DECODE terminates) */
  31.   int valptr[17];        /* huffval[] index of 1st symbol of length k */
  32.  
  33.   /* Back link to public Huffman table (needed only in slow_DECODE) */
  34.   JHUFF_TBL *pub;
  35.  
  36.   /* Lookahead tables: indexed by the next HUFF_LOOKAHEAD bits of
  37.    * the input data stream.  If the next Huffman code is no more
  38.    * than HUFF_LOOKAHEAD bits long, we can obtain its length and
  39.    * the corresponding symbol directly from these tables.
  40.    */
  41.   int look_nbits[1<<HUFF_LOOKAHEAD]; /* # bits, or 0 if too long */
  42.   UINT8 look_sym[1<<HUFF_LOOKAHEAD]; /* symbol, or unused */
  43. } D_DERIVED_TBL;
  44.  
  45. /* Expanded entropy decoder object for Huffman decoding.
  46.  *
  47.  * The savable_state subrecord contains fields that change within an MCU,
  48.  * but must not be updated permanently until we complete the MCU.
  49.  */
  50.  
  51. typedef struct {
  52.   INT32 get_buffer;        /* current bit-extraction buffer */
  53.   int bits_left;        /* # of unused bits in it */
  54.   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  55. } savable_state;
  56.  
  57. /* This macro is to work around compilers with missing or broken
  58.  * structure assignment.  You'll need to fix this code if you have
  59.  * such a compiler and you change MAX_COMPS_IN_SCAN.
  60.  */
  61.  
  62. #ifndef NO_STRUCT_ASSIGN
  63. #define ASSIGN_STATE(dest,src)  ((dest) = (src))
  64. #else
  65. #if MAX_COMPS_IN_SCAN == 4
  66. #define ASSIGN_STATE(dest,src)  \
  67.     ((dest).get_buffer = (src).get_buffer, \
  68.      (dest).bits_left = (src).bits_left, \
  69.      (dest).last_dc_val[0] = (src).last_dc_val[0], \
  70.      (dest).last_dc_val[1] = (src).last_dc_val[1], \
  71.      (dest).last_dc_val[2] = (src).last_dc_val[2], \
  72.      (dest).last_dc_val[3] = (src).last_dc_val[3])
  73. #endif
  74. #endif
  75.  
  76.  
  77. typedef struct {
  78.   struct jpeg_entropy_decoder pub; /* public fields */
  79.  
  80.   savable_state saved;        /* Bit buffer & DC state at start of MCU */
  81.  
  82.   /* These fields are NOT loaded into local working state. */
  83.   unsigned int restarts_to_go;    /* MCUs left in this restart interval */
  84.   boolean printed_eod;        /* flag to suppress extra end-of-data msgs */
  85.  
  86.   /* Pointers to derived tables (these workspaces have image lifespan) */
  87.   D_DERIVED_TBL * dc_derived_tbls[NUM_HUFF_TBLS];
  88.   D_DERIVED_TBL * ac_derived_tbls[NUM_HUFF_TBLS];
  89. } huff_entropy_decoder;
  90.  
  91. typedef huff_entropy_decoder * huff_entropy_ptr;
  92.  
  93. /* Working state while scanning an MCU.
  94.  * This struct contains all the fields that are needed by subroutines.
  95.  */
  96.  
  97. typedef struct {
  98.   int unread_marker;        /* nonzero if we have hit a marker */
  99.   const JOCTET * next_input_byte; /* => next byte to read from source */
  100.   size_t bytes_in_buffer;    /* # of bytes remaining in source buffer */
  101.   savable_state cur;        /* Current bit buffer & DC state */
  102.   j_decompress_ptr cinfo;    /* fill_bit_buffer needs access to this */
  103. } working_state;
  104.  
  105.  
  106. /* Forward declarations */
  107. LOCAL void fix_huff_tbl JPP((j_decompress_ptr cinfo, JHUFF_TBL * htbl,
  108.                  D_DERIVED_TBL ** pdtbl));
  109.  
  110.  
  111. /*
  112.  * Initialize for a Huffman-compressed scan.
  113.  */
  114.  
  115. METHODDEF void
  116. start_pass_huff_decoder (j_decompress_ptr cinfo)
  117. {
  118.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  119.   int ci, dctbl, actbl;
  120.   jpeg_component_info * compptr;
  121.  
  122.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  123.     compptr = cinfo->cur_comp_info[ci];
  124.     dctbl = compptr->dc_tbl_no;
  125.     actbl = compptr->ac_tbl_no;
  126.     /* Make sure requested tables are present */
  127.     if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
  128.     cinfo->dc_huff_tbl_ptrs[dctbl] == NULL)
  129.       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
  130.     if (actbl < 0 || actbl >= NUM_HUFF_TBLS ||
  131.     cinfo->ac_huff_tbl_ptrs[actbl] == NULL)
  132.       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
  133.     /* Compute derived values for Huffman tables */
  134.     /* We may do this more than once for a table, but it's not expensive */
  135.     fix_huff_tbl(cinfo, cinfo->dc_huff_tbl_ptrs[dctbl],
  136.          & entropy->dc_derived_tbls[dctbl]);
  137.     fix_huff_tbl(cinfo, cinfo->ac_huff_tbl_ptrs[actbl],
  138.          & entropy->ac_derived_tbls[actbl]);
  139.     /* Initialize DC predictions to 0 */
  140.     entropy->saved.last_dc_val[ci] = 0;
  141.   }
  142.  
  143.   /* Initialize private state variables */
  144.   entropy->saved.bits_left = 0;
  145.   entropy->printed_eod = FALSE;
  146.  
  147.   /* Initialize restart counter */
  148.   entropy->restarts_to_go = cinfo->restart_interval;
  149. }
  150.  
  151.  
  152. LOCAL void
  153. fix_huff_tbl (j_decompress_ptr cinfo, JHUFF_TBL * htbl, D_DERIVED_TBL ** pdtbl)
  154. /* Compute the derived values for a Huffman table */
  155. {
  156.   D_DERIVED_TBL *dtbl;
  157.   int p, i, l, si;
  158.   int lookbits, ctr;
  159.   char huffsize[257];
  160.   unsigned int huffcode[257];
  161.   unsigned int code;
  162.  
  163.   /* Allocate a workspace if we haven't already done so. */
  164.   if (*pdtbl == NULL)
  165.     *pdtbl = (D_DERIVED_TBL *)
  166.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  167.                   SIZEOF(D_DERIVED_TBL));
  168.   dtbl = *pdtbl;
  169.   dtbl->pub = htbl;        /* fill in back link */
  170.   
  171.   /* Figure C.1: make table of Huffman code length for each symbol */
  172.   /* Note that this is in code-length order. */
  173.  
  174.   p = 0;
  175.   for (l = 1; l <= 16; l++) {
  176.     for (i = 1; i <= (int) htbl->bits[l]; i++)
  177.       huffsize[p++] = (char) l;
  178.   }
  179.   huffsize[p] = 0;
  180.   
  181.   /* Figure C.2: generate the codes themselves */
  182.   /* Note that this is in code-length order. */
  183.   
  184.   code = 0;
  185.   si = huffsize[0];
  186.   p = 0;
  187.   while (huffsize[p]) {
  188.     while (((int) huffsize[p]) == si) {
  189.       huffcode[p++] = code;
  190.       code++;
  191.     }
  192.     code <<= 1;
  193.     si++;
  194.   }
  195.  
  196.   /* Figure F.15: generate decoding tables for bit-sequential decoding */
  197.  
  198.   p = 0;
  199.   for (l = 1; l <= 16; l++) {
  200.     if (htbl->bits[l]) {
  201.       dtbl->valptr[l] = p; /* huffval[] index of 1st symbol of code length l */
  202.       dtbl->mincode[l] = huffcode[p]; /* minimum code of length l */
  203.       p += htbl->bits[l];
  204.       dtbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
  205.     } else {
  206.       dtbl->maxcode[l] = -1;    /* -1 if no codes of this length */
  207.     }
  208.   }
  209.   dtbl->maxcode[17] = 0xFFFFFL; /* ensures huff_DECODE terminates */
  210.  
  211.   /* Compute lookahead tables to speed up decoding.
  212.    * First we set all the table entries to 0, indicating "too long";
  213.    * then we iterate through the Huffman codes that are short enough and
  214.    * fill in all the entries that correspond to bit sequences starting
  215.    * with that code.
  216.    */
  217.  
  218.   MEMZERO(dtbl->look_nbits, SIZEOF(dtbl->look_nbits));
  219.  
  220.   p = 0;
  221.   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
  222.     for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
  223.       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
  224.       /* Generate left-justified code followed by all possible bit sequences */
  225.       lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
  226.       for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
  227.     dtbl->look_nbits[lookbits] = l;
  228.     dtbl->look_sym[lookbits] = htbl->huffval[p];
  229.     lookbits++;
  230.       }
  231.     }
  232.   }
  233. }
  234.  
  235.  
  236. /*
  237.  * Code for extracting the next N bits from the input stream.
  238.  * (N never exceeds 15 for JPEG data.)
  239.  * This needs to go as fast as possible!
  240.  *
  241.  * We read source bytes into get_buffer and dole out bits as needed.
  242.  * If get_buffer already contains enough bits, they are fetched in-line
  243.  * by the macros check_bit_buffer and get_bits.  When there aren't enough
  244.  * bits, fill_bit_buffer is called; it will attempt to fill get_buffer to
  245.  * the "high water mark" (not just to the number of bits needed; this reduces
  246.  * the function-call overhead cost of entering fill_bit_buffer).
  247.  * Note that fill_bit_buffer may return FALSE to indicate suspension.
  248.  * On TRUE return, fill_bit_buffer guarantees that get_buffer contains
  249.  * at least the requested number of bits --- dummy zeroes are inserted if
  250.  * necessary.
  251.  *
  252.  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
  253.  * of get_buffer to be used.  (On machines with wider words, an even larger
  254.  * buffer could be used.)  However, on some machines 32-bit shifts are
  255.  * quite slow and take time proportional to the number of places shifted.
  256.  * (This is true with most PC compilers, for instance.)  In this case it may
  257.  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
  258.  * average shift distance at the cost of more calls to fill_bit_buffer.
  259.  */
  260.  
  261. #ifdef SLOW_SHIFT_32
  262. #define MIN_GET_BITS  15    /* minimum allowable value */
  263. #else
  264. #define MIN_GET_BITS  25    /* max value for 32-bit get_buffer */
  265. #endif
  266.  
  267.  
  268. LOCAL boolean
  269. fill_bit_buffer (working_state * state, int nbits)
  270. /* Load up the bit buffer to a depth of at least nbits */
  271. {
  272.   /* Copy heavily used state fields into locals (hopefully registers) */
  273.   register const JOCTET * next_input_byte = state->next_input_byte;
  274.   register size_t bytes_in_buffer = state->bytes_in_buffer;
  275.   register INT32 get_buffer = state->cur.get_buffer;
  276.   register int bits_left = state->cur.bits_left;
  277.   register int c;
  278.  
  279.   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
  280.   /* (It is assumed that no request will be for more than that many bits.) */
  281.  
  282.   while (bits_left < MIN_GET_BITS) {
  283.     /* Attempt to read a byte */
  284.     if (state->unread_marker != 0)
  285.       goto no_more_data;    /* can't advance past a marker */
  286.  
  287.     if (bytes_in_buffer == 0) {
  288.       if (! (*state->cinfo->src->fill_input_buffer) (state->cinfo))
  289.     return FALSE;
  290.       next_input_byte = state->cinfo->src->next_input_byte;
  291.       bytes_in_buffer = state->cinfo->src->bytes_in_buffer;
  292.     }
  293.     bytes_in_buffer--;
  294.     c = GETJOCTET(*next_input_byte++);
  295.  
  296.     /* If it's 0xFF, check and discard stuffed zero byte */
  297.     if (c == 0xFF) {
  298.       do {
  299.     if (bytes_in_buffer == 0) {
  300.       if (! (*state->cinfo->src->fill_input_buffer) (state->cinfo))
  301.         return FALSE;
  302.       next_input_byte = state->cinfo->src->next_input_byte;
  303.       bytes_in_buffer = state->cinfo->src->bytes_in_buffer;
  304.     }
  305.     bytes_in_buffer--;
  306.     c = GETJOCTET(*next_input_byte++);
  307.       } while (c == 0xFF);
  308.  
  309.       if (c == 0) {
  310.     /* Found FF/00, which represents an FF data byte */
  311.     c = 0xFF;
  312.       } else {
  313.     /* Oops, it's actually a marker indicating end of compressed data. */
  314.     /* Better put it back for use later */
  315.     state->unread_marker = c;
  316.  
  317.       no_more_data:
  318.     /* There should be enough bits still left in the data segment; */
  319.     /* if so, just break out of the outer while loop. */
  320.     if (bits_left >= nbits)
  321.       break;
  322.     /* Uh-oh.  Report corrupted data to user and stuff zeroes into
  323.      * the data stream, so that we can produce some kind of image.
  324.      * Note that this will be repeated for each byte demanded for the
  325.      * rest of the segment; this is slow but not unreasonably so.
  326.      * The main thing is to avoid getting a zillion warnings, hence
  327.      * we use a flag to ensure that only one warning appears.
  328.      */
  329.     if (! ((huff_entropy_ptr) state->cinfo->entropy)->printed_eod) {
  330.       WARNMS(state->cinfo, JWRN_HIT_MARKER);
  331.       ((huff_entropy_ptr) state->cinfo->entropy)->printed_eod = TRUE;
  332.     }
  333.     c = 0;            /* insert a zero byte into bit buffer */
  334.       }
  335.     }
  336.  
  337.     /* OK, load c into get_buffer */
  338.     get_buffer = (get_buffer << 8) | c;
  339.     bits_left += 8;
  340.   }
  341.  
  342.   /* Unload the local registers */
  343.   state->next_input_byte = next_input_byte;
  344.   state->bytes_in_buffer = bytes_in_buffer;
  345.   state->cur.get_buffer = get_buffer;
  346.   state->cur.bits_left = bits_left;
  347.  
  348.   return TRUE;
  349. }
  350.  
  351.  
  352. /*
  353.  * These macros provide the in-line portion of bit fetching.
  354.  * Use check_bit_buffer to ensure there are N bits in get_buffer
  355.  * before using get_bits, peek_bits, or drop_bits.
  356.  *    check_bit_buffer(state,n,action);
  357.  *        Ensure there are N bits in get_buffer; if suspend, take action.
  358.  *      val = get_bits(state,n);
  359.  *        Fetch next N bits.
  360.  *      val = peek_bits(state,n);
  361.  *        Fetch next N bits without removing them from the buffer.
  362.  *    drop_bits(state,n);
  363.  *        Discard next N bits.
  364.  * The value N should be a simple variable, not an expression, because it
  365.  * is evaluated multiple times.
  366.  */
  367.  
  368. #define check_bit_buffer(state,nbits,action) \
  369.     { if ((state).cur.bits_left < (nbits))  \
  370.         if (! fill_bit_buffer(&(state), nbits))  \
  371.           { action; } }
  372.  
  373. #define get_bits(state,nbits) \
  374.     (((int) ((state).cur.get_buffer >> ((state).cur.bits_left -= (nbits)))) & ((1<<(nbits))-1))
  375.  
  376. #define peek_bits(state,nbits) \
  377.     (((int) ((state).cur.get_buffer >> ((state).cur.bits_left -  (nbits)))) & ((1<<(nbits))-1))
  378.  
  379. #define drop_bits(state,nbits) \
  380.     ((state).cur.bits_left -= (nbits))
  381.  
  382.  
  383. /*
  384.  * Code for extracting next Huffman-coded symbol from input bit stream.
  385.  * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
  386.  * without looping.  Usually, more than 95% of the Huffman codes will be 8
  387.  * or fewer bits long.  The few overlength codes are handled with a loop.
  388.  * The primary case is made a macro for speed reasons; the secondary
  389.  * routine slow_DECODE is rarely entered and need not be inline code.
  390.  *
  391.  * Notes about the huff_DECODE macro:
  392.  * 1. Near the end of the data segment, we may fail to get enough bits
  393.  *    for a lookahead.  In that case, we do it the hard way.
  394.  * 2. If the lookahead table contains no entry, the next code must be
  395.  *    more than HUFF_LOOKAHEAD bits long.
  396.  * 3. slow_DECODE returns -1 if forced to suspend.
  397.  */
  398.  
  399. #define huff_DECODE(result,state,htbl,donelabel) \
  400. { if (state.cur.bits_left < HUFF_LOOKAHEAD) {  \
  401.     if (! fill_bit_buffer(&state, 0)) return FALSE;  \
  402.     if (state.cur.bits_left < HUFF_LOOKAHEAD) {  \
  403.       if ((result = slow_DECODE(&state, htbl, 1)) < 0) return FALSE;  \
  404.       goto donelabel;  \
  405.     }  \
  406.   }  \
  407.   { register int nb, look;  \
  408.     look = peek_bits(state, HUFF_LOOKAHEAD);  \
  409.     if ((nb = htbl->look_nbits[look]) != 0) {  \
  410.       drop_bits(state, nb);  \
  411.       result = htbl->look_sym[look];  \
  412.     } else {  \
  413.       if ((result = slow_DECODE(&state, htbl, HUFF_LOOKAHEAD+1)) < 0)  \
  414.     return FALSE;  \
  415.     }  \
  416.   }  \
  417. donelabel:;  \
  418. }
  419.  
  420.   
  421. LOCAL int
  422. slow_DECODE (working_state * state, D_DERIVED_TBL * htbl, int min_bits)
  423. {
  424.   register int l = min_bits;
  425.   register INT32 code;
  426.  
  427.   /* huff_DECODE has determined that the code is at least min_bits */
  428.   /* bits long, so fetch that many bits in one swoop. */
  429.  
  430.   check_bit_buffer(*state, l, return -1);
  431.   code = get_bits(*state, l);
  432.  
  433.   /* Collect the rest of the Huffman code one bit at a time. */
  434.   /* This is per Figure F.16 in the JPEG spec. */
  435.  
  436.   while (code > htbl->maxcode[l]) {
  437.     code <<= 1;
  438.     check_bit_buffer(*state, 1, return -1);
  439.     code |= get_bits(*state, 1);
  440.     l++;
  441.   }
  442.  
  443.   /* With garbage input we may reach the sentinel value l = 17. */
  444.  
  445.   if (l > 16) {
  446.     WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
  447.     return 0;            /* fake a zero as the safest result */
  448.   }
  449.  
  450.   return htbl->pub->huffval[ htbl->valptr[l] +
  451.                 ((int) (code - htbl->mincode[l])) ];
  452. }
  453.  
  454.  
  455. /* Figure F.12: extend sign bit.
  456.  * On some machines, a shift and add will be faster than a table lookup.
  457.  */
  458.  
  459. #ifdef AVOID_TABLES
  460.  
  461. #define huff_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
  462.  
  463. #else
  464.  
  465. #define huff_EXTEND(x,s)  ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
  466.  
  467. static const int extend_test[16] =   /* entry n is 2**(n-1) */
  468.   { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
  469.     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
  470.  
  471. static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
  472.   { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
  473.     ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
  474.     ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
  475.     ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
  476.  
  477. #endif /* AVOID_TABLES */
  478.  
  479.  
  480. /*
  481.  * Check for a restart marker & resynchronize decoder.
  482.  * Returns FALSE if must suspend.
  483.  */
  484.  
  485. LOCAL boolean
  486. process_restart (j_decompress_ptr cinfo)
  487. {
  488.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  489.   int ci;
  490.  
  491.   /* Throw away any unused bits remaining in bit buffer; */
  492.   /* include any full bytes in next_marker's count of discarded bytes */
  493.   cinfo->marker->discarded_bytes += entropy->saved.bits_left / 8;
  494.   entropy->saved.bits_left = 0;
  495.  
  496.   /* Advance past the RSTn marker */
  497.   if (! (*cinfo->marker->read_restart_marker) (cinfo))
  498.     return FALSE;
  499.  
  500.   /* Re-initialize DC predictions to 0 */
  501.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  502.     entropy->saved.last_dc_val[ci] = 0;
  503.  
  504.   /* Reset restart counter */
  505.   entropy->restarts_to_go = cinfo->restart_interval;
  506.  
  507.   entropy->printed_eod = FALSE; /* next segment can get another warning */
  508.  
  509.   return TRUE;
  510. }
  511.  
  512.  
  513. /* ZAG[i] is the natural-order position of the i'th element of zigzag order.
  514.  * If the incoming data is corrupted, decode_mcu could attempt to
  515.  * reference values beyond the end of the array.  To avoid a wild store,
  516.  * we put some extra zeroes after the real entries.
  517.  */
  518.  
  519. static const int ZAG[DCTSIZE2+16] = {
  520.   0,  1,  8, 16,  9,  2,  3, 10,
  521.  17, 24, 32, 25, 18, 11,  4,  5,
  522.  12, 19, 26, 33, 40, 48, 41, 34,
  523.  27, 20, 13,  6,  7, 14, 21, 28,
  524.  35, 42, 49, 56, 57, 50, 43, 36,
  525.  29, 22, 15, 23, 30, 37, 44, 51,
  526.  58, 59, 52, 45, 38, 31, 39, 46,
  527.  53, 60, 61, 54, 47, 55, 62, 63,
  528.   0,  0,  0,  0,  0,  0,  0,  0, /* extra entries in case k>63 below */
  529.   0,  0,  0,  0,  0,  0,  0,  0
  530. };
  531.  
  532.  
  533. /*
  534.  * Decode and return one MCU's worth of Huffman-compressed coefficients.
  535.  * The coefficients are reordered from zigzag order into natural array order,
  536.  * but are not dequantized.
  537.  *
  538.  * The i'th block of the MCU is stored into the block pointed to by
  539.  * MCU_data[i].  WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
  540.  * (Wholesale zeroing is usually a little faster than retail...)
  541.  *
  542.  * Returns FALSE if data source requested suspension.  In that case no
  543.  * changes have been made to permanent state.  (Exception: some output
  544.  * coefficients may already have been assigned.  This is harmless for
  545.  * this module, but would not work for decoding progressive JPEG.)
  546.  */
  547.  
  548. METHODDEF boolean
  549. decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
  550. {
  551.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  552.   register int s, k, r;
  553.   int blkn, ci;
  554.   JBLOCKROW block;
  555.   working_state state;
  556.   D_DERIVED_TBL * dctbl;
  557.   D_DERIVED_TBL * actbl;
  558.   jpeg_component_info * compptr;
  559.  
  560.   /* Process restart marker if needed; may have to suspend */
  561.   if (cinfo->restart_interval) {
  562.     if (entropy->restarts_to_go == 0)
  563.       if (! process_restart(cinfo))
  564.     return FALSE;
  565.   }
  566.  
  567.   /* Load up working state */
  568.   state.unread_marker = cinfo->unread_marker;
  569.   state.next_input_byte = cinfo->src->next_input_byte;
  570.   state.bytes_in_buffer = cinfo->src->bytes_in_buffer;
  571.   ASSIGN_STATE(state.cur, entropy->saved);
  572.   state.cinfo = cinfo;
  573.  
  574.   /* Outer loop handles each block in the MCU */
  575.  
  576.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  577.     block = MCU_data[blkn];
  578.     ci = cinfo->MCU_membership[blkn];
  579.     compptr = cinfo->cur_comp_info[ci];
  580.     dctbl = entropy->dc_derived_tbls[compptr->dc_tbl_no];
  581.     actbl = entropy->ac_derived_tbls[compptr->ac_tbl_no];
  582.  
  583.     /* Decode a single block's worth of coefficients */
  584.  
  585.     /* Section F.2.2.1: decode the DC coefficient difference */
  586.     huff_DECODE(s, state, dctbl, label1);
  587.     if (s) {
  588.       check_bit_buffer(state, s, return FALSE);
  589.       r = get_bits(state, s);
  590.       s = huff_EXTEND(r, s);
  591.     }
  592.  
  593.     /* Shortcut if component's values are not interesting */
  594.     if (! compptr->component_needed)
  595.       goto skip_ACs;
  596.  
  597.     /* Convert DC difference to actual value, update last_dc_val */
  598.     s += state.cur.last_dc_val[ci];
  599.     state.cur.last_dc_val[ci] = s;
  600.     /* Output the DC coefficient (assumes ZAG[0] = 0) */
  601.     (*block)[0] = (JCOEF) s;
  602.  
  603.     /* Do we need to decode the AC coefficients for this component? */
  604.     if (compptr->DCT_scaled_size > 1) {
  605.  
  606.       /* Section F.2.2.2: decode the AC coefficients */
  607.       /* Since zeroes are skipped, output area must be cleared beforehand */
  608.       for (k = 1; k < DCTSIZE2; k++) {
  609.     huff_DECODE(s, state, actbl, label2);
  610.       
  611.     r = s >> 4;
  612.     s &= 15;
  613.       
  614.     if (s) {
  615.       k += r;
  616.       check_bit_buffer(state, s, return FALSE);
  617.       r = get_bits(state, s);
  618.       s = huff_EXTEND(r, s);
  619.       /* Output coefficient in natural (dezigzagged) order */
  620.       (*block)[ZAG[k]] = (JCOEF) s;
  621.     } else {
  622.       if (r != 15)
  623.         break;
  624.       k += 15;
  625.     }
  626.       }
  627.  
  628.     } else {
  629. skip_ACs:
  630.  
  631.       /* Section F.2.2.2: decode the AC coefficients */
  632.       /* In this path we just discard the values */
  633.       for (k = 1; k < DCTSIZE2; k++) {
  634.     huff_DECODE(s, state, actbl, label3);
  635.       
  636.     r = s >> 4;
  637.     s &= 15;
  638.       
  639.     if (s) {
  640.       k += r;
  641.       check_bit_buffer(state, s, return FALSE);
  642.       drop_bits(state, s);
  643.     } else {
  644.       if (r != 15)
  645.         break;
  646.       k += 15;
  647.     }
  648.       }
  649.  
  650.     }
  651.   }
  652.  
  653.   /* Completed MCU, so update state */
  654.   cinfo->unread_marker = state.unread_marker;
  655.   cinfo->src->next_input_byte = state.next_input_byte;
  656.   cinfo->src->bytes_in_buffer = state.bytes_in_buffer;
  657.   ASSIGN_STATE(entropy->saved, state.cur);
  658.  
  659.   /* Account for restart interval (no-op if not using restarts) */
  660.   entropy->restarts_to_go--;
  661.  
  662.   return TRUE;
  663. }
  664.  
  665.  
  666. /*
  667.  * Module initialization routine for Huffman entropy decoding.
  668.  */
  669.  
  670. GLOBAL void
  671. jinit_huff_decoder (j_decompress_ptr cinfo)
  672. {
  673.   huff_entropy_ptr entropy;
  674.   int i;
  675.  
  676.   entropy = (huff_entropy_ptr)
  677.     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  678.                 SIZEOF(huff_entropy_decoder));
  679.   cinfo->entropy = (struct jpeg_entropy_decoder *) entropy;
  680.   entropy->pub.start_pass = start_pass_huff_decoder;
  681.   entropy->pub.decode_mcu = decode_mcu;
  682.  
  683.   /* Mark tables unallocated */
  684.   for (i = 0; i < NUM_HUFF_TBLS; i++) {
  685.     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
  686.   }
  687. }
  688.