From 91e4938b8c0f979f84c2b66d1ff5370e83e00eb0 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Wed, 4 May 2011 23:23:54 +0000 Subject: [PATCH] PR libstdc++/47913 (again) 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. From-SVN: r173400 --- libstdc++-v3/ChangeLog | 9 + libstdc++-v3/include/std/ratio | 353 ++++++++++++------ .../20_util/ratio/cons/cons_overflow_neg.cc | 4 +- .../20_util/ratio/operations/47913.cc | 33 +- .../ratio/operations/ops_overflow_neg.cc | 2 +- 5 files changed, 284 insertions(+), 117 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 416b656bc20..7b766dc3393 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +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. + 2011-05-03 Paolo Carlini PR libstdc++/48848 diff --git a/libstdc++-v3/include/std/ratio b/libstdc++-v3/include/std/ratio index 17d28a10f46..a9cbfe246e3 100644 --- a/libstdc++-v3/include/std/ratio +++ b/libstdc++-v3/include/std/ratio @@ -98,41 +98,154 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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 + { + 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; + }; + + // 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 { - static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, - "overflow in addition"); + 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; - static const intmax_t value = _Pn + _Qn; + 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 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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,45 +344,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : 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 - { }; - - 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 + : integral_constant::value> { }; template struct ratio_less : __ratio_less_impl<_R1, _R2>::type @@ -365,6 +398,110 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : 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; diff --git a/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc b/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc index 6a611e833c6..14076a2d121 100644 --- a/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc +++ b/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc @@ -49,6 +49,6 @@ test04() // { 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 } diff --git a/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc b/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc index 4105a710d91..aa873946924 100644 --- a/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc +++ b/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc @@ -19,6 +19,7 @@ // . #include +#include #include // libstdc++/47913 @@ -27,12 +28,32 @@ void test01() 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; - - VERIFY( ra_type::num == 2 ); - VERIFY( ra_type::den == (m - 1) * (m - 3) ); + 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) ); + + 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() diff --git a/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc b/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc index b7076dfc57a..f1da21978ec 100644 --- a/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc +++ b/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc @@ -39,7 +39,7 @@ test02() // { 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 } -- 2.30.2