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