1 // Copyright 2014 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_SAFE_CONVERSIONS_IMPL_H_
6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
7
8 #include <stdint.h>
9
10 #include <limits>
11 #include <type_traits>
12
13 #if defined(__GNUC__) || defined(__clang__)
14 #define PA_BASE_NUMERICS_LIKELY(x) __builtin_expect(!!(x), 1)
15 #define PA_BASE_NUMERICS_UNLIKELY(x) __builtin_expect(!!(x), 0)
16 #else
17 #define PA_BASE_NUMERICS_LIKELY(x) (x)
18 #define PA_BASE_NUMERICS_UNLIKELY(x) (x)
19 #endif
20
21 namespace partition_alloc::internal::base::internal {
22
23 // The std library doesn't provide a binary max_exponent for integers, however
24 // we can compute an analog using std::numeric_limits<>::digits.
25 template <typename NumericType>
26 struct MaxExponent {
27 static const int value = std::is_floating_point_v<NumericType>
28 ? std::numeric_limits<NumericType>::max_exponent
29 : std::numeric_limits<NumericType>::digits + 1;
30 };
31
32 // The number of bits (including the sign) in an integer. Eliminates sizeof
33 // hacks.
34 template <typename NumericType>
35 struct IntegerBitsPlusSign {
36 static const int value =
37 std::numeric_limits<NumericType>::digits + std::is_signed_v<NumericType>;
38 };
39
40 // Helper templates for integer manipulations.
41
42 template <typename Integer>
43 struct PositionOfSignBit {
44 static const size_t value = IntegerBitsPlusSign<Integer>::value - 1;
45 };
46
47 // Determines if a numeric value is negative without throwing compiler
48 // warnings on: unsigned(value) < 0.
49 template <typename T,
50 typename std::enable_if<std::is_signed_v<T>>::type* = nullptr>
IsValueNegative(T value)51 constexpr bool IsValueNegative(T value) {
52 static_assert(std::is_arithmetic_v<T>, "Argument must be numeric.");
53 return value < 0;
54 }
55
56 template <typename T,
57 typename std::enable_if<!std::is_signed_v<T>>::type* = nullptr>
IsValueNegative(T)58 constexpr bool IsValueNegative(T) {
59 static_assert(std::is_arithmetic_v<T>, "Argument must be numeric.");
60 return false;
61 }
62
63 // This performs a fast negation, returning a signed value. It works on unsigned
64 // arguments, but probably doesn't do what you want for any unsigned value
65 // larger than max / 2 + 1 (i.e. signed min cast to unsigned).
66 template <typename T>
ConditionalNegate(T x,bool is_negative)67 constexpr typename std::make_signed<T>::type ConditionalNegate(
68 T x,
69 bool is_negative) {
70 static_assert(std::is_integral_v<T>, "Type must be integral");
71 using SignedT = typename std::make_signed<T>::type;
72 using UnsignedT = typename std::make_unsigned<T>::type;
73 return static_cast<SignedT>((static_cast<UnsignedT>(x) ^
74 static_cast<UnsignedT>(-SignedT(is_negative))) +
75 is_negative);
76 }
77
78 // This performs a safe, absolute value via unsigned overflow.
79 template <typename T>
SafeUnsignedAbs(T value)80 constexpr typename std::make_unsigned<T>::type SafeUnsignedAbs(T value) {
81 static_assert(std::is_integral_v<T>, "Type must be integral");
82 using UnsignedT = typename std::make_unsigned<T>::type;
83 return IsValueNegative(value)
84 ? static_cast<UnsignedT>(0u - static_cast<UnsignedT>(value))
85 : static_cast<UnsignedT>(value);
86 }
87
88 // TODO(jschuh): Switch to std::is_constant_evaluated() once C++20 is supported.
89 // Alternately, the usage could be restructured for "consteval if" in C++23.
90 #define PA_IsConstantEvaluated() (__builtin_is_constant_evaluated())
91
92 // TODO(jschuh): Debug builds don't reliably propagate constants, so we restrict
93 // some accelerated runtime paths to release builds until this can be forced
94 // with consteval support in C++20 or C++23.
95 #if defined(NDEBUG)
96 constexpr bool kEnableAsmCode = true;
97 #else
98 constexpr bool kEnableAsmCode = false;
99 #endif
100
101 // Forces a crash, like a CHECK(false). Used for numeric boundary errors.
102 // Also used in a constexpr template to trigger a compilation failure on
103 // an error condition.
104 struct CheckOnFailure {
105 template <typename T>
HandleFailureCheckOnFailure106 static T HandleFailure() {
107 #if defined(_MSC_VER)
108 __debugbreak();
109 #elif defined(__GNUC__) || defined(__clang__)
110 __builtin_trap();
111 #else
112 ((void)(*(volatile char*)0 = 0));
113 #endif
114 return T();
115 }
116 };
117
118 enum IntegerRepresentation {
119 INTEGER_REPRESENTATION_UNSIGNED,
120 INTEGER_REPRESENTATION_SIGNED
121 };
122
123 // A range for a given nunmeric Src type is contained for a given numeric Dst
124 // type if both numeric_limits<Src>::max() <= numeric_limits<Dst>::max() and
125 // numeric_limits<Src>::lowest() >= numeric_limits<Dst>::lowest() are true.
126 // We implement this as template specializations rather than simple static
127 // comparisons to ensure type correctness in our comparisons.
128 enum NumericRangeRepresentation {
129 NUMERIC_RANGE_NOT_CONTAINED,
130 NUMERIC_RANGE_CONTAINED
131 };
132
133 // Helper templates to statically determine if our destination type can contain
134 // maximum and minimum values represented by the source type.
135
136 template <typename Dst,
137 typename Src,
138 IntegerRepresentation DstSign = std::is_signed_v<Dst>
139 ? INTEGER_REPRESENTATION_SIGNED
140 : INTEGER_REPRESENTATION_UNSIGNED,
141 IntegerRepresentation SrcSign = std::is_signed_v<Src>
142 ? INTEGER_REPRESENTATION_SIGNED
143 : INTEGER_REPRESENTATION_UNSIGNED>
144 struct StaticDstRangeRelationToSrcRange;
145
146 // Same sign: Dst is guaranteed to contain Src only if its range is equal or
147 // larger.
148 template <typename Dst, typename Src, IntegerRepresentation Sign>
149 struct StaticDstRangeRelationToSrcRange<Dst, Src, Sign, Sign> {
150 static const NumericRangeRepresentation value =
151 MaxExponent<Dst>::value >= MaxExponent<Src>::value
152 ? NUMERIC_RANGE_CONTAINED
153 : NUMERIC_RANGE_NOT_CONTAINED;
154 };
155
156 // Unsigned to signed: Dst is guaranteed to contain source only if its range is
157 // larger.
158 template <typename Dst, typename Src>
159 struct StaticDstRangeRelationToSrcRange<Dst,
160 Src,
161 INTEGER_REPRESENTATION_SIGNED,
162 INTEGER_REPRESENTATION_UNSIGNED> {
163 static const NumericRangeRepresentation value =
164 MaxExponent<Dst>::value > MaxExponent<Src>::value
165 ? NUMERIC_RANGE_CONTAINED
166 : NUMERIC_RANGE_NOT_CONTAINED;
167 };
168
169 // Signed to unsigned: Dst cannot be statically determined to contain Src.
170 template <typename Dst, typename Src>
171 struct StaticDstRangeRelationToSrcRange<Dst,
172 Src,
173 INTEGER_REPRESENTATION_UNSIGNED,
174 INTEGER_REPRESENTATION_SIGNED> {
175 static const NumericRangeRepresentation value = NUMERIC_RANGE_NOT_CONTAINED;
176 };
177
178 // This class wraps the range constraints as separate booleans so the compiler
179 // can identify constants and eliminate unused code paths.
180 class RangeCheck {
181 public:
182 constexpr RangeCheck(bool is_in_lower_bound, bool is_in_upper_bound)
183 : is_underflow_(!is_in_lower_bound), is_overflow_(!is_in_upper_bound) {}
184 constexpr RangeCheck() : is_underflow_(false), is_overflow_(false) {}
185 constexpr bool IsValid() const { return !is_overflow_ && !is_underflow_; }
186 constexpr bool IsInvalid() const { return is_overflow_ && is_underflow_; }
187 constexpr bool IsOverflow() const { return is_overflow_ && !is_underflow_; }
188 constexpr bool IsUnderflow() const { return !is_overflow_ && is_underflow_; }
189 constexpr bool IsOverflowFlagSet() const { return is_overflow_; }
190 constexpr bool IsUnderflowFlagSet() const { return is_underflow_; }
191 constexpr bool operator==(const RangeCheck rhs) const {
192 return is_underflow_ == rhs.is_underflow_ &&
193 is_overflow_ == rhs.is_overflow_;
194 }
195 constexpr bool operator!=(const RangeCheck rhs) const {
196 return !(*this == rhs);
197 }
198
199 private:
200 // Do not change the order of these member variables. The integral conversion
201 // optimization depends on this exact order.
202 const bool is_underflow_;
203 const bool is_overflow_;
204 };
205
206 // The following helper template addresses a corner case in range checks for
207 // conversion from a floating-point type to an integral type of smaller range
208 // but larger precision (e.g. float -> unsigned). The problem is as follows:
209 // 1. Integral maximum is always one less than a power of two, so it must be
210 // truncated to fit the mantissa of the floating point. The direction of
211 // rounding is implementation defined, but by default it's always IEEE
212 // floats, which round to nearest and thus result in a value of larger
213 // magnitude than the integral value.
214 // Example: float f = UINT_MAX; // f is 4294967296f but UINT_MAX
215 // // is 4294967295u.
216 // 2. If the floating point value is equal to the promoted integral maximum
217 // value, a range check will erroneously pass.
218 // Example: (4294967296f <= 4294967295u) // This is true due to a precision
219 // // loss in rounding up to float.
220 // 3. When the floating point value is then converted to an integral, the
221 // resulting value is out of range for the target integral type and
222 // thus is implementation defined.
223 // Example: unsigned u = (float)INT_MAX; // u will typically overflow to 0.
224 // To fix this bug we manually truncate the maximum value when the destination
225 // type is an integral of larger precision than the source floating-point type,
226 // such that the resulting maximum is represented exactly as a floating point.
227 template <typename Dst, typename Src, template <typename> class Bounds>
228 struct NarrowingRange {
229 using SrcLimits = std::numeric_limits<Src>;
230 using DstLimits = typename std::numeric_limits<Dst>;
231
232 // Computes the mask required to make an accurate comparison between types.
233 static const int kShift =
234 (MaxExponent<Src>::value > MaxExponent<Dst>::value &&
235 SrcLimits::digits < DstLimits::digits)
236 ? (DstLimits::digits - SrcLimits::digits)
237 : 0;
238 template <typename T,
239 typename std::enable_if<std::is_integral_v<T>>::type* = nullptr>
240
241 // Masks out the integer bits that are beyond the precision of the
242 // intermediate type used for comparison.
243 static constexpr T Adjust(T value) {
244 static_assert(std::is_same_v<T, Dst>, "");
245 static_assert(kShift < DstLimits::digits, "");
246 using UnsignedDst = typename std::make_unsigned_t<T>;
247 return static_cast<T>(ConditionalNegate(
248 SafeUnsignedAbs(value) & ~((UnsignedDst{1} << kShift) - UnsignedDst{1}),
249 IsValueNegative(value)));
250 }
251
252 template <
253 typename T,
254 typename std::enable_if<std::is_floating_point_v<T>>::type* = nullptr>
255 static constexpr T Adjust(T value) {
256 static_assert(std::is_same_v<T, Dst>, "");
257 static_assert(kShift == 0, "");
258 return value;
259 }
260
261 static constexpr Dst max() { return Adjust(Bounds<Dst>::max()); }
262 static constexpr Dst lowest() { return Adjust(Bounds<Dst>::lowest()); }
263 };
264
265 template <typename Dst,
266 typename Src,
267 template <typename>
268 class Bounds,
269 IntegerRepresentation DstSign = std::is_signed_v<Dst>
270 ? INTEGER_REPRESENTATION_SIGNED
271 : INTEGER_REPRESENTATION_UNSIGNED,
272 IntegerRepresentation SrcSign = std::is_signed_v<Src>
273 ? INTEGER_REPRESENTATION_SIGNED
274 : INTEGER_REPRESENTATION_UNSIGNED,
275 NumericRangeRepresentation DstRange =
276 StaticDstRangeRelationToSrcRange<Dst, Src>::value>
277 struct DstRangeRelationToSrcRangeImpl;
278
279 // The following templates are for ranges that must be verified at runtime. We
280 // split it into checks based on signedness to avoid confusing casts and
281 // compiler warnings on signed an unsigned comparisons.
282
283 // Same sign narrowing: The range is contained for normal limits.
284 template <typename Dst,
285 typename Src,
286 template <typename>
287 class Bounds,
288 IntegerRepresentation DstSign,
289 IntegerRepresentation SrcSign>
290 struct DstRangeRelationToSrcRangeImpl<Dst,
291 Src,
292 Bounds,
293 DstSign,
294 SrcSign,
295 NUMERIC_RANGE_CONTAINED> {
296 static constexpr RangeCheck Check(Src value) {
297 using SrcLimits = std::numeric_limits<Src>;
298 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
299 return RangeCheck(
300 static_cast<Dst>(SrcLimits::lowest()) >= DstLimits::lowest() ||
301 static_cast<Dst>(value) >= DstLimits::lowest(),
302 static_cast<Dst>(SrcLimits::max()) <= DstLimits::max() ||
303 static_cast<Dst>(value) <= DstLimits::max());
304 }
305 };
306
307 // Signed to signed narrowing: Both the upper and lower boundaries may be
308 // exceeded for standard limits.
309 template <typename Dst, typename Src, template <typename> class Bounds>
310 struct DstRangeRelationToSrcRangeImpl<Dst,
311 Src,
312 Bounds,
313 INTEGER_REPRESENTATION_SIGNED,
314 INTEGER_REPRESENTATION_SIGNED,
315 NUMERIC_RANGE_NOT_CONTAINED> {
316 static constexpr RangeCheck Check(Src value) {
317 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
318 return RangeCheck(value >= DstLimits::lowest(), value <= DstLimits::max());
319 }
320 };
321
322 // Unsigned to unsigned narrowing: Only the upper bound can be exceeded for
323 // standard limits.
324 template <typename Dst, typename Src, template <typename> class Bounds>
325 struct DstRangeRelationToSrcRangeImpl<Dst,
326 Src,
327 Bounds,
328 INTEGER_REPRESENTATION_UNSIGNED,
329 INTEGER_REPRESENTATION_UNSIGNED,
330 NUMERIC_RANGE_NOT_CONTAINED> {
331 static constexpr RangeCheck Check(Src value) {
332 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
333 return RangeCheck(
334 DstLimits::lowest() == Dst(0) || value >= DstLimits::lowest(),
335 value <= DstLimits::max());
336 }
337 };
338
339 // Unsigned to signed: Only the upper bound can be exceeded for standard limits.
340 template <typename Dst, typename Src, template <typename> class Bounds>
341 struct DstRangeRelationToSrcRangeImpl<Dst,
342 Src,
343 Bounds,
344 INTEGER_REPRESENTATION_SIGNED,
345 INTEGER_REPRESENTATION_UNSIGNED,
346 NUMERIC_RANGE_NOT_CONTAINED> {
347 static constexpr RangeCheck Check(Src value) {
348 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
349 using Promotion = decltype(Src() + Dst());
350 return RangeCheck(DstLimits::lowest() <= Dst(0) ||
351 static_cast<Promotion>(value) >=
352 static_cast<Promotion>(DstLimits::lowest()),
353 static_cast<Promotion>(value) <=
354 static_cast<Promotion>(DstLimits::max()));
355 }
356 };
357
358 // Signed to unsigned: The upper boundary may be exceeded for a narrower Dst,
359 // and any negative value exceeds the lower boundary for standard limits.
360 template <typename Dst, typename Src, template <typename> class Bounds>
361 struct DstRangeRelationToSrcRangeImpl<Dst,
362 Src,
363 Bounds,
364 INTEGER_REPRESENTATION_UNSIGNED,
365 INTEGER_REPRESENTATION_SIGNED,
366 NUMERIC_RANGE_NOT_CONTAINED> {
367 static constexpr RangeCheck Check(Src value) {
368 using SrcLimits = std::numeric_limits<Src>;
369 using DstLimits = NarrowingRange<Dst, Src, Bounds>;
370 using Promotion = decltype(Src() + Dst());
371 bool ge_zero = false;
372 // Converting floating-point to integer will discard fractional part, so
373 // values in (-1.0, -0.0) will truncate to 0 and fit in Dst.
374 if (std::is_floating_point_v<Src>) {
375 ge_zero = value > Src(-1);
376 } else {
377 ge_zero = value >= Src(0);
378 }
379 return RangeCheck(
380 ge_zero && (DstLimits::lowest() == 0 ||
381 static_cast<Dst>(value) >= DstLimits::lowest()),
382 static_cast<Promotion>(SrcLimits::max()) <=
383 static_cast<Promotion>(DstLimits::max()) ||
384 static_cast<Promotion>(value) <=
385 static_cast<Promotion>(DstLimits::max()));
386 }
387 };
388
389 // Simple wrapper for statically checking if a type's range is contained.
390 template <typename Dst, typename Src>
391 struct IsTypeInRangeForNumericType {
392 static const bool value = StaticDstRangeRelationToSrcRange<Dst, Src>::value ==
393 NUMERIC_RANGE_CONTAINED;
394 };
395
396 template <typename Dst,
397 template <typename> class Bounds = std::numeric_limits,
398 typename Src>
399 constexpr RangeCheck DstRangeRelationToSrcRange(Src value) {
400 static_assert(std::is_arithmetic_v<Src>, "Argument must be numeric.");
401 static_assert(std::is_arithmetic_v<Dst>, "Result must be numeric.");
402 static_assert(Bounds<Dst>::lowest() < Bounds<Dst>::max(), "");
403 return DstRangeRelationToSrcRangeImpl<Dst, Src, Bounds>::Check(value);
404 }
405
406 // Integer promotion templates used by the portable checked integer arithmetic.
407 template <size_t Size, bool IsSigned>
408 struct IntegerForDigitsAndSign;
409
410 #define PA_INTEGER_FOR_DIGITS_AND_SIGN(I) \
411 template <> \
412 struct IntegerForDigitsAndSign<IntegerBitsPlusSign<I>::value, \
413 std::is_signed_v<I>> { \
414 using type = I; \
415 }
416
417 PA_INTEGER_FOR_DIGITS_AND_SIGN(int8_t);
418 PA_INTEGER_FOR_DIGITS_AND_SIGN(uint8_t);
419 PA_INTEGER_FOR_DIGITS_AND_SIGN(int16_t);
420 PA_INTEGER_FOR_DIGITS_AND_SIGN(uint16_t);
421 PA_INTEGER_FOR_DIGITS_AND_SIGN(int32_t);
422 PA_INTEGER_FOR_DIGITS_AND_SIGN(uint32_t);
423 PA_INTEGER_FOR_DIGITS_AND_SIGN(int64_t);
424 PA_INTEGER_FOR_DIGITS_AND_SIGN(uint64_t);
425 #undef PA_INTEGER_FOR_DIGITS_AND_SIGN
426
427 // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
428 // support 128-bit math, then the ArithmeticPromotion template below will need
429 // to be updated (or more likely replaced with a decltype expression).
430 static_assert(IntegerBitsPlusSign<intmax_t>::value == 64,
431 "Max integer size not supported for this toolchain.");
432
433 template <typename Integer, bool IsSigned = std::is_signed_v<Integer>>
434 struct TwiceWiderInteger {
435 using type =
436 typename IntegerForDigitsAndSign<IntegerBitsPlusSign<Integer>::value * 2,
437 IsSigned>::type;
438 };
439
440 enum ArithmeticPromotionCategory {
441 LEFT_PROMOTION, // Use the type of the left-hand argument.
442 RIGHT_PROMOTION // Use the type of the right-hand argument.
443 };
444
445 // Determines the type that can represent the largest positive value.
446 template <typename Lhs,
447 typename Rhs,
448 ArithmeticPromotionCategory Promotion =
449 (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
450 ? LEFT_PROMOTION
451 : RIGHT_PROMOTION>
452 struct MaxExponentPromotion;
453
454 template <typename Lhs, typename Rhs>
455 struct MaxExponentPromotion<Lhs, Rhs, LEFT_PROMOTION> {
456 using type = Lhs;
457 };
458
459 template <typename Lhs, typename Rhs>
460 struct MaxExponentPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
461 using type = Rhs;
462 };
463
464 // Determines the type that can represent the lowest arithmetic value.
465 template <typename Lhs,
466 typename Rhs,
467 ArithmeticPromotionCategory Promotion =
468 std::is_signed_v<Lhs>
469 ? (std::is_signed_v<Rhs>
470 ? (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value
471 ? LEFT_PROMOTION
472 : RIGHT_PROMOTION)
473 : LEFT_PROMOTION)
474 : (std::is_signed_v<Rhs>
475 ? RIGHT_PROMOTION
476 : (MaxExponent<Lhs>::value < MaxExponent<Rhs>::value
477 ? LEFT_PROMOTION
478 : RIGHT_PROMOTION))>
479 struct LowestValuePromotion;
480
481 template <typename Lhs, typename Rhs>
482 struct LowestValuePromotion<Lhs, Rhs, LEFT_PROMOTION> {
483 using type = Lhs;
484 };
485
486 template <typename Lhs, typename Rhs>
487 struct LowestValuePromotion<Lhs, Rhs, RIGHT_PROMOTION> {
488 using type = Rhs;
489 };
490
491 // Determines the type that is best able to represent an arithmetic result.
492 template <
493 typename Lhs,
494 typename Rhs = Lhs,
495 bool is_intmax_type =
496 std::is_integral_v<typename MaxExponentPromotion<Lhs, Rhs>::type> &&
497 IntegerBitsPlusSign<typename MaxExponentPromotion<Lhs, Rhs>::type>::
498 value == IntegerBitsPlusSign<intmax_t>::value,
499 bool is_max_exponent = StaticDstRangeRelationToSrcRange<
500 typename MaxExponentPromotion<Lhs, Rhs>::type,
501 Lhs>::value == NUMERIC_RANGE_CONTAINED &&
502 StaticDstRangeRelationToSrcRange<
503 typename MaxExponentPromotion<Lhs, Rhs>::type,
504 Rhs>::value == NUMERIC_RANGE_CONTAINED>
505 struct BigEnoughPromotion;
506
507 // The side with the max exponent is big enough.
508 template <typename Lhs, typename Rhs, bool is_intmax_type>
509 struct BigEnoughPromotion<Lhs, Rhs, is_intmax_type, true> {
510 using type = typename MaxExponentPromotion<Lhs, Rhs>::type;
511 static const bool is_contained = true;
512 };
513
514 // We can use a twice wider type to fit.
515 template <typename Lhs, typename Rhs>
516 struct BigEnoughPromotion<Lhs, Rhs, false, false> {
517 using type =
518 typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type,
519 std::is_signed_v<Lhs> ||
520 std::is_signed_v<Rhs>>::type;
521 static const bool is_contained = true;
522 };
523
524 // No type is large enough.
525 template <typename Lhs, typename Rhs>
526 struct BigEnoughPromotion<Lhs, Rhs, true, false> {
527 using type = typename MaxExponentPromotion<Lhs, Rhs>::type;
528 static const bool is_contained = false;
529 };
530
531 // We can statically check if operations on the provided types can wrap, so we
532 // can skip the checked operations if they're not needed. So, for an integer we
533 // care if the destination type preserves the sign and is twice the width of
534 // the source.
535 template <typename T, typename Lhs, typename Rhs = Lhs>
536 struct IsIntegerArithmeticSafe {
537 static const bool value =
538 !std::is_floating_point_v<T> && !std::is_floating_point_v<Lhs> &&
539 !std::is_floating_point_v<Rhs> &&
540 std::is_signed_v<T> >= std::is_signed_v<Lhs> &&
541 IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Lhs>::value) &&
542 std::is_signed_v<T> >= std::is_signed_v<Rhs> &&
543 IntegerBitsPlusSign<T>::value >= (2 * IntegerBitsPlusSign<Rhs>::value);
544 };
545
546 // Promotes to a type that can represent any possible result of a binary
547 // arithmetic operation with the source types.
548 template <typename Lhs,
549 typename Rhs,
550 bool is_promotion_possible = IsIntegerArithmeticSafe<
551 typename std::conditional<std::is_signed_v<Lhs> ||
552 std::is_signed_v<Rhs>,
553 intmax_t,
554 uintmax_t>::type,
555 typename MaxExponentPromotion<Lhs, Rhs>::type>::value>
556 struct FastIntegerArithmeticPromotion;
557
558 template <typename Lhs, typename Rhs>
559 struct FastIntegerArithmeticPromotion<Lhs, Rhs, true> {
560 using type =
561 typename TwiceWiderInteger<typename MaxExponentPromotion<Lhs, Rhs>::type,
562 std::is_signed_v<Lhs> ||
563 std::is_signed_v<Rhs>>::type;
564 static_assert(IsIntegerArithmeticSafe<type, Lhs, Rhs>::value, "");
565 static const bool is_contained = true;
566 };
567
568 template <typename Lhs, typename Rhs>
569 struct FastIntegerArithmeticPromotion<Lhs, Rhs, false> {
570 using type = typename BigEnoughPromotion<Lhs, Rhs>::type;
571 static const bool is_contained = false;
572 };
573
574 // Extracts the underlying type from an enum.
575 template <typename T, bool is_enum = std::is_enum_v<T>>
576 struct ArithmeticOrUnderlyingEnum;
577
578 template <typename T>
579 struct ArithmeticOrUnderlyingEnum<T, true> {
580 using type = typename std::underlying_type<T>::type;
581 static const bool value = std::is_arithmetic_v<type>;
582 };
583
584 template <typename T>
585 struct ArithmeticOrUnderlyingEnum<T, false> {
586 using type = T;
587 static const bool value = std::is_arithmetic_v<type>;
588 };
589
590 // The following are helper templates used in the CheckedNumeric class.
591 template <typename T>
592 class CheckedNumeric;
593
594 template <typename T>
595 class ClampedNumeric;
596
597 template <typename T>
598 class StrictNumeric;
599
600 // Used to treat CheckedNumeric and arithmetic underlying types the same.
601 template <typename T>
602 struct UnderlyingType {
603 using type = typename ArithmeticOrUnderlyingEnum<T>::type;
604 static const bool is_numeric = std::is_arithmetic_v<type>;
605 static const bool is_checked = false;
606 static const bool is_clamped = false;
607 static const bool is_strict = false;
608 };
609
610 template <typename T>
611 struct UnderlyingType<CheckedNumeric<T>> {
612 using type = T;
613 static const bool is_numeric = true;
614 static const bool is_checked = true;
615 static const bool is_clamped = false;
616 static const bool is_strict = false;
617 };
618
619 template <typename T>
620 struct UnderlyingType<ClampedNumeric<T>> {
621 using type = T;
622 static const bool is_numeric = true;
623 static const bool is_checked = false;
624 static const bool is_clamped = true;
625 static const bool is_strict = false;
626 };
627
628 template <typename T>
629 struct UnderlyingType<StrictNumeric<T>> {
630 using type = T;
631 static const bool is_numeric = true;
632 static const bool is_checked = false;
633 static const bool is_clamped = false;
634 static const bool is_strict = true;
635 };
636
637 template <typename L, typename R>
638 struct IsCheckedOp {
639 static const bool value =
640 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric &&
641 (UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked);
642 };
643
644 template <typename L, typename R>
645 struct IsClampedOp {
646 static const bool value =
647 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric &&
648 (UnderlyingType<L>::is_clamped || UnderlyingType<R>::is_clamped) &&
649 !(UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked);
650 };
651
652 template <typename L, typename R>
653 struct IsStrictOp {
654 static const bool value =
655 UnderlyingType<L>::is_numeric && UnderlyingType<R>::is_numeric &&
656 (UnderlyingType<L>::is_strict || UnderlyingType<R>::is_strict) &&
657 !(UnderlyingType<L>::is_checked || UnderlyingType<R>::is_checked) &&
658 !(UnderlyingType<L>::is_clamped || UnderlyingType<R>::is_clamped);
659 };
660
661 // as_signed<> returns the supplied integral value (or integral castable
662 // Numeric template) cast as a signed integral of equivalent precision.
663 // I.e. it's mostly an alias for: static_cast<std::make_signed<T>::type>(t)
664 template <typename Src>
665 constexpr typename std::make_signed<
666 typename base::internal::UnderlyingType<Src>::type>::type
667 as_signed(const Src value) {
668 static_assert(std::is_integral_v<decltype(as_signed(value))>,
669 "Argument must be a signed or unsigned integer type.");
670 return static_cast<decltype(as_signed(value))>(value);
671 }
672
673 // as_unsigned<> returns the supplied integral value (or integral castable
674 // Numeric template) cast as an unsigned integral of equivalent precision.
675 // I.e. it's mostly an alias for: static_cast<std::make_unsigned<T>::type>(t)
676 template <typename Src>
677 constexpr typename std::make_unsigned<
678 typename base::internal::UnderlyingType<Src>::type>::type
679 as_unsigned(const Src value) {
680 static_assert(std::is_integral_v<decltype(as_unsigned(value))>,
681 "Argument must be a signed or unsigned integer type.");
682 return static_cast<decltype(as_unsigned(value))>(value);
683 }
684
685 template <typename L, typename R>
686 constexpr bool IsLessImpl(const L lhs,
687 const R rhs,
688 const RangeCheck l_range,
689 const RangeCheck r_range) {
690 return l_range.IsUnderflow() || r_range.IsOverflow() ||
691 (l_range == r_range && static_cast<decltype(lhs + rhs)>(lhs) <
692 static_cast<decltype(lhs + rhs)>(rhs));
693 }
694
695 template <typename L, typename R>
696 struct IsLess {
697 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
698 "Types must be numeric.");
699 static constexpr bool Test(const L lhs, const R rhs) {
700 return IsLessImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
701 DstRangeRelationToSrcRange<L>(rhs));
702 }
703 };
704
705 template <typename L, typename R>
706 constexpr bool IsLessOrEqualImpl(const L lhs,
707 const R rhs,
708 const RangeCheck l_range,
709 const RangeCheck r_range) {
710 return l_range.IsUnderflow() || r_range.IsOverflow() ||
711 (l_range == r_range && static_cast<decltype(lhs + rhs)>(lhs) <=
712 static_cast<decltype(lhs + rhs)>(rhs));
713 }
714
715 template <typename L, typename R>
716 struct IsLessOrEqual {
717 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
718 "Types must be numeric.");
719 static constexpr bool Test(const L lhs, const R rhs) {
720 return IsLessOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
721 DstRangeRelationToSrcRange<L>(rhs));
722 }
723 };
724
725 template <typename L, typename R>
726 constexpr bool IsGreaterImpl(const L lhs,
727 const R rhs,
728 const RangeCheck l_range,
729 const RangeCheck r_range) {
730 return l_range.IsOverflow() || r_range.IsUnderflow() ||
731 (l_range == r_range && static_cast<decltype(lhs + rhs)>(lhs) >
732 static_cast<decltype(lhs + rhs)>(rhs));
733 }
734
735 template <typename L, typename R>
736 struct IsGreater {
737 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
738 "Types must be numeric.");
739 static constexpr bool Test(const L lhs, const R rhs) {
740 return IsGreaterImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
741 DstRangeRelationToSrcRange<L>(rhs));
742 }
743 };
744
745 template <typename L, typename R>
746 constexpr bool IsGreaterOrEqualImpl(const L lhs,
747 const R rhs,
748 const RangeCheck l_range,
749 const RangeCheck r_range) {
750 return l_range.IsOverflow() || r_range.IsUnderflow() ||
751 (l_range == r_range && static_cast<decltype(lhs + rhs)>(lhs) >=
752 static_cast<decltype(lhs + rhs)>(rhs));
753 }
754
755 template <typename L, typename R>
756 struct IsGreaterOrEqual {
757 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
758 "Types must be numeric.");
759 static constexpr bool Test(const L lhs, const R rhs) {
760 return IsGreaterOrEqualImpl(lhs, rhs, DstRangeRelationToSrcRange<R>(lhs),
761 DstRangeRelationToSrcRange<L>(rhs));
762 }
763 };
764
765 template <typename L, typename R>
766 struct IsEqual {
767 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
768 "Types must be numeric.");
769 static constexpr bool Test(const L lhs, const R rhs) {
770 return DstRangeRelationToSrcRange<R>(lhs) ==
771 DstRangeRelationToSrcRange<L>(rhs) &&
772 static_cast<decltype(lhs + rhs)>(lhs) ==
773 static_cast<decltype(lhs + rhs)>(rhs);
774 }
775 };
776
777 template <typename L, typename R>
778 struct IsNotEqual {
779 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
780 "Types must be numeric.");
781 static constexpr bool Test(const L lhs, const R rhs) {
782 return DstRangeRelationToSrcRange<R>(lhs) !=
783 DstRangeRelationToSrcRange<L>(rhs) ||
784 static_cast<decltype(lhs + rhs)>(lhs) !=
785 static_cast<decltype(lhs + rhs)>(rhs);
786 }
787 };
788
789 // These perform the actual math operations on the CheckedNumerics.
790 // Binary arithmetic operations.
791 template <template <typename, typename> class C, typename L, typename R>
792 constexpr bool SafeCompare(const L lhs, const R rhs) {
793 static_assert(std::is_arithmetic_v<L> && std::is_arithmetic_v<R>,
794 "Types must be numeric.");
795 using Promotion = BigEnoughPromotion<L, R>;
796 using BigType = typename Promotion::type;
797 return Promotion::is_contained
798 // Force to a larger type for speed if both are contained.
799 ? C<BigType, BigType>::Test(
800 static_cast<BigType>(static_cast<L>(lhs)),
801 static_cast<BigType>(static_cast<R>(rhs)))
802 // Let the template functions figure it out for mixed types.
803 : C<L, R>::Test(lhs, rhs);
804 }
805
806 template <typename Dst, typename Src>
807 constexpr bool IsMaxInRangeForNumericType() {
808 return IsGreaterOrEqual<Dst, Src>::Test(std::numeric_limits<Dst>::max(),
809 std::numeric_limits<Src>::max());
810 }
811
812 template <typename Dst, typename Src>
813 constexpr bool IsMinInRangeForNumericType() {
814 return IsLessOrEqual<Dst, Src>::Test(std::numeric_limits<Dst>::lowest(),
815 std::numeric_limits<Src>::lowest());
816 }
817
818 template <typename Dst, typename Src>
819 constexpr Dst CommonMax() {
820 return !IsMaxInRangeForNumericType<Dst, Src>()
821 ? Dst(std::numeric_limits<Dst>::max())
822 : Dst(std::numeric_limits<Src>::max());
823 }
824
825 template <typename Dst, typename Src>
826 constexpr Dst CommonMin() {
827 return !IsMinInRangeForNumericType<Dst, Src>()
828 ? Dst(std::numeric_limits<Dst>::lowest())
829 : Dst(std::numeric_limits<Src>::lowest());
830 }
831
832 // This is a wrapper to generate return the max or min for a supplied type.
833 // If the argument is false, the returned value is the maximum. If true the
834 // returned value is the minimum.
835 template <typename Dst, typename Src = Dst>
836 constexpr Dst CommonMaxOrMin(bool is_min) {
837 return is_min ? CommonMin<Dst, Src>() : CommonMax<Dst, Src>();
838 }
839
840 } // namespace partition_alloc::internal::base::internal
841
842 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_
843