Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * jdhuff.c |
| 3 | * |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 4 | * Copyright (C) 1991, 1992, 1993, Thomas G. Lane. |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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 |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 10 | * and entropy_decode_init/term. |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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 | |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 20 | static INT32 get_buffer; /* current bit-extraction buffer */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 21 | static int bits_left; /* # of unused bits in it */ |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 22 | static boolean printed_eod; /* flag to suppress multiple end-of-data msgs */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 23 | |
| 24 | LOCAL void |
| 25 | fix_huff_tbl (HUFF_TBL * htbl) |
| 26 | /* Compute derived values for a Huffman table */ |
| 27 | { |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame] | 28 | int p, i, l, si; |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 29 | int lookbits, ctr; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 30 | char huffsize[257]; |
| 31 | UINT16 huffcode[257]; |
| 32 | UINT16 code; |
| 33 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame] | 34 | /* Figure C.1: make table of Huffman code length for each symbol */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 35 | /* Note that this is in code-length order. */ |
| 36 | |
| 37 | p = 0; |
| 38 | for (l = 1; l <= 16; l++) { |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 39 | for (i = 1; i <= (int) htbl->bits[l]; i++) |
| 40 | huffsize[p++] = (char) l; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 41 | } |
| 42 | huffsize[p] = 0; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 43 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame] | 44 | /* Figure C.2: generate the codes themselves */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 45 | /* Note that this is in code-length order. */ |
| 46 | |
| 47 | code = 0; |
| 48 | si = huffsize[0]; |
| 49 | p = 0; |
| 50 | while (huffsize[p]) { |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 51 | while (((int) huffsize[p]) == si) { |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 52 | huffcode[p++] = code; |
| 53 | code++; |
| 54 | } |
| 55 | code <<= 1; |
| 56 | si++; |
| 57 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 58 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 59 | /* Figure F.15: generate decoding tables for bit-sequential decoding */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 60 | |
| 61 | p = 0; |
| 62 | for (l = 1; l <= 16; l++) { |
| 63 | if (htbl->bits[l]) { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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 */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 66 | p += htbl->bits[l]; |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 67 | htbl->priv.dec.maxcode[l] = huffcode[p-1]; /* maximum code of length l */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 68 | } else { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 69 | htbl->priv.dec.maxcode[l] = -1; /* -1 if no codes of this length */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 70 | } |
| 71 | } |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 96 | } |
| 97 | |
| 98 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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 | * |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 128 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 129 | LOCAL void |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 130 | fill_bit_buffer (int nbits) |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 131 | /* Load up the bit buffer to a depth of at least nbits */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 132 | { |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 133 | /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */ |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 134 | /* (It is assumed that no request will be for more than that many bits.) */ |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 135 | while (bits_left < MIN_GET_BITS) { |
| 136 | register int c = JGETC(dcinfo); |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 137 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 138 | /* If it's 0xFF, check and discard stuffed zero byte */ |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 151 | * the data stream, so that we can produce some kind of image. |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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. |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 154 | * The main thing is to avoid getting a zillion warnings, hence |
| 155 | * we use a flag to ensure that only one warning appears. |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 163 | } |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 164 | |
| 165 | /* OK, load c into get_buffer */ |
| 166 | get_buffer = (get_buffer << 8) | c; |
| 167 | bits_left += 8; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 168 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 169 | } |
| 170 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 171 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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); } |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 184 | |
| 185 | #define get_bits(nbits) \ |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 186 | (((int) (get_buffer >> (bits_left -= (nbits)))) & ((1<<(nbits))-1)) |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 187 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 188 | #define peek_bits(nbits) \ |
| 189 | (((int) (get_buffer >> (bits_left - (nbits)))) & ((1<<(nbits))-1)) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 190 | |
| 191 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 224 | |
| 225 | LOCAL int |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 226 | slow_DECODE (HUFF_TBL * htbl, int min_bits) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 227 | { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 228 | register int l = min_bits; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 229 | register INT32 code; |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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); |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 244 | l++; |
| 245 | } |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 246 | |
| 247 | /* With garbage input we may reach the sentinel value l = 17. */ |
| 248 | |
| 249 | if (l > 16) { |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 250 | WARNMS(dcinfo->emethods, "Corrupt JPEG data: bad Huffman code"); |
| 251 | return 0; /* fake a zero as the safest result */ |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 252 | } |
| 253 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 254 | return htbl->huffval[ htbl->priv.dec.valptr[l] + |
| 255 | ((int) (code - htbl->priv.dec.mincode[l])) ]; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 256 | } |
| 257 | |
| 258 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 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 |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 268 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 269 | #define huff_EXTEND(x,s) ((x) < extend_test[s] ? (x) + extend_offset[s] : (x)) |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 270 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 }; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 274 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 }; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 280 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 281 | #endif /* AVOID_TABLES */ |
| 282 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 283 | |
| 284 | /* |
| 285 | * Initialize for a Huffman-compressed scan. |
| 286 | * This is invoked after reading the SOS marker. |
| 287 | */ |
| 288 | |
| 289 | METHODDEF void |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 290 | decoder_init (decompress_info_ptr cinfo) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 291 | { |
| 292 | short ci; |
| 293 | jpeg_component_info * compptr; |
| 294 | |
| 295 | /* Initialize static variables */ |
| 296 | dcinfo = cinfo; |
| 297 | bits_left = 0; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 298 | printed_eod = FALSE; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 330 | /* Throw away any unused bits remaining in bit buffer */ |
| 331 | nbytes = bits_left / 8; /* count any full bytes loaded into buffer */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 332 | bits_left = 0; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 333 | printed_eod = FALSE; /* next segment can get another warning */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 334 | |
| 335 | /* Scan for next JPEG marker */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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 */ |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 342 | /* we don't increment nbytes here since extra FFs are legal */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 343 | c = JGETC(cinfo); |
| 344 | } while (c == 0xFF); |
| 345 | } while (c == 0); /* repeat if it was a stuffed FF/00 */ |
| 346 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 347 | if (nbytes != 1) |
| 348 | WARNMS2(cinfo->emethods, |
| 349 | "Corrupt JPEG data: %d extraneous bytes before marker 0x%02x", |
| 350 | nbytes-1, c); |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 351 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 365 | cinfo->next_restart_num = (cinfo->next_restart_num + 1) & 7; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 366 | } |
| 367 | |
| 368 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 369 | /* ZAG[i] is the natural-order position of the i'th element of zigzag order. |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 370 | * If the incoming data is corrupted, decode_mcu could attempt to |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 389 | /* |
| 390 | * Decode and return one MCU's worth of Huffman-compressed coefficients. |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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...) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 397 | */ |
| 398 | |
| 399 | METHODDEF void |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 400 | decode_mcu (decompress_info_ptr cinfo, JBLOCKROW *MCU_data) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 401 | { |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 402 | register int s, k, r; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 403 | short blkn, ci; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 404 | register JBLOCKROW block; |
| 405 | register QUANT_TBL_PTR quanttbl; |
| 406 | HUFF_TBL *dctbl; |
| 407 | HUFF_TBL *actbl; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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 | |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 417 | /* Outer loop handles each block in the MCU */ |
| 418 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 419 | for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 420 | block = MCU_data[blkn]; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 421 | ci = cinfo->MCU_membership[blkn]; |
| 422 | compptr = cinfo->cur_comp_info[ci]; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 */ |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 430 | huff_DECODE(dctbl, s); |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 431 | if (s) { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 432 | check_bit_buffer(s); |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 433 | r = get_bits(s); |
| 434 | s = huff_EXTEND(r, s); |
| 435 | } |
| 436 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 437 | /* Convert DC difference to actual value, update last_dc_val */ |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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++) { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 446 | huff_DECODE(actbl, s); |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 447 | |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 448 | r = s >> 4; |
| 449 | s &= 15; |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 450 | |
| 451 | if (s) { |
| 452 | k += r; |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 453 | check_bit_buffer(s); |
Thomas G. Lane | 88aeed4 | 1992-12-10 00:00:00 +0000 | [diff] [blame] | 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 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 464 | } |
| 465 | } |
| 466 | |
| 467 | |
| 468 | /* |
| 469 | * Finish up at the end of a Huffman-compressed scan. |
| 470 | */ |
| 471 | |
| 472 | METHODDEF void |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 473 | decoder_term (decompress_info_ptr cinfo) |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 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) { |
Thomas G. Lane | cc7150e | 1993-02-18 00:00:00 +0000 | [diff] [blame^] | 487 | cinfo->methods->entropy_decode_init = decoder_init; |
| 488 | cinfo->methods->entropy_decode = decode_mcu; |
| 489 | cinfo->methods->entropy_decode_term = decoder_term; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 490 | } |
| 491 | } |