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 (at) gmail.com) 13 // Vikas Arora (vikaas.arora (at) 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 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 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 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 MIN_EXTRA_SIZE (32768ULL) 204 205 // Returns 1 on success. 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 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 return 1; 252 } 253 254 void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { 255 if (bw != NULL) { 256 WebPSafeFree(bw->buf_); 257 memset(bw, 0, sizeof(*bw)); 258 } 259 } 260 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 270 void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) { 271 const VP8LBitWriter tmp = *src; 272 *src = *dst; 273 *dst = tmp; 274 } 275 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 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 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
