home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / jpeg / jpegv4a.tar / jdhuff.c < prev    next >
C/C++ Source or Header  |  1993-02-11  |  15KB  |  492 lines
  1. /*
  2.  * jdhuff.c
  3.  *
  4.  * Copyright (C) 1991, 1992, 1993, 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.  * These routines are invoked via the methods entropy_decode
  10.  * and entropy_decode_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15.  
  16. /* Static variables to avoid passing 'round extra parameters */
  17.  
  18. static decompress_info_ptr dcinfo;
  19.  
  20. static INT32 get_buffer;    /* current bit-extraction buffer */
  21. static int bits_left;        /* # of unused bits in it */
  22. static boolean printed_eod;    /* flag to suppress multiple end-of-data msgs */
  23.  
  24. LOCAL void
  25. fix_huff_tbl (HUFF_TBL * htbl)
  26. /* Compute derived values for a Huffman table */
  27. {
  28.   int p, i, l, si;
  29.   int lookbits, ctr;
  30.   char huffsize[257];
  31.   UINT16 huffcode[257];
  32.   UINT16 code;
  33.   
  34.   /* Figure C.1: make table of Huffman code length for each symbol */
  35.   /* Note that this is in code-length order. */
  36.  
  37.   p = 0;
  38.   for (l = 1; l <= 16; l++) {
  39.     for (i = 1; i <= (int) htbl->bits[l]; i++)
  40.       huffsize[p++] = (char) l;
  41.   }
  42.   huffsize[p] = 0;
  43.   
  44.   /* Figure C.2: generate the codes themselves */
  45.   /* Note that this is in code-length order. */
  46.   
  47.   code = 0;
  48.   si = huffsize[0];
  49.   p = 0;
  50.   while (huffsize[p]) {
  51.     while (((int) huffsize[p]) == si) {
  52.       huffcode[p++] = code;
  53.       code++;
  54.     }
  55.     code <<= 1;
  56.     si++;
  57.   }
  58.  
  59.   /* Figure F.15: generate decoding tables for bit-sequential decoding */
  60.  
  61.   p = 0;
  62.   for (l = 1; l <= 16; l++) {
  63.     if (htbl->bits[l]) {
  64.       htbl->priv.dec.valptr[l] = p; /* huffval[] index of 1st symbol of code length l */
  65.       htbl->priv.dec.mincode[l] = huffcode[p]; /* minimum code of length l */
  66.       p += htbl->bits[l];
  67.       htbl->priv.dec.maxcode[l] = huffcode[p-1]; /* maximum code of length l */
  68.     } else {
  69.       htbl->priv.dec.maxcode[l] = -1; /* -1 if no codes of this length */
  70.     }
  71.   }
  72.   htbl->priv.dec.maxcode[17] = 0xFFFFFL; /* ensures huff_DECODE terminates */
  73.  
  74.   /* Compute lookahead tables to speed up decoding.
  75.    * First we set all the table entries to 0, indicating "too long";
  76.    * then we iterate through the Huffman codes that are short enough and
  77.    * fill in all the entries that correspond to bit sequences starting
  78.    * with that code.
  79.    */
  80.  
  81.   MEMZERO(htbl->priv.dec.look_nbits, SIZEOF(htbl->priv.dec.look_nbits));
  82.  
  83.   p = 0;
  84.   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
  85.     for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
  86.       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
  87.       /* Generate left-justified code followed by all possible bit sequences */
  88.       lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
  89.       for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
  90.     htbl->priv.dec.look_nbits[lookbits] = l;
  91.     htbl->priv.dec.look_sym[lookbits] = htbl->huffval[p];
  92.     lookbits++;
  93.       }
  94.     }
  95.   }
  96. }
  97.  
  98.  
  99. /*
  100.  * Code for extracting the next N bits from the input stream.
  101.  * (N never exceeds 15 for JPEG data.)
  102.  * This needs to go as fast as possible!
  103.  *
  104.  * We read source bytes into get_buffer and dole out bits as needed.
  105.  * If get_buffer already contains enough bits, they are fetched in-line
  106.  * by the macros check_bit_buffer and get_bits.  When there aren't enough
  107.  * bits, fill_bit_buffer is called; it will attempt to fill get_buffer to
  108.  * the "high water mark" (not just to the number of bits needed; this reduces
  109.  * the function-call overhead cost of entering fill_bit_buffer).
  110.  * On return, fill_bit_buffer guarantees that get_buffer contains at least
  111.  * the requested number of bits --- dummy zeroes are inserted if necessary.
  112.  *
  113.  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
  114.  * of get_buffer to be used.  (On machines with wider words, an even larger
  115.  * buffer could be used.)  However, on some machines 32-bit shifts are
  116.  * relatively slow and take time proportional to the number of places shifted.
  117.  * (This is true with most PC compilers, for instance.)  In this case it may
  118.  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
  119.  * average shift distance at the cost of more calls to fill_bit_buffer.
  120.  */
  121.  
  122. #ifdef SLOW_SHIFT_32
  123. #define MIN_GET_BITS  15    /* minimum allowable value */
  124. #else
  125. #define MIN_GET_BITS  25    /* max value for 32-bit get_buffer */
  126. #endif
  127.  
  128.  
  129. LOCAL void
  130. fill_bit_buffer (int nbits)
  131. /* Load up the bit buffer to a depth of at least nbits */
  132. {
  133.   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
  134.   /* (It is assumed that no request will be for more than that many bits.) */
  135.   while (bits_left < MIN_GET_BITS) {
  136.     register int c = JGETC(dcinfo);
  137.     
  138.     /* If it's 0xFF, check and discard stuffed zero byte */
  139.     if (c == 0xFF) {
  140.       int c2 = JGETC(dcinfo);
  141.       if (c2 != 0) {
  142.     /* Oops, it's actually a marker indicating end of compressed data. */
  143.     /* Better put it back for use later */
  144.     JUNGETC(c2,dcinfo);
  145.     JUNGETC(c,dcinfo);
  146.     /* There should be enough bits still left in the data segment; */
  147.     /* if so, just break out of the while loop. */
  148.     if (bits_left >= nbits)
  149.       break;
  150.     /* Uh-oh.  Report corrupted data to user and stuff zeroes into
  151.      * the data stream, so that we can produce some kind of image.
  152.      * Note that this will be repeated for each byte demanded for the
  153.      * rest of the segment; this is a bit slow but not unreasonably so.
  154.      * The main thing is to avoid getting a zillion warnings, hence
  155.      * we use a flag to ensure that only one warning appears.
  156.      */
  157.     if (! printed_eod) {
  158.       WARNMS(dcinfo->emethods, "Corrupt JPEG data: premature end of data segment");
  159.       printed_eod = TRUE;
  160.     }
  161.     c = 0;            /* insert a zero byte into bit buffer */
  162.       }
  163.     }
  164.  
  165.     /* OK, load c into get_buffer */
  166.     get_buffer = (get_buffer << 8) | c;
  167.     bits_left += 8;
  168.   }
  169. }
  170.  
  171.  
  172. /*
  173.  * These macros provide the in-line portion of bit fetching.
  174.  * Correct usage is:
  175.  *    check_bit_buffer(n);        ensure there are N bits in get_buffer
  176.  *      val = get_bits(n);        fetch N bits
  177.  * The value n should be a simple variable, not an expression, because it
  178.  * is evaluated multiple times.
  179.  * peek_bits() fetches next N bits without removing them from the buffer.
  180.  */
  181.  
  182. #define check_bit_buffer(nbits) \
  183.     { if (bits_left < (nbits))  fill_bit_buffer(nbits); }
  184.  
  185. #define get_bits(nbits) \
  186.     (((int) (get_buffer >> (bits_left -= (nbits)))) & ((1<<(nbits))-1))
  187.  
  188. #define peek_bits(nbits) \
  189.     (((int) (get_buffer >> (bits_left -  (nbits)))) & ((1<<(nbits))-1))
  190.  
  191.  
  192. /*
  193.  * Routines to extract next Huffman-coded symbol from input bit stream.
  194.  * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
  195.  * without looping.  Usually, more than 95% of the Huffman codes will be 8
  196.  * or fewer bits long.  The few overlength codes are handled with a loop.
  197.  * The primary case is made a macro for speed reasons; the secondary
  198.  * routine slow_DECODE is rarely entered and need not be inline code.
  199.  *
  200.  * Notes about the huff_DECODE macro:
  201.  * 1. The first if-test is coded to call fill_bit_buffer only when necessary.
  202.  * 2. If the lookahead succeeds, we need only decrement bits_left to remove
  203.  *    the proper number of bits from get_buffer.
  204.  * 3. If the lookahead table contains no entry, the next code must be
  205.  *    more than HUFF_LOOKAHEAD bits long.
  206.  * 4. Near the end of the data segment, we may fail to get enough bits
  207.  *    for a lookahead.  In that case, we do it the hard way.
  208.  */
  209.  
  210. #define huff_DECODE(htbl,result) \
  211. { register int nb, look;                    \
  212.   if (bits_left >= HUFF_LOOKAHEAD ||                \
  213.       (fill_bit_buffer(0), bits_left >= HUFF_LOOKAHEAD)) {    \
  214.     look = peek_bits(HUFF_LOOKAHEAD);                \
  215.     if ((nb = htbl->priv.dec.look_nbits[look]) != 0) {        \
  216.       bits_left -= nb;                        \
  217.       result = htbl->priv.dec.look_sym[look];            \
  218.     } else                            \
  219.       result = slow_DECODE(htbl, HUFF_LOOKAHEAD+1);        \
  220.   } else                            \
  221.     result = slow_DECODE(htbl, 1);                \
  222. }
  223.  
  224.   
  225. LOCAL int
  226. slow_DECODE (HUFF_TBL * htbl, int min_bits)
  227. {
  228.   register int l = min_bits;
  229.   register INT32 code;
  230.  
  231.   /* huff_DECODE has determined that the code is at least min_bits */
  232.   /* bits long, so fetch that many bits in one swoop. */
  233.  
  234.   check_bit_buffer(l);
  235.   code = get_bits(l);
  236.  
  237.   /* Collect the rest of the Huffman code one bit at a time. */
  238.   /* This is per Figure F.16 in the JPEG spec. */
  239.  
  240.   while (code > htbl->priv.dec.maxcode[l]) {
  241.     code <<= 1;
  242.     check_bit_buffer(1);
  243.     code |= get_bits(1);
  244.     l++;
  245.   }
  246.  
  247.   /* With garbage input we may reach the sentinel value l = 17. */
  248.  
  249.   if (l > 16) {
  250.     WARNMS(dcinfo->emethods, "Corrupt JPEG data: bad Huffman code");
  251.     return 0;            /* fake a zero as the safest result */
  252.   }
  253.  
  254.   return htbl->huffval[ htbl->priv.dec.valptr[l] +
  255.                 ((int) (code - htbl->priv.dec.mincode[l])) ];
  256. }
  257.  
  258.  
  259. /* Figure F.12: extend sign bit.
  260.  * On some machines, a shift and add will be faster than a table lookup.
  261.  */
  262.  
  263. #ifdef AVOID_TABLES
  264.  
  265. #define huff_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
  266.  
  267. #else
  268.  
  269. #define huff_EXTEND(x,s)  ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
  270.  
  271. static const int extend_test[16] =   /* entry n is 2**(n-1) */
  272.   { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
  273.     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
  274.  
  275. static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
  276.   { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
  277.     ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
  278.     ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
  279.     ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
  280.  
  281. #endif /* AVOID_TABLES */
  282.  
  283.  
  284. /*
  285.  * Initialize for a Huffman-compressed scan.
  286.  * This is invoked after reading the SOS marker.
  287.  */
  288.  
  289. METHODDEF void
  290. decoder_init (decompress_info_ptr cinfo)
  291. {
  292.   short ci;
  293.   jpeg_component_info * compptr;
  294.  
  295.   /* Initialize static variables */
  296.   dcinfo = cinfo;
  297.   bits_left = 0;
  298.   printed_eod = FALSE;
  299.  
  300.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  301.     compptr = cinfo->cur_comp_info[ci];
  302.     /* Make sure requested tables are present */
  303.     if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
  304.     cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
  305.       ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
  306.     /* Compute derived values for Huffman tables */
  307.     /* We may do this more than once for same table, but it's not a big deal */
  308.     fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
  309.     fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  310.     /* Initialize DC predictions to 0 */
  311.     cinfo->last_dc_val[ci] = 0;
  312.   }
  313.  
  314.   /* Initialize restart stuff */
  315.   cinfo->restarts_to_go = cinfo->restart_interval;
  316.   cinfo->next_restart_num = 0;
  317. }
  318.  
  319.  
  320. /*
  321.  * Check for a restart marker & resynchronize decoder.
  322.  */
  323.  
  324. LOCAL void
  325. process_restart (decompress_info_ptr cinfo)
  326. {
  327.   int c, nbytes;
  328.   short ci;
  329.  
  330.   /* Throw away any unused bits remaining in bit buffer */
  331.   nbytes = bits_left / 8;    /* count any full bytes loaded into buffer */
  332.   bits_left = 0;
  333.   printed_eod = FALSE;        /* next segment can get another warning */
  334.  
  335.   /* Scan for next JPEG marker */
  336.   do {
  337.     do {            /* skip any non-FF bytes */
  338.       nbytes++;
  339.       c = JGETC(cinfo);
  340.     } while (c != 0xFF);
  341.     do {            /* skip any duplicate FFs */
  342.       /* we don't increment nbytes here since extra FFs are legal */
  343.       c = JGETC(cinfo);
  344.     } while (c == 0xFF);
  345.   } while (c == 0);        /* repeat if it was a stuffed FF/00 */
  346.  
  347.   if (nbytes != 1)
  348.     WARNMS2(cinfo->emethods,
  349.         "Corrupt JPEG data: %d extraneous bytes before marker 0x%02x",
  350.         nbytes-1, c);
  351.  
  352.   if (c != (RST0 + cinfo->next_restart_num)) {
  353.     /* Uh-oh, the restart markers have been messed up too. */
  354.     /* Let the file-format module try to figure out how to resync. */
  355.     (*cinfo->methods->resync_to_restart) (cinfo, c);
  356.   } else
  357.     TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num);
  358.  
  359.   /* Re-initialize DC predictions to 0 */
  360.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  361.     cinfo->last_dc_val[ci] = 0;
  362.  
  363.   /* Update restart state */
  364.   cinfo->restarts_to_go = cinfo->restart_interval;
  365.   cinfo->next_restart_num = (cinfo->next_restart_num + 1) & 7;
  366. }
  367.  
  368.  
  369. /* ZAG[i] is the natural-order position of the i'th element of zigzag order.
  370.  * If the incoming data is corrupted, decode_mcu could attempt to
  371.  * reference values beyond the end of the array.  To avoid a wild store,
  372.  * we put some extra zeroes after the real entries.
  373.  */
  374.  
  375. static const short ZAG[DCTSIZE2+16] = {
  376.   0,  1,  8, 16,  9,  2,  3, 10,
  377.  17, 24, 32, 25, 18, 11,  4,  5,
  378.  12, 19, 26, 33, 40, 48, 41, 34,
  379.  27, 20, 13,  6,  7, 14, 21, 28,
  380.  35, 42, 49, 56, 57, 50, 43, 36,
  381.  29, 22, 15, 23, 30, 37, 44, 51,
  382.  58, 59, 52, 45, 38, 31, 39, 46,
  383.  53, 60, 61, 54, 47, 55, 62, 63,
  384.   0,  0,  0,  0,  0,  0,  0,  0, /* extra entries in case k>63 below */
  385.   0,  0,  0,  0,  0,  0,  0,  0
  386. };
  387.  
  388.  
  389. /*
  390.  * Decode and return one MCU's worth of Huffman-compressed coefficients.
  391.  * This routine also handles quantization descaling and zigzag reordering
  392.  * of coefficient values.
  393.  *
  394.  * The i'th block of the MCU is stored into the block pointed to by
  395.  * MCU_data[i].  WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
  396.  * (Wholesale zeroing is usually a little faster than retail...)
  397.  */
  398.  
  399. METHODDEF void
  400. decode_mcu (decompress_info_ptr cinfo, JBLOCKROW *MCU_data)
  401. {
  402.   register int s, k, r;
  403.   short blkn, ci;
  404.   register JBLOCKROW block;
  405.   register QUANT_TBL_PTR quanttbl;
  406.   HUFF_TBL *dctbl;
  407.   HUFF_TBL *actbl;
  408.   jpeg_component_info * compptr;
  409.  
  410.   /* Account for restart interval, process restart marker if needed */
  411.   if (cinfo->restart_interval) {
  412.     if (cinfo->restarts_to_go == 0)
  413.       process_restart(cinfo);
  414.     cinfo->restarts_to_go--;
  415.   }
  416.  
  417.   /* Outer loop handles each block in the MCU */
  418.  
  419.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  420.     block = MCU_data[blkn];
  421.     ci = cinfo->MCU_membership[blkn];
  422.     compptr = cinfo->cur_comp_info[ci];
  423.     quanttbl = cinfo->quant_tbl_ptrs[compptr->quant_tbl_no];
  424.     actbl = cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no];
  425.     dctbl = cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no];
  426.  
  427.     /* Decode a single block's worth of coefficients */
  428.  
  429.     /* Section F.2.2.1: decode the DC coefficient difference */
  430.     huff_DECODE(dctbl, s);
  431.     if (s) {
  432.       check_bit_buffer(s);
  433.       r = get_bits(s);
  434.       s = huff_EXTEND(r, s);
  435.     }
  436.  
  437.     /* Convert DC difference to actual value, update last_dc_val */
  438.     s += cinfo->last_dc_val[ci];
  439.     cinfo->last_dc_val[ci] = (JCOEF) s;
  440.     /* Descale and output the DC coefficient (assumes ZAG[0] = 0) */
  441.     (*block)[0] = (JCOEF) (((JCOEF) s) * quanttbl[0]);
  442.     
  443.     /* Section F.2.2.2: decode the AC coefficients */
  444.     /* Since zero values are skipped, output area must be zeroed beforehand */
  445.     for (k = 1; k < DCTSIZE2; k++) {
  446.       huff_DECODE(actbl, s);
  447.       
  448.       r = s >> 4;
  449.       s &= 15;
  450.       
  451.       if (s) {
  452.     k += r;
  453.     check_bit_buffer(s);
  454.     r = get_bits(s);
  455.     s = huff_EXTEND(r, s);
  456.     /* Descale coefficient and output in natural (dezigzagged) order */
  457.     (*block)[ZAG[k]] = (JCOEF) (((JCOEF) s) * quanttbl[k]);
  458.       } else {
  459.     if (r != 15)
  460.       break;
  461.     k += 15;
  462.       }
  463.     }
  464.   }
  465. }
  466.  
  467.  
  468. /*
  469.  * Finish up at the end of a Huffman-compressed scan.
  470.  */
  471.  
  472. METHODDEF void
  473. decoder_term (decompress_info_ptr cinfo)
  474. {
  475.   /* No work needed */
  476. }
  477.  
  478.  
  479. /*
  480.  * The method selection routine for Huffman entropy decoding.
  481.  */
  482.  
  483. GLOBAL void
  484. jseldhuffman (decompress_info_ptr cinfo)
  485. {
  486.   if (! cinfo->arith_code) {
  487.     cinfo->methods->entropy_decode_init = decoder_init;
  488.     cinfo->methods->entropy_decode = decode_mcu;
  489.     cinfo->methods->entropy_decode_term = decoder_term;
  490.   }
  491. }
  492.