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 BASE_NUMERICS_SAFE_MATH_H_ 6 #define BASE_NUMERICS_SAFE_MATH_H_ 7 8 #include <stddef.h> 9 10 #include <limits> 11 #include <type_traits> 12 13 #include "base/numerics/safe_math_impl.h" 14 15 namespace base { 16 namespace internal { 17 18 // CheckedNumeric<> implements all the logic and operators for detecting integer 19 // boundary conditions such as overflow, underflow, and invalid conversions. 20 // The CheckedNumeric type implicitly converts from floating point and integer 21 // data types, and contains overloads for basic arithmetic operations (i.e.: +, 22 // -, *, / for all types and %, <<, >>, &, |, ^ for integers). Type promotions 23 // are a slightly modified version of the standard C arithmetic rules with the 24 // two differences being that there is no default promotion to int and bitwise 25 // logical operations always return an unsigned of the wider type. 26 // 27 // You may also use one of the variadic convenience functions, which accept 28 // standard arithmetic or CheckedNumeric types, perform arithmetic operations, 29 // and return a CheckedNumeric result. The supported functions are: 30 // CheckAdd() - Addition. 31 // CheckSub() - Subtraction. 32 // CheckMul() - Multiplication. 33 // CheckDiv() - Division. 34 // CheckMod() - Modulous (integer only). 35 // CheckLsh() - Left integer shift (integer only). 36 // CheckRsh() - Right integer shift (integer only). 37 // CheckAnd() - Bitwise AND (integer only with unsigned result). 38 // CheckOr() - Bitwise OR (integer only with unsigned result). 39 // CheckXor() - Bitwise XOR (integer only with unsigned result). 40 // CheckMax() - Maximum of supplied arguments. 41 // CheckMin() - Minimum of supplied arguments. 42 // 43 // The unary negation, increment, and decrement operators are supported, along 44 // with the following unary arithmetic methods, which return a new 45 // CheckedNumeric as a result of the operation: 46 // Abs() - Absolute value. 47 // UnsignedAbs() - Absolute value as an equal-width unsigned underlying type 48 // (valid for only integral types). 49 // Max() - Returns whichever is greater of the current instance or argument. 50 // The underlying return type is whichever has the greatest magnitude. 51 // Min() - Returns whichever is lowest of the current instance or argument. 52 // The underlying return type is whichever has can represent the lowest 53 // number in the smallest width (e.g. int8_t over unsigned, int over 54 // int8_t, and float over int). 55 // 56 // The following methods convert from CheckedNumeric to standard numeric values: 57 // AssignIfValid() - Assigns the underlying value to the supplied destination 58 // pointer if the value is currently valid and within the range 59 // supported by the destination type. Returns true on success. 60 // **************************************************************************** 61 // * WARNING: All of the following functions return a StrictNumeric, which * 62 // * is valid for comparison and assignment operations, but will trigger a * 63 // * compile failure on attempts to assign to a type of insufficient range. * 64 // **************************************************************************** 65 // IsValid() - Returns true if the underlying numeric value is valid (i.e. has 66 // has not wrapped and is not the result of an invalid conversion). 67 // ValueOrDie() - Returns the underlying value. If the state is not valid this 68 // call will crash on a CHECK. 69 // ValueOrDefault() - Returns the current value, or the supplied default if the 70 // state is not valid (will not trigger a CHECK). 71 // 72 // The following wrapper functions can be used to avoid the template 73 // disambiguator syntax when converting a destination type. 74 // IsValidForType<>() in place of: a.template IsValid<Dst>() 75 // ValueOrDieForType<>() in place of: a.template ValueOrDie() 76 // ValueOrDefaultForType<>() in place of: a.template ValueOrDefault(default) 77 // 78 // The following are general utility methods that are useful for converting 79 // between arithmetic types and CheckedNumeric types: 80 // CheckedNumeric::Cast<Dst>() - Instance method returning a CheckedNumeric 81 // derived from casting the current instance to a CheckedNumeric of 82 // the supplied destination type. 83 // MakeCheckedNum() - Creates a new CheckedNumeric from the underlying type of 84 // the supplied arithmetic, CheckedNumeric, or StrictNumeric type. 85 // 86 // Comparison operations are explicitly not supported because they could result 87 // in a crash on an unexpected CHECK condition. You should use patterns like the 88 // following for comparisons: 89 // CheckedNumeric<size_t> checked_size = untrusted_input_value; 90 // checked_size += HEADER LENGTH; 91 // if (checked_size.IsValid() && checked_size.ValueOrDie() < buffer_size) 92 // Do stuff... 93 94 template <typename T> 95 class CheckedNumeric { 96 static_assert(std::is_arithmetic<T>::value, 97 "CheckedNumeric<T>: T must be a numeric type."); 98 99 public: 100 using type = T; 101 CheckedNumeric()102 constexpr CheckedNumeric() {} 103 104 // Copy constructor. 105 template <typename Src> CheckedNumeric(const CheckedNumeric<Src> & rhs)106 constexpr CheckedNumeric(const CheckedNumeric<Src>& rhs) 107 : state_(rhs.state_.value(), rhs.IsValid()) {} 108 109 template <typename Src> 110 friend class CheckedNumeric; 111 112 // This is not an explicit constructor because we implicitly upgrade regular 113 // numerics to CheckedNumerics to make them easier to use. 114 template <typename Src> CheckedNumeric(Src value)115 constexpr CheckedNumeric(Src value) // NOLINT(runtime/explicit) 116 : state_(value) { 117 static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric."); 118 } 119 120 // This is not an explicit constructor because we want a seamless conversion 121 // from StrictNumeric types. 122 template <typename Src> CheckedNumeric(StrictNumeric<Src> value)123 constexpr CheckedNumeric( 124 StrictNumeric<Src> value) // NOLINT(runtime/explicit) 125 : state_(static_cast<Src>(value)) {} 126 127 // IsValid() - The public API to test if a CheckedNumeric is currently valid. 128 // A range checked destination type can be supplied using the Dst template 129 // parameter. 130 template <typename Dst = T> IsValid()131 constexpr bool IsValid() const { 132 return state_.is_valid() && 133 IsValueInRangeForNumericType<Dst>(state_.value()); 134 } 135 136 // AssignIfValid(Dst) - Assigns the underlying value if it is currently valid 137 // and is within the range supported by the destination type. Returns true if 138 // successful and false otherwise. 139 template <typename Dst> AssignIfValid(Dst * result)140 constexpr bool AssignIfValid(Dst* result) const { 141 return IsValid<Dst>() ? ((*result = static_cast<Dst>(state_.value())), true) 142 : false; 143 } 144 145 // ValueOrDie() - The primary accessor for the underlying value. If the 146 // current state is not valid it will CHECK and crash. 147 // A range checked destination type can be supplied using the Dst template 148 // parameter, which will trigger a CHECK if the value is not in bounds for 149 // the destination. 150 // The CHECK behavior can be overridden by supplying a handler as a 151 // template parameter, for test code, etc. However, the handler cannot access 152 // the underlying value, and it is not available through other means. 153 template <typename Dst = T, class CheckHandler = CheckOnFailure> ValueOrDie()154 constexpr StrictNumeric<Dst> ValueOrDie() const { 155 return IsValid<Dst>() ? static_cast<Dst>(state_.value()) 156 : CheckHandler::template HandleFailure<Dst>(); 157 } 158 159 // ValueOrDefault(T default_value) - A convenience method that returns the 160 // current value if the state is valid, and the supplied default_value for 161 // any other state. 162 // A range checked destination type can be supplied using the Dst template 163 // parameter. WARNING: This function may fail to compile or CHECK at runtime 164 // if the supplied default_value is not within range of the destination type. 165 template <typename Dst = T, typename Src> ValueOrDefault(const Src default_value)166 constexpr StrictNumeric<Dst> ValueOrDefault(const Src default_value) const { 167 return IsValid<Dst>() ? static_cast<Dst>(state_.value()) 168 : checked_cast<Dst>(default_value); 169 } 170 171 // Returns a checked numeric of the specified type, cast from the current 172 // CheckedNumeric. If the current state is invalid or the destination cannot 173 // represent the result then the returned CheckedNumeric will be invalid. 174 template <typename Dst> Cast()175 constexpr CheckedNumeric<typename UnderlyingType<Dst>::type> Cast() const { 176 return *this; 177 } 178 179 // This friend method is available solely for providing more detailed logging 180 // in the the tests. Do not implement it in production code, because the 181 // underlying values may change at any time. 182 template <typename U> 183 friend U GetNumericValueForTest(const CheckedNumeric<U>& src); 184 185 // Prototypes for the supported arithmetic operator overloads. 186 template <typename Src> 187 CheckedNumeric& operator+=(const Src rhs); 188 template <typename Src> 189 CheckedNumeric& operator-=(const Src rhs); 190 template <typename Src> 191 CheckedNumeric& operator*=(const Src rhs); 192 template <typename Src> 193 CheckedNumeric& operator/=(const Src rhs); 194 template <typename Src> 195 CheckedNumeric& operator%=(const Src rhs); 196 template <typename Src> 197 CheckedNumeric& operator<<=(const Src rhs); 198 template <typename Src> 199 CheckedNumeric& operator>>=(const Src rhs); 200 template <typename Src> 201 CheckedNumeric& operator&=(const Src rhs); 202 template <typename Src> 203 CheckedNumeric& operator|=(const Src rhs); 204 template <typename Src> 205 CheckedNumeric& operator^=(const Src rhs); 206 207 constexpr CheckedNumeric operator-() const { 208 return CheckedNumeric<T>( 209 NegateWrapper(state_.value()), 210 IsValid() && 211 (!std::is_signed<T>::value || std::is_floating_point<T>::value || 212 NegateWrapper(state_.value()) != 213 std::numeric_limits<T>::lowest())); 214 } 215 216 constexpr CheckedNumeric operator~() const { 217 return CheckedNumeric<decltype(InvertWrapper(T()))>( 218 InvertWrapper(state_.value()), IsValid()); 219 } 220 Abs()221 constexpr CheckedNumeric Abs() const { 222 return CheckedNumeric<T>( 223 AbsWrapper(state_.value()), 224 IsValid() && 225 (!std::is_signed<T>::value || std::is_floating_point<T>::value || 226 AbsWrapper(state_.value()) != std::numeric_limits<T>::lowest())); 227 } 228 229 template <typename U> Max(const U rhs)230 constexpr CheckedNumeric<typename MathWrapper<CheckedMaxOp, T, U>::type> Max( 231 const U rhs) const { 232 using R = typename UnderlyingType<U>::type; 233 using result_type = typename MathWrapper<CheckedMaxOp, T, U>::type; 234 // TODO(jschuh): This can be converted to the MathOp version and remain 235 // constexpr once we have C++14 support. 236 return CheckedNumeric<result_type>( 237 static_cast<result_type>( 238 IsGreater<T, R>::Test(state_.value(), Wrapper<U>::value(rhs)) 239 ? state_.value() 240 : Wrapper<U>::value(rhs)), 241 state_.is_valid() && Wrapper<U>::is_valid(rhs)); 242 } 243 244 template <typename U> Min(const U rhs)245 constexpr CheckedNumeric<typename MathWrapper<CheckedMinOp, T, U>::type> Min( 246 const U rhs) const { 247 using R = typename UnderlyingType<U>::type; 248 using result_type = typename MathWrapper<CheckedMinOp, T, U>::type; 249 // TODO(jschuh): This can be converted to the MathOp version and remain 250 // constexpr once we have C++14 support. 251 return CheckedNumeric<result_type>( 252 static_cast<result_type>( 253 IsLess<T, R>::Test(state_.value(), Wrapper<U>::value(rhs)) 254 ? state_.value() 255 : Wrapper<U>::value(rhs)), 256 state_.is_valid() && Wrapper<U>::is_valid(rhs)); 257 } 258 259 // This function is available only for integral types. It returns an unsigned 260 // integer of the same width as the source type, containing the absolute value 261 // of the source, and properly handling signed min. 262 constexpr CheckedNumeric<typename UnsignedOrFloatForSize<T>::type> UnsignedAbs()263 UnsignedAbs() const { 264 return CheckedNumeric<typename UnsignedOrFloatForSize<T>::type>( 265 SafeUnsignedAbs(state_.value()), state_.is_valid()); 266 } 267 268 CheckedNumeric& operator++() { 269 *this += 1; 270 return *this; 271 } 272 273 CheckedNumeric operator++(int) { 274 CheckedNumeric value = *this; 275 *this += 1; 276 return value; 277 } 278 279 CheckedNumeric& operator--() { 280 *this -= 1; 281 return *this; 282 } 283 284 CheckedNumeric operator--(int) { 285 CheckedNumeric value = *this; 286 *this -= 1; 287 return value; 288 } 289 290 // These perform the actual math operations on the CheckedNumerics. 291 // Binary arithmetic operations. 292 template <template <typename, typename, typename> class M, 293 typename L, 294 typename R> MathOp(const L lhs,const R rhs)295 static CheckedNumeric MathOp(const L lhs, const R rhs) { 296 using Math = typename MathWrapper<M, L, R>::math; 297 T result = 0; 298 bool is_valid = 299 Wrapper<L>::is_valid(lhs) && Wrapper<R>::is_valid(rhs) && 300 Math::Do(Wrapper<L>::value(lhs), Wrapper<R>::value(rhs), &result); 301 return CheckedNumeric<T>(result, is_valid); 302 }; 303 304 // Assignment arithmetic operations. 305 template <template <typename, typename, typename> class M, typename R> MathOp(const R rhs)306 CheckedNumeric& MathOp(const R rhs) { 307 using Math = typename MathWrapper<M, T, R>::math; 308 T result = 0; // Using T as the destination saves a range check. 309 bool is_valid = state_.is_valid() && Wrapper<R>::is_valid(rhs) && 310 Math::Do(state_.value(), Wrapper<R>::value(rhs), &result); 311 *this = CheckedNumeric<T>(result, is_valid); 312 return *this; 313 }; 314 315 private: 316 CheckedNumericState<T> state_; 317 318 template <typename Src> CheckedNumeric(Src value,bool is_valid)319 constexpr CheckedNumeric(Src value, bool is_valid) 320 : state_(value, is_valid) {} 321 322 // These wrappers allow us to handle state the same way for both 323 // CheckedNumeric and POD arithmetic types. 324 template <typename Src> 325 struct Wrapper { is_validWrapper326 static constexpr bool is_valid(Src) { return true; } valueWrapper327 static constexpr Src value(Src value) { return value; } 328 }; 329 330 template <typename Src> 331 struct Wrapper<CheckedNumeric<Src>> { 332 static constexpr bool is_valid(const CheckedNumeric<Src> v) { 333 return v.IsValid(); 334 } 335 static constexpr Src value(const CheckedNumeric<Src> v) { 336 return v.state_.value(); 337 } 338 }; 339 340 template <typename Src> 341 struct Wrapper<StrictNumeric<Src>> { 342 static constexpr bool is_valid(const StrictNumeric<Src>) { return true; } 343 static constexpr Src value(const StrictNumeric<Src> v) { 344 return static_cast<Src>(v); 345 } 346 }; 347 }; 348 349 // Convenience functions to avoid the ugly template disambiguator syntax. 350 template <typename Dst, typename Src> 351 constexpr bool IsValidForType(const CheckedNumeric<Src> value) { 352 return value.template IsValid<Dst>(); 353 } 354 355 template <typename Dst, typename Src> 356 constexpr StrictNumeric<Dst> ValueOrDieForType( 357 const CheckedNumeric<Src> value) { 358 return value.template ValueOrDie<Dst>(); 359 } 360 361 template <typename Dst, typename Src, typename Default> 362 constexpr StrictNumeric<Dst> ValueOrDefaultForType( 363 const CheckedNumeric<Src> value, 364 const Default default_value) { 365 return value.template ValueOrDefault<Dst>(default_value); 366 } 367 368 // These variadic templates work out the return types. 369 // TODO(jschuh): Rip all this out once we have C++14 non-trailing auto support. 370 template <template <typename, typename, typename> class M, 371 typename L, 372 typename R, 373 typename... Args> 374 struct ResultType; 375 376 template <template <typename, typename, typename> class M, 377 typename L, 378 typename R> 379 struct ResultType<M, L, R> { 380 using type = typename MathWrapper<M, L, R>::type; 381 }; 382 383 template <template <typename, typename, typename> class M, 384 typename L, 385 typename R, 386 typename... Args> 387 struct ResultType { 388 using type = 389 typename ResultType<M, typename ResultType<M, L, R>::type, Args...>::type; 390 }; 391 392 // Convience wrapper to return a new CheckedNumeric from the provided arithmetic 393 // or CheckedNumericType. 394 template <typename T> 395 constexpr CheckedNumeric<typename UnderlyingType<T>::type> MakeCheckedNum( 396 const T value) { 397 return value; 398 } 399 400 // These implement the variadic wrapper for the math operations. 401 template <template <typename, typename, typename> class M, 402 typename L, 403 typename R> 404 CheckedNumeric<typename MathWrapper<M, L, R>::type> ChkMathOp(const L lhs, 405 const R rhs) { 406 using Math = typename MathWrapper<M, L, R>::math; 407 return CheckedNumeric<typename Math::result_type>::template MathOp<M>(lhs, 408 rhs); 409 } 410 411 // General purpose wrapper template for arithmetic operations. 412 template <template <typename, typename, typename> class M, 413 typename L, 414 typename R, 415 typename... Args> 416 CheckedNumeric<typename ResultType<M, L, R, Args...>::type> 417 ChkMathOp(const L lhs, const R rhs, const Args... args) { 418 auto tmp = ChkMathOp<M>(lhs, rhs); 419 return tmp.IsValid() ? ChkMathOp<M>(tmp, args...) 420 : decltype(ChkMathOp<M>(tmp, args...))(tmp); 421 }; 422 423 // The following macros are just boilerplate for the standard arithmetic 424 // operator overloads and variadic function templates. A macro isn't the nicest 425 // solution, but it beats rewriting these over and over again. 426 #define BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME) \ 427 template <typename L, typename R, typename... Args> \ 428 CheckedNumeric<typename ResultType<Checked##NAME##Op, L, R, Args...>::type> \ 429 Check##NAME(const L lhs, const R rhs, const Args... args) { \ 430 return ChkMathOp<Checked##NAME##Op, L, R, Args...>(lhs, rhs, args...); \ 431 } 432 433 #define BASE_NUMERIC_ARITHMETIC_OPERATORS(NAME, OP, COMPOUND_OP) \ 434 /* Binary arithmetic operator for all CheckedNumeric operations. */ \ 435 template <typename L, typename R, \ 436 typename std::enable_if<IsCheckedOp<L, R>::value>::type* = \ 437 nullptr> \ 438 CheckedNumeric<typename MathWrapper<Checked##NAME##Op, L, R>::type> \ 439 operator OP(const L lhs, const R rhs) { \ 440 return decltype(lhs OP rhs)::template MathOp<Checked##NAME##Op>(lhs, rhs); \ 441 } \ 442 /* Assignment arithmetic operator implementation from CheckedNumeric. */ \ 443 template <typename L> \ 444 template <typename R> \ 445 CheckedNumeric<L>& CheckedNumeric<L>::operator COMPOUND_OP(const R rhs) { \ 446 return MathOp<Checked##NAME##Op>(rhs); \ 447 } \ 448 /* Variadic arithmetic functions that return CheckedNumeric. */ \ 449 BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME) 450 451 BASE_NUMERIC_ARITHMETIC_OPERATORS(Add, +, +=) 452 BASE_NUMERIC_ARITHMETIC_OPERATORS(Sub, -, -=) 453 BASE_NUMERIC_ARITHMETIC_OPERATORS(Mul, *, *=) 454 BASE_NUMERIC_ARITHMETIC_OPERATORS(Div, /, /=) 455 BASE_NUMERIC_ARITHMETIC_OPERATORS(Mod, %, %=) 456 BASE_NUMERIC_ARITHMETIC_OPERATORS(Lsh, <<, <<=) 457 BASE_NUMERIC_ARITHMETIC_OPERATORS(Rsh, >>, >>=) 458 BASE_NUMERIC_ARITHMETIC_OPERATORS(And, &, &=) 459 BASE_NUMERIC_ARITHMETIC_OPERATORS(Or, |, |=) 460 BASE_NUMERIC_ARITHMETIC_OPERATORS(Xor, ^, ^=) 461 BASE_NUMERIC_ARITHMETIC_VARIADIC(Max) 462 BASE_NUMERIC_ARITHMETIC_VARIADIC(Min) 463 464 #undef BASE_NUMERIC_ARITHMETIC_VARIADIC 465 #undef BASE_NUMERIC_ARITHMETIC_OPERATORS 466 467 // These are some extra StrictNumeric operators to support simple pointer 468 // arithmetic with our result types. Since wrapping on a pointer is always 469 // bad, we trigger the CHECK condition here. 470 template <typename L, typename R> 471 L* operator+(L* lhs, const StrictNumeric<R> rhs) { 472 uintptr_t result = CheckAdd(reinterpret_cast<uintptr_t>(lhs), 473 CheckMul(sizeof(L), static_cast<R>(rhs))) 474 .template ValueOrDie<uintptr_t>(); 475 return reinterpret_cast<L*>(result); 476 } 477 478 template <typename L, typename R> 479 L* operator-(L* lhs, const StrictNumeric<R> rhs) { 480 uintptr_t result = CheckSub(reinterpret_cast<uintptr_t>(lhs), 481 CheckMul(sizeof(L), static_cast<R>(rhs))) 482 .template ValueOrDie<uintptr_t>(); 483 return reinterpret_cast<L*>(result); 484 } 485 486 } // namespace internal 487 488 using internal::CheckedNumeric; 489 using internal::IsValidForType; 490 using internal::ValueOrDieForType; 491 using internal::ValueOrDefaultForType; 492 using internal::MakeCheckedNum; 493 using internal::CheckMax; 494 using internal::CheckMin; 495 using internal::CheckAdd; 496 using internal::CheckSub; 497 using internal::CheckMul; 498 using internal::CheckDiv; 499 using internal::CheckMod; 500 using internal::CheckLsh; 501 using internal::CheckRsh; 502 using internal::CheckAnd; 503 using internal::CheckOr; 504 using internal::CheckXor; 505 506 } // namespace base 507 508 #endif // BASE_NUMERICS_SAFE_MATH_H_ 509