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