blob: 59b71fcb4468ab64d55222b1aa967998cf145675 [file] [log] [blame]
Noah Richardsbbf7c862015-04-21 23:30:131/*
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
Steve Anton10542f22019-01-11 17:11:0011#include "rtc_base/bit_buffer.h"
Noah Richardsbbf7c862015-04-21 23:30:1312
Noah Richards86153c22015-04-28 22:13:4413#include <algorithm>
Noah Richardsbbf7c862015-04-21 23:30:1314#include <limits>
15
Mirko Bonadei92ea95e2017-09-15 04:47:3116#include "rtc_base/checks.h"
Noah Richardsbbf7c862015-04-21 23:30:1317
18namespace {
19
20// Returns the lowest (right-most) |bit_count| bits in |byte|.
Noah Richards9b9f1c42015-05-12 19:20:4721uint8_t LowestBits(uint8_t byte, size_t bit_count) {
kwibergaf476c72016-11-28 23:21:3922 RTC_DCHECK_LE(bit_count, 8);
Noah Richards86153c22015-04-28 22:13:4423 return byte & ((1 << bit_count) - 1);
Noah Richardsbbf7c862015-04-21 23:30:1324}
25
26// Returns the highest (left-most) |bit_count| bits in |byte|, shifted to the
27// lowest bits (to the right).
Noah Richards9b9f1c42015-05-12 19:20:4728uint8_t HighestBits(uint8_t byte, size_t bit_count) {
kwibergaf476c72016-11-28 23:21:3929 RTC_DCHECK_LE(bit_count, 8);
Noah Richards9b9f1c42015-05-12 19:20:4730 uint8_t shift = 8 - static_cast<uint8_t>(bit_count);
31 uint8_t mask = 0xFF << shift;
Noah Richardsbbf7c862015-04-21 23:30:1332 return (byte & mask) >> shift;
33}
34
Noah Richards9b9f1c42015-05-12 19:20:4735// Returns the highest byte of |val| in a uint8_t.
36uint8_t HighestByte(uint64_t val) {
37 return static_cast<uint8_t>(val >> 56);
Noah Richards86153c22015-04-28 22:13:4438}
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.
Noah Richards9b9f1c42015-05-12 19:20:4743uint8_t WritePartialByte(uint8_t source,
44 size_t source_bit_count,
45 uint8_t target,
46 size_t target_bit_offset) {
henrikg91d6ede2015-09-17 07:24:3447 RTC_DCHECK(target_bit_offset < 8);
48 RTC_DCHECK(source_bit_count < 9);
49 RTC_DCHECK(source_bit_count <= (8 - target_bit_offset));
Noah Richards86153c22015-04-28 22:13:4450 // Generate a mask for just the bits we're going to overwrite, so:
Noah Richards9b9f1c42015-05-12 19:20:4751 uint8_t mask =
Noah Richards86153c22015-04-28 22:13:4452 // The number of bits we want, in the most significant bits...
Noah Richards9b9f1c42015-05-12 19:20:4753 static_cast<uint8_t>(0xFF << (8 - source_bit_count))
Noah Richards86153c22015-04-28 22:13:4454 // ...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.
Noah Richards9b9f1c42015-05-12 19:20:4763size_t CountBits(uint64_t val) {
Noah Richards86153c22015-04-28 22:13:4464 size_t bit_count = 0;
65 while (val != 0) {
66 bit_count++;
67 val >>= 1;
68 }
69 return bit_count;
70}
71
Noah Richardsbbf7c862015-04-21 23:30:1372} // namespace
73
74namespace rtc {
75
Noah Richards9b9f1c42015-05-12 19:20:4776BitBuffer::BitBuffer(const uint8_t* bytes, size_t byte_count)
Noah Richardsbbf7c862015-04-21 23:30:1377 : bytes_(bytes), byte_count_(byte_count), byte_offset_(), bit_offset_() {
henrikg91d6ede2015-09-17 07:24:3478 RTC_DCHECK(static_cast<uint64_t>(byte_count_) <=
79 std::numeric_limits<uint32_t>::max());
Noah Richardsbbf7c862015-04-21 23:30:1380}
81
Noah Richards9b9f1c42015-05-12 19:20:4782uint64_t BitBuffer::RemainingBitCount() const {
83 return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_;
Noah Richardsbbf7c862015-04-21 23:30:1384}
85
Noah Richards9b9f1c42015-05-12 19:20:4786bool BitBuffer::ReadUInt8(uint8_t* val) {
87 uint32_t bit_val;
88 if (!ReadBits(&bit_val, sizeof(uint8_t) * 8)) {
Noah Richardsbbf7c862015-04-21 23:30:1389 return false;
90 }
henrikg91d6ede2015-09-17 07:24:3491 RTC_DCHECK(bit_val <= std::numeric_limits<uint8_t>::max());
Noah Richards9b9f1c42015-05-12 19:20:4792 *val = static_cast<uint8_t>(bit_val);
Noah Richardsbbf7c862015-04-21 23:30:1393 return true;
94}
95
Noah Richards9b9f1c42015-05-12 19:20:4796bool BitBuffer::ReadUInt16(uint16_t* val) {
97 uint32_t bit_val;
98 if (!ReadBits(&bit_val, sizeof(uint16_t) * 8)) {
Noah Richardsbbf7c862015-04-21 23:30:1399 return false;
100 }
henrikg91d6ede2015-09-17 07:24:34101 RTC_DCHECK(bit_val <= std::numeric_limits<uint16_t>::max());
Noah Richards9b9f1c42015-05-12 19:20:47102 *val = static_cast<uint16_t>(bit_val);
Noah Richardsbbf7c862015-04-21 23:30:13103 return true;
104}
105
Noah Richards9b9f1c42015-05-12 19:20:47106bool BitBuffer::ReadUInt32(uint32_t* val) {
107 return ReadBits(val, sizeof(uint32_t) * 8);
Noah Richardsbbf7c862015-04-21 23:30:13108}
109
Noah Richards9b9f1c42015-05-12 19:20:47110bool BitBuffer::PeekBits(uint32_t* val, size_t bit_count) {
Niels Möller827cf3c2018-09-27 09:02:08111 // TODO(nisse): Could allow bit_count == 0 and always return success. But
112 // current code reads one byte beyond end of buffer in the case that
113 // RemainingBitCount() == 0 and bit_count == 0.
114 RTC_DCHECK(bit_count > 0);
Noah Richardsbbf7c862015-04-21 23:30:13115 if (!val || bit_count > RemainingBitCount() || bit_count > 32) {
116 return false;
117 }
Noah Richards9b9f1c42015-05-12 19:20:47118 const uint8_t* bytes = bytes_ + byte_offset_;
Noah Richardsbbf7c862015-04-21 23:30:13119 size_t remaining_bits_in_current_byte = 8 - bit_offset_;
Noah Richards9b9f1c42015-05-12 19:20:47120 uint32_t bits = LowestBits(*bytes++, remaining_bits_in_current_byte);
Noah Richardsbbf7c862015-04-21 23:30:13121 // If we're reading fewer bits than what's left in the current byte, just
122 // return the portion of this byte that we need.
123 if (bit_count < remaining_bits_in_current_byte) {
124 *val = HighestBits(bits, bit_offset_ + bit_count);
125 return true;
126 }
127 // Otherwise, subtract what we've read from the bit count and read as many
128 // full bytes as we can into bits.
129 bit_count -= remaining_bits_in_current_byte;
130 while (bit_count >= 8) {
131 bits = (bits << 8) | *bytes++;
132 bit_count -= 8;
133 }
134 // Whatever we have left is smaller than a byte, so grab just the bits we need
135 // and shift them into the lowest bits.
136 if (bit_count > 0) {
137 bits <<= bit_count;
138 bits |= HighestBits(*bytes, bit_count);
139 }
140 *val = bits;
141 return true;
142}
143
Noah Richards9b9f1c42015-05-12 19:20:47144bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) {
Noah Richardsbbf7c862015-04-21 23:30:13145 return PeekBits(val, bit_count) && ConsumeBits(bit_count);
146}
147
148bool BitBuffer::ConsumeBytes(size_t byte_count) {
149 return ConsumeBits(byte_count * 8);
150}
151
152bool BitBuffer::ConsumeBits(size_t bit_count) {
153 if (bit_count > RemainingBitCount()) {
154 return false;
155 }
156
157 byte_offset_ += (bit_offset_ + bit_count) / 8;
158 bit_offset_ = (bit_offset_ + bit_count) % 8;
159 return true;
160}
161
Noah Richards9b9f1c42015-05-12 19:20:47162bool BitBuffer::ReadExponentialGolomb(uint32_t* val) {
Noah Richardsbbf7c862015-04-21 23:30:13163 if (!val) {
164 return false;
165 }
166 // Store off the current byte/bit offset, in case we want to restore them due
167 // to a failed parse.
168 size_t original_byte_offset = byte_offset_;
169 size_t original_bit_offset = bit_offset_;
170
171 // Count the number of leading 0 bits by peeking/consuming them one at a time.
172 size_t zero_bit_count = 0;
Noah Richards9b9f1c42015-05-12 19:20:47173 uint32_t peeked_bit;
Noah Richardsbbf7c862015-04-21 23:30:13174 while (PeekBits(&peeked_bit, 1) && peeked_bit == 0) {
175 zero_bit_count++;
176 ConsumeBits(1);
177 }
178
179 // We should either be at the end of the stream, or the next bit should be 1.
henrikg91d6ede2015-09-17 07:24:34180 RTC_DCHECK(!PeekBits(&peeked_bit, 1) || peeked_bit == 1);
Noah Richardsbbf7c862015-04-21 23:30:13181
182 // The bit count of the value is the number of zeros + 1. Make sure that many
Noah Richards9b9f1c42015-05-12 19:20:47183 // bits fits in a uint32_t and that we have enough bits left for it, and then
Noah Richardsbbf7c862015-04-21 23:30:13184 // read the value.
185 size_t value_bit_count = zero_bit_count + 1;
186 if (value_bit_count > 32 || !ReadBits(val, value_bit_count)) {
henrikg91d6ede2015-09-17 07:24:34187 RTC_CHECK(Seek(original_byte_offset, original_bit_offset));
Noah Richardsbbf7c862015-04-21 23:30:13188 return false;
189 }
190 *val -= 1;
191 return true;
192}
193
Peter Boström8c266e62015-09-24 13:06:50194bool BitBuffer::ReadSignedExponentialGolomb(int32_t* val) {
195 uint32_t unsigned_val;
196 if (!ReadExponentialGolomb(&unsigned_val)) {
197 return false;
198 }
199 if ((unsigned_val & 1) == 0) {
200 *val = -static_cast<int32_t>(unsigned_val / 2);
201 } else {
202 *val = (unsigned_val + 1) / 2;
203 }
204 return true;
205}
206
Yves Gerey665174f2018-06-19 13:03:05207void BitBuffer::GetCurrentOffset(size_t* out_byte_offset,
208 size_t* out_bit_offset) {
deadbeef37f5ecf2017-02-27 22:06:41209 RTC_CHECK(out_byte_offset != nullptr);
210 RTC_CHECK(out_bit_offset != nullptr);
Noah Richards86153c22015-04-28 22:13:44211 *out_byte_offset = byte_offset_;
212 *out_bit_offset = bit_offset_;
213}
214
215bool BitBuffer::Seek(size_t byte_offset, size_t bit_offset) {
216 if (byte_offset > byte_count_ || bit_offset > 7 ||
217 (byte_offset == byte_count_ && bit_offset > 0)) {
218 return false;
219 }
220 byte_offset_ = byte_offset;
221 bit_offset_ = bit_offset;
222 return true;
223}
224
Noah Richards9b9f1c42015-05-12 19:20:47225BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count)
Yves Gerey665174f2018-06-19 13:03:05226 : BitBuffer(bytes, byte_count), writable_bytes_(bytes) {}
Noah Richards86153c22015-04-28 22:13:44227
Noah Richards9b9f1c42015-05-12 19:20:47228bool BitBufferWriter::WriteUInt8(uint8_t val) {
229 return WriteBits(val, sizeof(uint8_t) * 8);
Noah Richards86153c22015-04-28 22:13:44230}
231
Noah Richards9b9f1c42015-05-12 19:20:47232bool BitBufferWriter::WriteUInt16(uint16_t val) {
233 return WriteBits(val, sizeof(uint16_t) * 8);
Noah Richards86153c22015-04-28 22:13:44234}
235
Noah Richards9b9f1c42015-05-12 19:20:47236bool BitBufferWriter::WriteUInt32(uint32_t val) {
237 return WriteBits(val, sizeof(uint32_t) * 8);
Noah Richards86153c22015-04-28 22:13:44238}
239
Noah Richards9b9f1c42015-05-12 19:20:47240bool BitBufferWriter::WriteBits(uint64_t val, size_t bit_count) {
Noah Richards86153c22015-04-28 22:13:44241 if (bit_count > RemainingBitCount()) {
242 return false;
243 }
244 size_t total_bits = bit_count;
245
246 // For simplicity, push the bits we want to read from val to the highest bits.
Noah Richards9b9f1c42015-05-12 19:20:47247 val <<= (sizeof(uint64_t) * 8 - bit_count);
Noah Richards86153c22015-04-28 22:13:44248
Noah Richards9b9f1c42015-05-12 19:20:47249 uint8_t* bytes = writable_bytes_ + byte_offset_;
Noah Richards86153c22015-04-28 22:13:44250
251 // The first byte is relatively special; the bit offset to write to may put us
252 // in the middle of the byte, and the total bit count to write may require we
253 // save the bits at the end of the byte.
254 size_t remaining_bits_in_current_byte = 8 - bit_offset_;
255 size_t bits_in_first_byte =
256 std::min(bit_count, remaining_bits_in_current_byte);
Yves Gerey665174f2018-06-19 13:03:05257 *bytes = WritePartialByte(HighestByte(val), bits_in_first_byte, *bytes,
258 bit_offset_);
Noah Richards86153c22015-04-28 22:13:44259 if (bit_count <= remaining_bits_in_current_byte) {
260 // Nothing left to write, so quit early.
261 return ConsumeBits(total_bits);
262 }
263
264 // Subtract what we've written from the bit count, shift it off the value, and
265 // write the remaining full bytes.
266 val <<= bits_in_first_byte;
267 bytes++;
268 bit_count -= bits_in_first_byte;
269 while (bit_count >= 8) {
270 *bytes++ = HighestByte(val);
271 val <<= 8;
272 bit_count -= 8;
273 }
274
275 // Last byte may also be partial, so write the remaining bits from the top of
276 // val.
277 if (bit_count > 0) {
278 *bytes = WritePartialByte(HighestByte(val), bit_count, *bytes, 0);
279 }
280
281 // All done! Consume the bits we've written.
282 return ConsumeBits(total_bits);
283}
284
Noah Richards9b9f1c42015-05-12 19:20:47285bool BitBufferWriter::WriteExponentialGolomb(uint32_t val) {
286 // We don't support reading UINT32_MAX, because it doesn't fit in a uint32_t
Noah Richards86153c22015-04-28 22:13:44287 // when encoded, so don't support writing it either.
Noah Richards9b9f1c42015-05-12 19:20:47288 if (val == std::numeric_limits<uint32_t>::max()) {
Noah Richards86153c22015-04-28 22:13:44289 return false;
290 }
Noah Richards9b9f1c42015-05-12 19:20:47291 uint64_t val_to_encode = static_cast<uint64_t>(val) + 1;
Noah Richards86153c22015-04-28 22:13:44292
293 // We need to write CountBits(val+1) 0s and then val+1. Since val (as a
Noah Richards9b9f1c42015-05-12 19:20:47294 // uint64_t) has leading zeros, we can just write the total golomb encoded
295 // size worth of bits, knowing the value will appear last.
Noah Richards86153c22015-04-28 22:13:44296 return WriteBits(val_to_encode, CountBits(val_to_encode) * 2 - 1);
297}
298
sprang52033d62016-06-02 09:43:32299bool BitBufferWriter::WriteSignedExponentialGolomb(int32_t val) {
300 if (val == 0) {
301 return WriteExponentialGolomb(0);
302 } else if (val > 0) {
303 uint32_t signed_val = val;
304 return WriteExponentialGolomb((signed_val * 2) - 1);
305 } else {
306 if (val == std::numeric_limits<int32_t>::min())
307 return false; // Not supported, would cause overflow.
308 uint32_t signed_val = -val;
309 return WriteExponentialGolomb(signed_val * 2);
310 }
311}
312
Noah Richardsbbf7c862015-04-21 23:30:13313} // namespace rtc