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 | |
66 | namespace arrow { |
67 | |
68 | class Buffer; |
69 | class MemoryPool; |
70 | class Status; |
71 | |
72 | namespace detail { |
73 | |
74 | template <typename Integer> |
75 | typename 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 | |
81 | namespace BitUtil { |
82 | |
83 | // |
84 | // Bit-related computations on integer values |
85 | // |
86 | |
87 | // Returns the ceil of value/divisor |
88 | constexpr int64_t CeilDiv(int64_t value, int64_t divisor) { |
89 | return value / divisor + (value % divisor != 0); |
90 | } |
91 | |
92 | constexpr 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. |
96 | static 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 | |
110 | constexpr bool IsMultipleOf64(int64_t n) { return (n & 63) == 0; } |
111 | |
112 | constexpr bool IsMultipleOf8(int64_t n) { return (n & 7) == 0; } |
113 | |
114 | // Returns 'value' rounded up to the nearest multiple of 'factor' |
115 | constexpr 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. |
123 | constexpr 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 | |
128 | constexpr int64_t RoundUpToMultipleOf8(int64_t num) { return RoundUpToPowerOf2(num, 8); } |
129 | |
130 | constexpr int64_t RoundUpToMultipleOf64(int64_t num) { |
131 | return RoundUpToPowerOf2(num, 64); |
132 | } |
133 | |
134 | // Returns the 'num_bits' least-significant bits of 'v'. |
135 | static 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. |
143 | static 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 | |
164 | static 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 |
186 | static inline int NumRequiredBits(uint64_t x) { return 64 - CountLeadingZeros(x); } |
187 | |
188 | // Returns ceil(log2(x)). |
189 | static 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) |
199 | static inline int64_t ByteSwap(int64_t value) { return ARROW_BYTE_SWAP64(value); } |
200 | static inline uint64_t ByteSwap(uint64_t value) { |
201 | return static_cast<uint64_t>(ARROW_BYTE_SWAP64(value)); |
202 | } |
203 | static inline int32_t ByteSwap(int32_t value) { return ARROW_BYTE_SWAP32(value); } |
204 | static inline uint32_t ByteSwap(uint32_t value) { |
205 | return static_cast<uint32_t>(ARROW_BYTE_SWAP32(value)); |
206 | } |
207 | static 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 | } |
211 | static 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. |
216 | static 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 |
243 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
244 | uint32_t, int16_t, uint16_t>> |
245 | static inline T ToBigEndian(T value) { |
246 | return ByteSwap(value); |
247 | } |
248 | |
249 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
250 | uint32_t, int16_t, uint16_t>> |
251 | static inline T ToLittleEndian(T value) { |
252 | return value; |
253 | } |
254 | #else |
255 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
256 | uint32_t, int16_t, uint16_t>> |
257 | static inline T ToBigEndian(T value) { |
258 | return value; |
259 | } |
260 | |
261 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
262 | uint32_t, int16_t, uint16_t>> |
263 | static 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 |
270 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
271 | uint32_t, int16_t, uint16_t>> |
272 | static inline T FromBigEndian(T value) { |
273 | return ByteSwap(value); |
274 | } |
275 | |
276 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
277 | uint32_t, int16_t, uint16_t>> |
278 | static inline T FromLittleEndian(T value) { |
279 | return value; |
280 | } |
281 | #else |
282 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
283 | uint32_t, int16_t, uint16_t>> |
284 | static inline T FromBigEndian(T value) { |
285 | return value; |
286 | } |
287 | |
288 | template <typename T, typename = internal::EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, |
289 | uint32_t, int16_t, uint16_t>> |
290 | static 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 |
301 | static constexpr uint8_t kBitmask[] = {1, 2, 4, 8, 16, 32, 64, 128}; |
302 | |
303 | // the bitwise complement version of kBitmask |
304 | static constexpr uint8_t kFlippedBitmask[] = {254, 253, 251, 247, 239, 223, 191, 127}; |
305 | |
306 | // Bitmask selecting the (k - 1) preceding bits in a byte |
307 | static constexpr uint8_t kPrecedingBitmask[] = {0, 1, 3, 7, 15, 31, 63, 127}; |
308 | |
309 | // the bitwise complement version of kPrecedingBitmask |
310 | static constexpr uint8_t kTrailingBitmask[] = {255, 254, 252, 248, 240, 224, 192, 128}; |
311 | |
312 | static inline bool GetBit(const uint8_t* bits, uint64_t i) { |
313 | return (bits[i >> 3] >> (i & 0x07)) & 1; |
314 | } |
315 | |
316 | static inline void ClearBit(uint8_t* bits, int64_t i) { |
317 | bits[i / 8] &= kFlippedBitmask[i % 8]; |
318 | } |
319 | |
320 | static inline void SetBit(uint8_t* bits, int64_t i) { bits[i / 8] |= kBitmask[i % 8]; } |
321 | |
322 | static 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 |
332 | static 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 |
374 | ARROW_EXPORT |
375 | Status BytesToBits(const std::vector<uint8_t>&, MemoryPool*, std::shared_ptr<Buffer>*); |
376 | |
377 | } // namespace BitUtil |
378 | |
379 | namespace internal { |
380 | |
381 | class 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 | |
419 | class 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 | |
470 | class 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 | |
526 | template <class Generator> |
527 | void 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 | |
552 | template <class Generator> |
553 | void 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 |
612 | ARROW_EXPORT |
613 | Status 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 |
624 | ARROW_EXPORT |
625 | void 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 |
636 | ARROW_EXPORT |
637 | void 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 |
649 | ARROW_EXPORT |
650 | Status 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 |
661 | ARROW_EXPORT |
662 | int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length); |
663 | |
664 | ARROW_EXPORT |
665 | bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right, |
666 | int64_t right_offset, int64_t bit_length); |
667 | |
668 | ARROW_EXPORT |
669 | Status 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 | |
673 | ARROW_EXPORT |
674 | Status 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 | |
678 | ARROW_EXPORT |
679 | Status 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 | |