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;
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 return 1;
252 }
253
VP8LBitWriterWipeOut(VP8LBitWriter * const bw)254 void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
255 if (bw != NULL) {
256 WebPSafeFree(bw->buf_);
257 memset(bw, 0, sizeof(*bw));
258 }
259 }
260
VP8LBitWriterReset(const VP8LBitWriter * const bw_init,VP8LBitWriter * const bw)261 void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
262 VP8LBitWriter* const bw) {
263 bw->bits_ = bw_init->bits_;
264 bw->used_ = bw_init->used_;
265 bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_);
266 assert(bw->cur_ <= bw->end_);
267 bw->error_ = bw_init->error_;
268 }
269
VP8LBitWriterSwap(VP8LBitWriter * const src,VP8LBitWriter * const dst)270 void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
271 const VP8LBitWriter tmp = *src;
272 *src = *dst;
273 *dst = tmp;
274 }
275
VP8LPutBitsFlushBits(VP8LBitWriter * const bw)276 void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) {
277 // If needed, make some room by flushing some bits out.
278 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
279 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
280 if (extra_size != (size_t)extra_size ||
281 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
282 bw->cur_ = bw->buf_;
283 bw->error_ = 1;
284 return;
285 }
286 }
287 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_);
288 bw->cur_ += VP8L_WRITER_BYTES;
289 bw->bits_ >>= VP8L_WRITER_BITS;
290 bw->used_ -= VP8L_WRITER_BITS;
291 }
292
VP8LPutBitsInternal(VP8LBitWriter * const bw,uint32_t bits,int n_bits)293 void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) {
294 assert(n_bits <= 32);
295 // That's the max we can handle:
296 assert(sizeof(vp8l_wtype_t) == 2);
297 if (n_bits > 0) {
298 vp8l_atype_t lbits = bw->bits_;
299 int used = bw->used_;
300 // Special case of overflow handling for 32bit accumulator (2-steps flush).
301 #if VP8L_WRITER_BITS == 16
302 if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
303 // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
304 const int shift = VP8L_WRITER_MAX_BITS - used;
305 lbits |= (vp8l_atype_t)bits << used;
306 used = VP8L_WRITER_MAX_BITS;
307 n_bits -= shift;
308 bits >>= shift;
309 assert(n_bits <= VP8L_WRITER_MAX_BITS);
310 }
311 #endif
312 // If needed, make some room by flushing some bits out.
313 while (used >= VP8L_WRITER_BITS) {
314 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
315 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
316 if (extra_size != (size_t)extra_size ||
317 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
318 bw->cur_ = bw->buf_;
319 bw->error_ = 1;
320 return;
321 }
322 }
323 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
324 bw->cur_ += VP8L_WRITER_BYTES;
325 lbits >>= VP8L_WRITER_BITS;
326 used -= VP8L_WRITER_BITS;
327 }
328 bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
329 bw->used_ = used + n_bits;
330 }
331 }
332
VP8LBitWriterFinish(VP8LBitWriter * const bw)333 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
334 // flush leftover bits
335 if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
336 while (bw->used_ > 0) {
337 *bw->cur_++ = (uint8_t)bw->bits_;
338 bw->bits_ >>= 8;
339 bw->used_ -= 8;
340 }
341 bw->used_ = 0;
342 }
343 return bw->buf_;
344 }
345
346 //------------------------------------------------------------------------------
347