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