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