bitnum parameter of core.bitop.bt should be signed

[dlangBugzillaToGithub]

ag0aep6g reported this on 2018-04-05T21:22:40Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=18734

CC List

• Walter Bright (@WalterBright)
• Ketmar Dark

Description

Closely related to issue 18730. But 18730 is x86-64 only, while this one affects both x86 and x86-64.

The issue is best demonstrated with 32-bit code:

----
import std.stdio;
void main()
{
    static assert(size_t.sizeof == 4); /* We're in 32-bit code. */
    
    enum len = 2 ^^ 27;
    assert(len * size_t.sizeof * 8L == 2L ^^ 32);
        /* Exactly enough space for size_t.max bits. */
    
    auto a = new size_t[len + 1];
        /* Adding one because we're going to start from a[1]. */
    
    a[$ - 1] = 0x8000_0000; /* Set the very last bit. */
    writeln(bt(&a[1], size_t.max)); /* Try to read it. */
        /* Without -O: 1, correct. With -O: 0, wrong. */
    
    a[$ - 1] = 0; /* Unset the very last bit. */
    a[0] = 0x8000_0000; /* Set the last bit of the first size_t. */
    writeln(bt(&a[1], size_t.max)); /* Try reading the very last bit again. */
        /* Without -O: "0", correct. With -O: "1", wrong. */
}

/* Copied from core.bitop. */
int bt(in size_t* p, size_t bitnum) pure @system
{
    static if (size_t.sizeof == 8)
        return ((p[bitnum >> 6] & (1L << (bitnum & 63)))) != 0;
    else static if (size_t.sizeof == 4)
        return ((p[bitnum >> 5] & (1  << (bitnum & 31)))) != 0;
    else
        static assert(0);
}
----

The wrong behavior happens because core.bitop.bt is optimized using the bt instruction. And the bt instruction interprets offset (bitnum) as signed. So instead of going size_t.max bits up from `a[1]`, it goes 1 bit down.

If core.bitop.bt is supposed to directly map to the bt instruction, the type of the bitnum parameter should be ptrdiff_t, not size_t. Making that change probably means that the body of core.bitop.bt has to be changed to accommodate for negative values of bitnum. And then DMD will have to be updated to recognize the new body.

x86-64 is affected in the same way, but you can't actually have an array of 2^63 bits, so it can't be hit like on x86.

[dlangBugzillaToGithub]

uplink.coder commented on 2018-04-10T11:43:21Z

DMD does not recognize bodies only function signatures.
So change it all you like :) it's only going to be used on systems where the intrinsic can't work.

[dlangBugzillaToGithub]

ag0aep6g commented on 2018-04-10T12:59:03Z

(In reply to uplink.coder from comment #1)
> DMD does not recognize bodies only function signatures.
> So change it all you like :) it's only going to be used on systems where the
> intrinsic can't work.

core.bitop.bt is not an intrinsic. The expression in the body is recognized by the optimizer.

[dlangBugzillaToGithub]

bugzilla (@WalterBright) commented on 2020-06-21T07:56:42Z

Huh, you are right. This:

https://www.felixcloutier.com/x86/bt

doesn't mention it's signed, but the AMD reference says it is.

[dlangBugzillaToGithub]

dlang-bot commented on 2020-06-21T08:40:11Z

@WalterBright created dlang/druntime pull request #3141 "fix Issue 18734 - bitnum parameter of core.bitop.bt should be signed" fixing this issue:

- fix Issue 18734 - bitnum parameter of core.bitop.bt should be signed

https://github.com/dlang/druntime/pull/3141

[dlangBugzillaToGithub]

dlang-bot commented on 2020-06-21T09:01:26Z

@WalterBright created dlang/dmd pull request #11306 "fix Issue 18734 - bitnum parameter of core.bitop.bt should be signed" fixing this issue:

- fix Issue 18734 - bitnum parameter of core.bitop.bt should be signed

https://github.com/dlang/dmd/pull/11306