1 // Copyright 2020 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // -----------------------------------------------------------------------------
16 // File: bits.h
17 // -----------------------------------------------------------------------------
18 //
19 // This file contains implementations of C++20's bitwise math functions, as
20 // defined by:
21 //
22 // P0553R4:
23 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html
24 // P0556R3:
25 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0556r3.html
26 // P1355R2:
27 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1355r2.html
28 // P1956R1:
29 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf
30 //
31 // When using a standard library that implements these functions, we use the
32 // standard library's implementation.
33
34 #ifndef ABSL_NUMERIC_BITS_H_
35 #define ABSL_NUMERIC_BITS_H_
36
37 #include <cstdint>
38 #include <limits>
39 #include <type_traits>
40
41 #include "absl/base/config.h"
42
43 #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L
44 #include <bit>
45 #endif
46
47 #include "absl/base/attributes.h"
48 #include "absl/numeric/internal/bits.h"
49
50 namespace absl {
51 ABSL_NAMESPACE_BEGIN
52
53 // https://github.com/llvm/llvm-project/issues/64544
54 // libc++ had the wrong signature for std::rotl and std::rotr
55 // prior to libc++ 18.0.
56 //
57 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) && \
58 (!defined(_LIBCPP_VERSION) || _LIBCPP_VERSION >= 180000)
59 using std::rotl;
60 using std::rotr;
61
62 #else
63
64 // Rotating functions
65 template <class T>
66 ABSL_MUST_USE_RESULT constexpr
67 typename std::enable_if<std::is_unsigned<T>::value, T>::type
68 rotl(T x, int s) noexcept {
69 return numeric_internal::RotateLeft(x, s);
70 }
71
72 template <class T>
73 ABSL_MUST_USE_RESULT constexpr
74 typename std::enable_if<std::is_unsigned<T>::value, T>::type
75 rotr(T x, int s) noexcept {
76 return numeric_internal::RotateRight(x, s);
77 }
78
79 #endif
80
81 // https://github.com/llvm/llvm-project/issues/64544
82 // libc++ had the wrong signature for std::rotl and std::rotr
83 // prior to libc++ 18.0.
84 //
85 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
86
87 using std::countl_one;
88 using std::countl_zero;
89 using std::countr_one;
90 using std::countr_zero;
91 using std::popcount;
92
93 #else
94
95 // Counting functions
96 //
97 // While these functions are typically constexpr, on some platforms, they may
98 // not be marked as constexpr due to constraints of the compiler/available
99 // intrinsics.
100 template <class T>
101 ABSL_INTERNAL_CONSTEXPR_CLZ inline
102 typename std::enable_if<std::is_unsigned<T>::value, int>::type
countl_zero(T x)103 countl_zero(T x) noexcept {
104 return numeric_internal::CountLeadingZeroes(x);
105 }
106
107 template <class T>
108 ABSL_INTERNAL_CONSTEXPR_CLZ inline
109 typename std::enable_if<std::is_unsigned<T>::value, int>::type
countl_one(T x)110 countl_one(T x) noexcept {
111 // Avoid integer promotion to a wider type
112 return countl_zero(static_cast<T>(~x));
113 }
114
115 template <class T>
116 ABSL_INTERNAL_CONSTEXPR_CTZ inline
117 typename std::enable_if<std::is_unsigned<T>::value, int>::type
countr_zero(T x)118 countr_zero(T x) noexcept {
119 return numeric_internal::CountTrailingZeroes(x);
120 }
121
122 template <class T>
123 ABSL_INTERNAL_CONSTEXPR_CTZ inline
124 typename std::enable_if<std::is_unsigned<T>::value, int>::type
countr_one(T x)125 countr_one(T x) noexcept {
126 // Avoid integer promotion to a wider type
127 return countr_zero(static_cast<T>(~x));
128 }
129
130 template <class T>
131 ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline
132 typename std::enable_if<std::is_unsigned<T>::value, int>::type
popcount(T x)133 popcount(T x) noexcept {
134 return numeric_internal::Popcount(x);
135 }
136
137 #endif
138
139 #if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L)
140
141 using std::bit_ceil;
142 using std::bit_floor;
143 using std::bit_width;
144 using std::has_single_bit;
145
146 #else
147
148 // Returns: true if x is an integral power of two; false otherwise.
149 template <class T>
150 constexpr inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
has_single_bit(T x)151 has_single_bit(T x) noexcept {
152 return x != 0 && (x & (x - 1)) == 0;
153 }
154
155 // Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any
156 // fractional part discarded.
157 template <class T>
158 ABSL_INTERNAL_CONSTEXPR_CLZ inline
159 typename std::enable_if<std::is_unsigned<T>::value, int>::type
bit_width(T x)160 bit_width(T x) noexcept {
161 return std::numeric_limits<T>::digits - countl_zero(x);
162 }
163
164 // Returns: If x == 0, 0; otherwise the maximal value y such that
165 // has_single_bit(y) is true and y <= x.
166 template <class T>
167 ABSL_INTERNAL_CONSTEXPR_CLZ inline
168 typename std::enable_if<std::is_unsigned<T>::value, T>::type
bit_floor(T x)169 bit_floor(T x) noexcept {
170 return x == 0 ? 0 : T{1} << (bit_width(x) - 1);
171 }
172
173 // Returns: N, where N is the smallest power of 2 greater than or equal to x.
174 //
175 // Preconditions: N is representable as a value of type T.
176 template <class T>
177 ABSL_INTERNAL_CONSTEXPR_CLZ inline
178 typename std::enable_if<std::is_unsigned<T>::value, T>::type
bit_ceil(T x)179 bit_ceil(T x) {
180 // If T is narrower than unsigned, T{1} << bit_width will be promoted. We
181 // want to force it to wraparound so that bit_ceil of an invalid value are not
182 // core constant expressions.
183 //
184 // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would
185 // undergo promotion to unsigned but not fit the result into T without
186 // truncation.
187 return has_single_bit(x) ? T{1} << (bit_width(x) - 1)
188 : numeric_internal::BitCeilNonPowerOf2(x);
189 }
190
191 #endif
192
193 ABSL_NAMESPACE_END
194 } // namespace absl
195
196 #endif // ABSL_NUMERIC_BITS_H_
197