1 // Copyright 2010 Google Inc. All Rights Reserved. 2 // 3 // Use of this source code is governed by a BSD-style license 4 // that can be found in the COPYING file in the root of the source 5 // tree. An additional intellectual property rights grant can be found 6 // in the file PATENTS. All contributing project authors may 7 // be found in the AUTHORS file in the root of the source tree. 8 // ----------------------------------------------------------------------------- 9 // 10 // Boolean decoder 11 // 12 // Author: Skal (pascal.massimino (at) gmail.com) 13 // Vikas Arora (vikaas.arora (at) gmail.com) 14 15 #ifndef WEBP_UTILS_BIT_READER_H_ 16 #define WEBP_UTILS_BIT_READER_H_ 17 18 #include <assert.h> 19 #ifdef _MSC_VER 20 #include <stdlib.h> // _byteswap_ulong 21 #endif 22 #include <string.h> // For memcpy 23 #include "../webp/types.h" 24 25 #if defined(__cplusplus) || defined(c_plusplus) 26 extern "C" { 27 #endif 28 29 // The Boolean decoder needs to maintain infinite precision on the value_ field. 30 // However, since range_ is only 8bit, we only need an active window of 8 bits 31 // for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls 32 // below 128, range_ is updated, and fresh bits read from the bitstream are 33 // brought in as LSB. 34 // To avoid reading the fresh bits one by one (slow), we cache a few of them 35 // ahead (actually, we cache BITS of them ahead. See below). There's two 36 // strategies regarding how to shift these looked-ahead fresh bits into the 37 // 8bit window of value_: either we shift them in, while keeping the position of 38 // the window fixed. Or we slide the window to the right while keeping the cache 39 // bits at a fixed, right-justified, position. 40 // 41 // Example, for BITS=16: here is the content of value_ for both strategies: 42 // 43 // !USE_RIGHT_JUSTIFY || USE_RIGHT_JUSTIFY 44 // || 45 // <- 8b -><- 8b -><- BITS bits -> || <- 8b+3b -><- 8b -><- 13 bits -> 46 // [unused][value_][cached bits][0] || [unused...][value_][cached bits] 47 // [........00vvvvvvBBBBBBBBBBBBB000]LSB || [...........00vvvvvvBBBBBBBBBBBBB] 48 // || 49 // After calling VP8Shift(), where we need to shift away two zeros: 50 // [........vvvvvvvvBBBBBBBBBBB00000]LSB || [.............vvvvvvvvBBBBBBBBBBB] 51 // || 52 // Just before we need to call VP8LoadNewBytes(), the situation is: 53 // [........vvvvvv000000000000000000]LSB || [..........................vvvvvv] 54 // || 55 // And just after calling VP8LoadNewBytes(): 56 // [........vvvvvvvvBBBBBBBBBBBBBBBB]LSB || [........vvvvvvvvBBBBBBBBBBBBBBBB] 57 // 58 // -> we're back to height active 'value_' bits (marked 'v') and BITS cached 59 // bits (marked 'B') 60 // 61 // The right-justify strategy tends to use less shifts and is often faster. 62 63 //------------------------------------------------------------------------------ 64 // BITS can be any multiple of 8 from 8 to 56 (inclusive). 65 // Pick values that fit natural register size. 66 67 #if !defined(WEBP_REFERENCE_IMPLEMENTATION) 68 69 #define USE_RIGHT_JUSTIFY 70 71 #if defined(__i386__) || defined(_M_IX86) // x86 32bit 72 #define BITS 16 73 #elif defined(__x86_64__) || defined(_M_X64) // x86 64bit 74 #define BITS 56 75 #elif defined(__arm__) || defined(_M_ARM) // ARM 76 #define BITS 24 77 #else // reasonable default 78 #define BITS 24 79 #endif 80 81 #else // reference choices 82 83 #define USE_RIGHT_JUSTIFY 84 #define BITS 8 85 86 #endif 87 88 //------------------------------------------------------------------------------ 89 // Derived types and constants 90 91 // bit_t = natural register type 92 // lbit_t = natural type for memory I/O 93 94 #if (BITS > 32) 95 typedef uint64_t bit_t; 96 typedef uint64_t lbit_t; 97 #elif (BITS == 32) 98 typedef uint64_t bit_t; 99 typedef uint32_t lbit_t; 100 #elif (BITS == 24) 101 typedef uint32_t bit_t; 102 typedef uint32_t lbit_t; 103 #elif (BITS == 16) 104 typedef uint32_t bit_t; 105 typedef uint16_t lbit_t; 106 #else 107 typedef uint32_t bit_t; 108 typedef uint8_t lbit_t; 109 #endif 110 111 #ifndef USE_RIGHT_JUSTIFY 112 typedef bit_t range_t; // type for storing range_ 113 #define MASK ((((bit_t)1) << (BITS)) - 1) 114 #else 115 typedef uint32_t range_t; // range_ only uses 8bits here. No need for bit_t. 116 #endif 117 118 //------------------------------------------------------------------------------ 119 // Bitreader 120 121 typedef struct VP8BitReader VP8BitReader; 122 struct VP8BitReader { 123 const uint8_t* buf_; // next byte to be read 124 const uint8_t* buf_end_; // end of read buffer 125 int eof_; // true if input is exhausted 126 127 // boolean decoder 128 range_t range_; // current range minus 1. In [127, 254] interval. 129 bit_t value_; // current value 130 int bits_; // number of valid bits left 131 }; 132 133 // Initialize the bit reader and the boolean decoder. 134 void VP8InitBitReader(VP8BitReader* const br, 135 const uint8_t* const start, const uint8_t* const end); 136 137 // return the next value made of 'num_bits' bits 138 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits); 139 static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) { 140 return VP8GetValue(br, 1); 141 } 142 143 // return the next value with sign-extension. 144 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); 145 146 // Read a bit with proba 'prob'. Speed-critical function! 147 extern const uint8_t kVP8Log2Range[128]; 148 extern const range_t kVP8NewRange[128]; 149 150 void VP8LoadFinalBytes(VP8BitReader* const br); // special case for the tail 151 152 static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { 153 assert(br != NULL && br->buf_ != NULL); 154 // Read 'BITS' bits at a time if possible. 155 if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { 156 // convert memory type to register type (with some zero'ing!) 157 bit_t bits; 158 lbit_t in_bits = *(lbit_t*)br->buf_; 159 br->buf_ += (BITS) >> 3; 160 #if !defined(__BIG_ENDIAN__) 161 #if (BITS > 32) 162 // gcc 4.3 has builtin functions for swap32/swap64 163 #if defined(__GNUC__) && \ 164 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) 165 bits = (bit_t)__builtin_bswap64(in_bits); 166 #elif defined(_MSC_VER) 167 bits = (bit_t)_byteswap_uint64(in_bits); 168 #elif defined(__x86_64__) 169 __asm__ volatile("bswapq %0" : "=r"(bits) : "0"(in_bits)); 170 #else // generic code for swapping 64-bit values (suggested by bdb@) 171 bits = (bit_t)in_bits; 172 bits = ((bits & 0xffffffff00000000ull) >> 32) | 173 ((bits & 0x00000000ffffffffull) << 32); 174 bits = ((bits & 0xffff0000ffff0000ull) >> 16) | 175 ((bits & 0x0000ffff0000ffffull) << 16); 176 bits = ((bits & 0xff00ff00ff00ff00ull) >> 8) | 177 ((bits & 0x00ff00ff00ff00ffull) << 8); 178 #endif 179 bits >>= 64 - BITS; 180 #elif (BITS >= 24) 181 #if defined(__i386__) || defined(__x86_64__) 182 __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits)); 183 bits = (bit_t)in_bits; // 24b/32b -> 32b/64b zero-extension 184 #elif defined(_MSC_VER) 185 bits = (bit_t)_byteswap_ulong(in_bits); 186 #else 187 bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00) 188 | ((in_bits << 8) & 0xff0000) | (in_bits << 24); 189 #endif // x86 190 bits >>= (32 - BITS); 191 #elif (BITS == 16) 192 // gcc will recognize a 'rorw $8, ...' here: 193 bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8); 194 #else // BITS == 8 195 bits = (bit_t)in_bits; 196 #endif 197 #else // BIG_ENDIAN 198 bits = (bit_t)in_bits; 199 if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - BITS); 200 #endif 201 #ifndef USE_RIGHT_JUSTIFY 202 br->value_ |= bits << (-br->bits_); 203 #else 204 br->value_ = bits | (br->value_ << (BITS)); 205 #endif 206 br->bits_ += (BITS); 207 } else { 208 VP8LoadFinalBytes(br); // no need to be inlined 209 } 210 } 211 212 static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, range_t split) { 213 if (br->bits_ < 0) { // Make sure we have a least BITS bits in 'value_' 214 VP8LoadNewBytes(br); 215 } 216 #ifndef USE_RIGHT_JUSTIFY 217 split |= (MASK); 218 if (br->value_ > split) { 219 br->range_ -= split + 1; 220 br->value_ -= split + 1; 221 return 1; 222 } else { 223 br->range_ = split; 224 return 0; 225 } 226 #else 227 { 228 const int pos = br->bits_; 229 const range_t value = (range_t)(br->value_ >> pos); 230 if (value > split) { 231 br->range_ -= split + 1; 232 br->value_ -= (bit_t)(split + 1) << pos; 233 return 1; 234 } else { 235 br->range_ = split; 236 return 0; 237 } 238 } 239 #endif 240 } 241 242 static WEBP_INLINE void VP8Shift(VP8BitReader* const br) { 243 #ifndef USE_RIGHT_JUSTIFY 244 // range_ is in [0..127] interval here. 245 const bit_t idx = br->range_ >> (BITS); 246 const int shift = kVP8Log2Range[idx]; 247 br->range_ = kVP8NewRange[idx]; 248 br->value_ <<= shift; 249 br->bits_ -= shift; 250 #else 251 const int shift = kVP8Log2Range[br->range_]; 252 assert(br->range_ < (range_t)128); 253 br->range_ = kVP8NewRange[br->range_]; 254 br->bits_ -= shift; 255 #endif 256 } 257 static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) { 258 #ifndef USE_RIGHT_JUSTIFY 259 // It's important to avoid generating a 64bit x 64bit multiply here. 260 // We just need an 8b x 8b after all. 261 const range_t split = 262 (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8); 263 const int bit = VP8BitUpdate(br, split); 264 if (br->range_ <= (((range_t)0x7e << (BITS)) | (MASK))) { 265 VP8Shift(br); 266 } 267 return bit; 268 #else 269 const range_t split = (br->range_ * prob) >> 8; 270 const int bit = VP8BitUpdate(br, split); 271 if (br->range_ <= (range_t)0x7e) { 272 VP8Shift(br); 273 } 274 return bit; 275 #endif 276 } 277 278 static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) { 279 const range_t split = (br->range_ >> 1); 280 const int bit = VP8BitUpdate(br, split); 281 VP8Shift(br); 282 return bit ? -v : v; 283 } 284 285 286 // ----------------------------------------------------------------------------- 287 // Bitreader for lossless format 288 289 typedef uint64_t vp8l_val_t; // right now, this bit-reader can only use 64bit. 290 291 typedef struct { 292 vp8l_val_t val_; // pre-fetched bits 293 const uint8_t* buf_; // input byte buffer 294 size_t len_; // buffer length 295 size_t pos_; // byte position in buf_ 296 int bit_pos_; // current bit-reading position in val_ 297 int eos_; // bitstream is finished 298 int error_; // an error occurred (buffer overflow attempt...) 299 } VP8LBitReader; 300 301 void VP8LInitBitReader(VP8LBitReader* const br, 302 const uint8_t* const start, 303 size_t length); 304 305 // Sets a new data buffer. 306 void VP8LBitReaderSetBuffer(VP8LBitReader* const br, 307 const uint8_t* const buffer, size_t length); 308 309 // Reads the specified number of bits from Read Buffer. 310 // Flags an error in case end_of_stream or n_bits is more than allowed limit. 311 // Flags eos if this read attempt is going to cross the read buffer. 312 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits); 313 314 // Return the prefetched bits, so they can be looked up. 315 static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) { 316 return (uint32_t)(br->val_ >> br->bit_pos_); 317 } 318 319 // Discard 'num_bits' bits from the cache. 320 static WEBP_INLINE void VP8LDiscardBits(VP8LBitReader* const br, int num_bits) { 321 br->bit_pos_ += num_bits; 322 } 323 324 // Advances the Read buffer by 4 bytes to make room for reading next 32 bits. 325 void VP8LFillBitWindow(VP8LBitReader* const br); 326 327 #if defined(__cplusplus) || defined(c_plusplus) 328 } // extern "C" 329 #endif 330 331 #endif /* WEBP_UTILS_BIT_READER_H_ */ 332
