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