folly/experimental/EliasFanoCoding.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  * @author Philip Pronin (philipp@fb.com)
  19  *
  20  * Based on the paper by Sebastiano Vigna,
  21  * "Quasi-succinct indices" (arxiv:1206.4300).
  22  */
  23
  24 #ifndef FOLLY_EXPERIMENTAL_ELIAS_FANO_CODING_H
  25 #define FOLLY_EXPERIMENTAL_ELIAS_FANO_CODING_H
  26
  27 #ifndef __GNUC__
  28 #error EliasFanoCoding.h requires GCC
  29 #endif
  30
  31 #if !FOLLY_X64
  32 #error EliasFanoCoding.h requires x86_64
  33 #endif
  34
  35 #include <cstdlib>
  36 #include <limits>
  37 #include <type_traits>
  38 #include <boost/noncopyable.hpp>
  39 #include <glog/logging.h>
  40
  41 #include <folly/Bits.h>
  42 #include <folly/CpuId.h>
  43 #include <folly/Likely.h>
  44 #include <folly/Range.h>
  45 #include <folly/experimental/Select64.h>
  46
  47 #if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
  48 #error EliasFanoCoding.h requires little endianness
  49 #endif
  50
  51 namespace folly { namespace compression {
  52
  53 template <class Pointer>
  54 struct EliasFanoCompressedListBase {
  55   EliasFanoCompressedListBase() = default;
  56
  57   template <class OtherPointer>
  58   EliasFanoCompressedListBase(
  59     const EliasFanoCompressedListBase<OtherPointer>& other)
  60       : size(other.size),
  61         numLowerBits(other.numLowerBits),
  62         data(other.data),
  63         skipPointers(reinterpret_cast<Pointer>(other.skipPointers)),
  64         forwardPointers(reinterpret_cast<Pointer>(other.forwardPointers)),
  65         lower(reinterpret_cast<Pointer>(other.lower)),
  66         upper(reinterpret_cast<Pointer>(other.upper)) {
  67   }
  68
  69   void free() {
  70     ::free(const_cast<unsigned char*>(data.data()));
  71   }
  72
  73   size_t upperSize() const {
  74     return data.end() - upper;
  75   }
  76
  77   size_t size = 0;
  78   uint8_t numLowerBits = 0;
  79
  80   // WARNING: EliasFanoCompressedList has no ownership of data. The 7
  81   // bytes following the last byte should be readable.
  82   folly::Range<Pointer> data;
  83
  84   Pointer skipPointers = nullptr;
  85   Pointer forwardPointers = nullptr;
  86   Pointer lower = nullptr;
  87   Pointer upper = nullptr;
  88 };
  89
  90 typedef EliasFanoCompressedListBase<const uint8_t*> EliasFanoCompressedList;
  91 typedef EliasFanoCompressedListBase<uint8_t*> MutableEliasFanoCompressedList;
  92
  93 template <class Value,
  94           class SkipValue = size_t,
  95           size_t kSkipQuantum = 0,     // 0 = disabled
  96           size_t kForwardQuantum = 0>  // 0 = disabled
  97 struct EliasFanoEncoderV2 {
  98   static_assert(std::is_integral<Value>::value &&
  99                 std::is_unsigned<Value>::value,
 100                 "Value should be unsigned integral");
 101
 102   typedef EliasFanoCompressedList CompressedList;
 103
 104   typedef Value ValueType;
 105   typedef SkipValue SkipValueType;
 106   struct Layout;
 107
 108   static constexpr size_t skipQuantum = kSkipQuantum;
 109   static constexpr size_t forwardQuantum = kForwardQuantum;
 110
 111   static uint8_t defaultNumLowerBits(size_t upperBound, size_t size) {
 112     if (size == 0 || upperBound < size) {
 113       return 0;
 114     }
 115     // floor(log(upperBound / size));
 116     return folly::findLastSet(upperBound / size) - 1;
 117   }
 118
 119   // Requires: input range (begin, end) is sorted (encoding
 120   // crashes if it's not).
 121   // WARNING: encode() mallocates lower, upper, skipPointers
 122   // and forwardPointers. As EliasFanoCompressedList has
 123   // no ownership of them, you need to call free() explicitly.
 124   template <class RandomAccessIterator>
 125   static EliasFanoCompressedList encode(RandomAccessIterator begin,
 126                                         RandomAccessIterator end) {
 127     if (begin == end) {
 128       return EliasFanoCompressedList();
 129     }
 130     EliasFanoEncoderV2 encoder(end - begin, *(end - 1));
 131     for (; begin != end; ++begin) {
 132       encoder.add(*begin);
 133     }
 134     return encoder.finish();
 135   }
 136
 137   explicit EliasFanoEncoderV2(const MutableEliasFanoCompressedList& result)
 138       : lower_(result.lower),
 139         upper_(result.upper),
 140         skipPointers_(reinterpret_cast<SkipValueType*>(
 141                         result.skipPointers)),
 142         forwardPointers_(reinterpret_cast<SkipValueType*>(
 143                            result.forwardPointers)),
 144         result_(result) {
 145   }
 146
 147   EliasFanoEncoderV2(size_t size, ValueType upperBound)
 148       : EliasFanoEncoderV2(
 149             Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {
 150   }
 151
 152   void add(ValueType value) {
 153     CHECK_GE(value, lastValue_);
 154
 155     const auto numLowerBits = result_.numLowerBits;
 156     const ValueType upperBits = value >> numLowerBits;
 157
 158     // Upper sequence consists of upperBits 0-bits and (size_ + 1) 1-bits.
 159     const size_t pos = upperBits + size_;
 160     upper_[pos / 8] |= 1U << (pos % 8);
 161     // Append numLowerBits bits to lower sequence.
 162     if (numLowerBits != 0) {
 163       const ValueType lowerBits = value & ((ValueType(1) << numLowerBits) - 1);
 164       writeBits56(lower_, size_ * numLowerBits, numLowerBits, lowerBits);
 165     }
 166
 167     /* static */ if (skipQuantum != 0) {
 168       while ((skipPointersSize_ + 1) * skipQuantum <= upperBits) {
 169         // Store the number of preceding 1-bits.
 170         skipPointers_[skipPointersSize_++] = size_;
 171       }
 172     }
 173
 174     /* static */ if (forwardQuantum != 0) {
 175       if ((size_ + 1) % forwardQuantum == 0) {
 176         const auto pos = size_ / forwardQuantum;
 177         // Store the number of preceding 0-bits.
 178         forwardPointers_[pos] = upperBits;
 179       }
 180     }
 181
 182     lastValue_ = value;
 183     ++size_;
 184   }
 185
 186   const EliasFanoCompressedList& finish() const {
 187     CHECK_EQ(size_, result_.size);
 188     return result_;
 189   }
 190
 191  private:
 192   // Writes value (with len up to 56 bits) to data starting at pos-th bit.
 193   static void writeBits56(unsigned char* data, size_t pos,
 194                           uint8_t len, uint64_t value) {
 195     DCHECK_LE(uint32_t(len), 56);
 196     DCHECK_EQ(0, value & ~((uint64_t(1) << len) - 1));
 197     unsigned char* const ptr = data + (pos / 8);
 198     uint64_t ptrv = folly::loadUnaligned<uint64_t>(ptr);
 199     ptrv |= value << (pos % 8);
 200     folly::storeUnaligned<uint64_t>(ptr, ptrv);
 201   }
 202
 203   unsigned char* lower_ = nullptr;
 204   unsigned char* upper_ = nullptr;
 205   SkipValueType* skipPointers_ = nullptr;
 206   SkipValueType* forwardPointers_ = nullptr;
 207
 208   ValueType lastValue_ = 0;
 209   size_t size_ = 0;
 210   size_t skipPointersSize_ = 0;
 211
 212   EliasFanoCompressedList result_;
 213 };
 214
 215 template <class Value,
 216           class SkipValue,
 217           size_t kSkipQuantum,
 218           size_t kForwardQuantum>
 219 struct EliasFanoEncoderV2<Value,
 220                           SkipValue,
 221                           kSkipQuantum,
 222                           kForwardQuantum>::Layout {
 223   static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
 224     // numLowerBits can be at most 56 because of detail::writeBits56.
 225     const uint8_t numLowerBits = std::min(defaultNumLowerBits(upperBound,
 226                                                               size),
 227                                           uint8_t(56));
 228     // *** Upper bits.
 229     // Upper bits are stored using unary delta encoding.
 230     // For example, (3 5 5 9) will be encoded as 1000011001000_2.
 231     const size_t upperSizeBits =
 232       (upperBound >> numLowerBits) +  // Number of 0-bits to be stored.
 233       size;                           // 1-bits.
 234     const size_t upper = (upperSizeBits + 7) / 8;
 235
 236     // *** Validity checks.
 237     // Shift by numLowerBits must be valid.
 238     CHECK_LT(numLowerBits, 8 * sizeof(Value));
 239     CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
 240     CHECK_LT(upperBound >> numLowerBits,
 241              std::numeric_limits<SkipValueType>::max());
 242
 243     return fromInternalSizes(numLowerBits, upper, size);
 244   }
 245
 246   static Layout fromInternalSizes(uint8_t numLowerBits,
 247                                   size_t upper,
 248                                   size_t size) {
 249     Layout layout;
 250     layout.size = size;
 251     layout.numLowerBits = numLowerBits;
 252
 253     layout.lower = (numLowerBits * size + 7) / 8;
 254     layout.upper = upper;
 255
 256     // *** Skip pointers.
 257     // Store (1-indexed) position of every skipQuantum-th
 258     // 0-bit in upper bits sequence.
 259     /* static */ if (skipQuantum != 0) {
 260       // 8 * upper is used here instead of upperSizeBits, as that is
 261       // more serialization-friendly way (upperSizeBits doesn't need
 262       // to be known by this function, unlike upper).
 263
 264       // '?: 1' is a workaround for false 'division by zero'
 265       // compile-time error.
 266       size_t numSkipPointers = (8 * upper - size) / (skipQuantum ?: 1);
 267       layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
 268     }
 269
 270     // *** Forward pointers.
 271     // Store (1-indexed) position of every forwardQuantum-th
 272     // 1-bit in upper bits sequence.
 273     /* static */ if (forwardQuantum != 0) {
 274       size_t numForwardPointers = size / (forwardQuantum ?: 1);
 275       layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
 276     }
 277
 278     return layout;
 279   }
 280
 281   size_t bytes() const {
 282     return lower + upper + skipPointers + forwardPointers;
 283   }
 284
 285   template <typename Range>
 286   EliasFanoCompressedListBase<typename Range::iterator>
 287   openList(Range& buf) const {
 288     EliasFanoCompressedListBase<typename Range::iterator> result;
 289     result.size = size;
 290     result.numLowerBits = numLowerBits;
 291     result.data = buf.subpiece(0, bytes());
 292
 293     auto advance = [&] (size_t n) {
 294       auto begin = buf.data();
 295       buf.advance(n);
 296       return begin;
 297     };
 298
 299     result.skipPointers = advance(skipPointers);
 300     result.forwardPointers = advance(forwardPointers);
 301     result.lower = advance(lower);
 302     result.upper = advance(upper);
 303
 304     return result;
 305   }
 306
 307   MutableEliasFanoCompressedList allocList() const {
 308     uint8_t* buf = nullptr;
 309     // WARNING: Current read/write logic assumes that the 7 bytes
 310     // following the last byte of lower and upper sequences are
 311     // readable (stored value doesn't matter and won't be changed),
 312     // so we allocate additional 7B, but do not include them in size
 313     // of returned value.
 314     if (size > 0) {
 315       buf = static_cast<uint8_t*>(calloc(bytes() + 7, 1));
 316     }
 317     folly::MutableByteRange bufRange(buf, bytes());
 318     return openList(bufRange);
 319   }
 320
 321   size_t size = 0;
 322   uint8_t numLowerBits = 0;
 323
 324   // Sizes in bytes.
 325   size_t lower = 0;
 326   size_t upper = 0;
 327   size_t skipPointers = 0;
 328   size_t forwardPointers = 0;
 329 };
 330
 331 // NOTE: It's recommended to compile EF coding with -msse4.2, starting
 332 // with Nehalem, Intel CPUs support POPCNT instruction and gcc will emit
 333 // it for __builtin_popcountll intrinsic.
 334 // But we provide an alternative way for the client code: it can switch to
 335 // the appropriate version of EliasFanoReader<> in realtime (client should
 336 // implement this switching logic itself) by specifying instruction set to
 337 // use explicitly.
 338 namespace instructions {
 339
 340 struct Default {
 341   static bool supported(const folly::CpuId& cpuId = {}) {
 342     return true;
 343   }
 344   static inline uint64_t popcount(uint64_t value) {
 345     return __builtin_popcountll(value);
 346   }
 347   static inline int ctz(uint64_t value) {
 348     DCHECK_GT(value, 0);
 349     return __builtin_ctzll(value);
 350   }
 351   static inline uint64_t blsr(uint64_t value) {
 352     return value & (value - 1);
 353   }
 354 };
 355
 356 struct Nehalem : public Default {
 357   static bool supported(const folly::CpuId& cpuId = {}) {
 358     return cpuId.popcnt();
 359   }
 360   static inline uint64_t popcount(uint64_t value) {
 361     // POPCNT is supported starting with Intel Nehalem, AMD K10.
 362     uint64_t result;
 363     asm ("popcntq %1, %0" : "=r" (result) : "r" (value));
 364     return result;
 365   }
 366 };
 367
 368 struct Haswell : public Nehalem {
 369   static bool supported(const folly::CpuId& cpuId = {}) {
 370     return Nehalem::supported(cpuId) && cpuId.bmi1();
 371   }
 372   static inline uint64_t blsr(uint64_t value) {
 373     // BMI1 is supported starting with Intel Haswell, AMD Piledriver.
 374     // BLSR combines two instuctions into one and reduces register pressure.
 375     uint64_t result;
 376     asm ("blsrq %1, %0" : "=r" (result) : "r" (value));
 377     return result;
 378   }
 379 };
 380
 381 }  // namespace instructions
 382
 383 namespace detail {
 384
 385 template <class Encoder, class Instructions>
 386 class UpperBitsReader {
 387   typedef typename Encoder::SkipValueType SkipValueType;
 388  public:
 389   typedef typename Encoder::ValueType ValueType;
 390
 391   explicit UpperBitsReader(const EliasFanoCompressedList& list)
 392     : forwardPointers_(list.forwardPointers),
 393       skipPointers_(list.skipPointers),
 394       start_(list.upper) {
 395     reset();
 396   }
 397
 398   void reset() {
 399     block_ = start_ != nullptr ? folly::loadUnaligned<block_t>(start_) : 0;
 400     outer_ = 0;
 401     inner_ = -1;
 402     position_ = -1;
 403     value_ = 0;
 404   }
 405
 406   size_t position() const { return position_; }
 407   ValueType value() const { return value_; }
 408
 409   ValueType next() {
 410     // Skip to the first non-zero block.
 411     while (block_ == 0) {
 412       outer_ += sizeof(block_t);
 413       block_ = folly::loadUnaligned<block_t>(start_ + outer_);
 414     }
 415
 416     ++position_;
 417     inner_ = Instructions::ctz(block_);
 418     block_ = Instructions::blsr(block_);
 419
 420     return setValue();
 421   }
 422
 423   ValueType skip(size_t n) {
 424     DCHECK_GT(n, 0);
 425
 426     position_ += n;  // n 1-bits will be read.
 427
 428     // Use forward pointer.
 429     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
 430       // Workaround to avoid 'division by zero' compile-time error.
 431       constexpr size_t q = Encoder::forwardQuantum ?: 1;
 432
 433       const size_t steps = position_ / q;
 434       const size_t dest =
 435         folly::loadUnaligned<SkipValueType>(
 436             forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
 437
 438       reposition(dest + steps * q);
 439       n = position_ + 1 - steps * q;  // n is > 0.
 440       // Correct inner_ will be set at the end.
 441     }
 442
 443     size_t cnt;
 444     // Find necessary block.
 445     while ((cnt = Instructions::popcount(block_)) < n) {
 446       n -= cnt;
 447       outer_ += sizeof(block_t);
 448       block_ = folly::loadUnaligned<block_t>(start_ + outer_);
 449     }
 450
 451     // Skip to the n-th one in the block.
 452     DCHECK_GT(n, 0);
 453     inner_ = select64<Instructions>(block_, n - 1);
 454     block_ &= (block_t(-1) << inner_) << 1;
 455
 456     return setValue();
 457   }
 458
 459   // Skip to the first element that is >= v and located *after* the current
 460   // one (so even if current value equals v, position will be increased by 1).
 461   ValueType skipToNext(ValueType v) {
 462     DCHECK_GE(v, value_);
 463
 464     // Use skip pointer.
 465     if (Encoder::skipQuantum > 0 && v >= value_ + Encoder::skipQuantum) {
 466       // Workaround to avoid 'division by zero' compile-time error.
 467       constexpr size_t q = Encoder::skipQuantum ?: 1;
 468
 469       const size_t steps = v / q;
 470       const size_t dest =
 471         folly::loadUnaligned<SkipValueType>(
 472             skipPointers_ + (steps - 1) * sizeof(SkipValueType));
 473
 474       reposition(dest + q * steps);
 475       position_ = dest - 1;
 476
 477       // Correct inner_ and value_ will be set during the next()
 478       // call at the end.
 479
 480       // NOTE: Corresponding block of lower bits sequence may be
 481       // prefetched here (via __builtin_prefetch), but experiments
 482       // didn't show any significant improvements.
 483     }
 484
 485     // Skip by blocks.
 486     size_t cnt;
 487     size_t skip = v - (8 * outer_ - position_ - 1);
 488
 489     constexpr size_t kBitsPerBlock = 8 * sizeof(block_t);
 490     while ((cnt = Instructions::popcount(~block_)) < skip) {
 491       skip -= cnt;
 492       position_ += kBitsPerBlock - cnt;
 493       outer_ += sizeof(block_t);
 494       block_ = folly::loadUnaligned<block_t>(start_ + outer_);
 495     }
 496
 497     if (LIKELY(skip)) {
 498       auto inner = select64<Instructions>(~block_, skip - 1);
 499       position_ += inner - skip + 1;
 500       block_ &= block_t(-1) << inner;
 501     }
 502
 503     next();
 504     return value_;
 505   }
 506
 507   ValueType jump(size_t n) {
 508     if (Encoder::forwardQuantum == 0 || n <= Encoder::forwardQuantum) {
 509       reset();
 510     } else {
 511       position_ = -1;  // Avoid reading the head, skip() will reposition.
 512     }
 513     return skip(n);
 514   }
 515
 516   ValueType jumpToNext(ValueType v) {
 517     if (Encoder::skipQuantum == 0 || v < Encoder::skipQuantum) {
 518       reset();
 519     } else {
 520       value_ = 0;  // Avoid reading the head, skipToNext() will reposition.
 521     }
 522     return skipToNext(v);
 523   }
 524
 525   void setDone(size_t endPos) {
 526     position_ = endPos;
 527   }
 528
 529  private:
 530   ValueType setValue() {
 531     value_ = static_cast<ValueType>(8 * outer_ + inner_ - position_);
 532     return value_;
 533   }
 534
 535   void reposition(size_t dest) {
 536     outer_ = dest / 8;
 537     block_ = folly::loadUnaligned<block_t>(start_ + outer_);
 538     block_ &= ~((block_t(1) << (dest % 8)) - 1);
 539   }
 540
 541   typedef unsigned long long block_t;
 542   const unsigned char* const forwardPointers_;
 543   const unsigned char* const skipPointers_;
 544   const unsigned char* const start_;
 545   block_t block_;
 546   size_t outer_;  // Outer offset: number of consumed bytes in upper.
 547   size_t inner_;  // Inner offset: (bit) position in current block.
 548   size_t position_;  // Index of current value (= #reads - 1).
 549   ValueType value_;
 550 };
 551
 552 }  // namespace detail
 553
 554 template <class Encoder,
 555           class Instructions = instructions::Default>
 556 class EliasFanoReader : private boost::noncopyable {
 557  public:
 558   typedef Encoder EncoderType;
 559   typedef typename Encoder::ValueType ValueType;
 560
 561   explicit EliasFanoReader(const EliasFanoCompressedList& list)
 562       : size_(list.size),
 563         lower_(list.lower),
 564         upper_(list),
 565         lowerMask_((ValueType(1) << list.numLowerBits) - 1),
 566         numLowerBits_(list.numLowerBits) {
 567     DCHECK(Instructions::supported());
 568     // To avoid extra branching during skipTo() while reading
 569     // upper sequence we need to know the last element.
 570     if (UNLIKELY(list.size == 0)) {
 571       lastValue_ = 0;
 572       return;
 573     }
 574     ValueType lastUpperValue = 8 * list.upperSize() - size_;
 575     auto it = list.upper + list.upperSize() - 1;
 576     DCHECK_NE(*it, 0);
 577     lastUpperValue -= 8 - folly::findLastSet(*it);
 578     lastValue_ = readLowerPart(size_ - 1) | (lastUpperValue << numLowerBits_);
 579   }
 580
 581   void reset() {
 582     upper_.reset();
 583     value_ = 0;
 584   }
 585
 586   bool next() {
 587     if (UNLIKELY(position() + 1 >= size_)) {
 588       return setDone();
 589     }
 590     upper_.next();
 591     value_ = readLowerPart(upper_.position()) |
 592              (upper_.value() << numLowerBits_);
 593     return true;
 594   }
 595
 596   bool skip(size_t n) {
 597     CHECK_GT(n, 0);
 598
 599     if (LIKELY(position() + n < size_)) {
 600       if (LIKELY(n < kLinearScanThreshold)) {
 601         for (size_t i = 0; i < n; ++i) upper_.next();
 602       } else {
 603         upper_.skip(n);
 604       }
 605       value_ = readLowerPart(upper_.position()) |
 606         (upper_.value() << numLowerBits_);
 607       return true;
 608     }
 609
 610     return setDone();
 611   }
 612
 613   bool skipTo(ValueType value) {
 614     DCHECK_GE(value, value_);
 615     if (value <= value_) {
 616       return true;
 617     } else if (value > lastValue_) {
 618       return setDone();
 619     }
 620
 621     size_t upperValue = (value >> numLowerBits_);
 622     size_t upperSkip = upperValue - upper_.value();
 623     // The average density of ones in upper bits is 1/2.
 624     // LIKELY here seems to make things worse, even for small skips.
 625     if (upperSkip < 2 * kLinearScanThreshold) {
 626       do {
 627         upper_.next();
 628       } while (UNLIKELY(upper_.value() < upperValue));
 629     } else {
 630       upper_.skipToNext(upperValue);
 631     }
 632
 633     iterateTo(value);
 634     return true;
 635   }
 636
 637   bool jump(size_t n) {
 638     if (LIKELY(n - 1 < size_)) {  // n > 0 && n <= size_
 639       value_ = readLowerPart(n - 1) | (upper_.jump(n) << numLowerBits_);
 640       return true;
 641     } else if (n == 0) {
 642       reset();
 643       return true;
 644     }
 645     return setDone();
 646   }
 647
 648   bool jumpTo(ValueType value) {
 649     if (value <= 0) {
 650       reset();
 651       return true;
 652     } else if (value > lastValue_) {
 653       return setDone();
 654     }
 655
 656     upper_.jumpToNext(value >> numLowerBits_);
 657     iterateTo(value);
 658     return true;
 659   }
 660
 661   size_t size() const { return size_; }
 662
 663   size_t position() const { return upper_.position(); }
 664   ValueType value() const { return value_; }
 665
 666  private:
 667   bool setDone() {
 668     value_ = std::numeric_limits<ValueType>::max();
 669     upper_.setDone(size_);
 670     return false;
 671   }
 672
 673   ValueType readLowerPart(size_t i) const {
 674     DCHECK_LT(i, size_);
 675     const size_t pos = i * numLowerBits_;
 676     const unsigned char* ptr = lower_ + (pos / 8);
 677     const uint64_t ptrv = folly::loadUnaligned<uint64_t>(ptr);
 678     return lowerMask_ & (ptrv >> (pos % 8));
 679   }
 680
 681   void iterateTo(ValueType value) {
 682     while (true) {
 683       value_ = readLowerPart(upper_.position()) |
 684         (upper_.value() << numLowerBits_);
 685       if (LIKELY(value_ >= value)) break;
 686       upper_.next();
 687     }
 688   }
 689
 690   constexpr static size_t kLinearScanThreshold = 8;
 691
 692   size_t size_;
 693   const uint8_t* lower_;
 694   detail::UpperBitsReader<Encoder, Instructions> upper_;
 695   const ValueType lowerMask_;
 696   ValueType value_ = 0;
 697   ValueType lastValue_;
 698   uint8_t numLowerBits_;
 699 };
 700
 701 }}  // namespaces
 702
 703 #endif  // FOLLY_EXPERIMENTAL_ELIAS_FANO_CODING_H