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#define BITS 32     // can be 32, 16 or 8
28#define MASK ((((bit_t)1) << (BITS)) - 1)
29#if (BITS == 32)
30typedef uint64_t bit_t;   // natural register type
31typedef uint32_t lbit_t;  // natural type for memory I/O
32#elif (BITS == 16)
33typedef uint32_t bit_t;
34typedef uint16_t lbit_t;
35#else
36typedef uint32_t bit_t;
37typedef uint8_t lbit_t;
38#endif
39
40//------------------------------------------------------------------------------
41// Bitreader and code-tree reader
42
43typedef struct VP8BitReader VP8BitReader;
44struct 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.
56void 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
60uint32_t VP8GetValue(VP8BitReader* const br, int num_bits);
61static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) {
62  return VP8GetValue(br, 1);
63}
64
65// return the next value with sign-extension.
66int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits);
67
68// Read a bit with proba 'prob'. Speed-critical function!
69extern const uint8_t kVP8Log2Range[128];
70extern const bit_t kVP8NewRange[128];
71
72void VP8LoadFinalBytes(VP8BitReader* const br);    // special case for the tail
73
74static 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
107static 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
122static 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
131static 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
143static 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
154typedef 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
164void VP8LInitBitReader(VP8LBitReader* const br,
165                       const uint8_t* const start,
166                       size_t length);
167
168//  Sets a new data buffer.
169void 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.
175uint32_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.
179uint32_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.
184static 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.
191void 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