Re: Latest commit introduces undefined behavior in hgcd2.c

[Niels Möller]

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

> Or simply:
>
>   dh = (dh << dcnt) + (dl >> (GMP_LIMB_BITS - 1 - dcnt) >> 1);

Looks better, thanks.

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: Latest commit introduces undefined behavior in hgcd2.c

[Guido Vranken]

I don't mind if you don't fix it, but technically undefined behavior
can have consequences beyond the value of the involved variable.

On Wed, Sep 18, 2019 at 9:20 PM Torbjörn Granlund  wrote:
>
> Guido Vranken  writes:
>
>   My bignum fuzzer running at OSS-Fuzz came up with this:
>
>   hgcd2.c:223:42: runtime error: shift exponent 64 is too large for
>   64-bit type 'mp_limb_t' (aka 'unsigned long')
>   #0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42
>   #1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18
>   #2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11
>   #3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c
>
>   Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9
>
> I think it is a false positive.  The result of the shifted value is
> masked when the shift count is not in range.
>
> (We got the same false positive from our nightly testing using gcc's
> sanitized-something command-line option.)
>
> --
> Torbjörn
> Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Latest commit introduces undefined behavior in hgcd2.c

[Torbjörn Granlund]

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

  Is it reasonable to change it to

#define LIMB_SHIFT_MASK (GMP_LIMB_BITS - 1)
dh = (dh << dcnt) + (-(dcnt > 0) & (dl >> (LIMB_SHIFT_MASK & - dcnt)));

Or simply:

  dh = (dh << dcnt) + (dl >> (GMP_LIMB_BITS - 1 - dcnt) >> 1);


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

Re: Latest commit introduces undefined behavior in hgcd2.c

[Niels Möller]

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

> I think it is a false positive.  The result of the shifted value is
> masked when the shift count is not in range.

The line in question is

  dh = (dh << dcnt) + (-(dcnt > 0) & (dl >> (GMP_LIMB_BITS - dcnt)));

Should be fine if shift by 64 is "implementation defined", but a
problem, at least in theory, if it is "undefined behavior". I'm afraid I
don't know these fine details of the C spec by heart.

Is it reasonable to change it to

  #define LIMB_SHIFT_MASK (GMP_LIMB_BITS - 1)
  dh = (dh << dcnt) + (-(dcnt > 0) & (dl >> (LIMB_SHIFT_MASK & - dcnt)));

I'd expect compilers for common archs will generate the same code. It
depends on GMP_LIMB_BITS being a power of 2, though.

Vaguely related: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157. But
unlike rotate, an extra masking step seems necessary.

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: Latest commit introduces undefined behavior in hgcd2.c

[Vincent Lefevre]

On 2019-09-18 21:20:41 +0200, Torbjorn Granlund wrote:
> Guido Vranken  writes:
> 
>   My bignum fuzzer running at OSS-Fuzz came up with this:
> 
>   hgcd2.c:223:42: runtime error: shift exponent 64 is too large for
>   64-bit type 'mp_limb_t' (aka 'unsigned long')
>   #0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42
>   #1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18
>   #2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11
>   #3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c
> 
>   Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9
> 
> I think it is a false positive.  The result of the shifted value is
> masked when the shift count is not in range.

If the shift count is not in range, the behavior is undefined,
whatever you do with the "result". Having such undefined behavior
is a bug, as the compiler can do some optimization, such as
considering this as dead code. This is different from the case
where you have implementation-defined behavior.

-- 
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: Latest commit introduces undefined behavior in hgcd2.c

[Torbjörn Granlund]

Guido Vranken  writes:

  My bignum fuzzer running at OSS-Fuzz came up with this:

  hgcd2.c:223:42: runtime error: shift exponent 64 is too large for
  64-bit type 'mp_limb_t' (aka 'unsigned long')
  #0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42
  #1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18
  #2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11
  #3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c

  Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9

I think it is a false positive.  The result of the shifted value is
masked when the shift count is not in range.

(We got the same false positive from our nightly testing using gcc's
sanitized-something command-line option.)

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

Latest commit introduces undefined behavior in hgcd2.c

[Guido Vranken]

My bignum fuzzer running at OSS-Fuzz came up with this:

hgcd2.c:223:42: runtime error: shift exponent 64 is too large for
64-bit type 'mp_limb_t' (aka 'unsigned long')
#0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42
#1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18
#2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11
#3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c

Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs