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 | |
26 | static int BitWriterResize(VP8BitWriter* const bw, size_t ) { |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 (32768ULL) |
204 | |
205 | // Returns 1 on success. |
206 | static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t ) { |
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 | |
237 | int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { |
238 | memset(bw, 0, sizeof(*bw)); |
239 | return VP8LBitWriterResize(bw, expected_size); |
240 | } |
241 | |
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 | |
255 | void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { |
256 | if (bw != NULL) { |
257 | WebPSafeFree(bw->buf_); |
258 | memset(bw, 0, sizeof(*bw)); |
259 | } |
260 | } |
261 | |
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 | |
271 | void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) { |
272 | const VP8LBitWriter tmp = *src; |
273 | *src = *dst; |
274 | *dst = tmp; |
275 | } |
276 | |
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 = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; |
281 | if (extra_size != (size_t)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 | |
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 = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; |
317 | if (extra_size != (size_t)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 | |
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 | |