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