From 82db1a42e9254c9009bbf8ac01366da4d1ab6df5 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Fri, 28 Aug 2020 22:45:24 +0100 Subject: [PATCH] libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978] This fixes a bug with mixed signed and unsigned types, where converting a negative value to the unsigned result type alters the value. The solution is to obtain the absolute values of the arguments immediately and to perform the actual GCD or LCM algorithm on two arguments of the same type. In order to operate on the most negative number without overflow when taking its absolute, use an unsigned type for the result of the abs operation. For example, -INT_MIN will overflow, but -(unsigned)INT_MIN is (unsigned)INT_MAX+1U which is the correct value. libstdc++-v3/ChangeLog: PR libstdc++/92978 * include/std/numeric (__abs_integral): Replace with ... (__detail::__absu): New function template that returns an unsigned type, guaranteeing it can represent the most negative signed value. (__detail::__gcd, __detail::__lcm): Require arguments to be unsigned and therefore already non-negative. (gcd, lcm): Convert arguments to absolute value as unsigned type before calling __detail::__gcd or __detail::__lcm. * include/experimental/numeric (gcd, lcm): Likewise. * testsuite/26_numerics/gcd/gcd_neg.cc: Adjust expected errors. * testsuite/26_numerics/lcm/lcm_neg.cc: Likewise. * testsuite/26_numerics/gcd/92978.cc: New test. * testsuite/26_numerics/lcm/92978.cc: New test. * testsuite/experimental/numeric/92978.cc: New test. --- libstdc++-v3/include/experimental/numeric | 38 +++++---- libstdc++-v3/include/std/numeric | 83 ++++++++++--------- .../testsuite/26_numerics/gcd/92978.cc | 40 +++++++++ .../testsuite/26_numerics/gcd/gcd_neg.cc | 11 ++- .../testsuite/26_numerics/lcm/92978.cc | 27 ++++++ .../testsuite/26_numerics/lcm/lcm_neg.cc | 11 ++- .../testsuite/experimental/numeric/92978.cc | 48 +++++++++++ 7 files changed, 190 insertions(+), 68 deletions(-) create mode 100644 libstdc++-v3/testsuite/26_numerics/gcd/92978.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/lcm/92978.cc create mode 100644 libstdc++-v3/testsuite/experimental/numeric/92978.cc diff --git a/libstdc++-v3/include/experimental/numeric b/libstdc++-v3/include/experimental/numeric index d8a904a7057..4154e535a94 100644 --- a/libstdc++-v3/include/experimental/numeric +++ b/libstdc++-v3/include/experimental/numeric @@ -54,15 +54,19 @@ inline namespace fundamentals_v2 /// Greatest common divisor template constexpr common_type_t<_Mn, _Nn> - gcd(_Mn __m, _Nn __n) + gcd(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, "gcd arguments are integers"); - static_assert(is_integral_v<_Nn>, "gcd arguments are integers"); - static_assert(!is_same_v, bool>, - "gcd arguments are not bools"); - static_assert(!is_same_v, bool>, - "gcd arguments are not bools"); - return std::__detail::__gcd(__m, __n); + 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>; + return std::__detail::__gcd(std::__detail::__absu<_Up>(__m), + std::__detail::__absu<_Up>(__n)); } /// Least common multiple @@ -70,13 +74,17 @@ inline namespace fundamentals_v2 constexpr common_type_t<_Mn, _Nn> lcm(_Mn __m, _Nn __n) { - static_assert(is_integral_v<_Mn>, "lcm arguments are integers"); - static_assert(is_integral_v<_Nn>, "lcm arguments are integers"); - static_assert(!is_same_v, bool>, - "lcm arguments are not bools"); - static_assert(!is_same_v, bool>, - "lcm arguments are not bools"); - return std::__detail::__lcm(__m, __n); + static_assert(is_integral_v<_Mn>, + "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), + "std::experimental::lcm arguments must not be bool"); + using _Up = make_unsigned_t>; + return std::__detail::__lcm(std::__detail::__absu<_Up>(__m), + std::__detail::__absu<_Up>(__n)); } } // namespace fundamentals_v2 } // namespace experimental diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric index 57dcac6d215..8f2ed5c6a5e 100644 --- a/libstdc++-v3/include/std/numeric +++ b/libstdc++-v3/include/std/numeric @@ -60,6 +60,7 @@ #include #include #include +#include #ifdef _GLIBCXX_PARALLEL # include @@ -82,38 +83,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace __detail { - // std::abs is not constexpr and doesn't support unsigned integers. - template - constexpr - enable_if_t<__and_, is_signed<_Tp>>::value, _Tp> - __abs_integral(_Tp __val) - { return __val < 0 ? -__val : __val; } - - template - constexpr - enable_if_t<__and_, is_unsigned<_Tp>>::value, _Tp> - __abs_integral(_Tp __val) - { return __val; } + // std::abs is not constexpr, doesn't support unsigned integers, + // and std::abs(std::numeric_limits::min()) is undefined. + template + constexpr _Up + __absu(_Tp __val) + { + static_assert(is_unsigned<_Up>::value, "result type must be unsigned"); + static_assert(sizeof(_Up) >= sizeof(_Tp), + "result type must be at least as wide as the input type"); + return __val < 0 ? -(_Up)__val : (_Up)__val; + } - void __abs_integral(bool) = delete; + void __absu(bool) = delete; - template - constexpr common_type_t<_Mn, _Nn> - __gcd(_Mn __m, _Nn __n) + // GCD implementation + template + constexpr _Tp + __gcd(_Tp __m, _Tp __n) { - return __m == 0 ? __detail::__abs_integral(__n) - : __n == 0 ? __detail::__abs_integral(__m) - : __detail::__gcd(__n, __m % __n); + static_assert(is_unsigned<_Tp>::value, "type must be unsigned"); + return __m == 0 ? __n + : __n == 0 ? __m + : __detail::__gcd(__n, _Tp(__m % __n)); } - /// Least common multiple - template - constexpr common_type_t<_Mn, _Nn> - __lcm(_Mn __m, _Nn __n) + // LCM implementation + template + constexpr _Tp + __lcm(_Tp __m, _Tp __n) { return (__m != 0 && __n != 0) - ? (__detail::__abs_integral(__m) / __detail::__gcd(__m, __n)) - * __detail::__abs_integral(__n) + ? (__m / __detail::__gcd(__m, __n)) * __n : 0; } } // namespace __detail @@ -128,29 +129,29 @@ namespace __detail /// Greatest common divisor template constexpr common_type_t<_Mn, _Nn> - gcd(_Mn __m, _Nn __n) + gcd(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, "gcd arguments are integers"); - static_assert(is_integral_v<_Nn>, "gcd arguments are integers"); - static_assert(!is_same_v, bool>, - "gcd arguments are not bools"); - static_assert(!is_same_v, bool>, - "gcd arguments are not bools"); - return __detail::__gcd(__m, __n); + 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>; + return __detail::__gcd(__detail::__absu<_Up>(__m), + __detail::__absu<_Up>(__n)); } /// Least common multiple template constexpr common_type_t<_Mn, _Nn> - lcm(_Mn __m, _Nn __n) + lcm(_Mn __m, _Nn __n) noexcept { - static_assert(is_integral_v<_Mn>, "lcm arguments are integers"); - static_assert(is_integral_v<_Nn>, "lcm arguments are integers"); - static_assert(!is_same_v, bool>, - "lcm arguments are not bools"); - static_assert(!is_same_v, bool>, - "lcm arguments are not bools"); - return __detail::__lcm(__m, __n); + 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>; + return __detail::__lcm(__detail::__absu<_Up>(__m), + __detail::__absu<_Up>(__n)); } #endif // C++17 diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc b/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc new file mode 100644 index 00000000000..0ae1d3bb6c4 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/gcd/92978.cc @@ -0,0 +1,40 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do compile { target c++17 } } + +#include +#include + +void +test01() +{ + // PR libstdc++/92978 + static_assert( std::gcd(-120, 10U) == 10 ); + static_assert( std::gcd(120U, -10) == 10 ); +} + +void +test02() +{ + // |INT_MIN| should not be undefined, as long as it fits in the result type. + static_assert( std::gcd(INT_MIN, 0LL) == 1LL+INT_MAX ); + static_assert( std::gcd(0LL, INT_MIN) == 1LL+INT_MAX ); + static_assert( std::gcd(INT_MIN, 0LL + INT_MIN) == 1LL + INT_MAX ); + static_assert( std::gcd(INT_MIN, 1LL + INT_MAX) == 1LL + INT_MAX ); + static_assert( std::gcd(SHRT_MIN, 1U + SHRT_MAX) == 1U + SHRT_MAX ); +} diff --git a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc index fe0dd9a6503..707148a2670 100644 --- a/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc @@ -46,9 +46,8 @@ test01() std::gcd(0.1, 0.1); // { dg-error "from here" } } -// { dg-error "integers" "" { target *-*-* } 133 } -// { dg-error "integers" "" { target *-*-* } 134 } -// { dg-error "not bools" "" { target *-*-* } 135 } -// { dg-error "not bools" "" { target *-*-* } 137 } -// { dg-prune-output "deleted function" } -// { dg-prune-output "invalid operands" } +// { dg-error "must be integers" "" { target *-*-* } 134 } +// { dg-error "must be integers" "" { target *-*-* } 135 } +// { dg-error "must not be bool" "" { target *-*-* } 136 } +// { dg-error "must not be bool" "" { target *-*-* } 137 } +// { dg-prune-output "incomplete type .*make_unsigned" } diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc b/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc new file mode 100644 index 00000000000..0a016c34d43 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/lcm/92978.cc @@ -0,0 +1,27 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do compile { target c++17 } } + +#include + +void +test01() +{ + // PR libstdc++/92978 + static_assert( std::lcm(-42, 21U) == 42U ); +} diff --git a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc index c9d95d80c12..d4aa6b59da8 100644 --- a/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc @@ -46,9 +46,8 @@ test01() std::lcm(0.1, 0.1); // { dg-error "from here" } } -// { dg-error "integers" "" { target *-*-* } 147 } -// { dg-error "integers" "" { target *-*-* } 148 } -// { dg-error "not bools" "" { target *-*-* } 149 } -// { dg-error "not bools" "" { target *-*-* } 151 } -// { dg-prune-output "deleted function" } -// { dg-prune-output "invalid operands" } +// { dg-error "must be integers" "" { target *-*-* } 148 } +// { dg-error "must be integers" "" { target *-*-* } 149 } +// { dg-error "must not be bool" "" { target *-*-* } 150 } +// { dg-error "must not be bool" "" { target *-*-* } 151 } +// { dg-prune-output "incomplete type .*make_unsigned" } diff --git a/libstdc++-v3/testsuite/experimental/numeric/92978.cc b/libstdc++-v3/testsuite/experimental/numeric/92978.cc new file mode 100644 index 00000000000..8408fd4d9ce --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/numeric/92978.cc @@ -0,0 +1,48 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do compile { target c++14 } } + +#include +#include + +void +test01() +{ + // PR libstdc++/92978 + static_assert( std::experimental::gcd(-120, 10U) == 10, + "mixed signed/unsigned" ); + static_assert( std::experimental::gcd(120U, -10) == 10, + "mixed signed/unsigned" ); + + static_assert( std::lcm(-42, 21U) == 42U ); +} + +void +test02() +{ + static_assert( std::experimental::gcd(INT_MIN, 0LL) == 1LL+INT_MAX, + "|INT_MIN| should not be undefined as long as it fits in the result" ); + static_assert( std::experimental::gcd(0LL, INT_MIN) == 1LL+INT_MAX, + "|INT_MIN| should not be undefined" ); + static_assert( std::experimental::gcd(INT_MIN, 0LL + INT_MIN) == 1LL + INT_MAX, + "|INT_MIN| should not be undefined" ); + static_assert( std::experimental::gcd(INT_MIN, 1LL + INT_MAX) == 1LL + INT_MAX, + "|INT_MIN| should not be undefined" ); + static_assert( std::experimental::gcd(SHRT_MIN, 1U + SHRT_MAX) == 1U + SHRT_MAX, + "|SHRT_MIN| should not be undefined" ); +} -- 2.30.2