1// Copyright 2017 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_CHECKED_MATH_IMPL_H_
6#define BASE_NUMERICS_CHECKED_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 "base/numerics/safe_conversions.h"
18#include "base/numerics/safe_math_shared_impl.h"
19
20namespace base {
21namespace internal {
22
23template <typename T>
24constexpr bool CheckedAddImpl(T x, T y, T* result) {
25  static_assert(std::is_integral<T>::value, "Type must be integral");
26  // Since the value of x+y is undefined if we have a signed type, we compute
27  // it using the unsigned type of the same size.
28  using UnsignedDst = typename std::make_unsigned<T>::type;
29  using SignedDst = typename std::make_signed<T>::type;
30  UnsignedDst ux = static_cast<UnsignedDst>(x);
31  UnsignedDst uy = static_cast<UnsignedDst>(y);
32  UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy);
33  *result = static_cast<T>(uresult);
34  // Addition is valid if the sign of (x + y) is equal to either that of x or
35  // that of y.
36  return (std::is_signed<T>::value)
37             ? static_cast<SignedDst>((uresult ^ ux) & (uresult ^ uy)) >= 0
38             : uresult >= uy;  // Unsigned is either valid or underflow.
39}
40
41template <typename T, typename U, class Enable = void>
42struct CheckedAddOp {};
43
44template <typename T, typename U>
45struct CheckedAddOp<T,
46                    U,
47                    typename std::enable_if<std::is_integral<T>::value &&
48                                            std::is_integral<U>::value>::type> {
49  using result_type = typename MaxExponentPromotion<T, U>::type;
50  template <typename V>
51  static constexpr bool Do(T x, U y, V* result) {
52    // TODO(jschuh) Make this "constexpr if" once we're C++17.
53    if (CheckedAddFastOp<T, U>::is_supported)
54      return CheckedAddFastOp<T, U>::Do(x, y, result);
55
56    // Double the underlying type up to a full machine word.
57    using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type;
58    using Promotion =
59        typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value >
60                                   IntegerBitsPlusSign<intptr_t>::value),
61                                  typename BigEnoughPromotion<T, U>::type,
62                                  FastPromotion>::type;
63    // Fail if either operand is out of range for the promoted type.
64    // TODO(jschuh): This could be made to work for a broader range of values.
65    if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) ||
66                               !IsValueInRangeForNumericType<Promotion>(y))) {
67      return false;
68    }
69
70    Promotion presult = {};
71    bool is_valid = true;
72    if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
73      presult = static_cast<Promotion>(x) + static_cast<Promotion>(y);
74    } else {
75      is_valid = CheckedAddImpl(static_cast<Promotion>(x),
76                                static_cast<Promotion>(y), &presult);
77    }
78    *result = static_cast<V>(presult);
79    return is_valid && IsValueInRangeForNumericType<V>(presult);
80  }
81};
82
83template <typename T>
84constexpr bool CheckedSubImpl(T x, T y, T* result) {
85  static_assert(std::is_integral<T>::value, "Type must be integral");
86  // Since the value of x+y is undefined if we have a signed type, we compute
87  // it using the unsigned type of the same size.
88  using UnsignedDst = typename std::make_unsigned<T>::type;
89  using SignedDst = typename std::make_signed<T>::type;
90  UnsignedDst ux = static_cast<UnsignedDst>(x);
91  UnsignedDst uy = static_cast<UnsignedDst>(y);
92  UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy);
93  *result = static_cast<T>(uresult);
94  // Subtraction is valid if either x and y have same sign, or (x-y) and x have
95  // the same sign.
96  return (std::is_signed<T>::value)
97             ? static_cast<SignedDst>((uresult ^ ux) & (ux ^ uy)) >= 0
98             : x >= y;
99}
100
101template <typename T, typename U, class Enable = void>
102struct CheckedSubOp {};
103
104template <typename T, typename U>
105struct CheckedSubOp<T,
106                    U,
107                    typename std::enable_if<std::is_integral<T>::value &&
108                                            std::is_integral<U>::value>::type> {
109  using result_type = typename MaxExponentPromotion<T, U>::type;
110  template <typename V>
111  static constexpr bool Do(T x, U y, V* result) {
112    // TODO(jschuh) Make this "constexpr if" once we're C++17.
113    if (CheckedSubFastOp<T, U>::is_supported)
114      return CheckedSubFastOp<T, U>::Do(x, y, result);
115
116    // Double the underlying type up to a full machine word.
117    using FastPromotion = typename FastIntegerArithmeticPromotion<T, U>::type;
118    using Promotion =
119        typename std::conditional<(IntegerBitsPlusSign<FastPromotion>::value >
120                                   IntegerBitsPlusSign<intptr_t>::value),
121                                  typename BigEnoughPromotion<T, U>::type,
122                                  FastPromotion>::type;
123    // Fail if either operand is out of range for the promoted type.
124    // TODO(jschuh): This could be made to work for a broader range of values.
125    if (BASE_NUMERICS_UNLIKELY(!IsValueInRangeForNumericType<Promotion>(x) ||
126                               !IsValueInRangeForNumericType<Promotion>(y))) {
127      return false;
128    }
129
130    Promotion presult = {};
131    bool is_valid = true;
132    if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
133      presult = static_cast<Promotion>(x) - static_cast<Promotion>(y);
134    } else {
135      is_valid = CheckedSubImpl(static_cast<Promotion>(x),
136                                static_cast<Promotion>(y), &presult);
137    }
138    *result = static_cast<V>(presult);
139    return is_valid && IsValueInRangeForNumericType<V>(presult);
140  }
141};
142
143template <typename T>
144constexpr bool CheckedMulImpl(T x, T y, T* result) {
145  static_assert(std::is_integral<T>::value, "Type must be integral");
146  // Since the value of x*y is potentially undefined if we have a signed type,
147  // we compute it using the unsigned type of the same size.
148  using UnsignedDst = typename std::make_unsigned<T>::type;
149  using SignedDst = typename std::make_signed<T>::type;
150  const UnsignedDst ux = SafeUnsignedAbs(x);
151  const UnsignedDst uy = SafeUnsignedAbs(y);
152  UnsignedDst uresult = static_cast<UnsignedDst>(ux * uy);
153  const bool is_negative =
154      std::is_signed<T>::value && static_cast<SignedDst>(x ^ y) < 0;
155  *result = is_negative ? 0 - uresult : uresult;
156  // We have a fast out for unsigned identity or zero on the second operand.
157  // After that it's an unsigned overflow check on the absolute value, with
158  // a +1 bound for a negative result.
159  return uy <= UnsignedDst(!std::is_signed<T>::value || is_negative) ||
160         ux <= (std::numeric_limits<T>::max() + UnsignedDst(is_negative)) / uy;
161}
162
163template <typename T, typename U, class Enable = void>
164struct CheckedMulOp {};
165
166template <typename T, typename U>
167struct CheckedMulOp<T,
168                    U,
169                    typename std::enable_if<std::is_integral<T>::value &&
170                                            std::is_integral<U>::value>::type> {
171  using result_type = typename MaxExponentPromotion<T, U>::type;
172  template <typename V>
173  static constexpr bool Do(T x, U y, V* result) {
174    // TODO(jschuh) Make this "constexpr if" once we're C++17.
175    if (CheckedMulFastOp<T, U>::is_supported)
176      return CheckedMulFastOp<T, U>::Do(x, y, result);
177
178    using Promotion = typename FastIntegerArithmeticPromotion<T, U>::type;
179    // Verify the destination type can hold the result (always true for 0).
180    if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) ||
181                                !IsValueInRangeForNumericType<Promotion>(y)) &&
182                               x && y)) {
183      return false;
184    }
185
186    Promotion presult = {};
187    bool is_valid = true;
188    if (CheckedMulFastOp<Promotion, Promotion>::is_supported) {
189      // The fast op may be available with the promoted type.
190      is_valid = CheckedMulFastOp<Promotion, Promotion>::Do(x, y, &presult);
191    } else if (IsIntegerArithmeticSafe<Promotion, T, U>::value) {
192      presult = static_cast<Promotion>(x) * static_cast<Promotion>(y);
193    } else {
194      is_valid = CheckedMulImpl(static_cast<Promotion>(x),
195                                static_cast<Promotion>(y), &presult);
196    }
197    *result = static_cast<V>(presult);
198    return is_valid && IsValueInRangeForNumericType<V>(presult);
199  }
200};
201
202// Division just requires a check for a zero denominator or an invalid negation
203// on signed min/-1.
204template <typename T, typename U, class Enable = void>
205struct CheckedDivOp {};
206
207template <typename T, typename U>
208struct CheckedDivOp<T,
209                    U,
210                    typename std::enable_if<std::is_integral<T>::value &&
211                                            std::is_integral<U>::value>::type> {
212  using result_type = typename MaxExponentPromotion<T, U>::type;
213  template <typename V>
214  static constexpr bool Do(T x, U y, V* result) {
215    if (BASE_NUMERICS_UNLIKELY(!y))
216      return false;
217
218    // The overflow check can be compiled away if we don't have the exact
219    // combination of types needed to trigger this case.
220    using Promotion = typename BigEnoughPromotion<T, U>::type;
221    if (BASE_NUMERICS_UNLIKELY(
222            (std::is_signed<T>::value && std::is_signed<U>::value &&
223             IsTypeInRangeForNumericType<T, Promotion>::value &&
224             static_cast<Promotion>(x) ==
225                 std::numeric_limits<Promotion>::lowest() &&
226             y == static_cast<U>(-1)))) {
227      return false;
228    }
229
230    // This branch always compiles away if the above branch wasn't removed.
231    if (BASE_NUMERICS_UNLIKELY((!IsValueInRangeForNumericType<Promotion>(x) ||
232                                !IsValueInRangeForNumericType<Promotion>(y)) &&
233                               x)) {
234      return false;
235    }
236
237    Promotion presult = Promotion(x) / Promotion(y);
238    *result = static_cast<V>(presult);
239    return IsValueInRangeForNumericType<V>(presult);
240  }
241};
242
243template <typename T, typename U, class Enable = void>
244struct CheckedModOp {};
245
246template <typename T, typename U>
247struct CheckedModOp<T,
248                    U,
249                    typename std::enable_if<std::is_integral<T>::value &&
250                                            std::is_integral<U>::value>::type> {
251  using result_type = typename MaxExponentPromotion<T, U>::type;
252  template <typename V>
253  static constexpr bool Do(T x, U y, V* result) {
254    using Promotion = typename BigEnoughPromotion<T, U>::type;
255    if (BASE_NUMERICS_LIKELY(y)) {
256      Promotion presult = static_cast<Promotion>(x) % static_cast<Promotion>(y);
257      *result = static_cast<Promotion>(presult);
258      return IsValueInRangeForNumericType<V>(presult);
259    }
260    return false;
261  }
262};
263
264template <typename T, typename U, class Enable = void>
265struct CheckedLshOp {};
266
267// Left shift. Shifts less than 0 or greater than or equal to the number
268// of bits in the promoted type are undefined. Shifts of negative values
269// are undefined. Otherwise it is defined when the result fits.
270template <typename T, typename U>
271struct CheckedLshOp<T,
272                    U,
273                    typename std::enable_if<std::is_integral<T>::value &&
274                                            std::is_integral<U>::value>::type> {
275  using result_type = T;
276  template <typename V>
277  static constexpr bool Do(T x, U shift, V* result) {
278    // Disallow negative numbers and verify the shift is in bounds.
279    if (BASE_NUMERICS_LIKELY(!IsValueNegative(x) &&
280                             as_unsigned(shift) <
281                                 as_unsigned(std::numeric_limits<T>::digits))) {
282      // Shift as unsigned to avoid undefined behavior.
283      *result = static_cast<V>(as_unsigned(x) << shift);
284      // If the shift can be reversed, we know it was valid.
285      return *result >> shift == x;
286    }
287
288    // Handle the legal corner-case of a full-width signed shift of zero.
289    return std::is_signed<T>::value && !x &&
290           as_unsigned(shift) == as_unsigned(std::numeric_limits<T>::digits);
291  }
292};
293
294template <typename T, typename U, class Enable = void>
295struct CheckedRshOp {};
296
297// Right shift. Shifts less than 0 or greater than or equal to the number
298// of bits in the promoted type are undefined. Otherwise, it is always defined,
299// but a right shift of a negative value is implementation-dependent.
300template <typename T, typename U>
301struct CheckedRshOp<T,
302                    U,
303                    typename std::enable_if<std::is_integral<T>::value &&
304                                            std::is_integral<U>::value>::type> {
305  using result_type = T;
306  template <typename V>
307  static bool Do(T x, U shift, V* result) {
308    // Use the type conversion push negative values out of range.
309    if (BASE_NUMERICS_LIKELY(as_unsigned(shift) <
310                             IntegerBitsPlusSign<T>::value)) {
311      T tmp = x >> shift;
312      *result = static_cast<V>(tmp);
313      return IsValueInRangeForNumericType<V>(tmp);
314    }
315    return false;
316  }
317};
318
319template <typename T, typename U, class Enable = void>
320struct CheckedAndOp {};
321
322// For simplicity we support only unsigned integer results.
323template <typename T, typename U>
324struct CheckedAndOp<T,
325                    U,
326                    typename std::enable_if<std::is_integral<T>::value &&
327                                            std::is_integral<U>::value>::type> {
328  using result_type = typename std::make_unsigned<
329      typename MaxExponentPromotion<T, U>::type>::type;
330  template <typename V>
331  static constexpr bool Do(T x, U y, V* result) {
332    result_type tmp = static_cast<result_type>(x) & static_cast<result_type>(y);
333    *result = static_cast<V>(tmp);
334    return IsValueInRangeForNumericType<V>(tmp);
335  }
336};
337
338template <typename T, typename U, class Enable = void>
339struct CheckedOrOp {};
340
341// For simplicity we support only unsigned integers.
342template <typename T, typename U>
343struct CheckedOrOp<T,
344                   U,
345                   typename std::enable_if<std::is_integral<T>::value &&
346                                           std::is_integral<U>::value>::type> {
347  using result_type = typename std::make_unsigned<
348      typename MaxExponentPromotion<T, U>::type>::type;
349  template <typename V>
350  static constexpr bool Do(T x, U y, V* result) {
351    result_type tmp = static_cast<result_type>(x) | static_cast<result_type>(y);
352    *result = static_cast<V>(tmp);
353    return IsValueInRangeForNumericType<V>(tmp);
354  }
355};
356
357template <typename T, typename U, class Enable = void>
358struct CheckedXorOp {};
359
360// For simplicity we support only unsigned integers.
361template <typename T, typename U>
362struct CheckedXorOp<T,
363                    U,
364                    typename std::enable_if<std::is_integral<T>::value &&
365                                            std::is_integral<U>::value>::type> {
366  using result_type = typename std::make_unsigned<
367      typename MaxExponentPromotion<T, U>::type>::type;
368  template <typename V>
369  static constexpr bool Do(T x, U y, V* result) {
370    result_type tmp = static_cast<result_type>(x) ^ static_cast<result_type>(y);
371    *result = static_cast<V>(tmp);
372    return IsValueInRangeForNumericType<V>(tmp);
373  }
374};
375
376// Max doesn't really need to be implemented this way because it can't fail,
377// but it makes the code much cleaner to use the MathOp wrappers.
378template <typename T, typename U, class Enable = void>
379struct CheckedMaxOp {};
380
381template <typename T, typename U>
382struct CheckedMaxOp<
383    T,
384    U,
385    typename std::enable_if<std::is_arithmetic<T>::value &&
386                            std::is_arithmetic<U>::value>::type> {
387  using result_type = typename MaxExponentPromotion<T, U>::type;
388  template <typename V>
389  static constexpr bool Do(T x, U y, V* result) {
390    result_type tmp = IsGreater<T, U>::Test(x, y) ? static_cast<result_type>(x)
391                                                  : static_cast<result_type>(y);
392    *result = static_cast<V>(tmp);
393    return IsValueInRangeForNumericType<V>(tmp);
394  }
395};
396
397// Min doesn't really need to be implemented this way because it can't fail,
398// but it makes the code much cleaner to use the MathOp wrappers.
399template <typename T, typename U, class Enable = void>
400struct CheckedMinOp {};
401
402template <typename T, typename U>
403struct CheckedMinOp<
404    T,
405    U,
406    typename std::enable_if<std::is_arithmetic<T>::value &&
407                            std::is_arithmetic<U>::value>::type> {
408  using result_type = typename LowestValuePromotion<T, U>::type;
409  template <typename V>
410  static constexpr bool Do(T x, U y, V* result) {
411    result_type tmp = IsLess<T, U>::Test(x, y) ? static_cast<result_type>(x)
412                                               : static_cast<result_type>(y);
413    *result = static_cast<V>(tmp);
414    return IsValueInRangeForNumericType<V>(tmp);
415  }
416};
417
418// This is just boilerplate that wraps the standard floating point arithmetic.
419// A macro isn't the nicest solution, but it beats rewriting these repeatedly.
420#define BASE_FLOAT_ARITHMETIC_OPS(NAME, OP)                              \
421  template <typename T, typename U>                                      \
422  struct Checked##NAME##Op<                                              \
423      T, U,                                                              \
424      typename std::enable_if<std::is_floating_point<T>::value ||        \
425                              std::is_floating_point<U>::value>::type> { \
426    using result_type = typename MaxExponentPromotion<T, U>::type;       \
427    template <typename V>                                                \
428    static constexpr bool Do(T x, U y, V* result) {                      \
429      using Promotion = typename MaxExponentPromotion<T, U>::type;       \
430      Promotion presult = x OP y;                                        \
431      *result = static_cast<V>(presult);                                 \
432      return IsValueInRangeForNumericType<V>(presult);                   \
433    }                                                                    \
434  };
435
436BASE_FLOAT_ARITHMETIC_OPS(Add, +)
437BASE_FLOAT_ARITHMETIC_OPS(Sub, -)
438BASE_FLOAT_ARITHMETIC_OPS(Mul, *)
439BASE_FLOAT_ARITHMETIC_OPS(Div, /)
440
441#undef BASE_FLOAT_ARITHMETIC_OPS
442
443// Floats carry around their validity state with them, but integers do not. So,
444// we wrap the underlying value in a specialization in order to hide that detail
445// and expose an interface via accessors.
446enum NumericRepresentation {
447  NUMERIC_INTEGER,
448  NUMERIC_FLOATING,
449  NUMERIC_UNKNOWN
450};
451
452template <typename NumericType>
453struct GetNumericRepresentation {
454  static const NumericRepresentation value =
455      std::is_integral<NumericType>::value
456          ? NUMERIC_INTEGER
457          : (std::is_floating_point<NumericType>::value ? NUMERIC_FLOATING
458                                                        : NUMERIC_UNKNOWN);
459};
460
461template <typename T,
462          NumericRepresentation type = GetNumericRepresentation<T>::value>
463class CheckedNumericState {};
464
465// Integrals require quite a bit of additional housekeeping to manage state.
466template <typename T>
467class CheckedNumericState<T, NUMERIC_INTEGER> {
468 private:
469  // is_valid_ precedes value_ because member initializers in the constructors
470  // are evaluated in field order, and is_valid_ must be read when initializing
471  // value_.
472  bool is_valid_;
473  T value_;
474
475  // Ensures that a type conversion does not trigger undefined behavior.
476  template <typename Src>
477  static constexpr T WellDefinedConversionOrZero(const Src value,
478                                                 const bool is_valid) {
479    using SrcType = typename internal::UnderlyingType<Src>::type;
480    return (std::is_integral<SrcType>::value || is_valid)
481               ? static_cast<T>(value)
482               : static_cast<T>(0);
483  }
484
485 public:
486  template <typename Src, NumericRepresentation type>
487  friend class CheckedNumericState;
488
489  constexpr CheckedNumericState() : is_valid_(true), value_(0) {}
490
491  template <typename Src>
492  constexpr CheckedNumericState(Src value, bool is_valid)
493      : is_valid_(is_valid && IsValueInRangeForNumericType<T>(value)),
494        value_(WellDefinedConversionOrZero(value, is_valid_)) {
495    static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric.");
496  }
497
498  // Copy constructor.
499  template <typename Src>
500  constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
501      : is_valid_(rhs.IsValid()),
502        value_(WellDefinedConversionOrZero(rhs.value(), is_valid_)) {}
503
504  template <typename Src>
505  constexpr explicit CheckedNumericState(Src value)
506      : is_valid_(IsValueInRangeForNumericType<T>(value)),
507        value_(WellDefinedConversionOrZero(value, is_valid_)) {}
508
509  constexpr bool is_valid() const { return is_valid_; }
510  constexpr T value() const { return value_; }
511};
512
513// Floating points maintain their own validity, but need translation wrappers.
514template <typename T>
515class CheckedNumericState<T, NUMERIC_FLOATING> {
516 private:
517  T value_;
518
519  // Ensures that a type conversion does not trigger undefined behavior.
520  template <typename Src>
521  static constexpr T WellDefinedConversionOrNaN(const Src value,
522                                                const bool is_valid) {
523    using SrcType = typename internal::UnderlyingType<Src>::type;
524    return (StaticDstRangeRelationToSrcRange<T, SrcType>::value ==
525                NUMERIC_RANGE_CONTAINED ||
526            is_valid)
527               ? static_cast<T>(value)
528               : std::numeric_limits<T>::quiet_NaN();
529  }
530
531 public:
532  template <typename Src, NumericRepresentation type>
533  friend class CheckedNumericState;
534
535  constexpr CheckedNumericState() : value_(0.0) {}
536
537  template <typename Src>
538  constexpr CheckedNumericState(Src value, bool is_valid)
539      : value_(WellDefinedConversionOrNaN(value, is_valid)) {}
540
541  template <typename Src>
542  constexpr explicit CheckedNumericState(Src value)
543      : value_(WellDefinedConversionOrNaN(
544            value,
545            IsValueInRangeForNumericType<T>(value))) {}
546
547  // Copy constructor.
548  template <typename Src>
549  constexpr CheckedNumericState(const CheckedNumericState<Src>& rhs)
550      : value_(WellDefinedConversionOrNaN(
551            rhs.value(),
552            rhs.is_valid() && IsValueInRangeForNumericType<T>(rhs.value()))) {}
553
554  constexpr bool is_valid() const {
555    // Written this way because std::isfinite is not reliably constexpr.
556    return MustTreatAsConstexpr(value_)
557               ? value_ <= std::numeric_limits<T>::max() &&
558                     value_ >= std::numeric_limits<T>::lowest()
559               : std::isfinite(value_);
560  }
561  constexpr T value() const { return value_; }
562};
563
564}  // namespace internal
565}  // namespace base
566
567#endif  // BASE_NUMERICS_CHECKED_MATH_IMPL_H_
568