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