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
VP8BitReaderSetBuffer(VP8BitReader * const br,const uint8_t * const start,size_t size)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
VP8InitBitReader(VP8BitReader * const br,const uint8_t * const start,size_t size)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
VP8RemapBitReader(VP8BitReader * const br,ptrdiff_t offset)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
VP8LoadFinalBytes(VP8BitReader * const br)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
VP8GetValue(VP8BitReader * const br,int bits,const char label[])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
VP8GetSignedValue(VP8BitReader * const br,int bits,const char label[])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 defined(__wasm__)
129 #define VP8L_USE_FAST_LOAD
130 #endif
131
132 static const uint32_t kBitMask[VP8L_MAX_NUM_BIT_READ + 1] = {
133 0,
134 0x000001, 0x000003, 0x000007, 0x00000f,
135 0x00001f, 0x00003f, 0x00007f, 0x0000ff,
136 0x0001ff, 0x0003ff, 0x0007ff, 0x000fff,
137 0x001fff, 0x003fff, 0x007fff, 0x00ffff,
138 0x01ffff, 0x03ffff, 0x07ffff, 0x0fffff,
139 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff
140 };
141
VP8LInitBitReader(VP8LBitReader * const br,const uint8_t * const start,size_t length)142 void VP8LInitBitReader(VP8LBitReader* const br, const uint8_t* const start,
143 size_t length) {
144 size_t i;
145 vp8l_val_t value = 0;
146 assert(br != NULL);
147 assert(start != NULL);
148 assert(length < 0xfffffff8u); // can't happen with a RIFF chunk.
149
150 br->len_ = length;
151 br->val_ = 0;
152 br->bit_pos_ = 0;
153 br->eos_ = 0;
154
155 if (length > sizeof(br->val_)) {
156 length = sizeof(br->val_);
157 }
158 for (i = 0; i < length; ++i) {
159 value |= (vp8l_val_t)start[i] << (8 * i);
160 }
161 br->val_ = value;
162 br->pos_ = length;
163 br->buf_ = start;
164 }
165
VP8LBitReaderSetBuffer(VP8LBitReader * const br,const uint8_t * const buf,size_t len)166 void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
167 const uint8_t* const buf, size_t len) {
168 assert(br != NULL);
169 assert(buf != NULL);
170 assert(len < 0xfffffff8u); // can't happen with a RIFF chunk.
171 br->buf_ = buf;
172 br->len_ = len;
173 // pos_ > len_ should be considered a param error.
174 br->eos_ = (br->pos_ > br->len_) || VP8LIsEndOfStream(br);
175 }
176
VP8LSetEndOfStream(VP8LBitReader * const br)177 static void VP8LSetEndOfStream(VP8LBitReader* const br) {
178 br->eos_ = 1;
179 br->bit_pos_ = 0; // To avoid undefined behaviour with shifts.
180 }
181
182 // If not at EOS, reload up to VP8L_LBITS byte-by-byte
ShiftBytes(VP8LBitReader * const br)183 static void ShiftBytes(VP8LBitReader* const br) {
184 while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
185 br->val_ >>= 8;
186 br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (VP8L_LBITS - 8);
187 ++br->pos_;
188 br->bit_pos_ -= 8;
189 }
190 if (VP8LIsEndOfStream(br)) {
191 VP8LSetEndOfStream(br);
192 }
193 }
194
VP8LDoFillBitWindow(VP8LBitReader * const br)195 void VP8LDoFillBitWindow(VP8LBitReader* const br) {
196 assert(br->bit_pos_ >= VP8L_WBITS);
197 #if defined(VP8L_USE_FAST_LOAD)
198 if (br->pos_ + sizeof(br->val_) < br->len_) {
199 br->val_ >>= VP8L_WBITS;
200 br->bit_pos_ -= VP8L_WBITS;
201 br->val_ |= (vp8l_val_t)HToLE32(WebPMemToUint32(br->buf_ + br->pos_)) <<
202 (VP8L_LBITS - VP8L_WBITS);
203 br->pos_ += VP8L_LOG8_WBITS;
204 return;
205 }
206 #endif
207 ShiftBytes(br); // Slow path.
208 }
209
VP8LReadBits(VP8LBitReader * const br,int n_bits)210 uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) {
211 assert(n_bits >= 0);
212 // Flag an error if end_of_stream or n_bits is more than allowed limit.
213 if (!br->eos_ && n_bits <= VP8L_MAX_NUM_BIT_READ) {
214 const uint32_t val = VP8LPrefetchBits(br) & kBitMask[n_bits];
215 const int new_bits = br->bit_pos_ + n_bits;
216 br->bit_pos_ = new_bits;
217 ShiftBytes(br);
218 return val;
219 } else {
220 VP8LSetEndOfStream(br);
221 return 0;
222 }
223 }
224
225 //------------------------------------------------------------------------------
226 // Bit-tracing tool
227
228 #if (BITTRACE > 0)
229
230 #include <stdlib.h> // for atexit()
231 #include <stdio.h>
232 #include <string.h>
233
234 #define MAX_NUM_LABELS 32
235 static struct {
236 const char* label;
237 int size;
238 int count;
239 } kLabels[MAX_NUM_LABELS];
240
241 static int last_label = 0;
242 static int last_pos = 0;
243 static const uint8_t* buf_start = NULL;
244 static int init_done = 0;
245
PrintBitTraces(void)246 static void PrintBitTraces(void) {
247 int i;
248 int scale = 1;
249 int total = 0;
250 const char* units = "bits";
251 #if (BITTRACE == 2)
252 scale = 8;
253 units = "bytes";
254 #endif
255 for (i = 0; i < last_label; ++i) total += kLabels[i].size;
256 if (total < 1) total = 1; // avoid rounding errors
257 printf("=== Bit traces ===\n");
258 for (i = 0; i < last_label; ++i) {
259 const int skip = 16 - (int)strlen(kLabels[i].label);
260 const int value = (kLabels[i].size + scale - 1) / scale;
261 assert(skip > 0);
262 printf("%s \%*s: %6d %s \t[%5.2f%%] [count: %7d]\n",
263 kLabels[i].label, skip, "", value, units,
264 100.f * kLabels[i].size / total,
265 kLabels[i].count);
266 }
267 total = (total + scale - 1) / scale;
268 printf("Total: %d %s\n", total, units);
269 }
270
BitTrace(const struct VP8BitReader * const br,const char label[])271 void BitTrace(const struct VP8BitReader* const br, const char label[]) {
272 int i, pos;
273 if (!init_done) {
274 memset(kLabels, 0, sizeof(kLabels));
275 atexit(PrintBitTraces);
276 buf_start = br->buf_;
277 init_done = 1;
278 }
279 pos = (int)(br->buf_ - buf_start) * 8 - br->bits_;
280 // if there's a too large jump, we've changed partition -> reset counter
281 if (abs(pos - last_pos) > 32) {
282 buf_start = br->buf_;
283 pos = 0;
284 last_pos = 0;
285 }
286 if (br->range_ >= 0x7f) pos += kVP8Log2Range[br->range_ - 0x7f];
287 for (i = 0; i < last_label; ++i) {
288 if (!strcmp(label, kLabels[i].label)) break;
289 }
290 if (i == MAX_NUM_LABELS) abort(); // overflow!
291 kLabels[i].label = label;
292 kLabels[i].size += pos - last_pos;
293 kLabels[i].count += 1;
294 if (i == last_label) ++last_label;
295 last_pos = pos;
296 }
297
298 #endif // BITTRACE > 0
299
300 //------------------------------------------------------------------------------
301