More efficient BitReader::SkipBits for large numbers of bits.

BUG=376450

Review URL: https://codereview.chromium.org/599123002

Cr-Commit-Position: refs/heads/master@{#296956}

3 files changed, 92 insertions, 5 deletions

diff --git a/media/base/bit_reader_core.cc b/media/base/bit_reader_core.cc
index 7087c33..f292f97 100644
--- a/media/base/bit_reader_core.cc
+++ b/media/base/bit_reader_core.cc
@@ -51,12 +51,8 @@ int BitReaderCore::PeekBitsMsbAligned(int num_bits, uint64* out) {
   return nbits_;
 }
 
-bool BitReaderCore::SkipBits(int num_bits) {
-  // TODO(dalecurtis): Rewrite to be efficient, see http://crbug.com/376450
+bool BitReaderCore::SkipBitsSmall(int num_bits) {
   DCHECK_GE(num_bits, 0);
-  DVLOG_IF(1, num_bits > 100)
-      << "BitReader::SkipBits inefficient for large skips";
-
   uint64 dummy;
   while (num_bits >= kRegWidthInBits) {
     if (!ReadBitsInternal(kRegWidthInBits, &dummy))
@@ -66,6 +62,39 @@ bool BitReaderCore::SkipBits(int num_bits) {
   return ReadBitsInternal(num_bits, &dummy);
 }
 
+bool BitReaderCore::SkipBits(int num_bits) {
+  DCHECK_GE(num_bits, 0);
+
+  const int remaining_bits = nbits_ + nbits_next_;
+  if (remaining_bits >= num_bits)
+    return SkipBitsSmall(num_bits);
+
+  // Skip first the remaining available bits.
+  num_bits -= remaining_bits;
+  bits_read_ += remaining_bits;
+  nbits_ = 0;
+  reg_ = 0;
+  nbits_next_ = 0;
+  reg_next_ = 0;
+
+  // Next, skip an integer number of bytes.
+  const int nbytes = num_bits / 8;
+  if (nbytes > 0) {
+    const uint8* byte_stream_window;
+    const int window_size =
+        byte_stream_provider_->GetBytes(nbytes, &byte_stream_window);
+    DCHECK_GE(window_size, 0);
+    DCHECK_LE(window_size, nbytes);
+    if (window_size < nbytes)
+      return false;
+    num_bits -= 8 * nbytes;
+    bits_read_ += 8 * nbytes;
+  }
+
+  // Skip the remaining bits.
+  return SkipBitsSmall(num_bits);
+}
+
 int BitReaderCore::bits_read() const {
   return bits_read_;
 }
diff --git a/media/base/bit_reader_core.h b/media/base/bit_reader_core.h
index 6f92d17..525d619 100644
--- a/media/base/bit_reader_core.h
+++ b/media/base/bit_reader_core.h
@@ -85,6 +85,11 @@ class MEDIA_EXPORT BitReaderCore {
   int bits_read() const;
 
  private:
+  // This function can skip any number of bits but is more efficient
+  // for small numbers. Return false if the given number of bits cannot be
+  // skipped (not enough bits in the stream), true otherwise.
+  bool SkipBitsSmall(int num_bits);
+
   // Help function used by ReadBits to avoid inlining the bit reading logic.
   bool ReadBitsInternal(int num_bits, uint64* out);
 
diff --git a/media/base/bit_reader_unittest.cc b/media/base/bit_reader_unittest.cc
index b6edd49..88431ef 100644
--- a/media/base/bit_reader_unittest.cc
+++ b/media/base/bit_reader_unittest.cc
@@ -8,6 +8,13 @@
 
 namespace media {
 
+static void SetBit(uint8* buf, size_t size, size_t bit_pos) {
+  size_t byte_pos = bit_pos / 8;
+  bit_pos -= byte_pos * 8;
+  DCHECK_LT(byte_pos, size);
+  buf[byte_pos] |= (1 << (7 - bit_pos));
+}
+
 TEST(BitReaderTest, NormalOperationTest) {
   uint8 value8;
   uint64 value64;
@@ -64,6 +71,52 @@ TEST(BitReaderTest, SkipBitsTest) {
   EXPECT_FALSE(reader1.SkipBits(1));
 }
 
+TEST(BitReaderTest, VariableSkipBitsTest) {
+  uint8 buffer[256] = {0};
+
+  // The test alternates between ReadBits and SkipBits.
+  // The first number is the number of bits to read, the second one is the
+  // number of bits to skip. The number of bits to read was arbitrarily chosen
+  // while the number of bits to skip was chosen so as to cover from small skips
+  // to large skips.
+  const size_t pattern_read_skip[][2] = {
+    {  5,  17 },
+    {  4,  34 },
+    {  0,  44 },
+    {  3,   4 },   // Note: aligned read.
+    {  7,   7 },   // Note: both read&skip cross byte boundary.
+    { 17,  68 },
+    {  7, 102 },
+    {  9, 204 },
+    {  3, 408 } };
+
+  // Set bits to one only for the first and last bit of each read
+  // in the pattern.
+  size_t pos = 0;
+  for (size_t k = 0; k < arraysize(pattern_read_skip); ++k) {
+    const size_t read_bit_count = pattern_read_skip[k][0];
+    if (read_bit_count > 0) {
+      SetBit(buffer, sizeof(buffer), pos);
+      SetBit(buffer, sizeof(buffer), pos + read_bit_count - 1);
+      pos += read_bit_count;
+    }
+    pos += pattern_read_skip[k][1];
+  }
+
+  // Run the test.
+  BitReader bit_reader(buffer, sizeof(buffer));
+  EXPECT_EQ(bit_reader.bits_available(), static_cast<int>(sizeof(buffer) * 8));
+  for (size_t k = 0; k < arraysize(pattern_read_skip); ++k) {
+    const size_t read_bit_count = pattern_read_skip[k][0];
+    if (read_bit_count > 0) {
+      int value;
+      EXPECT_TRUE(bit_reader.ReadBits(read_bit_count, &value));
+      EXPECT_EQ(value, 1 | (1 << (read_bit_count - 1)));
+    }
+    EXPECT_TRUE(bit_reader.SkipBits(pattern_read_skip[k][1]));
+  }
+}
+
 TEST(BitReaderTest, BitsReadTest) {
   int value;
   bool flag;