2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <type_traits>
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>
33 #error BitVectorCoding.h requires GCC
37 #error BitVectorCoding.h requires x86_64
40 #if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
41 #error BitVectorCoding.h requires little endianness
44 namespace folly { namespace compression {
46 template <class Pointer>
47 struct BitVectorCompressedListBase {
48 BitVectorCompressedListBase() = default;
50 template <class OtherPointer>
51 BitVectorCompressedListBase(
52 const BitVectorCompressedListBase<OtherPointer>& other)
54 upperBound(other.upperBound),
56 bits(reinterpret_cast<Pointer>(other.bits)),
57 skipPointers(reinterpret_cast<Pointer>(other.skipPointers)),
58 forwardPointers(reinterpret_cast<Pointer>(other.forwardPointers)) {}
60 template <class T = Pointer>
61 auto free() -> decltype(::free(T(nullptr))) {
62 return ::free(data.data());
66 size_t upperBound = 0;
68 folly::Range<Pointer> data;
70 Pointer bits = nullptr;
71 Pointer skipPointers = nullptr;
72 Pointer forwardPointers = nullptr;
75 typedef BitVectorCompressedListBase<const uint8_t*> BitVectorCompressedList;
76 typedef BitVectorCompressedListBase<uint8_t*> MutableBitVectorCompressedList;
78 template <class Value,
80 size_t kSkipQuantum = 0,
81 size_t kForwardQuantum = 0>
82 struct BitVectorEncoder {
83 static_assert(std::is_integral<Value>::value &&
84 std::is_unsigned<Value>::value,
85 "Value should be unsigned integral");
87 typedef BitVectorCompressedList CompressedList;
88 typedef MutableBitVectorCompressedList MutableCompressedList;
90 typedef Value ValueType;
91 typedef SkipValue SkipValueType;
94 static constexpr size_t skipQuantum = kSkipQuantum;
95 static constexpr size_t forwardQuantum = kForwardQuantum;
97 template <class RandomAccessIterator>
98 static MutableCompressedList encode(RandomAccessIterator begin,
99 RandomAccessIterator end) {
101 return MutableCompressedList();
103 BitVectorEncoder encoder(end - begin, *(end - 1));
104 for (; begin != end; ++begin) {
107 return encoder.finish();
110 explicit BitVectorEncoder(const MutableCompressedList& result)
111 : bits_(result.bits),
112 skipPointers_(result.skipPointers),
113 forwardPointers_(result.forwardPointers),
115 memset(result.data.data(), 0, result.data.size());
118 BitVectorEncoder(size_t size, ValueType upperBound)
120 Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {}
122 void add(ValueType value) {
123 CHECK_LT(value, std::numeric_limits<ValueType>::max());
124 // Also works when lastValue_ == -1.
125 CHECK_GT(value + 1, lastValue_ + 1)
126 << "BitVectorCoding only supports stricly monotone lists";
128 auto block = bits_ + (value / 64) * sizeof(uint64_t);
129 size_t inner = value % 64;
130 folly::Bits<folly::Unaligned<uint64_t>>::set(
131 reinterpret_cast<folly::Unaligned<uint64_t>*>(block), inner);
133 if (skipQuantum != 0) {
134 size_t nextSkipPointerSize = value / (skipQuantum ?: 1);
135 while (skipPointersSize_ < nextSkipPointerSize) {
136 auto pos = skipPointersSize_++;
137 folly::storeUnaligned<SkipValueType>(
138 skipPointers_ + pos * sizeof(SkipValueType), size_);
142 if (forwardQuantum != 0) {
143 if (size_ != 0 && (size_ % (forwardQuantum ?: 1) == 0)) {
144 const auto pos = size_ / (forwardQuantum ?: 1) - 1;
145 folly::storeUnaligned<SkipValueType>(
146 forwardPointers_ + pos * sizeof(SkipValueType), value);
154 const MutableCompressedList& finish() const {
155 CHECK_EQ(size_, result_.size);
156 // TODO(ott): Relax this assumption.
157 CHECK_EQ(result_.upperBound, lastValue_);
162 uint8_t* const bits_ = nullptr;
163 uint8_t* const skipPointers_ = nullptr;
164 uint8_t* const forwardPointers_ = nullptr;
166 ValueType lastValue_ = -1;
168 size_t skipPointersSize_ = 0;
170 MutableCompressedList result_;
173 template <class Value,
176 size_t kForwardQuantum>
177 struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
179 static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
182 layout.upperBound = upperBound;
184 size_t bitVectorSizeInBytes = (upperBound / 8) + 1;
185 layout.bits = bitVectorSizeInBytes;
187 if (skipQuantum != 0) {
188 size_t numSkipPointers = upperBound / (skipQuantum ?: 1);
189 layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
191 if (forwardQuantum != 0) {
192 size_t numForwardPointers = size / (forwardQuantum ?: 1);
193 layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
196 CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
201 size_t bytes() const { return bits + skipPointers + forwardPointers; }
203 template <class Range>
204 BitVectorCompressedListBase<typename Range::iterator> openList(
206 BitVectorCompressedListBase<typename Range::iterator> result;
208 result.upperBound = upperBound;
209 result.data = buf.subpiece(0, bytes());
210 auto advance = [&](size_t n) {
211 auto begin = buf.data();
216 result.bits = advance(bits);
217 result.skipPointers = advance(skipPointers);
218 result.forwardPointers = advance(forwardPointers);
219 CHECK_EQ(buf.data() - result.data.data(), bytes());
224 MutableCompressedList allocList() const {
225 uint8_t* buf = nullptr;
227 buf = static_cast<uint8_t*>(malloc(bytes() + 7));
229 folly::MutableByteRange bufRange(buf, bytes());
230 return openList(bufRange);
234 size_t upperBound = 0;
238 size_t skipPointers = 0;
239 size_t forwardPointers = 0;
242 template <class Encoder,
243 class Instructions = instructions::Default,
244 bool kUnchecked = false>
245 class BitVectorReader {
247 typedef Encoder EncoderType;
248 typedef typename Encoder::ValueType ValueType;
249 typedef typename Encoder::SkipValueType SkipValueType;
251 explicit BitVectorReader(const typename Encoder::CompressedList& list)
254 skipPointers_(list.skipPointers),
255 forwardPointers_(list.forwardPointers) {
258 if (kUnchecked || UNLIKELY(list.size == 0)) {
263 upperBound_ = list.upperBound;
267 block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
271 value_ = kInvalidValue;
275 if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
279 while (block_ == 0) {
280 outer_ += sizeof(uint64_t);
281 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
285 inner_ = Instructions::ctz(block_);
286 block_ = Instructions::blsr(block_);
291 bool skip(size_t n) {
294 if (!kUnchecked && position() + n >= size_) {
297 // Small skip optimization.
298 if (LIKELY(n < kLinearScanThreshold)) {
299 for (size_t i = 0; i < n; ++i) {
307 // Use forward pointer.
308 if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
309 // Workaround to avoid 'division by zero' compile-time error.
310 constexpr size_t q = Encoder::forwardQuantum ?: 1;
312 const size_t steps = position_ / q;
313 const size_t dest = folly::loadUnaligned<SkipValueType>(
314 forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
317 n = position_ + 1 - steps * q;
318 // Correct inner_ will be set at the end.
322 // Find necessary block.
323 while ((cnt = Instructions::popcount(block_)) < n) {
325 outer_ += sizeof(uint64_t);
326 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
329 // Skip to the n-th one in the block.
331 inner_ = select64<Instructions>(block_, n - 1);
332 block_ &= (uint64_t(-1) << inner_) << 1;
337 bool skipTo(ValueType v) {
338 // Also works when value_ == kInvalidValue.
339 if (v != kInvalidValue) { DCHECK_GE(v + 1, value_ + 1); }
341 if (!kUnchecked && v > upperBound_) {
343 } else if (v == value_) {
347 // Small skip optimization.
348 if (v - value_ < kLinearScanThreshold) {
351 } while (value() < v);
356 if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
357 size_t q = v / Encoder::skipQuantum;
358 position_ = folly::loadUnaligned<SkipValueType>(
359 skipPointers_ + (q - 1) * sizeof(SkipValueType)) - 1;
361 reposition(q * Encoder::skipQuantum);
365 size_t outer = v / 64 * 8;
367 while (outer_ < outer) {
368 position_ += Instructions::popcount(block_);
369 outer_ += sizeof(uint64_t);
370 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
373 DCHECK_EQ(outer_, outer);
374 uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
375 position_ += Instructions::popcount(block_ & ~mask) + 1;
378 while (block_ == 0) {
379 outer_ += sizeof(uint64_t);
380 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
383 inner_ = Instructions::ctz(block_);
384 block_ = Instructions::blsr(block_);
390 size_t size() const { return size_; }
393 return position() < size(); // Also checks that position() != -1.
396 size_t position() const { return position_; }
397 ValueType value() const {
402 bool jump(size_t n) {
407 bool jumpTo(ValueType v) {
413 value_ = kInvalidValue;
419 constexpr static ValueType kInvalidValue =
420 std::numeric_limits<ValueType>::max(); // Must hold kInvalidValue + 1 == 0.
423 value_ = static_cast<ValueType>(8 * outer_ + inner_);
427 void reposition(size_t dest) {
428 outer_ = dest / 64 * 8;
429 // We maintain the invariant that outer_ is divisible by 8.
430 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
431 block_ &= ~((uint64_t(1) << (dest % 64)) - 1);
434 constexpr static size_t kLinearScanThreshold = 4;
443 ValueType upperBound_;
444 const uint8_t* const bits_;
445 const uint8_t* const skipPointers_;
446 const uint8_t* const forwardPointers_;