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