Line data Source code
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 :
18 : namespace {
19 :
20 : // Returns the lowest (right-most) |bit_count| bits in |byte|.
21 0 : uint8_t LowestBits(uint8_t byte, size_t bit_count) {
22 0 : RTC_DCHECK_LE(bit_count, 8);
23 0 : 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).
28 0 : uint8_t HighestBits(uint8_t byte, size_t bit_count) {
29 0 : RTC_DCHECK_LE(bit_count, 8);
30 0 : uint8_t shift = 8 - static_cast<uint8_t>(bit_count);
31 0 : uint8_t mask = 0xFF << shift;
32 0 : return (byte & mask) >> shift;
33 : }
34 :
35 : // Returns the highest byte of |val| in a uint8_t.
36 0 : uint8_t HighestByte(uint64_t val) {
37 0 : 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.
43 0 : uint8_t WritePartialByte(uint8_t source,
44 : size_t source_bit_count,
45 : uint8_t target,
46 : size_t target_bit_offset) {
47 0 : RTC_DCHECK(target_bit_offset < 8);
48 0 : RTC_DCHECK(source_bit_count < 9);
49 0 : 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 0 : static_cast<uint8_t>(0xFF << (8 - source_bit_count))
54 : // ...shifted over to the target offset from the most signficant bit.
55 0 : >> 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 0 : return (target & ~mask) | (source >> target_bit_offset);
60 : }
61 :
62 : // Counts the number of bits used in the binary representation of val.
63 0 : size_t CountBits(uint64_t val) {
64 0 : size_t bit_count = 0;
65 0 : while (val != 0) {
66 0 : bit_count++;
67 0 : val >>= 1;
68 : }
69 0 : return bit_count;
70 : }
71 :
72 : } // namespace
73 :
74 : namespace rtc {
75 :
76 0 : BitBuffer::BitBuffer(const uint8_t* bytes, size_t byte_count)
77 0 : : bytes_(bytes), byte_count_(byte_count), byte_offset_(), bit_offset_() {
78 0 : RTC_DCHECK(static_cast<uint64_t>(byte_count_) <=
79 0 : std::numeric_limits<uint32_t>::max());
80 0 : }
81 :
82 0 : uint64_t BitBuffer::RemainingBitCount() const {
83 0 : return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_;
84 : }
85 :
86 0 : bool BitBuffer::ReadUInt8(uint8_t* val) {
87 : uint32_t bit_val;
88 0 : if (!ReadBits(&bit_val, sizeof(uint8_t) * 8)) {
89 0 : return false;
90 : }
91 0 : RTC_DCHECK(bit_val <= std::numeric_limits<uint8_t>::max());
92 0 : *val = static_cast<uint8_t>(bit_val);
93 0 : return true;
94 : }
95 :
96 0 : bool BitBuffer::ReadUInt16(uint16_t* val) {
97 : uint32_t bit_val;
98 0 : if (!ReadBits(&bit_val, sizeof(uint16_t) * 8)) {
99 0 : return false;
100 : }
101 0 : RTC_DCHECK(bit_val <= std::numeric_limits<uint16_t>::max());
102 0 : *val = static_cast<uint16_t>(bit_val);
103 0 : return true;
104 : }
105 :
106 0 : bool BitBuffer::ReadUInt32(uint32_t* val) {
107 0 : return ReadBits(val, sizeof(uint32_t) * 8);
108 : }
109 :
110 0 : bool BitBuffer::PeekBits(uint32_t* val, size_t bit_count) {
111 0 : if (!val || bit_count > RemainingBitCount() || bit_count > 32) {
112 0 : return false;
113 : }
114 0 : const uint8_t* bytes = bytes_ + byte_offset_;
115 0 : size_t remaining_bits_in_current_byte = 8 - bit_offset_;
116 0 : 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 0 : if (bit_count < remaining_bits_in_current_byte) {
120 0 : *val = HighestBits(bits, bit_offset_ + bit_count);
121 0 : 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 0 : bit_count -= remaining_bits_in_current_byte;
126 0 : while (bit_count >= 8) {
127 0 : bits = (bits << 8) | *bytes++;
128 0 : 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 0 : if (bit_count > 0) {
133 0 : bits <<= bit_count;
134 0 : bits |= HighestBits(*bytes, bit_count);
135 : }
136 0 : *val = bits;
137 0 : return true;
138 : }
139 :
140 0 : bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) {
141 0 : return PeekBits(val, bit_count) && ConsumeBits(bit_count);
142 : }
143 :
144 0 : bool BitBuffer::ConsumeBytes(size_t byte_count) {
145 0 : return ConsumeBits(byte_count * 8);
146 : }
147 :
148 0 : bool BitBuffer::ConsumeBits(size_t bit_count) {
149 0 : if (bit_count > RemainingBitCount()) {
150 0 : return false;
151 : }
152 :
153 0 : byte_offset_ += (bit_offset_ + bit_count) / 8;
154 0 : bit_offset_ = (bit_offset_ + bit_count) % 8;
155 0 : return true;
156 : }
157 :
158 0 : bool BitBuffer::ReadExponentialGolomb(uint32_t* val) {
159 0 : if (!val) {
160 0 : 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 0 : size_t original_byte_offset = byte_offset_;
165 0 : 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 0 : size_t zero_bit_count = 0;
169 : uint32_t peeked_bit;
170 0 : while (PeekBits(&peeked_bit, 1) && peeked_bit == 0) {
171 0 : zero_bit_count++;
172 0 : ConsumeBits(1);
173 : }
174 :
175 : // We should either be at the end of the stream, or the next bit should be 1.
176 0 : 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 0 : size_t value_bit_count = zero_bit_count + 1;
182 0 : if (value_bit_count > 32 || !ReadBits(val, value_bit_count)) {
183 0 : RTC_CHECK(Seek(original_byte_offset, original_bit_offset));
184 0 : return false;
185 : }
186 0 : *val -= 1;
187 0 : return true;
188 : }
189 :
190 0 : bool BitBuffer::ReadSignedExponentialGolomb(int32_t* val) {
191 : uint32_t unsigned_val;
192 0 : if (!ReadExponentialGolomb(&unsigned_val)) {
193 0 : return false;
194 : }
195 0 : if ((unsigned_val & 1) == 0) {
196 0 : *val = -static_cast<int32_t>(unsigned_val / 2);
197 : } else {
198 0 : *val = (unsigned_val + 1) / 2;
199 : }
200 0 : return true;
201 : }
202 :
203 0 : void BitBuffer::GetCurrentOffset(
204 : size_t* out_byte_offset, size_t* out_bit_offset) {
205 0 : RTC_CHECK(out_byte_offset != NULL);
206 0 : RTC_CHECK(out_bit_offset != NULL);
207 0 : *out_byte_offset = byte_offset_;
208 0 : *out_bit_offset = bit_offset_;
209 0 : }
210 :
211 0 : bool BitBuffer::Seek(size_t byte_offset, size_t bit_offset) {
212 0 : if (byte_offset > byte_count_ || bit_offset > 7 ||
213 0 : (byte_offset == byte_count_ && bit_offset > 0)) {
214 0 : return false;
215 : }
216 0 : byte_offset_ = byte_offset;
217 0 : bit_offset_ = bit_offset;
218 0 : return true;
219 : }
220 :
221 0 : BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count)
222 0 : : BitBuffer(bytes, byte_count), writable_bytes_(bytes) {
223 0 : }
224 :
225 0 : bool BitBufferWriter::WriteUInt8(uint8_t val) {
226 0 : return WriteBits(val, sizeof(uint8_t) * 8);
227 : }
228 :
229 0 : bool BitBufferWriter::WriteUInt16(uint16_t val) {
230 0 : return WriteBits(val, sizeof(uint16_t) * 8);
231 : }
232 :
233 0 : bool BitBufferWriter::WriteUInt32(uint32_t val) {
234 0 : return WriteBits(val, sizeof(uint32_t) * 8);
235 : }
236 :
237 0 : bool BitBufferWriter::WriteBits(uint64_t val, size_t bit_count) {
238 0 : if (bit_count > RemainingBitCount()) {
239 0 : return false;
240 : }
241 0 : size_t total_bits = bit_count;
242 :
243 : // For simplicity, push the bits we want to read from val to the highest bits.
244 0 : val <<= (sizeof(uint64_t) * 8 - bit_count);
245 :
246 0 : 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 0 : size_t remaining_bits_in_current_byte = 8 - bit_offset_;
252 : size_t bits_in_first_byte =
253 0 : std::min(bit_count, remaining_bits_in_current_byte);
254 0 : *bytes = WritePartialByte(
255 0 : HighestByte(val), bits_in_first_byte, *bytes, bit_offset_);
256 0 : if (bit_count <= remaining_bits_in_current_byte) {
257 : // Nothing left to write, so quit early.
258 0 : 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 0 : val <<= bits_in_first_byte;
264 0 : bytes++;
265 0 : bit_count -= bits_in_first_byte;
266 0 : while (bit_count >= 8) {
267 0 : *bytes++ = HighestByte(val);
268 0 : val <<= 8;
269 0 : bit_count -= 8;
270 : }
271 :
272 : // Last byte may also be partial, so write the remaining bits from the top of
273 : // val.
274 0 : if (bit_count > 0) {
275 0 : *bytes = WritePartialByte(HighestByte(val), bit_count, *bytes, 0);
276 : }
277 :
278 : // All done! Consume the bits we've written.
279 0 : return ConsumeBits(total_bits);
280 : }
281 :
282 0 : bool 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 0 : if (val == std::numeric_limits<uint32_t>::max()) {
286 0 : return false;
287 : }
288 0 : 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 0 : return WriteBits(val_to_encode, CountBits(val_to_encode) * 2 - 1);
294 : }
295 :
296 0 : bool BitBufferWriter::WriteSignedExponentialGolomb(int32_t val) {
297 0 : if (val == 0) {
298 0 : return WriteExponentialGolomb(0);
299 0 : } else if (val > 0) {
300 0 : uint32_t signed_val = val;
301 0 : return WriteExponentialGolomb((signed_val * 2) - 1);
302 : } else {
303 0 : if (val == std::numeric_limits<int32_t>::min())
304 0 : return false; // Not supported, would cause overflow.
305 0 : uint32_t signed_val = -val;
306 0 : return WriteExponentialGolomb(signed_val * 2);
307 : }
308 : }
309 :
310 : } // namespace rtc
|
