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
19#include "src/utils/bit_writer_utils.h"
20#include "src/utils/endian_inl_utils.h"
21#include "src/utils/utils.h"
22
23//------------------------------------------------------------------------------
24// VP8BitWriter
25
26static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
27  uint8_t* new_buf;
28  size_t new_size;
29  const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
30  const size_t needed_size = (size_t)needed_size_64b;
31  if (needed_size_64b != needed_size) {
32    bw->error_ = 1;
33    return 0;
34  }
35  if (needed_size <= bw->max_pos_) return 1;
36  // If the following line wraps over 32bit, the test just after will catch it.
37  new_size = 2 * bw->max_pos_;
38  if (new_size < needed_size) new_size = needed_size;
39  if (new_size < 1024) new_size = 1024;
40  new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size);
41  if (new_buf == NULL) {
42    bw->error_ = 1;
43    return 0;
44  }
45  if (bw->pos_ > 0) {
46    assert(bw->buf_ != NULL);
47    memcpy(new_buf, bw->buf_, bw->pos_);
48  }
49  WebPSafeFree(bw->buf_);
50  bw->buf_ = new_buf;
51  bw->max_pos_ = new_size;
52  return 1;
53}
54
55static void Flush(VP8BitWriter* const bw) {
56  const int s = 8 + bw->nb_bits_;
57  const int32_t bits = bw->value_ >> s;
58  assert(bw->nb_bits_ >= 0);
59  bw->value_ -= bits << s;
60  bw->nb_bits_ -= 8;
61  if ((bits & 0xff) != 0xff) {
62    size_t pos = bw->pos_;
63    if (!BitWriterResize(bw, bw->run_ + 1)) {
64      return;
65    }
66    if (bits & 0x100) {  // overflow -> propagate carry over pending 0xff's
67      if (pos > 0) bw->buf_[pos - 1]++;
68    }
69    if (bw->run_ > 0) {
70      const int value = (bits & 0x100) ? 0x00 : 0xff;
71      for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
72    }
73    bw->buf_[pos++] = bits;
74    bw->pos_ = pos;
75  } else {
76    bw->run_++;   // delay writing of bytes 0xff, pending eventual carry.
77  }
78}
79
80//------------------------------------------------------------------------------
81// renormalization
82
83static const uint8_t kNorm[128] = {  // renorm_sizes[i] = 8 - log2(i)
84     7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
85  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
86  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
87  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
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  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
91  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
92  0
93};
94
95// range = ((range + 1) << kVP8Log2Range[range]) - 1
96static const uint8_t kNewRange[128] = {
97  127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239,
98  127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239,
99  247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
100  183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
101  243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
102  151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
103  181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
104  211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
105  241, 243, 245, 247, 249, 251, 253, 127
106};
107
108int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
109  const int split = (bw->range_ * prob) >> 8;
110  if (bit) {
111    bw->value_ += split + 1;
112    bw->range_ -= split + 1;
113  } else {
114    bw->range_ = split;
115  }
116  if (bw->range_ < 127) {   // emit 'shift' bits out and renormalize
117    const int shift = kNorm[bw->range_];
118    bw->range_ = kNewRange[bw->range_];
119    bw->value_ <<= shift;
120    bw->nb_bits_ += shift;
121    if (bw->nb_bits_ > 0) Flush(bw);
122  }
123  return bit;
124}
125
126int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
127  const int split = bw->range_ >> 1;
128  if (bit) {
129    bw->value_ += split + 1;
130    bw->range_ -= split + 1;
131  } else {
132    bw->range_ = split;
133  }
134  if (bw->range_ < 127) {
135    bw->range_ = kNewRange[bw->range_];
136    bw->value_ <<= 1;
137    bw->nb_bits_ += 1;
138    if (bw->nb_bits_ > 0) Flush(bw);
139  }
140  return bit;
141}
142
143void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) {
144  uint32_t mask;
145  assert(nb_bits > 0 && nb_bits < 32);
146  for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) {
147    VP8PutBitUniform(bw, value & mask);
148  }
149}
150
151void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) {
152  if (!VP8PutBitUniform(bw, value != 0)) return;
153  if (value < 0) {
154    VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1);
155  } else {
156    VP8PutBits(bw, value << 1, nb_bits + 1);
157  }
158}
159
160//------------------------------------------------------------------------------
161
162int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
163  bw->range_   = 255 - 1;
164  bw->value_   = 0;
165  bw->run_     = 0;
166  bw->nb_bits_ = -8;
167  bw->pos_     = 0;
168  bw->max_pos_ = 0;
169  bw->error_   = 0;
170  bw->buf_     = NULL;
171  return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
172}
173
174uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
175  VP8PutBits(bw, 0, 9 - bw->nb_bits_);
176  bw->nb_bits_ = 0;   // pad with zeroes
177  Flush(bw);
178  return bw->buf_;
179}
180
181int VP8BitWriterAppend(VP8BitWriter* const bw,
182                       const uint8_t* data, size_t size) {
183  assert(data != NULL);
184  if (bw->nb_bits_ != -8) return 0;   // Flush() must have been called
185  if (!BitWriterResize(bw, size)) return 0;
186  memcpy(bw->buf_ + bw->pos_, data, size);
187  bw->pos_ += size;
188  return 1;
189}
190
191void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
192  if (bw != NULL) {
193    WebPSafeFree(bw->buf_);
194    memset(bw, 0, sizeof(*bw));
195  }
196}
197
198//------------------------------------------------------------------------------
199// VP8LBitWriter
200
201// This is the minimum amount of size the memory buffer is guaranteed to grow
202// when extra space is needed.
203#define MIN_EXTRA_SIZE  (32768ULL)
204
205// Returns 1 on success.
206static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
207  uint8_t* allocated_buf;
208  size_t allocated_size;
209  const size_t max_bytes = bw->end_ - bw->buf_;
210  const size_t current_size = bw->cur_ - bw->buf_;
211  const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
212  const size_t size_required = (size_t)size_required_64b;
213  if (size_required != size_required_64b) {
214    bw->error_ = 1;
215    return 0;
216  }
217  if (max_bytes > 0 && size_required <= max_bytes) return 1;
218  allocated_size = (3 * max_bytes) >> 1;
219  if (allocated_size < size_required) allocated_size = size_required;
220  // make allocated size multiple of 1k
221  allocated_size = (((allocated_size >> 10) + 1) << 10);
222  allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
223  if (allocated_buf == NULL) {
224    bw->error_ = 1;
225    return 0;
226  }
227  if (current_size > 0) {
228    memcpy(allocated_buf, bw->buf_, current_size);
229  }
230  WebPSafeFree(bw->buf_);
231  bw->buf_ = allocated_buf;
232  bw->cur_ = bw->buf_ + current_size;
233  bw->end_ = bw->buf_ + allocated_size;
234  return 1;
235}
236
237int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
238  memset(bw, 0, sizeof(*bw));
239  return VP8LBitWriterResize(bw, expected_size);
240}
241
242int VP8LBitWriterClone(const VP8LBitWriter* const src,
243                       VP8LBitWriter* const dst) {
244  const size_t current_size = src->cur_ - src->buf_;
245  assert(src->cur_ >= src->buf_ && src->cur_ <= src->end_);
246  if (!VP8LBitWriterResize(dst, current_size)) return 0;
247  memcpy(dst->buf_, src->buf_, current_size);
248  dst->bits_ = src->bits_;
249  dst->used_ = src->used_;
250  dst->error_ = src->error_;
251  return 1;
252}
253
254void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
255  if (bw != NULL) {
256    WebPSafeFree(bw->buf_);
257    memset(bw, 0, sizeof(*bw));
258  }
259}
260
261void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
262                        VP8LBitWriter* const bw) {
263  bw->bits_ = bw_init->bits_;
264  bw->used_ = bw_init->used_;
265  bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_);
266  assert(bw->cur_ <= bw->end_);
267  bw->error_ = bw_init->error_;
268}
269
270void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
271  const VP8LBitWriter tmp = *src;
272  *src = *dst;
273  *dst = tmp;
274}
275
276void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) {
277  // If needed, make some room by flushing some bits out.
278  if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
279    const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
280    if (extra_size != (size_t)extra_size ||
281        !VP8LBitWriterResize(bw, (size_t)extra_size)) {
282      bw->cur_ = bw->buf_;
283      bw->error_ = 1;
284      return;
285    }
286  }
287  *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_);
288  bw->cur_ += VP8L_WRITER_BYTES;
289  bw->bits_ >>= VP8L_WRITER_BITS;
290  bw->used_ -= VP8L_WRITER_BITS;
291}
292
293void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) {
294  assert(n_bits <= 32);
295  // That's the max we can handle:
296  assert(sizeof(vp8l_wtype_t) == 2);
297  if (n_bits > 0) {
298    vp8l_atype_t lbits = bw->bits_;
299    int used = bw->used_;
300    // Special case of overflow handling for 32bit accumulator (2-steps flush).
301#if VP8L_WRITER_BITS == 16
302    if (used + n_bits >= VP8L_WRITER_MAX_BITS) {
303      // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below.
304      const int shift = VP8L_WRITER_MAX_BITS - used;
305      lbits |= (vp8l_atype_t)bits << used;
306      used = VP8L_WRITER_MAX_BITS;
307      n_bits -= shift;
308      bits >>= shift;
309      assert(n_bits <= VP8L_WRITER_MAX_BITS);
310    }
311#endif
312    // If needed, make some room by flushing some bits out.
313    while (used >= VP8L_WRITER_BITS) {
314      if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
315        const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
316        if (extra_size != (size_t)extra_size ||
317            !VP8LBitWriterResize(bw, (size_t)extra_size)) {
318          bw->cur_ = bw->buf_;
319          bw->error_ = 1;
320          return;
321        }
322      }
323      *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits);
324      bw->cur_ += VP8L_WRITER_BYTES;
325      lbits >>= VP8L_WRITER_BITS;
326      used -= VP8L_WRITER_BITS;
327    }
328    bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
329    bw->used_ = used + n_bits;
330  }
331}
332
333uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
334  // flush leftover bits
335  if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
336    while (bw->used_ > 0) {
337      *bw->cur_++ = (uint8_t)bw->bits_;
338      bw->bits_ >>= 8;
339      bw->used_ -= 8;
340    }
341    bw->used_ = 0;
342  }
343  return bw->buf_;
344}
345
346//------------------------------------------------------------------------------
347