On 2026-07-30T18:40:37, Alexey Charkov <[email protected]> wrote: > lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem() > > fls() counts bits starting from 1, so shifting the operands right by > 1 + fls(high) discards one more bit of the divisor than intended. Both > functions estimate the quotient from the shifted operands and then fix > it up with a single decrement/increment, so an estimate that is off by > more than one cannot be repaired and the result comes out wrong. > > This only affects BITS_PER_LONG == 32, where these are the out-of-line > implementations; on 64-bit the header provides plain C division. > > The error is only reachable when the quotient is large, which needs a > divisor just above 2^32. For example: > > dividend = 15559272575191414037 > divisor = 4333540799 > expected = 3590429465 > actual = 3590429468 (off by 3) > > A sweep over 6.4M random operand pairs, stratified by the width of the > divisor's high word, mismatches a __int128 reference 8260 times before > this change and never after it. All failures have a divisor with one or > two significant bits above bit 32; uniformly random 64-bit divisors are > closer to 2^63 and yield quotients of ~1, which hides the problem. > > Port of Linux commit cdc94a374931 ("lib/div64.c: off by one in shift"), > which fixed the same code and cites [1]. > > In-tree users of div64_u64() that are built for 32-bit targets include > the Aspeed, Meson and Cadence TTC PWM drivers, the Versaclock and > wrpll-cln28hpc clock drivers, and the DWC3 USB core. > > Link: https://bugzilla.kernel.org/show_bug.cgi?id=202391 [1] > Fixes: 0342e335ba88 ("lib: div64: sync with Linux") > Signed-off-by: Alexey Charkov <[email protected]> > > lib/div64.c | 4 ++-- > 1 file changed, 2 insertions(+), 2 deletions(-)
Reviewed-by: Simon Glass <[email protected]>
