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_GE(value, lastValue_);
 125     auto block = bits_ + (value / 64) * sizeof(uint64_t);
 126     size_t inner = value % 64;
 127     folly::Bits<folly::Unaligned<uint64_t>>::set(
 128         reinterpret_cast<folly::Unaligned<uint64_t>*>(block), inner);
 129
 130     if (skipQuantum != 0) {
 131       size_t nextSkipPointerSize = value / (skipQuantum ?: 1);
 132       while (skipPointersSize_ < nextSkipPointerSize) {
 133         auto pos = skipPointersSize_++;
 134         folly::storeUnaligned<SkipValueType>(
 135             skipPointers_ + pos * sizeof(SkipValueType), size_);
 136       }
 137     }
 138
 139     if (forwardQuantum != 0) {
 140       if (size_ != 0 && (size_ % (forwardQuantum ?: 1) == 0)) {
 141         const auto pos = size_ / (forwardQuantum ?: 1) - 1;
 142         folly::storeUnaligned<SkipValueType>(
 143             forwardPointers_ + pos * sizeof(SkipValueType), value);
 144       }
 145     }
 146
 147     lastValue_ = value;
 148     ++size_;
 149   }
 150
 151   const MutableCompressedList& finish() const {
 152     CHECK_EQ(size_, result_.size);
 153     // TODO(ott): Relax this assumption.
 154     CHECK_EQ(result_.upperBound, lastValue_);
 155     return result_;
 156   }
 157
 158  private:
 159   uint8_t* const bits_ = nullptr;
 160   uint8_t* const skipPointers_ = nullptr;
 161   uint8_t* const forwardPointers_ = nullptr;
 162
 163   ValueType lastValue_ = 0;
 164   size_t size_ = 0;
 165   size_t skipPointersSize_ = 0;
 166
 167   MutableCompressedList result_;
 168 };
 169
 170 template <class Value,
 171           class SkipValue,
 172           size_t kSkipQuantum,
 173           size_t kForwardQuantum>
 174 struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
 175     Layout {
 176   static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
 177     Layout layout;
 178     layout.size = size;
 179     layout.upperBound = upperBound;
 180
 181     size_t bitVectorSizeInBytes = (upperBound / 8) + 1;
 182     layout.bits = bitVectorSizeInBytes;
 183
 184     if (skipQuantum != 0) {
 185       size_t numSkipPointers = upperBound / (skipQuantum ?: 1);
 186       layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
 187     }
 188     if (forwardQuantum != 0) {
 189       size_t numForwardPointers = size / (forwardQuantum ?: 1);
 190       layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
 191     }
 192
 193     CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
 194
 195     return layout;
 196   }
 197
 198   size_t bytes() const { return bits + skipPointers + forwardPointers; }
 199
 200   template <class Range>
 201   BitVectorCompressedListBase<typename Range::iterator> openList(
 202       Range& buf) const {
 203     BitVectorCompressedListBase<typename Range::iterator> result;
 204     result.size = size;
 205     result.upperBound = upperBound;
 206     result.data = buf.subpiece(0, bytes());
 207     auto advance = [&](size_t n) {
 208       auto begin = buf.data();
 209       buf.advance(n);
 210       return begin;
 211     };
 212
 213     result.bits = advance(bits);
 214     result.skipPointers = advance(skipPointers);
 215     result.forwardPointers = advance(forwardPointers);
 216     CHECK_EQ(buf.data() - result.data.data(), bytes());
 217
 218     return result;
 219   }
 220
 221   MutableCompressedList allocList() const {
 222     uint8_t* buf = nullptr;
 223     if (size > 0) {
 224       buf = static_cast<uint8_t*>(malloc(bytes() + 7));
 225     }
 226     folly::MutableByteRange bufRange(buf, bytes());
 227     return openList(bufRange);
 228   }
 229
 230   size_t size = 0;
 231   size_t upperBound = 0;
 232
 233   // Sizes in bytes.
 234   size_t bits = 0;
 235   size_t skipPointers = 0;
 236   size_t forwardPointers = 0;
 237 };
 238
 239 template <class Encoder,
 240           class Instructions = instructions::Default,
 241           bool kUnchecked = false>
 242 class BitVectorReader {
 243  public:
 244   typedef Encoder EncoderType;
 245   typedef typename Encoder::ValueType ValueType;
 246   typedef typename Encoder::SkipValueType SkipValueType;
 247
 248   explicit BitVectorReader(const typename Encoder::CompressedList& list)
 249       : size_(list.size),
 250         bits_(list.bits),
 251         skipPointers_(list.skipPointers),
 252         forwardPointers_(list.forwardPointers) {
 253     reset();
 254
 255     if (kUnchecked || UNLIKELY(list.size == 0)) {
 256       upperBound_ = 0;
 257       return;
 258     }
 259
 260     upperBound_ = list.upperBound;
 261   }
 262
 263   void reset() {
 264     block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
 265     outer_ = 0;
 266     inner_ = -1;
 267     position_ = -1;
 268     value_ = 0;
 269   }
 270
 271   bool next() {
 272     if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
 273       return setDone();
 274     }
 275
 276     while (block_ == 0) {
 277       outer_ += sizeof(uint64_t);
 278       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 279     }
 280
 281     ++position_;
 282     inner_ = Instructions::ctz(block_);
 283     block_ = Instructions::blsr(block_);
 284
 285     return setValue();
 286   }
 287
 288   bool skip(size_t n) {
 289     CHECK_GT(n, 0);
 290
 291     if (!kUnchecked && position() + n >= size_) {
 292       return setDone();
 293     }
 294     // Small skip optimization.
 295     if (LIKELY(n < kLinearScanThreshold)) {
 296       for (size_t i = 0; i < n; ++i) {
 297         next();
 298       }
 299       return true;
 300     }
 301
 302     position_ += n;
 303
 304     // Use forward pointer.
 305     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
 306       // Workaround to avoid 'division by zero' compile-time error.
 307       constexpr size_t q = Encoder::forwardQuantum ?: 1;
 308
 309       const size_t steps = position_ / q;
 310       const size_t dest = folly::loadUnaligned<SkipValueType>(
 311           forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
 312
 313       reposition(dest);
 314       n = position_ + 1 - steps * q;
 315       // Correct inner_ will be set at the end.
 316     }
 317
 318     size_t cnt;
 319     // Find necessary block.
 320     while ((cnt = Instructions::popcount(block_)) < n) {
 321       n -= cnt;
 322       outer_ += sizeof(uint64_t);
 323       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 324     }
 325
 326     // Skip to the n-th one in the block.
 327     DCHECK_GT(n, 0);
 328     inner_ = select64<Instructions>(block_, n - 1);
 329     block_ &= (uint64_t(-1) << inner_) << 1;
 330
 331     return setValue();
 332   }
 333
 334   bool skipTo(ValueType v) {
 335     DCHECK_GE(v, value_);
 336     if (v <= value_) {
 337       return true;
 338     } else if (!kUnchecked && v > upperBound_) {
 339       return setDone();
 340     }
 341
 342     // Small skip optimization.
 343     if (v - value_ < kLinearScanThreshold) {
 344       do {
 345         next();
 346       } while (value() < v);
 347
 348       return true;
 349     }
 350
 351     if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
 352       size_t q = v / Encoder::skipQuantum;
 353       position_ = folly::loadUnaligned<SkipValueType>(
 354                       skipPointers_ + (q - 1) * sizeof(SkipValueType)) - 1;
 355
 356       reposition(q * Encoder::skipQuantum);
 357     }
 358
 359     // Find the value.
 360     size_t outer = v / 64 * 8;
 361
 362     while (outer_ < outer) {
 363       position_ += Instructions::popcount(block_);
 364       outer_ += sizeof(uint64_t);
 365       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 366     }
 367
 368     DCHECK_EQ(outer_, outer);
 369     uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
 370     position_ += Instructions::popcount(block_ & ~mask) + 1;
 371     block_ &= mask;
 372
 373     while (block_ == 0) {
 374       outer_ += sizeof(uint64_t);
 375       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 376     }
 377
 378     inner_ = Instructions::ctz(block_);
 379     block_ = Instructions::blsr(block_);
 380
 381     setValue();
 382     return true;
 383   }
 384
 385   size_t size() const { return size_; }
 386
 387   size_t position() const { return position_; }
 388   ValueType value() const { return value_; }
 389
 390   bool jump(size_t n) {
 391     reset();
 392     if (n > 0) {
 393       return skip(n);
 394     } else {
 395       return true;
 396     }
 397   }
 398
 399   bool jumpTo(ValueType v) {
 400     reset();
 401     return skipTo(v);
 402   }
 403
 404   bool setDone() {
 405     value_ = std::numeric_limits<ValueType>::max();
 406     position_ = size_;
 407     return false;
 408   }
 409
 410  private:
 411   bool setValue() {
 412     value_ = static_cast<ValueType>(8 * outer_ + inner_);
 413     return true;
 414   }
 415
 416   void reposition(size_t dest) {
 417     outer_ = dest / 64 * 8;
 418     // We maintain the invariant that outer_ is divisible by 8.
 419     block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
 420     block_ &= ~((uint64_t(1) << (dest % 64)) - 1);
 421   }
 422
 423   constexpr static size_t kLinearScanThreshold = 4;
 424
 425   size_t outer_;
 426   size_t inner_;
 427   size_t position_;
 428   uint64_t block_;
 429   ValueType value_ = 0;
 430
 431   size_t size_;
 432   ValueType upperBound_;
 433   const uint8_t* const bits_;
 434   const uint8_t* const skipPointers_;
 435   const uint8_t* const forwardPointers_;
 436 };
 437
 438 }}  // namespaces
 439
 440 #endif  // FOLLY_EXPERIMENTAL_BIT_VECTOR_CODING_H