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