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 
20 namespace v8 {
21 namespace base {
22 namespace internal {
23 
24 
25 // From Chromium's base/template_util.h:
26 
27 template<class T, T v>
28 struct integral_constant {
29   static const T value = v;
30   typedef T value_type;
31   typedef integral_constant<T, v> type;
32 };
33 
34 template <class T, T v> const T integral_constant<T, v>::value;
35 
36 typedef integral_constant<bool, true> true_type;
37 typedef integral_constant<bool, false> false_type;
38 
39 template <class T, class U> struct is_same : public false_type {};
40 template <class T> struct is_same<T, T> : true_type {};
41 
42 template<bool B, class T = void>
43 struct enable_if {};
44 
45 template<class T>
46 struct 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.
56 template <size_t Size, bool IsSigned>
57 struct IntegerForSizeAndSign;
58 template <>
59 struct IntegerForSizeAndSign<1, true> {
60   typedef int8_t type;
61 };
62 template <>
63 struct IntegerForSizeAndSign<1, false> {
64   typedef uint8_t type;
65 };
66 template <>
67 struct IntegerForSizeAndSign<2, true> {
68   typedef int16_t type;
69 };
70 template <>
71 struct IntegerForSizeAndSign<2, false> {
72   typedef uint16_t type;
73 };
74 template <>
75 struct IntegerForSizeAndSign<4, true> {
76   typedef int32_t type;
77 };
78 template <>
79 struct IntegerForSizeAndSign<4, false> {
80   typedef uint32_t type;
81 };
82 template <>
83 struct IntegerForSizeAndSign<8, true> {
84   typedef int64_t type;
85 };
86 template <>
87 struct 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 
95 template <typename Integer>
96 struct UnsignedIntegerForSize {
97   typedef typename enable_if<
98       std::numeric_limits<Integer>::is_integer,
99       typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
100 };
101 
102 template <typename Integer>
103 struct SignedIntegerForSize {
104   typedef typename enable_if<
105       std::numeric_limits<Integer>::is_integer,
106       typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
107 };
108 
109 template <typename Integer>
110 struct 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 
118 template <typename Integer>
119 struct 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 
126 template <typename T>
127 bool 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.
134 template <typename T>
135 T 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 
143 template <typename T>
144 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
145 CheckedAdd(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 
166 template <typename T>
167 typename enable_if<std::numeric_limits<T>::is_integer, T>::type
168 CheckedSub(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.
193 template <typename T>
194 typename enable_if<
195     std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
196     T>::type
197 CheckedMul(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 
205 template <typename T>
206 typename 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
210 CheckedMul(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 
235 template <typename T>
236 typename 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
240 CheckedMul(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.
248 template <typename T>
249 T 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 
264 template <typename T>
265 typename enable_if<
266     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
267     T>::type
268 CheckedMod(T x, T y, RangeConstraint* validity) {
269   *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
270   return x % y;
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 CheckedMod(T x, T y, RangeConstraint* validity) {
278   *validity = RANGE_VALID;
279   return x % y;
280 }
281 
282 template <typename T>
283 typename enable_if<
284     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
285     T>::type
286 CheckedNeg(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 
293 template <typename T>
294 typename enable_if<
295     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
296     T>::type
297 CheckedNeg(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 
304 template <typename T>
305 typename enable_if<
306     std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
307     T>::type
308 CheckedAbs(T value, RangeConstraint* validity) {
309   *validity =
310       value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
311   return std::abs(value);
312 }
313 
314 template <typename T>
315 typename enable_if<
316     std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
317     T>::type
318 CheckedAbs(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 
334 BASE_FLOAT_ARITHMETIC_STUBS(Add)
335 BASE_FLOAT_ARITHMETIC_STUBS(Sub)
336 BASE_FLOAT_ARITHMETIC_STUBS(Mul)
337 BASE_FLOAT_ARITHMETIC_STUBS(Div)
338 BASE_FLOAT_ARITHMETIC_STUBS(Mod)
339 
340 #undef BASE_FLOAT_ARITHMETIC_STUBS
341 
342 template <typename T>
343 typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
344     T value,
345     RangeConstraint*) {
346   return -value;
347 }
348 
349 template <typename T>
350 typename 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.
359 enum NumericRepresentation {
360   NUMERIC_INTEGER,
361   NUMERIC_FLOATING,
362   NUMERIC_UNKNOWN
363 };
364 
365 template <typename NumericType>
366 struct 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 
374 template <typename T, NumericRepresentation type =
375                           GetNumericRepresentation<T>::value>
376 class CheckedNumericState {};
377 
378 // Integrals require quite a bit of additional housekeeping to manage state.
379 template <typename T>
380 class 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.
420 template <typename T>
421 class 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.
479 enum ArithmeticPromotionCategory {
480   LEFT_PROMOTION,
481   RIGHT_PROMOTION,
482   DEFAULT_PROMOTION
483 };
484 
485 template <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) >
495 struct ArithmeticPromotion;
496 
497 template <typename Lhs, typename Rhs>
498 struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
499   typedef Lhs type;
500 };
501 
502 template <typename Lhs, typename Rhs>
503 struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
504   typedef Rhs type;
505 };
506 
507 template <typename Lhs, typename Rhs>
508 struct 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.
516 template <typename T, typename Lhs, typename Rhs>
517 struct 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