1 // Copyright 2011 Google Inc. 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 12 #include <assert.h> 13 #include <stdlib.h> 14 #include "vp8enci.h" 15 16 #if defined(__cplusplus) || defined(c_plusplus) 17 extern "C" { 18 #endif 19 20 //----------------------------------------------------------------------------- 21 // VP8BitWriter 22 23 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) { 24 uint8_t* new_buf; 25 size_t new_size; 26 const size_t needed_size = bw->pos_ + extra_size; 27 if (needed_size <= bw->max_pos_) return 1; 28 new_size = 2 * bw->max_pos_; 29 if (new_size < needed_size) 30 new_size = needed_size; 31 if (new_size < 1024) new_size = 1024; 32 new_buf = (uint8_t*)malloc(new_size); 33 if (new_buf == NULL) { 34 bw->error_ = 1; 35 return 0; 36 } 37 if (bw->pos_ > 0) memcpy(new_buf, bw->buf_, bw->pos_); 38 free(bw->buf_); 39 bw->buf_ = new_buf; 40 bw->max_pos_ = new_size; 41 return 1; 42 } 43 44 static void kFlush(VP8BitWriter* const bw) { 45 const int s = 8 + bw->nb_bits_; 46 const int32_t bits = bw->value_ >> s; 47 assert(bw->nb_bits_ >= 0); 48 bw->value_ -= bits << s; 49 bw->nb_bits_ -= 8; 50 if ((bits & 0xff) != 0xff) { 51 size_t pos = bw->pos_; 52 if (pos + bw->run_ >= bw->max_pos_) { // reallocate 53 if (!BitWriterResize(bw, bw->run_ + 1)) { 54 return; 55 } 56 } 57 if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's 58 if (pos > 0) bw->buf_[pos - 1]++; 59 } 60 if (bw->run_ > 0) { 61 const int value = (bits & 0x100) ? 0x00 : 0xff; 62 for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value; 63 } 64 bw->buf_[pos++] = bits; 65 bw->pos_ = pos; 66 } else { 67 bw->run_++; // delay writing of bytes 0xff, pending eventual carry. 68 } 69 } 70 71 //----------------------------------------------------------------------------- 72 // renormalization 73 74 static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i) 75 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 76 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 77 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 78 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 79 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 80 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 81 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 82 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 83 0 84 }; 85 86 // range = ((range + 1) << kVP8Log2Range[range]) - 1 87 const uint8_t kNewRange[128] = { 88 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239, 89 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239, 90 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 91 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 92 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 93 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 94 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 95 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 96 241, 243, 245, 247, 249, 251, 253, 127 97 }; 98 99 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) { 100 const int split = (bw->range_ * prob) >> 8; 101 if (bit) { 102 bw->value_ += split + 1; 103 bw->range_ -= split + 1; 104 } else { 105 bw->range_ = split; 106 } 107 if (bw->range_ < 127) { // emit 'shift' bits out and renormalize 108 const int shift = kNorm[bw->range_]; 109 bw->range_ = kNewRange[bw->range_]; 110 bw->value_ <<= shift; 111 bw->nb_bits_ += shift; 112 if (bw->nb_bits_ > 0) kFlush(bw); 113 } 114 return bit; 115 } 116 117 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) { 118 const int split = bw->range_ >> 1; 119 if (bit) { 120 bw->value_ += split + 1; 121 bw->range_ -= split + 1; 122 } else { 123 bw->range_ = split; 124 } 125 if (bw->range_ < 127) { 126 bw->range_ = kNewRange[bw->range_]; 127 bw->value_ <<= 1; 128 bw->nb_bits_ += 1; 129 if (bw->nb_bits_ > 0) kFlush(bw); 130 } 131 return bit; 132 } 133 134 void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) { 135 int mask; 136 for (mask = 1 << (nb_bits - 1); mask; mask >>= 1) 137 VP8PutBitUniform(bw, value & mask); 138 } 139 140 void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) { 141 if (!VP8PutBitUniform(bw, value != 0)) 142 return; 143 if (value < 0) { 144 VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1); 145 } else { 146 VP8PutValue(bw, value << 1, nb_bits + 1); 147 } 148 } 149 150 //----------------------------------------------------------------------------- 151 152 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) { 153 bw->range_ = 255 - 1; 154 bw->value_ = 0; 155 bw->run_ = 0; 156 bw->nb_bits_ = -8; 157 bw->pos_ = 0; 158 bw->max_pos_ = 0; 159 bw->error_ = 0; 160 bw->buf_ = NULL; 161 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1; 162 } 163 164 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 165 VP8PutValue(bw, 0, 9 - bw->nb_bits_); 166 bw->nb_bits_ = 0; // pad with zeroes 167 kFlush(bw); 168 return bw->buf_; 169 } 170 171 int VP8BitWriterAppend(VP8BitWriter* const bw, 172 const uint8_t* data, size_t size) { 173 assert(data); 174 if (bw->nb_bits_ != -8) return 0; // kFlush() must have been called 175 if (!BitWriterResize(bw, size)) return 0; 176 memcpy(bw->buf_ + bw->pos_, data, size); 177 bw->pos_ += size; 178 return 1; 179 } 180 181 //----------------------------------------------------------------------------- 182 183 #if defined(__cplusplus) || defined(c_plusplus) 184 } // extern "C" 185 #endif 186
