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)
26extern "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)
95typedef uint64_t bit_t;
96typedef uint64_t lbit_t;
97#elif (BITS == 32)
98typedef uint64_t bit_t;
99typedef uint32_t lbit_t;
100#elif (BITS == 24)
101typedef uint32_t bit_t;
102typedef uint32_t lbit_t;
103#elif (BITS == 16)
104typedef uint32_t bit_t;
105typedef uint16_t lbit_t;
106#else
107typedef uint32_t bit_t;
108typedef uint8_t lbit_t;
109#endif
110
111#ifndef USE_RIGHT_JUSTIFY
112typedef bit_t range_t;     // type for storing range_
113#define MASK ((((bit_t)1) << (BITS)) - 1)
114#else
115typedef uint32_t range_t;  // range_ only uses 8bits here. No need for bit_t.
116#endif
117
118//------------------------------------------------------------------------------
119// Bitreader
120
121typedef struct VP8BitReader VP8BitReader;
122struct 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.
134void 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
138uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
139static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
140  return VP8GetValue(br, 1);
141}
142
143// return the next value with sign-extension.
144int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
145
146// Read a bit with proba 'prob'. Speed-critical function!
147extern const uint8_t kVP8Log2Range[128];
148extern const range_t kVP8NewRange[128];
149
150void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
151
152static 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
212static 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
242static 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}
257static 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
278static 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
289typedef uint64_t vp8l_val_t;  // right now, this bit-reader can only use 64bit.
290
291typedef 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
301void VP8LInitBitReader(VP8LBitReader* const br,
302                       const uint8_t* const start,
303                       size_t length);
304
305//  Sets a new data buffer.
306void 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.
312uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits);
313
314// Return the prefetched bits, so they can be looked up.
315static 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.
320static 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.
325void 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