Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * jdhuff.c |
| 3 | * |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 4 | * Copyright (C) 1991, 1992, 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 |
| 10 | * and entropy_decoder_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 | |
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 */ |
| 22 | |
| 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 | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 29 | char huffsize[257]; |
| 30 | UINT16 huffcode[257]; |
| 31 | UINT16 code; |
| 32 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 33 | /* 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] | 34 | /* Note that this is in code-length order. */ |
| 35 | |
| 36 | p = 0; |
| 37 | for (l = 1; l <= 16; l++) { |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 38 | for (i = 1; i <= (int) htbl->bits[l]; i++) |
| 39 | huffsize[p++] = (char) l; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 40 | } |
| 41 | huffsize[p] = 0; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 42 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 43 | /* Figure C.2: generate the codes themselves */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 44 | /* Note that this is in code-length order. */ |
| 45 | |
| 46 | code = 0; |
| 47 | si = huffsize[0]; |
| 48 | p = 0; |
| 49 | while (huffsize[p]) { |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 50 | while (((int) huffsize[p]) == si) { |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 51 | huffcode[p++] = code; |
| 52 | code++; |
| 53 | } |
| 54 | code <<= 1; |
| 55 | si++; |
| 56 | } |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 57 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 58 | /* We don't bother to fill in the encoding tables ehufco[] and ehufsi[], */ |
| 59 | /* since they are not used for decoding. */ |
| 60 | |
| 61 | /* Figure F.15: generate decoding tables */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 62 | |
| 63 | p = 0; |
| 64 | for (l = 1; l <= 16; l++) { |
| 65 | if (htbl->bits[l]) { |
| 66 | htbl->valptr[l] = p; /* huffval[] index of 1st sym of code len l */ |
| 67 | htbl->mincode[l] = huffcode[p]; /* minimum code of length l */ |
| 68 | p += htbl->bits[l]; |
| 69 | htbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */ |
| 70 | } else { |
| 71 | htbl->maxcode[l] = -1; |
| 72 | } |
| 73 | } |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 74 | htbl->maxcode[17] = 0xFFFFFL; /* ensures huff_DECODE terminates */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 75 | } |
| 76 | |
| 77 | |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 78 | /* Extract the next N bits from the input stream (N <= 15) */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 79 | |
| 80 | LOCAL int |
| 81 | get_bits (int nbits) |
| 82 | { |
| 83 | int result; |
| 84 | |
| 85 | while (nbits > bits_left) { |
| 86 | int c = JGETC(dcinfo); |
| 87 | |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 88 | get_buffer <<= 8; |
| 89 | get_buffer |= c; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 90 | bits_left += 8; |
| 91 | /* If it's 0xFF, check and discard stuffed zero byte */ |
| 92 | if (c == 0xff) { |
| 93 | c = JGETC(dcinfo); /* Byte stuffing */ |
| 94 | if (c != 0) |
| 95 | ERREXIT1(dcinfo->emethods, |
| 96 | "Unexpected marker 0x%02x in compressed data", c); |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | bits_left -= nbits; |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 101 | result = ((int) (get_buffer >> bits_left)) & ((1 << nbits) - 1); |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 102 | return result; |
| 103 | } |
| 104 | |
| 105 | /* Macro to make things go at some speed! */ |
| 106 | |
| 107 | #define get_bit() (bits_left ? \ |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 108 | ((int) (get_buffer >> (--bits_left))) & 1 : \ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 109 | get_bits(1)) |
| 110 | |
| 111 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 112 | /* Figure F.16: extract next coded symbol from input stream */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 113 | |
| 114 | LOCAL int |
| 115 | huff_DECODE (HUFF_TBL * htbl) |
| 116 | { |
| 117 | int l, p; |
| 118 | INT32 code; |
| 119 | |
| 120 | code = get_bit(); |
| 121 | l = 1; |
| 122 | while (code > htbl->maxcode[l]) { |
| 123 | code = (code << 1) + get_bit(); |
| 124 | l++; |
| 125 | } |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 126 | |
| 127 | /* With garbage input we may reach the sentinel value l = 17. */ |
| 128 | |
| 129 | if (l > 16) { |
| 130 | ERREXIT(dcinfo->emethods, "Corrupted data in JPEG file"); |
| 131 | } |
| 132 | |
| 133 | p = (int) (htbl->valptr[l] + (code - htbl->mincode[l])); |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 134 | |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 135 | return (int) htbl->huffval[p]; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 136 | } |
| 137 | |
| 138 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 139 | /* Figure F.12: extend sign bit */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 140 | |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 141 | /* NB: on some compilers this will only work for s > 0 */ |
| 142 | |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 143 | #define huff_EXTEND(x, s) ((x) < (1 << ((s)-1)) ? \ |
| 144 | (x) + (-1 << (s)) + 1 : \ |
| 145 | (x)) |
| 146 | |
| 147 | |
| 148 | /* Decode a single block's worth of coefficients */ |
| 149 | /* Note that only the difference is returned for the DC coefficient */ |
| 150 | |
| 151 | LOCAL void |
| 152 | decode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl) |
| 153 | { |
| 154 | int s, k, r, n; |
| 155 | |
| 156 | /* zero out the coefficient block */ |
| 157 | |
| 158 | MEMZERO((void *) block, SIZEOF(JBLOCK)); |
| 159 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 160 | /* Section F.2.2.1: decode the DC coefficient difference */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 161 | |
| 162 | s = huff_DECODE(dctbl); |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 163 | if (s) { |
| 164 | r = get_bits(s); |
| 165 | s = huff_EXTEND(r, s); |
| 166 | } |
| 167 | block[0] = s; |
| 168 | |
Thomas G. Lane | 4a6b730 | 1992-03-17 00:00:00 +0000 | [diff] [blame^] | 169 | /* Section F.2.2.2: decode the AC coefficients */ |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 170 | |
| 171 | for (k = 1; k < DCTSIZE2; k++) { |
| 172 | r = huff_DECODE(actbl); |
| 173 | |
| 174 | s = r & 15; |
| 175 | n = r >> 4; |
| 176 | |
| 177 | if (s) { |
Thomas G. Lane | bd543f0 | 1991-12-13 00:00:00 +0000 | [diff] [blame] | 178 | k += n; |
Thomas G. Lane | 2cbeb8a | 1991-10-07 00:00:00 +0000 | [diff] [blame] | 179 | r = get_bits(s); |
| 180 | block[k] = huff_EXTEND(r, s); |
| 181 | } else { |
| 182 | if (n != 15) |
| 183 | break; |
| 184 | k += 15; |
| 185 | } |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | |
| 190 | /* |
| 191 | * Initialize for a Huffman-compressed scan. |
| 192 | * This is invoked after reading the SOS marker. |
| 193 | */ |
| 194 | |
| 195 | METHODDEF void |
| 196 | huff_decoder_init (decompress_info_ptr cinfo) |
| 197 | { |
| 198 | short ci; |
| 199 | jpeg_component_info * compptr; |
| 200 | |
| 201 | /* Initialize static variables */ |
| 202 | dcinfo = cinfo; |
| 203 | bits_left = 0; |
| 204 | |
| 205 | for (ci = 0; ci < cinfo->comps_in_scan; ci++) { |
| 206 | compptr = cinfo->cur_comp_info[ci]; |
| 207 | /* Make sure requested tables are present */ |
| 208 | if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL || |
| 209 | cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL) |
| 210 | ERREXIT(cinfo->emethods, "Use of undefined Huffman table"); |
| 211 | /* Compute derived values for Huffman tables */ |
| 212 | /* We may do this more than once for same table, but it's not a big deal */ |
| 213 | fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]); |
| 214 | fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]); |
| 215 | /* Initialize DC predictions to 0 */ |
| 216 | cinfo->last_dc_val[ci] = 0; |
| 217 | } |
| 218 | |
| 219 | /* Initialize restart stuff */ |
| 220 | cinfo->restarts_to_go = cinfo->restart_interval; |
| 221 | cinfo->next_restart_num = 0; |
| 222 | } |
| 223 | |
| 224 | |
| 225 | /* |
| 226 | * Check for a restart marker & resynchronize decoder. |
| 227 | */ |
| 228 | |
| 229 | LOCAL void |
| 230 | process_restart (decompress_info_ptr cinfo) |
| 231 | { |
| 232 | int c, nbytes; |
| 233 | short ci; |
| 234 | |
| 235 | /* Throw away any partial unread byte */ |
| 236 | bits_left = 0; |
| 237 | |
| 238 | /* Scan for next JPEG marker */ |
| 239 | nbytes = 0; |
| 240 | do { |
| 241 | do { /* skip any non-FF bytes */ |
| 242 | nbytes++; |
| 243 | c = JGETC(cinfo); |
| 244 | } while (c != 0xFF); |
| 245 | do { /* skip any duplicate FFs */ |
| 246 | nbytes++; |
| 247 | c = JGETC(cinfo); |
| 248 | } while (c == 0xFF); |
| 249 | } while (c == 0); /* repeat if it was a stuffed FF/00 */ |
| 250 | |
| 251 | if (c != (RST0 + cinfo->next_restart_num)) |
| 252 | ERREXIT2(cinfo->emethods, "Found 0x%02x marker instead of RST%d", |
| 253 | c, cinfo->next_restart_num); |
| 254 | |
| 255 | if (nbytes != 2) |
| 256 | TRACEMS2(cinfo->emethods, 1, "Skipped %d bytes before RST%d", |
| 257 | nbytes-2, cinfo->next_restart_num); |
| 258 | else |
| 259 | TRACEMS1(cinfo->emethods, 2, "RST%d", cinfo->next_restart_num); |
| 260 | |
| 261 | /* Re-initialize DC predictions to 0 */ |
| 262 | for (ci = 0; ci < cinfo->comps_in_scan; ci++) |
| 263 | cinfo->last_dc_val[ci] = 0; |
| 264 | |
| 265 | /* Update restart state */ |
| 266 | cinfo->restarts_to_go = cinfo->restart_interval; |
| 267 | cinfo->next_restart_num++; |
| 268 | cinfo->next_restart_num &= 7; |
| 269 | } |
| 270 | |
| 271 | |
| 272 | /* |
| 273 | * Decode and return one MCU's worth of Huffman-compressed coefficients. |
| 274 | */ |
| 275 | |
| 276 | METHODDEF void |
| 277 | huff_decode (decompress_info_ptr cinfo, JBLOCK *MCU_data) |
| 278 | { |
| 279 | short blkn, ci; |
| 280 | jpeg_component_info * compptr; |
| 281 | |
| 282 | /* Account for restart interval, process restart marker if needed */ |
| 283 | if (cinfo->restart_interval) { |
| 284 | if (cinfo->restarts_to_go == 0) |
| 285 | process_restart(cinfo); |
| 286 | cinfo->restarts_to_go--; |
| 287 | } |
| 288 | |
| 289 | for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { |
| 290 | ci = cinfo->MCU_membership[blkn]; |
| 291 | compptr = cinfo->cur_comp_info[ci]; |
| 292 | decode_one_block(MCU_data[blkn], |
| 293 | cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no], |
| 294 | cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]); |
| 295 | /* Convert DC difference to actual value, update last_dc_val */ |
| 296 | MCU_data[blkn][0] += cinfo->last_dc_val[ci]; |
| 297 | cinfo->last_dc_val[ci] = MCU_data[blkn][0]; |
| 298 | } |
| 299 | } |
| 300 | |
| 301 | |
| 302 | /* |
| 303 | * Finish up at the end of a Huffman-compressed scan. |
| 304 | */ |
| 305 | |
| 306 | METHODDEF void |
| 307 | huff_decoder_term (decompress_info_ptr cinfo) |
| 308 | { |
| 309 | /* No work needed */ |
| 310 | } |
| 311 | |
| 312 | |
| 313 | /* |
| 314 | * The method selection routine for Huffman entropy decoding. |
| 315 | */ |
| 316 | |
| 317 | GLOBAL void |
| 318 | jseldhuffman (decompress_info_ptr cinfo) |
| 319 | { |
| 320 | if (! cinfo->arith_code) { |
| 321 | cinfo->methods->entropy_decoder_init = huff_decoder_init; |
| 322 | cinfo->methods->entropy_decode = huff_decode; |
| 323 | cinfo->methods->entropy_decoder_term = huff_decoder_term; |
| 324 | } |
| 325 | } |