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