Branch data Line data Source code
1 : : // Copyright (c) 2021-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_UTIL_OVERFLOW_H
6 : : #define BITCOIN_UTIL_OVERFLOW_H
7 : :
8 : : #include <cassert>
9 : : #include <climits>
10 : : #include <concepts>
11 : : #include <limits>
12 : : #include <optional>
13 : : #include <type_traits>
14 : :
15 : : template <class T>
16 : 513047 : [[nodiscard]] bool AdditionOverflow(const T i, const T j) noexcept
17 : : {
18 : : static_assert(std::is_integral_v<T>, "Integral required.");
19 : : if constexpr (std::numeric_limits<T>::is_signed) {
20 [ + + + + : 5441 : return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
+ + ]
21 [ + + ]: 10 : (i < 0 && j < std::numeric_limits<T>::min() - i);
22 : : }
23 : 507606 : return std::numeric_limits<T>::max() - i < j;
24 : : }
25 : :
26 : : template <class T>
27 : 513047 : [[nodiscard]] std::optional<T> CheckedAdd(const T i, const T j) noexcept
28 : : {
29 [ + + ]: 513047 : if (AdditionOverflow(i, j)) {
30 : 12 : return std::nullopt;
31 : : }
32 : 513035 : return i + j;
33 : : }
34 : :
35 : : template <std::unsigned_integral T, std::unsigned_integral U>
36 : 608468 : [[nodiscard]] constexpr bool TrySub(T& i, const U j) noexcept
37 : : {
38 [ + - + - : 608468 : if (i < T{j}) return false;
+ - + - +
- + - + -
+ - + - ]
[ + - ]
39 : 608468 : i -= T{j};
40 : 608468 : return true;
41 : : }
42 : :
43 : : template <class T>
44 : 81 : [[nodiscard]] T SaturatingAdd(const T i, const T j) noexcept
45 : : {
46 : : if constexpr (std::numeric_limits<T>::is_signed) {
47 [ + + + + ]: 51 : if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48 : : return std::numeric_limits<T>::max();
49 : : }
50 [ + + + + ]: 31 : if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51 : : return std::numeric_limits<T>::min();
52 : : }
53 : : } else {
54 [ + + ]: 30 : if (std::numeric_limits<T>::max() - i < j) {
55 : : return std::numeric_limits<T>::max();
56 : : }
57 : : }
58 : 67 : return i + j;
59 : : }
60 : :
61 : : /**
62 : : * @brief Integer ceiling division (for unsigned values).
63 : : *
64 : : * Computes the smallest integer q such that q * divisor >= dividend.
65 : : * Both dividend and divisor must be unsigned, and divisor must be non-zero.
66 : : *
67 : : * The implementation avoids overflow that can occur with `(dividend + divisor - 1) / divisor`.
68 : : */
69 : : template <std::unsigned_integral Dividend, std::unsigned_integral Divisor>
70 : 57480302 : [[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
71 : : {
72 [ - + ]: 950532 : assert(divisor > 0);
73 [ + + + + ]: 57480302 : return dividend / divisor + (dividend % divisor != 0);
[ + + ][ - +
- + - + +
+ - + +
+ ]
74 : : }
75 : :
76 : : /**
77 : : * @brief Left bit shift with overflow checking.
78 : : * @param input The input value to be left shifted.
79 : : * @param shift The number of bits to left shift.
80 : : * @return (input * 2^shift) or nullopt if it would not fit in the return type.
81 : : */
82 : : template <std::integral T>
83 : 1 : constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
84 : : {
85 [ + - - + ]: 1 : if (shift == 0 || input == 0) return input;
86 : : // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87 [ - + ]: 1 : if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88 : : // If input << shift is too big to fit in T, return nullopt.
89 [ + - ]: 1 : if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90 : : if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91 : 0 : return input << shift;
92 : : }
93 : :
94 : : /**
95 : : * @brief Left bit shift with safe minimum and maximum values.
96 : : * @param input The input value to be left shifted.
97 : : * @param shift The number of bits to left shift.
98 : : * @return (input * 2^shift) clamped to fit between the lowest and highest
99 : : * representable values of the type T.
100 : : */
101 : : template <std::integral T>
102 : 0 : constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
103 : : {
104 [ # # ]: 0 : if (auto result{CheckedLeftShift(input, shift)}) return *result;
105 : : // If input << shift is too big to fit in T, return biggest positive or negative
106 : : // number that fits.
107 : : return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108 : : }
109 : :
110 : : #endif // BITCOIN_UTIL_OVERFLOW_H
|
