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 <vector>
59 
60 #include "arrow/util/macros.h"
61 #include "arrow/util/type_traits.h"
62 #include "arrow/util/visibility.h"
63 
64 #ifdef ARROW_USE_SSE
65 #include "arrow/util/cpu-info.h"
66 #include "arrow/util/sse-util.h"
67 #endif
68 
69 namespace arrow {
70 
71 // TODO(wesm): The source from Impala was depending on boost::make_unsigned
72 //
73 // We add a partial stub implementation here
74 
75 namespace detail {
76 
77 template <typename T>
78 struct make_unsigned {};
79 
80 template <>
81 struct make_unsigned<int8_t> {
82  typedef uint8_t type;
83 };
84 
85 template <>
86 struct make_unsigned<int16_t> {
87  typedef uint16_t type;
88 };
89 
90 template <>
91 struct make_unsigned<int32_t> {
92  typedef uint32_t type;
93 };
94 
95 template <>
96 struct make_unsigned<int64_t> {
97  typedef uint64_t type;
98 };
99 
100 } // namespace detail
101 
102 class Buffer;
103 class MemoryPool;
104 class MutableBuffer;
105 class Status;
106 
107 namespace BitUtil {
108 
109 static constexpr uint8_t kBitmask[] = {1, 2, 4, 8, 16, 32, 64, 128};
110 
111 // the ~i byte version of kBitmaks
112 static constexpr uint8_t kFlippedBitmask[] = {254, 253, 251, 247, 239, 223, 191, 127};
113 
114 static inline int64_t CeilByte(int64_t size) { return (size + 7) & ~7; }
115 
116 static inline int64_t BytesForBits(int64_t size) { return CeilByte(size) / 8; }
117 
118 static inline int64_t Ceil2Bytes(int64_t size) { return (size + 15) & ~15; }
119 
120 static inline bool GetBit(const uint8_t* bits, int64_t i) {
121  return (bits[i / 8] & kBitmask[i % 8]) != 0;
122 }
123 
124 static inline bool BitNotSet(const uint8_t* bits, int64_t i) {
125  return (bits[i / 8] & kBitmask[i % 8]) == 0;
126 }
127 
128 static inline void ClearBit(uint8_t* bits, int64_t i) {
129  bits[i / 8] &= kFlippedBitmask[i % 8];
130 }
131 
132 static inline void SetBit(uint8_t* bits, int64_t i) { bits[i / 8] |= kBitmask[i % 8]; }
133 
135 static inline void SetArrayBit(uint8_t* bits, int i, bool is_set) {
136  if (is_set) {
137  SetBit(bits, i);
138  }
139 }
140 
141 static inline void SetBitTo(uint8_t* bits, int64_t i, bool bit_is_set) {
142  // https://graphics.stanford.edu/~seander/bithacks.html
143  // "Conditionally set or clear bits without branching"
144  bits[i / 8] ^= static_cast<uint8_t>(-static_cast<uint8_t>(bit_is_set) ^ bits[i / 8]) &
145  kBitmask[i % 8];
146 }
147 
148 // Returns the minimum number of bits needed to represent the value of 'x'
149 static inline int NumRequiredBits(uint64_t x) {
150  for (int i = 63; i >= 0; --i) {
151  if (x & (UINT64_C(1) << i)) return i + 1;
152  }
153  return 0;
154 }
155 
160 static inline int64_t NextPower2(int64_t n) {
161  n--;
162  n |= n >> 1;
163  n |= n >> 2;
164  n |= n >> 4;
165  n |= n >> 8;
166  n |= n >> 16;
167  n |= n >> 32;
168  n++;
169  return n;
170 }
171 
172 static inline bool IsMultipleOf64(int64_t n) { return (n & 63) == 0; }
173 
174 static inline bool IsMultipleOf8(int64_t n) { return (n & 7) == 0; }
175 
177 static inline int64_t Ceil(int64_t value, int64_t divisor) {
178  return value / divisor + (value % divisor != 0);
179 }
180 
182 inline int64_t RoundUp(int64_t value, int64_t factor) {
183  return (value + (factor - 1)) / factor * factor;
184 }
185 
187 static inline int64_t RoundDown(int64_t value, int64_t factor) {
188  return (value / factor) * factor;
189 }
190 
193 static inline int RoundUpToPowerOf2(int value, int factor) {
194  // DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
195  return (value + (factor - 1)) & ~(factor - 1);
196 }
197 
198 static inline int RoundDownToPowerOf2(int value, int factor) {
199  // DCHECK((factor > 0) && ((factor & (factor - 1)) == 0));
200  return value & ~(factor - 1);
201 }
202 
206 static inline uint32_t RoundUpNumBytes(uint32_t bits) { return (bits + 7) >> 3; }
207 
209 static inline uint32_t RoundDownNumBytes(uint32_t bits) { return bits >> 3; }
210 
212 static inline uint32_t RoundUpNumi32(uint32_t bits) { return (bits + 31) >> 5; }
213 
215 static inline uint32_t RoundDownNumi32(uint32_t bits) { return bits >> 5; }
216 
218 static inline uint32_t RoundUpNumi64(uint32_t bits) { return (bits + 63) >> 6; }
219 
221 static inline uint32_t RoundDownNumi64(uint32_t bits) { return bits >> 6; }
222 
223 template <int64_t ROUND_TO>
224 static inline int64_t RoundToPowerOfTwo(int64_t num) {
225  // TODO(wesm): is this definitely needed?
226  // DCHECK_GE(num, 0);
227  constexpr int64_t force_carry_addend = ROUND_TO - 1;
228  constexpr int64_t truncate_bitmask = ~(ROUND_TO - 1);
229  constexpr int64_t max_roundable_num = std::numeric_limits<int64_t>::max() - ROUND_TO;
230  if (num <= max_roundable_num) {
231  return (num + force_carry_addend) & truncate_bitmask;
232  }
233  // handle overflow case. This should result in a malloc error upstream
234  return num;
235 }
236 
237 static inline int64_t RoundUpToMultipleOf64(int64_t num) {
238  return RoundToPowerOfTwo<64>(num);
239 }
240 
241 static inline int64_t RoundUpToMultipleOf8(int64_t num) {
242  return RoundToPowerOfTwo<8>(num);
243 }
244 
248 static inline int PopcountNoHw(uint64_t x) {
249  int count = 0;
250  for (; x != 0; ++count) x &= x - 1;
251  return count;
252 }
253 
255 static inline int Popcount(uint64_t x) {
256 #ifdef ARROW_USE_SSE
258  return POPCNT_popcnt_u64(x);
259  } else {
260  return PopcountNoHw(x);
261  }
262 #else
263  return PopcountNoHw(x);
264 #endif
265 }
266 
267 // Compute correct population count for various-width signed integers
268 template <typename T>
269 static inline int PopcountSigned(T v) {
270  // Converting to same-width unsigned then extending preserves the bit pattern.
271  return BitUtil::Popcount(static_cast<typename detail::make_unsigned<T>::type>(v));
272 }
273 
275 static inline uint64_t TrailingBits(uint64_t v, int num_bits) {
276  if (ARROW_PREDICT_FALSE(num_bits == 0)) return 0;
277  if (ARROW_PREDICT_FALSE(num_bits >= 64)) return v;
278  int n = 64 - num_bits;
279  return (v << n) >> n;
280 }
281 
285 static inline int Log2(uint64_t x) {
286  // DCHECK_GT(x, 0);
287  if (x == 1) return 0;
288  // Compute result = ceil(log2(x))
289  // = floor(log2(x - 1)) + 1, for x > 1
290  // by finding the position of the most significant bit (1-indexed) of x - 1
291  // (floor(log2(n)) = MSB(n) (0-indexed))
292  --x;
293  int result = 1;
294  while (x >>= 1) ++result;
295  return result;
296 }
297 
299 static inline int64_t CountLeadingZeros(uint32_t value) {
300 // DCHECK_NE(value, 0);
301 #if defined(__clang__) || defined(__GNUC__)
302  return static_cast<int64_t>(__builtin_clz(value));
303 #elif defined(_MSC_VER)
304  unsigned long index; // NOLINT
305  _BitScanReverse(&index, static_cast<unsigned long>(value)); // NOLINT
306  return 31LL - static_cast<int64_t>(index);
307 #else
308  int64_t bitpos = 0;
309  while (value != 0) {
310  value >>= 1;
311  ++bitpos;
312  }
313  return 32LL - bitpos;
314 #endif
315 }
316 
318 static inline int64_t ByteSwap(int64_t value) { return ARROW_BYTE_SWAP64(value); }
319 static inline uint64_t ByteSwap(uint64_t value) {
320  return static_cast<uint64_t>(ARROW_BYTE_SWAP64(value));
321 }
322 static inline int32_t ByteSwap(int32_t value) { return ARROW_BYTE_SWAP32(value); }
323 static inline uint32_t ByteSwap(uint32_t value) {
324  return static_cast<uint32_t>(ARROW_BYTE_SWAP32(value));
325 }
326 static inline int16_t ByteSwap(int16_t value) {
327  constexpr auto m = static_cast<int16_t>(0xff);
328  return static_cast<int16_t>(((value >> 8) & m) | ((value & m) << 8));
329 }
330 static inline uint16_t ByteSwap(uint16_t value) {
331  return static_cast<uint16_t>(ByteSwap(static_cast<int16_t>(value)));
332 }
333 
335 static inline void ByteSwap(void* dst, const void* src, int len) {
336  switch (len) {
337  case 1:
338  *reinterpret_cast<int8_t*>(dst) = *reinterpret_cast<const int8_t*>(src);
339  return;
340  case 2:
341  *reinterpret_cast<int16_t*>(dst) = ByteSwap(*reinterpret_cast<const int16_t*>(src));
342  return;
343  case 4:
344  *reinterpret_cast<int32_t*>(dst) = ByteSwap(*reinterpret_cast<const int32_t*>(src));
345  return;
346  case 8:
347  *reinterpret_cast<int64_t*>(dst) = ByteSwap(*reinterpret_cast<const int64_t*>(src));
348  return;
349  default:
350  break;
351  }
352 
353  auto d = reinterpret_cast<uint8_t*>(dst);
354  auto s = reinterpret_cast<const uint8_t*>(src);
355  for (int i = 0; i < len; ++i) {
356  d[i] = s[len - i - 1];
357  }
358 }
359 
362 #if ARROW_LITTLE_ENDIAN
363 template <typename T,
364  typename =
365  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
366 static inline T ToBigEndian(T value) {
367  return ByteSwap(value);
368 }
369 
370 template <typename T,
371  typename =
372  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
373 static inline T ToLittleEndian(T value) {
374  return value;
375 }
376 #else
377 template <typename T,
378  typename =
379  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
380 static inline T ToBigEndian(T value) {
381  return value;
382 }
383 #endif
384 
386 #if ARROW_LITTLE_ENDIAN
387 template <typename T,
388  typename =
389  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
390 static inline T FromBigEndian(T value) {
391  return ByteSwap(value);
392 }
393 
394 template <typename T,
395  typename =
396  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
397 static inline T FromLittleEndian(T value) {
398  return value;
399 }
400 #else
401 template <typename T,
402  typename =
403  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
404 static inline T FromBigEndian(T value) {
405  return value;
406 }
407 
408 template <typename T,
409  typename =
410  EnableIfIsOneOf<T, int64_t, uint64_t, int32_t, uint32_t, int16_t, uint16_t>>
411 static inline T FromLittleEndian(T value) {
412  return ByteSwap(value);
413 }
414 #endif
415 
416 // Logical right shift for signed integer types
417 // This is needed because the C >> operator does arithmetic right shift
418 // Negative shift amounts lead to undefined behavior
419 template <typename T>
420 static T ShiftRightLogical(T v, int shift) {
421  // Conversion to unsigned ensures most significant bits always filled with 0's
422  return static_cast<typename detail::make_unsigned<T>::type>(v) >> shift;
423 }
424 
425 void FillBitsFromBytes(const std::vector<uint8_t>& bytes, uint8_t* bits);
426 
428 ARROW_EXPORT
429 Status BytesToBits(const std::vector<uint8_t>&, MemoryPool*, std::shared_ptr<Buffer>*);
430 
431 } // namespace BitUtil
432 
433 namespace internal {
434 
435 class BitmapReader {
436  public:
437  BitmapReader(const uint8_t* bitmap, int64_t start_offset, int64_t length)
438  : bitmap_(bitmap), position_(0), length_(length) {
439  current_byte_ = 0;
440  byte_offset_ = start_offset / 8;
441  bit_offset_ = start_offset % 8;
442  if (length > 0) {
443  current_byte_ = bitmap[byte_offset_];
444  }
445  }
446 
447 #if defined(_MSC_VER)
448  // MSVC is finicky about this cast
449  bool IsSet() const { return (current_byte_ & (1 << bit_offset_)) != 0; }
450 #else
451  bool IsSet() const { return current_byte_ & (1 << bit_offset_); }
452 #endif
453 
454  bool IsNotSet() const { return (current_byte_ & (1 << bit_offset_)) == 0; }
455 
456  void Next() {
457  ++bit_offset_;
458  ++position_;
459  if (bit_offset_ == 8) {
460  bit_offset_ = 0;
461  ++byte_offset_;
462  if (ARROW_PREDICT_TRUE(position_ < length_)) {
463  current_byte_ = bitmap_[byte_offset_];
464  }
465  }
466  }
467 
468  private:
469  const uint8_t* bitmap_;
470  int64_t position_;
471  int64_t length_;
472 
473  uint8_t current_byte_;
474  int64_t byte_offset_;
475  int64_t bit_offset_;
476 };
477 
478 class BitmapWriter {
479  public:
480  BitmapWriter(uint8_t* bitmap, int64_t start_offset, int64_t length)
481  : bitmap_(bitmap), position_(0), length_(length) {
482  current_byte_ = 0;
483  byte_offset_ = start_offset / 8;
484  bit_offset_ = start_offset % 8;
485  if (length > 0) {
486  current_byte_ = bitmap[byte_offset_];
487  }
488  }
489 
490  void Set() { current_byte_ |= BitUtil::kBitmask[bit_offset_]; }
491 
492  void Clear() { current_byte_ &= BitUtil::kFlippedBitmask[bit_offset_]; }
493 
494  void Next() {
495  ++bit_offset_;
496  ++position_;
497  bitmap_[byte_offset_] = current_byte_;
498  if (bit_offset_ == 8) {
499  bit_offset_ = 0;
500  ++byte_offset_;
501  if (ARROW_PREDICT_TRUE(position_ < length_)) {
502  current_byte_ = bitmap_[byte_offset_];
503  }
504  }
505  }
506 
507  void Finish() {
508  if (ARROW_PREDICT_TRUE(position_ < length_)) {
509  if (bit_offset_ != 0) {
510  bitmap_[byte_offset_] = current_byte_;
511  }
512  }
513  }
514 
515  int64_t position() const { return position_; }
516 
517  private:
518  uint8_t* bitmap_;
519  int64_t position_;
520  int64_t length_;
521 
522  uint8_t current_byte_;
523  int64_t byte_offset_;
524  int64_t bit_offset_;
525 };
526 
527 } // namespace internal
528 
529 // ----------------------------------------------------------------------
530 // Bitmap utilities
531 
532 ARROW_EXPORT
533 Status GetEmptyBitmap(MemoryPool* pool, int64_t length, std::shared_ptr<Buffer>* result);
534 
544 ARROW_EXPORT
545 Status CopyBitmap(MemoryPool* pool, const uint8_t* bitmap, int64_t offset, int64_t length,
546  std::shared_ptr<Buffer>* out);
547 
555 ARROW_EXPORT
556 int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length);
557 
558 ARROW_EXPORT
559 bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right,
560  int64_t right_offset, int64_t bit_length);
561 
562 } // namespace arrow
563 
564 #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.
#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
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.