refactor: add overflow-safe `CeilDiv` helper and use it in unsigned callsites #34436

It really sticks out to me that the divisor is a compile time constant in all cases except flatfile and feefrac.

Have you considered having an overload to serve the most common usecase?

template <uint64_t Divisor, std::unsigned_integral Dividend>
[[nodiscard]] constexpr Dividend CeilDiv(const Dividend dividend)
{
    static_assert(Divisor > 0);
    return dividend / Divisor + (dividend % Divisor != 0);
}

Only drawback I see is that the order of operands gets reversed:

-    str.reserve(CeilDiv(input.size(), 5u) * 8);
+    str.reserve(CeilDiv<5>(input.size()) * 8);

Compile-time division by zero would be a cool feature, but I wouldn't expect it to catch anything in reality - we'd never explicitly add 0 as a divisor. Or if you mean that the division may not be optimized for powers of two, or that we would do the division needlessly twice (because of the modulo), please see https://godbolt.org/z/neM9E1Mae which indicates that both gcc and clang emit a single division and proper branchless shift sequences for powers of two, and assert-failure paths are placed out-of-line (without needing [[unlikely]]).

Only drawback I see is that the order of operands gets reversed

Agree, but maybe I don't understand what advantage it would have, I only see downsides.

Guess I wasn't trusting the compiler-optimizers enough and wanting to be more explicit with nailing down the divisor for it. Tried adding my CeilDiv<Divisor>() variant (https://godbolt.org/z/c888Gcbc8) and diffing the assembly outputs and it doesn't improve anything for neither GCC nor Clang. As you say, shifts and bitwise and's are already used when possible for instance.

Which results in, for example: CeilDiv<ELEM_ALIGN_BYTES>(bytes) And for the case of unknown divisors the function could perhaps be overloaded. @rustaceanrob, we have already discussed a similar attempt. I do not think having the divisor before the dividend helps with readability. What problem would that solve in your opinion? What is currently lacking?

I do not think having the divisor before the dividend helps with readability

I first explored this because I thought the first approach was strange to read. Perhaps matter of opinion.

What problem would that solve in your opinion?

In the example I produced I use a constant as the divisor. The compile time error rejects changes to constants that should be non-zero (and non-negative).

we'd never explicitly add 0 as a divisor.

Not intentionally, of course, but constants may change that are not present at the callsite.

Can you provide a realistic example where that would be useful? I don't want to swap the order of the operands; the diff is also simpler that way, and it's not obvious to me what the advantage would be.

I don't see constant divisors changing to 0 and no test catching it as a realistic scenario, but the confusion of A / B changing to CeilDiv<B>(A) would be real.

I thought the first approach was strange to read

https://github.com/bitcoin/bitcoin/blob/fab51e470e738944dfc832926b05019e8b70f8c6/test/functional/test_framework/util.py#L361-L369

https://www.mathworks.com/help/fixedpoint/ref/ceildiv.html

y = ceilDiv(x,d) returns the result of x/d rounded to the nearest integer value in the direction of positive infinity.

https://www.javaguides.net/2024/06/java-math-ceildiv-method.html

ceilDiv(long x, long y) public static long ceilDiv(long x, long y) Parameters: x: The dividend. y: The divisor.

Thanks for the examples, your format here is justified well with that context. I consider my concern resolved, but for the sake of completeness:

Can you provide a realistic example where that would be useful?

One such example is having a discount factor to encourage particular behavior, say FooDiscount = 4. If one later tries to change the factor to zero, as in this behavior should no longer be discounted, then the program would not compile.

Knew from before that there are multiple places using these types of expressions involving WITNESS_SCALE_FACTOR. Here is a somewhat minimal diff that applies to those places. It's sad that we allow expressing negative transaction sizes and weights in many places even after this diff... but I agree with deferring fixing that.

<details><summary>Diff, maybe makes sense as a second commit?</summary>

diff --git a/src/consensus/consensus.h b/src/consensus/consensus.h
index 71b5fe2468..bcfc1a0140 100644
--- a/src/consensus/consensus.h
+++ b/src/consensus/consensus.h
@@ -18,7 +18,7 @@ static const int64_t MAX_BLOCK_SIGOPS_COST = 80000;
 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
 static const int COINBASE_MATURITY = 100;
 
-static const int WITNESS_SCALE_FACTOR = 4;
+constexpr unsigned int WITNESS_SCALE_FACTOR{4};
 
 static const size_t MIN_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 60; // 60 is the lower bound for the size of a valid serialized CTransaction
 static const size_t MIN_SERIALIZABLE_TRANSACTION_WEIGHT = WITNESS_SCALE_FACTOR * 10; // 10 is the lower bound for the size of a serialized CTransaction
diff --git a/src/consensus/validation.h b/src/consensus/validation.h
index 37a40e767e..5cf0b45c86 100644
--- a/src/consensus/validation.h
+++ b/src/consensus/validation.h
@@ -129,15 +129,15 @@ class BlockValidationState : public ValidationState<BlockValidationResult> {};
 // using only serialization with and without witness data. As witness_size
 // is equal to total_size - stripped_size, this formula is identical to:
 // weight = (stripped_size * 3) + total_size.
-static inline int32_t GetTransactionWeight(const CTransaction& tx)
+static inline uint32_t GetTransactionWeight(const CTransaction& tx)
 {
     return ::GetSerializeSize(TX_NO_WITNESS(tx)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(tx));
 }
-static inline int64_t GetBlockWeight(const CBlock& block)
+static inline uint64_t GetBlockWeight(const CBlock& block)
 {
     return ::GetSerializeSize(TX_NO_WITNESS(block)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(block));
 }
-static inline int64_t GetTransactionInputWeight(const CTxIn& txin)
+static inline uint64_t GetTransactionInputWeight(const CTxIn& txin)
 {
     // scriptWitness size is added here because witnesses and txins are split up in segwit serialization.
     return ::GetSerializeSize(TX_NO_WITNESS(txin)) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(TX_WITH_WITNESS(txin)) + ::GetSerializeSize(txin.scriptWitness.stack);
diff --git a/src/core_io.cpp b/src/core_io.cpp
index 7492e9ca50..fdc9e2cbe7 100644
--- a/src/core_io.cpp
+++ b/src/core_io.cpp
@@ -28,6 +28,7 @@
 #include <undo.h>
 #include <univalue.h>
 #include <util/check.h>
+#include <util/overflow.h>
 #include <util/result.h>
 #include <util/strencodings.h>
 #include <util/string.h>
@@ -435,7 +436,7 @@ void TxToUniv(const CTransaction& tx, const uint256& block_hash, UniValue& entry
     entry.pushKV("hash", tx.GetWitnessHash().GetHex());
     entry.pushKV("version", tx.version);
     entry.pushKV("size", tx.ComputeTotalSize());
-    entry.pushKV("vsize", (GetTransactionWeight(tx) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR);
+    entry.pushKV("vsize", CeilDiv(GetTransactionWeight(tx), WITNESS_SCALE_FACTOR));
     entry.pushKV("weight", GetTransactionWeight(tx));
     entry.pushKV("locktime", tx.nLockTime);
 
diff --git a/src/kernel/mempool_entry.h b/src/kernel/mempool_entry.h
index 58824f7a80..cc3e64fa02 100644
--- a/src/kernel/mempool_entry.h
+++ b/src/kernel/mempool_entry.h
@@ -91,7 +91,7 @@ public:
         : TxGraph::Ref(std::move(ref)),
           tx{tx},
           nFee{fee},
-          nTxWeight{GetTransactionWeight(*tx)},
+          nTxWeight{static_cast<int32_t>(GetTransactionWeight(*tx))},
           nUsageSize{RecursiveDynamicUsage(tx)},
           nTime{time},
           entry_sequence{entry_sequence},
diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
index 46ec238c3b..4d20fe7c1e 100644
--- a/src/policy/policy.cpp
+++ b/src/policy/policy.cpp
@@ -373,22 +373,22 @@ bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& p
     return false;
 }
 
-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop)
+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
 {
     return std::max(weight, sigop_cost * bytes_per_sigop);
 }
 
-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop)
 {
-    return (GetSigOpsAdjustedWeight(nWeight, nSigOpCost, bytes_per_sigop) + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR;
+    return CeilDiv(GetSigOpsAdjustedWeight(weight, sigop_cost, bytes_per_sigop), WITNESS_SCALE_FACTOR);
 }
 
-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop)
 {
-    return GetVirtualTransactionSize(GetTransactionWeight(tx), nSigOpCost, bytes_per_sigop);
+    return GetVirtualTransactionSize(GetTransactionWeight(tx), sigop_cost, bytes_per_sigop);
 }
 
-int64_t GetVirtualTransactionInputSize(const CTxIn& txin, int64_t nSigOpCost, unsigned int bytes_per_sigop)
+uint64_t GetVirtualTransactionInputSize(const CTxIn& txin, uint64_t sigop_cost, unsigned int bytes_per_sigop)
 {
-    return GetVirtualTransactionSize(GetTransactionInputWeight(txin), nSigOpCost, bytes_per_sigop);
+    return GetVirtualTransactionSize(GetTransactionInputWeight(txin), sigop_cost, bytes_per_sigop);
 }
diff --git a/src/policy/policy.h b/src/policy/policy.h
index 35189d7133..5f7877ba75 100644
--- a/src/policy/policy.h
+++ b/src/policy/policy.h
@@ -12,6 +12,7 @@
 #include <script/interpreter.h>
 #include <script/solver.h>
 #include <util/feefrac.h>
+#include <util/overflow.h>
 
 #include <cstdint>
 #include <string>
@@ -175,9 +176,9 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
 bool SpendsNonAnchorWitnessProg(const CTransaction& tx, const CCoinsViewCache& prevouts);
 
 /** Compute the virtual transaction size (weight reinterpreted as bytes). */
-int64_t GetVirtualTransactionSize(int64_t nWeight, int64_t nSigOpCost, unsigned int bytes_per_sigop);
-int64_t GetVirtualTransactionSize(const CTransaction& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
-int64_t GetVirtualTransactionInputSize(const CTxIn& tx, int64_t nSigOpCost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionSize(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionSize(const CTransaction& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetVirtualTransactionInputSize(const CTxIn& tx, uint64_t sigop_cost, unsigned int bytes_per_sigop);
 
 static inline int64_t GetVirtualTransactionSize(const CTransaction& tx)
 {
@@ -189,8 +190,8 @@ static inline int64_t GetVirtualTransactionInputSize(const CTxIn& tx)
     return GetVirtualTransactionInputSize(tx, 0, 0);
 }
 
-int64_t GetSigOpsAdjustedWeight(int64_t weight, int64_t sigop_cost, unsigned int bytes_per_sigop);
+uint64_t GetSigOpsAdjustedWeight(uint64_t weight, uint64_t sigop_cost, unsigned int bytes_per_sigop);
 
-static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, (feerate.size + WITNESS_SCALE_FACTOR - 1) / WITNESS_SCALE_FACTOR}; }
+static inline FeePerVSize ToFeePerVSize(FeePerWeight feerate) { return {feerate.fee, static_cast<int32_t>(CeilDiv(static_cast<uint32_t>(feerate.size), WITNESS_SCALE_FACTOR))}; }
 
 #endif // BITCOIN_POLICY_POLICY_H
diff --git a/src/test/util/transaction_utils.cpp b/src/test/util/transaction_utils.cpp
index 7b1e2eb3ed..f69207774f 100644
--- a/src/test/util/transaction_utils.cpp
+++ b/src/test/util/transaction_utils.cpp
@@ -6,6 +6,7 @@
 #include <consensus/validation.h>
 #include <script/signingprovider.h>
 #include <test/util/transaction_utils.h>
+#include <util/overflow.h>
 
 CMutableTransaction BuildCreditingTransaction(const CScript& scriptPubKey, int nValue)
 {
@@ -71,14 +72,14 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
     return dummyTransactions;
 }
 
-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight)
+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight)
 {
     tx.vout.emplace_back(0, CScript() << OP_RETURN);
     auto unpadded_weight{GetTransactionWeight(CTransaction(tx))};
     assert(target_weight >= unpadded_weight);
 
     // determine number of needed padding bytes by converting weight difference to vbytes
-    auto dummy_vbytes = (target_weight - unpadded_weight + (WITNESS_SCALE_FACTOR - 1)) / WITNESS_SCALE_FACTOR;
+    auto dummy_vbytes = CeilDiv(target_weight - unpadded_weight, WITNESS_SCALE_FACTOR);
     // compensate for the increase of the compact-size encoded script length
     // (note that the length encoding of the unpadded output script needs one byte)
     dummy_vbytes -= GetSizeOfCompactSize(dummy_vbytes) - 1;
diff --git a/src/test/util/transaction_utils.h b/src/test/util/transaction_utils.h
index 867554f805..1b3df73e3d 100644
--- a/src/test/util/transaction_utils.h
+++ b/src/test/util/transaction_utils.h
@@ -29,7 +29,7 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst
 
 // bulk transaction to reach a certain target weight,
 // by appending a single output with padded output script
-void BulkTransaction(CMutableTransaction& tx, int32_t target_weight);
+void BulkTransaction(CMutableTransaction& tx, uint32_t target_weight);
 
 /**
  * Produce a satisfying script (scriptSig or witness).
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index edde923452..656f3e676d 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -167,7 +167,7 @@ TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *walle
     }
 
     // It's ok to use 0 as the number of sigops since we never create any pathological transaction.
-    return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight};
+    return TxSize{static_cast<int64_t>(GetVirtualTransactionSize(weight, 0, 0)), weight};
 }
 
 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control)

</details>

Also found: https://github.com/bitcoin/bitcoin/blob/9cad97f6cdf1bd660732cd10e844a6a7e0771ea0/src/wallet/coinselection.cpp#L457 Which uses signed integers and I understand wanting to punt on it for now... although maybe providing a signed CeilDiv() overload could be an alternative?

We should do all/most of these, I already had a few in this PR and reverted since it was getting too complicated to review - the risky ones should be done in separate commits/PRs. Thanks for checking them, my understanding is that you agree these should be done in a follow-up, to be safe, right?

I already had a few in this PR and reverted since it was getting too complicated to review - the risky ones should be done in separate commits/PRs.

Ah, I see. Went back and range-diffed 5bf64fbe6c6ced406027deaf2de964f228e7d806 to HEAD, I see you were on a similar track.

my understanding is that you agree these should be done in a follow-up, to be safe, right?

If the deadline to get this PR merged is tight (I saw #29678 depends on it), I agree it seems prudent to defer what is not currently included.

In other cases, I think it would be preferable to attempt something more complete in the scope of this PR. At least have a CeilDiv() variant for signed integers which just de-inlines the repetitive code without any additional guarantees (unlike the unsigned one protecting from overflow). But it's not a blocker.

Thanks for checking. Strictly speaking it's not that urgent, but I would like to separate the risk-free cheap refactor from doing it in risky places - my understand was that @sedited would prefer it be split. If not, I don't mind doing it in separate commits or separate PRs.