Re: Likely GMP bug

[Torbjörn Granlund]

Vincent Lefevre  writes:

  But shouldn't it be the goal of the compiler to generate the fastest
  code for the target?

Yeah, that's a good idea.  :-)

This might require more analysis than what we can expect from the
compiler, as (x >> 1) >> c is not the same thing as x >> (1+c) (at least
not if the CPU truncates counts).

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

Re: Likely GMP bug

[Marco Bodrato]

Ciao,

Il Mer, 30 Maggio 2018 10:20 am, Niels Möller ha scritto:
> "Marco Bodrato"  writes:

> Thinking about micro optimizations... Consider

>>   count_trailing_zeros (c, ulimb);
>>   ulimb = (ulimb >> 1) >> c;

> vs

>>   count_trailing_zeros (c, ulimb);
>>   ulimb >>= (c + 1);

> I wonder if maybe it's preferable to always use the first variant? Both

You are saying that my patch https://gmplib.org/repo/gmp/rev/e4849ae7c974
was not an emergency workaround, but a cleverly subtle optimization?
Well, I have to admit that I was not aware... but thanks :-)

> first variant, the first shift can be issued in parallel with ctz,

If we could hint to the compiler...
  HINT (c >= 0 && c + 1 < )
then they should be equivalent. The optimiser of the compiler can choose
the best one for the target environment :-)

If we define c as unsigned, we do not need other hints, the compiler has
enough information to understand that ulimb>>(c+1) can be implemented as
(ulimb>>1)>>c for all non-undefined cases. The vice-versa is not as easy.

Maybe, of course, that current compilers does not take care of this
possible optimisation...

Ĝis,
m

-- 
http://bodrato.it/

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

Re: Likely GMP bug

[Torbjörn Granlund]

ni...@lysator.liu.se (Niels Möller) writes:

  But you may be right that it's important for performance to avoid a
  redundant count_trailing_zeros on u.

It is slow on several machines, but it has become more common to provide
good leading/trailing bit count for newer microarchs.

  It seems tricky to avoid that, without code duplication or complications
  in the code flow. For my personal preference, tradeoff threshold between
  goto and duplicated code is around 5-10 duplicated code lines.

  Thinking about micro optimizations... Consider

  >   count_trailing_zeros (c, ulimb);
  >   ulimb = (ulimb >> 1) >> c;

  vs

  >   count_trailing_zeros (c, ulimb);
  >   ulimb >>= (c + 1);

Right shift has OK performance almost everywhere.  (And obsolete
exceptions is x86-64 Pentium 4 where it takes some 8 cycles and stalls
the pipeline.)

On newer Intel x86-64 shifting is fast for immediate counts but takes 2
cycles with 1/2 thoughput for dynamic counts.  The latest generations
provides a new set of shifts for dynamic counts which are fast,
e.g. shrx.

AMD chips have great right shift performance with no exceptions.

No RISCs have any problems here.

  I wonder if maybe it's preferable to always use the first variant? Both
  should compile to three instructions (assuming we have a ctz
  instruction), ctz + shift + shift, or ctz + add + shift. But with the
  first variant, the first shift can be issued in parallel with ctz,
  reducing the critical path of the gcd loop.

  We'd need some benchmarking to see if it makes a difference.

Suppressing redundant count_trailing_zeros should make more difference.

Ref: https://gmplib.org/~tege/x86-timing.pdf

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

Re: Likely GMP bug

[Niels Möller]

"Marco Bodrato"  writes:

> ... the effect is that in many cases (if U don't need reduction modulo V)
> the trailing zeros of U are removed twice.

But you may be right that it's important for performance to avoid a
redundant count_trailing_zeros on u.

It seems tricky to avoid that, without code duplication or complications
in the code flow. For my personal preference, tradeoff threshold between
goto and duplicated code is around 5-10 duplicated code lines.

Thinking about micro optimizations... Consider

>   count_trailing_zeros (c, ulimb);
>   ulimb = (ulimb >> 1) >> c;

vs

>   count_trailing_zeros (c, ulimb);
>   ulimb >>= (c + 1);

I wonder if maybe it's preferable to always use the first variant? Both
should compile to three instructions (assuming we have a ctz
instruction), ctz + shift + shift, or ctz + add + shift. But with the
first variant, the first shift can be issued in parallel with ctz,
reducing the critical path of the gcd loop.

We'd need some benchmarking to see if it makes a difference.

Regards,
/Niels

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

Re: Likely GMP bug

[Marco Bodrato]

Ciao,

Il Lun, 28 Maggio 2018 10:00 pm, Niels Möller ha scritto:
> I'd suggest the below (complete file, I think that's more readable

The code is clean.

You removed all gotos...

> The last part of the function requires vlimb odd, but tolerates
> arbitrary u, including 0.

... the effect is that in many cases (if U don't need reduction modulo V)
the trailing zeros of U are removed twice.

> This would be a candidate gcd_11 or gcd_11_odd.

Maybe, if we keep both parts in the same function, some code replication
can be good?

Is something like the following too redundant?

mp_limb_t
mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
{
  mp_limb_t  ulimb;
  unsigned long  zero_bits, u_low_zero_bits;
  int c;

  ASSERT (size >= 1);
  ASSERT (vlimb != 0);
  ASSERT_MPN_NONZERO_P (up, size);

  ulimb = up[0];

  /* Need vlimb odd for modexact, want it odd to get common zeros. */
  count_trailing_zeros (zero_bits, vlimb);
  vlimb >>= zero_bits;

  if (size > 1)
{
  /* Must get common zeros before the mod reduction.  If ulimb==0 then
 vlimb already gives the common zeros.  */
  if (ulimb != 0)
{
  count_trailing_zeros (u_low_zero_bits, ulimb);
  zero_bits = MIN (zero_bits, u_low_zero_bits);
}

  ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
  if (ulimb == 0)
return vlimb << zero_bits;

 /* Note that if ulimb == GMP_LIMB_HIGHBIT, c+1 is an invalid shift
count. */
  count_trailing_zeros (c, ulimb);
  ulimb = (ulimb >> 1) >> c;
}
  else
{
  /* size==1, so up[0]!=0 */
  count_trailing_zeros (u_low_zero_bits, ulimb);
  ulimb >>= u_low_zero_bits;
  zero_bits = MIN (zero_bits, u_low_zero_bits);

  /* make u bigger */
  if (vlimb > ulimb)
MP_LIMB_T_SWAP (ulimb, vlimb);

  /* if u is much bigger than v, reduce using a division rather than
 chipping away at it bit-by-bit */
  if ((ulimb >> 16) > vlimb)
{
  ulimb %= vlimb;
  if (ulimb == 0)
return vlimb << zero_bits;

  count_trailing_zeros (c, ulimb);
  ulimb >>= (c + 1);
{
  else
ulimb >>= 1;
}

  ASSERT (vlimb & 1);

  /* Represent the odd numbers ulimb and vlimb without the redundant
 least significant one bit. This reduction in size by one bit
 ensures that the high bit of t, below, is set if and only if
 vlimb > ulimb. And in addition, t != GMP_LIMB_HIGHBIT. */
  vlimb >>= 1;

  while (ulimb != vlimb)
{
...



Ĝis,
m

-- 
http://bodrato.it/

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

Re: Likely GMP bug

[Torbjörn Granlund]

"Marco Bodrato"  writes:

  The test suite now checks for this bug, for every run with
  --disable-assembly. So yes, you can remove the failure file, it will be
  recreated if some asm implementation is affected :-)

I beleieve all x86 asm for gcd_1 was whacked tonight (we only have two
implementatons, actually).

All non-x86 gcd_1 code should be tested within a week.

https://gmplib.org/devel/systemup.html

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

Re: Likely GMP bug

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> For now, I'd suggest to just rip out USE_ZEROTAB.

I've pushed a change to do just that. For making the rest of the file
clearer, I'd suggest the below (complete file, I think that's more
readable than the diff). I've also ripped out the GCD_1_METHOD==1 code,
since it appears to be disabled everywhere. Let me know if anyone has
any interest in keeping that around.

The last part of the function requires vlimb odd, but tolerates
arbitrary u, including 0. This would be a candidate gcd_11 or
gcd_11_odd. If it's made it's own function, the live zero_bits variable
prevents it from being a tail call, but maybe that's not a big deal.

I haven't done any benchmarks, and I'm not able to do any tonight.

Regards,
/Niels

/* mpn_gcd_1 -- mpn and limb greatest common divisor.

Copyright 1994, 1996, 2000, 2001, 2009, 2012 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of either:

  * the GNU Lesser General Public License as published by the Free
Software Foundation; either version 3 of the License, or (at your
option) any later version.

or

  * the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any
later version.

or both in parallel, as here.

The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received copies of the GNU General Public License and the
GNU Lesser General Public License along with the GNU MP Library.  If not,
see https://www.gnu.org/licenses/.  */

#include "gmp-impl.h"
#include "longlong.h"

/* Does not work for U == 0 or V == 0.  It would be tough to make it work for
   V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.

   The threshold for doing u%v when size==1 will vary by CPU according to
   the speed of a division and the code generated for the main loop.  Any
   tuning for this is left to a CPU specific implementation.  */

mp_limb_t
mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
{
  mp_limb_t  ulimb;
  unsigned long  zero_bits, u_low_zero_bits;
  int c;

  ASSERT (size >= 1);
  ASSERT (vlimb != 0);
  ASSERT_MPN_NONZERO_P (up, size);

  ulimb = up[0];

  /* Need vlimb odd for modexact, want it odd to get common zeros. */
  count_trailing_zeros (zero_bits, vlimb);
  vlimb >>= zero_bits;

  if (size > 1)
{
  /* Must get common zeros before the mod reduction.  If ulimb==0 then
 vlimb already gives the common zeros.  */
  if (ulimb != 0)
{
  count_trailing_zeros (u_low_zero_bits, ulimb);
  zero_bits = MIN (zero_bits, u_low_zero_bits);
}

  ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
}
  else
{
  /* size==1, so up[0]!=0 */
  count_trailing_zeros (u_low_zero_bits, ulimb);
  ulimb >>= u_low_zero_bits;
  zero_bits = MIN (zero_bits, u_low_zero_bits);

  /* make u bigger */
  if (vlimb > ulimb)
MP_LIMB_T_SWAP (ulimb, vlimb);

  /* if u is much bigger than v, reduce using a division rather than
 chipping away at it bit-by-bit */
  if ((ulimb >> 16) > vlimb)
ulimb %= vlimb;

}

  ASSERT (vlimb & 1);
  if (ulimb == 0)
return vlimb << zero_bits;

  count_trailing_zeros (c, ulimb);
  /* Note that if ulimb == GMP_LIMB_HIGHBIT, c+1 is an invalid shift count. */
  ulimb >>= c;

  /* Represent the odd numbers ulimb and vlimb without the redundant
 least significant one bit. This reduction in size by one bit
 ensures that the high bit of t, below, is set if and only if
 vlimb > ulimb. And in addition, t != GMP_LIMB_HIGHBIT. */
  ulimb >>= 1;
  vlimb >>= 1;

  while (ulimb != vlimb)
{
  mp_limb_t t;
  mp_limb_t vgtu;

  t = ulimb - vlimb;
  vgtu = LIMB_HIGHBIT_TO_MASK (t);

  /* v <-- min (u, v) */
  vlimb += (vgtu & t);

  /* u <-- |u - v| */
  ulimb = (t ^ vgtu) - vgtu;

  count_trailing_zeros (c, t);
  ASSERT (c + 1 < GMP_LIMB_BITS);
  ulimb >>= (c + 1);
}

  vlimb = (vlimb << 1) | 1;
  return vlimb << zero_bits;
}





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

Re: Likely GMP bug

[Torbjörn Granlund]

"Marco Bodrato"  writes:

  The test suite now checks for this bug, for every run with
  --disable-assembly. So yes, you can remove the failure file, it will be
  recreated if some asm implementation is affected :-)

Ehum?

With --disable-assembly asm code tends to be excluded...

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

Re: Likely GMP bug

[Niels Möller]

t...@gmplib.org (Torbjörn Granlund) writes:

> It really worries me that our crazy broad testing did not catch this
> until now.  This makes me much less confident about GMP's correctness,
> actually.

Here we have a bug where assumptions made by the code are violated, with
a pretty low probability given random inputs. And which results in an
actual miscomputation with *even* lower probability.

So found thanks to ubsan, not the testcode's validation of the result.

It's good to use ASSERTs to document assumptions made, even if an
ASSERT (c <= GMP_LIMB_BITS - 2) was missing in this case.

I think another contributing factor is that gcd_1 does two different
things: The tight loop to compute gcd of two words, and somewhat hairy
logic to reduce larger numbers before entering the loop. If we had gcd_1
doing the reduction and then calling a gcd_11 (ulimb, vlimb) to do the
remaining work, where the latter function has a well defined interface
with its own tests, it had been harder and less tempting to do the
obscure thing.

> Replacement code should not jump into loops.  This bug (but not the
> shortcoming of the test suite) should teach us that lesson.

goto has its uses, but this case with multiple target labels is more
like the infamous COME FROM... https://en.wikipedia.org/wiki/COMEFROM

Regards,
/Niels

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

Re: Likely GMP bug

[Torbjörn Granlund]

"Marco Bodrato"  writes:

  It was hard, but we got it:
  https://gmplib.org/repo/gmp/rev/1f8a8fefb5c2

Thanks!

It really worries me that our crazy broad testing did not catch this
until now.  This makes me much less confident about GMP's correctness,
actually.

I realise that a plain assembly enabled build will not trigger this for
any current platform, so few people will be afffected in practice.

  The bug is triggered not only for 32-bit limbs, but also for other sizes.
  On any machine, if the undefined behaviour is not the one we hope,

  ./configure --disable-assembly && make
  make check TESTS= && tests/mpz/t-gcd_ui

  should fail.
  It does, with ABI=64 on shell.

  Of course I also healed the bug, to avoid too many red lines in the next
  "GMP testing status": https://gmplib.org/repo/gmp/rev/e4849ae7c974 .
  This is just a workaround, waiting for a code reorganisation by someone
  who knows better than me the various algorithm alternatives.

Replacement code should not jump into loops.  This bug (but not the
shortcoming of the test suite) should teach us that lesson.

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

Re: Likely GMP bug

[Marco Bodrato]

Ciao,

Il Sab, 26 Maggio 2018 11:01 pm, Niels Möller ha scritto:
> Is it possible to construct some examples with v a multiple of 641, and
> input U such that ulimb = 2^31 after reduction?

It was hard, but we got it:
https://gmplib.org/repo/gmp/rev/1f8a8fefb5c2

The bug is triggered not only for 32-bit limbs, but also for other sizes.
On any machine, if the undefined behaviour is not the one we hope,

./configure --disable-assembly && make
make check TESTS= && tests/mpz/t-gcd_ui

should fail.
It does, with ABI=64 on shell.

Of course I also healed the bug, to avoid too many red lines in the next
"GMP testing status": https://gmplib.org/repo/gmp/rev/e4849ae7c974 .
This is just a workaround, waiting for a code reorganisation by someone
who knows better than me the various algorithm alternatives.

Ĝis,
m

-- 
http://bodrato.it/papers/

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

Re: Likely GMP bug

[Marco Bodrato]

Ciao,

Il Sab, 26 Maggio 2018 11:01 pm, Niels Möller ha scritto:
> "Marco Bodrato"  writes:

> shift, that is interpreted as the odd value 2^32+1. This number has the
> factorization 641 * 6700417, and if v happens to be a multiple of one of

> And we have potential miscpumputatino also on 64-bit, if we jump into
> the code with ulimb = 2^63, and v has a common factor with 2^64+1 =
> 274177 * 67280421310721.

> Is it possible to construct some examples with v a multiple of 641, and
> input U such that ulimb = 2^31 after reduction?

  if limbs are unsigned long, and _ui functions can be used...

  factor = 641; /* A factor of GMP_NUMB_MAX + 2 */
  vlimb = factor * (GMP_NUMB_MAX / factor - 1);
  ASSERT (vlimb > CNST_LIMB (1) << 31);

  mpz_set_ui (U, vlimb);
  mpz_mul_ui (U, U, somerandomdata);
  mpz_add_ui (U, U, CNST_LIMB (1) << 31);
  /* Try also sub_ui, because of MODEXACT */

> Yes. gcd (V, kV + 2^32) = gcd (V, 2^32) = 1. Not sure I see the
> connection to the bug, though.

I confused 32 with 31...

Ĝis,
m

-- 
http://bodrato.it/papers/

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

Re: Likely GMP bug

[Niels Möller]

"Marco Bodrato"  writes:

> Il Ven, 25 Maggio 2018 2:10 pm, Niels Möller ha scritto:
>> That fails with undefined behavior if by chance t == 2^31, so that c ==
>> 31.
>>
>> I don't see how that can happen, though, since ulimb, vlimb < 2^31
>> through out the loop, and t = (ulimb - vlimb) mod 2^32.
>
> ... but can jump inside the loop ...
>
> That's the culprit:
>
>   if (size > 1)
> {
>   ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
>   goto strip_u_maybe;
> }

Ah, that's subtle! Thank's for tracking it down. Do you know if it
results in a miscomputation on the typical (32-bit) machines where (x >>
32) == x?

> diff -r a2b594f11916 mpn/generic/gcd_1.c
> --- a/mpn/generic/gcd_1.c   Sun May 13 16:13:42 2018 +0200
> +++ b/mpn/generic/gcd_1.c   Sat May 26 09:29:41 2018 +0200
> @@ -83,8 +83,13 @@
> }
>
>ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
> -  if (ulimb == 0)
> -   goto done;
> +  ASSERT_ALWAYS (POW2_P (0));
> +  if (POW2_P (ulimb))
> +   {
> + if (ulimb != 0)
> +   vlimb = 1;
> + goto done;
> +   }
>
>goto strip_u_maybe;
>  }

Alternatively, change only the branch that have this problem,
something like this (untested):

*** /tmp/extdiff.B7tg0s/gmp.aab8a010d10f/mpn/generic/gcd_1.c
2018-05-26 10:42:48.367993924 +0200
--- /home/nisse/hack/gmp/mpn/generic/gcd_1.c2018-05-26
10:42:42.89642 +0200
*** mpn_gcd_1 (mp_srcptr up, mp_size_t size,
*** 180,185 
{
strip_u_maybe:
  vlimb >>= 1;
! t = ulimb;
}
count_trailing_zeros (c, t);
--- 180,189 
{
strip_u_maybe:
+ count_trailing_zeros (c, ulimb);
  vlimb >>= 1;
! ulimb >>= 1;
! /* c+1 is not always a valid shift count. */
! ulimb >>= c;
! continue;
}
count_trailing_zeros (c, t);

Regards,
/Niels

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

Re: Likely GMP bug

[Dennis Clarke]

On 05/25/2018 04:30 PM, Torbjörn Granlund wrote:

Dennis Clarke  writes:

   I have run all the testsuite, both with the assembly and without, on a
   pure 32-bit Debian machine and see no errors anywhere.

Our machine runs gentoo with gcc 6.4.0.  (Not sure if the exact machine
matters.)

datan$ somepath/gmp/configure CFLAGS="-m32 -g -fsanitize=undefined -fno-sanitize-recover" 
--disable-shared --disable-assembly ABI=32 && make && make check TESTS= INTERPRETER=)

datan$ GMP_CHECK_RANDOMIZE=140064609456624 tests/mpq/t-cmp_ui
gcd_1.c:187:13: runtime error: shift exponent 32 is too large for 32-bit type 
'long unsigned int'




OKay .. same result here :

phobos$ gcc --version
gcc (genunix Thu May 17 17:47:37 UTC 2018) 8.1.0
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

phobos$ ./configure ABI=32 --enable-cxx --prefix=/usr/local 
--libdir=/usr/local/lib --with-gnu-ld --disable-assembly


PASS: t-aors
FAIL: t-cmp
FAIL: t-cmp_ui
PASS: t-cmp_si
PASS: t-equal
PASS: t-get_d
PASS: t-get_str
PASS: t-inp_str
PASS: t-inv
PASS: t-md_2exp
PASS: t-set_f
PASS: t-set_str
PASS: io
PASS: reuse
PASS: t-cmp_z

Testsuite summary for GNU MP 6.1.99

# TOTAL: 15
# PASS:  13
# SKIP:  0
# XFAIL: 0
# FAIL:  2
# XPASS: 0
# ERROR: 0



phobos$ gdb tests/mpq/t-cmp_ui
GNU gdb (Debian 7.12-6+b1) 7.12.0.20161007-git
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 


This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i686-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
.
Find the GDB manual and other documentation resources online at:
.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from tests/mpq/t-cmp_ui...done.
warning: File 
"/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/.gdbinit" 
auto-loading has been declined by your `auto-load safe-path' set to 
"$debugdir:$datadir/auto-load".

To enable execution of this file add
add-auto-load-safe-path 
/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/.gdbinit

line to your configuration file "/home/dclarke/.gdbinit".
To completely disable this security protection add
set auto-load safe-path /
line to your configuration file "/home/dclarke/.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual.  E.g., run from the 
shell:

info "(gdb)Auto-loading safe path"
(gdb) dir 
/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/mpn:/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/mpn/generic 

Source directories searched: 
/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/mpn:/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/mpn/generic:$cdir:$cwd

(gdb) break gcd_1.c:187
No source file named gcd_1.c.
Make breakpoint pending on future shared library load? (y or [n]) y
Breakpoint 1 (gcd_1.c:187) pending.
(gdb) run
Starting program: 
/usr/local/build/gmp-6.1.99-20180525_4.16.4-genunix_i686.003/tests/mpq/t-cmp_ui 


[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
warning: File "/usr/local/gcc8/lib/libstdc++.so.6.0.25-gdb.py" 
auto-loading has been declined by your `auto-load safe-path' set to 
"$debugdir:$datadir/auto-load".

Re-seeding with GMP_CHECK_RANDOMIZE=140064609456624

Breakpoint 1, __gmpn_gcd_1 (up=0xb690, size=1, vlimb=100580449) at 
gcd_1.c:187

187   ulimb >>= (c + 1);
(gdb) print c
$1 = 1
(gdb) print c=30
$2 = 30
(gdb) cont
Continuing.

Breakpoint 1, __gmpn_gcd_1 (up=0xb690, size=1, vlimb=0) at gcd_1.c:187
187   ulimb >>= (c + 1);
(gdb) print c=31
$3 = 31
(gdb) frame
#0  __gmpn_gcd_1 (up=0xb690, size=1, vlimb=0) at gcd_1.c:187
187   ulimb >>= (c + 1);
(gdb) bt
#0  __gmpn_gcd_1 (up=0xb690, size=1, vlimb=0) at gcd_1.c:187
#1  0xb7ec6bef in gcd_2 (gp=0xb690, up=0xb570, vp=0xb6b0) at 
gcd.c:129
#2  0xb7ec81c3 in __gmpn_gcd (gp=0xb690, up=0xb570, usize=4, 
vp=0xb6b0, n=2) at gcd.c:304
#3  0xb7e600bc in __gmpz_gcd (g=0xb7f0, u=0xb83c, v=0xb848) 
at gcd.c:138

#4  0xb7e88ee2 in __gmpq_canonicalize (op=0xb83c) at canonicalize.c:54
#5  0x080498bc in main (argc=1, 

Re: Likely GMP bug

[Dennis Clarke]

On 05/25/2018 08:10 AM, Niels Möller wrote:

Dennis Clarke  writes:


gcd_1.c:187:13: runtime error: shift exponent 32 is too large for
32-bit type 'long unsigned int'
FAIL t-cmp_ui (exit status: 1)


And code is essentially

   count_trailing_zeros (c, t);
   ulimb >>= (c + 1);

The intention is to shift right to get rid of both trailing zero bits,
and the redundant least significant one bit.

That fails with undefined behavior if by chance t == 2^31, so that c ==
31.


I would have thought the deBruijn hash method works for all 32-bit
values to find trailing consecutive zero bits :

http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup



I don't see how that can happen, though, since ulimb, vlimb < 2^31
through out the loop, and t = (ulimb - vlimb) mod 2^32.

And I also wonder why USE_ZEROTAB is set to 0 here.


I have run all the testsuite, both with the assembly and without, on a
pure 32-bit Debian machine and see no errors anywhere.

I'd love to see an isolated code case that creates that runtime error.

Dennis

ps: hours later

phobos$
phobos$ find . -type f -ls | grep "gcd_1" | awk '{ printf("%4i%s\n", 
$7, $11 )}'

7158./mpn/ia64/gcd_1.asm
7192./mpn/gcd_1.o
4465./mpn/generic/gcd_1.c
7516./mpn/.libs/gcd_1.o
4125./mpn/x86/k7/gcd_1.asm
6418./mpn/x86/k6/gcd_1.asm
3820./mpn/x86/p6/gcd_1.asm
1057./mpn/x86/fat/gcd_1.c
3323./mpn/sparc64/gcd_1.asm
2807./mpn/powerpc64/mode64/gcd_1.asm
2520./mpn/powerpc64/mode64/p7/gcd_1.asm
2983./mpn/arm64/gcd_1.asm
2819./mpn/arm/v5/gcd_1.asm
2756./mpn/arm/v6t2/gcd_1.asm
4198./mpn/alpha/ev67/gcd_1.asm
 267./mpn/gcd_1.lo
1255./mpn/x86_64/bd1/gcd_1.asm
1255./mpn/x86_64/k10/gcd_1.asm
4260./mpn/x86_64/gcd_1.asm
4228./mpn/x86_64/core2/gcd_1.asm
1255./mpn/x86_64/zen/gcd_1.asm
1255./mpn/x86_64/nano/gcd_1.asm
phobos$ cat mpn/generic/gcd_1.c
/* mpn_gcd_1 -- mpn and limb greatest common divisor.

Copyright 1994, 1996, 2000, 2001, 2009, 2012 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of either:

  * the GNU Lesser General Public License as published by the Free
Software Foundation; either version 3 of the License, or (at your
option) any later version.

or

  * the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any
later version.

or both in parallel, as here.

The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received copies of the GNU General Public License and the
GNU Lesser General Public License along with the GNU MP Library.  If not,
see https://www.gnu.org/licenses/.  */

#include "gmp-impl.h"
#include "longlong.h"

#ifndef GCD_1_METHOD
#define GCD_1_METHOD 2
#endif

#define USE_ZEROTAB 0

#if USE_ZEROTAB
#define MAXSHIFT 4
#define MASK ((1 << MAXSHIFT) - 1)
static const unsigned char zerotab[1 << MAXSHIFT] =
{
#if MAXSHIFT > 4
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
#endif
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
#endif

/* Does not work for U == 0 or V == 0.  It would be tough to make it 
work for

   V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.

   The threshold for doing u%v when size==1 will vary by CPU according to
   the speed of a division and the code generated for the main loop.  Any
   tuning for this is left to a CPU specific implementation.  */

mp_limb_t
mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
{
  mp_limb_t  ulimb;
  unsigned long  zero_bits, u_low_zero_bits;

  ASSERT (size >= 1);
  ASSERT (vlimb != 0);
  ASSERT_MPN_NONZERO_P (up, size);

  ulimb = up[0];

  /* Need vlimb odd for modexact, want it odd to get common zeros. */
  count_trailing_zeros (zero_bits, vlimb);
  vlimb >>= zero_bits;

  if (size > 1)
{
  /* Must get common zeros before the mod reduction.  If ulimb==0 then
 vlimb already gives the common zeros.  */
  if (ulimb != 0)
{
  count_trailing_zeros (u_low_zero_bits, ulimb);
  zero_bits = MIN (zero_bits, u_low_zero_bits);
}

  ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
  if (ulimb == 0)
goto done;

  goto strip_u_maybe;
}

  /* size==1, so up[0]!=0 */
  count_trailing_zeros (u_low_zero_bits, ulimb);
  ulimb >>= u_low_zero_bits;
  zero_bits = MIN (zero_bits, u_low_zero_bits);

  /* make u bigger */
  if (vlimb > ulimb)
MP_LIMB_T_SWAP (ulimb, vlimb);

  /* if u is much bigger than v, reduce using a division rather than
 chipping away at it bit-by-bit */
  if ((ulimb >> 16) > vlimb)
{
  ulimb %= vlimb;
  if (ulimb == 

Re: Likely GMP bug

[Torbjörn Granlund]

ni...@lysator.liu.se (Niels Möller) writes:

  And code is essentially 

count_trailing_zeros (c, t);
ulimb >>= (c + 1);

  The intention is to shift right to get rid of both trailing zero bits,
  and the redundant least significant one bit.

  That fails with undefined behavior if by chance t == 2^31, so that c ==
  31.

And ubsan complains about exactly that.

  I don't see how that can happen, though, since ulimb, vlimb < 2^31
  through out the loop, and t = (ulimb - vlimb) mod 2^32.

The setting GMP_CHECK_RANDOMIZE=140064609456624 seems to trigger it, but
that could of course also be bugs in the compiler.

  And I also wonder why USE_ZEROTAB is set to 0 here.

That might be good as count_trailing_zeros is usually fast.

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

Re: Likely GMP bug

[Dennis Clarke]

On 05/25/2018 04:45 AM, Torbjörn Granlund wrote:

If somebody could take a look at

https://gmplib.org/devel/tm/gmp/check/failure/ivygentoo32.gmplib.org-dyn-noasm-ubsan:32.txt

I would appreciate it.  (I  am traveling.)



This seems to require --disable-assembly during configure ..
... starting over   :-\

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

Re: Likely GMP bug

[Dennis Clarke]

On 05/25/2018 04:45 AM, Torbjörn Granlund wrote:

If somebody could take a look at

https://gmplib.org/devel/tm/gmp/check/failure/ivygentoo32.gmplib.org-dyn-noasm-ubsan:32.txt

I would appreciate it.  (I  am traveling.)



Not able to reproduce that failure with gmp-6.1.99-20180525 :


configure: summary of build options:

  Version:   GNU MP 6.1.99
  Host type: pentium2-pc-linux-gnu
  ABI:   32
  Install prefix:/usr/local
  Compiler:  gcc
  Static libraries:  yes
  Shared libraries:  yes


Every test passes.

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

Likely GMP bug

[Torbjörn Granlund]

If somebody could take a look at

https://gmplib.org/devel/tm/gmp/check/failure/ivygentoo32.gmplib.org-dyn-noasm-ubsan:32.txt

I would appreciate it.  (I  am traveling.)

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