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   typedef typename Encoder::SkipValueType SkipValueType;
 244
 245   explicit BitVectorReader(const typename Encoder::CompressedList& list)
 246       : size_(list.size),
 247         bits_(list.bits),
 248         skipPointers_(list.skipPointers),
 249         forwardPointers_(list.forwardPointers) {
 250     reset();
 251
 252     if (kUnchecked || UNLIKELY(list.size == 0)) {
 253       upperBound_ = 0;
 254       return;
 255     }
 256
 257     upperBound_ = list.upperBound;
 258   }
 259
 260   void reset() {
 261     block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
 262     outer_ = 0;
 263     inner_ = -1;
 264     position_ = -1;
 265     value_ = kInvalidValue;
 266   }
 267
 268   bool next() {
 269     if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
 270       return setDone();
 271     }
 272
 273     while (block_ == 0) {
 274       outer_ += sizeof(uint64_t);
 275       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 276     }
 277
 278     ++position_;
 279     inner_ = Instructions::ctz(block_);
 280     block_ = Instructions::blsr(block_);
 281
 282     return setValue();
 283   }
 284
 285   bool skip(size_t n) {
 286     CHECK_GT(n, 0);
 287
 288     if (!kUnchecked && position() + n >= size_) {
 289       return setDone();
 290     }
 291     // Small skip optimization.
 292     if (LIKELY(n < kLinearScanThreshold)) {
 293       for (size_t i = 0; i < n; ++i) {
 294         next();
 295       }
 296       return true;
 297     }
 298
 299     position_ += n;
 300
 301     // Use forward pointer.
 302     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
 303       const size_t steps = position_ / Encoder::forwardQuantum;
 304       const size_t dest = folly::loadUnaligned<SkipValueType>(
 305           forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
 306
 307       reposition(dest);
 308       n = position_ + 1 - steps * Encoder::forwardQuantum;
 309       // Correct inner_ will be set at the end.
 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     inner_ = select64<Instructions>(block_, n - 1);
 323     block_ &= (uint64_t(-1) << inner_) << 1;
 324
 325     return setValue();
 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       position_ = size_t(folly::loadUnaligned<SkipValueType>(
 350                       skipPointers_ + (q - 1) * sizeof(SkipValueType))) - 1;
 351
 352       reposition(q * Encoder::skipQuantum);
 353     }
 354
 355     // Find the value.
 356     size_t outer = v / 64 * 8;
 357
 358     while (outer_ < outer) {
 359       position_ += Instructions::popcount(block_);
 360       outer_ += sizeof(uint64_t);
 361       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 362     }
 363
 364     DCHECK_EQ(outer_, outer);
 365     uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
 366     position_ += Instructions::popcount(block_ & ~mask) + 1;
 367     block_ &= mask;
 368
 369     while (block_ == 0) {
 370       outer_ += sizeof(uint64_t);
 371       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 372     }
 373
 374     inner_ = Instructions::ctz(block_);
 375     block_ = Instructions::blsr(block_);
 376
 377     setValue();
 378     return true;
 379   }
 380
 381   size_t size() const { return size_; }
 382
 383   bool valid() const {
 384     return position() < size(); // Also checks that position() != -1.
 385   }
 386
 387   size_t position() const { return position_; }
 388   ValueType value() const {
 389     DCHECK(valid());
 390     return value_;
 391   }
 392
 393   bool jump(size_t n) {
 394     reset();
 395     return skip(n + 1);
 396   }
 397
 398   bool jumpTo(ValueType v) {
 399     reset();
 400     return skipTo(v);
 401   }
 402
 403   bool setDone() {
 404     value_ = kInvalidValue;
 405     position_ = size_;
 406     return false;
 407   }
 408
 409  private:
 410   constexpr static ValueType kInvalidValue =
 411     std::numeric_limits<ValueType>::max();  // Must hold kInvalidValue + 1 == 0.
 412
 413   bool setValue() {
 414     value_ = static_cast<ValueType>(8 * outer_ + inner_);
 415     return true;
 416   }
 417
 418   void reposition(size_t dest) {
 419     outer_ = dest / 64 * 8;
 420     // We maintain the invariant that outer_ is divisible by 8.
 421     block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 422     block_ &= ~((uint64_t(1) << (dest % 64)) - 1);
 423   }
 424
 425   constexpr static size_t kLinearScanThreshold = 4;
 426
 427   size_t outer_;
 428   size_t inner_;
 429   size_t position_;
 430   uint64_t block_;
 431   ValueType value_;
 432
 433   size_t size_;
 434   ValueType upperBound_;
 435   const uint8_t* const bits_;
 436   const uint8_t* const skipPointers_;
 437   const uint8_t* const forwardPointers_;
 438 };
 439
 440 }}  // namespaces