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 #include "./bit_writer.h" 19 20 #if defined(__cplusplus) || defined(c_plusplus) 21 extern "C" { 22 #endif 23 24 //------------------------------------------------------------------------------ 25 // VP8BitWriter 26 27 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) { 28 uint8_t* new_buf; 29 size_t new_size; 30 const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size; 31 const size_t needed_size = (size_t)needed_size_64b; 32 if (needed_size_64b != needed_size) { 33 bw->error_ = 1; 34 return 0; 35 } 36 if (needed_size <= bw->max_pos_) return 1; 37 // If the following line wraps over 32bit, the test just after will catch it. 38 new_size = 2 * bw->max_pos_; 39 if (new_size < needed_size) new_size = needed_size; 40 if (new_size < 1024) new_size = 1024; 41 new_buf = (uint8_t*)malloc(new_size); 42 if (new_buf == NULL) { 43 bw->error_ = 1; 44 return 0; 45 } 46 memcpy(new_buf, bw->buf_, bw->pos_); 47 free(bw->buf_); 48 bw->buf_ = new_buf; 49 bw->max_pos_ = new_size; 50 return 1; 51 } 52 53 static void kFlush(VP8BitWriter* const bw) { 54 const int s = 8 + bw->nb_bits_; 55 const int32_t bits = bw->value_ >> s; 56 assert(bw->nb_bits_ >= 0); 57 bw->value_ -= bits << s; 58 bw->nb_bits_ -= 8; 59 if ((bits & 0xff) != 0xff) { 60 size_t pos = bw->pos_; 61 if (!BitWriterResize(bw, bw->run_ + 1)) { 62 return; 63 } 64 if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's 65 if (pos > 0) bw->buf_[pos - 1]++; 66 } 67 if (bw->run_ > 0) { 68 const int value = (bits & 0x100) ? 0x00 : 0xff; 69 for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value; 70 } 71 bw->buf_[pos++] = bits; 72 bw->pos_ = pos; 73 } else { 74 bw->run_++; // delay writing of bytes 0xff, pending eventual carry. 75 } 76 } 77 78 //------------------------------------------------------------------------------ 79 // renormalization 80 81 static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i) 82 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 83 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 84 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 85 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 86 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 87 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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 0 91 }; 92 93 // range = ((range + 1) << kVP8Log2Range[range]) - 1 94 static const uint8_t kNewRange[128] = { 95 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239, 96 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239, 97 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 98 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 99 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 100 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 101 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 102 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 103 241, 243, 245, 247, 249, 251, 253, 127 104 }; 105 106 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) { 107 const int split = (bw->range_ * prob) >> 8; 108 if (bit) { 109 bw->value_ += split + 1; 110 bw->range_ -= split + 1; 111 } else { 112 bw->range_ = split; 113 } 114 if (bw->range_ < 127) { // emit 'shift' bits out and renormalize 115 const int shift = kNorm[bw->range_]; 116 bw->range_ = kNewRange[bw->range_]; 117 bw->value_ <<= shift; 118 bw->nb_bits_ += shift; 119 if (bw->nb_bits_ > 0) kFlush(bw); 120 } 121 return bit; 122 } 123 124 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) { 125 const int split = bw->range_ >> 1; 126 if (bit) { 127 bw->value_ += split + 1; 128 bw->range_ -= split + 1; 129 } else { 130 bw->range_ = split; 131 } 132 if (bw->range_ < 127) { 133 bw->range_ = kNewRange[bw->range_]; 134 bw->value_ <<= 1; 135 bw->nb_bits_ += 1; 136 if (bw->nb_bits_ > 0) kFlush(bw); 137 } 138 return bit; 139 } 140 141 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) { 142 int mask; 143 for (mask = 1 << (nb_bits - 1); mask; mask >>= 1) 144 VP8PutBitUniform(bw, value & mask); 145 } 146 147 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) { 148 if (!VP8PutBitUniform(bw, value != 0)) 149 return; 150 if (value < 0) { 151 VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1); 152 } else { 153 VP8PutValue(bw, value << 1, nb_bits + 1); 154 } 155 } 156 157 //------------------------------------------------------------------------------ 158 159 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) { 160 bw->range_ = 255 - 1; 161 bw->value_ = 0; 162 bw->run_ = 0; 163 bw->nb_bits_ = -8; 164 bw->pos_ = 0; 165 bw->max_pos_ = 0; 166 bw->error_ = 0; 167 bw->buf_ = NULL; 168 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1; 169 } 170 171 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 172 VP8PutValue(bw, 0, 9 - bw->nb_bits_); 173 bw->nb_bits_ = 0; // pad with zeroes 174 kFlush(bw); 175 return bw->buf_; 176 } 177 178 int VP8BitWriterAppend(VP8BitWriter* const bw, 179 const uint8_t* data, size_t size) { 180 assert(data); 181 if (bw->nb_bits_ != -8) return 0; // kFlush() must have been called 182 if (!BitWriterResize(bw, size)) return 0; 183 memcpy(bw->buf_ + bw->pos_, data, size); 184 bw->pos_ += size; 185 return 1; 186 } 187 188 void VP8BitWriterWipeOut(VP8BitWriter* const bw) { 189 if (bw) { 190 free(bw->buf_); 191 memset(bw, 0, sizeof(*bw)); 192 } 193 } 194 195 //------------------------------------------------------------------------------ 196 // VP8LBitWriter 197 198 // Returns 1 on success. 199 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) { 200 uint8_t* allocated_buf; 201 size_t allocated_size; 202 const size_t current_size = VP8LBitWriterNumBytes(bw); 203 const uint64_t size_required_64b = (uint64_t)current_size + extra_size; 204 const size_t size_required = (size_t)size_required_64b; 205 if (size_required != size_required_64b) { 206 bw->error_ = 1; 207 return 0; 208 } 209 if (bw->max_bytes_ > 0 && size_required <= bw->max_bytes_) return 1; 210 allocated_size = (3 * bw->max_bytes_) >> 1; 211 if (allocated_size < size_required) allocated_size = size_required; 212 // make allocated size multiple of 1k 213 allocated_size = (((allocated_size >> 10) + 1) << 10); 214 allocated_buf = (uint8_t*)malloc(allocated_size); 215 if (allocated_buf == NULL) { 216 bw->error_ = 1; 217 return 0; 218 } 219 memcpy(allocated_buf, bw->buf_, current_size); 220 free(bw->buf_); 221 bw->buf_ = allocated_buf; 222 bw->max_bytes_ = allocated_size; 223 memset(allocated_buf + current_size, 0, allocated_size - current_size); 224 return 1; 225 } 226 227 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { 228 memset(bw, 0, sizeof(*bw)); 229 return VP8LBitWriterResize(bw, expected_size); 230 } 231 232 void VP8LBitWriterDestroy(VP8LBitWriter* const bw) { 233 if (bw != NULL) { 234 free(bw->buf_); 235 memset(bw, 0, sizeof(*bw)); 236 } 237 } 238 239 void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) { 240 if (n_bits < 1) return; 241 #if !defined(__BIG_ENDIAN__) 242 // Technically, this branch of the code can write up to 25 bits at a time, 243 // but in prefix encoding, the maximum number of bits written is 18 at a time. 244 { 245 uint8_t* const p = &bw->buf_[bw->bit_pos_ >> 3]; 246 uint32_t v = *(const uint32_t*)p; 247 v |= bits << (bw->bit_pos_ & 7); 248 *(uint32_t*)p = v; 249 bw->bit_pos_ += n_bits; 250 } 251 #else // BIG_ENDIAN 252 { 253 uint8_t* p = &bw->buf_[bw->bit_pos_ >> 3]; 254 const int bits_reserved_in_first_byte = bw->bit_pos_ & 7; 255 const int bits_left_to_write = n_bits - 8 + bits_reserved_in_first_byte; 256 // implicit & 0xff is assumed for uint8_t arithmetics 257 *p++ |= bits << bits_reserved_in_first_byte; 258 bits >>= 8 - bits_reserved_in_first_byte; 259 if (bits_left_to_write >= 1) { 260 *p++ = bits; 261 bits >>= 8; 262 if (bits_left_to_write >= 9) { 263 *p++ = bits; 264 bits >>= 8; 265 } 266 } 267 assert(n_bits <= 25); 268 *p = bits; 269 bw->bit_pos_ += n_bits; 270 } 271 #endif 272 if ((bw->bit_pos_ >> 3) > (bw->max_bytes_ - 8)) { 273 const uint64_t extra_size = 32768ULL + bw->max_bytes_; 274 if (extra_size != (size_t)extra_size || 275 !VP8LBitWriterResize(bw, (size_t)extra_size)) { 276 bw->bit_pos_ = 0; 277 bw->error_ = 1; 278 } 279 } 280 } 281 282 //------------------------------------------------------------------------------ 283 284 #if defined(__cplusplus) || defined(c_plusplus) 285 } // extern "C" 286 #endif 287
