diff options
-rw-r--r-- | libstdc++-v3/include/experimental/numeric | 46 | ||||
-rw-r--r-- | libstdc++-v3/include/std/numeric | 75 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/26_numerics/gcd/105844.cc | 21 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc | 10 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/26_numerics/lcm/105844.cc | 22 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc | 10 |
6 files changed, 123 insertions, 61 deletions
diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric index 4c6a662fdd6..426d9430dd6 100644 --- a/libstdc++-v3/include/experimental/numeric +++ b/libstdc++-v3/include/experimental/numeric @@ -56,17 +56,15 @@ inline namespace fundamentals_v2 constexpr common_type_t<_Mn, _Nn> gcd(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, - "std::experimental::gcd arguments must be integers"); - static_assert(is_integral_v<_Nn>, - "std::experimental::gcd arguments must be integers"); - static_assert(_Mn(2) != _Mn(1), - "std::experimental::gcd arguments must not be bool"); - static_assert(_Nn(2) != _Nn(1), - "std::experimental::gcd arguments must not be bool"); - using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; - return std::__detail::__gcd(std::__detail::__absu<_Up>(__m), - std::__detail::__absu<_Up>(__n)); + static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>, + "std::experimental::gcd arguments must be integers"); + static_assert(_Mn(2) == 2 && _Nn(2) == 2, + "std::experimental::gcd arguments must not be bool"); + namespace __detail = std::__detail; + using _Ct = common_type_t<_Mn, _Nn>; + const _Ct __m2 = __detail::__abs_r<_Ct>(__m); + const _Ct __n2 = __detail::__abs_r<_Ct>(__n); + return __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2); } /// Least common multiple @@ -74,17 +72,25 @@ inline namespace fundamentals_v2 constexpr common_type_t<_Mn, _Nn> lcm(_Mn __m, _Nn __n) { - static_assert(is_integral_v<_Mn>, + static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>, "std::experimental::lcm arguments must be integers"); - static_assert(is_integral_v<_Nn>, - "std::experimental::lcm arguments must be integers"); - static_assert(_Mn(2) != _Mn(1), - "std::experimental::lcm arguments must not be bool"); - static_assert(_Nn(2) != _Nn(1), + static_assert(_Mn(2) == 2 && _Nn(2) == 2, "std::experimental::lcm arguments must not be bool"); - using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; - return std::__detail::__lcm(std::__detail::__absu<_Up>(__m), - std::__detail::__absu<_Up>(__n)); + namespace __detail = std::__detail; + using _Ct = common_type_t<_Mn, _Nn>; + const _Ct __m2 = __detail::__abs_r<_Ct>(__m); + const _Ct __n2 = __detail::__abs_r<_Ct>(__n); + if (__m2 == 0 || __n2 == 0) + return 0; + _Ct __r = __m2 / __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2); + + if _GLIBCXX17_CONSTEXPR (is_signed_v<_Ct>) + if (__is_constant_evaluated()) + return __r * __n2; // constant evaluation can detect overflow here. + + bool __overflow = __builtin_mul_overflow(__r, __n2, &__r); + __glibcxx_assert(!__overflow); + return __r; } } // namespace fundamentals_v2 } // namespace experimental diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric index 5388239ef04..60a99d18ffd 100644 --- a/libstdc++-v3/include/std/numeric +++ b/libstdc++-v3/include/std/numeric @@ -68,6 +68,7 @@ #if __cplusplus >= 201402L # include <type_traits> # include <bit> +# include <ext/numeric_traits.h> #endif #if __cplusplus >= 201703L @@ -93,19 +94,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus >= 201402L namespace __detail { - // std::abs is not constexpr, doesn't support unsigned integers, - // and std::abs(std::numeric_limits<T>::min()) is undefined. - template<typename _Up, typename _Tp> - constexpr _Up - __absu(_Tp __val) + // Like std::abs, but supports unsigned types and returns the specified type, + // so |std::numeric_limits<_Tp>::min()| is OK if representable in _Res. + template<typename _Res, typename _Tp> + constexpr _Res + __abs_r(_Tp __val) { - static_assert(is_unsigned<_Up>::value, "result type must be unsigned"); - static_assert(sizeof(_Up) >= sizeof(_Tp), + static_assert(sizeof(_Res) >= sizeof(_Tp), "result type must be at least as wide as the input type"); - return __val < 0 ? -(_Up)__val : (_Up)__val; + + if (__val >= 0) + return __val; +#ifdef _GLIBCXX_ASSERTIONS + if (!__is_constant_evaluated()) // overflow already detected in constexpr + __glibcxx_assert(__val != __gnu_cxx::__int_traits<_Res>::__min); +#endif + return -static_cast<_Res>(__val); } - template<typename _Up> void __absu(bool) = delete; + template<typename> void __abs_r(bool) = delete; // GCD implementation, using Stein's algorithm template<typename _Tp> @@ -142,16 +149,6 @@ namespace __detail __n >>= std::__countr_zero(__n); } } - - // LCM implementation - template<typename _Tp> - constexpr _Tp - __lcm(_Tp __m, _Tp __n) - { - return (__m != 0 && __n != 0) - ? (__m / __detail::__gcd(__m, __n)) * __n - : 0; - } } // namespace __detail #if __cplusplus >= 201703L @@ -166,13 +163,14 @@ namespace __detail constexpr common_type_t<_Mn, _Nn> gcd(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, "std::gcd arguments must be integers"); - static_assert(is_integral_v<_Nn>, "std::gcd arguments must be integers"); - static_assert(_Mn(2) != _Mn(1), "std::gcd arguments must not be bool"); - static_assert(_Nn(2) != _Nn(1), "std::gcd arguments must not be bool"); - using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; - return __detail::__gcd(__detail::__absu<_Up>(__m), - __detail::__absu<_Up>(__n)); + static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>, + "std::gcd arguments must be integers"); + static_assert(_Mn(2) == 2 && _Nn(2) == 2, + "std::gcd arguments must not be bool"); + using _Ct = common_type_t<_Mn, _Nn>; + const _Ct __m2 = __detail::__abs_r<_Ct>(__m); + const _Ct __n2 = __detail::__abs_r<_Ct>(__n); + return __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2); } /// Least common multiple @@ -180,13 +178,24 @@ namespace __detail constexpr common_type_t<_Mn, _Nn> lcm(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integers"); - static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integers"); - static_assert(_Mn(2) == 2, "std::lcm arguments must not be bool"); - static_assert(_Nn(2) == 2, "std::lcm arguments must not be bool"); - using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; - return __detail::__lcm(__detail::__absu<_Up>(__m), - __detail::__absu<_Up>(__n)); + static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>, + "std::lcm arguments must be integers"); + static_assert(_Mn(2) == 2 && _Nn(2) == 2, + "std::lcm arguments must not be bool"); + using _Ct = common_type_t<_Mn, _Nn>; + const _Ct __m2 = __detail::__abs_r<_Ct>(__m); + const _Ct __n2 = __detail::__abs_r<_Ct>(__n); + if (__m2 == 0 || __n2 == 0) + return 0; + _Ct __r = __m2 / __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2); + + if constexpr (is_signed_v<_Ct>) + if (__is_constant_evaluated()) + return __r * __n2; // constant evaluation can detect overflow here. + + bool __overflow = __builtin_mul_overflow(__r, __n2, &__r); + __glibcxx_assert(!__overflow); + return __r; } #endif // C++17 diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc b/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc new file mode 100644 index 00000000000..5b6fea7b560 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/gcd/105844.cc @@ -0,0 +1,21 @@ +// { dg-do compile { target c++17 } } +#include <numeric> +#include <climits> + +// PR libstdc++/105844 + +// |INT_MIN| can be represented in common_type_t<int, unsigned> i.e. unsigned. +static_assert( std::gcd(INT_MIN, 2u) == 2 ); +static_assert( std::gcd(2u, INT_MIN) == 2 ); + +// |LLONG_MIN| can be represented in unsigned long long. +static_assert( std::gcd(LLONG_MIN, 2ull) == 2 ); +static_assert( std::gcd(2ull, LLONG_MIN) == 2 ); + +// But |INT_MIN| cannot be represented in common_type<int, int> i.e. int. +constexpr int a = std::gcd(INT_MIN, 1); // { dg-error "overflow" } +constexpr int b = std::gcd(1, INT_MIN); // { dg-error "overflow" } + +// And |LLONG_MIN| cannot be represented in long. +constexpr long long c = std::gcd(LLONG_MIN, 1); // { dg-error "overflow" } +constexpr long long d = std::gcd(1, LLONG_MIN); // { dg-error "overflow" } diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc index c9faeebc269..e5d03a9a453 100644 --- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc @@ -45,9 +45,11 @@ test01() std::gcd<const int&, const int&>(0.1, 0.1); // { dg-error "from here" } } -// { dg-error "must be integers" "" { target *-*-* } 169 } -// { dg-error "must be integers" "" { target *-*-* } 170 } -// { dg-error "must not be bool" "" { target *-*-* } 171 } -// { dg-error "must not be bool" "" { target *-*-* } 172 } +// { dg-error "must be integers" "" { target *-*-* } 0 } +// { dg-error "must not be bool" "" { target *-*-* } 0 } +// These prunes could be removed if a fix for PR c++/96286 stops them. // { dg-prune-output "deleted function" } // { dg-prune-output "incomplete type .*make_unsigned" } +// { dg-prune-output "does not have integral type" } +// { dg-prune-output "non-integral type" } +// { dg-prune-output "invalid specialization" } diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc b/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc new file mode 100644 index 00000000000..d0e032e03e0 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/lcm/105844.cc @@ -0,0 +1,22 @@ +// { dg-do compile { target c++17 } } +#include <numeric> +#include <climits> + +// PR libstdc++/105844 + +// |INT_MIN| can be represented in common_type_t<int, unsigned> i.e. unsigned. +static_assert( std::lcm(INT_MIN, 1u) == INT_MAX+1u ); +static_assert( std::lcm(1u, INT_MIN) == INT_MAX+1u ); + +// But |INT_MIN| cannot be represented in common_type<int, int> i.e. int. +constexpr int a = std::lcm(INT_MIN, 1); // { dg-error "overflow" } +constexpr int b = std::lcm(1, INT_MIN); // { dg-error "overflow" } + +// And the LCM of 50000 and 49999 cannot be represented in int. +constexpr int c = std::lcm(50000, 49999); // { dg-error "overflow" } +constexpr int d = std::lcm(49999, 50000); // { dg-error "overflow" } + +// Similarly for unsigned, but the diagnostic is a failed assertion instead. +constexpr int e = std::lcm(500000u, 499999); // { dg-error "in 'constexpr'" } +constexpr int f = std::lcm(499999u, 500000); // { dg-error "in 'constexpr'" } +// { dg-error "unreachable" "" { target *-*-* } 0 } diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc index 6c3c9d0c02a..77cb974aab4 100644 --- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc @@ -45,9 +45,11 @@ test01() std::lcm<const int&, const int&>(0.1, 0.1); // { dg-error "from here" } } -// { dg-error "must be integers" "" { target *-*-* } 183 } -// { dg-error "must be integers" "" { target *-*-* } 184 } -// { dg-error "must not be bool" "" { target *-*-* } 185 } -// { dg-error "must not be bool" "" { target *-*-* } 186 } +// { dg-error "must be integers" "" { target *-*-* } 0 } +// { dg-error "must not be bool" "" { target *-*-* } 0 } +// These prunes could be removed if a fix for PR c++/96286 stops them. // { dg-prune-output "deleted function" } // { dg-prune-output "incomplete type .*make_unsigned" } +// { dg-prune-output "does not have integral type" } +// { dg-prune-output "non-integral type" } +// { dg-prune-output "invalid specialization" } |