[Issue 7993] BigInt divide-by-1 error

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=7993



--- Comment #5 from c.m.brandenburg at gmail.com 2012-04-28 03:34:45 PDT ---
After debugging the code, I discovered the root cause. (Code snippets below.)

BigInt uses BigUint.divInt() for performing the underlying division operation.
BigUint.divInt() has two cases: (1) the divisor is a power of 2, and (2) the
divisor is not a power of 2.

In the case of dividing by 1, the divisor is a power of two and case #1 is
followed (if ((y&(-y))==y)). However, the number of bits to shift is 0. But
multibyteShr() explicitly states that the number of bits to shift must not be 0
(numbits must be in the range 1..31).

By changing BigUint.divInt() to treat y==1 as case #2—not a power of 2—rather
than case #1, the problem is fixed.

Code snippets: this is the runtime code that ships with my DMD/Phobos package.

/usr/include/d/std/internal/math/biguintcore.d:549:

    // return x / y
    static BigUint divInt(T)(BigUint x, T y) if ( is(T==uint) )
    {
        uint [] result = new BigDigit[x.data.length];
        if ((y&(-y))==y)
        {
            assert(y!=0, "BigUint division by zero");
            // perfect power of 2
            uint b = 0;
            for (;y!=1; y>>=1)
            {
                ++b;
            }
            multibyteShr(result, x.data, b);
        }
        else
        {
            result[] = x.data[];
            uint rem = multibyteDivAssign(result, y, 0);
        }
        return BigUint(removeLeadingZeros(result));
    }

/usr/include/d/std/internal/math/biguintnoasm.d:150

/** dest[] = src[] >> numbits
 *  numbits must be in the range 1..31
 */
void multibyteShr(uint [] dest, const(uint) [] src, uint numbits)
{
    ulong c = 0;
    for(ptrdiff_t i = dest.length; i!=0; --i)
    {
        c += (src[i-1] >>numbits) + (cast(ulong)(src[i-1]) << (64 - numbits));
        dest[i-1] = cast(uint)c;
        c >>>= 32;
   }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------