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 "./bit_writer.h"
20 #include "./endian_inl.h"
21 #include "./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
VP8PutValue(VP8BitWriter * const bw,int value,int nb_bits)143 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) {
144 int mask;
145 for (mask = 1 << (nb_bits - 1); mask; mask >>= 1)
146 VP8PutBitUniform(bw, value & mask);
147 }
148
VP8PutSignedValue(VP8BitWriter * const bw,int value,int nb_bits)149 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) {
150 if (!VP8PutBitUniform(bw, value != 0))
151 return;
152 if (value < 0) {
153 VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1);
154 } else {
155 VP8PutValue(bw, value << 1, nb_bits + 1);
156 }
157 }
158
159 //------------------------------------------------------------------------------
160
VP8BitWriterInit(VP8BitWriter * const bw,size_t expected_size)161 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
162 bw->range_ = 255 - 1;
163 bw->value_ = 0;
164 bw->run_ = 0;
165 bw->nb_bits_ = -8;
166 bw->pos_ = 0;
167 bw->max_pos_ = 0;
168 bw->error_ = 0;
169 bw->buf_ = NULL;
170 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
171 }
172
VP8BitWriterFinish(VP8BitWriter * const bw)173 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
174 VP8PutValue(bw, 0, 9 - bw->nb_bits_);
175 bw->nb_bits_ = 0; // pad with zeroes
176 Flush(bw);
177 return bw->buf_;
178 }
179
VP8BitWriterAppend(VP8BitWriter * const bw,const uint8_t * data,size_t size)180 int VP8BitWriterAppend(VP8BitWriter* const bw,
181 const uint8_t* data, size_t size) {
182 assert(data != NULL);
183 if (bw->nb_bits_ != -8) return 0; // Flush() must have been called
184 if (!BitWriterResize(bw, size)) return 0;
185 memcpy(bw->buf_ + bw->pos_, data, size);
186 bw->pos_ += size;
187 return 1;
188 }
189
VP8BitWriterWipeOut(VP8BitWriter * const bw)190 void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
191 if (bw != NULL) {
192 WebPSafeFree(bw->buf_);
193 memset(bw, 0, sizeof(*bw));
194 }
195 }
196
197 //------------------------------------------------------------------------------
198 // VP8LBitWriter
199
200 // This is the minimum amount of size the memory buffer is guaranteed to grow
201 // when extra space is needed.
202 #define MIN_EXTRA_SIZE (32768ULL)
203
204 #define VP8L_WRITER_BYTES ((int)sizeof(vp8l_wtype_t))
205 #define VP8L_WRITER_BITS (VP8L_WRITER_BYTES * 8)
206 #define VP8L_WRITER_MAX_BITS (8 * (int)sizeof(vp8l_atype_t))
207
208 // Returns 1 on success.
VP8LBitWriterResize(VP8LBitWriter * const bw,size_t extra_size)209 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
210 uint8_t* allocated_buf;
211 size_t allocated_size;
212 const size_t max_bytes = bw->end_ - bw->buf_;
213 const size_t current_size = bw->cur_ - bw->buf_;
214 const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
215 const size_t size_required = (size_t)size_required_64b;
216 if (size_required != size_required_64b) {
217 bw->error_ = 1;
218 return 0;
219 }
220 if (max_bytes > 0 && size_required <= max_bytes) return 1;
221 allocated_size = (3 * max_bytes) >> 1;
222 if (allocated_size < size_required) allocated_size = size_required;
223 // make allocated size multiple of 1k
224 allocated_size = (((allocated_size >> 10) + 1) << 10);
225 allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
226 if (allocated_buf == NULL) {
227 bw->error_ = 1;
228 return 0;
229 }
230 if (current_size > 0) {
231 memcpy(allocated_buf, bw->buf_, current_size);
232 }
233 WebPSafeFree(bw->buf_);
234 bw->buf_ = allocated_buf;
235 bw->cur_ = bw->buf_ + current_size;
236 bw->end_ = bw->buf_ + allocated_size;
237 return 1;
238 }
239
VP8LBitWriterInit(VP8LBitWriter * const bw,size_t expected_size)240 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
241 memset(bw, 0, sizeof(*bw));
242 return VP8LBitWriterResize(bw, expected_size);
243 }
244
VP8LBitWriterDestroy(VP8LBitWriter * const bw)245 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) {
246 if (bw != NULL) {
247 WebPSafeFree(bw->buf_);
248 memset(bw, 0, sizeof(*bw));
249 }
250 }
251
VP8LWriteBits(VP8LBitWriter * const bw,int n_bits,uint32_t bits)252 void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) {
253 assert(n_bits <= 32);
254 // That's the max we can handle:
255 assert(bw->used_ + n_bits <= 2 * VP8L_WRITER_MAX_BITS);
256 if (n_bits > 0) {
257 // Local field copy.
258 vp8l_atype_t lbits = bw->bits_;
259 int used = bw->used_;
260 // Special case of overflow handling for 32bit accumulator (2-steps flush).
261 if (VP8L_WRITER_BITS == 16) {
262 if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
263 // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
264 const int shift = VP8L_WRITER_MAX_BITS - used;
265 lbits |= (vp8l_atype_t)bits << used;
266 used = VP8L_WRITER_MAX_BITS;
267 n_bits -= shift;
268 bits >>= shift;
269 assert(n_bits <= VP8L_WRITER_MAX_BITS);
270 }
271 }
272 // If needed, make some room by flushing some bits out.
273 while (used >= VP8L_WRITER_BITS) {
274 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
275 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
276 if (extra_size != (size_t)extra_size ||
277 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
278 bw->cur_ = bw->buf_;
279 bw->error_ = 1;
280 return;
281 }
282 }
283 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
284 bw->cur_ += VP8L_WRITER_BYTES;
285 lbits >>= VP8L_WRITER_BITS;
286 used -= VP8L_WRITER_BITS;
287 }
288 // Eventually, insert new bits.
289 bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
290 bw->used_ = used + n_bits;
291 }
292 }
293
VP8LBitWriterFinish(VP8LBitWriter * const bw)294 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
295 // flush leftover bits
296 if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
297 while (bw->used_ > 0) {
298 *bw->cur_++ = (uint8_t)bw->bits_;
299 bw->bits_ >>= 8;
300 bw->used_ -= 8;
301 }
302 bw->used_ = 0;
303 }
304 return bw->buf_;
305 }
306
307 //------------------------------------------------------------------------------
308