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