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