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 non-inlined methods |
11 | // |
12 | // Author: Skal (pascal.massimino@gmail.com) |
13 | |
14 | #ifdef HAVE_CONFIG_H |
15 | #include "src/webp/config.h" |
16 | #endif |
17 | |
18 | #include "src/dsp/cpu.h" |
19 | #include "src/utils/bit_reader_inl_utils.h" |
20 | #include "src/utils/utils.h" |
21 | |
22 | //------------------------------------------------------------------------------ |
23 | // VP8BitReader |
24 | |
25 | void VP8BitReaderSetBuffer(VP8BitReader* const br, |
26 | const uint8_t* const start, |
27 | size_t size) { |
28 | br->buf_ = start; |
29 | br->buf_end_ = start + size; |
30 | br->buf_max_ = |
31 | (size >= sizeof(lbit_t)) ? start + size - sizeof(lbit_t) + 1 |
32 | : start; |
33 | } |
34 | |
35 | void VP8InitBitReader(VP8BitReader* const br, |
36 | const uint8_t* const start, size_t size) { |
37 | assert(br != NULL); |
38 | assert(start != NULL); |
39 | assert(size < (1u << 31)); // limit ensured by format and upstream checks |
40 | br->range_ = 255 - 1; |
41 | br->value_ = 0; |
42 | br->bits_ = -8; // to load the very first 8bits |
43 | br->eof_ = 0; |
44 | VP8BitReaderSetBuffer(br, start, size); |
45 | VP8LoadNewBytes(br); |
46 | } |
47 | |
48 | void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset) { |
49 | if (br->buf_ != NULL) { |
50 | br->buf_ += offset; |
51 | br->buf_end_ += offset; |
52 | br->buf_max_ += offset; |
53 | } |
54 | } |
55 | |
56 | const uint8_t kVP8Log2Range[128] = { |
57 | 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, |
58 | 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, |
59 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, |
60 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, |
61 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
62 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
63 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
64 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
65 | 0 |
66 | }; |
67 | |
68 | // range = ((range - 1) << kVP8Log2Range[range]) + 1 |
69 | const uint8_t kVP8NewRange[128] = { |
70 | 127, 127, 191, 127, 159, 191, 223, 127, |
71 | 143, 159, 175, 191, 207, 223, 239, 127, |
72 | 135, 143, 151, 159, 167, 175, 183, 191, |
73 | 199, 207, 215, 223, 231, 239, 247, 127, |
74 | 131, 135, 139, 143, 147, 151, 155, 159, |
75 | 163, 167, 171, 175, 179, 183, 187, 191, |
76 | 195, 199, 203, 207, 211, 215, 219, 223, |
77 | 227, 231, 235, 239, 243, 247, 251, 127, |
78 | 129, 131, 133, 135, 137, 139, 141, 143, |
79 | 145, 147, 149, 151, 153, 155, 157, 159, |
80 | 161, 163, 165, 167, 169, 171, 173, 175, |
81 | 177, 179, 181, 183, 185, 187, 189, 191, |
82 | 193, 195, 197, 199, 201, 203, 205, 207, |
83 | 209, 211, 213, 215, 217, 219, 221, 223, |
84 | 225, 227, 229, 231, 233, 235, 237, 239, |
85 | 241, 243, 245, 247, 249, 251, 253, 127 |
86 | }; |
87 | |
88 | void VP8LoadFinalBytes(VP8BitReader* const br) { |
89 | assert(br != NULL && br->buf_ != NULL); |
90 | // Only read 8bits at a time |
91 | if (br->buf_ < br->buf_end_) { |
92 | br->bits_ += 8; |
93 | br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8); |
94 | } else if (!br->eof_) { |
95 | br->value_ <<= 8; |
96 | br->bits_ += 8; |
97 | br->eof_ = 1; |
98 | } else { |
99 | br->bits_ = 0; // This is to avoid undefined behaviour with shifts. |
100 | } |
101 | } |
102 | |
103 | //------------------------------------------------------------------------------ |
104 | // Higher-level calls |
105 | |
106 | uint32_t VP8GetValue(VP8BitReader* const br, int bits, const char label[]) { |
107 | uint32_t v = 0; |
108 | while (bits-- > 0) { |
109 | v |= VP8GetBit(br, 0x80, label) << bits; |
110 | } |
111 | return v; |
112 | } |
113 | |
114 | int32_t VP8GetSignedValue(VP8BitReader* const br, int bits, |
115 | const char label[]) { |
116 | const int value = VP8GetValue(br, bits, label); |
117 | return VP8Get(br, label) ? -value : value; |
118 | } |
119 | |
120 | //------------------------------------------------------------------------------ |
121 | // VP8LBitReader |
122 | |
123 | #define VP8L_LOG8_WBITS 4 // Number of bytes needed to store VP8L_WBITS bits. |
124 | |
125 | #if defined(__arm__) || defined(_M_ARM) || WEBP_AARCH64 || \ |
126 | defined(__i386__) || defined(_M_IX86) || \ |
127 | defined(__x86_64__) || defined(_M_X64) |
128 | #define VP8L_USE_FAST_LOAD |
129 | #endif |
130 | |
131 | static const uint32_t kBitMask[VP8L_MAX_NUM_BIT_READ + 1] = { |
132 | 0, |
133 | 0x000001, 0x000003, 0x000007, 0x00000f, |
134 | 0x00001f, 0x00003f, 0x00007f, 0x0000ff, |
135 | 0x0001ff, 0x0003ff, 0x0007ff, 0x000fff, |
136 | 0x001fff, 0x003fff, 0x007fff, 0x00ffff, |
137 | 0x01ffff, 0x03ffff, 0x07ffff, 0x0fffff, |
138 | 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff |
139 | }; |
140 | |
141 | void VP8LInitBitReader(VP8LBitReader* const br, const uint8_t* const start, |
142 | size_t length) { |
143 | size_t i; |
144 | vp8l_val_t value = 0; |
145 | assert(br != NULL); |
146 | assert(start != NULL); |
147 | assert(length < 0xfffffff8u); // can't happen with a RIFF chunk. |
148 | |
149 | br->len_ = length; |
150 | br->val_ = 0; |
151 | br->bit_pos_ = 0; |
152 | br->eos_ = 0; |
153 | |
154 | if (length > sizeof(br->val_)) { |
155 | length = sizeof(br->val_); |
156 | } |
157 | for (i = 0; i < length; ++i) { |
158 | value |= (vp8l_val_t)start[i] << (8 * i); |
159 | } |
160 | br->val_ = value; |
161 | br->pos_ = length; |
162 | br->buf_ = start; |
163 | } |
164 | |
165 | void VP8LBitReaderSetBuffer(VP8LBitReader* const br, |
166 | const uint8_t* const buf, size_t len) { |
167 | assert(br != NULL); |
168 | assert(buf != NULL); |
169 | assert(len < 0xfffffff8u); // can't happen with a RIFF chunk. |
170 | br->buf_ = buf; |
171 | br->len_ = len; |
172 | // pos_ > len_ should be considered a param error. |
173 | br->eos_ = (br->pos_ > br->len_) || VP8LIsEndOfStream(br); |
174 | } |
175 | |
176 | static void VP8LSetEndOfStream(VP8LBitReader* const br) { |
177 | br->eos_ = 1; |
178 | br->bit_pos_ = 0; // To avoid undefined behaviour with shifts. |
179 | } |
180 | |
181 | // If not at EOS, reload up to VP8L_LBITS byte-by-byte |
182 | static void ShiftBytes(VP8LBitReader* const br) { |
183 | while (br->bit_pos_ >= 8 && br->pos_ < br->len_) { |
184 | br->val_ >>= 8; |
185 | br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (VP8L_LBITS - 8); |
186 | ++br->pos_; |
187 | br->bit_pos_ -= 8; |
188 | } |
189 | if (VP8LIsEndOfStream(br)) { |
190 | VP8LSetEndOfStream(br); |
191 | } |
192 | } |
193 | |
194 | void VP8LDoFillBitWindow(VP8LBitReader* const br) { |
195 | assert(br->bit_pos_ >= VP8L_WBITS); |
196 | #if defined(VP8L_USE_FAST_LOAD) |
197 | if (br->pos_ + sizeof(br->val_) < br->len_) { |
198 | br->val_ >>= VP8L_WBITS; |
199 | br->bit_pos_ -= VP8L_WBITS; |
200 | br->val_ |= (vp8l_val_t)HToLE32(WebPMemToUint32(br->buf_ + br->pos_)) << |
201 | (VP8L_LBITS - VP8L_WBITS); |
202 | br->pos_ += VP8L_LOG8_WBITS; |
203 | return; |
204 | } |
205 | #endif |
206 | ShiftBytes(br); // Slow path. |
207 | } |
208 | |
209 | uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) { |
210 | assert(n_bits >= 0); |
211 | // Flag an error if end_of_stream or n_bits is more than allowed limit. |
212 | if (!br->eos_ && n_bits <= VP8L_MAX_NUM_BIT_READ) { |
213 | const uint32_t val = VP8LPrefetchBits(br) & kBitMask[n_bits]; |
214 | const int new_bits = br->bit_pos_ + n_bits; |
215 | br->bit_pos_ = new_bits; |
216 | ShiftBytes(br); |
217 | return val; |
218 | } else { |
219 | VP8LSetEndOfStream(br); |
220 | return 0; |
221 | } |
222 | } |
223 | |
224 | //------------------------------------------------------------------------------ |
225 | // Bit-tracing tool |
226 | |
227 | #if (BITTRACE > 0) |
228 | |
229 | #include <stdlib.h> // for atexit() |
230 | #include <stdio.h> |
231 | #include <string.h> |
232 | |
233 | #define MAX_NUM_LABELS 32 |
234 | static struct { |
235 | const char* label; |
236 | int size; |
237 | int count; |
238 | } kLabels[MAX_NUM_LABELS]; |
239 | |
240 | static int last_label = 0; |
241 | static int last_pos = 0; |
242 | static const uint8_t* buf_start = NULL; |
243 | static int init_done = 0; |
244 | |
245 | static void PrintBitTraces(void) { |
246 | int i; |
247 | int scale = 1; |
248 | int total = 0; |
249 | const char* units = "bits" ; |
250 | #if (BITTRACE == 2) |
251 | scale = 8; |
252 | units = "bytes" ; |
253 | #endif |
254 | for (i = 0; i < last_label; ++i) total += kLabels[i].size; |
255 | if (total < 1) total = 1; // avoid rounding errors |
256 | printf("=== Bit traces ===\n" ); |
257 | for (i = 0; i < last_label; ++i) { |
258 | const int skip = 16 - (int)strlen(kLabels[i].label); |
259 | const int value = (kLabels[i].size + scale - 1) / scale; |
260 | assert(skip > 0); |
261 | printf("%s \%*s: %6d %s \t[%5.2f%%] [count: %7d]\n" , |
262 | kLabels[i].label, skip, "" , value, units, |
263 | 100.f * kLabels[i].size / total, |
264 | kLabels[i].count); |
265 | } |
266 | total = (total + scale - 1) / scale; |
267 | printf("Total: %d %s\n" , total, units); |
268 | } |
269 | |
270 | void BitTrace(const struct VP8BitReader* const br, const char label[]) { |
271 | int i, pos; |
272 | if (!init_done) { |
273 | memset(kLabels, 0, sizeof(kLabels)); |
274 | atexit(PrintBitTraces); |
275 | buf_start = br->buf_; |
276 | init_done = 1; |
277 | } |
278 | pos = (int)(br->buf_ - buf_start) * 8 - br->bits_; |
279 | // if there's a too large jump, we've changed partition -> reset counter |
280 | if (abs(pos - last_pos) > 32) { |
281 | buf_start = br->buf_; |
282 | pos = 0; |
283 | last_pos = 0; |
284 | } |
285 | if (br->range_ >= 0x7f) pos += kVP8Log2Range[br->range_ - 0x7f]; |
286 | for (i = 0; i < last_label; ++i) { |
287 | if (!strcmp(label, kLabels[i].label)) break; |
288 | } |
289 | if (i == MAX_NUM_LABELS) abort(); // overflow! |
290 | kLabels[i].label = label; |
291 | kLabels[i].size += pos - last_pos; |
292 | kLabels[i].count += 1; |
293 | if (i == last_label) ++last_label; |
294 | last_pos = pos; |
295 | } |
296 | |
297 | #endif // BITTRACE > 0 |
298 | |
299 | //------------------------------------------------------------------------------ |
300 | |