1 // Copyright 2011 Google Inc. All Rights Reserved.
2 //
3 // This code is licensed under the same terms as WebM:
4 // Software License Agreement: http://www.webmproject.org/license/software/
5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/
6 // -----------------------------------------------------------------------------
7 //
8 // Bit writing and boolean coder
9 //
10 // Author: Skal (pascal.massimino@gmail.com)
11 // Vikas Arora (vikaas.arora@gmail.com)
12
13 #include <assert.h>
14 #include <string.h> // for memcpy()
15 #include <stdlib.h>
16 #include "./bit_writer.h"
17
18 #if defined(__cplusplus) || defined(c_plusplus)
19 extern "C" {
20 #endif
21
22 //------------------------------------------------------------------------------
23 // VP8BitWriter
24
BitWriterResize(VP8BitWriter * const bw,size_t extra_size)25 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
26 uint8_t* new_buf;
27 size_t new_size;
28 const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
29 const size_t needed_size = (size_t)needed_size_64b;
30 if (needed_size_64b != needed_size) {
31 bw->error_ = 1;
32 return 0;
33 }
34 if (needed_size <= bw->max_pos_) return 1;
35 // If the following line wraps over 32bit, the test just after will catch it.
36 new_size = 2 * bw->max_pos_;
37 if (new_size < needed_size) new_size = needed_size;
38 if (new_size < 1024) new_size = 1024;
39 new_buf = (uint8_t*)malloc(new_size);
40 if (new_buf == NULL) {
41 bw->error_ = 1;
42 return 0;
43 }
44 memcpy(new_buf, bw->buf_, bw->pos_);
45 free(bw->buf_);
46 bw->buf_ = new_buf;
47 bw->max_pos_ = new_size;
48 return 1;
49 }
50
kFlush(VP8BitWriter * const bw)51 static void kFlush(VP8BitWriter* const bw) {
52 const int s = 8 + bw->nb_bits_;
53 const int32_t bits = bw->value_ >> s;
54 assert(bw->nb_bits_ >= 0);
55 bw->value_ -= bits << s;
56 bw->nb_bits_ -= 8;
57 if ((bits & 0xff) != 0xff) {
58 size_t pos = bw->pos_;
59 if (!BitWriterResize(bw, bw->run_ + 1)) {
60 return;
61 }
62 if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's
63 if (pos > 0) bw->buf_[pos - 1]++;
64 }
65 if (bw->run_ > 0) {
66 const int value = (bits & 0x100) ? 0x00 : 0xff;
67 for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
68 }
69 bw->buf_[pos++] = bits;
70 bw->pos_ = pos;
71 } else {
72 bw->run_++; // delay writing of bytes 0xff, pending eventual carry.
73 }
74 }
75
76 //------------------------------------------------------------------------------
77 // renormalization
78
79 static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i)
80 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
81 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
82 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
83 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
84 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
85 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
86 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
87 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
88 0
89 };
90
91 // range = ((range + 1) << kVP8Log2Range[range]) - 1
92 static const uint8_t kNewRange[128] = {
93 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
94 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
95 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
96 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
97 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
98 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
99 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
100 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
101 241, 243, 245, 247, 249, 251, 253, 127
102 };
103
VP8PutBit(VP8BitWriter * const bw,int bit,int prob)104 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
105 const int split = (bw->range_ * prob) >> 8;
106 if (bit) {
107 bw->value_ += split + 1;
108 bw->range_ -= split + 1;
109 } else {
110 bw->range_ = split;
111 }
112 if (bw->range_ < 127) { // emit 'shift' bits out and renormalize
113 const int shift = kNorm[bw->range_];
114 bw->range_ = kNewRange[bw->range_];
115 bw->value_ <<= shift;
116 bw->nb_bits_ += shift;
117 if (bw->nb_bits_ > 0) kFlush(bw);
118 }
119 return bit;
120 }
121
VP8PutBitUniform(VP8BitWriter * const bw,int bit)122 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
123 const int split = bw->range_ >> 1;
124 if (bit) {
125 bw->value_ += split + 1;
126 bw->range_ -= split + 1;
127 } else {
128 bw->range_ = split;
129 }
130 if (bw->range_ < 127) {
131 bw->range_ = kNewRange[bw->range_];
132 bw->value_ <<= 1;
133 bw->nb_bits_ += 1;
134 if (bw->nb_bits_ > 0) kFlush(bw);
135 }
136 return bit;
137 }
138
VP8PutValue(VP8BitWriter * const bw,int value,int nb_bits)139 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) {
140 int mask;
141 for (mask = 1 << (nb_bits - 1); mask; mask >>= 1)
142 VP8PutBitUniform(bw, value & mask);
143 }
144
VP8PutSignedValue(VP8BitWriter * const bw,int value,int nb_bits)145 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) {
146 if (!VP8PutBitUniform(bw, value != 0))
147 return;
148 if (value < 0) {
149 VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1);
150 } else {
151 VP8PutValue(bw, value << 1, nb_bits + 1);
152 }
153 }
154
155 //------------------------------------------------------------------------------
156
VP8BitWriterInit(VP8BitWriter * const bw,size_t expected_size)157 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
158 bw->range_ = 255 - 1;
159 bw->value_ = 0;
160 bw->run_ = 0;
161 bw->nb_bits_ = -8;
162 bw->pos_ = 0;
163 bw->max_pos_ = 0;
164 bw->error_ = 0;
165 bw->buf_ = NULL;
166 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
167 }
168
VP8BitWriterFinish(VP8BitWriter * const bw)169 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
170 VP8PutValue(bw, 0, 9 - bw->nb_bits_);
171 bw->nb_bits_ = 0; // pad with zeroes
172 kFlush(bw);
173 return bw->buf_;
174 }
175
VP8BitWriterAppend(VP8BitWriter * const bw,const uint8_t * data,size_t size)176 int VP8BitWriterAppend(VP8BitWriter* const bw,
177 const uint8_t* data, size_t size) {
178 assert(data);
179 if (bw->nb_bits_ != -8) return 0; // kFlush() must have been called
180 if (!BitWriterResize(bw, size)) return 0;
181 memcpy(bw->buf_ + bw->pos_, data, size);
182 bw->pos_ += size;
183 return 1;
184 }
185
VP8BitWriterWipeOut(VP8BitWriter * const bw)186 void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
187 if (bw) {
188 free(bw->buf_);
189 memset(bw, 0, sizeof(*bw));
190 }
191 }
192
193 //------------------------------------------------------------------------------
194 // VP8LBitWriter
195
196 // Returns 1 on success.
VP8LBitWriterResize(VP8LBitWriter * const bw,size_t extra_size)197 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
198 uint8_t* allocated_buf;
199 size_t allocated_size;
200 const size_t current_size = VP8LBitWriterNumBytes(bw);
201 const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
202 const size_t size_required = (size_t)size_required_64b;
203 if (size_required != size_required_64b) {
204 bw->error_ = 1;
205 return 0;
206 }
207 if (bw->max_bytes_ > 0 && size_required <= bw->max_bytes_) return 1;
208 allocated_size = (3 * bw->max_bytes_) >> 1;
209 if (allocated_size < size_required) allocated_size = size_required;
210 // make allocated size multiple of 1k
211 allocated_size = (((allocated_size >> 10) + 1) << 10);
212 allocated_buf = (uint8_t*)malloc(allocated_size);
213 if (allocated_buf == NULL) {
214 bw->error_ = 1;
215 return 0;
216 }
217 memcpy(allocated_buf, bw->buf_, current_size);
218 free(bw->buf_);
219 bw->buf_ = allocated_buf;
220 bw->max_bytes_ = allocated_size;
221 memset(allocated_buf + current_size, 0, allocated_size - current_size);
222 return 1;
223 }
224
VP8LBitWriterInit(VP8LBitWriter * const bw,size_t expected_size)225 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
226 memset(bw, 0, sizeof(*bw));
227 return VP8LBitWriterResize(bw, expected_size);
228 }
229
VP8LBitWriterDestroy(VP8LBitWriter * const bw)230 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) {
231 if (bw != NULL) {
232 free(bw->buf_);
233 memset(bw, 0, sizeof(*bw));
234 }
235 }
236
VP8LWriteBits(VP8LBitWriter * const bw,int n_bits,uint32_t bits)237 void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) {
238 if (n_bits < 1) return;
239 #if !defined(__BIG_ENDIAN__)
240 // Technically, this branch of the code can write up to 25 bits at a time,
241 // but in prefix encoding, the maximum number of bits written is 18 at a time.
242 {
243 uint8_t* const p = &bw->buf_[bw->bit_pos_ >> 3];
244 uint32_t v = *(const uint32_t*)p;
245 v |= bits << (bw->bit_pos_ & 7);
246 *(uint32_t*)p = v;
247 bw->bit_pos_ += n_bits;
248 }
249 #else // BIG_ENDIAN
250 {
251 uint8_t* p = &bw->buf_[bw->bit_pos_ >> 3];
252 const int bits_reserved_in_first_byte = bw->bit_pos_ & 7;
253 const int bits_left_to_write = n_bits - 8 + bits_reserved_in_first_byte;
254 // implicit & 0xff is assumed for uint8_t arithmetics
255 *p++ |= bits << bits_reserved_in_first_byte;
256 bits >>= 8 - bits_reserved_in_first_byte;
257 if (bits_left_to_write >= 1) {
258 *p++ = bits;
259 bits >>= 8;
260 if (bits_left_to_write >= 9) {
261 *p++ = bits;
262 bits >>= 8;
263 }
264 }
265 assert(n_bits <= 25);
266 *p = bits;
267 bw->bit_pos_ += n_bits;
268 }
269 #endif
270 if ((bw->bit_pos_ >> 3) > (bw->max_bytes_ - 8)) {
271 const uint64_t extra_size = 32768ULL + bw->max_bytes_;
272 if (extra_size != (size_t)extra_size ||
273 !VP8LBitWriterResize(bw, (size_t)extra_size)) {
274 bw->bit_pos_ = 0;
275 bw->error_ = 1;
276 }
277 }
278 }
279
280 //------------------------------------------------------------------------------
281
282 #if defined(__cplusplus) || defined(c_plusplus)
283 } // extern "C"
284 #endif
285