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 <bit>
14 #include <concepts>
15
16 #include "base/check.h"
17
18 namespace base::bits {
19
20 // Bit functions in <bit> are restricted to a specific set of types of unsigned
21 // integer; restrict functions in this file that are related to those in that
22 // header to match for consistency.
23 template <typename T>
24 concept UnsignedInteger =
25 std::unsigned_integral<T> && !std::same_as<T, bool> &&
26 !std::same_as<T, char> && !std::same_as<T, char8_t> &&
27 !std::same_as<T, char16_t> && !std::same_as<T, char32_t> &&
28 !std::same_as<T, wchar_t>;
29
30 // We want to migrate all users of these functions to use the unsigned type
31 // versions of the functions, but until they are all moved over, create a
32 // concept that captures all the types that must be supported for compatibility
33 // but that we want to remove.
34 //
35 // TODO(https://crbug.com/1414634): Switch uses to supported functions and
36 // remove.
37 template <typename T>
38 concept SignedIntegerDeprecatedDoNotUse =
39 std::integral<T> && !UnsignedInteger<T>;
40
41 // Returns true iff |value| is a power of 2. DEPRECATED; use
42 // std::has_single_bit() instead.
43 //
44 // TODO(https://crbug.com/1414634): Switch uses and remove.
45 template <typename T>
46 requires SignedIntegerDeprecatedDoNotUse<T>
IsPowerOfTwoDeprecatedDoNotUse(T value)47 constexpr bool IsPowerOfTwoDeprecatedDoNotUse(T value) {
48 // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits.
49 //
50 // Only positive integers with a single bit set are powers of two. If only one
51 // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set
52 // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence
53 // |x & (x-1)| is 0 iff x is a power of two.
54 return value > 0 && (value & (value - 1)) == 0;
55 }
56
57 // Round down |size| to a multiple of alignment, which must be a power of two.
58 template <typename T>
59 requires UnsignedInteger<T>
AlignDown(T size,T alignment)60 inline constexpr T AlignDown(T size, T alignment) {
61 DCHECK(std::has_single_bit(alignment));
62 return size & ~(alignment - 1);
63 }
64
65 // Round down |size| to a multiple of alignment, which must be a power of two.
66 // DEPRECATED; use the UnsignedInteger version.
67 //
68 // TODO(https://crbug.com/1414634): Switch uses and remove.
69 template <typename T>
70 requires SignedIntegerDeprecatedDoNotUse<T>
AlignDownDeprecatedDoNotUse(T size,T alignment)71 inline constexpr T AlignDownDeprecatedDoNotUse(T size, T alignment) {
72 DCHECK(IsPowerOfTwoDeprecatedDoNotUse(alignment));
73 return size & ~(alignment - 1);
74 }
75
76 // Move |ptr| back to the previous multiple of alignment, which must be a power
77 // of two. Defined for types where sizeof(T) is one byte.
78 template <typename T>
79 requires(sizeof(T) == 1)
AlignDown(T * ptr,uintptr_t alignment)80 inline T* AlignDown(T* ptr, uintptr_t alignment) {
81 return reinterpret_cast<T*>(
82 AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment));
83 }
84
85 // Round up |size| to a multiple of alignment, which must be a power of two.
86 template <typename T>
87 requires UnsignedInteger<T>
AlignUp(T size,T alignment)88 inline constexpr T AlignUp(T size, T alignment) {
89 DCHECK(std::has_single_bit(alignment));
90 return (size + alignment - 1) & ~(alignment - 1);
91 }
92
93 // Round up |size| to a multiple of alignment, which must be a power of two.
94 // DEPRECATED; use the UnsignedInteger version.
95 //
96 // TODO(https://crbug.com/1414634): Switch uses and remove.
97 template <typename T>
98 requires SignedIntegerDeprecatedDoNotUse<T>
AlignUpDeprecatedDoNotUse(T size,T alignment)99 inline constexpr T AlignUpDeprecatedDoNotUse(T size, T alignment) {
100 DCHECK(IsPowerOfTwoDeprecatedDoNotUse(alignment));
101 return (size + alignment - 1) & ~(alignment - 1);
102 }
103
104 // Advance |ptr| to the next multiple of alignment, which must be a power of
105 // two. Defined for types where sizeof(T) is one byte.
106 template <typename T>
107 requires(sizeof(T) == 1)
AlignUp(T * ptr,uintptr_t alignment)108 inline T* AlignUp(T* ptr, uintptr_t alignment) {
109 return reinterpret_cast<T*>(
110 AlignUp(reinterpret_cast<uintptr_t>(ptr), alignment));
111 }
112
113 // Returns the integer i such as 2^i <= n < 2^(i+1).
114 //
115 // A common use for this function is to measure the number of bits required to
116 // contain a value; for that case use std::bit_width().
117 //
118 // A common use for this function is to take its result and use it to left-shift
119 // a bit; instead of doing so, use std::bit_floor().
Log2Floor(uint32_t n)120 constexpr int Log2Floor(uint32_t n) {
121 return 31 - std::countl_zero(n);
122 }
123
124 // Returns the integer i such as 2^(i-1) < n <= 2^i.
125 //
126 // A common use for this function is to measure the number of bits required to
127 // contain a value; for that case use std::bit_width().
128 //
129 // A common use for this function is to take its result and use it to left-shift
130 // a bit; instead of doing so, use std::bit_ceil().
Log2Ceiling(uint32_t n)131 constexpr int Log2Ceiling(uint32_t n) {
132 // When n == 0, we want the function to return -1.
133 // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
134 // why the statement below starts with (n ? 32 : -1).
135 return (n ? 32 : -1) - std::countl_zero(n - 1);
136 }
137
138 // Returns a value of type T with a single bit set in the left-most position.
139 // Can be used instead of manually shifting a 1 to the left. Unlike the other
140 // functions in this file, usable for any integral type.
141 template <typename T>
142 requires std::integral<T>
LeftmostBit()143 constexpr T LeftmostBit() {
144 T one(1u);
145 return one << (8 * sizeof(T) - 1);
146 }
147
148 } // namespace base::bits
149
150 #endif // BASE_BITS_H_
151