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 ([email protected])
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 #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
VP8LInitBitReader(VP8LBitReader * const br,const uint8_t * const start,size_t length)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
VP8LBitReaderSetBuffer(VP8LBitReader * const br,const uint8_t * const buf,size_t len)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
VP8LSetEndOfStream(VP8LBitReader * const br)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
ShiftBytes(VP8LBitReader * const br)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
VP8LDoFillBitWindow(VP8LBitReader * const br)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
VP8LReadBits(VP8LBitReader * const br,int n_bits)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
PrintBitTraces(void)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
BitTrace(const struct VP8BitReader * const br,const char label[])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