bits.h (8013B)
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 // P0463R1 31 // https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0463r1.html 32 // P1272R4 33 // https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1272r4.html 34 // 35 // When using a standard library that implements these functions, we use the 36 // standard library's implementation. 37 38 #ifndef ABSL_NUMERIC_BITS_H_ 39 #define ABSL_NUMERIC_BITS_H_ 40 41 #include <cstdint> 42 #include <limits> 43 #include <type_traits> 44 45 #include "absl/base/config.h" 46 47 #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L 48 #include <bit> 49 #endif 50 51 #include "absl/base/attributes.h" 52 #include "absl/base/internal/endian.h" 53 #include "absl/numeric/internal/bits.h" 54 55 namespace absl { 56 ABSL_NAMESPACE_BEGIN 57 58 // https://github.com/llvm/llvm-project/issues/64544 59 // libc++ had the wrong signature for std::rotl and std::rotr 60 // prior to libc++ 18.0. 61 // 62 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) && \ 63 (!defined(_LIBCPP_VERSION) || _LIBCPP_VERSION >= 180000) 64 using std::rotl; 65 using std::rotr; 66 67 #else 68 69 // Rotating functions 70 template <class T> 71 [[nodiscard]] constexpr 72 typename std::enable_if<std::is_unsigned<T>::value, T>::type 73 rotl(T x, int s) noexcept { 74 return numeric_internal::RotateLeft(x, s); 75 } 76 77 template <class T> 78 [[nodiscard]] constexpr 79 typename std::enable_if<std::is_unsigned<T>::value, T>::type 80 rotr(T x, int s) noexcept { 81 return numeric_internal::RotateRight(x, s); 82 } 83 84 #endif 85 86 // https://github.com/llvm/llvm-project/issues/64544 87 // libc++ had the wrong signature for std::rotl and std::rotr 88 // prior to libc++ 18.0. 89 // 90 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) 91 92 using std::countl_one; 93 using std::countl_zero; 94 using std::countr_one; 95 using std::countr_zero; 96 using std::popcount; 97 98 #else 99 100 // Counting functions 101 // 102 // While these functions are typically constexpr, on some platforms, they may 103 // not be marked as constexpr due to constraints of the compiler/available 104 // intrinsics. 105 template <class T> 106 ABSL_INTERNAL_CONSTEXPR_CLZ inline 107 typename std::enable_if<std::is_unsigned<T>::value, int>::type 108 countl_zero(T x) noexcept { 109 return numeric_internal::CountLeadingZeroes(x); 110 } 111 112 template <class T> 113 ABSL_INTERNAL_CONSTEXPR_CLZ inline 114 typename std::enable_if<std::is_unsigned<T>::value, int>::type 115 countl_one(T x) noexcept { 116 // Avoid integer promotion to a wider type 117 return countl_zero(static_cast<T>(~x)); 118 } 119 120 template <class T> 121 ABSL_INTERNAL_CONSTEXPR_CTZ inline 122 typename std::enable_if<std::is_unsigned<T>::value, int>::type 123 countr_zero(T x) noexcept { 124 return numeric_internal::CountTrailingZeroes(x); 125 } 126 127 template <class T> 128 ABSL_INTERNAL_CONSTEXPR_CTZ inline 129 typename std::enable_if<std::is_unsigned<T>::value, int>::type 130 countr_one(T x) noexcept { 131 // Avoid integer promotion to a wider type 132 return countr_zero(static_cast<T>(~x)); 133 } 134 135 template <class T> 136 ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline 137 typename std::enable_if<std::is_unsigned<T>::value, int>::type 138 popcount(T x) noexcept { 139 return numeric_internal::Popcount(x); 140 } 141 142 #endif 143 144 #if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) 145 146 using std::bit_ceil; 147 using std::bit_floor; 148 using std::bit_width; 149 using std::has_single_bit; 150 151 #else 152 153 // Returns: true if x is an integral power of two; false otherwise. 154 template <class T> 155 constexpr inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type 156 has_single_bit(T x) noexcept { 157 return x != 0 && (x & (x - 1)) == 0; 158 } 159 160 // Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any 161 // fractional part discarded. 162 template <class T> 163 ABSL_INTERNAL_CONSTEXPR_CLZ inline 164 typename std::enable_if<std::is_unsigned<T>::value, int>::type 165 bit_width(T x) noexcept { 166 return std::numeric_limits<T>::digits - countl_zero(x); 167 } 168 169 // Returns: If x == 0, 0; otherwise the maximal value y such that 170 // has_single_bit(y) is true and y <= x. 171 template <class T> 172 ABSL_INTERNAL_CONSTEXPR_CLZ inline 173 typename std::enable_if<std::is_unsigned<T>::value, T>::type 174 bit_floor(T x) noexcept { 175 return x == 0 ? 0 : T{1} << (bit_width(x) - 1); 176 } 177 178 // Returns: N, where N is the smallest power of 2 greater than or equal to x. 179 // 180 // Preconditions: N is representable as a value of type T. 181 template <class T> 182 ABSL_INTERNAL_CONSTEXPR_CLZ inline 183 typename std::enable_if<std::is_unsigned<T>::value, T>::type 184 bit_ceil(T x) { 185 // If T is narrower than unsigned, T{1} << bit_width will be promoted. We 186 // want to force it to wraparound so that bit_ceil of an invalid value are not 187 // core constant expressions. 188 // 189 // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would 190 // undergo promotion to unsigned but not fit the result into T without 191 // truncation. 192 return has_single_bit(x) ? T{1} << (bit_width(x) - 1) 193 : numeric_internal::BitCeilNonPowerOf2(x); 194 } 195 196 #endif 197 198 #if defined(__cpp_lib_endian) && __cpp_lib_endian >= 201907L 199 200 // https://en.cppreference.com/w/cpp/types/endian 201 // 202 // Indicates the endianness of all scalar types: 203 // * If all scalar types are little-endian, `absl::endian::native` equals 204 // absl::endian::little. 205 // * If all scalar types are big-endian, `absl::endian::native` equals 206 // `absl::endian::big`. 207 // * Platforms that use anything else are unsupported. 208 using std::endian; 209 210 #else 211 212 enum class endian { 213 little, 214 big, 215 #if defined(ABSL_IS_LITTLE_ENDIAN) 216 native = little 217 #elif defined(ABSL_IS_BIG_ENDIAN) 218 native = big 219 #else 220 #error "Endian detection needs to be set up for this platform" 221 #endif 222 }; 223 224 #endif // defined(__cpp_lib_endian) && __cpp_lib_endian >= 201907L 225 226 #if defined(__cpp_lib_byteswap) && __cpp_lib_byteswap >= 202110L 227 228 // https://en.cppreference.com/w/cpp/numeric/byteswap 229 // 230 // Reverses the bytes in the given integer value `x`. 231 // 232 // `absl::byteswap` participates in overload resolution only if `T` satisfies 233 // integral, i.e., `T` is an integer type. The program is ill-formed if `T` has 234 // padding bits. 235 using std::byteswap; 236 237 #else 238 239 template <class T> 240 [[nodiscard]] constexpr T byteswap(T x) noexcept { 241 static_assert(std::is_integral_v<T>, 242 "byteswap requires an integral argument"); 243 static_assert( 244 sizeof(T) == 1 || sizeof(T) == 2 || sizeof(T) == 4 || sizeof(T) == 8, 245 "byteswap works only with 8, 16, 32, or 64-bit integers"); 246 if constexpr (sizeof(T) == 1) { 247 return x; 248 } else if constexpr (sizeof(T) == 2) { 249 return static_cast<T>(gbswap_16(static_cast<uint16_t>(x))); 250 } else if constexpr (sizeof(T) == 4) { 251 return static_cast<T>(gbswap_32(static_cast<uint32_t>(x))); 252 } else if constexpr (sizeof(T) == 8) { 253 return static_cast<T>(gbswap_64(static_cast<uint64_t>(x))); 254 } 255 } 256 257 #endif // defined(__cpp_lib_byteswap) && __cpp_lib_byteswap >= 202110L 258 259 ABSL_NAMESPACE_END 260 } // namespace absl 261 262 #endif // ABSL_NUMERIC_BITS_H_