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 <marc.gli...@normalesup.org>
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<intmax_t _Pn, intmax_t _Qn, bool>
- struct __add_overflow_check_impl
- : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)>
+ // Some double-precision utilities, where numbers are represented as
+ // __hi*2^(8*sizeof(uintmax_t)) + __lo.
+ template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
+ struct __big_less
+ : integral_constant<bool, (__hi1 < __hi2
+ || (__hi1 == __hi2 && __lo1 < __lo2))>
{ };
- template<intmax_t _Pn, intmax_t _Qn>
- struct __add_overflow_check_impl<_Pn, _Qn, false>
- : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)>
- { };
+ template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
+ struct __big_add
+ {
+ static constexpr uintmax_t __lo = __lo1 + __lo2;
+ static constexpr uintmax_t __hi = (__hi1 + __hi2 +
+ (__lo1 + __lo2 < __lo1)); // carry
+ };
- template<intmax_t _Pn, intmax_t _Qn>
- struct __add_overflow_check
- : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)>
- { };
+ // Subtract a number from a bigger one.
+ template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
+ 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<intmax_t _Pn, intmax_t _Qn>
- struct __safe_add
+ // Same principle as __safe_multiply.
+ template<uintmax_t __x, uintmax_t __y>
+ 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<uintmax_t __n1, uintmax_t __n0, uintmax_t __d>
+ 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<uintmax_t __n1, uintmax_t __n0, uintmax_t __d>
+ 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<intmax_t _Num, intmax_t _Den>
constexpr intmax_t ratio<_Num, _Den>::den;
- /// ratio_add
- template<typename _R1, typename _R2>
- 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<typename _R1, typename _R2>
- constexpr intmax_t ratio_add<_R1, _R2>::num;
-
- template<typename _R1, typename _R2>
- constexpr intmax_t ratio_add<_R1, _R2>::den;
-
- /// ratio_subtract
- template<typename _R1, typename _R2>
- 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<typename _R1, typename _R2>
- constexpr intmax_t ratio_subtract<_R1, _R2>::num;
-
- template<typename _R1, typename _R2>
- constexpr intmax_t ratio_subtract<_R1, _R2>::den;
-
/// ratio_multiply
template<typename _R1, typename _R2>
struct ratio_multiply
@@ -278,47 +344,15 @@
: integral_constant<bool, !ratio_equal<_R1, _R2>::value>
{ };
- // 0 <= _Ri < 1
- // If one is 0, conclude
- // Otherwise, x < y iff 1/y < 1/x
- template<typename _R1, typename _R2>
- struct __ratio_less_impl_2;
-
- // _Ri > 0
- // Compare the integral parts, and remove them if they are equal
- template<typename _R1, typename _R2, intmax_t __q1 = _R1::num / _R1::den,
- intmax_t __q2 = _R2::num / _R2::den, bool __eq = (__q1 == __q2)>
+ // Both numbers are positive.
+ template<typename _R1, typename _R2,
+ typename _Left = __big_mul<_R1::num,_R2::den>,
+ typename _Right = __big_mul<_R2::num,_R1::den> >
struct __ratio_less_impl_1
- : __ratio_less_impl_2<ratio<_R1::num % _R1::den, _R1::den>,
- ratio<_R2::num % _R2::den, _R2::den> >::type
+ : integral_constant<bool, __big_less<_Left::__hi, _Left::__lo,
+ _Right::__hi, _Right::__lo>::value>
{ };
- template<typename _R1, typename _R2, intmax_t __q1, intmax_t __q2>
- struct __ratio_less_impl_1<_R1, _R2, __q1, __q2, false>
- : integral_constant<bool, (__q1 < __q2) >
- { };
-
- template<typename _R1, typename _R2>
- struct __ratio_less_impl_2
- : __ratio_less_impl_1<ratio<_R2::den, _R2::num>,
- ratio<_R1::den, _R1::num> >::type
- { };
-
- template<intmax_t __d1, typename _R2>
- struct __ratio_less_impl_2<ratio<0, __d1>, _R2>
- : integral_constant<bool, true>
- { };
-
- template<typename _R1, intmax_t __d2>
- struct __ratio_less_impl_2<_R1, ratio<0, __d2> >
- : integral_constant<bool, false>
- { };
-
- template<intmax_t __d1, intmax_t __d2>
- struct __ratio_less_impl_2<ratio<0, __d1>, ratio<0, __d2> >
- : integral_constant<bool, false>
- { };
-
template<typename _R1, typename _R2,
bool = (_R1::num == 0 || _R2::num == 0
|| (__static_sign<_R1::num>::value
@@ -341,7 +375,6 @@
{ };
/// ratio_less
- // using a continued fraction expansion
template<typename _R1, typename _R2>
struct ratio_less
: __ratio_less_impl<_R1, _R2>::type
@@ -365,6 +398,110 @@
: integral_constant<bool, !ratio_less<_R1, _R2>::value>
{ };
+ template<typename _R1, typename _R2,
+ bool = (_R1::num >= 0),
+ bool = (_R2::num >= 0),
+ bool = ratio_less<ratio<__static_abs<_R1::num>::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<typename _R1, typename _R2, bool __b>
+ 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<typename _R1, typename _R2>
+ struct __ratio_add_impl<_R1, _R2, false, true, true>
+ : __ratio_add_impl<_R2, _R1>
+ { };
+
+ // True subtraction of nonnegative numbers yielding a nonnegative result.
+ template<typename _R1, typename _R2>
+ 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<typename _R1, typename _R2>
+ 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<typename _R1, typename _R2>
+ constexpr intmax_t ratio_add<_R1, _R2>::num;
+
+ template<typename _R1, typename _R2>
+ constexpr intmax_t ratio_add<_R1, _R2>::den;
+
+ /// ratio_subtract
+ template<typename _R1, typename _R2>
+ 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<typename _R1, typename _R2>
+ constexpr intmax_t ratio_subtract<_R1, _R2>::num;
+
+ template<typename _R1, typename _R2>
+ 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 @@
// <http://www.gnu.org/licenses/>.
#include <ratio>
+#include <limits>
#include <testsuite_hooks.h>
// 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 - 1) * (m - 2)>,
- 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 - 1) * (m1 - 2)>,
+ 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<intmax_t>::max();
+ typedef ratio_add<ratio<m2, 2>,
+ ratio<-m2, 3> > ra_type2;
+ VERIFY( ra_type2::num == m2 );
+ VERIFY( ra_type2::den == 6 );
+
+ typedef ratio_add<ratio<m2 / 7 * 5 - 1, 5>,
+ ratio<-m2 + 2, 7> > ra_type3;
+ ra_type3();
+
+ const intmax_t m3 = numeric_limits<intmax_t>::max() - 1;
+ typedef ratio_add<ratio<-m3 / 7 * 5 - 1, 5>,
+ ratio<m3, 7> > ra_type4;
+ ra_type4();
+
+ const intmax_t m4 = numeric_limits<intmax_t>::max() / 2;
+ typedef ratio_add<ratio<m4 - 5, 15>,
+ ratio<m4, 35> > ra_type5;
+ VERIFY( ra_type5::num == (2 * m4 - 7) );
+ VERIFY( ra_type5::den == 21 );
}
int main()
