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@gmail.com) 11 12#include <assert.h> 13#include <stdlib.h> 14#include "vp8enci.h" 15 16#if defined(__cplusplus) || defined(c_plusplus) 17extern "C" { 18#endif 19 20//----------------------------------------------------------------------------- 21// VP8BitWriter 22 23static 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 44static 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 74static 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 87const 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 99int 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 117int 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 134void 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 140void 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 152int 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 164uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 165 VP8PutValue(bw, 0, 8 - bw->nb_bits_); 166 bw->nb_bits_ = 0; // pad with zeroes 167 kFlush(bw); 168 return bw->buf_; 169} 170 171//----------------------------------------------------------------------------- 172 173#if defined(__cplusplus) || defined(c_plusplus) 174} // extern "C" 175#endif 176