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 "../common/platform.h" 15 #include <brotli/types.h> 16 17 #if defined(__cplusplus) || defined(c_plusplus) 18 extern "C" { 19 #endif 20 21 #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1) 22 23 static const uint32_t kBitMask[33] = { 0x00000000, 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 (BROTLI_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 brotli_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 brotli_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. 62 May consume up to sizeof(brotli_reg_t) - 1 bytes of input. 63 Returns BROTLI_FALSE if data is required but there is no input available. 64 For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned 65 reading. */ 66 BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br); 67 68 static BROTLI_INLINE void BrotliBitReaderSaveState( 69 BrotliBitReader* const from, BrotliBitReaderState* to) { 70 to->val_ = from->val_; 71 to->bit_pos_ = from->bit_pos_; 72 to->next_in = from->next_in; 73 to->avail_in = from->avail_in; 74 } 75 76 static BROTLI_INLINE void BrotliBitReaderRestoreState( 77 BrotliBitReader* const to, BrotliBitReaderState* from) { 78 to->val_ = from->val_; 79 to->bit_pos_ = from->bit_pos_; 80 to->next_in = from->next_in; 81 to->avail_in = from->avail_in; 82 } 83 84 static BROTLI_INLINE uint32_t BrotliGetAvailableBits( 85 const BrotliBitReader* br) { 86 return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_; 87 } 88 89 /* Returns amount of unread bytes the bit reader still has buffered from the 90 BrotliInput, including whole bytes in br->val_. */ 91 static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) { 92 return br->avail_in + (BrotliGetAvailableBits(br) >> 3); 93 } 94 95 /* Checks if there is at least |num| bytes left in the input ring-buffer 96 (excluding the bits remaining in br->val_). */ 97 static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount( 98 BrotliBitReader* const br, size_t num) { 99 return TO_BROTLI_BOOL(br->avail_in >= num); 100 } 101 102 /* Guarantees that there are at least |n_bits| + 1 bits in accumulator. 103 Precondition: accumulator contains at least 1 bit. 104 |n_bits| should be in the range [1..24] for regular build. For portable 105 non-64-bit little-endian build only 16 bits are safe to request. */ 106 static BROTLI_INLINE void BrotliFillBitWindow( 107 BrotliBitReader* const br, uint32_t n_bits) { 108 #if (BROTLI_64_BITS) 109 if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) { 110 if (br->bit_pos_ >= 56) { 111 br->val_ >>= 56; 112 br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */ 113 br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 8; 114 br->avail_in -= 7; 115 br->next_in += 7; 116 } 117 } else if ( 118 !BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 16)) { 119 if (br->bit_pos_ >= 48) { 120 br->val_ >>= 48; 121 br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */ 122 br->val_ |= BROTLI_UNALIGNED_LOAD64LE(br->next_in) << 16; 123 br->avail_in -= 6; 124 br->next_in += 6; 125 } 126 } else { 127 if (br->bit_pos_ >= 32) { 128 br->val_ >>= 32; 129 br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */ 130 br->val_ |= ((uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in)) << 32; 131 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; 132 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; 133 } 134 } 135 #else 136 if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) { 137 if (br->bit_pos_ >= 24) { 138 br->val_ >>= 24; 139 br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */ 140 br->val_ |= BROTLI_UNALIGNED_LOAD32LE(br->next_in) << 8; 141 br->avail_in -= 3; 142 br->next_in += 3; 143 } 144 } else { 145 if (br->bit_pos_ >= 16) { 146 br->val_ >>= 16; 147 br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */ 148 br->val_ |= ((uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in)) << 16; 149 br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; 150 br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; 151 } 152 } 153 #endif 154 } 155 156 /* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no 157 more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */ 158 static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) { 159 BrotliFillBitWindow(br, 17); 160 } 161 162 /* Tries to pull one byte of input to accumulator. 163 Returns BROTLI_FALSE if there is no input available. */ 164 static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) { 165 if (br->avail_in == 0) { 166 return BROTLI_FALSE; 167 } 168 br->val_ >>= 8; 169 #if (BROTLI_64_BITS) 170 br->val_ |= ((uint64_t)*br->next_in) << 56; 171 #else 172 br->val_ |= ((uint32_t)*br->next_in) << 24; 173 #endif 174 br->bit_pos_ -= 8; 175 --br->avail_in; 176 ++br->next_in; 177 return BROTLI_TRUE; 178 } 179 180 /* Returns currently available bits. 181 The number of valid bits could be calculated by BrotliGetAvailableBits. */ 182 static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked( 183 BrotliBitReader* const br) { 184 return br->val_ >> br->bit_pos_; 185 } 186 187 /* Like BrotliGetBits, but does not mask the result. 188 The result contains at least 16 valid bits. */ 189 static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked( 190 BrotliBitReader* const br) { 191 BrotliFillBitWindow(br, 16); 192 return (uint32_t)BrotliGetBitsUnmasked(br); 193 } 194 195 /* Returns the specified number of bits from |br| without advancing bit 196 position. */ 197 static BROTLI_INLINE uint32_t BrotliGetBits( 198 BrotliBitReader* const br, uint32_t n_bits) { 199 BrotliFillBitWindow(br, n_bits); 200 return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 201 } 202 203 /* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there 204 is not enough input. */ 205 static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits( 206 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 207 while (BrotliGetAvailableBits(br) < n_bits) { 208 if (!BrotliPullByte(br)) { 209 return BROTLI_FALSE; 210 } 211 } 212 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 213 return BROTLI_TRUE; 214 } 215 216 /* Advances the bit pos by |n_bits|. */ 217 static BROTLI_INLINE void BrotliDropBits( 218 BrotliBitReader* const br, uint32_t n_bits) { 219 br->bit_pos_ += n_bits; 220 } 221 222 static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { 223 uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3; 224 uint32_t unused_bits = unused_bytes << 3; 225 br->avail_in += unused_bytes; 226 br->next_in -= unused_bytes; 227 if (unused_bits == sizeof(br->val_) << 3) { 228 br->val_ = 0; 229 } else { 230 br->val_ <<= unused_bits; 231 } 232 br->bit_pos_ += unused_bits; 233 } 234 235 /* Reads the specified number of bits from |br| and advances the bit pos. 236 Precondition: accumulator MUST contain at least |n_bits|. */ 237 static BROTLI_INLINE void BrotliTakeBits( 238 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 239 *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); 240 BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n", 241 (int)br->avail_in, (int)br->bit_pos_, (int)n_bits, (int)*val)); 242 BrotliDropBits(br, n_bits); 243 } 244 245 /* Reads the specified number of bits from |br| and advances the bit pos. 246 Assumes that there is enough input to perform BrotliFillBitWindow. */ 247 static BROTLI_INLINE uint32_t BrotliReadBits( 248 BrotliBitReader* const br, uint32_t n_bits) { 249 if (BROTLI_64_BITS || (n_bits <= 16)) { 250 uint32_t val; 251 BrotliFillBitWindow(br, n_bits); 252 BrotliTakeBits(br, n_bits, &val); 253 return val; 254 } else { 255 uint32_t low_val; 256 uint32_t high_val; 257 BrotliFillBitWindow(br, 16); 258 BrotliTakeBits(br, 16, &low_val); 259 BrotliFillBitWindow(br, 8); 260 BrotliTakeBits(br, n_bits - 16, &high_val); 261 return low_val | (high_val << 16); 262 } 263 } 264 265 /* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there 266 is not enough input. |n_bits| MUST be positive. */ 267 static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( 268 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { 269 while (BrotliGetAvailableBits(br) < n_bits) { 270 if (!BrotliPullByte(br)) { 271 return BROTLI_FALSE; 272 } 273 } 274 BrotliTakeBits(br, n_bits, val); 275 return BROTLI_TRUE; 276 } 277 278 /* Advances the bit reader position to the next byte boundary and verifies 279 that any skipped bits are set to zero. */ 280 static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) { 281 uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7; 282 uint32_t pad_bits = 0; 283 if (pad_bits_count != 0) { 284 BrotliTakeBits(br, pad_bits_count, &pad_bits); 285 } 286 return TO_BROTLI_BOOL(pad_bits == 0); 287 } 288 289 /* Copies remaining input bytes stored in the bit reader to the output. Value 290 |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be 291 warmed up again after this. */ 292 static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest, 293 BrotliBitReader* br, size_t num) { 294 while (BrotliGetAvailableBits(br) >= 8 && num > 0) { 295 *dest = (uint8_t)BrotliGetBitsUnmasked(br); 296 BrotliDropBits(br, 8); 297 ++dest; 298 --num; 299 } 300 memcpy(dest, br->next_in, num); 301 br->avail_in -= num; 302 br->next_in += num; 303 } 304 305 #if defined(__cplusplus) || defined(c_plusplus) 306 } /* extern "C" */ 307 #endif 308 309 #endif /* BROTLI_DEC_BIT_READER_H_ */ 310
