1 /* Copyright 2013 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 7 /* Bit reading helpers */ 8 9 #ifndef BROTLI_DEC_BIT_READER_H_ 10 #define BROTLI_DEC_BIT_READER_H_ 11 12 #include <string.h> /* memcpy */ 13 14 #include <brotli/types.h> 15 #include "./port.h" 16 17 #if defined(__cplusplus) || defined(c_plusplus) 18 extern "C" { 19 #endif 20 21 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(reg_t) >> 1) 22 23 static const uint32_t kBitMask[33] = { 0x0000, 24 0x00000001, 0x00000003, 0x00000007, 0x0000000F, 25 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF, 26 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF, 27 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF, 28 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF, 29 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF, 30 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF, 31 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF 32 }; 33 34 static BROTLI_INLINE uint32_t BitMask(uint32_t n) { 35 if (IS_CONSTANT(n) || BROTLI_HAS_UBFX) { 36 /* Masking with this expression turns to a single 37 "Unsigned Bit Field Extract" UBFX instruction on ARM. */ 38 return ~((0xffffffffU) << n); 39 } else { 40 return kBitMask[n]; 41 } 42 } 43 44 typedef struct { 45 reg_t val_; /* pre-fetched bits */ 46 uint32_t bit_pos_; /* current bit-reading position in val_ */ 47 const uint8_t* next_in; /* the byte we're reading from */ 48 size_t avail_in; 49 } BrotliBitReader; 50 51 typedef struct { 52 reg_t val_; 53 uint32_t bit_pos_; 54 const uint8_t* next_in; 55 size_t avail_in; 56 } BrotliBitReaderState; 57 58 /* Initializes the BrotliBitReader fields. */ 59 BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br); 60 61 /* Ensures that accumulator is not empty. May consume one byte of input. 62 Returns 0 if data is required but there is no input available. 63 For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned 64 reading. */ 65 BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br); 66 67 static BROTLI_INLINE void BrotliBitReaderSaveState( 68 BrotliBitReader* const from, BrotliBitReaderState* to) { 69 to->val_ = from->val_; 70 to->bit_pos_ = from->bit_pos_; 71 to->next_in = from->next_in; 72 to->avail_in = from->avail_in; 73 } 74 75 static BROTLI_INLINE void BrotliBitReaderRestoreState( 76 BrotliBitReader* const to, BrotliBitReaderState* from) { 77 to->val_ = from->val_; 78 to->bit_pos_ = from->bit_pos_; 79 to->next_in = from->next_in; 80 to->avail_in = from->avail_in; 81 } 82 83 static BROTLI_INLINE uint32_t BrotliGetAvailableBits( 84 const BrotliBitReader* br) { 85 return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_; 86 } 87 88 /* Returns amount of unread bytes the bit reader still has buffered from the 89 BrotliInput, including whole bytes in br->val_. */ 90 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) { 91 return br->avail_in + (BrotliGetAvailableBits(br) >> 3); 92 } 93 94 /* Checks if there is at least |num| bytes left in the input ring-buffer 95 (excluding the bits remaining in br->val_). */ 96 static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount( 97 BrotliBitReader* const br, size_t num) { 98 return TO_BROTLI_BOOL(br->avail_in >= num); 99 } 100 101 static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) { 102 if (BROTLI_LITTLE_ENDIAN) { 103 return *((const uint16_t*)in); 104 } else if (BROTLI_BIG_ENDIAN) { 105 uint16_t value = *((const uint16_t*)in); 106 return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8)); 107 } else { 108 return (uint16_t)(in[0] | (in[1] << 8)); 109 } 110 } 111 112 static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) { 113 if (BROTLI_LITTLE_ENDIAN) { 114 return *((const uint32_t*)in); 115 } else if (BROTLI_BIG_ENDIAN) { 116 uint32_t value = *((const uint32_t*)in); 117 return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) | 118 ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24); 119 } else { 120 uint32_t value = (uint32_t)(*(in++)); 121 value |= (uint32_t)(*(in++)) << 8; 122 value |= (uint32_t)(*(in++)) << 16; 123 value |= (uint32_t)(*(in++)) << 24; 124 return value; 125 } 126 } 127 128 #if (BROTLI_64_BITS) 129 static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) { 130 if (BROTLI_LITTLE_ENDIAN) { 131 return *((const uint64_t*)in); 132 } else if (BROTLI_BIG_ENDIAN) { 133 uint64_t value = *((const uint64_t*)in); 134 return 135 ((value & 0xFFU) << 56) | 136 ((value & 0xFF00U) << 40) | 137 ((value & 0xFF0000U) << 24) | 138 ((value & 0xFF000000U) << 8) | 139 ((value & 0xFF00000000U) >> 8) | 140 ((value & 0xFF0000000000U) >> 24) | 141 ((value & 0xFF000000000000U) >> 40) | 142 ((value & 0xFF00000000000000U) >> 56); 143 } else { 144 uint64_t value = (uint64_t)(*(in++)); 145 value |= (uint64_t)(*(in++)) << 8; 146 value |= (uint64_t)(*(in++)) << 16; 147 value |= (uint64_t)(*(in++)) << 24; 148 value |= (uint64_t)(*(in++)) << 32; 149 value |= (uint64_t)(*(in++)) << 40; 150 value |= (uint64_t)(*(in++)) << 48; 151 value |= (uint64_t)(*(in++)) << 56; 152 return value; 153 } 154 } 155 #endif 156 157 /* Guarantees that there are at least n_bits + 1 bits in accumulator. 158 Precondition: accumulator contains at least 1 bit. 159 n_bits should be in the range [1..24] for regular build. For portable 160 non-64-bit little-endian build only 16 bits are safe to request. */ 161 static BROTLI_INLINE void BrotliFillBitWindow( 162 BrotliBitReader* const br, uint32_t n_bits) { 163 #if (BROTLI_64_BITS) 164 if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) { 165 if (br->bit_pos_ >= 56) { 166 br->val_ >>= 56; 167 br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */ 168 br->val_ |= BrotliLoad64LE(br->next_in) << 8; 169 br->avail_in -= 7; 170 br->next_in += 7; 171 } 172 } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) { 173 if (br->bit_pos_ >= 48) { 174 br->val_ >>= 48; 175 br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */ 176 br->val_ |= BrotliLoad64LE(br->next_in) << 16; 177 br->avail_in -= 6; 178 br->next_in += 6; 179 } 180 } else { 181 if (br->bit_pos_ >= 32) { 182 br->val_ >>= 32; 183 br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */ 184 br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32; 185 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; 186 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; 187 } 188 } 189 #else 190 if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) { 191 if (br->bit_pos_ >= 24) { 192 br->val_ >>= 24; 193 br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */ 194 br->val_ |= BrotliLoad32LE(br->next_in) << 8; 195 br->avail_in -= 3; 196 br->next_in += 3; 197 } 198 } else { 199 if (br->bit_pos_ >= 16) { 200 br->val_ >>= 16; 201 br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */ 202 br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16; 203 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; 204 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; 205 } 206 } 207 #endif 208 } 209 210 /* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no 211 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */ 212 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) { 213 BrotliFillBitWindow(br, 17); 214 } 215 216 /* Pulls one byte of input to accumulator. */ 217 static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) { 218 if (br->avail_in == 0) { 219 return BROTLI_FALSE; 220 } 221 br->val_ >>= 8; 222 #if (BROTLI_64_BITS) 223 br->val_ |= ((uint64_t)*br->next_in) << 56; 224 #else 225 br->val_ |= ((uint32_t)*br->next_in) << 24; 226 #endif 227 br->bit_pos_ -= 8; 228 --br->avail_in; 229 ++br->next_in; 230 return BROTLI_TRUE; 231 } 232 233 /* Returns currently available bits. 234 The number of valid bits could be calculated by BrotliGetAvailableBits. */ 235 static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) { 236 return br->val_ >> br->bit_pos_; 237 } 238 239 /* Like BrotliGetBits, but does not mask the result. 240 The result contains at least 16 valid bits. */ 241 static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked( 242 BrotliBitReader* const br) { 243 BrotliFillBitWindow(br, 16); 244 return (uint32_t)BrotliGetBitsUnmasked(br); 245 } 246 247 /* Returns the specified number of bits from |br| without advancing bit pos. */ 248 static BROTLI_INLINE uint32_t BrotliGetBits( 249 BrotliBitReader* const br, uint32_t n_bits) { 250 BrotliFillBitWindow(br, n_bits); 251 return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 252 } 253 254 /* Tries to peek the specified amount of bits. Returns 0, if there is not 255 enough input. */ 256 static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits( 257 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 258 while (BrotliGetAvailableBits(br) < n_bits) { 259 if (!BrotliPullByte(br)) { 260 return BROTLI_FALSE; 261 } 262 } 263 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 264 return BROTLI_TRUE; 265 } 266 267 /* Advances the bit pos by n_bits. */ 268 static BROTLI_INLINE void BrotliDropBits( 269 BrotliBitReader* const br, uint32_t n_bits) { 270 br->bit_pos_ += n_bits; 271 } 272 273 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { 274 uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3; 275 uint32_t unused_bits = unused_bytes << 3; 276 br->avail_in += unused_bytes; 277 br->next_in -= unused_bytes; 278 if (unused_bits == sizeof(br->val_) << 3) { 279 br->val_ = 0; 280 } else { 281 br->val_ <<= unused_bits; 282 } 283 br->bit_pos_ += unused_bits; 284 } 285 286 /* Reads the specified number of bits from |br| and advances the bit pos. 287 Precondition: accumulator MUST contain at least n_bits. */ 288 static BROTLI_INLINE void BrotliTakeBits( 289 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 290 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 291 BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n", 292 (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val)); 293 BrotliDropBits(br, n_bits); 294 } 295 296 /* Reads the specified number of bits from |br| and advances the bit pos. 297 Assumes that there is enough input to perform BrotliFillBitWindow. */ 298 static BROTLI_INLINE uint32_t BrotliReadBits( 299 BrotliBitReader* const br, uint32_t n_bits) { 300 if (BROTLI_64_BITS || (n_bits <= 16)) { 301 uint32_t val; 302 BrotliFillBitWindow(br, n_bits); 303 BrotliTakeBits(br, n_bits, &val); 304 return val; 305 } else { 306 uint32_t low_val; 307 uint32_t high_val; 308 BrotliFillBitWindow(br, 16); 309 BrotliTakeBits(br, 16, &low_val); 310 BrotliFillBitWindow(br, 8); 311 BrotliTakeBits(br, n_bits - 16, &high_val); 312 return low_val | (high_val << 16); 313 } 314 } 315 316 /* Tries to read the specified amount of bits. Returns 0, if there is not 317 enough input. n_bits MUST be positive. */ 318 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( 319 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 320 while (BrotliGetAvailableBits(br) < n_bits) { 321 if (!BrotliPullByte(br)) { 322 return BROTLI_FALSE; 323 } 324 } 325 BrotliTakeBits(br, n_bits, val); 326 return BROTLI_TRUE; 327 } 328 329 /* Advances the bit reader position to the next byte boundary and verifies 330 that any skipped bits are set to zero. */ 331 static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) { 332 uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7; 333 uint32_t pad_bits = 0; 334 if (pad_bits_count != 0) { 335 BrotliTakeBits(br, pad_bits_count, &pad_bits); 336 } 337 return TO_BROTLI_BOOL(pad_bits == 0); 338 } 339 340 /* Copies remaining input bytes stored in the bit reader to the output. Value 341 num may not be larger than BrotliGetRemainingBytes. The bit reader must be 342 warmed up again after this. */ 343 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest, 344 BrotliBitReader* br, size_t num) { 345 while (BrotliGetAvailableBits(br) >= 8 && num > 0) { 346 *dest = (uint8_t)BrotliGetBitsUnmasked(br); 347 BrotliDropBits(br, 8); 348 ++dest; 349 --num; 350 } 351 memcpy(dest, br->next_in, num); 352 br->avail_in -= num; 353 br->next_in += num; 354 } 355 356 #if defined(__cplusplus) || defined(c_plusplus) 357 } /* extern "C" */ 358 #endif 359 360 #endif /* BROTLI_DEC_BIT_READER_H_ */ 361
