From e639eac298aa914b7b56b3d78115b5abc1132e11 Mon Sep 17 00:00:00 2001
From: Giuseppe Ottaviano <ott@fb.com>
Date: Thu, 23 Feb 2017 17:51:16 -0800
Subject: [PATCH] Fix a corner case in EliasFanoReader::previousValue

Summary:
`previousValue` makes the incorrect assumption that `outer_`
is a multiple of the word size. This is incorrect because `skipToNext`
can reposition at an arbitrary point.

The bug is very rare because it can only happen if there is a gap
larger than the skip quantum after the first element in the upper
bits.

Reviewed By: philippv

Differential Revision: D4607270

fbshipit-source-id: ff016f09f3f1f87314b68370e3dc137b82694f45
---
 folly/experimental/EliasFanoCoding.h          |  4 ++--
 .../experimental/test/EliasFanoCodingTest.cpp | 22 +++++++++++++++++++
 2 files changed, 24 insertions(+), 2 deletions(-)

diff --git a/folly/experimental/EliasFanoCoding.h b/folly/experimental/EliasFanoCoding.h
index 6a7d4779..f75fabde 100644
--- a/folly/experimental/EliasFanoCoding.h
+++ b/folly/experimental/EliasFanoCoding.h
@@ -473,8 +473,8 @@ class UpperBitsReader {
     block &= (block_t(1) << inner_) - 1;
 
     while (UNLIKELY(block == 0)) {
-      DCHECK_GE(outer, sizeof(block_t));
-      outer -= sizeof(block_t);
+      DCHECK_GT(outer, 0);
+      outer -= std::min(sizeof(block_t), outer);
       block = folly::loadUnaligned<block_t>(start_ + outer);
     }
 
diff --git a/folly/experimental/test/EliasFanoCodingTest.cpp b/folly/experimental/test/EliasFanoCodingTest.cpp
index 63652300..8ae1425a 100644
--- a/folly/experimental/test/EliasFanoCodingTest.cpp
+++ b/folly/experimental/test/EliasFanoCodingTest.cpp
@@ -138,6 +138,28 @@ TEST_F(EliasFanoCodingTest, Select64) {
   }
 }
 
+TEST_F(EliasFanoCodingTest, BugLargeGapInUpperBits) { // t16274876
+  typedef EliasFanoEncoderV2<uint32_t, uint32_t, 2, 2> Encoder;
+  typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
+  constexpr uint32_t kLargeValue = 127;
+
+  // Build a list where the upper bits have a large gap after the
+  // first element, so that we need to reposition in the upper bits
+  // using skips to position the iterator on the second element.
+  std::vector<uint32_t> data = {0, kLargeValue};
+  for (uint32_t i = 0; i < kLargeValue; ++i) {
+    data.push_back(data.back() + 1);
+  }
+  auto list = Encoder::encode(data.begin(), data.end());
+
+  {
+    Reader reader(list);
+    ASSERT_TRUE(reader.skipTo(kLargeValue - 1));
+    ASSERT_EQ(kLargeValue, reader.value());
+    ASSERT_EQ(0, reader.previousValue());
+  }
+}
+
 namespace bm {
 
 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 128, 128> Encoder;
-- 
2.34.1