libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978]
authorJonathan Wakely <jwakely@redhat.com>
Fri, 28 Aug 2020 21:45:24 +0000 (22:45 +0100)
committerJonathan Wakely <jwakely@redhat.com>
Fri, 28 Aug 2020 22:03:28 +0000 (23:03 +0100)
commit82db1a42e9254c9009bbf8ac01366da4d1ab6df5
tree8888e703096458531a7c9060fe8285f5a89db2a9
parentd14c547abd484d3540b692bb8048c4a6efe92c8b
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
libstdc++-v3/include/std/numeric
libstdc++-v3/testsuite/26_numerics/gcd/92978.cc [new file with mode: 0644]
libstdc++-v3/testsuite/26_numerics/gcd/gcd_neg.cc
libstdc++-v3/testsuite/26_numerics/lcm/92978.cc [new file with mode: 0644]
libstdc++-v3/testsuite/26_numerics/lcm/lcm_neg.cc
libstdc++-v3/testsuite/experimental/numeric/92978.cc [new file with mode: 0644]