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.h" 20 #include "./endian_inl.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 kFlush(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) kFlush(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) kFlush(bw); 139 } 140 return bit; 141 } 142 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 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 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 173 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 174 VP8PutValue(bw, 0, 9 - bw->nb_bits_); 175 bw->nb_bits_ = 0; // pad with zeroes 176 kFlush(bw); 177 return bw->buf_; 178 } 179 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; // kFlush() 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 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. 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 240 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { 241 memset(bw, 0, sizeof(*bw)); 242 return VP8LBitWriterResize(bw, expected_size); 243 } 244 245 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) { 246 if (bw != NULL) { 247 WebPSafeFree(bw->buf_); 248 memset(bw, 0, sizeof(*bw)); 249 } 250 } 251 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 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
