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
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
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
16// under the License.
17
18#ifndef ARROW_UTIL_BIT_UTIL_H
19#define ARROW_UTIL_BIT_UTIL_H
20
21#ifdef _WIN32
22#define ARROW_LITTLE_ENDIAN 1
23#else
24#ifdef __APPLE__
25#include <machine/endian.h>
26#else
27#include <endian.h>
28#endif
29#
30#ifndef __BYTE_ORDER__
31#error "__BYTE_ORDER__ not defined"
32#endif
33#
34#ifndef __ORDER_LITTLE_ENDIAN__
35#error "__ORDER_LITTLE_ENDIAN__ not defined"
36#endif
37#
38#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
39#define ARROW_LITTLE_ENDIAN 1
40#else
41#define ARROW_LITTLE_ENDIAN 0
42#endif
43#endif
44
45#if defined(_MSC_VER)
46#include <intrin.h>
47#pragma intrinsic(_BitScanReverse)
48#define ARROW_BYTE_SWAP64 _byteswap_uint64
49#define ARROW_BYTE_SWAP32 _byteswap_ulong
50#else
51#define ARROW_BYTE_SWAP64 __builtin_bswap64
52#define ARROW_BYTE_SWAP32 __builtin_bswap32
53#endif
54
55#include <cstdint>
56#include <cstring>
57#include <limits>
58#include <memory>
59#include <type_traits>
60#include <vector>
61
62#include "arrow/util/macros.h"
63#include "arrow/util/type_traits.h"
64#include "arrow/util/visibility.h"
65
66namespace arrow {
67
68class Buffer;
69class MemoryPool;
70class Status;
71
72namespace detail {
73
74template <typename Integer>
75typename std::make_unsigned<Integer>::type as_unsigned(Integer x) {
76 return static_cast<typename std::make_unsigned<Integer>::type>(x);
77}
78
79} // namespace detail
80
81namespace BitUtil {
82
83//
84// Bit-related computations on integer values
85//
86
87// Returns the ceil of value/divisor
88constexpr int64_t CeilDiv(int64_t value, int64_t divisor) {
89 return value / divisor + (value % divisor != 0);
90}
91
92constexpr int64_t BytesForBits(int64_t bits) { return (bits + 7) >> 3; }
93
94// Returns the smallest power of two that contains v. If v is already a
95// power of two, it is returned as is.
96static inline int64_t NextPower2(int64_t n) {
97 // Taken from
98 // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
99 n--;
100 n |= n >> 1;
101 n |= n >> 2;
102 n |= n >> 4;
103 n |= n >> 8;
104 n |= n >> 16;
105 n |= n >> 32;
106 n++;
107 return n;
108}
109
110constexpr bool IsMultipleOf64(int64_t n) { return (n & 63) == 0; }
111
112constexpr bool IsMultipleOf8(int64_t n) { return (n & 7) == 0; }
113
114// Returns 'value' rounded up to the nearest multiple of 'factor'
115constexpr int64_t RoundUp(int64_t value, int64_t factor) {
116 return (value + (factor - 1)) / factor * factor;
117}
118
119// Returns 'value' rounded up to the nearest multiple of 'factor' when factor
120// is a power of two.
121// The result is undefined on overflow, i.e. if `value > 2**64 - factor`,
122// since we cannot return the correct result which would be 2**64.
123constexpr int64_t RoundUpToPowerOf2(int64_t value, int64_t factor) {
124 // DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
125 return (value + (factor - 1)) & ~(factor - 1);
126}
127
128constexpr int64_t RoundUpToMultipleOf8(int64_t num) { return RoundUpToPowerOf2(num, 8); }
129
130constexpr int64_t RoundUpToMultipleOf64(int64_t num) {
131 return RoundUpToPowerOf2(num, 64);
132}
133
134// Returns the 'num_bits' least-significant bits of 'v'.
135static inline uint64_t TrailingBits(uint64_t v, int num_bits) {
136 if (ARROW_PREDICT_FALSE(num_bits == 0)) return 0;
137 if (ARROW_PREDICT_FALSE(num_bits >= 64)) return v;
138 int n = 64 - num_bits;
139 return (v << n) >> n;
140}
141
142/// \brief Count the number of leading zeros in an unsigned integer.
143static inline int CountLeadingZeros(uint32_t value) {
144#if defined(__clang__) || defined(__GNUC__)
145 if (value == 0) return 32;
146 return static_cast<int>(__builtin_clz(value));
147#elif defined(_MSC_VER)
148 unsigned long index; // NOLINT
149 if (_BitScanReverse(&index, static_cast<unsigned long>(value))) { // NOLINT
150 return 31 - static_cast<int>(index);
151 } else {
152 return 32;
153 }
154#else
155 int bitpos = 0;
156 while (value != 0) {
157 value >>= 1;
158 ++bitpos;
159 }
160 return 32 - bitpos;
161#endif
162}
163
164static inline int CountLeadingZeros(uint64_t value) {
165#if defined(__clang__) || defined(__GNUC__)
166 if (value == 0) return 64;
167 return static_cast<int>(__builtin_clzll(value));
168#elif defined(_MSC_VER)
169 unsigned long index; // NOLINT
170 if (_BitScanReverse64(&index, value)) { // NOLINT
171 return 63 - static_cast<int>(index);
172 } else {
173 return 64;
174 }
175#else
176 int bitpos = 0;
177 while (value != 0) {
178 value >>= 1;
179 ++bitpos;
180 }
181 return 64 - bitpos;
182#endif
183}
184
185// Returns the minimum number of bits needed to represent an unsigned value
186static inline int NumRequiredBits(uint64_t x) { return 64 - CountLeadingZeros(x); }
187
188// Returns ceil(log2(x)).
189static inline int Log2(uint64_t x) {
190 // DCHECK_GT(x, 0);
191 return NumRequiredBits(x - 1);
192}
193
194//
195// Byte-swap 16-bit, 32-bit and 64-bit values
196//
197
198// Swap the byte order (i.e. endianess)
199static inline int64_t ByteSwap(int64_t value) { return ARROW_BYTE_SWAP64(value); }
200static inline uint64_t ByteSwap(uint64_t value) {
201 return static_cast<uint64_t>(ARROW_BYTE_SWAP64(value));
202}
203static inline int32_t ByteSwap(int32_t value) { return ARROW_BYTE_SWAP32(value); }
204static inline uint32_t ByteSwap(uint32_t value) {
205 return static_cast<uint32_t>(ARROW_BYTE_SWAP32(value));
206}
207static inline int16_t ByteSwap(int16_t value) {
208 constexpr auto m = static_cast<int16_t>(0xff);
209 return static_cast<int16_t>(((value >> 8) & m) | ((value & m) << 8));
210}
211static inline uint16_t ByteSwap(uint16_t value) {
212 return static_cast<uint16_t>(ByteSwap(static_cast<int16_t>(value)));
213}
214
215// Write the swapped bytes into dst. Src and dst cannot overlap.
216static inline void ByteSwap(void* dst, const void* src, int len) {
217 switch (len) {
218 case 1:
219 *reinterpret_cast<int8_t*>(dst) = *reinterpret_cast<const int8_t*>(src);
220 return;
221 case 2:
222 *reinterpret_cast<int16_t*>(dst) = ByteSwap(*reinterpret_cast<const int16_t*>(src));
223 return;
224 case 4:
225 *reinterpret_cast<int32_t*>(dst) = ByteSwap(*reinterpret_cast<const int32_t*>(src));
226 return;
227 case 8:
228 *reinterpret_cast<int64_t*>(dst) = ByteSwap(*reinterpret_cast<const int64_t*>(src));
229 return;
230 default:
231 break;
232 }
233
234 auto d = reinterpret_cast<uint8_t*>(dst);
235 auto s = reinterpret_cast<const uint8_t*>(src);
236 for (int i = 0; i < len; ++i) {
237 d[i] = s[len - i - 1];
238 }
239}
240
241// Convert to little/big endian format from the machine's native endian format.
242#if ARROW_LITTLE_ENDIAN
243template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
244 uint32_t, int16_t, uint16_t>>
245static inline T ToBigEndian(T value) {
246 return ByteSwap(value);
247}
248
249template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
250 uint32_t, int16_t, uint16_t>>
251static inline T ToLittleEndian(T value) {
252 return value;
253}
254#else
255template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
256 uint32_t, int16_t, uint16_t>>
257static inline T ToBigEndian(T value) {
258 return value;
259}
260
261template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
262 uint32_t, int16_t, uint16_t>>
263static inline T ToLittleEndian(T value) {
264 return ByteSwap(value);
265}
266#endif
267
268// Convert from big/little endian format to the machine's native endian format.
269#if ARROW_LITTLE_ENDIAN
270template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
271 uint32_t, int16_t, uint16_t>>
272static inline T FromBigEndian(T value) {
273 return ByteSwap(value);
274}
275
276template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
277 uint32_t, int16_t, uint16_t>>
278static inline T FromLittleEndian(T value) {
279 return value;
280}
281#else
282template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
283 uint32_t, int16_t, uint16_t>>
284static inline T FromBigEndian(T value) {
285 return value;
286}
287
288template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t,
289 uint32_t, int16_t, uint16_t>>
290static inline T FromLittleEndian(T value) {
291 return ByteSwap(value);
292}
293#endif
294
295//
296// Utilities for reading and writing individual bits by their index
297// in a memory area.
298//
299
300// Bitmask selecting the k-th bit in a byte
301static constexpr uint8_t kBitmask[] = {1, 2, 4, 8, 16, 32, 64, 128};
302
303// the bitwise complement version of kBitmask
304static constexpr uint8_t kFlippedBitmask[] = {254, 253, 251, 247, 239, 223, 191, 127};
305
306// Bitmask selecting the (k - 1) preceding bits in a byte
307static constexpr uint8_t kPrecedingBitmask[] = {0, 1, 3, 7, 15, 31, 63, 127};
308
309// the bitwise complement version of kPrecedingBitmask
310static constexpr uint8_t kTrailingBitmask[] = {255, 254, 252, 248, 240, 224, 192, 128};
311
312static inline bool GetBit(const uint8_t* bits, uint64_t i) {
313 return (bits[i >> 3] >> (i & 0x07)) & 1;
314}
315
316static inline void ClearBit(uint8_t* bits, int64_t i) {
317 bits[i / 8] &= kFlippedBitmask[i % 8];
318}
319
320static inline void SetBit(uint8_t* bits, int64_t i) { bits[i / 8] |= kBitmask[i % 8]; }
321
322static inline void SetBitTo(uint8_t* bits, int64_t i, bool bit_is_set) {
323 // https://graphics.stanford.edu/~seander/bithacks.html
324 // "Conditionally set or clear bits without branching"
325 // NOTE: this seems to confuse Valgrind as it reads from potentially
326 // uninitialized memory
327 bits[i / 8] ^= static_cast<uint8_t>(-static_cast<uint8_t>(bit_is_set) ^ bits[i / 8]) &
328 kBitmask[i % 8];
329}
330
331/// \brief set or clear a range of bits quickly
332static inline void SetBitsTo(uint8_t* bits, int64_t start_offset, int64_t length,
333 bool bits_are_set) {
334 if (length == 0) return;
335
336 const auto i_begin = start_offset;
337 const auto i_end = start_offset + length;
338 const uint8_t fill_byte = static_cast<uint8_t>(-static_cast<uint8_t>(bits_are_set));
339
340 const auto bytes_begin = i_begin / 8;
341 const auto bytes_end = i_end / 8 + 1;
342
343 const auto first_byte_mask = kPrecedingBitmask[i_begin % 8];
344 const auto last_byte_mask = kTrailingBitmask[i_end % 8];
345
346 if (bytes_end == bytes_begin + 1) {
347 // set bits within a single byte
348 const auto only_byte_mask =
349 i_end % 8 == 0 ? first_byte_mask
350 : static_cast<uint8_t>(first_byte_mask | last_byte_mask);
351 bits[bytes_begin] &= only_byte_mask;
352 bits[bytes_begin] |= static_cast<uint8_t>(fill_byte & ~only_byte_mask);
353 return;
354 }
355
356 // set/clear trailing bits of first byte
357 bits[bytes_begin] &= first_byte_mask;
358 bits[bytes_begin] |= static_cast<uint8_t>(fill_byte & ~first_byte_mask);
359
360 if (bytes_end - bytes_begin > 2) {
361 // set/clear whole bytes
362 std::memset(bits + bytes_begin + 1, fill_byte,
363 static_cast<size_t>(bytes_end - bytes_begin - 2));
364 }
365
366 if (i_end % 8 == 0) return;
367
368 // set/clear leading bits of last byte
369 bits[bytes_end - 1] &= last_byte_mask;
370 bits[bytes_end - 1] |= static_cast<uint8_t>(fill_byte & ~last_byte_mask);
371}
372
373/// \brief Convert vector of bytes to bitmap buffer
374ARROW_EXPORT
375Status BytesToBits(const std::vector<uint8_t>&, MemoryPool*, std::shared_ptr<Buffer>*);
376
377} // namespace BitUtil
378
379namespace internal {
380
381class BitmapReader {
382 public:
383 BitmapReader(const uint8_t* bitmap, int64_t start_offset, int64_t length)
384 : bitmap_(bitmap), position_(0), length_(length) {
385 current_byte_ = 0;
386 byte_offset_ = start_offset / 8;
387 bit_offset_ = start_offset % 8;
388 if (length > 0) {
389 current_byte_ = bitmap[byte_offset_];
390 }
391 }
392
393 bool IsSet() const { return (current_byte_ & (1 << bit_offset_)) != 0; }
394
395 bool IsNotSet() const { return (current_byte_ & (1 << bit_offset_)) == 0; }
396
397 void Next() {
398 ++bit_offset_;
399 ++position_;
400 if (ARROW_PREDICT_FALSE(bit_offset_ == 8)) {
401 bit_offset_ = 0;
402 ++byte_offset_;
403 if (ARROW_PREDICT_TRUE(position_ < length_)) {
404 current_byte_ = bitmap_[byte_offset_];
405 }
406 }
407 }
408
409 private:
410 const uint8_t* bitmap_;
411 int64_t position_;
412 int64_t length_;
413
414 uint8_t current_byte_;
415 int64_t byte_offset_;
416 int64_t bit_offset_;
417};
418
419class BitmapWriter {
420 // A sequential bitwise writer that preserves surrounding bit values.
421
422 public:
423 BitmapWriter(uint8_t* bitmap, int64_t start_offset, int64_t length)
424 : bitmap_(bitmap), position_(0), length_(length) {
425 byte_offset_ = start_offset / 8;
426 bit_mask_ = BitUtil::kBitmask[start_offset % 8];
427 if (length > 0) {
428 current_byte_ = bitmap[byte_offset_];
429 } else {
430 current_byte_ = 0;
431 }
432 }
433
434 void Set() { current_byte_ |= bit_mask_; }
435
436 void Clear() { current_byte_ &= bit_mask_ ^ 0xFF; }
437
438 void Next() {
439 bit_mask_ = static_cast<uint8_t>(bit_mask_ << 1);
440 ++position_;
441 if (bit_mask_ == 0) {
442 // Finished this byte, need advancing
443 bit_mask_ = 0x01;
444 bitmap_[byte_offset_++] = current_byte_;
445 if (ARROW_PREDICT_TRUE(position_ < length_)) {
446 current_byte_ = bitmap_[byte_offset_];
447 }
448 }
449 }
450
451 void Finish() {
452 // Store current byte if we didn't went past bitmap storage
453 if (length_ > 0 && (bit_mask_ != 0x01 || position_ < length_)) {
454 bitmap_[byte_offset_] = current_byte_;
455 }
456 }
457
458 int64_t position() const { return position_; }
459
460 private:
461 uint8_t* bitmap_;
462 int64_t position_;
463 int64_t length_;
464
465 uint8_t current_byte_;
466 uint8_t bit_mask_;
467 int64_t byte_offset_;
468};
469
470class FirstTimeBitmapWriter {
471 // Like BitmapWriter, but any bit values *following* the bits written
472 // might be clobbered. It is hence faster than BitmapWriter, and can
473 // also avoid false positives with Valgrind.
474
475 public:
476 FirstTimeBitmapWriter(uint8_t* bitmap, int64_t start_offset, int64_t length)
477 : bitmap_(bitmap), position_(0), length_(length) {
478 current_byte_ = 0;
479 byte_offset_ = start_offset / 8;
480 bit_mask_ = BitUtil::kBitmask[start_offset % 8];
481 if (length > 0) {
482 current_byte_ = bitmap[byte_offset_] & BitUtil::kPrecedingBitmask[start_offset % 8];
483 } else {
484 current_byte_ = 0;
485 }
486 }
487
488 void Set() { current_byte_ |= bit_mask_; }
489
490 void Clear() {}
491
492 void Next() {
493 bit_mask_ = static_cast<uint8_t>(bit_mask_ << 1);
494 ++position_;
495 if (bit_mask_ == 0) {
496 // Finished this byte, need advancing
497 bit_mask_ = 0x01;
498 bitmap_[byte_offset_++] = current_byte_;
499 current_byte_ = 0;
500 }
501 }
502
503 void Finish() {
504 // Store current byte if we didn't went past bitmap storage
505 if (length_ > 0 && (bit_mask_ != 0x01 || position_ < length_)) {
506 bitmap_[byte_offset_] = current_byte_;
507 }
508 }
509
510 int64_t position() const { return position_; }
511
512 private:
513 uint8_t* bitmap_;
514 int64_t position_;
515 int64_t length_;
516
517 uint8_t current_byte_;
518 uint8_t bit_mask_;
519 int64_t byte_offset_;
520};
521
522// A std::generate() like function to write sequential bits into a bitmap area.
523// Bits preceding the bitmap area are preserved, bits following the bitmap
524// area may be clobbered.
525
526template <class Generator>
527void GenerateBits(uint8_t* bitmap, int64_t start_offset, int64_t length, Generator&& g) {
528 if (length == 0) {
529 return;
530 }
531 uint8_t* cur = bitmap + start_offset / 8;
532 uint8_t bit_mask = BitUtil::kBitmask[start_offset % 8];
533 uint8_t current_byte = *cur & BitUtil::kPrecedingBitmask[start_offset % 8];
534
535 for (int64_t index = 0; index < length; ++index) {
536 const bool bit = g();
537 current_byte = bit ? (current_byte | bit_mask) : current_byte;
538 bit_mask = static_cast<uint8_t>(bit_mask << 1);
539 if (bit_mask == 0) {
540 bit_mask = 1;
541 *cur++ = current_byte;
542 current_byte = 0;
543 }
544 }
545 if (bit_mask != 1) {
546 *cur++ = current_byte;
547 }
548}
549
550// Like GenerateBits(), but unrolls its main loop for higher performance.
551
552template <class Generator>
553void GenerateBitsUnrolled(uint8_t* bitmap, int64_t start_offset, int64_t length,
554 Generator&& g) {
555 if (length == 0) {
556 return;
557 }
558 uint8_t current_byte;
559 uint8_t* cur = bitmap + start_offset / 8;
560 const uint64_t start_bit_offset = start_offset % 8;
561 uint8_t bit_mask = BitUtil::kBitmask[start_bit_offset];
562 int64_t remaining = length;
563
564 if (bit_mask != 0x01) {
565 current_byte = *cur & BitUtil::kPrecedingBitmask[start_bit_offset];
566 while (bit_mask != 0 && remaining > 0) {
567 current_byte = g() ? (current_byte | bit_mask) : current_byte;
568 bit_mask = static_cast<uint8_t>(bit_mask << 1);
569 --remaining;
570 }
571 *cur++ = current_byte;
572 }
573
574 int64_t remaining_bytes = remaining / 8;
575 while (remaining_bytes-- > 0) {
576 current_byte = 0;
577 current_byte = g() ? current_byte | 0x01 : current_byte;
578 current_byte = g() ? current_byte | 0x02 : current_byte;
579 current_byte = g() ? current_byte | 0x04 : current_byte;
580 current_byte = g() ? current_byte | 0x08 : current_byte;
581 current_byte = g() ? current_byte | 0x10 : current_byte;
582 current_byte = g() ? current_byte | 0x20 : current_byte;
583 current_byte = g() ? current_byte | 0x40 : current_byte;
584 current_byte = g() ? current_byte | 0x80 : current_byte;
585 *cur++ = current_byte;
586 }
587
588 int64_t remaining_bits = remaining % 8;
589 if (remaining_bits) {
590 current_byte = 0;
591 bit_mask = 0x01;
592 while (remaining_bits-- > 0) {
593 current_byte = g() ? (current_byte | bit_mask) : current_byte;
594 bit_mask = static_cast<uint8_t>(bit_mask << 1);
595 }
596 *cur++ = current_byte;
597 }
598}
599
600// ----------------------------------------------------------------------
601// Bitmap utilities
602
603/// Copy a bit range of an existing bitmap
604///
605/// \param[in] pool memory pool to allocate memory from
606/// \param[in] bitmap source data
607/// \param[in] offset bit offset into the source data
608/// \param[in] length number of bits to copy
609/// \param[out] out the resulting copy
610///
611/// \return Status message
612ARROW_EXPORT
613Status CopyBitmap(MemoryPool* pool, const uint8_t* bitmap, int64_t offset, int64_t length,
614 std::shared_ptr<Buffer>* out);
615
616/// Copy a bit range of an existing bitmap into an existing bitmap
617///
618/// \param[in] bitmap source data
619/// \param[in] offset bit offset into the source data
620/// \param[in] length number of bits to copy
621/// \param[in] dest_offset bit offset into the destination
622/// \param[out] dest the destination buffer, must have at least space for
623/// (offset + length) bits
624ARROW_EXPORT
625void CopyBitmap(const uint8_t* bitmap, int64_t offset, int64_t length, uint8_t* dest,
626 int64_t dest_offset);
627
628/// Invert a bit range of an existing bitmap into an existing bitmap
629///
630/// \param[in] bitmap source data
631/// \param[in] offset bit offset into the source data
632/// \param[in] length number of bits to copy
633/// \param[in] dest_offset bit offset into the destination
634/// \param[out] dest the destination buffer, must have at least space for
635/// (offset + length) bits
636ARROW_EXPORT
637void InvertBitmap(const uint8_t* bitmap, int64_t offset, int64_t length, uint8_t* dest,
638 int64_t dest_offset);
639
640/// Invert a bit range of an existing bitmap
641///
642/// \param[in] pool memory pool to allocate memory from
643/// \param[in] bitmap source data
644/// \param[in] offset bit offset into the source data
645/// \param[in] length number of bits to copy
646/// \param[out] out the resulting copy
647///
648/// \return Status message
649ARROW_EXPORT
650Status InvertBitmap(MemoryPool* pool, const uint8_t* bitmap, int64_t offset,
651 int64_t length, std::shared_ptr<Buffer>* out);
652
653/// Compute the number of 1's in the given data array
654///
655/// \param[in] data a packed LSB-ordered bitmap as a byte array
656/// \param[in] bit_offset a bitwise offset into the bitmap
657/// \param[in] length the number of bits to inspect in the bitmap relative to
658/// the offset
659///
660/// \return The number of set (1) bits in the range
661ARROW_EXPORT
662int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length);
663
664ARROW_EXPORT
665bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right,
666 int64_t right_offset, int64_t bit_length);
667
668ARROW_EXPORT
669Status BitmapAnd(MemoryPool* pool, const uint8_t* left, int64_t left_offset,
670 const uint8_t* right, int64_t right_offset, int64_t length,
671 int64_t out_offset, std::shared_ptr<Buffer>* out_buffer);
672
673ARROW_EXPORT
674Status BitmapOr(MemoryPool* pool, const uint8_t* left, int64_t left_offset,
675 const uint8_t* right, int64_t right_offset, int64_t length,
676 int64_t out_offset, std::shared_ptr<Buffer>* out_buffer);
677
678ARROW_EXPORT
679Status BitmapXor(MemoryPool* pool, const uint8_t* left, int64_t left_offset,
680 const uint8_t* right, int64_t right_offset, int64_t length,
681 int64_t out_offset, std::shared_ptr<Buffer>* out_buffer);
682
683} // namespace internal
684} // namespace arrow
685
686#endif // ARROW_UTIL_BIT_UTIL_H
687