bits.h (5325B)
1 // Copyright 2013 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // This file defines some bit utilities. 6 7 #ifndef BASE_BITS_H_ 8 #define BASE_BITS_H_ 9 10 #include <stddef.h> 11 #include <stdint.h> 12 13 #include <type_traits> 14 15 #include "base/check.h" 16 #include "base/compiler_specific.h" 17 #include "build/build_config.h" 18 19 namespace base { 20 namespace bits { 21 22 // Returns true iff |value| is a power of 2. 23 // 24 // TODO(pkasting): When C++20 is available, replace with std::has_single_bit(). 25 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>> 26 constexpr bool IsPowerOfTwo(T value) { 27 // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits. 28 // 29 // Only positive integers with a single bit set are powers of two. If only one 30 // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set 31 // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence 32 // |x & (x-1)| is 0 iff x is a power of two. 33 return value > 0 && (value & (value - 1)) == 0; 34 } 35 36 // Round down |size| to a multiple of alignment, which must be a power of two. 37 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>> 38 constexpr T AlignDown(T size, T alignment) { 39 DCHECK(IsPowerOfTwo(alignment)); 40 return size & ~(alignment - 1); 41 } 42 43 // Move |ptr| back to the previous multiple of alignment, which must be a power 44 // of two. Defined for types where sizeof(T) is one byte. 45 template <typename T, typename = std::enable_if_t<sizeof(T) == 1>> 46 inline T* AlignDown(T* ptr, uintptr_t alignment) { 47 return reinterpret_cast<T*>( 48 AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment)); 49 } 50 51 // Round up |size| to a multiple of alignment, which must be a power of two. 52 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>> 53 constexpr T AlignUp(T size, T alignment) { 54 DCHECK(IsPowerOfTwo(alignment)); 55 return (size + alignment - 1) & ~(alignment - 1); 56 } 57 58 // Advance |ptr| to the next multiple of alignment, which must be a power of 59 // two. Defined for types where sizeof(T) is one byte. 60 template <typename T, typename = std::enable_if_t<sizeof(T) == 1>> 61 inline T* AlignUp(T* ptr, uintptr_t alignment) { 62 return reinterpret_cast<T*>( 63 AlignUp(reinterpret_cast<uintptr_t>(ptr), alignment)); 64 } 65 66 // CountLeadingZeroBits(value) returns the number of zero bits following the 67 // most significant 1 bit in |value| if |value| is non-zero, otherwise it 68 // returns {sizeof(T) * 8}. 69 // Example: 00100010 -> 2 70 // 71 // CountTrailingZeroBits(value) returns the number of zero bits preceding the 72 // least significant 1 bit in |value| if |value| is non-zero, otherwise it 73 // returns {sizeof(T) * 8}. 74 // Example: 00100010 -> 1 75 // 76 // C does not have an operator to do this, but fortunately the various 77 // compilers have built-ins that map to fast underlying processor instructions. 78 // 79 // TODO(pkasting): When C++20 is available, replace with std::countl_zero() and 80 // similar. 81 82 // __builtin_clz has undefined behaviour for an input of 0, even though there's 83 // clearly a return value that makes sense, and even though some processor clz 84 // instructions have defined behaviour for 0. We could drop to raw __asm__ to 85 // do better, but we'll avoid doing that unless we see proof that we need to. 86 template <typename T, int bits = sizeof(T) * 8> 87 ALWAYS_INLINE constexpr 88 typename std::enable_if<std::is_unsigned_v<T> && sizeof(T) <= 8, int>::type 89 CountLeadingZeroBits(T value) { 90 static_assert(bits > 0, "invalid instantiation"); 91 return LIKELY(value) 92 ? bits == 64 93 ? __builtin_clzll(static_cast<uint64_t>(value)) 94 : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits) 95 : bits; 96 } 97 98 template <typename T, int bits = sizeof(T) * 8> 99 ALWAYS_INLINE constexpr 100 typename std::enable_if<std::is_unsigned_v<T> && sizeof(T) <= 8, int>::type 101 CountTrailingZeroBits(T value) { 102 return LIKELY(value) ? bits == 64 103 ? __builtin_ctzll(static_cast<uint64_t>(value)) 104 : __builtin_ctz(static_cast<uint32_t>(value)) 105 : bits; 106 } 107 108 // Returns the integer i such as 2^i <= n < 2^(i+1). 109 // 110 // There is a common `BitLength` function, which returns the number of bits 111 // required to represent a value. Rather than implement that function, 112 // use `Log2Floor` and add 1 to the result. 113 // 114 // TODO(pkasting): When C++20 is available, replace with std::bit_xxx(). 115 constexpr int Log2Floor(uint32_t n) { 116 return 31 - CountLeadingZeroBits(n); 117 } 118 119 // Returns the integer i such as 2^(i-1) < n <= 2^i. 120 constexpr int Log2Ceiling(uint32_t n) { 121 // When n == 0, we want the function to return -1. 122 // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is 123 // why the statement below starts with (n ? 32 : -1). 124 return (n ? 32 : -1) - CountLeadingZeroBits(n - 1); 125 } 126 127 // Returns a value of type T with a single bit set in the left-most position. 128 // Can be used instead of manually shifting a 1 to the left. 129 template <typename T> 130 constexpr T LeftmostBit() { 131 static_assert(std::is_integral_v<T>, 132 "This function can only be used with integral types."); 133 T one(1u); 134 return one << (8 * sizeof(T) - 1); 135 } 136 137 } // namespace bits 138 } // namespace base 139 140 #endif // BASE_BITS_H_