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