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