1 // Copyright 2011 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 // Bit writing and boolean coder
11 //
12 // Author: Skal (pascal.massimino@gmail.com)
13 // Vikas Arora (vikaas.arora@gmail.com)
14
15 #include <assert.h>
16 #include <string.h> // for memcpy()
17 #include <stdlib.h>
18
19 #include "src/utils/bit_writer_utils.h"
20 #include "src/utils/endian_inl_utils.h"
21 #include "src/utils/utils.h"
22
23 //------------------------------------------------------------------------------
24 // VP8BitWriter
25
BitWriterResize(VP8BitWriter * const bw,size_t extra_size)26 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
27 uint8_t* new_buf;
28 size_t new_size;
29 const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
30 const size_t needed_size = (size_t)needed_size_64b;
31 if (needed_size_64b != needed_size) {
32 bw->error_ = 1;
33 return 0;
34 }
35 if (needed_size <= bw->max_pos_) return 1;
36 // If the following line wraps over 32bit, the test just after will catch it.
37 new_size = 2 * bw->max_pos_;
38 if (new_size < needed_size) new_size = needed_size;
39 if (new_size < 1024) new_size = 1024;
40 new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size);
41 if (new_buf == NULL) {
42 bw->error_ = 1;
43 return 0;
44 }
45 if (bw->pos_ > 0) {
46 assert(bw->buf_ != NULL);
47 memcpy(new_buf, bw->buf_, bw->pos_);
48 }
49 WebPSafeFree(bw->buf_);
50 bw->buf_ = new_buf;
51 bw->max_pos_ = new_size;
52 return 1;
53 }
54
Flush(VP8BitWriter * const bw)55 static void Flush(VP8BitWriter* const bw) {
56 const int s = 8 + bw->nb_bits_;
57 const int32_t bits = bw->value_ >> s;
58 assert(bw->nb_bits_ >= 0);
59 bw->value_ -= bits << s;
60 bw->nb_bits_ -= 8;
61 if ((bits & 0xff) != 0xff) {
62 size_t pos = bw->pos_;
63 if (!BitWriterResize(bw, bw->run_ + 1)) {
64 return;
65 }
66 if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's
67 if (pos > 0) bw->buf_[pos - 1]++;
68 }
69 if (bw->run_ > 0) {
70 const int value = (bits & 0x100) ? 0x00 : 0xff;
71 for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
72 }
73 bw->buf_[pos++] = bits & 0xff;
74 bw->pos_ = pos;
75 } else {
76 bw->run_++; // delay writing of bytes 0xff, pending eventual carry.
77 }
78 }
79
80 //------------------------------------------------------------------------------
81 // renormalization
82
83 static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i)
84 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
85 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
86 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
87 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
88 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
89 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
90 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
91 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
92 0
93 };
94
95 // range = ((range + 1) << kVP8Log2Range[range]) - 1
96 static const uint8_t kNewRange[128] = {
97 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
98 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
99 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
100 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
101 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
102 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
103 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
104 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
105 241, 243, 245, 247, 249, 251, 253, 127
106 };
107
VP8PutBit(VP8BitWriter * const bw,int bit,int prob)108 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
109 const int split = (bw->range_ * prob) >> 8;
110 if (bit) {
111 bw->value_ += split + 1;
112 bw->range_ -= split + 1;
113 } else {
114 bw->range_ = split;
115 }
116 if (bw->range_ < 127) { // emit 'shift' bits out and renormalize
117 const int shift = kNorm[bw->range_];
118 bw->range_ = kNewRange[bw->range_];
119 bw->value_ <<= shift;
120 bw->nb_bits_ += shift;
121 if (bw->nb_bits_ > 0) Flush(bw);
122 }
123 return bit;
124 }
125
VP8PutBitUniform(VP8BitWriter * const bw,int bit)126 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
127 const int split = bw->range_ >> 1;
128 if (bit) {
129 bw->value_ += split + 1;
130 bw->range_ -= split + 1;
131 } else {
132 bw->range_ = split;
133 }
134 if (bw->range_ < 127) {
135 bw->range_ = kNewRange[bw->range_];
136 bw->value_ <<= 1;
137 bw->nb_bits_ += 1;
138 if (bw->nb_bits_ > 0) Flush(bw);
139 }
140 return bit;
141 }
142
VP8PutBits(VP8BitWriter * const bw,uint32_t value,int nb_bits)143 void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) {
144 uint32_t mask;
145 assert(nb_bits > 0 && nb_bits < 32);
146 for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) {
147 VP8PutBitUniform(bw, value & mask);
148 }
149 }
150
VP8PutSignedBits(VP8BitWriter * const bw,int value,int nb_bits)151 void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) {
152 if (!VP8PutBitUniform(bw, value != 0)) return;
153 if (value < 0) {
154 VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1);
155 } else {
156 VP8PutBits(bw, value << 1, nb_bits + 1);
157 }
158 }
159
160 //------------------------------------------------------------------------------
161
VP8BitWriterInit(VP8BitWriter * const bw,size_t expected_size)162 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
163 bw->range_ = 255 - 1;
164 bw->value_ = 0;
165 bw->run_ = 0;
166 bw->nb_bits_ = -8;
167 bw->pos_ = 0;
168 bw->max_pos_ = 0;
169 bw->error_ = 0;
170 bw->buf_ = NULL;
171 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
172 }
173
VP8BitWriterFinish(VP8BitWriter * const bw)174 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
175 VP8PutBits(bw, 0, 9 - bw->nb_bits_);
176 bw->nb_bits_ = 0; // pad with zeroes
177 Flush(bw);
178 return bw->buf_;
179 }
180
VP8BitWriterAppend(VP8BitWriter * const bw,const uint8_t * data,size_t size)181 int VP8BitWriterAppend(VP8BitWriter* const bw,
182 const uint8_t* data, size_t size) {
183 assert(data != NULL);
184 if (bw->nb_bits_ != -8) return 0; // Flush() must have been called
185 if (!BitWriterResize(bw, size)) return 0;
186 memcpy(bw->buf_ + bw->pos_, data, size);
187 bw->pos_ += size;
188 return 1;
189 }
190
VP8BitWriterWipeOut(VP8BitWriter * const bw)191 void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
192 if (bw != NULL) {
193 WebPSafeFree(bw->buf_);
194 memset(bw, 0, sizeof(*bw));
195 }
196 }
197
198 //------------------------------------------------------------------------------
199 // VP8LBitWriter
200
201 // This is the minimum amount of size the memory buffer is guaranteed to grow
202 // when extra space is needed.
203 #define MIN_EXTRA_SIZE (32768ULL)
204
205 // Returns 1 on success.
VP8LBitWriterResize(VP8LBitWriter * const bw,size_t extra_size)206 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
207 uint8_t* allocated_buf;
208 size_t allocated_size;
209 const size_t max_bytes = bw->end_ - bw->buf_;
210 const size_t current_size = bw->cur_ - bw->buf_;
211 const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
212 const size_t size_required = (size_t)size_required_64b;
213 if (size_required != size_required_64b) {
214 bw->error_ = 1;
215 return 0;
216 }
217 if (max_bytes > 0 && size_required <= max_bytes) return 1;
218 allocated_size = (3 * max_bytes) >> 1;
219 if (allocated_size < size_required) allocated_size = size_required;
220 // make allocated size multiple of 1k
221 allocated_size = (((allocated_size >> 10) + 1) << 10);
222 allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
223 if (allocated_buf == NULL) {
224 bw->error_ = 1;
225 return 0;
226 }
227 if (current_size > 0) {
228 memcpy(allocated_buf, bw->buf_, current_size);
229 }
230 WebPSafeFree(bw->buf_);
231 bw->buf_ = allocated_buf;
232 bw->cur_ = bw->buf_ + current_size;
233 bw->end_ = bw->buf_ + allocated_size;
234 return 1;
235 }
236
VP8LBitWriterInit(VP8LBitWriter * const bw,size_t expected_size)237 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
238 memset(bw, 0, sizeof(*bw));
239 return VP8LBitWriterResize(bw, expected_size);
240 }
241
VP8LBitWriterClone(const VP8LBitWriter * const src,VP8LBitWriter * const dst)242 int VP8LBitWriterClone(const VP8LBitWriter* const src,
243 VP8LBitWriter* const dst) {
244 const size_t current_size = src->cur_ - src->buf_;
245 assert(src->cur_ >= src->buf_ && src->cur_ <= src->end_);
246 if (!VP8LBitWriterResize(dst, current_size)) return 0;
247 memcpy(dst->buf_, src->buf_, current_size);
248 dst->bits_ = src->bits_;
249 dst->used_ = src->used_;
250 dst->error_ = src->error_;
251 dst->cur_ = dst->buf_ + current_size;
252 return 1;
253 }
254
VP8LBitWriterWipeOut(VP8LBitWriter * const bw)255 void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
256 if (bw != NULL) {
257 WebPSafeFree(bw->buf_);
258 memset(bw, 0, sizeof(*bw));
259 }
260 }
261
VP8LBitWriterReset(const VP8LBitWriter * const bw_init,VP8LBitWriter * const bw)262 void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
263 VP8LBitWriter* const bw) {
264 bw->bits_ = bw_init->bits_;
265 bw->used_ = bw_init->used_;
266 bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_);
267 assert(bw->cur_ <= bw->end_);
268 bw->error_ = bw_init->error_;
269 }
270
VP8LBitWriterSwap(VP8LBitWriter * const src,VP8LBitWriter * const dst)271 void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
272 const VP8LBitWriter tmp = *src;
273 *src = *dst;
274 *dst = tmp;
275 }
276
VP8LPutBitsFlushBits(VP8LBitWriter * const bw)277 void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) {
278 // If needed, make some room by flushing some bits out.
279 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
280 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
281 if (!CheckSizeOverflow(extra_size) ||
282 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
283 bw->cur_ = bw->buf_;
284 bw->error_ = 1;
285 return;
286 }
287 }
288 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_);
289 bw->cur_ += VP8L_WRITER_BYTES;
290 bw->bits_ >>= VP8L_WRITER_BITS;
291 bw->used_ -= VP8L_WRITER_BITS;
292 }
293
VP8LPutBitsInternal(VP8LBitWriter * const bw,uint32_t bits,int n_bits)294 void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) {
295 assert(n_bits <= 32);
296 // That's the max we can handle:
297 assert(sizeof(vp8l_wtype_t) == 2);
298 if (n_bits > 0) {
299 vp8l_atype_t lbits = bw->bits_;
300 int used = bw->used_;
301 // Special case of overflow handling for 32bit accumulator (2-steps flush).
302 #if VP8L_WRITER_BITS == 16
303 if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
304 // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
305 const int shift = VP8L_WRITER_MAX_BITS - used;
306 lbits |= (vp8l_atype_t)bits << used;
307 used = VP8L_WRITER_MAX_BITS;
308 n_bits -= shift;
309 bits >>= shift;
310 assert(n_bits <= VP8L_WRITER_MAX_BITS);
311 }
312 #endif
313 // If needed, make some room by flushing some bits out.
314 while (used >= VP8L_WRITER_BITS) {
315 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
316 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
317 if (!CheckSizeOverflow(extra_size) ||
318 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
319 bw->cur_ = bw->buf_;
320 bw->error_ = 1;
321 return;
322 }
323 }
324 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
325 bw->cur_ += VP8L_WRITER_BYTES;
326 lbits >>= VP8L_WRITER_BITS;
327 used -= VP8L_WRITER_BITS;
328 }
329 bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
330 bw->used_ = used + n_bits;
331 }
332 }
333
VP8LBitWriterFinish(VP8LBitWriter * const bw)334 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
335 // flush leftover bits
336 if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
337 while (bw->used_ > 0) {
338 *bw->cur_++ = (uint8_t)bw->bits_;
339 bw->bits_ >>= 8;
340 bw->used_ -= 8;
341 }
342 bw->used_ = 0;
343 }
344 return bw->buf_;
345 }
346
347 //------------------------------------------------------------------------------
348