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

Code before:
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:

Saturated left shifting a 0-input should probably always return a 0-output, so suggested update (+ tests, one depending on my [other comment re right-shift UB](https://github.com/bitcoin/bitcoin/pull/31483#discussion_r1913008528)):

<details>
<summary>git diff on e0a541702d</summary>

```diff
diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp
index 09ba278d3a..07b98be446 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>(0, std::numeric_limits<T>::digits + 1));  // TODO: requires right-shift overflow check to pass
     }
 }
 
@@ -1919,6 +1920,7 @@ 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>(0, std::numeric_limits<T>::digits + 1), 0);
     }
 }
 
diff --git a/src/util/overflow.h b/src/util/overflow.h
index a0698f5c69..f9e1fe4e82 100644
--- a/src/util/overflow.h
+++ b/src/util/overflow.h
@@ -77,10 +77,7 @@ constexpr std::optional<Output> CheckedLeftShift(Input i, unsigned shift) noexce
 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;
-    }
+    auto default_value{i <= 0 ? 0 : std::numeric_limits<Output>::max()};
     return CheckedLeftShift<Output>(i, shift).value_or(default_value);
 }
 

```
</details>




Code after:
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