1/*
2 *  Copyright 2015 The WebRTC Project Authors. All rights reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "webrtc/base/bitbuffer.h"
12
13#include <algorithm>
14#include <limits>
15
16#include "webrtc/base/checks.h"
17
18namespace {
19
20// Returns the lowest (right-most) |bit_count| bits in |byte|.
21uint8_t LowestBits(uint8_t byte, size_t bit_count) {
22  RTC_DCHECK_LE(bit_count, 8u);
23  return byte & ((1 << bit_count) - 1);
24}
25
26// Returns the highest (left-most) |bit_count| bits in |byte|, shifted to the
27// lowest bits (to the right).
28uint8_t HighestBits(uint8_t byte, size_t bit_count) {
29  RTC_DCHECK_LE(bit_count, 8u);
30  uint8_t shift = 8 - static_cast<uint8_t>(bit_count);
31  uint8_t mask = 0xFF << shift;
32  return (byte & mask) >> shift;
33}
34
35// Returns the highest byte of |val| in a uint8_t.
36uint8_t HighestByte(uint64_t val) {
37  return static_cast<uint8_t>(val >> 56);
38}
39
40// Returns the result of writing partial data from |source|, of
41// |source_bit_count| size in the highest bits, to |target| at
42// |target_bit_offset| from the highest bit.
43uint8_t WritePartialByte(uint8_t source,
44                         size_t source_bit_count,
45                         uint8_t target,
46                         size_t target_bit_offset) {
47  RTC_DCHECK(target_bit_offset < 8);
48  RTC_DCHECK(source_bit_count < 9);
49  RTC_DCHECK(source_bit_count <= (8 - target_bit_offset));
50  // Generate a mask for just the bits we're going to overwrite, so:
51  uint8_t mask =
52      // The number of bits we want, in the most significant bits...
53      static_cast<uint8_t>(0xFF << (8 - source_bit_count))
54      // ...shifted over to the target offset from the most signficant bit.
55      >> target_bit_offset;
56
57  // We want the target, with the bits we'll overwrite masked off, or'ed with
58  // the bits from the source we want.
59  return (target & ~mask) | (source >> target_bit_offset);
60}
61
62// Counts the number of bits used in the binary representation of val.
63size_t CountBits(uint64_t val) {
64  size_t bit_count = 0;
65  while (val != 0) {
66    bit_count++;
67    val >>= 1;
68  }
69  return bit_count;
70}
71
72}  // namespace
73
74namespace rtc {
75
76BitBuffer::BitBuffer(const uint8_t* bytes, size_t byte_count)
77    : bytes_(bytes), byte_count_(byte_count), byte_offset_(), bit_offset_() {
78  RTC_DCHECK(static_cast<uint64_t>(byte_count_) <=
79             std::numeric_limits<uint32_t>::max());
80}
81
82uint64_t BitBuffer::RemainingBitCount() const {
83  return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_;
84}
85
86bool BitBuffer::ReadUInt8(uint8_t* val) {
87  uint32_t bit_val;
88  if (!ReadBits(&bit_val, sizeof(uint8_t) * 8)) {
89    return false;
90  }
91  RTC_DCHECK(bit_val <= std::numeric_limits<uint8_t>::max());
92  *val = static_cast<uint8_t>(bit_val);
93  return true;
94}
95
96bool BitBuffer::ReadUInt16(uint16_t* val) {
97  uint32_t bit_val;
98  if (!ReadBits(&bit_val, sizeof(uint16_t) * 8)) {
99    return false;
100  }
101  RTC_DCHECK(bit_val <= std::numeric_limits<uint16_t>::max());
102  *val = static_cast<uint16_t>(bit_val);
103  return true;
104}
105
106bool BitBuffer::ReadUInt32(uint32_t* val) {
107  return ReadBits(val, sizeof(uint32_t) * 8);
108}
109
110bool BitBuffer::PeekBits(uint32_t* val, size_t bit_count) {
111  if (!val || bit_count > RemainingBitCount() || bit_count > 32) {
112    return false;
113  }
114  const uint8_t* bytes = bytes_ + byte_offset_;
115  size_t remaining_bits_in_current_byte = 8 - bit_offset_;
116  uint32_t bits = LowestBits(*bytes++, remaining_bits_in_current_byte);
117  // If we're reading fewer bits than what's left in the current byte, just
118  // return the portion of this byte that we need.
119  if (bit_count < remaining_bits_in_current_byte) {
120    *val = HighestBits(bits, bit_offset_ + bit_count);
121    return true;
122  }
123  // Otherwise, subtract what we've read from the bit count and read as many
124  // full bytes as we can into bits.
125  bit_count -= remaining_bits_in_current_byte;
126  while (bit_count >= 8) {
127    bits = (bits << 8) | *bytes++;
128    bit_count -= 8;
129  }
130  // Whatever we have left is smaller than a byte, so grab just the bits we need
131  // and shift them into the lowest bits.
132  if (bit_count > 0) {
133    bits <<= bit_count;
134    bits |= HighestBits(*bytes, bit_count);
135  }
136  *val = bits;
137  return true;
138}
139
140bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) {
141  return PeekBits(val, bit_count) && ConsumeBits(bit_count);
142}
143
144bool BitBuffer::ConsumeBytes(size_t byte_count) {
145  return ConsumeBits(byte_count * 8);
146}
147
148bool BitBuffer::ConsumeBits(size_t bit_count) {
149  if (bit_count > RemainingBitCount()) {
150    return false;
151  }
152
153  byte_offset_ += (bit_offset_ + bit_count) / 8;
154  bit_offset_ = (bit_offset_ + bit_count) % 8;
155  return true;
156}
157
158bool BitBuffer::ReadExponentialGolomb(uint32_t* val) {
159  if (!val) {
160    return false;
161  }
162  // Store off the current byte/bit offset, in case we want to restore them due
163  // to a failed parse.
164  size_t original_byte_offset = byte_offset_;
165  size_t original_bit_offset = bit_offset_;
166
167  // Count the number of leading 0 bits by peeking/consuming them one at a time.
168  size_t zero_bit_count = 0;
169  uint32_t peeked_bit;
170  while (PeekBits(&peeked_bit, 1) && peeked_bit == 0) {
171    zero_bit_count++;
172    ConsumeBits(1);
173  }
174
175  // We should either be at the end of the stream, or the next bit should be 1.
176  RTC_DCHECK(!PeekBits(&peeked_bit, 1) || peeked_bit == 1);
177
178  // The bit count of the value is the number of zeros + 1. Make sure that many
179  // bits fits in a uint32_t and that we have enough bits left for it, and then
180  // read the value.
181  size_t value_bit_count = zero_bit_count + 1;
182  if (value_bit_count > 32 || !ReadBits(val, value_bit_count)) {
183    RTC_CHECK(Seek(original_byte_offset, original_bit_offset));
184    return false;
185  }
186  *val -= 1;
187  return true;
188}
189
190bool BitBuffer::ReadSignedExponentialGolomb(int32_t* val) {
191  uint32_t unsigned_val;
192  if (!ReadExponentialGolomb(&unsigned_val)) {
193    return false;
194  }
195  if ((unsigned_val & 1) == 0) {
196    *val = -static_cast<int32_t>(unsigned_val / 2);
197  } else {
198    *val = (unsigned_val + 1) / 2;
199  }
200  return true;
201}
202
203void BitBuffer::GetCurrentOffset(
204    size_t* out_byte_offset, size_t* out_bit_offset) {
205  RTC_CHECK(out_byte_offset != NULL);
206  RTC_CHECK(out_bit_offset != NULL);
207  *out_byte_offset = byte_offset_;
208  *out_bit_offset = bit_offset_;
209}
210
211bool BitBuffer::Seek(size_t byte_offset, size_t bit_offset) {
212  if (byte_offset > byte_count_ || bit_offset > 7 ||
213      (byte_offset == byte_count_ && bit_offset > 0)) {
214    return false;
215  }
216  byte_offset_ = byte_offset;
217  bit_offset_ = bit_offset;
218  return true;
219}
220
221BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count)
222    : BitBuffer(bytes, byte_count), writable_bytes_(bytes) {
223}
224
225bool BitBufferWriter::WriteUInt8(uint8_t val) {
226  return WriteBits(val, sizeof(uint8_t) * 8);
227}
228
229bool BitBufferWriter::WriteUInt16(uint16_t val) {
230  return WriteBits(val, sizeof(uint16_t) * 8);
231}
232
233bool BitBufferWriter::WriteUInt32(uint32_t val) {
234  return WriteBits(val, sizeof(uint32_t) * 8);
235}
236
237bool BitBufferWriter::WriteBits(uint64_t val, size_t bit_count) {
238  if (bit_count > RemainingBitCount()) {
239    return false;
240  }
241  size_t total_bits = bit_count;
242
243  // For simplicity, push the bits we want to read from val to the highest bits.
244  val <<= (sizeof(uint64_t) * 8 - bit_count);
245
246  uint8_t* bytes = writable_bytes_ + byte_offset_;
247
248  // The first byte is relatively special; the bit offset to write to may put us
249  // in the middle of the byte, and the total bit count to write may require we
250  // save the bits at the end of the byte.
251  size_t remaining_bits_in_current_byte = 8 - bit_offset_;
252  size_t bits_in_first_byte =
253      std::min(bit_count, remaining_bits_in_current_byte);
254  *bytes = WritePartialByte(
255      HighestByte(val), bits_in_first_byte, *bytes, bit_offset_);
256  if (bit_count <= remaining_bits_in_current_byte) {
257    // Nothing left to write, so quit early.
258    return ConsumeBits(total_bits);
259  }
260
261  // Subtract what we've written from the bit count, shift it off the value, and
262  // write the remaining full bytes.
263  val <<= bits_in_first_byte;
264  bytes++;
265  bit_count -= bits_in_first_byte;
266  while (bit_count >= 8) {
267    *bytes++ = HighestByte(val);
268    val <<= 8;
269    bit_count -= 8;
270  }
271
272  // Last byte may also be partial, so write the remaining bits from the top of
273  // val.
274  if (bit_count > 0) {
275    *bytes = WritePartialByte(HighestByte(val), bit_count, *bytes, 0);
276  }
277
278  // All done! Consume the bits we've written.
279  return ConsumeBits(total_bits);
280}
281
282bool BitBufferWriter::WriteExponentialGolomb(uint32_t val) {
283  // We don't support reading UINT32_MAX, because it doesn't fit in a uint32_t
284  // when encoded, so don't support writing it either.
285  if (val == std::numeric_limits<uint32_t>::max()) {
286    return false;
287  }
288  uint64_t val_to_encode = static_cast<uint64_t>(val) + 1;
289
290  // We need to write CountBits(val+1) 0s and then val+1. Since val (as a
291  // uint64_t) has leading zeros, we can just write the total golomb encoded
292  // size worth of bits, knowing the value will appear last.
293  return WriteBits(val_to_encode, CountBits(val_to_encode) * 2 - 1);
294}
295
296}  // namespace rtc
297