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