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