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 rxboost::safe_numerics::automatic::division_result198 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 rxboost::safe_numerics::automatic::modulus_result258 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 union_intervalboost::safe_numerics::automatic::comparison_result340 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 480