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