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