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 namespace folly { namespace compression {
42 static_assert(kIsLittleEndian, "BitVectorCoding.h requires little endianness");
44 template <class Pointer>
45 struct BitVectorCompressedListBase {
46 BitVectorCompressedListBase() = default;
48 template <class OtherPointer>
49 BitVectorCompressedListBase(
50 const BitVectorCompressedListBase<OtherPointer>& other)
52 upperBound(other.upperBound),
54 bits(reinterpret_cast<Pointer>(other.bits)),
55 skipPointers(reinterpret_cast<Pointer>(other.skipPointers)),
56 forwardPointers(reinterpret_cast<Pointer>(other.forwardPointers)) {}
58 template <class T = Pointer>
59 auto free() -> decltype(::free(T(nullptr))) {
60 return ::free(data.data());
64 size_t upperBound = 0;
66 folly::Range<Pointer> data;
68 Pointer bits = nullptr;
69 Pointer skipPointers = nullptr;
70 Pointer forwardPointers = nullptr;
73 typedef BitVectorCompressedListBase<const uint8_t*> BitVectorCompressedList;
74 typedef BitVectorCompressedListBase<uint8_t*> MutableBitVectorCompressedList;
76 template <class Value,
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");
85 typedef BitVectorCompressedList CompressedList;
86 typedef MutableBitVectorCompressedList MutableCompressedList;
88 typedef Value ValueType;
89 typedef SkipValue SkipValueType;
92 static constexpr size_t skipQuantum = kSkipQuantum;
93 static constexpr size_t forwardQuantum = kForwardQuantum;
95 template <class RandomAccessIterator>
96 static MutableCompressedList encode(RandomAccessIterator begin,
97 RandomAccessIterator end) {
99 return MutableCompressedList();
101 BitVectorEncoder encoder(end - begin, *(end - 1));
102 for (; begin != end; ++begin) {
105 return encoder.finish();
108 explicit BitVectorEncoder(const MutableCompressedList& result)
109 : bits_(result.bits),
110 skipPointers_(result.skipPointers),
111 forwardPointers_(result.forwardPointers),
113 memset(result.data.data(), 0, result.data.size());
116 BitVectorEncoder(size_t size, ValueType upperBound)
118 Layout::fromUpperBoundAndSize(upperBound, size).allocList()) {}
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";
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);
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_);
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);
152 const MutableCompressedList& finish() const {
153 CHECK_EQ(size_, result_.size);
154 // TODO(ott): Relax this assumption.
155 CHECK_EQ(result_.upperBound, lastValue_);
160 uint8_t* const bits_ = nullptr;
161 uint8_t* const skipPointers_ = nullptr;
162 uint8_t* const forwardPointers_ = nullptr;
164 ValueType lastValue_ = -1;
166 size_t skipPointersSize_ = 0;
168 MutableCompressedList result_;
171 template <class Value,
174 size_t kForwardQuantum>
175 struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
177 static Layout fromUpperBoundAndSize(size_t upperBound, size_t size) {
180 layout.upperBound = upperBound;
182 size_t bitVectorSizeInBytes = (upperBound / 8) + 1;
183 layout.bits = bitVectorSizeInBytes;
185 if (skipQuantum != 0) {
186 size_t numSkipPointers = upperBound / (skipQuantum ?: 1);
187 layout.skipPointers = numSkipPointers * sizeof(SkipValueType);
189 if (forwardQuantum != 0) {
190 size_t numForwardPointers = size / (forwardQuantum ?: 1);
191 layout.forwardPointers = numForwardPointers * sizeof(SkipValueType);
194 CHECK_LT(size, std::numeric_limits<SkipValueType>::max());
199 size_t bytes() const { return bits + skipPointers + forwardPointers; }
201 template <class Range>
202 BitVectorCompressedListBase<typename Range::iterator> openList(
204 BitVectorCompressedListBase<typename Range::iterator> result;
206 result.upperBound = upperBound;
207 result.data = buf.subpiece(0, bytes());
208 auto advance = [&](size_t n) {
209 auto begin = buf.data();
214 result.bits = advance(bits);
215 result.skipPointers = advance(skipPointers);
216 result.forwardPointers = advance(forwardPointers);
217 CHECK_EQ(buf.data() - result.data.data(), bytes());
222 MutableCompressedList allocList() const {
223 uint8_t* buf = nullptr;
225 buf = static_cast<uint8_t*>(malloc(bytes() + 7));
227 folly::MutableByteRange bufRange(buf, bytes());
228 return openList(bufRange);
232 size_t upperBound = 0;
236 size_t skipPointers = 0;
237 size_t forwardPointers = 0;
240 template <class Encoder,
241 class Instructions = instructions::Default,
242 bool kUnchecked = false>
243 class BitVectorReader {
245 typedef Encoder EncoderType;
246 typedef typename Encoder::ValueType ValueType;
247 typedef typename Encoder::SkipValueType SkipValueType;
249 explicit BitVectorReader(const typename Encoder::CompressedList& list)
252 skipPointers_(list.skipPointers),
253 forwardPointers_(list.forwardPointers) {
256 if (kUnchecked || UNLIKELY(list.size == 0)) {
261 upperBound_ = list.upperBound;
265 block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
269 value_ = kInvalidValue;
273 if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
277 while (block_ == 0) {
278 outer_ += sizeof(uint64_t);
279 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
283 inner_ = Instructions::ctz(block_);
284 block_ = Instructions::blsr(block_);
289 bool skip(size_t n) {
292 if (!kUnchecked && position() + n >= size_) {
295 // Small skip optimization.
296 if (LIKELY(n < kLinearScanThreshold)) {
297 for (size_t i = 0; i < n; ++i) {
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;
310 const size_t steps = position_ / q;
311 const size_t dest = folly::loadUnaligned<SkipValueType>(
312 forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
315 n = position_ + 1 - steps * q;
316 // Correct inner_ will be set at the end.
320 // Find necessary block.
321 while ((cnt = Instructions::popcount(block_)) < n) {
323 outer_ += sizeof(uint64_t);
324 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
327 // Skip to the n-th one in the block.
329 inner_ = select64<Instructions>(block_, n - 1);
330 block_ &= (uint64_t(-1) << inner_) << 1;
335 bool skipTo(ValueType v) {
336 // Also works when value_ == kInvalidValue.
337 if (v != kInvalidValue) { DCHECK_GE(v + 1, value_ + 1); }
339 if (!kUnchecked && v > upperBound_) {
341 } else if (v == value_) {
345 // Small skip optimization.
346 if (v - value_ < kLinearScanThreshold) {
349 } while (value() < v);
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;
359 reposition(q * Encoder::skipQuantum);
363 size_t outer = v / 64 * 8;
365 while (outer_ < outer) {
366 position_ += Instructions::popcount(block_);
367 outer_ += sizeof(uint64_t);
368 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
371 DCHECK_EQ(outer_, outer);
372 uint64_t mask = ~((uint64_t(1) << (v % 64)) - 1);
373 position_ += Instructions::popcount(block_ & ~mask) + 1;
376 while (block_ == 0) {
377 outer_ += sizeof(uint64_t);
378 block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
381 inner_ = Instructions::ctz(block_);
382 block_ = Instructions::blsr(block_);
388 size_t size() const { return size_; }
391 return position() < size(); // Also checks that position() != -1.
394 size_t position() const { return position_; }
395 ValueType value() const {
400 bool jump(size_t n) {
405 bool jumpTo(ValueType v) {
411 value_ = kInvalidValue;
417 constexpr static ValueType kInvalidValue =
418 std::numeric_limits<ValueType>::max(); // Must hold kInvalidValue + 1 == 0.
421 value_ = static_cast<ValueType>(8 * outer_ + inner_);
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);
432 constexpr static size_t kLinearScanThreshold = 4;
441 ValueType upperBound_;
442 const uint8_t* const bits_;
443 const uint8_t* const skipPointers_;
444 const uint8_t* const forwardPointers_;