[committed] libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978]
Jonathan Wakely
jwakely@redhat.com
Fri Aug 28 22:11:26 GMT 2020
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.
Tested powerpc64le-linux. Committed to trunk.
-------------- next part --------------
commit 82db1a42e9254c9009bbf8ac01366da4d1ab6df5
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Fri Aug 28 22:45:24 2020
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.
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<typename _Mn, typename _Nn>
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<remove_cv_t<_Mn>, bool>,
- "gcd arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, 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<common_type_t<_Mn, _Nn>>;
+ 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<remove_cv_t<_Mn>, bool>,
- "lcm arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, 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<common_type_t<_Mn, _Nn>>;
+ 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 <bits/c++config.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_numeric.h>
+#include <ext/numeric_traits.h>
#ifdef _GLIBCXX_PARALLEL
# include <parallel/numeric>
@@ -82,38 +83,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace __detail
{
- // std::abs is not constexpr and doesn't support unsigned integers.
- template<typename _Tp>
- constexpr
- enable_if_t<__and_<is_integral<_Tp>, is_signed<_Tp>>::value, _Tp>
- __abs_integral(_Tp __val)
- { return __val < 0 ? -__val : __val; }
-
- template<typename _Tp>
- constexpr
- enable_if_t<__and_<is_integral<_Tp>, is_unsigned<_Tp>>::value, _Tp>
- __abs_integral(_Tp __val)
- { return __val; }
-
- void __abs_integral(bool) = delete;
-
- template<typename _Mn, typename _Nn>
- constexpr common_type_t<_Mn, _Nn>
- __gcd(_Mn __m, _Nn __n)
+ // 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)
{
- return __m == 0 ? __detail::__abs_integral(__n)
- : __n == 0 ? __detail::__abs_integral(__m)
- : __detail::__gcd(__n, __m % __n);
+ 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;
}
- /// Least common multiple
- template<typename _Mn, typename _Nn>
- constexpr common_type_t<_Mn, _Nn>
- __lcm(_Mn __m, _Nn __n)
+ void __absu(bool) = delete;
+
+ // GCD implementation
+ template<typename _Tp>
+ constexpr _Tp
+ __gcd(_Tp __m, _Tp __n)
+ {
+ static_assert(is_unsigned<_Tp>::value, "type must be unsigned");
+ return __m == 0 ? __n
+ : __n == 0 ? __m
+ : __detail::__gcd(__n, _Tp(__m % __n));
+ }
+
+ // LCM implementation
+ template<typename _Tp>
+ 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<typename _Mn, typename _Nn>
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<remove_cv_t<_Mn>, bool>,
- "gcd arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, 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<common_type_t<_Mn, _Nn>>;
+ return __detail::__gcd(__detail::__absu<_Up>(__m),
+ __detail::__absu<_Up>(__n));
}
/// Least common multiple
template<typename _Mn, typename _Nn>
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<remove_cv_t<_Mn>, bool>,
- "lcm arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, 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<common_type_t<_Mn, _Nn>>;
+ 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do compile { target c++17 } }
+
+#include <numeric>
+#include <limits.h>
+
+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<const int&, const int&>(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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do compile { target c++17 } }
+
+#include <numeric>
+
+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<const int&, const int&>(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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do compile { target c++14 } }
+
+#include <experimental/numeric>
+#include <limits.h>
+
+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" );
+}
More information about the Libstdc++
mailing list