From patchwork Fri Aug 28 22:11:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1353548 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=r1iKLlWU; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BdYjK3fCfz9sTF for ; Sat, 29 Aug 2020 08:11:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 92EEF38708A9; Fri, 28 Aug 2020 22:11:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 92EEF38708A9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1598652698; bh=VjgKw2GLuTCBqsfelGSMF+grfbjGbk63w96d9eJoxeM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=r1iKLlWUaZMsMMffxygEsyZAztQKNDjsYBRh4/R26ufQqVEO9fIL81SzZtwwSZM7W lnv4Anf1nmip/Z8Igixj/rR0tMocB8U2Ke2AmHEUqZt1SbjB073fO4BT3lXpDh+xrr WBh92pAMxMKXq7bml4InVloqoNYcgAeb6gjNaNhg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id EAFB53851C2E for ; Fri, 28 Aug 2020 22:11:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org EAFB53851C2E Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-286-SeUsDssaO2C7ydqyNPqQBw-1; Fri, 28 Aug 2020 18:11:29 -0400 X-MC-Unique: SeUsDssaO2C7ydqyNPqQBw-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 3AE9A10066FB; Fri, 28 Aug 2020 22:11:28 +0000 (UTC) Received: from localhost (unknown [10.33.36.2]) by smtp.corp.redhat.com (Postfix) with ESMTP id B7683757D1; Fri, 28 Aug 2020 22:11:27 +0000 (UTC) Date: Fri, 28 Aug 2020 23:11:26 +0100 To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Fix std::gcd and std::lcm for unsigned integers [PR 92978] Message-ID: <20200828221126.GA1290141@redhat.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0.002 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-14.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jonathan Wakely via Gcc-patches From: Jonathan Wakely Reply-To: Jonathan Wakely Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" 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. commit 82db1a42e9254c9009bbf8ac01366da4d1ab6df5 Author: Jonathan Wakely 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 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; } - - void __abs_integral(bool) = delete; - - template - 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::min()) is undefined. + template + 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 - constexpr common_type_t<_Mn, _Nn> - __lcm(_Mn __m, _Nn __n) + void __absu(bool) = delete; + + // GCD implementation + template + 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 + 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" ); +}