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.

1 files changed, 42 insertions, 41 deletions

diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index 57dcac6..8f2ed5c 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; }
+  // 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)
+    {
+      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<typename _Mn, typename _Nn>
-    constexpr common_type_t<_Mn, _Nn>
-    __gcd(_Mn __m, _Nn __n)
+  // GCD implementation
+  template<typename _Tp>
+    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<typename _Mn, typename _Nn>
-    constexpr common_type_t<_Mn, _Nn>
-    __lcm(_Mn __m, _Nn __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