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 "./bit_writer_utils.h" 20 #include "./endian_inl_utils.h" 21 #include "./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 void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { 243 if (bw != NULL) { 244 WebPSafeFree(bw->buf_); 245 memset(bw, 0, sizeof(*bw)); 246 } 247 } 248 249 void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) { 250 // If needed, make some room by flushing some bits out. 251 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { 252 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; 253 if (extra_size != (size_t)extra_size || 254 !VP8LBitWriterResize(bw, (size_t)extra_size)) { 255 bw->cur_ = bw->buf_; 256 bw->error_ = 1; 257 return; 258 } 259 } 260 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_); 261 bw->cur_ += VP8L_WRITER_BYTES; 262 bw->bits_ >>= VP8L_WRITER_BITS; 263 bw->used_ -= VP8L_WRITER_BITS; 264 } 265 266 void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) { 267 assert(n_bits <= 32); 268 // That's the max we can handle: 269 assert(sizeof(vp8l_wtype_t) == 2); 270 if (n_bits > 0) { 271 vp8l_atype_t lbits = bw->bits_; 272 int used = bw->used_; 273 // Special case of overflow handling for 32bit accumulator (2-steps flush). 274 #if VP8L_WRITER_BITS == 16 275 if (used + n_bits >= VP8L_WRITER_MAX_BITS) { 276 // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below. 277 const int shift = VP8L_WRITER_MAX_BITS - used; 278 lbits |= (vp8l_atype_t)bits << used; 279 used = VP8L_WRITER_MAX_BITS; 280 n_bits -= shift; 281 bits >>= shift; 282 assert(n_bits <= VP8L_WRITER_MAX_BITS); 283 } 284 #endif 285 // If needed, make some room by flushing some bits out. 286 while (used >= VP8L_WRITER_BITS) { 287 if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { 288 const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; 289 if (extra_size != (size_t)extra_size || 290 !VP8LBitWriterResize(bw, (size_t)extra_size)) { 291 bw->cur_ = bw->buf_; 292 bw->error_ = 1; 293 return; 294 } 295 } 296 *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits); 297 bw->cur_ += VP8L_WRITER_BYTES; 298 lbits >>= VP8L_WRITER_BITS; 299 used -= VP8L_WRITER_BITS; 300 } 301 bw->bits_ = lbits | ((vp8l_atype_t)bits << used); 302 bw->used_ = used + n_bits; 303 } 304 } 305 306 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) { 307 // flush leftover bits 308 if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) { 309 while (bw->used_ > 0) { 310 *bw->cur_++ = (uint8_t)bw->bits_; 311 bw->bits_ >>= 8; 312 bw->used_ -= 8; 313 } 314 bw->used_ = 0; 315 } 316 return bw->buf_; 317 } 318 319 //------------------------------------------------------------------------------ 320
