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