Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 1 | // Copyright 2011 Google Inc. All Rights Reserved. |
| 2 | // |
Vikas Arora | 0406ce1 | 2013-08-09 15:57:12 -0700 | [diff] [blame] | 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. |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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> |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 18 | |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 19 | #include "./bit_writer.h" |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 20 | #include "./endian_inl.h" |
| 21 | #include "./utils.h" |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 22 | |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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; |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 40 | new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 41 | if (new_buf == NULL) { |
| 42 | bw->error_ = 1; |
| 43 | return 0; |
| 44 | } |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 45 | if (bw->pos_ > 0) { |
| 46 | assert(bw->buf_ != NULL); |
| 47 | memcpy(new_buf, bw->buf_, bw->pos_); |
| 48 | } |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 49 | WebPSafeFree(bw->buf_); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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) { |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 182 | assert(data != NULL); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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) { |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 191 | if (bw != NULL) { |
| 192 | WebPSafeFree(bw->buf_); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 193 | memset(bw, 0, sizeof(*bw)); |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | //------------------------------------------------------------------------------ |
| 198 | // VP8LBitWriter |
| 199 | |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 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 | |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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; |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 212 | const size_t max_bytes = bw->end_ - bw->buf_; |
| 213 | const size_t current_size = bw->cur_ - bw->buf_; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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 | } |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 220 | if (max_bytes > 0 && size_required <= max_bytes) return 1; |
| 221 | allocated_size = (3 * max_bytes) >> 1; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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); |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 225 | allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 226 | if (allocated_buf == NULL) { |
| 227 | bw->error_ = 1; |
| 228 | return 0; |
| 229 | } |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 230 | if (current_size > 0) { |
| 231 | memcpy(allocated_buf, bw->buf_, current_size); |
| 232 | } |
| 233 | WebPSafeFree(bw->buf_); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 234 | bw->buf_ = allocated_buf; |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 235 | bw->cur_ = bw->buf_ + current_size; |
| 236 | bw->end_ = bw->buf_ + allocated_size; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 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) { |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 247 | WebPSafeFree(bw->buf_); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 248 | memset(bw, 0, sizeof(*bw)); |
| 249 | } |
| 250 | } |
| 251 | |
| 252 | void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) { |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 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); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 270 | } |
| 271 | } |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 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; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 287 | } |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 288 | // Eventually, insert new bits. |
| 289 | bw->bits_ = lbits | ((vp8l_atype_t)bits << used); |
| 290 | bw->used_ = used + n_bits; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 291 | } |
| 292 | } |
| 293 | |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 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 | } |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 306 | |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 307 | //------------------------------------------------------------------------------ |