OLD | NEW |
| (Empty) |
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 uint8_t LowestBits(uint8_t byte, size_t bit_count) { | |
22 RTC_DCHECK_LE(bit_count, 8); | |
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). | |
28 uint8_t HighestBits(uint8_t byte, size_t bit_count) { | |
29 RTC_DCHECK_LE(bit_count, 8); | |
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. | |
36 uint8_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. | |
43 uint8_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. | |
63 size_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 | |
74 namespace rtc { | |
75 | |
76 BitBuffer::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 | |
82 uint64_t BitBuffer::RemainingBitCount() const { | |
83 return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_; | |
84 } | |
85 | |
86 bool 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 | |
96 bool 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 | |
106 bool BitBuffer::ReadUInt32(uint32_t* val) { | |
107 return ReadBits(val, sizeof(uint32_t) * 8); | |
108 } | |
109 | |
110 bool 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 | |
140 bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) { | |
141 return PeekBits(val, bit_count) && ConsumeBits(bit_count); | |
142 } | |
143 | |
144 bool BitBuffer::ConsumeBytes(size_t byte_count) { | |
145 return ConsumeBits(byte_count * 8); | |
146 } | |
147 | |
148 bool 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 | |
158 bool 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 | |
190 bool 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 | |
203 void BitBuffer::GetCurrentOffset( | |
204 size_t* out_byte_offset, size_t* out_bit_offset) { | |
205 RTC_CHECK(out_byte_offset != nullptr); | |
206 RTC_CHECK(out_bit_offset != nullptr); | |
207 *out_byte_offset = byte_offset_; | |
208 *out_bit_offset = bit_offset_; | |
209 } | |
210 | |
211 bool 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 | |
221 BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count) | |
222 : BitBuffer(bytes, byte_count), writable_bytes_(bytes) { | |
223 } | |
224 | |
225 bool BitBufferWriter::WriteUInt8(uint8_t val) { | |
226 return WriteBits(val, sizeof(uint8_t) * 8); | |
227 } | |
228 | |
229 bool BitBufferWriter::WriteUInt16(uint16_t val) { | |
230 return WriteBits(val, sizeof(uint16_t) * 8); | |
231 } | |
232 | |
233 bool BitBufferWriter::WriteUInt32(uint32_t val) { | |
234 return WriteBits(val, sizeof(uint32_t) * 8); | |
235 } | |
236 | |
237 bool 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 | |
282 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 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 bool BitBufferWriter::WriteSignedExponentialGolomb(int32_t val) { | |
297 if (val == 0) { | |
298 return WriteExponentialGolomb(0); | |
299 } else if (val > 0) { | |
300 uint32_t signed_val = val; | |
301 return WriteExponentialGolomb((signed_val * 2) - 1); | |
302 } else { | |
303 if (val == std::numeric_limits<int32_t>::min()) | |
304 return false; // Not supported, would cause overflow. | |
305 uint32_t signed_val = -val; | |
306 return WriteExponentialGolomb(signed_val * 2); | |
307 } | |
308 } | |
309 | |
310 } // namespace rtc | |
OLD | NEW |