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
26static 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
55static 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
83static 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
96static 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
108int 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
126int 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
143void 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
151void 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
162int 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
174uint8_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
181int 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
191void 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.
206static 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
237int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
238 memset(bw, 0, sizeof(*bw));
239 return VP8LBitWriterResize(bw, expected_size);
240}
241
242int 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
255void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
256 if (bw != NULL) {
257 WebPSafeFree(bw->buf_);
258 memset(bw, 0, sizeof(*bw));
259 }
260}
261
262void 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
271void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
272 const VP8LBitWriter tmp = *src;
273 *src = *dst;
274 *dst = tmp;
275}
276
277void 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
294void 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
334uint8_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