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