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