1 //===-- Mimics llvm/Support/MathExtras.h ------------------------*- C++ -*-===// 2 // Provides useful math functions. 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H 11 #define LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H 12 13 #include "src/__support/CPP/bit.h" // countl_one, countr_zero 14 #include "src/__support/CPP/limits.h" // CHAR_BIT, numeric_limits 15 #include "src/__support/CPP/type_traits.h" // is_unsigned_v, is_constant_evaluated 16 #include "src/__support/macros/attributes.h" // LIBC_INLINE 17 #include "src/__support/macros/config.h" 18 19 namespace LIBC_NAMESPACE_DECL { 20 21 // Create a bitmask with the count right-most bits set to 1, and all other bits 22 // set to 0. Only unsigned types are allowed. 23 template <typename T, size_t count> 24 LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 25 mask_trailing_ones() { 26 constexpr unsigned T_BITS = CHAR_BIT * sizeof(T); 27 static_assert(count <= T_BITS && "Invalid bit index"); 28 return count == 0 ? 0 : (T(-1) >> (T_BITS - count)); 29 } 30 31 // Create a bitmask with the count left-most bits set to 1, and all other bits 32 // set to 0. Only unsigned types are allowed. 33 template <typename T, size_t count> 34 LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 35 mask_leading_ones() { 36 return T(~mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>()); 37 } 38 39 // Create a bitmask with the count right-most bits set to 0, and all other bits 40 // set to 1. Only unsigned types are allowed. 41 template <typename T, size_t count> 42 LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 43 mask_trailing_zeros() { 44 return mask_leading_ones<T, CHAR_BIT * sizeof(T) - count>(); 45 } 46 47 // Create a bitmask with the count left-most bits set to 0, and all other bits 48 // set to 1. Only unsigned types are allowed. 49 template <typename T, size_t count> 50 LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 51 mask_leading_zeros() { 52 return mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>(); 53 } 54 55 // Returns whether 'a + b' overflows, the result is stored in 'res'. 56 template <typename T> 57 [[nodiscard]] LIBC_INLINE constexpr bool add_overflow(T a, T b, T &res) { 58 return __builtin_add_overflow(a, b, &res); 59 } 60 61 // Returns whether 'a - b' overflows, the result is stored in 'res'. 62 template <typename T> 63 [[nodiscard]] LIBC_INLINE constexpr bool sub_overflow(T a, T b, T &res) { 64 return __builtin_sub_overflow(a, b, &res); 65 } 66 67 #define RETURN_IF(TYPE, BUILTIN) \ 68 if constexpr (cpp::is_same_v<T, TYPE>) \ 69 return BUILTIN(a, b, carry_in, carry_out); 70 71 // Returns the result of 'a + b' taking into account 'carry_in'. 72 // The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise. 73 // We keep the pass by pointer interface for consistency with the intrinsic. 74 template <typename T> 75 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 76 add_with_carry(T a, T b, T carry_in, T &carry_out) { 77 if constexpr (!cpp::is_constant_evaluated()) { 78 #if __has_builtin(__builtin_addcb) 79 RETURN_IF(unsigned char, __builtin_addcb) 80 #elif __has_builtin(__builtin_addcs) 81 RETURN_IF(unsigned short, __builtin_addcs) 82 #elif __has_builtin(__builtin_addc) 83 RETURN_IF(unsigned int, __builtin_addc) 84 #elif __has_builtin(__builtin_addcl) 85 RETURN_IF(unsigned long, __builtin_addcl) 86 #elif __has_builtin(__builtin_addcll) 87 RETURN_IF(unsigned long long, __builtin_addcll) 88 #endif 89 } 90 T sum = {}; 91 T carry1 = add_overflow(a, b, sum); 92 T carry2 = add_overflow(sum, carry_in, sum); 93 carry_out = carry1 | carry2; 94 return sum; 95 } 96 97 // Returns the result of 'a - b' taking into account 'carry_in'. 98 // The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise. 99 // We keep the pass by pointer interface for consistency with the intrinsic. 100 template <typename T> 101 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T> 102 sub_with_borrow(T a, T b, T carry_in, T &carry_out) { 103 if constexpr (!cpp::is_constant_evaluated()) { 104 #if __has_builtin(__builtin_subcb) 105 RETURN_IF(unsigned char, __builtin_subcb) 106 #elif __has_builtin(__builtin_subcs) 107 RETURN_IF(unsigned short, __builtin_subcs) 108 #elif __has_builtin(__builtin_subc) 109 RETURN_IF(unsigned int, __builtin_subc) 110 #elif __has_builtin(__builtin_subcl) 111 RETURN_IF(unsigned long, __builtin_subcl) 112 #elif __has_builtin(__builtin_subcll) 113 RETURN_IF(unsigned long long, __builtin_subcll) 114 #endif 115 } 116 T sub = {}; 117 T carry1 = sub_overflow(a, b, sub); 118 T carry2 = sub_overflow(sub, carry_in, sub); 119 carry_out = carry1 | carry2; 120 return sub; 121 } 122 123 #undef RETURN_IF 124 125 template <typename T> 126 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> 127 first_leading_zero(T value) { 128 return value == cpp::numeric_limits<T>::max() ? 0 129 : cpp::countl_one(value) + 1; 130 } 131 132 template <typename T> 133 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> 134 first_leading_one(T value) { 135 return first_leading_zero(static_cast<T>(~value)); 136 } 137 138 template <typename T> 139 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> 140 first_trailing_zero(T value) { 141 return value == cpp::numeric_limits<T>::max() 142 ? 0 143 : cpp::countr_zero(static_cast<T>(~value)) + 1; 144 } 145 146 template <typename T> 147 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> 148 first_trailing_one(T value) { 149 return value == cpp::numeric_limits<T>::max() ? 0 150 : cpp::countr_zero(value) + 1; 151 } 152 153 template <typename T> 154 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int> 155 count_zeros(T value) { 156 return cpp::popcount<T>(static_cast<T>(~value)); 157 } 158 159 } // namespace LIBC_NAMESPACE_DECL 160 161 #endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H 162