Line data Source code
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 43238620 : 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 43238620 : 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 43238620 : UnsignedDst ux = static_cast<UnsignedDst>(x);
150 43238620 : UnsignedDst uy = static_cast<UnsignedDst>(y);
151 43238620 : 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 86477240 : if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
156 : *validity = RANGE_VALID;
157 : else // Direction of wrap is inverse of result sign.
158 0 : *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 43238620 : 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 0 : UnsignedDst ux = static_cast<UnsignedDst>(x);
173 0 : UnsignedDst uy = static_cast<UnsignedDst>(y);
174 0 : 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 0 : if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
179 : *validity = RANGE_VALID;
180 : else // Direction of wrap is inverse of result sign.
181 0 : *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 0 : 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 97590 : static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
201 : *validity = DstRangeRelationToSrcRange<T>(tmp);
202 97590 : 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 43181042 : CheckedMul(T x, T y, RangeConstraint* validity) {
211 : // If either side is zero then the result will be zero.
212 43181042 : if (!x || !y) {
213 : return RANGE_VALID;
214 :
215 43176292 : } else if (x > 0) {
216 43176292 : if (y > 0)
217 43176292 : *validity =
218 : x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
219 : else
220 0 : *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
221 : : RANGE_UNDERFLOW;
222 :
223 : } else {
224 0 : if (y > 0)
225 0 : *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
226 : : RANGE_UNDERFLOW;
227 : else
228 0 : *validity =
229 : y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
230 : }
231 :
232 43176292 : 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 43177555 : 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_
|
