Adds ability to measure with a higher precision the number of bits
read per symbol.

Change-Id: I218abaa5172b769b66dba45050381c0212602668

aom_dsp/bitreader.h

diff --git a/aom_dsp/bitreader.h b/aom_dsp/bitreader.h
index d2fd5f2..ee34275 100644
--- a/aom_dsp/bitreader.h
+++ b/aom_dsp/bitreader.h
@@ -79,6 +79,7 @@
 #endif
 }
 
+// Returns the position in the bit reader in bits.
 static INLINE ptrdiff_t aom_reader_tell(const aom_reader *r) {
 #if CONFIG_ANS
   (void)r;
@@ -91,6 +92,19 @@
 #endif
 }
 
+// Returns the position in the bit reader in 1/8th bits.
+static INLINE ptrdiff_t aom_reader_tell_frac(const aom_reader *r) {
+#if CONFIG_ANS
+  (void)r;
+  assert(0 && "aom_reader_tell_frac() is unimplemented for ANS");
+  return 0;
+#elif CONFIG_DAALA_EC
+  return aom_daala_reader_tell_frac(r);
+#else
+  return aom_dk_reader_tell_frac(r);
+#endif
+}
+
 static INLINE int aom_read(aom_reader *r, int prob) {
 #if CONFIG_ANS
   return uabs_read(r, prob);

aom_dsp/daalaboolreader.c

diff --git a/aom_dsp/daalaboolreader.c b/aom_dsp/daalaboolreader.c
index 8e1c782..65f9d50 100644
--- a/aom_dsp/daalaboolreader.c
+++ b/aom_dsp/daalaboolreader.c
@@ -28,3 +28,7 @@
 ptrdiff_t aom_daala_reader_tell(const daala_reader *r) {
   return od_ec_dec_tell(&r->ec);
 }
+
+ptrdiff_t aom_daala_reader_tell_frac(const daala_reader *r) {
+  return od_ec_dec_tell_frac(&r->ec);
+}

aom_dsp/daalaboolreader.h

diff --git a/aom_dsp/daalaboolreader.h b/aom_dsp/daalaboolreader.h
index 4fc7ff4..896ec8b 100644
--- a/aom_dsp/daalaboolreader.h
+++ b/aom_dsp/daalaboolreader.h
@@ -30,6 +30,7 @@
 int aom_daala_reader_init(daala_reader *r, const uint8_t *buffer, int size);
 const uint8_t *aom_daala_reader_find_end(daala_reader *r);
 ptrdiff_t aom_daala_reader_tell(const daala_reader *r);
+ptrdiff_t aom_daala_reader_tell_frac(const daala_reader *r);
 
 static INLINE int aom_daala_read(daala_reader *r, int prob) {
   if (prob == 128) {

aom_dsp/dkboolreader.h

diff --git a/aom_dsp/dkboolreader.h b/aom_dsp/dkboolreader.h
index 2fd2b37..4d70c53 100644
--- a/aom_dsp/dkboolreader.h
+++ b/aom_dsp/dkboolreader.h
@@ -65,7 +65,29 @@
   const size_t bits_read = (r->buffer - r->buffer_start) * CHAR_BIT;
   const int count =
       (r->count < LOTS_OF_BITS) ? r->count : r->count - LOTS_OF_BITS;
-  return bits_read + BD_VALUE_SIZE - (count + CHAR_BIT);
+  return bits_read - (count + CHAR_BIT);
+}
+
+/*The resolution of fractional-precision bit usage measurements, i.e.,
+   3 => 1/8th bits.*/
+#define DK_BITRES (3)
+
+static INLINE ptrdiff_t aom_dk_reader_tell_frac(const struct aom_dk_reader *r) {
+  uint32_t num_bits;
+  uint32_t range;
+  int l;
+  int i;
+  num_bits = aom_dk_reader_tell(r) << DK_BITRES;
+  range = r->range;
+  l = 0;
+  for (i = DK_BITRES; i-- > 0;) {
+    int b;
+    range = range * range >> 7;
+    b = (int)(range >> 8);
+    l = l << 1 | b;
+    range >>= b;
+  }
+  return num_bits - l;
 }
 
 static INLINE int aom_dk_reader_has_error(struct aom_dk_reader *r) {

test/boolcoder_test.cc

diff --git a/test/boolcoder_test.cc b/test/boolcoder_test.cc
index de9b6e4..f1bad33 100644
--- a/test/boolcoder_test.cc
+++ b/test/boolcoder_test.cc
@@ -88,3 +88,54 @@
     }
   }
 }
+
+#if CONFIG_DAALA_EC
+#define FRAC_DIFF_TOTAL_ERROR 0.07
+#else
+#define FRAC_DIFF_TOTAL_ERROR 0.2
+#endif
+
+TEST(AV1, TestTell) {
+  const int kBufferSize = 10000;
+  aom_writer bw;
+  uint8_t bw_buffer[kBufferSize];
+  const int kSymbols = 1024;
+  // Coders are noisier at low probabilities, so we start at p = 4.
+  for (int p = 4; p <= 256; p++) {
+    double probability = p / 256.;
+    aom_start_encode(&bw, bw_buffer);
+    for (int i = 0; i < kSymbols; i++) {
+      aom_write(&bw, 0, p);
+    }
+    aom_stop_encode(&bw);
+    aom_reader br;
+    aom_reader_init(&br, bw_buffer, kBufferSize, NULL, NULL);
+    ptrdiff_t last_tell = aom_reader_tell(&br);
+    ptrdiff_t last_tell_frac = aom_reader_tell_frac(&br);
+    double frac_diff_total = 0;
+    GTEST_ASSERT_GE(aom_reader_tell(&br), 0);
+    GTEST_ASSERT_LE(aom_reader_tell(&br), 1);
+    for (int i = 0; i < kSymbols; i++) {
+      aom_read(&br, p);
+      ptrdiff_t tell = aom_reader_tell(&br);
+      ptrdiff_t tell_frac = aom_reader_tell_frac(&br);
+      GTEST_ASSERT_GE(tell, last_tell) << "tell: " << tell
+                                       << ", last_tell: " << last_tell;
+      GTEST_ASSERT_GE(tell_frac, last_tell_frac)
+          << "tell_frac: " << tell_frac
+          << ", last_tell_frac: " << last_tell_frac;
+      // Frac tell should round up to tell.
+      GTEST_ASSERT_EQ(tell, (tell_frac + 7) >> 3);
+      last_tell = tell;
+      frac_diff_total +=
+          fabs(((tell_frac - last_tell_frac) / 8.0) + log2(probability));
+      last_tell_frac = tell_frac;
+    }
+    const int expected = (int)(-kSymbols * log2(probability));
+    // Last tell should be close to the expected value.
+    GTEST_ASSERT_LE(last_tell - expected, 20) << " last_tell: " << last_tell;
+    // The average frac_diff error should be pretty small.
+    GTEST_ASSERT_LE(frac_diff_total / kSymbols, FRAC_DIFF_TOTAL_ERROR)
+        << " frac_diff_total: " << frac_diff_total;
+  }
+}