[Issue 12958] core.checkedint.mulu is broken

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=12958

David Bregman <uber.daveb at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |uber.daveb at gmail.com

--- Comment #2 from David Bregman <uber.daveb at gmail.com> ---
That won't work because there can still be overflows when summing the partial
products. Consider this test case:

assert(mulu(2uL*uint.max,uint.max,overflow) == 18446744056529682434uL);
assert(overflow);

To do the full thing, I'm pretty sure we essentially need to use addu()
(inlined of course) to sum the partials.

I also noticed that addu should be simplified:
((x+y<x) || (x+y<y)) == (x+y < (x|y))

So here's my proposed solution (below): The overflow checks are written in such
a way that DMD is able to generate branchless code (I checked the assembler).

uint mulu(uint x, uint y, ref bool overflow)
{
    ulong r = cast(ulong)x*y;
    overflow |= !!(r >> 32);
    return cast(uint)r;
}

ulong mulu(ulong x, ulong y, ref bool overflow)
{
    // x = b:a, y = d:c
    immutable uint a = cast(uint)x;
    immutable uint b = x >> 32;
    immutable uint c = cast(uint)y;
    immutable uint d = y >> 32;

    immutable low = cast(ulong)a*c;
    immutable mid1 = cast(ulong)b*c;
    immutable mid2 = cast(ulong)a*d;
    immutable mid = mid1+mid2;

    overflow |= !!b & !!d;
    overflow |= mid < (mid1|mid2);
    overflow |= !!(mid >> 32);

    immutable mid_lo = mid<<32;
    immutable r = low + mid_lo;

    overflow |= r < (low|mid_lo);

    return r;
}

--