blob: fd57e136b4c42dc1017118a32530fdf93945b5cd [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
Danil Chapovalov09fb7872021-08-20 10:46:1416#include "absl/numeric/bits.h"
philipel579a7b42023-03-02 10:51:5317#include "absl/strings/string_view.h"
Mirko Bonadei92ea95e2017-09-15 04:47:3118#include "rtc_base/checks.h"
Noah Richardsbbf7c862015-04-21 23:30:1319
20namespace {
21
Artem Titov96e3b992021-07-26 14:03:1422// Returns the highest byte of `val` in a uint8_t.
Noah Richards9b9f1c42015-05-12 19:20:4723uint8_t HighestByte(uint64_t val) {
24 return static_cast<uint8_t>(val >> 56);
Noah Richards86153c22015-04-28 22:13:4425}
26
Artem Titov96e3b992021-07-26 14:03:1427// Returns the result of writing partial data from `source`, of
28// `source_bit_count` size in the highest bits, to `target` at
29// `target_bit_offset` from the highest bit.
Noah Richards9b9f1c42015-05-12 19:20:4730uint8_t WritePartialByte(uint8_t source,
31 size_t source_bit_count,
32 uint8_t target,
33 size_t target_bit_offset) {
henrikg91d6ede2015-09-17 07:24:3434 RTC_DCHECK(target_bit_offset < 8);
35 RTC_DCHECK(source_bit_count < 9);
36 RTC_DCHECK(source_bit_count <= (8 - target_bit_offset));
Noah Richards86153c22015-04-28 22:13:4437 // Generate a mask for just the bits we're going to overwrite, so:
Noah Richards9b9f1c42015-05-12 19:20:4738 uint8_t mask =
Noah Richards86153c22015-04-28 22:13:4439 // The number of bits we want, in the most significant bits...
Noah Richards9b9f1c42015-05-12 19:20:4740 static_cast<uint8_t>(0xFF << (8 - source_bit_count))
Noah Richards86153c22015-04-28 22:13:4441 // ...shifted over to the target offset from the most signficant bit.
42 >> target_bit_offset;
43
44 // We want the target, with the bits we'll overwrite masked off, or'ed with
45 // the bits from the source we want.
46 return (target & ~mask) | (source >> target_bit_offset);
47}
48
Noah Richardsbbf7c862015-04-21 23:30:1349} // namespace
50
51namespace rtc {
52
Danil Chapovalov48f95252021-09-16 11:20:4853BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count)
54 : writable_bytes_(bytes),
55 byte_count_(byte_count),
56 byte_offset_(),
57 bit_offset_() {
henrikg91d6ede2015-09-17 07:24:3458 RTC_DCHECK(static_cast<uint64_t>(byte_count_) <=
59 std::numeric_limits<uint32_t>::max());
Noah Richardsbbf7c862015-04-21 23:30:1360}
61
Danil Chapovalov48f95252021-09-16 11:20:4862uint64_t BitBufferWriter::RemainingBitCount() const {
Noah Richards9b9f1c42015-05-12 19:20:4763 return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_;
Noah Richardsbbf7c862015-04-21 23:30:1364}
65
Danil Chapovalov48f95252021-09-16 11:20:4866bool BitBufferWriter::ConsumeBytes(size_t byte_count) {
Noah Richardsbbf7c862015-04-21 23:30:1367 return ConsumeBits(byte_count * 8);
68}
69
Danil Chapovalov48f95252021-09-16 11:20:4870bool BitBufferWriter::ConsumeBits(size_t bit_count) {
Noah Richardsbbf7c862015-04-21 23:30:1371 if (bit_count > RemainingBitCount()) {
72 return false;
73 }
74
75 byte_offset_ += (bit_offset_ + bit_count) / 8;
76 bit_offset_ = (bit_offset_ + bit_count) % 8;
77 return true;
78}
79
Danil Chapovalov48f95252021-09-16 11:20:4880void BitBufferWriter::GetCurrentOffset(size_t* out_byte_offset,
81 size_t* out_bit_offset) {
deadbeef37f5ecf2017-02-27 22:06:4182 RTC_CHECK(out_byte_offset != nullptr);
83 RTC_CHECK(out_bit_offset != nullptr);
Noah Richards86153c22015-04-28 22:13:4484 *out_byte_offset = byte_offset_;
85 *out_bit_offset = bit_offset_;
86}
87
Danil Chapovalov48f95252021-09-16 11:20:4888bool BitBufferWriter::Seek(size_t byte_offset, size_t bit_offset) {
Noah Richards86153c22015-04-28 22:13:4489 if (byte_offset > byte_count_ || bit_offset > 7 ||
90 (byte_offset == byte_count_ && bit_offset > 0)) {
91 return false;
92 }
93 byte_offset_ = byte_offset;
94 bit_offset_ = bit_offset;
95 return true;
96}
97
Noah Richards9b9f1c42015-05-12 19:20:4798bool BitBufferWriter::WriteUInt8(uint8_t val) {
99 return WriteBits(val, sizeof(uint8_t) * 8);
Noah Richards86153c22015-04-28 22:13:44100}
101
Noah Richards9b9f1c42015-05-12 19:20:47102bool BitBufferWriter::WriteUInt16(uint16_t val) {
103 return WriteBits(val, sizeof(uint16_t) * 8);
Noah Richards86153c22015-04-28 22:13:44104}
105
Noah Richards9b9f1c42015-05-12 19:20:47106bool BitBufferWriter::WriteUInt32(uint32_t val) {
107 return WriteBits(val, sizeof(uint32_t) * 8);
Noah Richards86153c22015-04-28 22:13:44108}
109
Noah Richards9b9f1c42015-05-12 19:20:47110bool BitBufferWriter::WriteBits(uint64_t val, size_t bit_count) {
Noah Richards86153c22015-04-28 22:13:44111 if (bit_count > RemainingBitCount()) {
112 return false;
113 }
114 size_t total_bits = bit_count;
115
116 // For simplicity, push the bits we want to read from val to the highest bits.
Noah Richards9b9f1c42015-05-12 19:20:47117 val <<= (sizeof(uint64_t) * 8 - bit_count);
Noah Richards86153c22015-04-28 22:13:44118
Noah Richards9b9f1c42015-05-12 19:20:47119 uint8_t* bytes = writable_bytes_ + byte_offset_;
Noah Richards86153c22015-04-28 22:13:44120
121 // The first byte is relatively special; the bit offset to write to may put us
122 // in the middle of the byte, and the total bit count to write may require we
123 // save the bits at the end of the byte.
124 size_t remaining_bits_in_current_byte = 8 - bit_offset_;
125 size_t bits_in_first_byte =
126 std::min(bit_count, remaining_bits_in_current_byte);
Yves Gerey665174f2018-06-19 13:03:05127 *bytes = WritePartialByte(HighestByte(val), bits_in_first_byte, *bytes,
128 bit_offset_);
Noah Richards86153c22015-04-28 22:13:44129 if (bit_count <= remaining_bits_in_current_byte) {
130 // Nothing left to write, so quit early.
131 return ConsumeBits(total_bits);
132 }
133
134 // Subtract what we've written from the bit count, shift it off the value, and
135 // write the remaining full bytes.
136 val <<= bits_in_first_byte;
137 bytes++;
138 bit_count -= bits_in_first_byte;
139 while (bit_count >= 8) {
140 *bytes++ = HighestByte(val);
141 val <<= 8;
142 bit_count -= 8;
143 }
144
145 // Last byte may also be partial, so write the remaining bits from the top of
146 // val.
147 if (bit_count > 0) {
148 *bytes = WritePartialByte(HighestByte(val), bit_count, *bytes, 0);
149 }
150
151 // All done! Consume the bits we've written.
152 return ConsumeBits(total_bits);
153}
154
Danil Chapovalova2b30d82019-07-03 12:41:50155bool BitBufferWriter::WriteNonSymmetric(uint32_t val, uint32_t num_values) {
156 RTC_DCHECK_LT(val, num_values);
157 RTC_DCHECK_LE(num_values, uint32_t{1} << 31);
Danil Chapovalova9e1b492020-07-08 09:24:19158 if (num_values == 1) {
159 // When there is only one possible value, it requires zero bits to store it.
160 // But WriteBits doesn't support writing zero bits.
161 return true;
162 }
Danil Chapovalov09fb7872021-08-20 10:46:14163 size_t count_bits = absl::bit_width(num_values);
Danil Chapovalova2b30d82019-07-03 12:41:50164 uint32_t num_min_bits_values = (uint32_t{1} << count_bits) - num_values;
165
166 return val < num_min_bits_values
167 ? WriteBits(val, count_bits - 1)
168 : WriteBits(val + num_min_bits_values, count_bits);
169}
170
171size_t BitBufferWriter::SizeNonSymmetricBits(uint32_t val,
172 uint32_t num_values) {
173 RTC_DCHECK_LT(val, num_values);
174 RTC_DCHECK_LE(num_values, uint32_t{1} << 31);
Danil Chapovalov09fb7872021-08-20 10:46:14175 size_t count_bits = absl::bit_width(num_values);
Danil Chapovalova2b30d82019-07-03 12:41:50176 uint32_t num_min_bits_values = (uint32_t{1} << count_bits) - num_values;
177
178 return val < num_min_bits_values ? (count_bits - 1) : count_bits;
179}
180
Noah Richards9b9f1c42015-05-12 19:20:47181bool BitBufferWriter::WriteExponentialGolomb(uint32_t val) {
182 // We don't support reading UINT32_MAX, because it doesn't fit in a uint32_t
Noah Richards86153c22015-04-28 22:13:44183 // when encoded, so don't support writing it either.
Noah Richards9b9f1c42015-05-12 19:20:47184 if (val == std::numeric_limits<uint32_t>::max()) {
Noah Richards86153c22015-04-28 22:13:44185 return false;
186 }
Noah Richards9b9f1c42015-05-12 19:20:47187 uint64_t val_to_encode = static_cast<uint64_t>(val) + 1;
Noah Richards86153c22015-04-28 22:13:44188
Danil Chapovalov09fb7872021-08-20 10:46:14189 // We need to write bit_width(val+1) 0s and then val+1. Since val (as a
Noah Richards9b9f1c42015-05-12 19:20:47190 // uint64_t) has leading zeros, we can just write the total golomb encoded
191 // size worth of bits, knowing the value will appear last.
Danil Chapovalov09fb7872021-08-20 10:46:14192 return WriteBits(val_to_encode, absl::bit_width(val_to_encode) * 2 - 1);
Noah Richards86153c22015-04-28 22:13:44193}
194
sprang52033d62016-06-02 09:43:32195bool BitBufferWriter::WriteSignedExponentialGolomb(int32_t val) {
196 if (val == 0) {
197 return WriteExponentialGolomb(0);
198 } else if (val > 0) {
199 uint32_t signed_val = val;
200 return WriteExponentialGolomb((signed_val * 2) - 1);
201 } else {
202 if (val == std::numeric_limits<int32_t>::min())
203 return false; // Not supported, would cause overflow.
204 uint32_t signed_val = -val;
205 return WriteExponentialGolomb(signed_val * 2);
206 }
207}
208
philipel579a7b42023-03-02 10:51:53209bool BitBufferWriter::WriteLeb128(uint64_t val) {
210 bool success = true;
211 do {
212 uint8_t byte = static_cast<uint8_t>(val & 0x7f);
213 val >>= 7;
214 if (val > 0) {
215 byte |= 0x80;
216 }
217 success &= WriteUInt8(byte);
218 } while (val > 0);
219 return success;
220}
221
222bool BitBufferWriter::WriteString(absl::string_view data) {
223 bool success = true;
224 for (char c : data) {
225 success &= WriteUInt8(c);
226 }
227 return success;
228}
229
Noah Richardsbbf7c862015-04-21 23:30:13230} // namespace rtc