| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 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 void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) { | |
| 151 if (!VP8PutBitUniform(bw, value != 0)) | |
| 152 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 //------------------------------------------------------------------------------ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2651883004:
libwebp-0.6.0-rc1 (Closed)
