ceph/src/boost/boost/safe_numerics/automatic.hpp

   1 #ifndef BOOST_NUMERIC_AUTOMATIC_HPP
   2 #define BOOST_NUMERIC_AUTOMATIC_HPP
   3
   4 //  Copyright (c) 2012 Robert Ramey
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 // policy which creates expanded results types designed
  11 // to avoid overflows.
  12
  13 #include <limits>
  14 #include <cstdint>     // (u)intmax_t,
  15 #include <type_traits> // conditional
  16 #include <boost/integer.hpp>
  17
  18 #include "safe_common.hpp"
  19 #include "checked_result.hpp"
  20 #include "checked_default.hpp"
  21 #include "checked_integer.hpp"
  22 #include "checked_result_operations.hpp"
  23 #include "interval.hpp"
  24 #include "utility.hpp"
  25
  26 namespace boost {
  27 namespace safe_numerics {
  28
  29 struct automatic {
  30 private:
  31     // the following returns the "true" type.  After calculating the new max and min
  32     // these return the minimum size type which can hold the expected result.
  33     struct defer_stored_signed_lazily {
  34         template<std::intmax_t Min, std::intmax_t Max>
  35         using type = utility::signed_stored_type<Min, Max>;
  36     };
  37
  38     struct defer_stored_unsigned_lazily {
  39         template<std::uintmax_t Min, std::uintmax_t Max>
  40         using type = utility::unsigned_stored_type<Min, Max>;
  41     };
  42
  43     template<typename T, T Min, T Max>
  44     struct result_type {
  45         using type = typename std::conditional<
  46             std::numeric_limits<T>::is_signed,
  47             defer_stored_signed_lazily,
  48             defer_stored_unsigned_lazily
  49         >::type::template type<Min, Max>;
  50     };
  51
  52 public:
  53     ///////////////////////////////////////////////////////////////////////
  54     template<typename T, typename U>
  55     struct addition_result {
  56         using temp_base_type = typename std::conditional<
  57             // if both arguments are unsigned
  58             ! std::numeric_limits<T>::is_signed
  59             && ! std::numeric_limits<U>::is_signed,
  60             // result is unsigned
  61             std::uintmax_t,
  62             // otherwise result is signed
  63             std::intmax_t
  64         >::type;
  65
  66         using r_type = checked_result<temp_base_type>;
  67         using r_interval_type = interval<r_type>;
  68
  69         constexpr static const r_interval_type t_interval{
  70             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
  71             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
  72         };
  73
  74         constexpr static const r_interval_type u_interval{
  75             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
  76             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
  77         };
  78
  79         constexpr static const r_interval_type r_interval = t_interval + u_interval;
  80
  81         constexpr static auto rl = r_interval.l;
  82         constexpr static auto ru = r_interval.u;
  83
  84         using type = typename result_type<
  85             temp_base_type,
  86             rl.exception()
  87                 ? std::numeric_limits<temp_base_type>::min()
  88                 : static_cast<temp_base_type>(rl),
  89             ru.exception()
  90                 ? std::numeric_limits<temp_base_type>::max()
  91                 : static_cast<temp_base_type>(ru)
  92         >::type;
  93     };
  94
  95     ///////////////////////////////////////////////////////////////////////
  96     template<typename T, typename U>
  97     struct subtraction_result {
  98         // result of subtraction are always signed.
  99         using temp_base_type = intmax_t;
 100
 101         using r_type = checked_result<temp_base_type>;
 102         using r_interval_type = interval<r_type>;
 103
 104         constexpr static const r_interval_type t_interval{
 105             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 106             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 107         };
 108
 109         constexpr static const r_interval_type u_interval{
 110             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 111             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 112         };
 113
 114         constexpr static const r_interval_type r_interval = t_interval - u_interval;
 115
 116         constexpr static auto rl = r_interval.l;
 117         constexpr static auto ru = r_interval.u;
 118
 119         using type = typename result_type<
 120             temp_base_type,
 121             rl.exception()
 122                 ? std::numeric_limits<temp_base_type>::min()
 123                 : static_cast<temp_base_type>(rl),
 124             ru.exception()
 125                 ? std::numeric_limits<temp_base_type>::max()
 126                 : static_cast<temp_base_type>(ru)
 127         >::type;
 128     };
 129
 130     ///////////////////////////////////////////////////////////////////////
 131     template<typename T, typename U>
 132     struct multiplication_result {
 133         using temp_base_type = typename std::conditional<
 134             // if both arguments are unsigned
 135             ! std::numeric_limits<T>::is_signed
 136             && ! std::numeric_limits<U>::is_signed,
 137             // result is unsigned
 138             std::uintmax_t,
 139             // otherwise result is signed
 140             std::intmax_t
 141         >::type;
 142
 143         using r_type = checked_result<temp_base_type>;
 144         using r_interval_type = interval<r_type>;
 145
 146         constexpr static const r_interval_type t_interval{
 147             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 148             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 149         };
 150
 151         constexpr static const r_interval_type u_interval{
 152             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 153             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 154         };
 155
 156         constexpr static const r_interval_type r_interval = t_interval * u_interval;
 157
 158         constexpr static const auto rl = r_interval.l;
 159         constexpr static const auto ru = r_interval.u;
 160
 161         using type = typename result_type<
 162             temp_base_type,
 163             rl.exception()
 164                 ? std::numeric_limits<temp_base_type>::min()
 165                 : static_cast<temp_base_type>(rl),
 166             ru.exception()
 167                 ? std::numeric_limits<temp_base_type>::max()
 168                 : static_cast<temp_base_type>(ru)
 169         >::type;
 170     };
 171
 172     ///////////////////////////////////////////////////////////////////////
 173     template<typename T, typename U>
 174     struct division_result {
 175         using temp_base_type = typename std::conditional<
 176             // if both arguments are unsigned
 177             ! std::numeric_limits<T>::is_signed
 178             && ! std::numeric_limits<U>::is_signed,
 179             // result is unsigned
 180             std::uintmax_t,
 181             // otherwise result is signed
 182             std::intmax_t
 183         >::type;
 184
 185         using r_type = checked_result<temp_base_type>;
 186         using r_interval_type = interval<r_type>;
 187
 188         constexpr static const r_interval_type t_interval{
 189             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 190             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 191         };
 192
 193         constexpr static const r_interval_type u_interval{
 194             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 195             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 196         };
 197
 198         constexpr static r_interval_type rx(){
 199             if(u_interval.u < r_type(0)
 200             || u_interval.l > r_type(0))
 201                 return t_interval / u_interval;
 202             return utility::minmax(
 203                 std::initializer_list<r_type> {
 204                     t_interval.l / u_interval.l,
 205                     t_interval.l / r_type(-1),
 206                     t_interval.l / r_type(1),
 207                     t_interval.l / u_interval.u,
 208                     t_interval.u / u_interval.l,
 209                     t_interval.u / r_type(-1),
 210                     t_interval.u / r_type(1),
 211                     t_interval.u / u_interval.u,
 212                 }
 213             );
 214         }
 215
 216         constexpr static const r_interval_type r_interval = rx();
 217
 218         constexpr static auto rl = r_interval.l;
 219         constexpr static auto ru = r_interval.u;
 220
 221         using type = typename result_type<
 222             temp_base_type,
 223             rl.exception()
 224                 ? std::numeric_limits<temp_base_type>::min()
 225                 : static_cast<temp_base_type>(rl),
 226             ru.exception()
 227                 ? std::numeric_limits<temp_base_type>::max()
 228                 : static_cast<temp_base_type>(ru)
 229         >::type;
 230     };
 231
 232     ///////////////////////////////////////////////////////////////////////
 233     template<typename T, typename U>
 234     struct modulus_result {
 235         using temp_base_type = typename std::conditional<
 236             // if both arguments are unsigned
 237             ! std::numeric_limits<T>::is_signed
 238             && ! std::numeric_limits<U>::is_signed,
 239             // result is unsigned
 240             std::uintmax_t,
 241             // otherwise result is signed
 242             std::intmax_t
 243         >::type;
 244
 245         using r_type = checked_result<temp_base_type>;
 246         using r_interval_type = interval<r_type>;
 247
 248         constexpr static const r_interval_type t_interval{
 249             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 250             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 251         };
 252
 253         constexpr static const r_interval_type u_interval{
 254             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 255             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 256         };
 257
 258         constexpr static r_interval_type rx(){
 259             if(u_interval.u < r_type(0)
 260             || u_interval.l > r_type(0))
 261                 return t_interval / u_interval;
 262             return utility::minmax(
 263                 std::initializer_list<r_type> {
 264                     t_interval.l % u_interval.l,
 265                     t_interval.l % r_type(-1),
 266                     t_interval.l % r_type(1),
 267                     t_interval.l % u_interval.u,
 268                     t_interval.u % u_interval.l,
 269                     t_interval.u % r_type(-1),
 270                     t_interval.u % r_type(1),
 271                     t_interval.u % u_interval.u,
 272                 }
 273             );
 274         }
 275
 276         constexpr static const r_interval_type r_interval = rx();
 277
 278         constexpr static auto rl = r_interval.l;
 279         constexpr static auto ru = r_interval.u;
 280
 281         using type = typename result_type<
 282             temp_base_type,
 283             rl.exception()
 284                 ? std::numeric_limits<temp_base_type>::min()
 285                 : static_cast<temp_base_type>(rl),
 286             ru.exception()
 287                 ? std::numeric_limits<temp_base_type>::max()
 288                 : static_cast<temp_base_type>(ru)
 289         >::type;
 290     };
 291
 292     ///////////////////////////////////////////////////////////////////////
 293     // note: comparison_result (<, >, ...) is special.
 294     // The return value is always a bool.  The type returned here is
 295     // the intermediate type applied to make the values comparable.
 296     template<typename T, typename U>
 297     struct comparison_result {
 298         using temp_base_type = typename std::conditional<
 299             // if both arguments are unsigned
 300             ! std::numeric_limits<T>::is_signed
 301             && ! std::numeric_limits<U>::is_signed,
 302             // result is unsigned
 303             std::uintmax_t,
 304             // otherwise result is signed
 305             std::intmax_t
 306         >::type;
 307
 308         using r_type = checked_result<temp_base_type>;
 309         using r_interval_type = interval<r_type>;
 310
 311         constexpr static const r_interval_type t_interval{
 312             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 313             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 314         };
 315
 316         constexpr static const r_interval_type u_interval{
 317             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 318             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 319         };
 320
 321         // workaround some microsoft problem
 322         #if 0
 323         constexpr static r_type min(const r_type & t, const r_type & u){
 324             // assert(! u.exception());
 325             // assert(! t.exception());
 326             return static_cast<bool>(t < u) ? t : u;
 327         }
 328
 329        constexpr static r_type max(const r_type & t, const r_type & u){
 330             // assert(! u.exception());
 331             // assert(! t.exception());
 332             return static_cast<bool>(t < u) ? u : t;
 333         }
 334         #endif
 335
 336         // union of two intervals
 337         // note: we can't use t_interval | u_interval because it
 338         // depends on max and min which in turn depend on < which in turn
 339         // depends on implicit conversion of tribool to bool
 340         constexpr static r_interval_type union_interval(
 341             const r_interval_type & t,
 342             const r_interval_type & u
 343         ){
 344             //const r_type & rl = min(t.l, u.l);
 345             const r_type & rmin = static_cast<bool>(t.l < u.l) ? t.l : u.l;
 346             //const r_type & ru = max(t.u, u.u);
 347             const r_type & rmax = static_cast<bool>(t.u < u.u) ? u.u : t.u;
 348             return r_interval_type(rmin, rmax);
 349         }
 350
 351         constexpr static const r_interval_type r_interval =
 352             union_interval(t_interval, u_interval);
 353
 354         constexpr static auto rl = r_interval.l;
 355         constexpr static auto ru = r_interval.u;
 356
 357         using type = typename result_type<
 358             temp_base_type,
 359             rl.exception()
 360                 ? std::numeric_limits<temp_base_type>::min()
 361                 : static_cast<temp_base_type>(rl),
 362             ru.exception()
 363                 ? std::numeric_limits<temp_base_type>::max()
 364                 : static_cast<temp_base_type>(ru)
 365         >::type;
 366     };
 367
 368     ///////////////////////////////////////////////////////////////////////
 369     // shift operations
 370     template<typename T, typename U>
 371     struct left_shift_result {
 372         using temp_base_type = typename std::conditional<
 373             std::numeric_limits<T>::is_signed,
 374             std::intmax_t,
 375             std::uintmax_t
 376         >::type;
 377
 378         using r_type = checked_result<temp_base_type>;
 379         using r_interval_type = interval<r_type>;
 380
 381         constexpr static const r_interval_type t_interval{
 382             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 383             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 384         };
 385
 386         constexpr static const r_interval_type u_interval{
 387             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min())),
 388             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 389         };
 390
 391         constexpr static const r_interval_type r_interval =
 392             t_interval << u_interval;
 393
 394         constexpr static auto rl = r_interval.l;
 395         constexpr static auto ru = r_interval.u;
 396
 397         using type = typename result_type<
 398             temp_base_type,
 399             rl.exception()
 400                 ? std::numeric_limits<temp_base_type>::min()
 401                 : static_cast<temp_base_type>(rl),
 402             ru.exception()
 403                 ? std::numeric_limits<temp_base_type>::max()
 404                 : static_cast<temp_base_type>(ru)
 405         >::type;
 406     };
 407
 408     ///////////////////////////////////////////////////////////////////////
 409     template<typename T, typename U>
 410     struct right_shift_result {
 411         using temp_base_type = typename std::conditional<
 412             std::numeric_limits<T>::is_signed,
 413             std::intmax_t,
 414             std::uintmax_t
 415         >::type;
 416
 417         using r_type = checked_result<temp_base_type>;
 418         using r_interval_type = interval<r_type>;
 419
 420         constexpr static const r_interval_type t_interval{
 421             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::min())),
 422             checked::cast<temp_base_type>(base_value(std::numeric_limits<T>::max()))
 423         };
 424
 425         constexpr static const r_type u_min
 426             = checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::min()));
 427
 428         constexpr static const r_interval_type u_interval{
 429             u_min.exception()
 430             ? r_type(0)
 431             : u_min,
 432             checked::cast<temp_base_type>(base_value(std::numeric_limits<U>::max()))
 433         };
 434
 435         constexpr static const r_interval_type r_interval = t_interval >> u_interval;
 436
 437         constexpr static auto rl = r_interval.l;
 438         constexpr static auto ru = r_interval.u;
 439
 440         using type = typename result_type<
 441             temp_base_type,
 442             rl.exception()
 443                 ? std::numeric_limits<temp_base_type>::min()
 444                 : static_cast<temp_base_type>(rl),
 445             ru.exception()
 446                 ? std::numeric_limits<temp_base_type>::max()
 447                 : static_cast<temp_base_type>(ru)
 448         >::type;
 449
 450     };
 451
 452     ///////////////////////////////////////////////////////////////////////
 453     template<typename T, typename U>
 454     struct bitwise_and_result {
 455         using type = decltype(
 456             typename base_type<T>::type()
 457             & typename base_type<U>::type()
 458         );
 459     };
 460     template<typename T, typename U>
 461     struct bitwise_or_result {
 462         using type = decltype(
 463             typename base_type<T>::type()
 464             | typename base_type<U>::type()
 465         );
 466     };
 467     template<typename T, typename U>
 468     struct bitwise_xor_result {
 469         using type = decltype(
 470             typename base_type<T>::type()
 471             ^ typename base_type<U>::type()
 472         );
 473     };
 474 };
 475
 476 } // safe_numerics
 477 } // boost
 478
 479 #endif // BOOST_NUMERIC_AUTOMATIC_HPP