Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread marco . bodrato 
Ciao,

3 set 2023, 22:16 da ni...@lysator.liu.se:

> Andrew Teylu  writes:
>


> 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?
>

Yes, unsigned is the best choice, it used to store a positive or
negative number, but now it actually is a mask: 0 or ~0.

I attach a possible patch.


>> I guess maybe a different question is: what is that code supposed to
>> do? Is the intent to `xor` with `0x` 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.
>

Correct.

Ĝis,
m
diff -r e3cc6f9e9753 gmp-impl.h
--- a/gmp-impl.h	Sun Aug 27 20:47:01 2023 +0200
+++ b/gmp-impl.h	Mon Sep 04 00:37:06 2023 +0200
@@ -1481,25 +1481,25 @@
 __GMP_DECLSPEC void  mpn_toom_interpolate_16pts (mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_size_t, int, mp_ptr);
 
 #define   mpn_toom_couple_handling __MPN(toom_couple_handling)
-__GMP_DECLSPEC void mpn_toom_couple_handling (mp_ptr, mp_size_t, mp_ptr, int, mp_size_t, int, int);
+__GMP_DECLSPEC void mpn_toom_couple_handling (mp_ptr, mp_size_t, mp_ptr, unsigned, mp_size_t, int, int);
 
 #define   mpn_toom_eval_dgr3_pm1 __MPN(toom_eval_dgr3_pm1)
-__GMP_DECLSPEC int mpn_toom_eval_dgr3_pm1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_dgr3_pm1 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
 
 #define   mpn_toom_eval_dgr3_pm2 __MPN(toom_eval_dgr3_pm2)
-__GMP_DECLSPEC int mpn_toom_eval_dgr3_pm2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_dgr3_pm2 (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
 
 #define   mpn_toom_eval_pm1 __MPN(toom_eval_pm1)
-__GMP_DECLSPEC int mpn_toom_eval_pm1 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_pm1 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
 
 #define   mpn_toom_eval_pm2 __MPN(toom_eval_pm2)
-__GMP_DECLSPEC int mpn_toom_eval_pm2 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_pm2 (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, mp_ptr);
 
 #define   mpn_toom_eval_pm2exp __MPN(toom_eval_pm2exp)
-__GMP_DECLSPEC int mpn_toom_eval_pm2exp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_pm2exp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);
 
 #define   mpn_toom_eval_pm2rexp __MPN(toom_eval_pm2rexp)
-__GMP_DECLSPEC int mpn_toom_eval_pm2rexp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);
+__GMP_DECLSPEC unsigned mpn_toom_eval_pm2rexp (mp_ptr, mp_ptr, unsigned, mp_srcptr, mp_size_t, mp_size_t, unsigned, mp_ptr);
 
 #define   mpn_toom22_mul __MPN(toom22_mul)
 __GMP_DECLSPEC void  mpn_toom22_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
diff -r e3cc6f9e9753 mpn/generic/toom54_mul.c
--- a/mpn/generic/toom54_mul.c	Sun Aug 27 20:47:01 2023 +0200
+++ b/mpn/generic/toom54_mul.c	Mon Sep 04 00:37:06 2023 +0200
@@ -61,7 +61,7 @@
 		mp_srcptr bp, mp_size_t bn, mp_ptr scratch)
 {
   mp_size_t n, s, t;
-  int sign;
+  unsigned sign;
 
   /* decomposition ***/
 #define a4  (ap + 4 * n)
diff -r e3cc6f9e9753 mpn/generic/toom63_mul.c
--- a/mpn/generic/toom63_mul.c	Sun Aug 27 20:47:01 2023 +0200
+++ b/mpn/generic/toom63_mul.c	Mon Sep 04 00:37:06 2023 +0200
@@ -99,7 +99,7 @@
 {
   mp_size_t n, s, t;
   mp_limb_t cy;
-  int sign;
+  unsigned sign;
 
   /* decomposition ***/
 #define a5  (ap + 5 * n)
diff -r e3cc6f9e9753 mpn/generic/toom6h_mul.c
--- a/mpn/generic/toom6h_mul.c	Sun Aug 27 20:47:01 2023 +0200
+++ b/mpn/generic/toom6h_mul.c	Mon Sep 04 00:37:06 2023 +0200
@@ -109,7 +109,7 @@
 {
   mp_size_t n, s, t;
   int p, q, half;
-  int sign;
+  unsigned sign;
 
   /* decomposition ***/
 
diff -r e3cc6f9e9753 mpn/generic/toom8h_mul.c
--- a/mpn/generic/toom8h_mul.c	Sun Aug 27 20:47:01 2023 +0200
+++ b/mpn/generic/toom8h_mul.c	Mon Sep 04 00:37:06 2023 +0200
@@ -119,7 +119,7 @@
 {
   mp_size_t n, s, t;
   int p, q, half;
-  int sign;
+  unsigned sign;
 
   /* decomposition ***/
 
diff -r e3cc6f9e9753 mpn/generic/toom_couple_handling.c
--- a/mpn/generic/toom_couple_handling.c	Sun Aug 27 20:47:01 2023 +0200
+++ b/mpn/generic/toom_couple_handling.c	Mon Sep 04 00:37:06 2023 +0200
@@ -45,7 +45,7 @@
 */
 void
 mpn_toom_couple_handling (mp_ptr pp, mp_size_t n, mp_ptr np,
-			  int

Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Vincent Lefevre 
On 2023-09-03 22:16:21 +0200, Niels Möller wrote:
> Andrew Teylu  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 `0x` 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  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Andrew Teylu 
On Sun, Sep 3, 2023 at 9:16 PM Niels Möller  wrote:
> Does it make any difference if you change the "1" constants to "1u" ?
>

I'll try this in the morning and see if the runtime error goes away or not.

> 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?
>

I don't know much about the GMP code, but looking at this code and its
surroundings, it seems that `neg` is actually `sign` (well, how it is
used by its callees).

I guess maybe rather than "negation" or "negated" (i.e., the
"opposite" of some value), it actually means "is_negative" (==
"sign"). In that case, I guess it doesn't matter if the return value
is signed or not: it is effectively just a bool with two values (0x0
and 0x).
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Niels Möller 
Andrew Teylu  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 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" ?

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?

> I guess maybe a different question is: what is that code supposed to
> do? Is the intent to `xor` with `0x` 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.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Andrew Teylu 
On Sun, Sep 3, 2023 at 7:16 PM Torbjörn Granlund  wrote:
>
> Andrew Teylu  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 `0x` 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
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Torbjörn Granlund 
Andrew Teylu  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.

This is not a real problem with any compiler I am aware of.  Of course,
an evil compiler is free to make demons fly out our noses whenever we
trigger "undefined" signed integer operations.

I don't think it is worth our time trying to placate clang and its ever
growing world of warnings.  We would end up with utterly messy code
which nobody could read.


-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Unsigned integer overflow in `toom_eval_pm2.c`

2023-09-03 Thread Andrew Teylu 
Hi,

I'm working with gmp-6.3.0 compiled with clang 16 and its
`-fsanitize=integer` flag.

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)
```

The values we're normally getting are:

 * neg (before): 0

 * k: 6

 * neg (after): -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.

Apologies for the noise if this is intended behaviour.

Cheers,

Andrew
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs