Apache Arrow (C++)
A columnar in-memory analytics layer designed to accelerate big data.
bit-util.h
Go to the documentation of this file.
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 <limits>
57 #include <memory>
58 #include <type_traits>
59 #include <vector>
60 
61 #include "arrow/util/macros.h"
62 #include "arrow/util/type_traits.h"
63 #include "arrow/util/visibility.h"
64 
65 #ifdef ARROW_USE_SSE
66 #include "arrow/util/cpu-info.h"
67 #include "arrow/util/sse-util.h"
68 #endif
69 
70 namespace arrow {
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 class Buffer;
82 class MemoryPool;
83 class MutableBuffer;
84 class Status;
85 
86 namespace BitUtil {
87 
88 static constexpr uint8_t kBitmask[] = {1, 2, 4, 8, 16, 32, 64, 128};
89 
90 // the ~i byte version of kBitmaks
91 static constexpr uint8_t kFlippedBitmask[] = {254, 253, 251, 247, 239, 223, 191, 127};
92 
93 static inline int64_t CeilByte(int64_t size) { return (size + 7) & ~7; }
94 
95 static inline int64_t BytesForBits(int64_t size) { return CeilByte(size) / 8; }
96 
97 static inline int64_t Ceil2Bytes(int64_t size) { return (size + 15) & ~15; }
98 
99 static inline bool GetBit(const uint8_t* bits, int64_t i) {
100  return (bits[i / 8] & kBitmask[i % 8]) != 0;
101 }
102 
103 static inline bool BitNotSet(const uint8_t* bits, int64_t i) {
104  return (bits[i / 8] & kBitmask[i % 8]) == 0;
105 }
106 
107 static inline void ClearBit(uint8_t* bits, int64_t i) {
108  bits[i / 8] &= kFlippedBitmask[i % 8];
109 }
110 
111 static inline void SetBit(uint8_t* bits, int64_t i) { bits[i / 8] |= kBitmask[i % 8]; }
112 
114 static inline void SetArrayBit(uint8_t* bits, int i, bool is_set) {
115  if (is_set) {
116  SetBit(bits, i);
117  }
118 }
119 
120 static inline void SetBitTo(uint8_t* bits, int64_t i, bool bit_is_set) {
121  // https://graphics.stanford.edu/~seander/bithacks.html
122  // "Conditionally set or clear bits without branching"
123  bits[i / 8] ^= static_cast<uint8_t>(-static_cast<uint8_t>(bit_is_set) ^ bits[i / 8]) &
124  kBitmask[i % 8];
125 }
126 
127 // Returns the minimum number of bits needed to represent the value of 'x'
128 static inline int NumRequiredBits(uint64_t x) {
129  for (int i = 63; i >= 0; --i) {
130  if (x & (UINT64_C(1) << i)) return i + 1;
131  }
132  return 0;
133 }
134 
139 static inline int64_t NextPower2(int64_t n) {
140  n--;
141  n |= n >> 1;
142  n |= n >> 2;
143  n |= n >> 4;
144  n |= n >> 8;
145  n |= n >> 16;
146  n |= n >> 32;
147  n++;
148  return n;
149 }
150 
151 static inline bool IsMultipleOf64(int64_t n) { return (n & 63) == 0; }
152 
153 static inline bool IsMultipleOf8(int64_t n) { return (n & 7) == 0; }
154 
156 static inline int64_t Ceil(int64_t value, int64_t divisor) {
157  return value / divisor + (value % divisor != 0);
158 }
159 
161 inline int64_t RoundUp(int64_t value, int64_t factor) {
162  return (value + (factor - 1)) / factor * factor;
163 }
164 
166 static inline int64_t RoundDown(int64_t value, int64_t factor) {
167  return (value / factor) * factor;
168 }
169 
172 static inline int RoundUpToPowerOf2(int value, int factor) {
173  // DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
174  return (value + (factor - 1)) & ~(factor - 1);
175 }
176 
177 static inline int RoundDownToPowerOf2(int value, int factor) {
178  // DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
179  return value & ~(factor - 1);
180 }
181 
185 static inline uint32_t RoundUpNumBytes(uint32_t bits) { return (bits + 7) >> 3; }
186 
188 static inline uint32_t RoundDownNumBytes(uint32_t bits) { return bits >> 3; }
189 
191 static inline uint32_t RoundUpNumi32(uint32_t bits) { return (bits + 31) >> 5; }
192 
194 static inline uint32_t RoundDownNumi32(uint32_t bits) { return bits >> 5; }
195 
197 static inline uint32_t RoundUpNumi64(uint32_t bits) { return (bits + 63) >> 6; }
198 
200 static inline uint32_t RoundDownNumi64(uint32_t bits) { return bits >> 6; }
201 
202 template <int64_t ROUND_TO>
203 static inline int64_t RoundToPowerOfTwo(int64_t num) {
204  // TODO(wesm): is this definitely needed?
205  // DCHECK_GE(num, 0);
206  constexpr int64_t force_carry_addend = ROUND_TO - 1;
207  constexpr int64_t truncate_bitmask = ~(ROUND_TO - 1);
208  constexpr int64_t max_roundable_num = std::numeric_limits<int64_t>::max() - ROUND_TO;
209  if (num <= max_roundable_num) {
210  return (num + force_carry_addend) & truncate_bitmask;
211  }
212  // handle overflow case. This should result in a malloc error upstream
213  return num;
214 }
215 
216 static inline int64_t RoundUpToMultipleOf64(int64_t num) {
217  return RoundToPowerOfTwo<64>(num);
218 }
219 
220 static inline int64_t RoundUpToMultipleOf8(int64_t num) {
221  return RoundToPowerOfTwo<8>(num);
222 }
223 
227 static inline int PopcountNoHw(uint64_t x) {
228  int count = 0;
229  for (; x != 0; ++count) x &= x - 1;
230  return count;
231 }
232 
234 static inline int Popcount(uint64_t x) {
235 #ifdef ARROW_USE_SSE
237  return POPCNT_popcnt_u64(x);
238  } else {
239  return PopcountNoHw(x);
240  }
241 #else
242  return PopcountNoHw(x);
243 #endif
244 }
245 
246 // Compute correct population count for various-width signed integers
247 template <typename T>
248 static inline int PopcountSigned(T v) {
249  // Converting to same-width unsigned then extending preserves the bit pattern.
250  return BitUtil::Popcount(detail::as_unsigned(v));
251 }
252 
254 static inline uint64_t TrailingBits(uint64_t v, int num_bits) {
255  if (ARROW_PREDICT_FALSE(num_bits == 0)) return 0;
256  if (ARROW_PREDICT_FALSE(num_bits >= 64)) return v;
257  int n = 64 - num_bits;
258  return (v << n) >> n;
259 }
260 
264 static inline int Log2(uint64_t x) {
265  // DCHECK_GT(x, 0);
266  if (x == 1) return 0;
267  // Compute result = ceil(log2(x))
268  // = floor(log2(x - 1)) + 1, for x > 1
269  // by finding the position of the most significant bit (1-indexed) of x - 1
270  // (floor(log2(n)) = MSB(n) (0-indexed))
271  --x;
272  int result = 1;
273  while (x >>= 1) ++result;
274  return result;
275 }
276 
278 static inline int64_t CountLeadingZeros(uint32_t value) {
279 // DCHECK_NE(value, 0);
280 #if defined(__clang__) || defined(__GNUC__)
281  return static_cast<int64_t>(__builtin_clz(value));
282 #elif defined(_MSC_VER)
283  unsigned long index; // NOLINT
284  _BitScanReverse(&index, static_cast<unsigned long>(value)); // NOLINT
285  return 31LL - static_cast<int64_t>(index);
286 #else
287  int64_t bitpos = 0;
288  while (value != 0) {
289  value >>= 1;
290  ++bitpos;
291  }
292  return 32LL - bitpos;
293 #endif
294 }
295 
297 static inline int64_t ByteSwap(int64_t value) { return ARROW_BYTE_SWAP64(value); }
298 static inline uint64_t ByteSwap(uint64_t value) {
299  return static_cast<uint64_t>(ARROW_BYTE_SWAP64(value));
300 }
301 static inline int32_t ByteSwap(int32_t value) { return ARROW_BYTE_SWAP32(value); }
302 static inline uint32_t ByteSwap(uint32_t value) {
303  return static_cast<uint32_t>(ARROW_BYTE_SWAP32(value));
304 }
305 static inline int16_t ByteSwap(int16_t value) {
306  constexpr auto m = static_cast<int16_t>(0xff);
307  return static_cast<int16_t>(((value >> 8) & m) | ((value & m) << 8));
308 }
309 static inline uint16_t ByteSwap(uint16_t value) {
310  return static_cast<uint16_t>(ByteSwap(static_cast<int16_t>(value)));
311 }
312 
314 static inline void ByteSwap(void* dst, const void* src, int len) {
315  switch (len) {
316  case 1:
317  *reinterpret_cast<int8_t*>(dst) = *reinterpret_cast<const int8_t*>(src);
318  return;
319  case 2:
320  *reinterpret_cast<int16_t*>(dst) = ByteSwap(*reinterpret_cast<const int16_t*>(src));
321  return;
322  case 4:
323  *reinterpret_cast<int32_t*>(dst) = ByteSwap(*reinterpret_cast<const int32_t*>(src));
324  return;
325  case 8:
326  *reinterpret_cast<int64_t*>(dst) = ByteSwap(*reinterpret_cast<const int64_t*>(src));
327  return;
328  default:
329  break;
330  }
331 
332  auto d = reinterpret_cast<uint8_t*>(dst);
333  auto s = reinterpret_cast<const uint8_t*>(src);
334  for (int i = 0; i < len; ++i) {
335  d[i] = s[len - i - 1];
336  }
337 }
338 
341 #if ARROW_LITTLE_ENDIAN
342 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
343  int16_t, uint16_t>>
344 static inline T ToBigEndian(T value) {
345  return ByteSwap(value);
346 }
347 
348 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
349  int16_t, uint16_t>>
350 static inline T ToLittleEndian(T value) {
351  return value;
352 }
353 #else
354 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
355  int16_t, uint16_t>>
356 static inline T ToBigEndian(T value) {
357  return value;
358 }
359 #endif
360 
362 #if ARROW_LITTLE_ENDIAN
363 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
364  int16_t, uint16_t>>
365 static inline T FromBigEndian(T value) {
366  return ByteSwap(value);
367 }
368 
369 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
370  int16_t, uint16_t>>
371 static inline T FromLittleEndian(T value) {
372  return value;
373 }
374 #else
375 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
376  int16_t, uint16_t>>
377 static inline T FromBigEndian(T value) {
378  return value;
379 }
380 
381 template <typename T, typename = EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t,
382  int16_t, uint16_t>>
383 static inline T FromLittleEndian(T value) {
384  return ByteSwap(value);
385 }
386 #endif
387 
388 // Logical right shift for signed integer types
389 // This is needed because the C >> operator does arithmetic right shift
390 // Negative shift amounts lead to undefined behavior
391 template <typename T>
392 static T ShiftRightLogical(T v, int shift) {
393  // Conversion to unsigned ensures most significant bits always filled with 0's
394  return detail::as_unsigned(v) >> shift;
395 }
396 
397 void FillBitsFromBytes(const std::vector<uint8_t>& bytes, uint8_t* bits);
398 
400 ARROW_EXPORT
401 Status BytesToBits(const std::vector<uint8_t>&, MemoryPool*, std::shared_ptr<Buffer>*);
402 
403 } // namespace BitUtil
404 
405 namespace internal {
406 
407 class BitmapReader {
408  public:
409  BitmapReader(const uint8_t* bitmap, int64_t start_offset, int64_t length)
410  : bitmap_(bitmap), position_(0), length_(length) {
411  current_byte_ = 0;
412  byte_offset_ = start_offset / 8;
413  bit_offset_ = start_offset % 8;
414  if (length > 0) {
415  current_byte_ = bitmap[byte_offset_];
416  }
417  }
418 
419 #if defined(_MSC_VER)
420  // MSVC is finicky about this cast
421  bool IsSet() const { return (current_byte_ & (1 << bit_offset_)) != 0; }
422 #else
423  bool IsSet() const { return current_byte_ & (1 << bit_offset_); }
424 #endif
425 
426  bool IsNotSet() const { return (current_byte_ & (1 << bit_offset_)) == 0; }
427 
428  void Next() {
429  ++bit_offset_;
430  ++position_;
431  if (ARROW_PREDICT_FALSE(bit_offset_ == 8)) {
432  bit_offset_ = 0;
433  ++byte_offset_;
434  if (ARROW_PREDICT_TRUE(position_ < length_)) {
435  current_byte_ = bitmap_[byte_offset_];
436  }
437  }
438  }
439 
440  private:
441  const uint8_t* bitmap_;
442  int64_t position_;
443  int64_t length_;
444 
445  uint8_t current_byte_;
446  int64_t byte_offset_;
447  int64_t bit_offset_;
448 };
449 
450 class BitmapWriter {
451  public:
452  BitmapWriter(uint8_t* bitmap, int64_t start_offset, int64_t length)
453  : bitmap_(bitmap), position_(0), length_(length) {
454  current_byte_ = 0;
455  byte_offset_ = start_offset / 8;
456  bit_mask_ = static_cast<uint8_t>(1 << (start_offset % 8));
457  if (length > 0) {
458  current_byte_ = bitmap[byte_offset_];
459  }
460  }
461 
462  void Set() { current_byte_ |= bit_mask_; }
463 
464  void Clear() { current_byte_ &= bit_mask_ ^ 0xFF; }
465 
466  void Next() {
467  bit_mask_ = static_cast<uint8_t>(bit_mask_ << 1);
468  ++position_;
469  if (bit_mask_ == 0) {
470  // Finished this byte, need advancing
471  bit_mask_ = 0x01;
472  bitmap_[byte_offset_++] = current_byte_;
473  if (ARROW_PREDICT_TRUE(position_ < length_)) {
474  current_byte_ = bitmap_[byte_offset_];
475  }
476  }
477  }
478 
479  void Finish() {
480  // Store current byte if we didn't went past bitmap storage
481  if (bit_mask_ != 0x01 || position_ < length_) {
482  bitmap_[byte_offset_] = current_byte_;
483  }
484  }
485 
486  int64_t position() const { return position_; }
487 
488  private:
489  uint8_t* bitmap_;
490  int64_t position_;
491  int64_t length_;
492 
493  uint8_t current_byte_;
494  uint8_t bit_mask_;
495  int64_t byte_offset_;
496 };
497 
498 } // namespace internal
499 
500 // ----------------------------------------------------------------------
501 // Bitmap utilities
502 
503 ARROW_EXPORT
504 Status GetEmptyBitmap(MemoryPool* pool, int64_t length, std::shared_ptr<Buffer>* result);
505 
515 ARROW_EXPORT
516 Status CopyBitmap(MemoryPool* pool, const uint8_t* bitmap, int64_t offset, int64_t length,
517  std::shared_ptr<Buffer>* out);
518 
526 ARROW_EXPORT
527 int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length);
528 
529 ARROW_EXPORT
530 bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right,
531  int64_t right_offset, int64_t bit_length);
532 
533 ARROW_EXPORT
534 Status BitmapAnd(MemoryPool* pool, const uint8_t* left, int64_t left_offset,
535  const uint8_t* right, int64_t right_offset, int64_t length,
536  int64_t out_offset, std::shared_ptr<Buffer>* out_buffer);
537 
538 } // namespace arrow
539 
540 #endif // ARROW_UTIL_BIT_UTIL_H
Status GetEmptyBitmap(MemoryPool *pool, int64_t length, std::shared_ptr< Buffer > *result)
static const int64_t POPCNT
Definition: cpu-info.h:40
#define ARROW_PREDICT_TRUE(x)
Definition: macros.h:49
int64_t CountSetBits(const uint8_t *data, int64_t bit_offset, int64_t length)
Compute the number of 1&#39;s in the given data array.
Status BitmapAnd(MemoryPool *pool, const uint8_t *left, int64_t left_offset, const uint8_t *right, int64_t right_offset, int64_t length, int64_t out_offset, std::shared_ptr< Buffer > *out_buffer)
#define ARROW_PREDICT_FALSE(x)
Definition: macros.h:48
#define ARROW_BYTE_SWAP32
Definition: bit-util.h:52
bool BitmapEquals(const uint8_t *left, int64_t left_offset, const uint8_t *right, int64_t right_offset, int64_t bit_length)
Top-level namespace for Apache Arrow C++ API.
Definition: adapter.h:32
#define ARROW_BYTE_SWAP64
Definition: bit-util.h:51
static bool IsSupported(int64_t flag)
Returns whether of not the cpu supports this flag.
Definition: cpu-info.h:60
typename std::enable_if< IsOneOf< T, Args... >::value, T >::type EnableIfIsOneOf
Shorthand for using IsOneOf + std::enable_if.
Definition: type_traits.h:37
Status CopyBitmap(MemoryPool *pool, const uint8_t *bitmap, int64_t offset, int64_t length, std::shared_ptr< Buffer > *out)
Copy a bit range of an existing bitmap.