1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef ANGLEBASE_NUMERICS_SAFE_MATH_IMPL_H_ 6 #define ANGLEBASE_NUMERICS_SAFE_MATH_IMPL_H_ 7 8 #include <stddef.h> 9 #include <stdint.h> 10 11 #include <climits> 12 #include <cmath> 13 #include <cstdlib> 14 #include <limits> 15 #include <type_traits> 16 17 #include "anglebase/numerics/safe_conversions.h" 18 19 namespace angle 20 { 21 22 namespace base 23 { 24 namespace internal 25 { 26 27 // Everything from here up to the floating point operations is portable C++, 28 // but it may not be fast. This code could be split based on 29 // platform/architecture and replaced with potentially faster implementations. 30 31 // Integer promotion templates used by the portable checked integer arithmetic. 32 template <size_t Size, bool IsSigned> 33 struct IntegerForSizeAndSign; 34 template <> 35 struct IntegerForSizeAndSign<1, true> 36 { 37 typedef int8_t type; 38 }; 39 template <> 40 struct IntegerForSizeAndSign<1, false> 41 { 42 typedef uint8_t type; 43 }; 44 template <> 45 struct IntegerForSizeAndSign<2, true> 46 { 47 typedef int16_t type; 48 }; 49 template <> 50 struct IntegerForSizeAndSign<2, false> 51 { 52 typedef uint16_t type; 53 }; 54 template <> 55 struct IntegerForSizeAndSign<4, true> 56 { 57 typedef int32_t type; 58 }; 59 template <> 60 struct IntegerForSizeAndSign<4, false> 61 { 62 typedef uint32_t type; 63 }; 64 template <> 65 struct IntegerForSizeAndSign<8, true> 66 { 67 typedef int64_t type; 68 }; 69 template <> 70 struct IntegerForSizeAndSign<8, false> 71 { 72 typedef uint64_t type; 73 }; 74 75 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to 76 // support 128-bit math, then the ArithmeticPromotion template below will need 77 // to be updated (or more likely replaced with a decltype expression). 78 79 template <typename Integer> 80 struct UnsignedIntegerForSize 81 { 82 typedef 83 typename std::enable_if<std::numeric_limits<Integer>::is_integer, 84 typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type 85 type; 86 }; 87 88 template <typename Integer> 89 struct SignedIntegerForSize 90 { 91 typedef 92 typename std::enable_if<std::numeric_limits<Integer>::is_integer, 93 typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type 94 type; 95 }; 96 97 template <typename Integer> 98 struct TwiceWiderInteger 99 { 100 typedef typename std::enable_if< 101 std::numeric_limits<Integer>::is_integer, 102 typename IntegerForSizeAndSign<sizeof(Integer) * 2, 103 std::numeric_limits<Integer>::is_signed>::type>::type type; 104 }; 105 106 template <typename Integer> 107 struct PositionOfSignBit 108 { 109 static const typename std::enable_if<std::numeric_limits<Integer>::is_integer, size_t>::type 110 value = CHAR_BIT * sizeof(Integer) - 1; 111 }; 112 113 // This is used for UnsignedAbs, where we need to support floating-point 114 // template instantiations even though we don't actually support the operations. 115 // However, there is no corresponding implementation of e.g. CheckedUnsignedAbs, 116 // so the float versions will not compile. 117 template <typename Numeric, 118 bool IsInteger = std::numeric_limits<Numeric>::is_integer, 119 bool IsFloat = std::numeric_limits<Numeric>::is_iec559> 120 struct UnsignedOrFloatForSize; 121 122 template <typename Numeric> 123 struct UnsignedOrFloatForSize<Numeric, true, false> 124 { 125 typedef typename UnsignedIntegerForSize<Numeric>::type type; 126 }; 127 128 template <typename Numeric> 129 struct UnsignedOrFloatForSize<Numeric, false, true> 130 { 131 typedef Numeric type; 132 }; 133 134 // Helper templates for integer manipulations. 135 136 template <typename T> 137 constexpr bool HasSignBit(T x) 138 { 139 // Cast to unsigned since right shift on signed is undefined. 140 return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >> 141 PositionOfSignBit<T>::value); 142 } 143 144 // This wrapper undoes the standard integer promotions. 145 template <typename T> 146 constexpr T BinaryComplement(T x) 147 { 148 return static_cast<T>(~x); 149 } 150 151 // Here are the actual portable checked integer math implementations. 152 // TODO(jschuh): Break this code out from the enable_if pattern and find a clean 153 // way to coalesce things into the CheckedNumericState specializations below. 154 155 template <typename T> 156 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type 157 CheckedAdd(T x, T y, RangeConstraint *validity) 158 { 159 // Since the value of x+y is undefined if we have a signed type, we compute 160 // it using the unsigned type of the same size. 161 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; 162 UnsignedDst ux = static_cast<UnsignedDst>(x); 163 UnsignedDst uy = static_cast<UnsignedDst>(y); 164 UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy); 165 // Addition is valid if the sign of (x + y) is equal to either that of x or 166 // that of y. 167 if (std::numeric_limits<T>::is_signed) 168 { 169 if (HasSignBit(BinaryComplement(static_cast<UnsignedDst>((uresult ^ ux) & (uresult ^ uy))))) 170 { 171 *validity = RANGE_VALID; 172 } 173 else 174 { // Direction of wrap is inverse of result sign. 175 *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; 176 } 177 } 178 else 179 { // Unsigned is either valid or overflow. 180 *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW; 181 } 182 return static_cast<T>(uresult); 183 } 184 185 template <typename T> 186 typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type 187 CheckedSub(T x, T y, RangeConstraint *validity) 188 { 189 // Since the value of x+y is undefined if we have a signed type, we compute 190 // it using the unsigned type of the same size. 191 typedef typename UnsignedIntegerForSize<T>::type UnsignedDst; 192 UnsignedDst ux = static_cast<UnsignedDst>(x); 193 UnsignedDst uy = static_cast<UnsignedDst>(y); 194 UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy); 195 // Subtraction is valid if either x and y have same sign, or (x-y) and x have 196 // the same sign. 197 if (std::numeric_limits<T>::is_signed) 198 { 199 if (HasSignBit(BinaryComplement(static_cast<UnsignedDst>((uresult ^ ux) & (ux ^ uy))))) 200 { 201 *validity = RANGE_VALID; 202 } 203 else 204 { // Direction of wrap is inverse of result sign. 205 *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW; 206 } 207 } 208 else 209 { // Unsigned is either valid or underflow. 210 *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW; 211 } 212 return static_cast<T>(uresult); 213 } 214 215 // Integer multiplication is a bit complicated. In the fast case we just 216 // we just promote to a twice wider type, and range check the result. In the 217 // slow case we need to manually check that the result won't be truncated by 218 // checking with division against the appropriate bound. 219 template <typename T> 220 typename std::enable_if<std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t), 221 T>::type 222 CheckedMul(T x, T y, RangeConstraint *validity) 223 { 224 typedef typename TwiceWiderInteger<T>::type IntermediateType; 225 IntermediateType tmp = static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y); 226 *validity = DstRangeRelationToSrcRange<T>(tmp); 227 return static_cast<T>(tmp); 228 } 229 230 template <typename T> 231 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed && 232 (sizeof(T) * 2 > sizeof(uintmax_t)), 233 T>::type 234 CheckedMul(T x, T y, RangeConstraint *validity) 235 { 236 // If either side is zero then the result will be zero. 237 if (!x || !y) 238 { 239 *validity = RANGE_VALID; 240 return static_cast<T>(0); 241 } 242 else if (x > 0) 243 { 244 if (y > 0) 245 *validity = x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW; 246 else 247 *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID : RANGE_UNDERFLOW; 248 } 249 else 250 { 251 if (y > 0) 252 *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID : RANGE_UNDERFLOW; 253 else 254 *validity = y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW; 255 } 256 257 return static_cast<T>(x * y); 258 } 259 260 template <typename T> 261 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed && 262 (sizeof(T) * 2 > sizeof(uintmax_t)), 263 T>::type 264 CheckedMul(T x, T y, RangeConstraint *validity) 265 { 266 *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y) ? RANGE_VALID : RANGE_OVERFLOW; 267 return static_cast<T>(x * y); 268 } 269 270 // Division just requires a check for an invalid negation on signed min/-1. 271 template <typename T> 272 T CheckedDiv(T x, 273 T y, 274 RangeConstraint *validity, 275 typename std::enable_if<std::numeric_limits<T>::is_integer, int>::type = 0) 276 { 277 if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() && 278 y == static_cast<T>(-1)) 279 { 280 *validity = RANGE_OVERFLOW; 281 return std::numeric_limits<T>::min(); 282 } 283 284 *validity = RANGE_VALID; 285 return static_cast<T>(x / y); 286 } 287 288 template <typename T> 289 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed, 290 T>::type 291 CheckedMod(T x, T y, RangeConstraint *validity) 292 { 293 *validity = y > 0 ? RANGE_VALID : RANGE_INVALID; 294 return static_cast<T>(x % y); 295 } 296 297 template <typename T> 298 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed, 299 T>::type 300 CheckedMod(T x, T y, RangeConstraint *validity) 301 { 302 *validity = RANGE_VALID; 303 return static_cast<T>(x % y); 304 } 305 306 template <typename T> 307 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed, 308 T>::type 309 CheckedNeg(T value, RangeConstraint *validity) 310 { 311 *validity = value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; 312 // The negation of signed min is min, so catch that one. 313 return static_cast<T>(-value); 314 } 315 316 template <typename T> 317 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed, 318 T>::type 319 CheckedNeg(T value, RangeConstraint *validity) 320 { 321 // The only legal unsigned negation is zero. 322 *validity = value ? RANGE_UNDERFLOW : RANGE_VALID; 323 return static_cast<T>(-static_cast<typename SignedIntegerForSize<T>::type>(value)); 324 } 325 326 template <typename T> 327 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed, 328 T>::type 329 CheckedAbs(T value, RangeConstraint *validity) 330 { 331 *validity = value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW; 332 return static_cast<T>(std::abs(value)); 333 } 334 335 template <typename T> 336 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed, 337 T>::type 338 CheckedAbs(T value, RangeConstraint *validity) 339 { 340 // T is unsigned, so |value| must already be positive. 341 *validity = RANGE_VALID; 342 return value; 343 } 344 345 template <typename T> 346 typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed, 347 typename UnsignedIntegerForSize<T>::type>::type 348 CheckedUnsignedAbs(T value) 349 { 350 typedef typename UnsignedIntegerForSize<T>::type UnsignedT; 351 return value == std::numeric_limits<T>::min() 352 ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1 353 : static_cast<UnsignedT>(std::abs(value)); 354 } 355 356 template <typename T> 357 typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed, 358 T>::type 359 CheckedUnsignedAbs(T value) 360 { 361 // T is unsigned, so |value| must already be positive. 362 return static_cast<T>(value); 363 } 364 365 // These are the floating point stubs that the compiler needs to see. Only the 366 // negation operation is ever called. 367 #define ANGLEBASE_FLOAT_ARITHMETIC_STUBS(NAME) \ 368 template <typename T> \ 369 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type Checked##NAME( \ 370 T, T, RangeConstraint *) \ 371 { \ 372 NOTREACHED(); \ 373 return static_cast<T>(0); \ 374 } 375 376 ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Add) 377 ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Sub) 378 ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Mul) 379 ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Div) 380 ANGLEBASE_FLOAT_ARITHMETIC_STUBS(Mod) 381 382 #undef ANGLEBASE_FLOAT_ARITHMETIC_STUBS 383 384 template <typename T> 385 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(T value, 386 RangeConstraint *) 387 { 388 return static_cast<T>(-value); 389 } 390 391 template <typename T> 392 typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(T value, 393 RangeConstraint *) 394 { 395 return static_cast<T>(std::abs(value)); 396 } 397 398 // Floats carry around their validity state with them, but integers do not. So, 399 // we wrap the underlying value in a specialization in order to hide that detail 400 // and expose an interface via accessors. 401 enum NumericRepresentation 402 { 403 NUMERIC_INTEGER, 404 NUMERIC_FLOATING, 405 NUMERIC_UNKNOWN 406 }; 407 408 template <typename NumericType> 409 struct GetNumericRepresentation 410 { 411 static const NumericRepresentation value = 412 std::numeric_limits<NumericType>::is_integer 413 ? NUMERIC_INTEGER 414 : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING : NUMERIC_UNKNOWN); 415 }; 416 417 template <typename T, NumericRepresentation type = GetNumericRepresentation<T>::value> 418 class CheckedNumericState 419 {}; 420 421 // Integrals require quite a bit of additional housekeeping to manage state. 422 template <typename T> 423 class CheckedNumericState<T, NUMERIC_INTEGER> 424 { 425 private: 426 T value_; 427 RangeConstraint validity_ : CHAR_BIT; // Actually requires only two bits. 428 429 public: 430 template <typename Src, NumericRepresentation type> 431 friend class CheckedNumericState; 432 433 CheckedNumericState() : value_(0), validity_(RANGE_VALID) {} 434 435 template <typename Src> 436 CheckedNumericState(Src value, RangeConstraint validity) 437 : value_(static_cast<T>(value)), 438 validity_(GetRangeConstraint(validity | DstRangeRelationToSrcRange<T>(value))) 439 { 440 static_assert(std::numeric_limits<Src>::is_specialized, "Argument must be numeric."); 441 } 442 443 // Copy constructor. 444 template <typename Src> 445 CheckedNumericState(const CheckedNumericState<Src> &rhs) 446 : value_(static_cast<T>(rhs.value())), 447 validity_(GetRangeConstraint(rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) 448 {} 449 450 template <typename Src> 451 explicit CheckedNumericState( 452 Src value, 453 typename std::enable_if<std::numeric_limits<Src>::is_specialized, int>::type = 0) 454 : value_(static_cast<T>(value)), validity_(DstRangeRelationToSrcRange<T>(value)) 455 {} 456 457 RangeConstraint validity() const { return validity_; } 458 T value() const { return value_; } 459 }; 460 461 // Floating points maintain their own validity, but need translation wrappers. 462 template <typename T> 463 class CheckedNumericState<T, NUMERIC_FLOATING> 464 { 465 private: 466 T value_; 467 468 public: 469 template <typename Src, NumericRepresentation type> 470 friend class CheckedNumericState; 471 472 CheckedNumericState() : value_(0.0) {} 473 474 template <typename Src> 475 CheckedNumericState( 476 Src value, 477 RangeConstraint validity, 478 typename std::enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0) 479 { 480 switch (DstRangeRelationToSrcRange<T>(value)) 481 { 482 case RANGE_VALID: 483 value_ = static_cast<T>(value); 484 break; 485 486 case RANGE_UNDERFLOW: 487 value_ = -std::numeric_limits<T>::infinity(); 488 break; 489 490 case RANGE_OVERFLOW: 491 value_ = std::numeric_limits<T>::infinity(); 492 break; 493 494 case RANGE_INVALID: 495 value_ = std::numeric_limits<T>::quiet_NaN(); 496 break; 497 498 default: 499 NOTREACHED(); 500 } 501 } 502 503 template <typename Src> 504 explicit CheckedNumericState( 505 Src value, 506 typename std::enable_if<std::numeric_limits<Src>::is_specialized, int>::type = 0) 507 : value_(static_cast<T>(value)) 508 {} 509 510 // Copy constructor. 511 template <typename Src> 512 CheckedNumericState(const CheckedNumericState<Src> &rhs) : value_(static_cast<T>(rhs.value())) 513 {} 514 515 RangeConstraint validity() const 516 { 517 return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(), 518 value_ >= -std::numeric_limits<T>::max()); 519 } 520 T value() const { return value_; } 521 }; 522 523 // For integers less than 128-bit and floats 32-bit or larger, we have the type 524 // with the larger maximum exponent take precedence. 525 enum ArithmeticPromotionCategory 526 { 527 LEFT_PROMOTION, 528 RIGHT_PROMOTION 529 }; 530 531 template <typename Lhs, 532 typename Rhs = Lhs, 533 ArithmeticPromotionCategory Promotion = 534 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value) ? LEFT_PROMOTION 535 : RIGHT_PROMOTION> 536 struct ArithmeticPromotion; 537 538 template <typename Lhs, typename Rhs> 539 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> 540 { 541 typedef Lhs type; 542 }; 543 544 template <typename Lhs, typename Rhs> 545 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> 546 { 547 typedef Rhs type; 548 }; 549 550 // We can statically check if operations on the provided types can wrap, so we 551 // can skip the checked operations if they're not needed. So, for an integer we 552 // care if the destination type preserves the sign and is twice the width of 553 // the source. 554 template <typename T, typename Lhs, typename Rhs> 555 struct IsIntegerArithmeticSafe 556 { 557 static const bool value = 558 !std::numeric_limits<T>::is_iec559 && 559 StaticDstRangeRelationToSrcRange<T, Lhs>::value == NUMERIC_RANGE_CONTAINED && 560 sizeof(T) >= (2 * sizeof(Lhs)) && 561 StaticDstRangeRelationToSrcRange<T, Rhs>::value != NUMERIC_RANGE_CONTAINED && 562 sizeof(T) >= (2 * sizeof(Rhs)); 563 }; 564 565 } // namespace internal 566 } // namespace base 567 568 } // namespace angle 569 570 #endif // ANGLEBASE_NUMERICS_SAFE_MATH_IMPL_H_ 571