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 #define BITS 32 // can be 32, 16 or 8 28 #define MASK ((((bit_t)1) << (BITS)) - 1) 29 #if (BITS == 32) 30 typedef uint64_t bit_t; // natural register type 31 typedef uint32_t lbit_t; // natural type for memory I/O 32 #elif (BITS == 16) 33 typedef uint32_t bit_t; 34 typedef uint16_t lbit_t; 35 #else 36 typedef uint32_t bit_t; 37 typedef uint8_t lbit_t; 38 #endif 39 40 //------------------------------------------------------------------------------ 41 // Bitreader and code-tree reader 42 43 typedef struct VP8BitReader VP8BitReader; 44 struct VP8BitReader { 45 const uint8_t* buf_; // next byte to be read 46 const uint8_t* buf_end_; // end of read buffer 47 int eof_; // true if input is exhausted 48 49 // boolean decoder 50 bit_t range_; // current range minus 1. In [127, 254] interval. 51 bit_t value_; // current value 52 int missing_; // number of missing bits in value_ (8bit) 53 }; 54 55 // Initialize the bit reader and the boolean decoder. 56 void VP8InitBitReader(VP8BitReader* const br, 57 const uint8_t* const start, const uint8_t* const end); 58 59 // return the next value made of 'num_bits' bits 60 uint32_t VP8GetValue(VP8BitReader* const br, int num_bits); 61 static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) { 62 return VP8GetValue(br, 1); 63 } 64 65 // return the next value with sign-extension. 66 int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); 67 68 // Read a bit with proba 'prob'. Speed-critical function! 69 extern const uint8_t kVP8Log2Range[128]; 70 extern const bit_t kVP8NewRange[128]; 71 72 void VP8LoadFinalBytes(VP8BitReader* const br); // special case for the tail 73 74 static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { 75 assert(br && br->buf_); 76 // Read 'BITS' bits at a time if possible. 77 if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { 78 // convert memory type to register type (with some zero'ing!) 79 bit_t bits; 80 lbit_t in_bits = *(lbit_t*)br->buf_; 81 br->buf_ += (BITS) >> 3; 82 #if !defined(__BIG_ENDIAN__) 83 #if (BITS == 32) 84 #if defined(__i386__) || defined(__x86_64__) 85 __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits)); 86 bits = (bit_t)in_bits; // 32b -> 64b zero-extension 87 #elif defined(_MSC_VER) 88 bits = _byteswap_ulong(in_bits); 89 #else 90 bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00) 91 | ((in_bits << 8) & 0xff0000) | (in_bits << 24); 92 #endif // x86 93 #elif (BITS == 16) 94 // gcc will recognize a 'rorw $8, ...' here: 95 bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8); 96 #endif 97 #else // LITTLE_ENDIAN 98 bits = (bit_t)in_bits; 99 #endif 100 br->value_ |= bits << br->missing_; 101 br->missing_ -= (BITS); 102 } else { 103 VP8LoadFinalBytes(br); // no need to be inlined 104 } 105 } 106 107 static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, bit_t split) { 108 const bit_t value_split = split | (MASK); 109 if (br->missing_ > 0) { // Make sure we have a least BITS bits in 'value_' 110 VP8LoadNewBytes(br); 111 } 112 if (br->value_ > value_split) { 113 br->range_ -= value_split + 1; 114 br->value_ -= value_split + 1; 115 return 1; 116 } else { 117 br->range_ = value_split; 118 return 0; 119 } 120 } 121 122 static WEBP_INLINE void VP8Shift(VP8BitReader* const br) { 123 // range_ is in [0..127] interval here. 124 const int idx = br->range_ >> (BITS); 125 const int shift = kVP8Log2Range[idx]; 126 br->range_ = kVP8NewRange[idx]; 127 br->value_ <<= shift; 128 br->missing_ += shift; 129 } 130 131 static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) { 132 // It's important to avoid generating a 64bit x 64bit multiply here. 133 // We just need an 8b x 8b after all. 134 const bit_t split = 135 (bit_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8); 136 const int bit = VP8BitUpdate(br, split); 137 if (br->range_ <= (((bit_t)0x7e << (BITS)) | (MASK))) { 138 VP8Shift(br); 139 } 140 return bit; 141 } 142 143 static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) { 144 const bit_t split = (br->range_ >> 1); 145 const int bit = VP8BitUpdate(br, split); 146 VP8Shift(br); 147 return bit ? -v : v; 148 } 149 150 151 // ----------------------------------------------------------------------------- 152 // Bitreader 153 154 typedef struct { 155 uint64_t val_; 156 const uint8_t* buf_; 157 size_t len_; 158 size_t pos_; 159 int bit_pos_; 160 int eos_; 161 int error_; 162 } VP8LBitReader; 163 164 void VP8LInitBitReader(VP8LBitReader* const br, 165 const uint8_t* const start, 166 size_t length); 167 168 // Sets a new data buffer. 169 void VP8LBitReaderSetBuffer(VP8LBitReader* const br, 170 const uint8_t* const buffer, size_t length); 171 172 // Reads the specified number of bits from Read Buffer. 173 // Flags an error in case end_of_stream or n_bits is more than allowed limit. 174 // Flags eos if this read attempt is going to cross the read buffer. 175 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits); 176 177 // Reads one bit from Read Buffer. Flags an error in case end_of_stream. 178 // Flags eos after reading last bit from the buffer. 179 uint32_t VP8LReadOneBit(VP8LBitReader* const br); 180 181 // VP8LReadOneBitUnsafe is faster than VP8LReadOneBit, but it can be called only 182 // 32 times after the last VP8LFillBitWindow. Any subsequent calls 183 // (without VP8LFillBitWindow) will return invalid data. 184 static WEBP_INLINE uint32_t VP8LReadOneBitUnsafe(VP8LBitReader* const br) { 185 const uint32_t val = (br->val_ >> br->bit_pos_) & 1; 186 ++br->bit_pos_; 187 return val; 188 } 189 190 // Advances the Read buffer by 4 bytes to make room for reading next 32 bits. 191 void VP8LFillBitWindow(VP8LBitReader* const br); 192 193 #if defined(__cplusplus) || defined(c_plusplus) 194 } // extern "C" 195 #endif 196 197 #endif /* WEBP_UTILS_BIT_READER_H_ */ 198
