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)
17 extern "C" {
18 #endif
19
20 //-----------------------------------------------------------------------------
21 // VP8BitWriter
22
BitWriterResize(VP8BitWriter * const bw,size_t extra_size)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
kFlush(VP8BitWriter * const bw)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
VP8PutBit(VP8BitWriter * const bw,int bit,int prob)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
VP8PutBitUniform(VP8BitWriter * const bw,int bit)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
VP8PutValue(VP8BitWriter * const bw,int value,int nb_bits)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
VP8PutSignedValue(VP8BitWriter * const bw,int value,int nb_bits)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
VP8BitWriterInit(VP8BitWriter * const bw,size_t expected_size)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
VP8BitWriterFinish(VP8BitWriter * const bw)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
VP8BitWriterAppend(VP8BitWriter * const bw,const uint8_t * data,size_t size)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