Coverage Report

Created: 2026-05-30 09:47

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/tmp/bitcoin/src/util/overflow.h
Line
Count
Source
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 <util/check.h>
9
10
#include <climits>
11
#include <concepts>
12
#include <limits>
13
#include <optional>
14
#include <type_traits>
15
16
template <std::integral T>
17
[[nodiscard]] bool AdditionOverflow(const T i, const T j) noexcept
18
12.3M
{
19
12.3M
    if constexpr (std::numeric_limits<T>::is_signed) {
20
17.9k
        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21
17.9k
               (i < 0 && j < std::numeric_limits<T>::min() - i);
22
17.9k
    }
23
0
    return std::numeric_limits<T>::max() - i < j;
24
12.3M
}
bool AdditionOverflow<unsigned long>(unsigned long, unsigned long)
Line
Count
Source
18
12.3M
{
19
    if constexpr (std::numeric_limits<T>::is_signed) {
20
        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21
               (i < 0 && j < std::numeric_limits<T>::min() - i);
22
    }
23
12.3M
    return std::numeric_limits<T>::max() - i < j;
24
12.3M
}
bool AdditionOverflow<unsigned int>(unsigned int, unsigned int)
Line
Count
Source
18
12
{
19
    if constexpr (std::numeric_limits<T>::is_signed) {
20
        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21
               (i < 0 && j < std::numeric_limits<T>::min() - i);
22
    }
23
12
    return std::numeric_limits<T>::max() - i < j;
24
12
}
bool AdditionOverflow<int>(int, int)
Line
Count
Source
18
24
{
19
24
    if constexpr (std::numeric_limits<T>::is_signed) {
20
24
        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21
24
               (i < 0 && j < std::numeric_limits<T>::min() - i);
22
24
    }
23
0
    return std::numeric_limits<T>::max() - i < j;
24
24
}
bool AdditionOverflow<long>(long, long)
Line
Count
Source
18
17.9k
{
19
17.9k
    if constexpr (std::numeric_limits<T>::is_signed) {
20
17.9k
        return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21
17.9k
               (i < 0 && j < std::numeric_limits<T>::min() - i);
22
17.9k
    }
23
0
    return std::numeric_limits<T>::max() - i < j;
24
17.9k
}
25
26
template <class T>
27
[[nodiscard]] std::optional<T> CheckedAdd(const T i, const T j) noexcept
28
12.3M
{
29
12.3M
    if (AdditionOverflow(i, j)) {
30
12
        return std::nullopt;
31
12
    }
32
12.3M
    return i + j;
33
12.3M
}
std::optional<unsigned long> CheckedAdd<unsigned long>(unsigned long, unsigned long)
Line
Count
Source
28
12.3M
{
29
12.3M
    if (AdditionOverflow(i, j)) {
30
0
        return std::nullopt;
31
0
    }
32
12.3M
    return i + j;
33
12.3M
}
std::optional<unsigned int> CheckedAdd<unsigned int>(unsigned int, unsigned int)
Line
Count
Source
28
12
{
29
12
    if (AdditionOverflow(i, j)) {
30
4
        return std::nullopt;
31
4
    }
32
8
    return i + j;
33
12
}
std::optional<int> CheckedAdd<int>(int, int)
Line
Count
Source
28
24
{
29
24
    if (AdditionOverflow(i, j)) {
30
8
        return std::nullopt;
31
8
    }
32
16
    return i + j;
33
24
}
std::optional<long> CheckedAdd<long>(long, long)
Line
Count
Source
28
17.9k
{
29
17.9k
    if (AdditionOverflow(i, j)) {
30
0
        return std::nullopt;
31
0
    }
32
17.9k
    return i + j;
33
17.9k
}
34
35
template <std::unsigned_integral T, std::unsigned_integral U>
36
[[nodiscard]] constexpr bool TrySub(T& i, const U j) noexcept
37
28.0M
{
38
28.0M
    if (i < T{j}) return false;
39
28.0M
    i -= T{j};
40
28.0M
    return true;
41
28.0M
}
bool TrySub<unsigned long, bool>(unsigned long&, bool)
Line
Count
Source
37
14.4M
{
38
14.4M
    if (i < T{j}) return false;
39
14.4M
    i -= T{j};
40
14.4M
    return true;
41
14.4M
}
bool TrySub<unsigned long, unsigned long>(unsigned long&, unsigned long)
Line
Count
Source
37
13.6M
{
38
13.6M
    if (i < T{j}) return false;
39
13.6M
    i -= T{j};
40
13.6M
    return true;
41
13.6M
}
42
43
template <std::integral T>
44
[[nodiscard]] T SaturatingAdd(const T i, const T j) noexcept
45
1.14k
{
46
1.14k
    if constexpr (std::numeric_limits<T>::is_signed) {
47
1.09k
        if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48
4
            return std::numeric_limits<T>::max();
49
4
        }
50
1.09k
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51
4
            return std::numeric_limits<T>::min();
52
4
        }
53
1.09k
    } else {
54
44
        if (std::numeric_limits<T>::max() - i < j) {
55
6
            return std::numeric_limits<T>::max();
56
6
        }
57
44
    }
58
1.12k
    return i + j;
59
1.14k
}
long SaturatingAdd<long>(long, long)
Line
Count
Source
45
1.07k
{
46
1.07k
    if constexpr (std::numeric_limits<T>::is_signed) {
47
1.07k
        if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48
0
            return std::numeric_limits<T>::max();
49
0
        }
50
1.07k
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51
0
            return std::numeric_limits<T>::min();
52
0
        }
53
    } else {
54
        if (std::numeric_limits<T>::max() - i < j) {
55
            return std::numeric_limits<T>::max();
56
        }
57
    }
58
1.07k
    return i + j;
59
1.07k
}
unsigned int SaturatingAdd<unsigned int>(unsigned int, unsigned int)
Line
Count
Source
45
12
{
46
    if constexpr (std::numeric_limits<T>::is_signed) {
47
        if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48
            return std::numeric_limits<T>::max();
49
        }
50
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51
            return std::numeric_limits<T>::min();
52
        }
53
12
    } else {
54
12
        if (std::numeric_limits<T>::max() - i < j) {
55
4
            return std::numeric_limits<T>::max();
56
4
        }
57
12
    }
58
8
    return i + j;
59
12
}
int SaturatingAdd<int>(int, int)
Line
Count
Source
45
24
{
46
24
    if constexpr (std::numeric_limits<T>::is_signed) {
47
24
        if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48
4
            return std::numeric_limits<T>::max();
49
4
        }
50
20
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51
4
            return std::numeric_limits<T>::min();
52
4
        }
53
    } else {
54
        if (std::numeric_limits<T>::max() - i < j) {
55
            return std::numeric_limits<T>::max();
56
        }
57
    }
58
16
    return i + j;
59
24
}
unsigned long SaturatingAdd<unsigned long>(unsigned long, unsigned long)
Line
Count
Source
45
32
{
46
    if constexpr (std::numeric_limits<T>::is_signed) {
47
        if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48
            return std::numeric_limits<T>::max();
49
        }
50
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51
            return std::numeric_limits<T>::min();
52
        }
53
32
    } else {
54
32
        if (std::numeric_limits<T>::max() - i < j) {
55
2
            return std::numeric_limits<T>::max();
56
2
        }
57
32
    }
58
30
    return i + j;
59
32
}
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
[[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
71
132M
{
72
132M
    assert(divisor > 0);
73
132M
    return dividend / divisor + (dividend % divisor != 0);
74
132M
}
auto CeilDiv<unsigned long, unsigned int>(unsigned long, unsigned int)
Line
Count
Source
71
1.85M
{
72
1.85M
    assert(divisor > 0);
73
1.85M
    return dividend / divisor + (dividend % divisor != 0);
74
1.85M
}
auto CeilDiv<unsigned long, unsigned long>(unsigned long, unsigned long)
Line
Count
Source
71
130M
{
72
130M
    assert(divisor > 0);
73
130M
    return dividend / divisor + (dividend % divisor != 0);
74
130M
}
auto CeilDiv<unsigned int, unsigned int>(unsigned int, unsigned int)
Line
Count
Source
71
272k
{
72
272k
    assert(divisor > 0);
73
272k
    return dividend / divisor + (dividend % divisor != 0);
74
272k
}
auto CeilDiv<unsigned int, unsigned long>(unsigned int, unsigned long)
Line
Count
Source
71
213k
{
72
213k
    assert(divisor > 0);
73
213k
    return dividend / divisor + (dividend % divisor != 0);
74
213k
}
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
constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
84
128
{
85
128
    if (shift == 0 || input == 0) return input;
86
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87
108
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88
    // If input << shift is too big to fit in T, return nullopt.
89
88
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90
64
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91
56
    return input << shift;
92
64
}
Unexecuted instantiation: std::optional<unsigned long long> CheckedLeftShift<unsigned long long>(unsigned long long, unsigned int)
std::optional<unsigned char> CheckedLeftShift<unsigned char>(unsigned char, unsigned int)
Line
Count
Source
84
20
{
85
20
    if (shift == 0 || input == 0) return input;
86
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87
16
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88
    // If input << shift is too big to fit in T, return nullopt.
89
12
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90
8
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91
8
    return input << shift;
92
8
}
std::optional<signed char> CheckedLeftShift<signed char>(signed char, unsigned int)
Line
Count
Source
84
34
{
85
34
    if (shift == 0 || input == 0) return input;
86
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87
30
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88
    // If input << shift is too big to fit in T, return nullopt.
89
26
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90
20
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91
16
    return input << shift;
92
20
}
std::optional<unsigned long> CheckedLeftShift<unsigned long>(unsigned long, unsigned int)
Line
Count
Source
84
40
{
85
40
    if (shift == 0 || input == 0) return input;
86
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87
32
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88
    // If input << shift is too big to fit in T, return nullopt.
89
24
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90
16
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91
16
    return input << shift;
92
16
}
std::optional<long> CheckedLeftShift<long>(long, unsigned int)
Line
Count
Source
84
34
{
85
34
    if (shift == 0 || input == 0) return input;
86
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87
30
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88
    // If input << shift is too big to fit in T, return nullopt.
89
26
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90
20
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91
16
    return input << shift;
92
20
}
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
constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
103
64
{
104
64
    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
26
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108
64
}
unsigned char SaturatingLeftShift<unsigned char>(unsigned char, unsigned int)
Line
Count
Source
103
10
{
104
10
    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
4
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108
10
}
signed char SaturatingLeftShift<signed char>(signed char, unsigned int)
Line
Count
Source
103
17
{
104
17
    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
7
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108
17
}
unsigned long SaturatingLeftShift<unsigned long>(unsigned long, unsigned int)
Line
Count
Source
103
20
{
104
20
    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
8
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108
20
}
long SaturatingLeftShift<long>(long, unsigned int)
Line
Count
Source
103
17
{
104
17
    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
7
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108
17
}
109
110
#endif // BITCOIN_UTIL_OVERFLOW_H