boost/ratio/detail/overflow_helpers.hpp

   1 //  ratio.hpp  ---------------------------------------------------------------//
   2
   3 //  Copyright 2008 Howard Hinnant
   4 //  Copyright 2008 Beman Dawes
   5 //  Copyright 2009 Vicente J. Botet Escriba
   6
   7 //  Distributed under the Boost Software License, Version 1.0.
   8 //  See http://www.boost.org/LICENSE_1_0.txt
   9
  10 /*
  11
  12 This code was derived by Beman Dawes from Howard Hinnant's time2_demo prototype.
  13 Many thanks to Howard for making his code available under the Boost license.
  14 The original code was modified to conform to Boost conventions and to section
  15 20.4 Compile-time rational arithmetic [ratio], of the C++ committee working
  16 paper N2798.
  17 See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf.
  18
  19 time2_demo contained this comment:
  20
  21     Much thanks to Andrei Alexandrescu,
  22                    Walter Brown,
  23                    Peter Dimov,
  24                    Jeff Garland,
  25                    Terry Golubiewski,
  26                    Daniel Krugler,
  27                    Anthony Williams.
  28 */
  29
  30 // The way overflow is managed for ratio_less is taken from llvm/libcxx/include/ratio
  31
  32 #ifndef BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP
  33 #define BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP
  34
  35 #include <boost/ratio/config.hpp>
  36 #include <boost/ratio/detail/mpl/abs.hpp>
  37 #include <boost/ratio/detail/mpl/sign.hpp>
  38 #include <cstdlib>
  39 #include <climits>
  40 #include <limits>
  41 #include <boost/cstdint.hpp>
  42 #include <boost/type_traits/integral_constant.hpp>
  43 #include <boost/core/enable_if.hpp>
  44 #include <boost/integer_traits.hpp>
  45
  46 //
  47 // We simply cannot include this header on gcc without getting copious warnings of the kind:
  48 //
  49 // boost/integer.hpp:77:30: warning: use of C99 long long integer constant
  50 //
  51 // And yet there is no other reasonable implementation, so we declare this a system header
  52 // to suppress these warnings.
  53 //
  54 #if defined(__GNUC__) && (__GNUC__ >= 4)
  55 #pragma GCC system_header
  56 #endif
  57
  58 namespace boost
  59 {
  60
  61 //----------------------------------------------------------------------------//
  62 //                                 helpers                                    //
  63 //----------------------------------------------------------------------------//
  64
  65 namespace ratio_detail
  66 {
  67
  68   template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value>
  69   class br_add;
  70
  71   template <boost::intmax_t X, boost::intmax_t Y>
  72   class br_add<X, Y, 1>
  73   {
  74       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
  75       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
  76
  77       BOOST_RATIO_STATIC_ASSERT(X <= max - Y , BOOST_RATIO_OVERFLOW_IN_ADD, ());
  78   public:
  79       static const boost::intmax_t value = X + Y;
  80   };
  81
  82   template <boost::intmax_t X, boost::intmax_t Y>
  83   class br_add<X, Y, 0>
  84   {
  85   public:
  86       static const boost::intmax_t value = X;
  87   };
  88
  89   template <boost::intmax_t X, boost::intmax_t Y>
  90   class br_add<X, Y, -1>
  91   {
  92       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
  93       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
  94
  95       BOOST_RATIO_STATIC_ASSERT(min - Y <= X, BOOST_RATIO_OVERFLOW_IN_ADD, ());
  96   public:
  97       static const boost::intmax_t value = X + Y;
  98   };
  99
 100   template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value>
 101   class br_sub;
 102
 103   template <boost::intmax_t X, boost::intmax_t Y>
 104   class br_sub<X, Y, 1>
 105   {
 106       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
 107       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
 108
 109       BOOST_RATIO_STATIC_ASSERT(min + Y <= X, BOOST_RATIO_OVERFLOW_IN_SUB, ());
 110   public:
 111       static const boost::intmax_t value = X - Y;
 112   };
 113
 114   template <boost::intmax_t X, boost::intmax_t Y>
 115   class br_sub<X, Y, 0>
 116   {
 117   public:
 118       static const boost::intmax_t value = X;
 119   };
 120
 121   template <boost::intmax_t X, boost::intmax_t Y>
 122   class br_sub<X, Y, -1>
 123   {
 124       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
 125       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
 126
 127       BOOST_RATIO_STATIC_ASSERT(X <= max + Y, BOOST_RATIO_OVERFLOW_IN_SUB, ());
 128   public:
 129       static const boost::intmax_t value = X - Y;
 130   };
 131
 132   template <boost::intmax_t X, boost::intmax_t Y>
 133   class br_mul
 134   {
 135       static const boost::intmax_t nan =
 136           boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1));
 137       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
 138       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
 139
 140       static const boost::intmax_t a_x = mpl::abs_c<boost::intmax_t, X>::value;
 141       static const boost::intmax_t a_y = mpl::abs_c<boost::intmax_t, Y>::value;
 142
 143       BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ());
 144       BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ());
 145       BOOST_RATIO_STATIC_ASSERT(a_x <= max / a_y, BOOST_RATIO_OVERFLOW_IN_MUL, ());
 146   public:
 147       static const boost::intmax_t value = X * Y;
 148   };
 149
 150   template <boost::intmax_t Y>
 151   class br_mul<0, Y>
 152   {
 153   public:
 154       static const boost::intmax_t value = 0;
 155   };
 156
 157   template <boost::intmax_t X>
 158   class br_mul<X, 0>
 159   {
 160   public:
 161       static const boost::intmax_t value = 0;
 162   };
 163
 164   template <>
 165   class br_mul<0, 0>
 166   {
 167   public:
 168       static const boost::intmax_t value = 0;
 169   };
 170
 171   // Not actually used but left here in case needed in future maintenance
 172   template <boost::intmax_t X, boost::intmax_t Y>
 173   class br_div
 174   {
 175       static const boost::intmax_t nan = boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1));
 176       static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
 177       static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
 178
 179       BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ());
 180       BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ());
 181       BOOST_RATIO_STATIC_ASSERT(Y != 0, BOOST_RATIO_DIVIDE_BY_0, ());
 182   public:
 183       static const boost::intmax_t value = X / Y;
 184   };
 185
 186   // ratio arithmetic
 187   template <class R1, class R2> struct ratio_add;
 188   template <class R1, class R2> struct ratio_subtract;
 189   template <class R1, class R2> struct ratio_multiply;
 190   template <class R1, class R2> struct ratio_divide;
 191
 192   template <class R1, class R2>
 193   struct ratio_add
 194   {
 195       //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value R1::num *
 196       //R2::den + R2::num * R1::den and T2 has the value R1::den * R2::den.
 197       // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
 198   private:
 199       static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
 200       static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
 201   public:
 202       // No need to normalize as ratio_multiply is already normalized
 203       typedef typename ratio_multiply
 204          <
 205              ratio<gcd_n1_n2, R1::den / gcd_d1_d2>,
 206              ratio
 207              <
 208                  boost::ratio_detail::br_add
 209                  <
 210                      boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
 211                      boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
 212                  >::value,
 213                  R2::den
 214              >
 215          >::type type;
 216   };
 217   template <class R, boost::intmax_t D>
 218   struct ratio_add<R, ratio<0,D> >
 219   {
 220     typedef R type;
 221   };
 222
 223   template <class R1, class R2>
 224   struct ratio_subtract
 225   {
 226       //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value
 227       // R1::num *R2::den - R2::num * R1::den and T2 has the value R1::den * R2::den.
 228       // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
 229   private:
 230       static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
 231       static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
 232   public:
 233       // No need to normalize as ratio_multiply is already normalized
 234       typedef typename ratio_multiply
 235          <
 236              ratio<gcd_n1_n2, R1::den / gcd_d1_d2>,
 237              ratio
 238              <
 239                  boost::ratio_detail::br_sub
 240                  <
 241                      boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
 242                      boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
 243                  >::value,
 244                  R2::den
 245              >
 246          >::type type;
 247   };
 248
 249   template <class R, boost::intmax_t D>
 250   struct ratio_subtract<R, ratio<0,D> >
 251   {
 252     typedef R type;
 253   };
 254
 255   template <class R1, class R2>
 256   struct ratio_multiply
 257   {
 258       // The nested typedef type  shall be a synonym for ratio<R1::num * R2::den - R2::num * R1::den, R1::den * R2::den>::type.
 259       // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
 260   private:
 261      static const boost::intmax_t gcd_n1_d2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::den>::value;
 262      static const boost::intmax_t gcd_d1_n2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::num>::value;
 263   public:
 264       typedef typename ratio
 265          <
 266              boost::ratio_detail::br_mul<R1::num / gcd_n1_d2, R2::num / gcd_d1_n2>::value,
 267              boost::ratio_detail::br_mul<R2::den / gcd_n1_d2, R1::den / gcd_d1_n2>::value
 268          >::type type;
 269   };
 270
 271   template <class R1, class R2>
 272   struct ratio_divide
 273   {
 274       // The nested typedef type  shall be a synonym for ratio<R1::num * R2::den, R2::num * R1::den>::type.
 275       // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
 276   private:
 277       static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
 278       static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
 279   public:
 280       typedef typename ratio
 281          <
 282              boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
 283              boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
 284          >::type type;
 285   };
 286   template <class R1, class R2>
 287   struct is_evenly_divisible_by
 288   {
 289   private:
 290       static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
 291       static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
 292   public:
 293       typedef integral_constant<bool,
 294              ((R2::num / gcd_n1_n2 ==1) && (R1::den / gcd_d1_d2)==1)
 295       > type;
 296   };
 297
 298   template <class T>
 299   struct is_ratio : public boost::false_type
 300   {};
 301   template <boost::intmax_t N, boost::intmax_t D>
 302   struct is_ratio<ratio<N, D> > : public boost::true_type
 303   {};
 304
 305   template <class R1, class R2,
 306             boost::intmax_t Q1 = R1::num / R1::den, boost::intmax_t M1 = R1::num % R1::den,
 307             boost::intmax_t Q2 = R2::num / R2::den, boost::intmax_t M2 = R2::num % R2::den>
 308   struct ratio_less1
 309   {
 310     static const bool value = Q1 < Q2;
 311   };
 312
 313   template <class R1, class R2, boost::intmax_t Q>
 314   struct ratio_less1<R1, R2, Q, 0, Q, 0>
 315   {
 316     static const bool value = false;
 317   };
 318
 319   template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M2>
 320   struct ratio_less1<R1, R2, Q, 0, Q, M2>
 321   {
 322     static const bool value = true;
 323   };
 324
 325   template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1>
 326   struct ratio_less1<R1, R2, Q, M1, Q, 0>
 327   {
 328     static const bool value = false;
 329   };
 330
 331   template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1, boost::intmax_t M2>
 332   struct ratio_less1<R1, R2, Q, M1, Q, M2>
 333   {
 334     static const bool value = ratio_less1<ratio<R2::den, M2>, ratio<R1::den, M1>
 335                                             >::value;
 336   };
 337
 338   template <
 339       class R1,
 340       class R2,
 341       boost::intmax_t S1 = mpl::sign_c<boost::intmax_t, R1::num>::value,
 342     boost::intmax_t S2 = mpl::sign_c<boost::intmax_t, R2::num>::value
 343 >
 344   struct ratio_less
 345   {
 346       static const bool value = S1 < S2;
 347   };
 348
 349   template <class R1, class R2>
 350   struct ratio_less<R1, R2, 1LL, 1LL>
 351   {
 352       static const bool value = ratio_less1<R1, R2>::value;
 353   };
 354
 355   template <class R1, class R2>
 356   struct ratio_less<R1, R2, -1LL, -1LL>
 357   {
 358       static const bool value = ratio_less1<ratio<-R2::num, R2::den>,
 359                                             ratio<-R1::num, R1::den> >::value;
 360   };
 361
 362
 363 }  // namespace ratio_detail
 364
 365 }  // namespace boost
 366
 367 #endif  // BOOST_RATIO_HPP