Unsigned integer overflow in `toom_eval_pm2.c`

[Vincent Lefevre]

On 2023-09-03 22:16:21 +0200, Niels Möller wrote:
> Andrew Teylu <andrewvaughanj at gmail.com> writes:
> 
> >> 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.
> 
> I can't say precisely what implicit conversions happen according to the
> spec: Unsigned to signed is always well defined, but the other direction
> only if the converted value fits.

It is signed to unsigned that is always well defined, with the
usual modulo rule. For unsigned to signed, if the value doesn't
fit, the behavior is implementation-defined.

> It may also depend on whether or not
> mp_limb_t is larger than int.
> 
> Does it make any difference if you change the "1" constants to "1u" ?

k is already unsigned. So changing the constants in ((k & 1) - 1)
won't change anything.

I suppose that clang complains because of the conversion from unsigned
to signed (since neg is an int). But note that this is *not* an
integer overflow.

> I see no good reason to involve any signed values here, though. Maybe
> the variable neg, and the return value, should be changed to mp_limb_t,
> or at least unsigned int?

You should also document the possibles values and their meaning.

> > 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)?
> 
> I think intention is to conditionally flip all the bits. And in
> addition, neg should always be either all ones or all zeros.

In toom_couple_handling.c, it is just used like a boolean value.

In mpn/generic/toom63_mul.c, there is

  sign ^= abs_sub_add_n (v1, v3, pp, n + 1);

and abs_sub_add_n also uses int with the same meaning. This seems
consistent, but you would need to check wherever such values can
be combined.

-- 
Vincent Lefèvre <vincent at vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)