1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
9 // http://www.apache.org/licenses/LICENSE-2.0
11 // Unless required by applicable law or agreed to in writing,
12 // software distributed under the License is distributed on an
13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, either express or implied. See the License for the
15 // specific language governing permissions and limitations
25 #include "arrow/util/bit_util.h"
26 #include "arrow/util/bitmap_reader.h"
27 #include "arrow/util/endian.h"
28 #include "arrow/util/macros.h"
29 #include "arrow/util/visibility.h"
36 // Whether bits are set at this point.
39 std::string
ToString() const {
40 return std::string("{Length: ") + std::to_string(length
) +
41 ", set=" + std::to_string(set
) + "}";
45 inline bool operator==(const BitRun
& lhs
, const BitRun
& rhs
) {
46 return lhs
.length
== rhs
.length
&& lhs
.set
== rhs
.set
;
49 inline bool operator!=(const BitRun
& lhs
, const BitRun
& rhs
) {
50 return lhs
.length
!= rhs
.length
|| lhs
.set
!= rhs
.set
;
53 class BitRunReaderLinear
{
55 BitRunReaderLinear(const uint8_t* bitmap
, int64_t start_offset
, int64_t length
)
56 : reader_(bitmap
, start_offset
, length
) {}
59 BitRun rl
= {/*length=*/0, reader_
.IsSet()};
60 // Advance while the values are equal and not at the end of list.
61 while (reader_
.position() < reader_
.length() && reader_
.IsSet() == rl
.set
) {
72 #if ARROW_LITTLE_ENDIAN
73 /// A convenience class for counting the number of contiguous set/unset bits
75 class ARROW_EXPORT BitRunReader
{
77 /// \brief Constructs new BitRunReader.
79 /// \param[in] bitmap source data
80 /// \param[in] start_offset bit offset into the source data
81 /// \param[in] length number of bits to copy
82 BitRunReader(const uint8_t* bitmap
, int64_t start_offset
, int64_t length
);
84 /// Returns a new BitRun containing the number of contiguous
85 /// bits with the same value. length == 0 indicates the
86 /// end of the bitmap.
88 if (ARROW_PREDICT_FALSE(position_
>= length_
)) {
89 return {/*length=*/0, false};
91 // This implementation relies on a efficient implementations of
92 // CountTrailingZeros and assumes that runs are more often then
93 // not. The logic is to incrementally find the next bit change
94 // from the current position. This is done by zeroing all
95 // bits in word_ up to position_ and using the TrailingZeroCount
96 // to find the index of the next set bit.
98 // The runs alternate on each call, so flip the bit.
99 current_run_bit_set_
= !current_run_bit_set_
;
101 int64_t start_position
= position_
;
102 int64_t start_bit_offset
= start_position
& 63;
103 // Invert the word for proper use of CountTrailingZeros and
104 // clear bits so CountTrailingZeros can do it magic.
105 word_
= ~word_
& ~BitUtil::LeastSignificantBitMask(start_bit_offset
);
107 // Go forward until the next change from unset to set.
108 int64_t new_bits
= BitUtil::CountTrailingZeros(word_
) - start_bit_offset
;
109 position_
+= new_bits
;
111 if (ARROW_PREDICT_FALSE(BitUtil::IsMultipleOf64(position_
)) &&
112 ARROW_PREDICT_TRUE(position_
< length_
)) {
113 // Continue extending position while we can advance an entire word.
114 // (updates position_ accordingly).
115 AdvanceUntilChange();
118 return {/*length=*/position_
- start_position
, current_run_bit_set_
};
122 void AdvanceUntilChange() {
123 int64_t new_bits
= 0;
125 // Advance the position of the bitmap for loading.
126 bitmap_
+= sizeof(uint64_t);
128 new_bits
= BitUtil::CountTrailingZeros(word_
);
129 // Continue calculating run length.
130 position_
+= new_bits
;
131 } while (ARROW_PREDICT_FALSE(BitUtil::IsMultipleOf64(position_
)) &&
132 ARROW_PREDICT_TRUE(position_
< length_
) && new_bits
> 0);
135 void LoadNextWord() { return LoadWord(length_
- position_
); }
137 // Helper method for Loading the next word.
138 void LoadWord(int64_t bits_remaining
) {
140 // we need at least an extra byte in this case.
141 if (ARROW_PREDICT_TRUE(bits_remaining
>= 64)) {
142 std::memcpy(&word_
, bitmap_
, 8);
144 int64_t bytes_to_load
= BitUtil::BytesForBits(bits_remaining
);
145 auto word_ptr
= reinterpret_cast<uint8_t*>(&word_
);
146 std::memcpy(word_ptr
, bitmap_
, bytes_to_load
);
147 // Ensure stoppage at last bit in bitmap by reversing the next higher
149 BitUtil::SetBitTo(word_ptr
, bits_remaining
,
150 !BitUtil::GetBit(word_ptr
, bits_remaining
- 1));
154 // 1. For unset, CountTrailingZeros works naturally so we don't
156 // 2. Otherwise invert so we can use CountTrailingZeros.
157 if (current_run_bit_set_
) {
161 const uint8_t* bitmap_
;
165 bool current_run_bit_set_
;
168 using BitRunReader
= BitRunReaderLinear
;
175 bool AtEnd() const { return length
== 0; }
177 std::string
ToString() const {
178 return std::string("{pos=") + std::to_string(position
) +
179 ", len=" + std::to_string(length
) + "}";
182 bool operator==(const SetBitRun
& other
) const {
183 return position
== other
.position
&& length
== other
.length
;
185 bool operator!=(const SetBitRun
& other
) const {
186 return position
!= other
.position
|| length
!= other
.length
;
190 template <bool Reverse
>
191 class BaseSetBitRunReader
{
193 /// \brief Constructs new SetBitRunReader.
195 /// \param[in] bitmap source data
196 /// \param[in] start_offset bit offset into the source data
197 /// \param[in] length number of bits to copy
199 BaseSetBitRunReader(const uint8_t* bitmap
, int64_t start_offset
, int64_t length
)
200 : bitmap_(util::MakeNonNull(bitmap
)),
204 current_num_bits_(0) {
206 bitmap_
+= (start_offset
+ length
) / 8;
207 const int8_t end_bit_offset
= static_cast<int8_t>((start_offset
+ length
) % 8);
208 if (length
> 0 && end_bit_offset
) {
209 // Get LSBs from last byte
212 std::min(static_cast<int32_t>(length
), static_cast<int32_t>(end_bit_offset
));
213 current_word_
= LoadPartialWord(8 - end_bit_offset
, current_num_bits_
);
216 bitmap_
+= start_offset
/ 8;
217 const int8_t bit_offset
= static_cast<int8_t>(start_offset
% 8);
218 if (length
> 0 && bit_offset
) {
219 // Get MSBs from first byte
221 std::min(static_cast<int32_t>(length
), static_cast<int32_t>(8 - bit_offset
));
222 current_word_
= LoadPartialWord(bit_offset
, current_num_bits_
);
228 SetBitRun
NextRun() {
231 if (current_num_bits_
) {
232 const auto run
= FindCurrentRun();
233 assert(remaining_
>= 0);
234 if (run
.length
&& current_num_bits_
) {
235 // The run ends in current_word_
236 return AdjustRun(run
);
242 // We didn't get any ones in current_word_, so we can skip any zeros
243 // in the following words
245 if (remaining_
== 0) {
248 assert(current_num_bits_
);
250 } else if (!current_num_bits_
) {
251 if (ARROW_PREDICT_TRUE(remaining_
>= 64)) {
252 current_word_
= LoadFullWord();
253 current_num_bits_
= 64;
254 } else if (remaining_
> 0) {
255 current_word_
= LoadPartialWord(/*bit_offset=*/0, remaining_
);
256 current_num_bits_
= static_cast<int32_t>(remaining_
);
258 // No bits remaining, perhaps we found a run?
259 return AdjustRun({pos
, len
});
261 // If current word starts with a zero, we got a full run
262 if (!(current_word_
& kFirstBit
)) {
263 return AdjustRun({pos
, len
});
266 // Current word should now start with a set bit
267 len
+= CountNextOnes();
268 return AdjustRun({pos
, len
});
272 int64_t position() const {
276 return length_
- remaining_
;
280 SetBitRun
AdjustRun(SetBitRun run
) {
282 assert(run
.position
>= run
.length
);
283 run
.position
-= run
.length
;
288 uint64_t LoadFullWord() {
293 memcpy(&word
, bitmap_
, 8);
297 return BitUtil::ToLittleEndian(word
);
300 uint64_t LoadPartialWord(int8_t bit_offset
, int64_t num_bits
) {
301 assert(num_bits
> 0);
303 const int64_t num_bytes
= BitUtil::BytesForBits(num_bits
);
305 // Read in the most significant bytes of the word
306 bitmap_
-= num_bytes
;
307 memcpy(reinterpret_cast<char*>(&word
) + 8 - num_bytes
, bitmap_
, num_bytes
);
308 // XXX MostSignificantBitmask
309 return (BitUtil::ToLittleEndian(word
) << bit_offset
) &
310 ~BitUtil::LeastSignificantBitMask(64 - num_bits
);
312 memcpy(&word
, bitmap_
, num_bytes
);
313 bitmap_
+= num_bytes
;
314 return (BitUtil::ToLittleEndian(word
) >> bit_offset
) &
315 BitUtil::LeastSignificantBitMask(num_bits
);
319 void SkipNextZeros() {
320 assert(current_num_bits_
== 0);
321 while (ARROW_PREDICT_TRUE(remaining_
>= 64)) {
322 current_word_
= LoadFullWord();
323 const auto num_zeros
= CountFirstZeros(current_word_
);
324 if (num_zeros
< 64) {
325 // Run of zeros ends here
326 current_word_
= ConsumeBits(current_word_
, num_zeros
);
327 current_num_bits_
= 64 - num_zeros
;
328 remaining_
-= num_zeros
;
329 assert(remaining_
>= 0);
330 assert(current_num_bits_
>= 0);
335 // Run of zeros continues in last bitmap word
336 if (remaining_
> 0) {
337 current_word_
= LoadPartialWord(/*bit_offset=*/0, remaining_
);
338 current_num_bits_
= static_cast<int32_t>(remaining_
);
339 const auto num_zeros
=
340 std::min
<int32_t>(current_num_bits_
, CountFirstZeros(current_word_
));
341 current_word_
= ConsumeBits(current_word_
, num_zeros
);
342 current_num_bits_
-= num_zeros
;
343 remaining_
-= num_zeros
;
344 assert(remaining_
>= 0);
345 assert(current_num_bits_
>= 0);
349 int64_t CountNextOnes() {
350 assert(current_word_
& kFirstBit
);
353 if (~current_word_
) {
354 const auto num_ones
= CountFirstZeros(~current_word_
);
355 assert(num_ones
<= current_num_bits_
);
356 assert(num_ones
<= remaining_
);
357 remaining_
-= num_ones
;
358 current_word_
= ConsumeBits(current_word_
, num_ones
);
359 current_num_bits_
-= num_ones
;
360 if (current_num_bits_
) {
361 // Run of ones ends here
366 // current_word_ is all ones
368 current_num_bits_
= 0;
372 while (ARROW_PREDICT_TRUE(remaining_
>= 64)) {
373 current_word_
= LoadFullWord();
374 const auto num_ones
= CountFirstZeros(~current_word_
);
376 remaining_
-= num_ones
;
378 // Run of ones ends here
379 current_word_
= ConsumeBits(current_word_
, num_ones
);
380 current_num_bits_
= 64 - num_ones
;
384 // Run of ones continues in last bitmap word
385 if (remaining_
> 0) {
386 current_word_
= LoadPartialWord(/*bit_offset=*/0, remaining_
);
387 current_num_bits_
= static_cast<int32_t>(remaining_
);
388 const auto num_ones
= CountFirstZeros(~current_word_
);
389 assert(num_ones
<= current_num_bits_
);
390 assert(num_ones
<= remaining_
);
391 current_word_
= ConsumeBits(current_word_
, num_ones
);
392 current_num_bits_
-= num_ones
;
393 remaining_
-= num_ones
;
399 SetBitRun
FindCurrentRun() {
400 // Skip any pending zeros
401 const auto num_zeros
= CountFirstZeros(current_word_
);
402 if (num_zeros
>= current_num_bits_
) {
403 remaining_
-= current_num_bits_
;
405 current_num_bits_
= 0;
408 assert(num_zeros
<= remaining_
);
409 current_word_
= ConsumeBits(current_word_
, num_zeros
);
410 current_num_bits_
-= num_zeros
;
411 remaining_
-= num_zeros
;
412 const int64_t pos
= position();
414 const auto num_ones
= CountFirstZeros(~current_word_
);
415 assert(num_ones
<= current_num_bits_
);
416 assert(num_ones
<= remaining_
);
417 current_word_
= ConsumeBits(current_word_
, num_ones
);
418 current_num_bits_
-= num_ones
;
419 remaining_
-= num_ones
;
420 return {pos
, num_ones
};
423 inline int CountFirstZeros(uint64_t word
);
424 inline uint64_t ConsumeBits(uint64_t word
, int32_t num_bits
);
426 const uint8_t* bitmap_
;
427 const int64_t length_
;
429 uint64_t current_word_
;
430 int32_t current_num_bits_
;
432 static constexpr uint64_t kFirstBit
= Reverse
? 0x8000000000000000ULL
: 1;
436 inline int BaseSetBitRunReader
<false>::CountFirstZeros(uint64_t word
) {
437 return BitUtil::CountTrailingZeros(word
);
441 inline int BaseSetBitRunReader
<true>::CountFirstZeros(uint64_t word
) {
442 return BitUtil::CountLeadingZeros(word
);
446 inline uint64_t BaseSetBitRunReader
<false>::ConsumeBits(uint64_t word
, int32_t num_bits
) {
447 return word
>> num_bits
;
451 inline uint64_t BaseSetBitRunReader
<true>::ConsumeBits(uint64_t word
, int32_t num_bits
) {
452 return word
<< num_bits
;
455 using SetBitRunReader
= BaseSetBitRunReader
</*Reverse=*/false>;
456 using ReverseSetBitRunReader
= BaseSetBitRunReader
</*Reverse=*/true>;
458 // Functional-style bit run visitors.
460 // XXX: Try to make this function small so the compiler can inline and optimize
461 // the `visit` function, which is normally a hot loop with vectorizable code.
462 // - don't inline SetBitRunReader constructor, it doesn't hurt performance
463 // - un-inline NextRun hurts 'many null' cases a bit, but improves normal cases
464 template <typename Visit
>
465 inline Status
VisitSetBitRuns(const uint8_t* bitmap
, int64_t offset
, int64_t length
,
467 if (bitmap
== NULLPTR
) {
468 // Assuming all set (as in a null bitmap)
469 return visit(static_cast<int64_t>(0), static_cast<int64_t>(length
));
471 SetBitRunReader
reader(bitmap
, offset
, length
);
473 const auto run
= reader
.NextRun();
474 if (run
.length
== 0) {
477 ARROW_RETURN_NOT_OK(visit(run
.position
, run
.length
));
482 template <typename Visit
>
483 inline void VisitSetBitRunsVoid(const uint8_t* bitmap
, int64_t offset
, int64_t length
,
485 if (bitmap
== NULLPTR
) {
486 // Assuming all set (as in a null bitmap)
487 visit(static_cast<int64_t>(0), static_cast<int64_t>(length
));
490 SetBitRunReader
reader(bitmap
, offset
, length
);
492 const auto run
= reader
.NextRun();
493 if (run
.length
== 0) {
496 visit(run
.position
, run
.length
);
500 template <typename Visit
>
501 inline Status
VisitSetBitRuns(const std::shared_ptr
<Buffer
>& bitmap
, int64_t offset
,
502 int64_t length
, Visit
&& visit
) {
503 return VisitSetBitRuns(bitmap
? bitmap
->data() : NULLPTR
, offset
, length
,
504 std::forward
<Visit
>(visit
));
507 template <typename Visit
>
508 inline void VisitSetBitRunsVoid(const std::shared_ptr
<Buffer
>& bitmap
, int64_t offset
,
509 int64_t length
, Visit
&& visit
) {
510 VisitSetBitRunsVoid(bitmap
? bitmap
->data() : NULLPTR
, offset
, length
,
511 std::forward
<Visit
>(visit
));
514 } // namespace internal