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