folly/experimental/BitVectorCoding.h

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