Add a new BitBuffer class to webrtc base.
Provides a read-only interface for reading byte and bit-sized data from
an underlying buffer in network/big-endian order. Also provides a method
for reading exponential golomb encoded values, which will be useful in
H.264 packet parsing (separate CL).
BUG=
R=pthatcher@webrtc.org
Review URL: https://webrtc-codereview.appspot.com/49719004
Cr-Commit-Position: refs/heads/master@{#9046}
diff --git a/webrtc/base/BUILD.gn b/webrtc/base/BUILD.gn
index 9168d16..46bacd8 100644
--- a/webrtc/base/BUILD.gn
+++ b/webrtc/base/BUILD.gn
@@ -179,6 +179,8 @@
"base64.cc",
"base64.h",
"basicdefs.h",
+ "bitbuffer.cc",
+ "bitbuffer.h",
"bytebuffer.cc",
"bytebuffer.h",
"byteorder.h",
diff --git a/webrtc/base/base.gyp b/webrtc/base/base.gyp
index c767a9a..72f1b63 100644
--- a/webrtc/base/base.gyp
+++ b/webrtc/base/base.gyp
@@ -102,6 +102,8 @@
'basictypes.h',
'bind.h',
'bind.h.pump',
+ 'bitbuffer.cc',
+ 'bitbuffer.h',
'bytebuffer.cc',
'bytebuffer.h',
'byteorder.h',
diff --git a/webrtc/base/base_tests.gyp b/webrtc/base/base_tests.gyp
index 3a9b164..d9e560e 100644
--- a/webrtc/base/base_tests.gyp
+++ b/webrtc/base/base_tests.gyp
@@ -53,6 +53,7 @@
'base64_unittest.cc',
'basictypes_unittest.cc',
'bind_unittest.cc',
+ 'bitbuffer_unittest.cc',
'buffer_unittest.cc',
'bytebuffer_unittest.cc',
'byteorder_unittest.cc',
diff --git a/webrtc/base/bitbuffer.cc b/webrtc/base/bitbuffer.cc
new file mode 100644
index 0000000..f41962a
--- /dev/null
+++ b/webrtc/base/bitbuffer.cc
@@ -0,0 +1,154 @@
+/*
+ * Copyright 2015 The WebRTC Project Authors. All rights reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/base/bitbuffer.h"
+
+#include <limits>
+
+#include "webrtc/base/checks.h"
+
+namespace {
+
+// Returns the lowest (right-most) |bit_count| bits in |byte|.
+uint8 LowestBits(uint8 byte, size_t bit_count) {
+ DCHECK_LE(bit_count, 8u);
+ uint8 mask_shift = 8 - static_cast<uint8>(bit_count);
+ return byte & (0xFF >> mask_shift);
+}
+
+// Returns the highest (left-most) |bit_count| bits in |byte|, shifted to the
+// lowest bits (to the right).
+uint8 HighestBits(uint8 byte, size_t bit_count) {
+ DCHECK_LE(bit_count, 8u);
+ uint8 shift = 8 - static_cast<uint8>(bit_count);
+ uint8 mask = 0xFF << shift;
+ return (byte & mask) >> shift;
+}
+
+} // namespace
+
+namespace rtc {
+
+BitBuffer::BitBuffer(const uint8* bytes, size_t byte_count)
+ : bytes_(bytes), byte_count_(byte_count), byte_offset_(), bit_offset_() {
+ DCHECK(static_cast<uint64>(byte_count_) <=
+ std::numeric_limits<uint32>::max());
+}
+
+uint64 BitBuffer::RemainingBitCount() const {
+ return (static_cast<uint64>(byte_count_) - byte_offset_) * 8 - bit_offset_;
+}
+
+bool BitBuffer::ReadUInt8(uint8* val) {
+ uint32 bit_val;
+ if (!ReadBits(&bit_val, sizeof(uint8) * 8)) {
+ return false;
+ }
+ DCHECK(bit_val <= std::numeric_limits<uint8>::max());
+ *val = static_cast<uint8>(bit_val);
+ return true;
+}
+
+bool BitBuffer::ReadUInt16(uint16* val) {
+ uint32 bit_val;
+ if (!ReadBits(&bit_val, sizeof(uint16) * 8)) {
+ return false;
+ }
+ DCHECK(bit_val <= std::numeric_limits<uint16>::max());
+ *val = static_cast<uint16>(bit_val);
+ return true;
+}
+
+bool BitBuffer::ReadUInt32(uint32* val) {
+ return ReadBits(val, sizeof(uint32) * 8);
+}
+
+bool BitBuffer::PeekBits(uint32* val, size_t bit_count) {
+ if (!val || bit_count > RemainingBitCount() || bit_count > 32) {
+ return false;
+ }
+ const uint8* bytes = bytes_ + byte_offset_;
+ size_t remaining_bits_in_current_byte = 8 - bit_offset_;
+ uint32 bits = LowestBits(*bytes++, remaining_bits_in_current_byte);
+ // If we're reading fewer bits than what's left in the current byte, just
+ // return the portion of this byte that we need.
+ if (bit_count < remaining_bits_in_current_byte) {
+ *val = HighestBits(bits, bit_offset_ + bit_count);
+ return true;
+ }
+ // Otherwise, subtract what we've read from the bit count and read as many
+ // full bytes as we can into bits.
+ bit_count -= remaining_bits_in_current_byte;
+ while (bit_count >= 8) {
+ bits = (bits << 8) | *bytes++;
+ bit_count -= 8;
+ }
+ // Whatever we have left is smaller than a byte, so grab just the bits we need
+ // and shift them into the lowest bits.
+ if (bit_count > 0) {
+ bits <<= bit_count;
+ bits |= HighestBits(*bytes, bit_count);
+ }
+ *val = bits;
+ return true;
+}
+
+bool BitBuffer::ReadBits(uint32* val, size_t bit_count) {
+ return PeekBits(val, bit_count) && ConsumeBits(bit_count);
+}
+
+bool BitBuffer::ConsumeBytes(size_t byte_count) {
+ return ConsumeBits(byte_count * 8);
+}
+
+bool BitBuffer::ConsumeBits(size_t bit_count) {
+ if (bit_count > RemainingBitCount()) {
+ return false;
+ }
+
+ byte_offset_ += (bit_offset_ + bit_count) / 8;
+ bit_offset_ = (bit_offset_ + bit_count) % 8;
+ return true;
+}
+
+bool BitBuffer::ReadExponentialGolomb(uint32* val) {
+ if (!val) {
+ return false;
+ }
+ // Store off the current byte/bit offset, in case we want to restore them due
+ // to a failed parse.
+ size_t original_byte_offset = byte_offset_;
+ size_t original_bit_offset = bit_offset_;
+
+ // Count the number of leading 0 bits by peeking/consuming them one at a time.
+ size_t zero_bit_count = 0;
+ uint32 peeked_bit;
+ while (PeekBits(&peeked_bit, 1) && peeked_bit == 0) {
+ zero_bit_count++;
+ ConsumeBits(1);
+ }
+
+ // We should either be at the end of the stream, or the next bit should be 1.
+ DCHECK(!PeekBits(&peeked_bit, 1) || peeked_bit == 1);
+
+ // The bit count of the value is the number of zeros + 1. Make sure that many
+ // bits fits in a uint32 and that we have enough bits left for it, and then
+ // read the value.
+ size_t value_bit_count = zero_bit_count + 1;
+ if (value_bit_count > 32 || !ReadBits(val, value_bit_count)) {
+ byte_offset_ = original_byte_offset;
+ bit_offset_ = original_bit_offset;
+ return false;
+ }
+ *val -= 1;
+ return true;
+}
+
+} // namespace rtc
diff --git a/webrtc/base/bitbuffer.h b/webrtc/base/bitbuffer.h
new file mode 100644
index 0000000..356a817
--- /dev/null
+++ b/webrtc/base/bitbuffer.h
@@ -0,0 +1,75 @@
+/*
+ * Copyright 2015 The WebRTC Project Authors. All rights reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_BASE_BITBUFFER_H_
+#define WEBRTC_BASE_BITBUFFER_H_
+
+#include "webrtc/base/common.h"
+
+namespace rtc {
+
+// A class, similar to ByteBuffer, that can parse bit-sized data out of a set of
+// bytes. Has a similar API to the read-only parts of ByteBuffer, plus methods
+// for reading bit-sized data and processing exponential golomb encoded data.
+// Sizes/counts specify bits/bytes, for clarity.
+// Byte order is assumed big-endian/network.
+class BitBuffer {
+ public:
+ BitBuffer(const uint8* bytes, size_t byte_count);
+
+ // The remaining bits in the byte buffer.
+ uint64 RemainingBitCount() const;
+
+ // Reads byte-sized values from the buffer. Returns false if there isn't
+ // enough data left for the specified type.
+ bool ReadUInt8(uint8* val);
+ bool ReadUInt16(uint16* val);
+ bool ReadUInt32(uint32* val);
+
+ // Reads bit-sized values from the buffer. Returns false if there isn't enough
+ // data left for the specified type.
+ bool ReadBits(uint32* val, size_t bit_count);
+
+ // Peeks bit-sized values from the buffer. Returns false if there isn't enough
+ // data left for the specified type. Doesn't move the current read offset.
+ bool PeekBits(uint32* val, size_t bit_count);
+
+ // Reads the exponential golomb encoded value at the current bit offset.
+ // Exponential golomb values are encoded as:
+ // 1) x = source val + 1
+ // 2) In binary, write [countbits(x) - 1] 0s, then x
+ // To decode, we count the number of leading 0 bits, read that many + 1 bits,
+ // and increment the result by 1.
+ // Returns false if there isn't enough data left for the specified type, or if
+ // the value wouldn't fit in a uint32.
+ bool ReadExponentialGolomb(uint32* val);
+
+ // Moves current position |byte_count| bytes forward. Returns false if
+ // there aren't enough bytes left in the buffer.
+ bool ConsumeBytes(size_t byte_count);
+ // Moves current position |bit_count| bits forward. Returns false if
+ // there aren't enough bits left in the buffer.
+ bool ConsumeBits(size_t bit_count);
+
+ private:
+ const uint8* const bytes_;
+ // The total size of |bytes_|.
+ size_t byte_count_;
+ // The current offset, in bytes, from the start of |bytes_|.
+ size_t byte_offset_;
+ // The current offset, in bits, into the current byte.
+ size_t bit_offset_;
+
+ DISALLOW_COPY_AND_ASSIGN(BitBuffer);
+};
+
+} // namespace rtc
+
+#endif // WEBRTC_BASE_BITBUFFER_H_
diff --git a/webrtc/base/bitbuffer_unittest.cc b/webrtc/base/bitbuffer_unittest.cc
new file mode 100644
index 0000000..143ea6f
--- /dev/null
+++ b/webrtc/base/bitbuffer_unittest.cc
@@ -0,0 +1,183 @@
+/*
+ * Copyright 2015 The WebRTC Project Authors. All rights reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "webrtc/base/bitbuffer.h"
+#include "webrtc/base/bytebuffer.h"
+#include "webrtc/base/common.h"
+#include "webrtc/base/gunit.h"
+
+namespace rtc {
+
+TEST(BitBufferTest, ConsumeBits) {
+ const uint8 bytes[64] = {0};
+ BitBuffer buffer(bytes, 32);
+ uint64 total_bits = 32 * 8;
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+ EXPECT_TRUE(buffer.ConsumeBits(3));
+ total_bits -= 3;
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+ EXPECT_TRUE(buffer.ConsumeBits(3));
+ total_bits -= 3;
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+ EXPECT_TRUE(buffer.ConsumeBits(15));
+ total_bits -= 15;
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+ EXPECT_TRUE(buffer.ConsumeBits(37));
+ total_bits -= 37;
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+
+ EXPECT_FALSE(buffer.ConsumeBits(32 * 8));
+ EXPECT_EQ(total_bits, buffer.RemainingBitCount());
+}
+
+TEST(BitBufferTest, ReadBytesAligned) {
+ const uint8 bytes[] = {0x0A, 0xBC, 0xDE, 0xF1, 0x23, 0x45, 0x67, 0x89};
+ uint8 val8;
+ uint16 val16;
+ uint32 val32;
+ BitBuffer buffer(bytes, 8);
+ EXPECT_TRUE(buffer.ReadUInt8(&val8));
+ EXPECT_EQ(0x0Au, val8);
+ EXPECT_TRUE(buffer.ReadUInt8(&val8));
+ EXPECT_EQ(0xBCu, val8);
+ EXPECT_TRUE(buffer.ReadUInt16(&val16));
+ EXPECT_EQ(0xDEF1u, val16);
+ EXPECT_TRUE(buffer.ReadUInt32(&val32));
+ EXPECT_EQ(0x23456789u, val32);
+}
+
+TEST(BitBufferTest, ReadBytesOffset4) {
+ const uint8 bytes[] = {0x0A, 0xBC, 0xDE, 0xF1, 0x23, 0x45, 0x67, 0x89, 0x0A};
+ uint8 val8;
+ uint16 val16;
+ uint32 val32;
+ BitBuffer buffer(bytes, 9);
+ EXPECT_TRUE(buffer.ConsumeBits(4));
+
+ EXPECT_TRUE(buffer.ReadUInt8(&val8));
+ EXPECT_EQ(0xABu, val8);
+ EXPECT_TRUE(buffer.ReadUInt8(&val8));
+ EXPECT_EQ(0xCDu, val8);
+ EXPECT_TRUE(buffer.ReadUInt16(&val16));
+ EXPECT_EQ(0xEF12u, val16);
+ EXPECT_TRUE(buffer.ReadUInt32(&val32));
+ EXPECT_EQ(0x34567890u, val32);
+}
+
+TEST(BitBufferTest, ReadBytesOffset3) {
+ // The pattern we'll check against is counting down from 0b1111. It looks
+ // weird here because it's all offset by 3.
+ // Byte pattern is:
+ // 56701234
+ // 0b00011111,
+ // 0b11011011,
+ // 0b10010111,
+ // 0b01010011,
+ // 0b00001110,
+ // 0b11001010,
+ // 0b10000110,
+ // 0b01000010
+ // xxxxx <-- last 5 bits unused.
+
+ // The bytes. It almost looks like counting down by two at a time, except the
+ // jump at 5->3->0, since that's when the high bit is turned off.
+ const uint8 bytes[] = {0x1F, 0xDB, 0x97, 0x53, 0x0E, 0xCA, 0x86, 0x42};
+
+ uint8 val8;
+ uint16 val16;
+ uint32 val32;
+ BitBuffer buffer(bytes, 8);
+ EXPECT_TRUE(buffer.ConsumeBits(3));
+ EXPECT_TRUE(buffer.ReadUInt8(&val8));
+ EXPECT_EQ(0xFEu, val8);
+ EXPECT_TRUE(buffer.ReadUInt16(&val16));
+ EXPECT_EQ(0xDCBAu, val16);
+ EXPECT_TRUE(buffer.ReadUInt32(&val32));
+ EXPECT_EQ(0x98765432u, val32);
+ // 5 bits left unread. Not enough to read a uint8.
+ EXPECT_EQ(5u, buffer.RemainingBitCount());
+ EXPECT_FALSE(buffer.ReadUInt8(&val8));
+}
+
+TEST(BitBufferTest, ReadBits) {
+ // Bit values are:
+ // 0b01001101,
+ // 0b00110010
+ const uint8 bytes[] = {0x4D, 0x32};
+ uint32_t val;
+ BitBuffer buffer(bytes, 2);
+ EXPECT_TRUE(buffer.ReadBits(&val, 3));
+ // 0b010
+ EXPECT_EQ(0x2u, val);
+ EXPECT_TRUE(buffer.ReadBits(&val, 2));
+ // 0b01
+ EXPECT_EQ(0x1u, val);
+ EXPECT_TRUE(buffer.ReadBits(&val, 7));
+ // 0b1010011
+ EXPECT_EQ(0x53u, val);
+ EXPECT_TRUE(buffer.ReadBits(&val, 2));
+ // 0b00
+ EXPECT_EQ(0x0u, val);
+ EXPECT_TRUE(buffer.ReadBits(&val, 1));
+ // 0b1
+ EXPECT_EQ(0x1u, val);
+ EXPECT_TRUE(buffer.ReadBits(&val, 1));
+ // 0b0
+ EXPECT_EQ(0x0u, val);
+
+ EXPECT_FALSE(buffer.ReadBits(&val, 1));
+}
+
+uint64 GolombEncoded(uint32 val) {
+ val++;
+ uint32 bit_counter = val;
+ uint64 bit_count = 0;
+ while (bit_counter > 0) {
+ bit_count++;
+ bit_counter >>= 1;
+ }
+ return static_cast<uint64>(val) << (64 - (bit_count * 2 - 1));
+}
+
+TEST(BitBufferTest, GolombString) {
+ char test_string[] = "my precious";
+ for (size_t i = 0; i < ARRAY_SIZE(test_string); ++i) {
+ uint64 encoded_val = GolombEncoded(test_string[i]);
+ // Use ByteBuffer to convert to bytes, to account for endianness (BitBuffer
+ // requires network order).
+ ByteBuffer byteBuffer;
+ byteBuffer.WriteUInt64(encoded_val);
+ BitBuffer buffer(reinterpret_cast<const uint8*>(byteBuffer.Data()),
+ byteBuffer.Length());
+ uint32 decoded_val;
+ EXPECT_TRUE(buffer.ReadExponentialGolomb(&decoded_val));
+ EXPECT_EQ(test_string[i], static_cast<char>(decoded_val));
+ }
+}
+
+TEST(BitBufferTest, NoGolombOverread) {
+ const uint8 bytes[] = {0x00, 0xFF, 0xFF};
+ // Make sure the bit buffer correctly enforces byte length on golomb reads.
+ // If it didn't, the above buffer would be valid at 3 bytes.
+ BitBuffer buffer(bytes, 1);
+ uint32 decoded_val;
+ EXPECT_FALSE(buffer.ReadExponentialGolomb(&decoded_val));
+
+ BitBuffer longer_buffer(bytes, 2);
+ EXPECT_FALSE(longer_buffer.ReadExponentialGolomb(&decoded_val));
+
+ BitBuffer longest_buffer(bytes, 3);
+ EXPECT_TRUE(longest_buffer.ReadExponentialGolomb(&decoded_val));
+ // Golomb should have read 9 bits, so 0x01FF, and since it is golomb, the
+ // result is 0x01FF - 1 = 0x01FE.
+ EXPECT_EQ(0x01FEu, decoded_val);
+}
+
+} // namespace rtc
