1 /* 2 * jdhuff.h 3 * 4 * This file was part of the Independent JPEG Group's software: 5 * Copyright (C) 1991-1997, Thomas G. Lane. 6 * libjpeg-turbo Modifications: 7 * Copyright (C) 2010-2011, 2015-2016, 2021, D. R. Commander. 8 * Copyright (C) 2018, Matthias Räncker. 9 * For conditions of distribution and use, see the accompanying README.ijg 10 * file. 11 * 12 * This file contains declarations for Huffman entropy decoding routines 13 * that are shared between the sequential decoder (jdhuff.c) and the 14 * progressive decoder (jdphuff.c). No other modules need to see these. 15 */ 16 17 #include "jconfigint.h" 18 19 #ifndef HUFF_DECODE_OPT 20 #define HUFF_LOOKAHEAD 8 21 #define HUFF_CODE_LARGE_LONG_ALIGNED 0 22 #else 23 // OH ISSUE: jpeg optimize 24 /* Derived data constructed for each Huffman table */ 25 #define MAX_HUFF_CODE_LEN 16 26 27 #define HUFF_LOOKAHEAD 10 /* # of bits of lookahead 9-13 maybe */ 28 #define HUFF_AC_SYMBOLS 192 29 30 #define HUFF_L_REM (16 - HUFF_LOOKAHEAD) 31 #define HUFF_L_DUP ((1 << HUFF_L_REM) - (HUFF_L_REM + 1)) 32 #define HUFF_L_UNUSED ((1 << HUFF_L_REM) - (1 << ((HUFF_L_REM)/2)) - (1 << ((HUFF_L_REM + 1)/2)) + 1) 33 #define HUFF_L_SIZE (HUFF_AC_SYMBOLS + HUFF_L_DUP + HUFF_L_UNUSED) 34 #define HUFF_CODE_LARGE_LONG_ALIGNED (HUFF_L_SIZE + (-HUFF_L_SIZE & 0xf)) 35 36 #define COEF_BITS_OFFSET 0 37 #define COEF_BITS_BITS 4 38 #define ZERO_NUM1_OFFSET 4 39 #define ZERO_NUM_BITS 7 40 #define NB_OFFSET 11 41 #define NB_BITS 5 42 #define COEF1_OFFSET 16 43 #define COEF_VALUE_BITS 16 44 45 #define EXTRA_BITS_OFFSET COEF_BITS_OFFSET // 2nd table offset bits 46 #define EXTRA_BITS_BITS COEF_BITS_BITS 47 48 #define SYM_OFFSET COEF_BITS_OFFSET 49 50 #define MAKE_BITS(x, s) (x) << (s) 51 #define GETS_BITS(x, s, l) (((x) >> (s)) & ((0x1L << (l)) - 1)) 52 53 #define MAKE_ZERO_NUM1(x) MAKE_BITS((x), ZERO_NUM1_OFFSET) 54 #define MAKE_COEF_BITS(x) MAKE_BITS((x), COEF_BITS_OFFSET) 55 #define MAKE_SYM(x) MAKE_BITS((x), SYM_OFFSET) 56 #define MAKE_NB(x) MAKE_BITS((x), NB_OFFSET) 57 #define MAKE_COEF1(x) (unsigned long long) MAKE_BITS((UINT16) (x), COEF1_OFFSET) 58 #define MAKE_BASE(x) MAKE_BITS((x), COEF1_OFFSET) 59 #define MAKE_EXTRA_BITS(x) MAKE_BITS((x), EXTRA_BITS_OFFSET) 60 61 #define GET_ZERO_NUM1(x) GETS_BITS((x), ZERO_NUM1_OFFSET, ZERO_NUM_BITS) 62 #define GET_COEF_BITS(x) GETS_BITS((x), COEF_BITS_OFFSET, COEF_BITS_BITS) 63 #define GET_NB(x) GETS_BITS((x), NB_OFFSET, NB_BITS) 64 #define GET_COEF1(x) GETS_BITS((x), COEF1_OFFSET, COEF_VALUE_BITS) 65 #define GET_BASE(x) GETS_BITS((x), COEF1_OFFSET, COEF_VALUE_BITS) 66 #define GET_EXTRA_BITS(x) GETS_BITS((x), EXTRA_BITS_OFFSET, EXTRA_BITS_BITS) 67 #endif 68 69 typedef struct { 70 /* Basic tables: (element [0] of each array is unused) */ 71 JLONG maxcode[18]; /* largest code of length k (-1 if none) */ 72 /* (maxcode[17] is a sentinel to ensure jpeg_huff_decode terminates) */ 73 JLONG valoffset[18]; /* huffval[] offset for codes of length k */ 74 /* valoffset[k] = huffval[] index of 1st symbol of code length k, less 75 * the smallest code of length k; so given a code of length k, the 76 * corresponding symbol is huffval[code + valoffset[k]] 77 */ 78 79 /* Link to public Huffman table (needed only in jpeg_huff_decode) */ 80 JHUFF_TBL *pub; 81 82 /* Lookahead table: indexed by the next HUFF_LOOKAHEAD bits of 83 * the input data stream. If the next Huffman code is no more 84 * than HUFF_LOOKAHEAD bits long, we can obtain its length and 85 * the corresponding symbol directly from this tables. 86 * 87 * The lower 8 bits of each table entry contain the number of 88 * bits in the corresponding Huffman code, or HUFF_LOOKAHEAD + 1 89 * if too long. The next 8 bits of each entry contain the 90 * symbol. 91 */ 92 int lookup[(1 << HUFF_LOOKAHEAD) + HUFF_CODE_LARGE_LONG_ALIGNED]; 93 } d_derived_tbl; 94 95 /* Expand a Huffman table definition into the derived format */ 96 EXTERN(void) jpeg_make_d_derived_tbl(j_decompress_ptr cinfo, boolean isDC, 97 int tblno, d_derived_tbl **pdtbl); 98 99 100 /* 101 * Fetching the next N bits from the input stream is a time-critical operation 102 * for the Huffman decoders. We implement it with a combination of inline 103 * macros and out-of-line subroutines. Note that N (the number of bits 104 * demanded at one time) never exceeds 15 for JPEG use. 105 * 106 * We read source bytes into get_buffer and dole out bits as needed. 107 * If get_buffer already contains enough bits, they are fetched in-line 108 * by the macros CHECK_BIT_BUFFER and GET_BITS. When there aren't enough 109 * bits, jpeg_fill_bit_buffer is called; it will attempt to fill get_buffer 110 * as full as possible (not just to the number of bits needed; this 111 * prefetching reduces the overhead cost of calling jpeg_fill_bit_buffer). 112 * Note that jpeg_fill_bit_buffer may return FALSE to indicate suspension. 113 * On TRUE return, jpeg_fill_bit_buffer guarantees that get_buffer contains 114 * at least the requested number of bits --- dummy zeroes are inserted if 115 * necessary. 116 */ 117 118 #if !defined(_WIN32) && !defined(SIZEOF_SIZE_T) 119 #error Cannot determine word size 120 #endif 121 122 #if SIZEOF_SIZE_T == 8 || defined(_WIN64) 123 124 typedef size_t bit_buf_type; /* type of bit-extraction buffer */ 125 #define BIT_BUF_SIZE 64 /* size of buffer in bits */ 126 127 #elif defined(__x86_64__) && defined(__ILP32__) 128 129 typedef unsigned long long bit_buf_type; /* type of bit-extraction buffer */ 130 #define BIT_BUF_SIZE 64 /* size of buffer in bits */ 131 132 #else 133 134 typedef unsigned long bit_buf_type; /* type of bit-extraction buffer */ 135 #define BIT_BUF_SIZE 32 /* size of buffer in bits */ 136 137 #endif 138 139 /* If long is > 32 bits on your machine, and shifting/masking longs is 140 * reasonably fast, making bit_buf_type be long and setting BIT_BUF_SIZE 141 * appropriately should be a win. Unfortunately we can't define the size 142 * with something like #define BIT_BUF_SIZE (sizeof(bit_buf_type)*8) 143 * because not all machines measure sizeof in 8-bit bytes. 144 */ 145 146 typedef struct { /* Bitreading state saved across MCUs */ 147 bit_buf_type get_buffer; /* current bit-extraction buffer */ 148 int bits_left; /* # of unused bits in it */ 149 } bitread_perm_state; 150 151 typedef struct { /* Bitreading working state within an MCU */ 152 /* Current data source location */ 153 /* We need a copy, rather than munging the original, in case of suspension */ 154 const JOCTET *next_input_byte; /* => next byte to read from source */ 155 size_t bytes_in_buffer; /* # of bytes remaining in source buffer */ 156 /* Bit input buffer --- note these values are kept in register variables, 157 * not in this struct, inside the inner loops. 158 */ 159 bit_buf_type get_buffer; /* current bit-extraction buffer */ 160 int bits_left; /* # of unused bits in it */ 161 /* Pointer needed by jpeg_fill_bit_buffer. */ 162 j_decompress_ptr cinfo; /* back link to decompress master record */ 163 } bitread_working_state; 164 165 /* Macros to declare and load/save bitread local variables. */ 166 #define BITREAD_STATE_VARS \ 167 register bit_buf_type get_buffer; \ 168 register int bits_left; \ 169 bitread_working_state br_state 170 171 #define BITREAD_LOAD_STATE(cinfop, permstate) \ 172 br_state.cinfo = cinfop; \ 173 br_state.next_input_byte = cinfop->src->next_input_byte; \ 174 br_state.bytes_in_buffer = cinfop->src->bytes_in_buffer; \ 175 get_buffer = permstate.get_buffer; \ 176 bits_left = permstate.bits_left; 177 178 #define BITREAD_SAVE_STATE(cinfop, permstate) \ 179 cinfop->src->next_input_byte = br_state.next_input_byte; \ 180 cinfop->src->bytes_in_buffer = br_state.bytes_in_buffer; \ 181 permstate.get_buffer = get_buffer; \ 182 permstate.bits_left = bits_left 183 184 /* 185 * These macros provide the in-line portion of bit fetching. 186 * Use CHECK_BIT_BUFFER to ensure there are N bits in get_buffer 187 * before using GET_BITS, PEEK_BITS, or DROP_BITS. 188 * The variables get_buffer and bits_left are assumed to be locals, 189 * but the state struct might not be (jpeg_huff_decode needs this). 190 * CHECK_BIT_BUFFER(state, n, action); 191 * Ensure there are N bits in get_buffer; if suspend, take action. 192 * val = GET_BITS(n); 193 * Fetch next N bits. 194 * val = PEEK_BITS(n); 195 * Fetch next N bits without removing them from the buffer. 196 * DROP_BITS(n); 197 * Discard next N bits. 198 * The value N should be a simple variable, not an expression, because it 199 * is evaluated multiple times. 200 */ 201 202 #define CHECK_BIT_BUFFER(state, nbits, action) { \ 203 if (bits_left < (nbits)) { \ 204 if (!jpeg_fill_bit_buffer(&(state), get_buffer, bits_left, nbits)) \ 205 { action; } \ 206 get_buffer = (state).get_buffer; bits_left = (state).bits_left; \ 207 } \ 208 } 209 210 #define GET_BITS(nbits) \ 211 (((int)(get_buffer >> (bits_left -= (nbits)))) & ((1 << (nbits)) - 1)) 212 213 #define PEEK_BITS(nbits) \ 214 (((int)(get_buffer >> (bits_left - (nbits)))) & ((1 << (nbits)) - 1)) 215 216 #define DROP_BITS(nbits) \ 217 (bits_left -= (nbits)) 218 219 /* Load up the bit buffer to a depth of at least nbits */ 220 EXTERN(boolean) jpeg_fill_bit_buffer(bitread_working_state *state, 221 register bit_buf_type get_buffer, 222 register int bits_left, int nbits); 223 224 225 /* 226 * Code for extracting next Huffman-coded symbol from input bit stream. 227 * Again, this is time-critical and we make the main paths be macros. 228 * 229 * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits 230 * without looping. Usually, more than 95% of the Huffman codes will be 8 231 * or fewer bits long. The few overlength codes are handled with a loop, 232 * which need not be inline code. 233 * 234 * Notes about the HUFF_DECODE macro: 235 * 1. Near the end of the data segment, we may fail to get enough bits 236 * for a lookahead. In that case, we do it the hard way. 237 * 2. If the lookahead table contains no entry, the next code must be 238 * more than HUFF_LOOKAHEAD bits long. 239 * 3. jpeg_huff_decode returns -1 if forced to suspend. 240 */ 241 242 #define HUFF_DECODE(result, state, htbl, failaction, slowlabel) { \ 243 register int nb, look; \ 244 if (bits_left < HUFF_LOOKAHEAD) { \ 245 if (!jpeg_fill_bit_buffer(&state, get_buffer, bits_left, 0)) \ 246 { failaction; } \ 247 get_buffer = state.get_buffer; bits_left = state.bits_left; \ 248 if (bits_left < HUFF_LOOKAHEAD) { \ 249 nb = 1; goto slowlabel; \ 250 } \ 251 } \ 252 look = PEEK_BITS(HUFF_LOOKAHEAD); \ 253 if ((nb = (htbl->lookup[look] >> HUFF_LOOKAHEAD)) <= HUFF_LOOKAHEAD) { \ 254 DROP_BITS(nb); \ 255 result = htbl->lookup[look] & ((1 << HUFF_LOOKAHEAD) - 1); \ 256 } else { \ 257 slowlabel: \ 258 if ((result = \ 259 jpeg_huff_decode(&state, get_buffer, bits_left, htbl, nb)) < 0) \ 260 { failaction; } \ 261 get_buffer = state.get_buffer; bits_left = state.bits_left; \ 262 } \ 263 } 264 265 #define HUFF_DECODE_FAST(s, nb, htbl) \ 266 FILL_BIT_BUFFER_FAST; \ 267 s = PEEK_BITS(HUFF_LOOKAHEAD); \ 268 s = htbl->lookup[s]; \ 269 nb = s >> HUFF_LOOKAHEAD; \ 270 /* Pre-execute the common case of nb <= HUFF_LOOKAHEAD */ \ 271 DROP_BITS(nb); \ 272 s = s & ((1 << HUFF_LOOKAHEAD) - 1); \ 273 if (nb > HUFF_LOOKAHEAD) { \ 274 /* Equivalent of jpeg_huff_decode() */ \ 275 /* Don't use GET_BITS() here because we don't want to modify bits_left */ \ 276 s = (get_buffer >> bits_left) & ((1 << (nb)) - 1); \ 277 while (s > htbl->maxcode[nb]) { \ 278 s <<= 1; \ 279 s |= GET_BITS(1); \ 280 nb++; \ 281 } \ 282 if (nb > 16) \ 283 s = 0; \ 284 else \ 285 s = htbl->pub->huffval[(int)(s + htbl->valoffset[nb]) & 0xFF]; \ 286 } 287 288 /* Out-of-line case for Huffman code fetching */ 289 EXTERN(int) jpeg_huff_decode(bitread_working_state *state, 290 register bit_buf_type get_buffer, 291 register int bits_left, d_derived_tbl *htbl, 292 int min_bits); 293