From patchwork Wed May 4 23:30:50 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Carlini X-Patchwork-Id: 94187 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 6F96F1007DB for ; Thu, 5 May 2011 09:31:53 +1000 (EST) Received: (qmail 22001 invoked by alias); 4 May 2011 23:31:51 -0000 Received: (qmail 21985 invoked by uid 22791); 4 May 2011 23:31:46 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, TW_CL, TW_QR X-Spam-Check-By: sourceware.org Received: from smtp204.alice.it (HELO smtp204.alice.it) (82.57.200.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 04 May 2011 23:31:30 +0000 Received: from [192.168.1.4] (79.53.13.206) by smtp204.alice.it (8.5.124.08) id 4D7E0F64046E1AEB; Thu, 5 May 2011 01:31:27 +0200 Message-ID: <4DC1E1AA.1060207@oracle.com> Date: Thu, 05 May 2011 01:30:50 +0200 From: Paolo Carlini User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.14) Gecko/20110221 SUSE/3.1.8 Thunderbird/3.1.8 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" CC: libstdc++ Subject: [v3] libstdc++/47913 (again) X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, Marc kindly contributed the below rewrite of std::ratio_add (and ratio_less), algorithmically derived from the macro __udiv_qrnnd_c in gcc's longlong.h, which amounts to the best behavior in terms of accepted inputs: a pair of std::ratio is *never* rejected unless the resulting std::ratio would not be legal. Tested x86_64-linux multilib, committed to mainline. Paolo. ///////////////////////// 2011-05-04 Marc Glisse PR libstdc++/47913 (again) * include/std/ratio (ratio_add, ratio_less): Rewrite. * testsuite/20_util/ratio/operations/47913.cc: Extend. * testsuite/20_util/ratio/cons/cons_overflow_neg.cc: Adjust dg-error line numbers. * testsuite/20_util/ratio/operations/ops_overflow_neg.cc: Likewise. Index: include/std/ratio =================================================================== --- include/std/ratio (revision 173386) +++ include/std/ratio (working copy) @@ -98,41 +98,154 @@ static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; static_assert(__a1 == 0 || __b1 == 0, - "overflow in multiplication"); + "overflow in multiplication"); static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), - "overflow in multiplication"); + "overflow in multiplication"); static_assert(__b0 * __a0 <= __INTMAX_MAX__, - "overflow in multiplication"); - static_assert((__a0 * __b1 + __b0 * __a1) * __c <= - __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); + "overflow in multiplication"); + static_assert((__a0 * __b1 + __b0 * __a1) * __c + <= __INTMAX_MAX__ - __b0 * __a0, + "overflow in multiplication"); public: static const intmax_t value = _Pn * _Qn; }; - // Helpers for __safe_add - template - struct __add_overflow_check_impl - : integral_constant + // Some double-precision utilities, where numbers are represented as + // __hi*2^(8*sizeof(uintmax_t)) + __lo. + template + struct __big_less + : integral_constant { }; - template - struct __add_overflow_check_impl<_Pn, _Qn, false> - : integral_constant= -__INTMAX_MAX__ - _Qn)> - { }; + template + struct __big_add + { + static constexpr uintmax_t __lo = __lo1 + __lo2; + static constexpr uintmax_t __hi = (__hi1 + __hi2 + + (__lo1 + __lo2 < __lo1)); // carry + }; - template - struct __add_overflow_check - : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> - { }; + // Subtract a number from a bigger one. + template + struct __big_sub + { + static_assert(!__big_less<__hi1, __lo1, __hi2, __lo2>::value, + "Internal library error"); + static constexpr uintmax_t __lo = __lo1 - __lo2; + static constexpr uintmax_t __hi = (__hi1 - __hi2 - + (__lo1 < __lo2)); // carry + }; - template - struct __safe_add + // Same principle as __safe_multiply. + template + struct __big_mul { - static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, - "overflow in addition"); + private: + static constexpr uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); + static constexpr uintmax_t __x0 = __x % __c; + static constexpr uintmax_t __x1 = __x / __c; + static constexpr uintmax_t __y0 = __y % __c; + static constexpr uintmax_t __y1 = __y / __c; + static constexpr uintmax_t __x0y0 = __x0 * __y0; + static constexpr uintmax_t __x0y1 = __x0 * __y1; + static constexpr uintmax_t __x1y0 = __x1 * __y0; + static constexpr uintmax_t __x1y1 = __x1 * __y1; + static constexpr uintmax_t __mix = __x0y1 + __x1y0; // possible carry... + static constexpr uintmax_t __mix_lo = __mix * __c; + static constexpr uintmax_t __mix_hi + = __mix / __c + ((__mix < __x0y1) ? __c : 0); // ... added here + typedef __big_add<__mix_hi, __mix_lo, __x1y1, __x0y0> _Res; + public: + static constexpr uintmax_t __hi = _Res::__hi; + static constexpr uintmax_t __lo = _Res::__lo; + }; - static const intmax_t value = _Pn + _Qn; + // Adapted from __udiv_qrnnd_c in longlong.h + // This version assumes that the high bit of __d is 1. + template + struct __big_div_impl + { + private: + static_assert(__d >= (uintmax_t(1) << (sizeof(intmax_t) * 8 - 1)), + "Internal library error"); + static_assert(__n1 < __d, "Internal library error"); + static constexpr uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); + static constexpr uintmax_t __d1 = __d / __c; + static constexpr uintmax_t __d0 = __d % __c; + + static constexpr uintmax_t __q1x = __n1 / __d1; + static constexpr uintmax_t __r1x = __n1 % __d1; + static constexpr uintmax_t __m = __q1x * __d0; + static constexpr uintmax_t __r1y = __r1x * __c + __n0 / __c; + static constexpr uintmax_t __r1z = __r1y + __d; + static constexpr uintmax_t __r1 + = ((__r1y < __m) ? ((__r1z >= __d) && (__r1z < __m)) + ? (__r1z + __d) : __r1z : __r1y) - __m; + static constexpr uintmax_t __q1 + = __q1x - ((__r1y < __m) + ? ((__r1z >= __d) && (__r1z < __m)) ? 2 : 1 : 0); + static constexpr uintmax_t __q0x = __r1 / __d1; + static constexpr uintmax_t __r0x = __r1 % __d1; + static constexpr uintmax_t __n = __q0x * __d0; + static constexpr uintmax_t __r0y = __r0x * __c + __n0 % __c; + static constexpr uintmax_t __r0z = __r0y + __d; + static constexpr uintmax_t __r0 + = ((__r0y < __n) ? ((__r0z >= __d) && (__r0z < __n)) + ? (__r0z + __d) : __r0z : __r0y) - __n; + static constexpr uintmax_t __q0 + = __q0x - ((__r0y < __n) ? ((__r0z >= __d) + && (__r0z < __n)) ? 2 : 1 : 0); + + public: + static constexpr uintmax_t __quot = __q1 * __c + __q0; + static constexpr uintmax_t __rem = __r0; + + private: + typedef __big_mul<__quot, __d> _Prod; + typedef __big_add<_Prod::__hi, _Prod::__lo, 0, __rem> _Sum; + static_assert(_Sum::__hi == __n1 && _Sum::__lo == __n0, + "Internal library error"); + }; + + template + struct __big_div + { + private: + static_assert(__d != 0, "Internal library error"); + static_assert(sizeof (uintmax_t) == sizeof (unsigned long long), + "This library calls __builtin_clzll on uintmax_t, which " + "is unsafe on your platform. Please complain to " + "http://gcc.gnu.org/bugzilla/"); + static constexpr int __shift = __builtin_clzll(__d); + static constexpr int __coshift_ = sizeof(uintmax_t) * 8 - __shift; + static constexpr int __coshift = (__shift != 0) ? __coshift_ : 0; + static constexpr uintmax_t __c1 = uintmax_t(1) << __shift; + static constexpr uintmax_t __c2 = uintmax_t(1) << __coshift; + static constexpr uintmax_t __new_d = __d * __c1; + static constexpr uintmax_t __new_n0 = __n0 * __c1; + static constexpr uintmax_t __n1_shifted = (__n1 % __d) * __c1; + static constexpr uintmax_t __n0_top = (__shift != 0) ? (__n0 / __c2) : 0; + static constexpr uintmax_t __new_n1 = __n1_shifted + __n0_top; + typedef __big_div_impl<__new_n1, __new_n0, __new_d> _Res; + + public: + static constexpr uintmax_t __quot_hi = __n1 / __d; + static constexpr uintmax_t __quot_lo = _Res::__quot; + static constexpr uintmax_t __rem = _Res::__rem / __c1; + + private: + typedef __big_mul<__quot_lo, __d> _P0; + typedef __big_mul<__quot_hi, __d> _P1; + typedef __big_add<_P0::__hi, _P0::__lo, _P1::__lo, __rem> _Sum; + // No overflow. + static_assert(_P1::__hi == 0, "Internal library error"); + static_assert(_Sum::__hi >= _P0::__hi, "Internal library error"); + // Matches the input data. + static_assert(_Sum::__hi == __n1 && _Sum::__lo == __n0, + "Internal library error"); + static_assert(__rem < __d, "Internal library error"); }; /** @@ -172,53 +285,6 @@ template constexpr intmax_t ratio<_Num, _Den>::den; - /// ratio_add - template - struct ratio_add - { - private: - static constexpr intmax_t __gcd = - __static_gcd<_R1::den, _R2::den>::value; - static constexpr intmax_t __n = __safe_add< - __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, - __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value; - - // The new numerator may have common factors with the denominator, - // but they have to also be factors of __gcd. - static constexpr intmax_t __gcd2 = __static_gcd<__n, __gcd>::value; - - public: - typedef ratio<__n / __gcd2, - __safe_multiply<_R1::den / __gcd2, _R2::den / __gcd>::value> type; - - static constexpr intmax_t num = type::num; - static constexpr intmax_t den = type::den; - }; - - template - constexpr intmax_t ratio_add<_R1, _R2>::num; - - template - constexpr intmax_t ratio_add<_R1, _R2>::den; - - /// ratio_subtract - template - struct ratio_subtract - { - typedef typename ratio_add< - _R1, - ratio<-_R2::num, _R2::den>>::type type; - - static constexpr intmax_t num = type::num; - static constexpr intmax_t den = type::den; - }; - - template - constexpr intmax_t ratio_subtract<_R1, _R2>::num; - - template - constexpr intmax_t ratio_subtract<_R1, _R2>::den; - /// ratio_multiply template struct ratio_multiply @@ -278,47 +344,15 @@ : integral_constant::value> { }; - // 0 <= _Ri < 1 - // If one is 0, conclude - // Otherwise, x < y iff 1/y < 1/x - template - struct __ratio_less_impl_2; - - // _Ri > 0 - // Compare the integral parts, and remove them if they are equal - template + // Both numbers are positive. + template, + typename _Right = __big_mul<_R2::num,_R1::den> > struct __ratio_less_impl_1 - : __ratio_less_impl_2, - ratio<_R2::num % _R2::den, _R2::den> >::type + : integral_constant::value> { }; - template - struct __ratio_less_impl_1<_R1, _R2, __q1, __q2, false> - : integral_constant - { }; - - template - struct __ratio_less_impl_2 - : __ratio_less_impl_1, - ratio<_R1::den, _R1::num> >::type - { }; - - template - struct __ratio_less_impl_2, _R2> - : integral_constant - { }; - - template - struct __ratio_less_impl_2<_R1, ratio<0, __d2> > - : integral_constant - { }; - - template - struct __ratio_less_impl_2, ratio<0, __d2> > - : integral_constant - { }; - template::value @@ -341,7 +375,6 @@ { }; /// ratio_less - // using a continued fraction expansion template struct ratio_less : __ratio_less_impl<_R1, _R2>::type @@ -365,6 +398,110 @@ : integral_constant::value> { }; + template= 0), + bool = (_R2::num >= 0), + bool = ratio_less::value, _R1::den>, + ratio<__static_abs<_R2::num>::value, _R2::den> >::value> + struct __ratio_add_impl + { + private: + typedef typename __ratio_add_impl< + ratio<-_R1::num, _R1::den>, + ratio<-_R2::num, _R2::den> >::type __t; + public: + typedef ratio<-__t::num, __t::den> type; + }; + + // True addition of nonnegative numbers. + template + struct __ratio_add_impl<_R1, _R2, true, true, __b> + { + private: + static constexpr uintmax_t __g = __static_gcd<_R1::den, _R2::den>::value; + static constexpr uintmax_t __d2 = _R2::den / __g; + typedef __big_mul<_R1::den, __d2> __d; + typedef __big_mul<_R1::num, _R2::den / __g> __x; + typedef __big_mul<_R2::num, _R1::den / __g> __y; + typedef __big_add<__x::__hi, __x::__lo, __y::__hi, __y::__lo> __n; + static_assert(__n::__hi >= __x::__hi, "Internal library error"); + typedef __big_div<__n::__hi, __n::__lo, __g> __ng; + static constexpr uintmax_t __g2 = __static_gcd<__ng::__rem, __g>::value; + typedef __big_div<__n::__hi, __n::__lo, __g2> __n_final; + static_assert(__n_final::__rem == 0, "Internal library error"); + static_assert(__n_final::__quot_hi == 0 && + __n_final::__quot_lo <= __INTMAX_MAX__, "overflow in addition"); + typedef __big_mul<_R1::den / __g2, __d2> __d_final; + static_assert(__d_final::__hi == 0 && + __d_final::__lo <= __INTMAX_MAX__, "overflow in addition"); + public: + typedef ratio<__n_final::__quot_lo, __d_final::__lo> type; + }; + + template + struct __ratio_add_impl<_R1, _R2, false, true, true> + : __ratio_add_impl<_R2, _R1> + { }; + + // True subtraction of nonnegative numbers yielding a nonnegative result. + template + struct __ratio_add_impl<_R1, _R2, true, false, false> + { + private: + static constexpr uintmax_t __g = __static_gcd<_R1::den, _R2::den>::value; + static constexpr uintmax_t __d2 = _R2::den / __g; + typedef __big_mul<_R1::den, __d2> __d; + typedef __big_mul<_R1::num, _R2::den / __g> __x; + typedef __big_mul<-_R2::num, _R1::den / __g> __y; + typedef __big_sub<__x::__hi, __x::__lo, __y::__hi, __y::__lo> __n; + typedef __big_div<__n::__hi, __n::__lo, __g> __ng; + static constexpr uintmax_t __g2 = __static_gcd<__ng::__rem, __g>::value; + typedef __big_div<__n::__hi, __n::__lo, __g2> __n_final; + static_assert(__n_final::__rem == 0, "Internal library error"); + static_assert(__n_final::__quot_hi == 0 && + __n_final::__quot_lo <= __INTMAX_MAX__, "overflow in addition"); + typedef __big_mul<_R1::den / __g2, __d2> __d_final; + static_assert(__d_final::__hi == 0 && + __d_final::__lo <= __INTMAX_MAX__, "overflow in addition"); + public: + typedef ratio<__n_final::__quot_lo, __d_final::__lo> type; + }; + + /// ratio_add + template + struct ratio_add + { + typedef typename __ratio_add_impl<_R1, _R2>::type type; + static constexpr intmax_t num = type::num; + static constexpr intmax_t den = type::den; + }; + + template + constexpr intmax_t ratio_add<_R1, _R2>::num; + + template + constexpr intmax_t ratio_add<_R1, _R2>::den; + + /// ratio_subtract + template + struct ratio_subtract + { + typedef typename ratio_add< + _R1, + ratio<-_R2::num, _R2::den>>::type type; + + static constexpr intmax_t num = type::num; + static constexpr intmax_t den = type::den; + }; + + template + constexpr intmax_t ratio_subtract<_R1, _R2>::num; + + template + constexpr intmax_t ratio_subtract<_R1, _R2>::den; + + + typedef ratio<1, 1000000000000000000> atto; typedef ratio<1, 1000000000000000> femto; typedef ratio<1, 1000000000000> pico; Index: testsuite/20_util/ratio/cons/cons_overflow_neg.cc =================================================================== --- testsuite/20_util/ratio/cons/cons_overflow_neg.cc (revision 173381) +++ testsuite/20_util/ratio/cons/cons_overflow_neg.cc (working copy) @@ -49,6 +49,6 @@ // { dg-error "instantiated from here" "" { target *-*-* } 34 } // { dg-error "instantiated from here" "" { target *-*-* } 40 } // { dg-error "instantiated from here" "" { target *-*-* } 46 } -// { dg-error "denominator cannot be zero" "" { target *-*-* } 155 } -// { dg-error "out of range" "" { target *-*-* } 156 } +// { dg-error "denominator cannot be zero" "" { target *-*-* } 268 } +// { dg-error "out of range" "" { target *-*-* } 269 } // { dg-error "overflow in constant expression" "" { target *-*-* } 99 } Index: testsuite/20_util/ratio/operations/ops_overflow_neg.cc =================================================================== --- testsuite/20_util/ratio/operations/ops_overflow_neg.cc (revision 173381) +++ testsuite/20_util/ratio/operations/ops_overflow_neg.cc (working copy) @@ -39,7 +39,7 @@ // { dg-error "instantiated from here" "" { target *-*-* } 29 } // { dg-error "instantiated from here" "" { target *-*-* } 35 } // { dg-error "instantiated from here" "" { target *-*-* } 36 } -// { dg-error "overflow in addition" "" { target *-*-* } 132 } +// { dg-error "overflow in addition" "" { target *-*-* } 432 } // { dg-error "overflow in multiplication" "" { target *-*-* } 104 } // { dg-error "overflow in multiplication" "" { target *-*-* } 100 } // { dg-error "overflow in multiplication" "" { target *-*-* } 102 } Index: testsuite/20_util/ratio/operations/47913.cc =================================================================== --- testsuite/20_util/ratio/operations/47913.cc (revision 173381) +++ testsuite/20_util/ratio/operations/47913.cc (working copy) @@ -19,6 +19,7 @@ // . #include +#include #include // libstdc++/47913 @@ -27,12 +28,32 @@ bool test __attribute__((unused)) = true; using namespace std; - const intmax_t m = (intmax_t)1 << (4 * sizeof(intmax_t) - 1); - typedef ratio_add, - ratio<1, (m - 3) * (m - 2)> > ra_type; + const intmax_t m1 = (intmax_t)1 << (4 * sizeof(intmax_t) - 1); + typedef ratio_add, + ratio<1, (m1 - 3) * (m1 - 2)> > ra_type1; + VERIFY( ra_type1::num == 2 ); + VERIFY( ra_type1::den == (m1 - 1) * (m1 - 3) ); - VERIFY( ra_type::num == 2 ); - VERIFY( ra_type::den == (m - 1) * (m - 3) ); + const intmax_t m2 = numeric_limits::max(); + typedef ratio_add, + ratio<-m2, 3> > ra_type2; + VERIFY( ra_type2::num == m2 ); + VERIFY( ra_type2::den == 6 ); + + typedef ratio_add, + ratio<-m2 + 2, 7> > ra_type3; + ra_type3(); + + const intmax_t m3 = numeric_limits::max() - 1; + typedef ratio_add, + ratio > ra_type4; + ra_type4(); + + const intmax_t m4 = numeric_limits::max() / 2; + typedef ratio_add, + ratio > ra_type5; + VERIFY( ra_type5::num == (2 * m4 - 7) ); + VERIFY( ra_type5::den == 21 ); } int main()