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