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@gmail.com)
13//         Vikas Arora (vikaas.arora@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)
21extern "C" {
22#endif
23
24//------------------------------------------------------------------------------
25// VP8BitWriter
26
27static 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
53static 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
81static 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
94static 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
106int 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
124int 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
141void 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
147void 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
159int 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
171uint8_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
178int 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
188void 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.
199static 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
227int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
228  memset(bw, 0, sizeof(*bw));
229  return VP8LBitWriterResize(bw, expected_size);
230}
231
232void VP8LBitWriterDestroy(VP8LBitWriter* const bw) {
233  if (bw != NULL) {
234    free(bw->buf_);
235    memset(bw, 0, sizeof(*bw));
236  }
237}
238
239void 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