Unsigned integer overflow in `toom_eval_pm2.c`

Andrew Teylu andrewvaughanj at gmail.com
Sun Sep 3 20:30:31 CEST 2023


On Sun, Sep 3, 2023 at 7:16 PM Torbjörn Granlund <tg at gmplib.org> wrote:
>
> Andrew Teylu <andrewvaughanj at gmail.com> writes:
>
>   When I run `multiply.c` from gmpbench [https://gmplib.org/gmpbench],
>   I'm seeing an unsigned integer overflow in `toom_eval_pm2.c` on this
>   line:
>
>   neg ^= ((k & 1) - 1)
>
>   I fully appreciate that unsigned integer overflow is implementation
>   defined, but I am not sure if this is the intended behaviour of
>   `mpn_toom_eval_pm2` or not.
>
> In C, unsigned arithmetic is completely defined as computing mod 2^k,
> where k is the bit size of the corresponding type.
>
> I am not sure the arithmetic on unsigned types is what clang is unhappy
> about, though.  Perhaps it dislikes the xor with "neg", which is a
> signed variable.
>
> Arithmetic on signed types as well as assignments between signed and
> unsigned is not well-defined for certain operand ranges.
>

I guess maybe a different question is: what is that code supposed to
do? Is the intent to `xor` with `0xFFFFFFFF` if the `k` is even and
`xor` with `0` if the `k` is odd (i.e., it either flips all the bits
in the even case or leaves them in the odd case)?

Cheers,

Andrew


More information about the gmp-bugs mailing list