Repository: bitcoin/bitcoin
File: src/util/overflow.h (C/C++)

Code before:
        }
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
            return std::numeric_limits<T>::min();
        }
    } else {
        if (std::numeric_limits<T>::max() - i < j) {
            return std::numeric_limits<T>::max();
        }
    }
    return i + j;
}

/**
 * @brief Left bit shift with overflow checking.
 * @param i The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return The result of the left shift, or std::nullopt in case of
 *         overflow or negative input value.
 */
template <std::unsigned_integral Output, std::integral Input>
constexpr std::optional<Output> CheckedLeftShift(Input i, unsigned shift) noexcept
{
    if constexpr (std::is_signed_v<Input>) {
        if (i < 0) return std::nullopt;
    }
    if (std::make_unsigned_t<Input>(i) > Output(std::numeric_limits<Output>::max() >> shift)) {
        return std::nullopt;
    }
    return i << shift;
}

/**
 * @brief Left bit shift with safe minimum and maximum values.
 * @param i The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return The result of the left shift, with the return value clamped
 *         between zero and the maximum Output value if overflow occurs.
 */
template <std::unsigned_integral Output, std::integral Input>
constexpr Output SaturatingLeftShift(Input i, unsigned shift) noexcept
{
    auto default_value{std::numeric_limits<Output>::max()};
    if constexpr (std::is_signed_v<Input>) {
        if (i < 0) default_value = 0;
    }
    return CheckedLeftShift<Output>(i, shift).value_or(default_value);
}

#endif // BITCOIN_UTIL_OVERFLOW_H


Review comment (bug):
in e0a541702def3a4c6cce8e44b6ebe8d608edad4e:

Right-shifting by more bits than the width of Output is UB, so we should probably add an extra check for that. I've also added some test cases, but interestingly they don't seem to trigger UBSan (without the `util/overflow.h` patch) on my machine:

<details>
<summary>git diff on e0a541702d</summary>

```diff
diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp
index 09ba278d3a..ae292d7761 100644
--- a/src/test/util_tests.cpp
+++ b/src/test/util_tests.cpp
@@ -1897,6 +1897,7 @@ void TestCheckedLeftShift()
         // Overflow cases
         BOOST_CHECK(!CheckedLeftShift<T>((MAX >> 1) + 1, 1));
         BOOST_CHECK(!CheckedLeftShift<T>(MAX, 1));
+        BOOST_CHECK(!CheckedLeftShift<T>(1, std::numeric_limits<T>::digits + 1));
     }
 }
 
@@ -1919,6 +1920,8 @@ void TestSaturatingLeftShift()
         // Saturation cases
         BOOST_CHECK_EQUAL(SaturatingLeftShift<T>((MAX >> 1) + 1, 1), MAX);
         BOOST_CHECK_EQUAL(SaturatingLeftShift<T>(MAX, 1), MAX);
+        BOOST_CHECK_EQUAL(SaturatingLeftShift<T>(-1, std::numeric_limits<T>::digits + 1), 0);
+        BOOST_CHECK_EQUAL(SaturatingLeftShift<T>(1, std::numeric_limits<T>::digits + 1), MAX);
     }
 }
 
diff --git a/src/util/overflow.h b/src/util/overflow.h
index a0698f5c69..d85f5b9c9d 100644
--- a/src/util/overflow.h
+++ b/src/util/overflow.h
@@ -61,7 +61,8 @@ constexpr std::optional<Output> CheckedLeftShift(Input i, unsigned shift) noexce
     if constexpr (std::is_signed_v<Input>) {
         if (i < 0) return std::nullopt;
     }
-    if (std::make_unsigned_t<Input>(i) > Output(std::numeric_limits<Output>::max() >> shift)) {
+    if (shift >= std::numeric_limits<Input>::digits ||
+        std::make_unsigned_t<Input>(i) > Output(std::numeric_limits<Output>::max() >> shift)) {
         return std::nullopt;
     }
     return i << shift;

```
</details>




Code after:
            return std::numeric_limits<T>::max();
        }
        if (i < 0 && j < std::numeric_limits<T>::min() - i) {
            return std::numeric_limits<T>::min();
        }
    } else {
        if (std::numeric_limits<T>::max() - i < j) {
            return std::numeric_limits<T>::max();
        }
    }
    return i + j;
}

/**
 * @brief Left bit shift with overflow checking.
 * @param input The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return (input * 2^shift) or nullopt if it would not fit in the return type.
 */
template <std::integral T>
constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
{
    if (shift == 0 || input == 0) return input;
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
    // If input << shift is too big to fit in T, return nullopt.
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
    return input << shift;
}

/**
 * @brief Left bit shift with safe minimum and maximum values.
 * @param input The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return (input * 2^shift) clamped to fit between the lowest and highest
 *         representable values of the type T.
 */
template <std::integral T>
constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
{
    if (auto result{CheckedLeftShift(input, shift)}) return *result;
    // If input << shift is too big to fit in T, return biggest positive or negative
    // number that fits.
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
}

#endif // BITCOIN_UTIL_OVERFLOW_H