Harden SaferMultDiv with two GCD reductions, matching RoundedMulDiv
Categories
(Core :: Audio/Video, enhancement, P3)
Tracking
()
People
(Reporter: chunmin, Unassigned)
References
Details
(Keywords: good-first-bug)
Discovered while investigating bug 2053103 (public); a companion good-first-bug to the TimeUnit::ToTicksAtRate multiply-before-divide overflow, addressing the same multiply-before-divide-without-GCD-reduction pattern in a different media helper.
What this is
This is an optional robustness (hardening) change to a public math helper, suitable for a first-time contributor. It has a small, self-contained diff, a clear correctness argument, and a focused unit test. It does not fix a user-visible bug in any current caller (see "Is this reachable today?" below); its value is making the shared helper behave well for future and external callers. GCD stands for greatest common divisor throughout, and UB stands for undefined behavior.
Where
SaferMultDiv(int64_t aValue, uint64_t aMul, uint64_t aDiv) is defined at dom/media/VideoUtils.cpp:51 and declared at dom/media/VideoUtils.h:119. Its documented contract at dom/media/VideoUtils.h:117 is "Perform aValue * aMul / aDiv, reducing the possibility of overflow due to aValue * aMul overflowing." The current body is:
CheckedInt64 SaferMultDiv(int64_t aValue, uint64_t aMul, uint64_t aDiv) {
if (aMul > INT64_MAX || aDiv > INT64_MAX) {
return CheckedInt64(INT64_MAX) + 1; // Return an invalid checked int.
}
int64_t mul = AssertedCast<int64_t>(aMul);
int64_t div = AssertedCast<int64_t>(aDiv);
int64_t major = aValue / div;
int64_t remainder = aValue % div;
return CheckedInt64(remainder) * mul / div + CheckedInt64(major) * mul;
}
The reference implementation to match is mozilla::RoundedMulDiv at mozglue/misc/RoundedMulDiv.h:20, which performs two GCD reductions (lines 29-35) before its own quotient/remainder split, and whose in-file comment (lines 58-68) documents exactly the intermediate-overflow limitation addressed here. The GCD helper is mozilla::GCD at mfbt/MathAlgorithms.h:124 (exported as mozilla/MathAlgorithms.h); it is a binary-GCD template T GCD(T, T) that asserts both operands are non-negative and requires them to share one type.
Background: what SaferMultDiv computes, and where it wrongly reports overflow
The naive way to compute aValue * aMul / aDiv in fixed-width integers is (aValue * aMul) / aDiv, but the product aValue * aMul can overflow int64_t even when the final quotient is small, and signed integer overflow is undefined behavior in C++. SaferMultDiv avoids that by splitting the dividend: with major = aValue / aDiv and remainder = aValue % aDiv (C++ / and % truncate toward zero, so remainder carries the sign of aValue and |remainder| <= aDiv - 1), and since aValue = major*aDiv + remainder, the identity trunc(aValue*aMul/aDiv) = major*aMul + trunc(remainder*aMul/aDiv) holds. The function evaluates that with CheckedInt64, so when nothing overflows it returns the exact truncated-toward-zero result, and when an intermediate overflows it returns an invalid CheckedInt64 (validity, once lost, propagates through the remaining operations).
The split tames a large aValue, but it does not bound the term remainder * aMul. That intermediate is at most (aDiv - 1) * aMul regardless of how small the true result is. So whenever (aDiv - 1) * aMul exceeds INT64_MAX, there exist inputs (for example any aValue in [0, aDiv), giving major = 0) whose true result fits comfortably in int64_t yet for which remainder * aMul overflows and the function returns invalid. This is a conservative (spurious) overflow: the answer exists, but the helper refuses to compute it. The major * aMul term and the final sum, by contrast, track the true result and only overflow when the true result itself is near or beyond the int64_t boundary, so they are not conservative.
The refinement: two GCD reductions
aValue * aMul / aDiv is an exact rational number, and cancelling any factor common to numerator and denominator does not change it. Doing that before forming products gives the arithmetic smaller numbers to work with. RoundedMulDiv performs two such reductions in this order:
g = GCD(value, divisor); value /= g; divisor /= g; // reduction A
g = GCD(multiplier, divisor); multiplier /= g; divisor /= g; // reduction B, on the post-A divisor
Mapping the names onto SaferMultDiv (value = aValue, multiplier = aMul, divisor = aDiv): reduction B is gcd(aMul, aDiv), and reduction A is gcd(aValue, aDiv). Reduction B shrinks the multiplier and the divisor; reduction A shrinks the value and the divisor. Both are value-preserving because each cancels a genuine common factor.
Why reduction A is not redundant with the existing major/remainder split
It is tempting to think the split already "handles aValue", so a gcd(aValue, aDiv) reduction would add nothing. That is wrong, and here is the precise reason. The split decomposes aValue into major (which feeds major*aMul, a non-conservative term) and remainder (which feeds the conservative remainder*aMul). The split leaves |remainder| as large as aDiv - 1; it does not exploit any common factor between aValue and aDiv. Reduction A does exactly that, and it acts precisely on the conservative term.
Claim: let g1 = gcd(|aValue|, aDiv) and reduce to aValue' = aValue/g1, aDiv' = aDiv/g1. Then major is unchanged and remainder shrinks by exactly g1. Proof: write aValue = q*aDiv + r0 with q = trunc(aValue/aDiv) and r0 = aValue mod aDiv, |r0| < aDiv. Because g1 divides both aValue and aDiv, it also divides r0 = aValue - q*aDiv. Dividing the identity by g1 gives aValue' = q*aDiv' + (r0/g1) with |r0/g1| < aDiv' and the same sign as r0. That is precisely the truncating-division decomposition of aValue' by aDiv', so major' = q (unchanged) and remainder' = r0/g1. Hence the binding intermediate remainder'*aMul = (r0/g1)*aMul is exactly 1/g1 of the original r0*aMul. Reduction A therefore shrinks the exact quantity the split leaves unbounded, which is why the two are complementary rather than redundant.
Proposed code
Add the GCD header near the other includes in dom/media/VideoUtils.cpp:
#include "mozilla/MathAlgorithms.h" // for mozilla::GCD
and rewrite the function (the code lives inside namespace mozilla, so GCD resolves unqualified, exactly as in RoundedMulDiv):
CheckedInt64 SaferMultDiv(int64_t aValue, uint64_t aMul, uint64_t aDiv) {
if (aMul > INT64_MAX || aDiv > INT64_MAX) {
return CheckedInt64(INT64_MAX) + 1; // Return an invalid checked int.
}
// Cancel common factors of the exact value aValue * aMul / aDiv before
// forming any product, mirroring mozilla::RoundedMulDiv. The first reduction
// shrinks the remainder feeding the overflow-prone remainder * mul term; the
// second shrinks the multiplier and the divisor further. Both preserve the
// value exactly. GCD needs non-negative operands, so reduce against the
// magnitude of aValue and re-apply its sign via the signed division.
uint64_t magnitude = aValue < 0 ? ~static_cast<uint64_t>(aValue) + 1u
: static_cast<uint64_t>(aValue);
uint64_t g = GCD(magnitude, aDiv);
aValue /= static_cast<int64_t>(g);
aDiv /= g;
g = GCD(aMul, aDiv);
aMul /= g;
aDiv /= g;
int64_t mul = AssertedCast<int64_t>(aMul);
int64_t div = AssertedCast<int64_t>(aDiv);
int64_t major = aValue / div;
int64_t remainder = aValue % div;
return CheckedInt64(remainder) * mul / div + CheckedInt64(major) * mul;
}
Notes on correctness of the mechanics. The aMul > INT64_MAX || aDiv > INT64_MAX guard is kept and stays first: it preserves the existing contract and, because the reductions only shrink aMul and aDiv, it keeps the later AssertedCast<int64_t> conversions safe. The magnitude computation aValue < 0 ? ~static_cast<uint64_t>(aValue) + 1u : static_cast<uint64_t>(aValue) is the same two's-complement absolute value RoundedMulDiv uses; it is correct even for INT64_MIN, whose magnitude 2^63 does not fit int64_t but does fit uint64_t. GCD(magnitude, aDiv) and GCD(aMul, aDiv) are each called with two uint64_t operands, satisfying the template's same-type and non-negativity requirements. Reducing the signed value with aValue /= static_cast<int64_t>(g) is exact because g divides |aValue|, and it preserves the sign; the cast is safe because g <= aDiv <= INT64_MAX, and the division cannot overflow because g > 0 (there is no INT64_MIN / -1 case). As in RoundedMulDiv, g is at least 1 whenever aDiv >= 1, so the divisions by g are well-defined; aDiv must be non-zero, which is already a precondition of the current implementation (it divides by aDiv today).
Why the value is preserved
g1 = gcd(|aValue|, aDiv) divides both aValue and aDiv, so aValue/aDiv = (aValue/g1)/(aDiv/g1) as exact rationals; likewise reduction B preserves aMul/(post-A aDiv). Therefore the real number aValue*aMul/aDiv is unchanged by either reduction, and truncation toward zero is a function of that real number alone. On every input where the current function already succeeds, the reduced function returns the identical value. This was checked independently with exact-integer models in python3, including the negative-value, zero, and INT64_MIN cases.
How much the valid input domain grows
Let g1 = gcd(aValue, aDiv) and g2 = gcd(aMul, aDiv/g1) (the divisor reduction B sees, after A). After both reductions the multiplier is aMul/g2, the divisor is aDiv/(g1*g2), and the remainder magnitude is at most aDiv/(g1*g2) - 1, so the worst-case binding intermediate is (aDiv/(g1*g2) - 1) * (aMul/g2), which is roughly aDiv*aMul / (g1 * g2^2) versus the baseline (aDiv - 1)*aMul of about aDiv*aMul.
Reading off the contributions: reduction A shrinks the divisor, and hence the remainder's upper bound, by g1, but leaves the multiplier untouched, so on its own it shrinks the intermediate linearly, by about g1. Reduction B shrinks both the multiplier and the divisor by g2, so on its own it shrinks the intermediate quadratically, by about g2^2. Combined, the divisor (and thus the remainder bound) collapses by exactly the product g1*g2 of the two GCDs, while the multiplier collapses by g2, giving the overall g1*g2^2 on the binding remainder*mul product. Equivalently, the helper stays valid roughly a factor g1*g2 further along the divisor axis and a factor g2 further along the multiplier axis before it conservatively overflows. When the operands are coprime along a given axis, that reduction is 1 and costs nothing but a GCD call.
Residual limitation (this is genuine overflow, correctly reported)
The reductions only remove conservative overflow attributable to shared factors. If aValue, aMul, and aDiv are mutually coprime (g1 = g2 = 1), nothing can be cancelled; and if the true result genuinely exceeds the int64_t range, the function still returns an invalid CheckedInt64. That is correct behavior, not conservatism: the answer does not fit, so "invalid" is the right answer. Fully closing the remaining conservative gap for large coprime operands would require a 128-bit intermediate (for example __int128 or a multiply-with-carry primitive) rather than a GCD reduction; that is deliberately out of scope here. This change is the cheap, value-preserving, partial enlargement, maximally effective exactly when operands share large factors.
Test
Add to dom/media/gtest/TestVideoUtils.cpp (already registered in dom/media/gtest/moz.build, so no build-file change is needed). Every constant below was verified with exact integer arithmetic; INT64_MAX = 9223372036854775807.
TEST(VideoUtils, SaferMultDivGcdReduction)
{
// aValue and aDiv share a large factor while aMul is coprime to aDiv, so
// cancelling gcd(aMul, aDiv) does nothing; only cancelling gcd(aValue, aDiv)
// shrinks the remainder * aMul intermediate below the overflow threshold.
{
CheckedInt64 r =
SaferMultDiv(8000000000000000000, 7u, 6000000000000000000u);
EXPECT_TRUE(r.isValid());
EXPECT_EQ(r.value(), static_cast<int64_t>(9));
}
// Same shape with a negative value: the sign must be preserved.
{
CheckedInt64 r =
SaferMultDiv(-8000000000000000000, 7u, 6000000000000000000u);
EXPECT_TRUE(r.isValid());
EXPECT_EQ(r.value(), static_cast<int64_t>(-9));
}
// aMul and aDiv share the factor 2e18 (reducing to 3/2) while aValue is
// coprime to aDiv, so here cancelling gcd(aMul, aDiv) is what avoids overflow.
{
CheckedInt64 r = SaferMultDiv(3999999999999999999, 6000000000000000000u,
4000000000000000000u);
EXPECT_TRUE(r.isValid());
EXPECT_EQ(r.value(), static_cast<int64_t>(5999999999999999998));
}
// Fully coprime operands whose exact result exceeds int64_t: no factor can be
// cancelled and the overflow is real, so invalid is the correct answer.
{
CheckedInt64 r = SaferMultDiv(INT64_MAX, 7u, 3u);
EXPECT_FALSE(r.isValid());
}
}
Run it with ./mach gtest 'VideoUtils.SaferMultDivGcdReduction' (or 'VideoUtils.*').
The load-bearing case is the first one, (aValue, aMul, aDiv) = (8000000000000000000, 7, 6000000000000000000). Here gcd(aMul, aDiv) = gcd(7, 6e18) = 1, so reduction B (the earlier single-reduction proposal) does nothing and the input is rejected today exactly as it is with no reduction at all. Only reduction A, gcd(aValue, aDiv) = gcd(8e18, 6e18) = 2e18, saves it. This case also directly exhibits the proof above: major is 1 both before reduction (8e18 / 6e18) and after (4 / 3), while the remainder drops from 2e18 to 1, exactly 1/g1. The true result trunc(8e18 * 7 / 6e18) = 9 is tiny, yet without reduction A the binding intermediate remainder * aMul = 2000000000000000000 * 7 = 14000000000000000000 exceeds INT64_MAX and the current code returns invalid; with both reductions the intermediate is 1 * 7 = 7 and the result is a valid 9. The third case is the complement: there gcd(aValue, aDiv) = 1 so reduction A is the no-op and reduction B (gcd(aMul, aDiv) = 2e18, reducing to the ratio 3/2) does the work, returning a valid 5999999999999999998; today it is rejected because the intermediate is about 2.4e37. The two cases together show A and B are each independently load-bearing.
Is this reachable today? Recommendation
Through the three current callers the conservative overflow cannot be triggered, so this is hardening rather than a bug fix. FramesToUsecs (dom/media/VideoUtils.cpp:65) calls SaferMultDiv(aFrames, USECS_PER_S, aRate) and UsecsToFrames (dom/media/VideoUtils.cpp:71) calls SaferMultDiv(aUsecs, aRate, USECS_PER_S), where USECS_PER_S = 1000000 and aRate is a uint32_t (at most about 4.295e9). The worst-case (aDiv - 1)*aMul there is about 1e6 * 4.295e9 = 4.3e15, three orders of magnitude below INT64_MAX, so it never conservatively overflows. AudioSink.cpp:472 calls SaferMultDiv(mFramesParsed, newRate, oldRate) with two uint32_t sample rates; the intermediate crosses INT64_MAX only if a rate exceeds about 3.04e9 Hz (roughly 3 GHz), which is physically absurd, and realistic maxima (768000 Hz or less) keep it around 6e11, seven orders of magnitude under the limit. None of these callers passes operands with a large shared factor either, so for them the reductions are a no-op that merely costs a couple of GCD calls per invocation.
The value of the change is therefore the robustness of the public helper for future in-tree and external callers, which the header contract already advertises ("reducing the possibility of overflow"). It is provably value-preserving and only widens the set of inputs it accepts. Recommendation: land it as optional hardening, a good candidate for a good-first-bug. It is the same "multiply-before-divide, then reduce by GCD" family as the separate TimeUnit::ToTicksAtRate bug, and it reuses the exact reduction pattern already established in mozilla::RoundedMulDiv.
Description
•