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)
24extern "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)
88typedef uint64_t bit_t;   // natural register type
89typedef uint32_t lbit_t;  // natural type for memory I/O
90#elif (BITS == 24)
91typedef uint32_t bit_t;
92typedef uint32_t lbit_t;
93#elif (BITS == 16)
94typedef uint32_t bit_t;
95typedef uint16_t lbit_t;
96#else
97typedef uint32_t bit_t;
98typedef uint8_t lbit_t;
99#endif
100
101#ifndef USE_RIGHT_JUSTIFY
102typedef bit_t range_t;     // type for storing range_
103#define MASK ((((bit_t)1) << (BITS)) - 1)
104#else
105typedef uint32_t range_t;  // range_ only uses 8bits here. No need for bit_t.
106#endif
107
108//------------------------------------------------------------------------------
109// Bitreader
110
111typedef struct VP8BitReader VP8BitReader;
112struct 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.
124void 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
128uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
129static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
130  return VP8GetValue(br, 1);
131}
132
133// return the next value with sign-extension.
134int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
135
136// Read a bit with proba 'prob'. Speed-critical function!
137extern const uint8_t kVP8Log2Range[128];
138extern const range_t kVP8NewRange[128];
139
140void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
141
142static 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
184static 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
214static 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}
229static 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
250static 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
261typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
262
263typedef 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
273void VP8LInitBitReader(VP8LBitReader* const br,
274                       const uint8_t* const start,
275                       size_t length);
276
277//  Sets a new data buffer.
278void 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.
284uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
285
286// Return the prefetched bits, so they can be looked up.
287static 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.
292static 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.
297void 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