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

           Summary: BigInt divide-by-1 error
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: c.m.brandenburg@gmail.com


--- Comment #0 from c.m.brandenburg@gmail.com 2012-04-26 15:55:34 PDT ---
It seems that dividing a BigInt by 1 has the same effect as multiplying by 2.

The following program:

import std.bigint;
import std.stdio;

void main() {
  BigInt foo = 10;
  writeln(foo / 1);
  writeln(foo / 2);
}

Outputs:

$ ./main
20
5

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

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


SomeDude <lovelydear@mailmetrash.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |lovelydear@mailmetrash.com


--- Comment #1 from SomeDude <lovelydear@mailmetrash.com> 2012-04-27 08:44:10 PDT ---
Which version are you using ? I get the correct result (10, 5) with dmd 2.059

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

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



--- Comment #2 from c.m.brandenburg@gmail.com 2012-04-27 09:06:38 PDT ---
(In reply to comment #1)
> Which version are you using ? I get the correct result (10, 5) with dmd 2.059

$ dmd | head -n3
DMD64 D Compiler v2.059
Copyright (c) 1999-2012 by Digital Mars written by Walter Bright
Documentation: http://www.dlang.org/index.html

I get this errant BigInt behavior both on an Arch Linux installation, using the community dmd package. And I get this errant behavior on Ubuntu 11.10 using gdc and on Ubuntu 12.04 using the dmd deb file gotten from the dlang.org download page (http://ftp.digitalmars.com/dmd_2.059-0_amd64.deb). These are all the combinations of versions I've tried. Indeed, I have yet to see D produce correct behavior for BigInt divide-by-1.

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

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



--- Comment #3 from c.m.brandenburg@gmail.com 2012-04-27 09:08:30 PDT ---
(In reply to comment #1)
> Which version are you using ? I get the correct result (10, 5) with dmd 2.059

By the way, these are all on x86_64. I've modified the 'Platform' field in the bug record to reflect that.

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

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



--- Comment #4 from c.m.brandenburg@gmail.com 2012-04-28 03:05:39 PDT ---
$ dmd | head -n3
DMD64 D Compiler v2.059
Copyright (c) 1999-2012 by Digital Mars written by Walter Bright
Documentation: http://www.dlang.org/index.html


I do _not_ get this error when using the 32-bit v2.059 compiler. This appears to be a problem specific to the 64-bit compiler.

Also, I've tested this only on Linux systems—Arch, Ubuntu 11.10, and Ubuntu 12.04.

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

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



--- Comment #5 from c.m.brandenburg@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: -------

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



--- Comment #6 from c.m.brandenburg@gmail.com 2012-04-28 03:38:38 PDT ---
Here's my modified BigUint.divInt() as a proof-of-concept of the fix.

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

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

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



--- Comment #7 from github-bugzilla@puremagic.com 2012-07-01 19:53:05 PDT ---
Commit pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/a79bb20ea79955da2422b32b6291ed464530c86d Fix issue 7993 BigInt divide-by-1 error

Thanks to c.m.brandeburg for the fix.

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

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


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |clugdbug@yahoo.com.au
         Resolution|                            |FIXED


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