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