safe_conversions_impl.h 34 KB

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