folly/experimental/BitVectorCoding.h

   1 /*
   2  * Copyright 2016 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 #pragma once
  18
  19 #include <cstdlib>
  20 #include <limits>
  21 #include <type_traits>
  22
  23 #include <folly/Bits.h>
  24 #include <folly/Likely.h>
  25 #include <folly/Portability.h>
  26 #include <folly/Range.h>
  27 #include <folly/experimental/Bits.h>
  28 #include <folly/experimental/Instructions.h>
  29 #include <folly/experimental/Select64.h>
  30 #include <glog/logging.h>
  31
  32 #ifndef __GNUC__
  33 #error BitVectorCoding.h requires GCC
  34 #endif
  35
  36 #if !FOLLY_X64
  37 #error BitVectorCoding.h requires x86_64
  38 #endif
  39
  40 #if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
  41 #error BitVectorCoding.h requires little endianness
  42 #endif
  43
  44 namespace folly { namespace compression {
  45
  46 template <class Pointer>
  47 struct BitVectorCompressedListBase {
  48   BitVectorCompressedListBase() = default;
  49
  50   template <class OtherPointer>
  51   BitVectorCompressedListBase(
  52       const BitVectorCompressedListBase<OtherPointer>& other)
  53       : size(other.size),
  54         upperBound(other.upperBound),
  55         data(other.data),
  56         bits(reinterpret_cast<Pointer>(other.bits)),
  57         skipPointers(reinterpret_cast<Pointer>(other.skipPointers)),
  58         forwardPointers(reinterpret_cast<Pointer>(other.forwardPointers)) {}
  59
  60   template <class T = Pointer>
  61   auto free() -> decltype(::free(T(nullptr))) {
  62     return ::free(data.data());
  63   }
  64
  65   size_t size = 0;
  66   size_t upperBound = 0;
  67
  68   folly::Range<Pointer> data;
  69
  70   Pointer bits = nullptr;
  71   Pointer skipPointers = nullptr;
  72   Pointer forwardPointers = nullptr;
  73 };
  74
  75 typedef BitVectorCompressedListBase<const uint8_t*> BitVectorCompressedList;
  76 typedef BitVectorCompressedListBase<uint8_t*> MutableBitVectorCompressedList;
  77
  78 template <class Value,
  79           class SkipValue,
  80           size_t kSkipQuantum = 0,
  81           size_t kForwardQuantum = 0>
  82 struct BitVectorEncoder {
  83   static_assert(std::is_integral<Value>::value &&
  84                     std::is_unsigned<Value>::value,
  85                 "Value should be unsigned integral");
  86
  87   typedef BitVectorCompressedList CompressedList;
  88   typedef MutableBitVectorCompressedList MutableCompressedList;
  89
  90   typedef Value ValueType;
  91   typedef SkipValue SkipValueType;
  92   struct Layout;
  93
  94   static constexpr size_t skipQuantum = kSkipQuantum;
  95   static constexpr size_t forwardQuantum = kForwardQuantum;
  96
  97   template <class RandomAccessIterator>
  98   static MutableCompressedList encode(RandomAccessIterator begin,
  99                                       RandomAccessIterator end) {
 100     if (begin == end) {
 101       return MutableCompressedList();
 102     }
 103     BitVectorEncoder encoder(end - begin, *(end - 1));
 104     for (; begin != end; ++begin) {
 105       encoder.add(*begin);
 106     }
 107     return encoder.finish();
 108   }
 109
 110   explicit BitVectorEncoder(const MutableCompressedList& result)
 111       : bits_(result.bits),
 112         skipPointers_(result.skipPointers),
 113         forwardPointers_(result.forwardPointers),
 114         result_(result) {
 115     memset(result.data.data(), 0, result.data.size());
 116   }
 117
 118   BitVectorEncoder(size_t size, ValueType upperBound)
 119       : BitVectorEncoder(
 120             Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {}
 121
 122   void add(ValueType value) {
 123     CHECK_LT(value, std::numeric_limits<ValueType>::max());
 124     // Also works when lastValue_ == -1.
 125     CHECK_GT(value + 1, lastValue_ + 1)
 126       << "BitVectorCoding only supports stricly monotone lists";
 127
 128     auto block = bits_ + (value / 64) * sizeof(uint64_t);
 129     size_t inner = value % 64;
 130     folly::Bits<folly::Unaligned<uint64_t>>::set(
 131         reinterpret_cast<folly::Unaligned<uint64_t>*>(block), inner);
 132
 133     if (skipQuantum != 0) {
 134       size_t nextSkipPointerSize = value / (skipQuantum ?: 1);
 135       while (skipPointersSize_ < nextSkipPointerSize) {
 136         auto pos = skipPointersSize_++;
 137         folly::storeUnaligned<SkipValueType>(
 138             skipPointers_ + pos * sizeof(SkipValueType), size_);
 139       }
 140     }
 141
 142     if (forwardQuantum != 0) {
 143       if (size_ != 0 && (size_ % (forwardQuantum ?: 1) == 0)) {
 144         const auto pos = size_ / (forwardQuantum ?: 1) - 1;
 145         folly::storeUnaligned<SkipValueType>(
 146             forwardPointers_ + pos * sizeof(SkipValueType), value);
 147       }
 148     }
 149
 150     lastValue_ = value;
 151     ++size_;
 152   }
 153
 154   const MutableCompressedList& finish() const {
 155     CHECK_EQ(size_, result_.size);
 156     // TODO(ott): Relax this assumption.
 157     CHECK_EQ(result_.upperBound, lastValue_);
 158     return result_;
 159   }
 160
 161  private:
 162   uint8_t* const bits_ = nullptr;
 163   uint8_t* const skipPointers_ = nullptr;
 164   uint8_t* const forwardPointers_ = nullptr;
 165
 166   ValueType lastValue_ = -1;
 167   size_t size_ = 0;
 168   size_t skipPointersSize_ = 0;
 169
 170   MutableCompressedList result_;
 171 };
 172
 173 template <class Value,
 174           class SkipValue,
 175           size_t kSkipQuantum,
 176           size_t kForwardQuantum>
 177 struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
 178     Layout {
 179   static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
 180     Layout layout;
 181     layout.size = size;
 182     layout.upperBound = upperBound;
 183
 184     size_t bitVectorSizeInBytes = (upperBound / 8) + 1;
 185     layout.bits = bitVectorSizeInBytes;
 186
 187     if (skipQuantum != 0) {
 188       size_t numSkipPointers = upperBound / (skipQuantum ?: 1);
 189       layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
 190     }
 191     if (forwardQuantum != 0) {
 192       size_t numForwardPointers = size / (forwardQuantum ?: 1);
 193       layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
 194     }
 195
 196     CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
 197
 198     return layout;
 199   }
 200
 201   size_t bytes() const { return bits + skipPointers + forwardPointers; }
 202
 203   template <class Range>
 204   BitVectorCompressedListBase<typename Range::iterator> openList(
 205       Range& buf) const {
 206     BitVectorCompressedListBase<typename Range::iterator> result;
 207     result.size = size;
 208     result.upperBound = upperBound;
 209     result.data = buf.subpiece(0, bytes());
 210     auto advance = [&](size_t n) {
 211       auto begin = buf.data();
 212       buf.advance(n);
 213       return begin;
 214     };
 215
 216     result.bits = advance(bits);
 217     result.skipPointers = advance(skipPointers);
 218     result.forwardPointers = advance(forwardPointers);
 219     CHECK_EQ(buf.data() - result.data.data(), bytes());
 220
 221     return result;
 222   }
 223
 224   MutableCompressedList allocList() const {
 225     uint8_t* buf = nullptr;
 226     if (size > 0) {
 227       buf = static_cast<uint8_t*>(malloc(bytes() + 7));
 228     }
 229     folly::MutableByteRange bufRange(buf, bytes());
 230     return openList(bufRange);
 231   }
 232
 233   size_t size = 0;
 234   size_t upperBound = 0;
 235
 236   // Sizes in bytes.
 237   size_t bits = 0;
 238   size_t skipPointers = 0;
 239   size_t forwardPointers = 0;
 240 };
 241
 242 template <class Encoder,
 243           class Instructions = instructions::Default,
 244           bool kUnchecked = false>
 245 class BitVectorReader {
 246  public:
 247   typedef Encoder EncoderType;
 248   typedef typename Encoder::ValueType ValueType;
 249   typedef typename Encoder::SkipValueType SkipValueType;
 250
 251   explicit BitVectorReader(const typename Encoder::CompressedList& list)
 252       : size_(list.size),
 253         bits_(list.bits),
 254         skipPointers_(list.skipPointers),
 255         forwardPointers_(list.forwardPointers) {
 256     reset();
 257
 258     if (kUnchecked || UNLIKELY(list.size == 0)) {
 259       upperBound_ = 0;
 260       return;
 261     }
 262
 263     upperBound_ = list.upperBound;
 264   }
 265
 266   void reset() {
 267     block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
 268     outer_ = 0;
 269     inner_ = -1;
 270     position_ = -1;
 271     value_ = kInvalidValue;
 272   }
 273
 274   bool next() {
 275     if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
 276       return setDone();
 277     }
 278
 279     while (block_ == 0) {
 280       outer_ += sizeof(uint64_t);
 281       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 282     }
 283
 284     ++position_;
 285     inner_ = Instructions::ctz(block_);
 286     block_ = Instructions::blsr(block_);
 287
 288     return setValue();
 289   }
 290
 291   bool skip(size_t n) {
 292     CHECK_GT(n, 0);
 293
 294     if (!kUnchecked && position() + n >= size_) {
 295       return setDone();
 296     }
 297     // Small skip optimization.
 298     if (LIKELY(n < kLinearScanThreshold)) {
 299       for (size_t i = 0; i < n; ++i) {
 300         next();
 301       }
 302       return true;
 303     }
 304
 305     position_ += n;
 306
 307     // Use forward pointer.
 308     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
 309       // Workaround to avoid 'division by zero' compile-time error.
 310       constexpr size_t q = Encoder::forwardQuantum ?: 1;
 311
 312       const size_t steps = position_ / q;
 313       const size_t dest = folly::loadUnaligned<SkipValueType>(
 314           forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
 315
 316       reposition(dest);
 317       n = position_ + 1 - steps * q;
 318       // Correct inner_ will be set at the end.
 319     }
 320
 321     size_t cnt;
 322     // Find necessary block.
 323     while ((cnt = Instructions::popcount(block_)) < n) {
 324       n -= cnt;
 325       outer_ += sizeof(uint64_t);
 326       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 327     }
 328
 329     // Skip to the n-th one in the block.
 330     DCHECK_GT(n, 0);
 331     inner_ = select64<Instructions>(block_, n - 1);
 332     block_ &= (uint64_t(-1) << inner_) << 1;
 333
 334     return setValue();
 335   }
 336
 337   bool skipTo(ValueType v) {
 338     // Also works when value_ == kInvalidValue.
 339     if (v != kInvalidValue) { DCHECK_GE(v + 1, value_ + 1); }
 340
 341     if (!kUnchecked && v > upperBound_) {
 342       return setDone();
 343     } else if (v == value_) {
 344       return true;
 345     }
 346
 347     // Small skip optimization.
 348     if (v - value_ < kLinearScanThreshold) {
 349       do {
 350         next();
 351       } while (value() < v);
 352
 353       return true;
 354     }
 355
 356     if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
 357       size_t q = v / Encoder::skipQuantum;
 358       position_ = folly::loadUnaligned<SkipValueType>(
 359                       skipPointers_ + (q - 1) * sizeof(SkipValueType)) - 1;
 360
 361       reposition(q * Encoder::skipQuantum);
 362     }
 363
 364     // Find the value.
 365     size_t outer = v / 64 * 8;
 366
 367     while (outer_ < outer) {
 368       position_ += Instructions::popcount(block_);
 369       outer_ += sizeof(uint64_t);
 370       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 371     }
 372
 373     DCHECK_EQ(outer_, outer);
 374     uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
 375     position_ += Instructions::popcount(block_ & ~mask) + 1;
 376     block_ &= mask;
 377
 378     while (block_ == 0) {
 379       outer_ += sizeof(uint64_t);
 380       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 381     }
 382
 383     inner_ = Instructions::ctz(block_);
 384     block_ = Instructions::blsr(block_);
 385
 386     setValue();
 387     return true;
 388   }
 389
 390   size_t size() const { return size_; }
 391
 392   bool valid() const {
 393     return position() < size(); // Also checks that position() != -1.
 394   }
 395
 396   size_t position() const { return position_; }
 397   ValueType value() const {
 398     DCHECK(valid());
 399     return value_;
 400   }
 401
 402   bool jump(size_t n) {
 403     reset();
 404     return skip(n + 1);
 405   }
 406
 407   bool jumpTo(ValueType v) {
 408     reset();
 409     return skipTo(v);
 410   }
 411
 412   bool setDone() {
 413     value_ = kInvalidValue;
 414     position_ = size_;
 415     return false;
 416   }
 417
 418  private:
 419   constexpr static ValueType kInvalidValue =
 420     std::numeric_limits<ValueType>::max();  // Must hold kInvalidValue + 1 == 0.
 421
 422   bool setValue() {
 423     value_ = static_cast<ValueType>(8 * outer_ + inner_);
 424     return true;
 425   }
 426
 427   void reposition(size_t dest) {
 428     outer_ = dest / 64 * 8;
 429     // We maintain the invariant that outer_ is divisible by 8.
 430     block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 431     block_ &= ~((uint64_t(1) << (dest % 64)) - 1);
 432   }
 433
 434   constexpr static size_t kLinearScanThreshold = 4;
 435
 436   size_t outer_;
 437   size_t inner_;
 438   size_t position_;
 439   uint64_t block_;
 440   ValueType value_;
 441
 442   size_t size_;
 443   ValueType upperBound_;
 444   const uint8_t* const bits_;
 445   const uint8_t* const skipPointers_;
 446   const uint8_t* const forwardPointers_;
 447 };
 448
 449 }}  // namespaces