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 18namespace { 19 20// Returns the lowest (right-most) |bit_count| bits in |byte|. 21uint8_t LowestBits(uint8_t byte, size_t bit_count) { 22 RTC_DCHECK_LE(bit_count, 8u); 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). 28uint8_t HighestBits(uint8_t byte, size_t bit_count) { 29 RTC_DCHECK_LE(bit_count, 8u); 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. 36uint8_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. 43uint8_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. 63size_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 74namespace rtc { 75 76BitBuffer::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 82uint64_t BitBuffer::RemainingBitCount() const { 83 return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_; 84} 85 86bool 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 96bool 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 106bool BitBuffer::ReadUInt32(uint32_t* val) { 107 return ReadBits(val, sizeof(uint32_t) * 8); 108} 109 110bool 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 140bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) { 141 return PeekBits(val, bit_count) && ConsumeBits(bit_count); 142} 143 144bool BitBuffer::ConsumeBytes(size_t byte_count) { 145 return ConsumeBits(byte_count * 8); 146} 147 148bool 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 158bool 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 190bool 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 203void BitBuffer::GetCurrentOffset( 204 size_t* out_byte_offset, size_t* out_bit_offset) { 205 RTC_CHECK(out_byte_offset != NULL); 206 RTC_CHECK(out_bit_offset != NULL); 207 *out_byte_offset = byte_offset_; 208 *out_bit_offset = bit_offset_; 209} 210 211bool 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 221BitBufferWriter::BitBufferWriter(uint8_t* bytes, size_t byte_count) 222 : BitBuffer(bytes, byte_count), writable_bytes_(bytes) { 223} 224 225bool BitBufferWriter::WriteUInt8(uint8_t val) { 226 return WriteBits(val, sizeof(uint8_t) * 8); 227} 228 229bool BitBufferWriter::WriteUInt16(uint16_t val) { 230 return WriteBits(val, sizeof(uint16_t) * 8); 231} 232 233bool BitBufferWriter::WriteUInt32(uint32_t val) { 234 return WriteBits(val, sizeof(uint32_t) * 8); 235} 236 237bool 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 282bool 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} // namespace rtc 297