+ /* static */ if (skipQuantum != 0) {
+ while ((skipPointersSize_ + 1) * skipQuantum <= upperBits) {
+ // Store the number of preceding 1-bits.
+ skipPointers_[skipPointersSize_++] = size_;
+ }
+ }
+
+ /* static */ if (forwardQuantum != 0) {
+ if ((size_ + 1) % forwardQuantum == 0) {
+ const auto pos = size_ / forwardQuantum;
+ // Store the number of preceding 0-bits.
+ forwardPointers_[pos] = upperBits;
+ }
+ }
+
+ lastValue_ = value;
+ ++size_;
+ }
+
+ const EliasFanoCompressedList& finish() const {
+ CHECK_EQ(size_, result_.size);
+ return result_;
+ }
+
+ private:
+ // Writes value (with len up to 56 bits) to data starting at pos-th bit.
+ static void writeBits56(unsigned char* data, size_t pos,
+ uint8_t len, uint64_t value) {
+ DCHECK_LE(uint32_t(len), 56);
+ DCHECK_EQ(0, value & ~((uint64_t(1) << len) - 1));
+ unsigned char* const ptr = data + (pos / 8);
+ uint64_t ptrv = folly::loadUnaligned<uint64_t>(ptr);
+ ptrv |= value << (pos % 8);
+ folly::storeUnaligned<uint64_t>(ptr, ptrv);
+ }
+
+ unsigned char* lower_ = nullptr;
+ unsigned char* upper_ = nullptr;
+ SkipValueType* skipPointers_ = nullptr;
+ SkipValueType* forwardPointers_ = nullptr;
+
+ ValueType lastValue_ = 0;
+ size_t size_ = 0;
+ size_t skipPointersSize_ = 0;
+
+ EliasFanoCompressedList result_;
+};
+
+template <class Value,
+ class SkipValue,
+ size_t kSkipQuantum,
+ size_t kForwardQuantum>
+struct EliasFanoEncoderV2<Value,
+ SkipValue,
+ kSkipQuantum,
+ kForwardQuantum>::Layout {
+ static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
+ // numLowerBits can be at most 56 because of detail::writeBits56.
+ const uint8_t numLowerBits = std::min(defaultNumLowerBits(upperBound,
+ size),
+ uint8_t(56));