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@gmail.com)
11 // Vikas Arora (vikaas.arora@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);
VP8Get(VP8BitReader * const br)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
VP8LoadNewBytes(VP8BitReader * const br)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
VP8BitUpdate(VP8BitReader * const br,range_t split)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
VP8Shift(VP8BitReader * const br)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 }
VP8GetBit(VP8BitReader * const br,int prob)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
VP8GetSigned(VP8BitReader * const br,int v)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.
VP8LPrefetchBits(VP8LBitReader * const br)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.
VP8LDiscardBits(VP8LBitReader * const br,int num_bits)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