| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef SRC_UI_LIB_ESCHER_UTIL_BIT_OPS_H_ |
| #define SRC_UI_LIB_ESCHER_UTIL_BIT_OPS_H_ |
| |
| #include <cmath> |
| #include <cstdint> |
| #include <limits> |
| #include <type_traits> |
| |
| namespace escher { |
| |
| // Rotate the value the specified number of bits to the left. In other words, |
| // this is a bit-shift where any high-order bits that are "shifted out" are |
| // "rotated in" as the low-order bytes instead of being discarded. |
| template <typename IntT> |
| constexpr IntT RotateLeft(IntT val, size_t len) { |
| static_assert(std::is_unsigned<IntT>::value, "RotateLeft only makes sense for unsigned types."); |
| return (val << len) | (val >> (std::numeric_limits<IntT>::digits - len)); |
| } |
| |
| // Use compiler built-ins, if available. |
| #if defined(__clang__) || defined(__GCC__) |
| inline int32_t CountLeadingZeros(uint32_t value) { return value == 0 ? 32 : __builtin_clz(value); } |
| inline int32_t CountTrailingZeros(uint32_t value) { return value == 0 ? 32 : __builtin_ctz(value); } |
| inline uint32_t CountOnes(uint32_t value) { return uint32_t(__builtin_popcount(value)); } |
| #else |
| inline int32_t CountLeadingZeros(uint32_t value) { |
| constexpr uint32_t mask = 1 << 31; |
| int32_t count = 0; |
| while (value != 0) { |
| if (value & mask) { |
| return count; |
| } |
| count += 1; |
| value = value << 1; |
| } |
| return 32; |
| } |
| inline int32_t CountTrailingZeros(uint32_t value) { |
| int32_t count = 0; |
| while (value != 0) { |
| if (value & 1) { |
| return count; |
| } |
| count += 1; |
| value = value >> 1; |
| } |
| return 32; |
| } |
| inline uint32_t CountOnes(uint32_t value) { |
| uint32_t count = 0; |
| while (value != 0) { |
| count += value & 1; |
| value = value >> 1; |
| } |
| return count; |
| } |
| #endif // #if defined(__clang__) || defined(__GCC__) |
| |
| inline int32_t CountLeadingOnes(uint32_t value) { return CountLeadingZeros(~value); } |
| |
| inline int32_t CountTrailingOnes(uint32_t value) { return CountTrailingZeros(~value); } |
| |
| // Invoke |func| with the index of each non-zero bit in |value|. |
| template <typename T> |
| inline void ForEachBitIndex(uint32_t value, const T& func) { |
| while (value) { |
| uint32_t bit = CountTrailingZeros(value); |
| func(bit); |
| value &= ~(1u << bit); |
| } |
| } |
| |
| // Invoke |func| for each contiguous range of non-zero bits in |value|. Two |
| // arguments are passed to each invocation of |func|: |
| // - the index of the initial bit of the range |
| // - the number of bits in the range |
| template <typename T> |
| inline void ForEachBitRange(uint32_t value, const T& func) { |
| while (value) { |
| // Find the first non-zero bit. |
| uint32_t bit = CountTrailingZeros(value); |
| // Starting with that bit, count the number of contiguous non-zero bits. |
| uint32_t range = CountTrailingOnes(value >> bit); |
| func(bit, range); |
| // Prepare for the next iteration by zeroing out the non-zero range that |
| // was just found. |
| value &= ~((1u << (bit + range)) - 1); |
| } |
| } |
| |
| // Set to 1 all bits in |input| at and above |index|. |
| template <typename T> |
| inline void SetBitsAtAndAboveIndex(T* input, uint32_t index) { |
| using UT = std::make_unsigned_t<T>; |
| *input |= ~(static_cast<T>((UT{1} << index) - 1U)); |
| } |
| |
| } // namespace escher |
| |
| #endif // SRC_UI_LIB_ESCHER_UTIL_BIT_OPS_H_ |