177 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H11#define LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H12 13#include "src/__support/CPP/bit.h" // countl_one, countr_zero14#include "src/__support/CPP/limits.h" // CHAR_BIT, numeric_limits15#include "src/__support/CPP/type_traits.h" // is_unsigned_v, is_constant_evaluated16#include "src/__support/macros/attributes.h" // LIBC_INLINE17#include "src/__support/macros/config.h"18 19namespace LIBC_NAMESPACE_DECL {20 21// Create a bitmask with the count right-most bits set to 1, and all other bits22// set to 0. Only unsigned types are allowed.23template <typename T, size_t count>24LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>25mask_trailing_ones() {26 constexpr unsigned T_BITS = CHAR_BIT * sizeof(T);27 static_assert(count <= T_BITS && "Invalid bit index");28 // MSVC complains about out of range shifts.29 if constexpr (count == 0)30 return 0;31 else if constexpr (count >= T_BITS)32 return T(-1);33 else34 return T(-1) >> (T_BITS - count);35}36 37// Create a bitmask with the count left-most bits set to 1, and all other bits38// set to 0. Only unsigned types are allowed.39template <typename T, size_t count>40LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>41mask_leading_ones() {42 return T(~mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>());43}44 45// Create a bitmask with the count right-most bits set to 0, and all other bits46// set to 1. Only unsigned types are allowed.47template <typename T, size_t count>48LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>49mask_trailing_zeros() {50 return mask_leading_ones<T, CHAR_BIT * sizeof(T) - count>();51}52 53// Create a bitmask with the count left-most bits set to 0, and all other bits54// set to 1. Only unsigned types are allowed.55template <typename T, size_t count>56LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>57mask_leading_zeros() {58 return mask_trailing_ones<T, CHAR_BIT * sizeof(T) - count>();59}60 61// Returns whether 'a + b' overflows, the result is stored in 'res'.62template <typename T>63[[nodiscard]] LIBC_INLINE constexpr bool add_overflow(T a, T b, T &res) {64#if __has_builtin(__builtin_add_overflow)65 return __builtin_add_overflow(a, b, &res);66#else67 res = a + b;68 return (res < a) || (res < b);69#endif // __builtin_add_overflow70}71 72// Returns whether 'a - b' overflows, the result is stored in 'res'.73template <typename T>74[[nodiscard]] LIBC_INLINE constexpr bool sub_overflow(T a, T b, T &res) {75#if __has_builtin(__builtin_sub_overflow)76 return __builtin_sub_overflow(a, b, &res);77#else78 res = a - b;79 return (res > a);80#endif // __builtin_sub_overflow81}82 83#define RETURN_IF(TYPE, BUILTIN) \84 if constexpr (cpp::is_same_v<T, TYPE>) \85 return BUILTIN(a, b, carry_in, &carry_out);86 87// Returns the result of 'a + b' taking into account 'carry_in'.88// The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise.89// We keep the pass by pointer interface for consistency with the intrinsic.90template <typename T>91[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>92add_with_carry(T a, T b, T carry_in, T &carry_out) {93 if (!cpp::is_constant_evaluated()) {94#if __has_builtin(__builtin_addcb)95 RETURN_IF(unsigned char, __builtin_addcb)96#elif __has_builtin(__builtin_addcs)97 RETURN_IF(unsigned short, __builtin_addcs)98#elif __has_builtin(__builtin_addc)99 RETURN_IF(unsigned int, __builtin_addc)100#elif __has_builtin(__builtin_addcl)101 RETURN_IF(unsigned long, __builtin_addcl)102#elif __has_builtin(__builtin_addcll)103 RETURN_IF(unsigned long long, __builtin_addcll)104#endif105 }106 T sum = {};107 T carry1 = add_overflow(a, b, sum);108 T carry2 = add_overflow(sum, carry_in, sum);109 carry_out = carry1 | carry2;110 return sum;111}112 113// Returns the result of 'a - b' taking into account 'carry_in'.114// The carry out is stored in 'carry_out' it not 'nullptr', dropped otherwise.115// We keep the pass by pointer interface for consistency with the intrinsic.116template <typename T>117[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>118sub_with_borrow(T a, T b, T carry_in, T &carry_out) {119 if (!cpp::is_constant_evaluated()) {120#if __has_builtin(__builtin_subcb)121 RETURN_IF(unsigned char, __builtin_subcb)122#elif __has_builtin(__builtin_subcs)123 RETURN_IF(unsigned short, __builtin_subcs)124#elif __has_builtin(__builtin_subc)125 RETURN_IF(unsigned int, __builtin_subc)126#elif __has_builtin(__builtin_subcl)127 RETURN_IF(unsigned long, __builtin_subcl)128#elif __has_builtin(__builtin_subcll)129 RETURN_IF(unsigned long long, __builtin_subcll)130#endif131 }132 T sub = {};133 T carry1 = sub_overflow(a, b, sub);134 T carry2 = sub_overflow(sub, carry_in, sub);135 carry_out = carry1 | carry2;136 return sub;137}138 139#undef RETURN_IF140 141template <typename T>142[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>143first_leading_zero(T value) {144 return value == cpp::numeric_limits<T>::max() ? 0145 : cpp::countl_one(value) + 1;146}147 148template <typename T>149[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>150first_leading_one(T value) {151 return first_leading_zero(static_cast<T>(~value));152}153 154template <typename T>155[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>156first_trailing_zero(T value) {157 return value == cpp::numeric_limits<T>::max()158 ? 0159 : cpp::countr_zero(static_cast<T>(~value)) + 1;160}161 162template <typename T>163[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>164first_trailing_one(T value) {165 return value == 0 ? 0 : cpp::countr_zero(value) + 1;166}167 168template <typename T>169[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>170count_zeros(T value) {171 return cpp::popcount<T>(static_cast<T>(~value));172}173 174} // namespace LIBC_NAMESPACE_DECL175 176#endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXTRAS_H177