Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 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 | |
Steve Anton | 10542f2 | 2019-01-11 17:11:00 | [diff] [blame] | 11 | #include "rtc_base/bit_buffer.h" |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 12 | |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 13 | #include <algorithm> |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 14 | #include <limits> |
| 15 | |
Danil Chapovalov | 09fb787 | 2021-08-20 10:46:14 | [diff] [blame] | 16 | #include "absl/numeric/bits.h" |
philipel | 579a7b4 | 2023-03-02 10:51:53 | [diff] [blame] | 17 | #include "absl/strings/string_view.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 04:47:31 | [diff] [blame] | 18 | #include "rtc_base/checks.h" |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 19 | |
| 20 | namespace { |
| 21 | |
Artem Titov | 96e3b99 | 2021-07-26 14:03:14 | [diff] [blame] | 22 | // Returns the highest byte of `val` in a uint8_t. |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 23 | uint8_t HighestByte(uint64_t val) { |
| 24 | return static_cast<uint8_t>(val >> 56); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 25 | } |
| 26 | |
Artem Titov | 96e3b99 | 2021-07-26 14:03:14 | [diff] [blame] | 27 | // 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 Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 30 | uint8_t WritePartialByte(uint8_t source, |
| 31 | size_t source_bit_count, |
| 32 | uint8_t target, |
| 33 | size_t target_bit_offset) { |
henrikg | 91d6ede | 2015-09-17 07:24:34 | [diff] [blame] | 34 | RTC_DCHECK(target_bit_offset < 8); |
| 35 | RTC_DCHECK(source_bit_count < 9); |
| 36 | RTC_DCHECK(source_bit_count <= (8 - target_bit_offset)); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 37 | // Generate a mask for just the bits we're going to overwrite, so: |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 38 | uint8_t mask = |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 39 | // The number of bits we want, in the most significant bits... |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 40 | static_cast<uint8_t>(0xFF << (8 - source_bit_count)) |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 41 | // ...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 Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 49 | } // namespace |
| 50 | |
| 51 | namespace rtc { |
| 52 | |
Danil Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 53 | BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count) |
| 54 | : writable_bytes_(bytes), |
| 55 | byte_count_(byte_count), |
| 56 | byte_offset_(), |
| 57 | bit_offset_() { |
henrikg | 91d6ede | 2015-09-17 07:24:34 | [diff] [blame] | 58 | RTC_DCHECK(static_cast<uint64_t>(byte_count_) <= |
| 59 | std::numeric_limits<uint32_t>::max()); |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 60 | } |
| 61 | |
Danil Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 62 | uint64_t BitBufferWriter::RemainingBitCount() const { |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 63 | return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_; |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 64 | } |
| 65 | |
Danil Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 66 | bool BitBufferWriter::ConsumeBytes(size_t byte_count) { |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 67 | return ConsumeBits(byte_count * 8); |
| 68 | } |
| 69 | |
Danil Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 70 | bool BitBufferWriter::ConsumeBits(size_t bit_count) { |
Noah Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 71 | 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 Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 80 | void BitBufferWriter::GetCurrentOffset(size_t* out_byte_offset, |
| 81 | size_t* out_bit_offset) { |
deadbeef | 37f5ecf | 2017-02-27 22:06:41 | [diff] [blame] | 82 | RTC_CHECK(out_byte_offset != nullptr); |
| 83 | RTC_CHECK(out_bit_offset != nullptr); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 84 | *out_byte_offset = byte_offset_; |
| 85 | *out_bit_offset = bit_offset_; |
| 86 | } |
| 87 | |
Danil Chapovalov | 48f9525 | 2021-09-16 11:20:48 | [diff] [blame] | 88 | bool BitBufferWriter::Seek(size_t byte_offset, size_t bit_offset) { |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 89 | 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 Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 98 | bool BitBufferWriter::WriteUInt8(uint8_t val) { |
| 99 | return WriteBits(val, sizeof(uint8_t) * 8); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 100 | } |
| 101 | |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 102 | bool BitBufferWriter::WriteUInt16(uint16_t val) { |
| 103 | return WriteBits(val, sizeof(uint16_t) * 8); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 104 | } |
| 105 | |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 106 | bool BitBufferWriter::WriteUInt32(uint32_t val) { |
| 107 | return WriteBits(val, sizeof(uint32_t) * 8); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 108 | } |
| 109 | |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 110 | bool BitBufferWriter::WriteBits(uint64_t val, size_t bit_count) { |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 111 | 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 Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 117 | val <<= (sizeof(uint64_t) * 8 - bit_count); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 118 | |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 119 | uint8_t* bytes = writable_bytes_ + byte_offset_; |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 120 | |
| 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 Gerey | 665174f | 2018-06-19 13:03:05 | [diff] [blame] | 127 | *bytes = WritePartialByte(HighestByte(val), bits_in_first_byte, *bytes, |
| 128 | bit_offset_); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 129 | 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 Chapovalov | a2b30d8 | 2019-07-03 12:41:50 | [diff] [blame] | 155 | bool 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 Chapovalov | a9e1b49 | 2020-07-08 09:24:19 | [diff] [blame] | 158 | 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 Chapovalov | 09fb787 | 2021-08-20 10:46:14 | [diff] [blame] | 163 | size_t count_bits = absl::bit_width(num_values); |
Danil Chapovalov | a2b30d8 | 2019-07-03 12:41:50 | [diff] [blame] | 164 | 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 | |
| 171 | size_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 Chapovalov | 09fb787 | 2021-08-20 10:46:14 | [diff] [blame] | 175 | size_t count_bits = absl::bit_width(num_values); |
Danil Chapovalov | a2b30d8 | 2019-07-03 12:41:50 | [diff] [blame] | 176 | 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 Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 181 | bool BitBufferWriter::WriteExponentialGolomb(uint32_t val) { |
| 182 | // We don't support reading UINT32_MAX, because it doesn't fit in a uint32_t |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 183 | // when encoded, so don't support writing it either. |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 184 | if (val == std::numeric_limits<uint32_t>::max()) { |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 185 | return false; |
| 186 | } |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 187 | uint64_t val_to_encode = static_cast<uint64_t>(val) + 1; |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 188 | |
Danil Chapovalov | 09fb787 | 2021-08-20 10:46:14 | [diff] [blame] | 189 | // We need to write bit_width(val+1) 0s and then val+1. Since val (as a |
Noah Richards | 9b9f1c4 | 2015-05-12 19:20:47 | [diff] [blame] | 190 | // 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 Chapovalov | 09fb787 | 2021-08-20 10:46:14 | [diff] [blame] | 192 | return WriteBits(val_to_encode, absl::bit_width(val_to_encode) * 2 - 1); |
Noah Richards | 86153c2 | 2015-04-28 22:13:44 | [diff] [blame] | 193 | } |
| 194 | |
sprang | 52033d6 | 2016-06-02 09:43:32 | [diff] [blame] | 195 | bool 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 | |
philipel | 579a7b4 | 2023-03-02 10:51:53 | [diff] [blame] | 209 | bool 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 | |
| 222 | bool 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 Richards | bbf7c86 | 2015-04-21 23:30:13 | [diff] [blame] | 230 | } // namespace rtc |