Re: Unsigned integer overflow in `toom_eval_pm2.c`

[marco . bodrato]

Ciao,

4 set 2023, 15:19 da vinc...@vinc17.net:

> On 2023-09-04 09:52:23 +0200, marco.bodr...@tutanota.com wrote:
>
>> Should the value ~0 be written as ~0U to be correctly assigned to an
>> unsigned?
>>
>
> IMHO, this would be better as this would make the signedness of
> the types more consistent
>

Ok, I changed all the
neg = (v<0)? ~0:0;
into
neg = - (unsigned) (v<0):

For x86-64, gcc generates exactly the same code:

# m.c:2:  return v<0?~0:0;
 movl   %edi, %eax
 sarl   $31, %eax

# m.c:6:  return -(unsigned)(v<0);
movl   %edi, %eax
sarl   $31, %eax



All but one. Everything started with a question on the line:
neg ^= ((k & 1) - 1);

Well, now neg before this line contains 0 or 1, so that the line is now
neg ^= 1 ^ k & 1;
 
And it is transformed to a mask after that,

Changes pushed here:
https://gmplib.org/repo/gmp/rev/ef441e461f42

Ĝis,
m
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

[Vincent Lefevre]

On 2023-09-04 09:52:23 +0200, marco.bodr...@tutanota.com wrote:
> Should the value ~0 be written as ~0U to be correctly assigned to an
> unsigned?

IMHO, this would be better as this would make the signedness of
the types more consistent (the goal being to have an unsigned int
for all these masks).

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

[Niels Möller]

marco.bodr...@tutanota.com writes:

> Would a comment "It returns 0 or ~0, depending on the sign of the result"
> added to all the mpn_toom_eval_ functions suffice?

Yes. It would be nice if there were some reasonable place to document
that only once, but don't know where that could be.

> From the value in {0,1} we can get mask = -value, and from the mask in
> {0, ~0} we can get value = mask & 1. Of course we can switch to a
> different convention, if someone feels it's important. I don't.

If it's actually used as a mask in several places, I'm happy to leave as
is.

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`

[marco . bodrato]

Ciao,

4 set 2023, 08:02 da ni...@lysator.liu.se:

> As Vincent suggested, it would be good to document somewhere what the
> convention is (values 0 or ~0).
>

Would a comment "It returns 0 or ~0, depending on the sign of the result"
added to all the mpn_toom_eval_ functions suffice?


> And maybe change to 0 and 1 convention,
>

I see a line

mpn/generic/toom42_mul.c:  vm1_neg = mpn_toom_eval_dgr3_pm1 (as1, asm1, ap, n, 
s, a0_a2) & 1;

where we actually use 0 or 1, and many lines like

mpn/generic/toom52_mul.c:  flags = (enum toom6_flags) (toom6_vm2_neg & 
mpn_toom_eval_pm2 (as2, asm2, 4, ap, n, s, a1a3));

where we use the value as a mask: 0 or ~ 0.


>From the value in {0,1} we can get mask = -value, and from the mask in {0, ~0} 
>we can get value = mask & 1.
Of course we can switch to a different convention, if someone feels it's 
important. I don't.


> since that fits better with assigning it from the return value from
> mpn_sub_n, and it seems generally more consistent with how we handle
>

We never use mpn_sub_n to assign that value.


> boolean values elsewhere. But may need further changes, like to
> abs_sub_add_n, also noted by Vincent.
>
Yes, Vincent is right. New patch.

Should the value ~0 be written as ~0U to be correctly assigned to an unsigned?

Ĝ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 09:40:02 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 09:40:02 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 09:40:02 2023 +0200
@@ -37,8 +37,9 @@
 
 #include "gmp-impl.h"
 
-/* Stores |{ap,n}-{bp,n}| in {rp,n}, returns the sign. */
-static int
+/* Stores |{ap,n}-{bp,n}| in {rp,n}. */
+/* It returns 0 or ~0, depending on the sign of the result. */
+static unsigned
 abs_sub_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
 {
   mp_limb_t  x, y;
@@ -65,9 +66,10 @@
   return 0;
 }
 
-static int
+/* It returns 0 or ~0, depending on the sign of the result rm. */
+static unsigned
 abs_sub_add_n (mp_ptr rm, mp_ptr rp, mp_srcptr rs, mp_size_t n) {
-  int result;
+  unsigned result;
   result = abs_sub_n (rm, rp, rs, n);
   ASSERT_NOCARRY(mpn_add_n (rp, rp, rs, n));
   return result;
@@ -99,7 +101,7 @@
 {
   mp_size_t n, s, t;
   mp_limb_t cy;
-  int sign;
+  

Re: Unsigned integer overflow in `toom_eval_pm2.c`

[Andrew Teylu]

On Sun, Sep 3, 2023 at 11:40 PM  wrote:
> I attach a possible patch.
>

As an outsider, does it make sense to also change instances of "neg"
to be "sign" (if that's the interpretation) for consistency?

For someone who isn't literate in the GMP code, neg vs. sign seems to
be used slightly inconsistently, and (personally) "neg" reads as
"negated" rather than "is negative".
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Unsigned integer overflow in `toom_eval_pm2.c`

[Niels Möller]

marco.bodr...@tutanota.com writes:

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

Makes sense, I think.

As Vincent suggested, it would be good to document somewhere what the
convention is (values 0 or ~0). And maybe change to 0 and 1 convention,
since that fits better with assigning it from the return value from
mpn_sub_n, and it seems generally more consistent with how we handle
boolean values elsewhere. But may need further changes, like to
abs_sub_add_n, also noted by Vincent.

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`

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

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

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

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

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

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

[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