[PATCH] fix a bug in the rand48 family of prng

[PATCH] fix a bug in the rand48 family of prng

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 674 bytes --]


This fixes a bug found by Nadav Har'El, who observed that musl was giving
different prn sequences than other systems, even if seeded with the same
value.

The problem with something like

a = lc[0] | lc[1]<<16 | lc[2]+0ULL<<32;

where lc[1] is an unsigned short and int is 32bit is the following

(1) lc[1] is promoted to int
(2) the left shift 16 is performed on int

this is UB if bit 15 is set in lc[1], since it moves a 1 into the sign
bit.

In particular, bit 15 *is* 1 for the default multplicator A as defined by POSIX.

(On systems with 16 bit int all of this has UB anyhow.)
---
 src/prng/__rand48_step.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)


[-- Attachment #2: 0001-fix-a-bug-in-the-rand48-family-of-prng.patch --]
[-- Type: text/x-patch, Size: 484 bytes --]

diff --git a/src/prng/__rand48_step.c b/src/prng/__rand48_step.c
index ccaffc3..a87bea6 100644
--- a/src/prng/__rand48_step.c
+++ b/src/prng/__rand48_step.c
@@ -3,8 +3,8 @@
 uint64_t __rand48_step(unsigned short *xi, unsigned short *lc)
 {
 	uint64_t a, x;
-	x = xi[0] | xi[1]<<16 | xi[2]+0ULL<<32;
-	a = lc[0] | lc[1]<<16 | lc[2]+0ULL<<32;
+	x = xi[0] | xi[1]+0ULL<<16 | xi[2]+0ULL<<32;
+	a = lc[0] | lc[1]+0ULL<<16 | lc[2]+0ULL<<32;
 	x = a*x + lc[3];
 	xi[0] = x;
 	xi[1] = x>>16;

Re: [PATCH] fix a bug in the rand48 family of prng

[Szabolcs Nagy]

* Jens Gustedt <Jens.Gustedt@inria.fr> [2014-09-21 16:39:34 +0200]:
> 
> This fixes a bug found by Nadav Har'El, who observed that musl was giving
> different prn sequences than other systems, even if seeded with the same
> value.
> 
> The problem with something like
> 
> a = lc[0] | lc[1]<<16 | lc[2]+0ULL<<32;
> 
> where lc[1] is an unsigned short and int is 32bit is the following
> 
> (1) lc[1] is promoted to int
> (2) the left shift 16 is performed on int
> 

the fix looks ok, but i'm not clear on why it breaks in practice

(i know it's ub, but gcc used to handle such shifts "as expected"
the linux kernel is full of them and c++14 allows this and there
is a dr to change the semantics for c too
http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_463.htm
)

> this is UB if bit 15 is set in lc[1], since it moves a 1 into the sign
> bit.
> 
> In particular, bit 15 *is* 1 for the default multplicator A as defined by POSIX.
> 
> (On systems with 16 bit int all of this has UB anyhow.)

posix requires at least 32 bit int

Re: [PATCH] fix a bug in the rand48 family of prng

[Alexander Monakov]

On Sun, 21 Sep 2014, Szabolcs Nagy wrote:

> * Jens Gustedt <Jens.Gustedt@inria.fr> [2014-09-21 16:39:34 +0200]:
> > 
> > This fixes a bug found by Nadav Har'El, who observed that musl was giving
> > different prn sequences than other systems, even if seeded with the same
> > value.
> > 
> > The problem with something like
> > 
> > a = lc[0] | lc[1]<<16 | lc[2]+0ULL<<32;
> > 
> > where lc[1] is an unsigned short and int is 32bit is the following
> > 
> > (1) lc[1] is promoted to int
> > (2) the left shift 16 is performed on int
> > 
> 
> the fix looks ok, but i'm not clear on why it breaks in practice

UB on shift shouldn't be a problem here; I think the issue is that
"lc[0] | lc[1]<<16" gets sign-extended rather than zero-extended from 32 bit
to 64 bit.

Alexander

Re: [PATCH] fix a bug in the rand48 family of prng

[Alexander Monakov]

On Sun, 21 Sep 2014, Alexander Monakov wrote:

> UB on shift shouldn't be a problem here; I think the issue is that
> "lc[0] | lc[1]<<16" gets sign-extended rather than zero-extended from 32 bit
> to 64 bit.

(sorry, sent previous email too soon)

example code:

unsigned short a[3];
long long foo()
{
  return a[0] | a[1]    << 16 | a[2]+0ull<<32;
}
long long bar()
{
  return a[0] | a[1]+0u << 16 | a[2]+0ull<<32;
}

Incidentally I think a "+0u" should suffice as a fix rather that "+0ull".

Alexander

Re: [PATCH] fix a bug in the rand48 family of prng

[Szabolcs Nagy]

* Alexander Monakov <amonakov@ispras.ru> [2014-09-21 20:01:08 +0400]:
> unsigned short a[3];
> long long foo()
> {
>   return a[0] | a[1]    << 16 | a[2]+0ull<<32;
> }
> long long bar()
> {
>   return a[0] | a[1]+0u << 16 | a[2]+0ull<<32;
> }

ah yes signextension explains the problem


btw original mail said:

>        printf("%ld %ld %ld\n", lrand48(), lrand48(), lrand48());
> ...
> I expected to get the same sequence because...

the arg evaluation order is unspecified so
one should expect the same numbers but not
in the same order for this test

Re: [PATCH] fix a bug in the rand48 family of prng

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1728 bytes --]

Am Sonntag, den 21.09.2014, 17:34 +0200 schrieb Szabolcs Nagy:
> * Jens Gustedt <Jens.Gustedt@inria.fr> [2014-09-21 16:39:34 +0200]:
> > 
> > This fixes a bug found by Nadav Har'El, who observed that musl was giving
> > different prn sequences than other systems, even if seeded with the same
> > value.
> > 
> > The problem with something like
> > 
> > a = lc[0] | lc[1]<<16 | lc[2]+0ULL<<32;
> > 
> > where lc[1] is an unsigned short and int is 32bit is the following
> > 
> > (1) lc[1] is promoted to int
> > (2) the left shift 16 is performed on int
> > 
> 
> the fix looks ok, but i'm not clear on why it breaks in practice

I was curious, too. The assembler looks a bit different, so it is not
so easy to tell. But it looks to me that the problem comes from a cltq
instruction that is inserted in the faulty code. It probably sets the
high bits of %rax to 1 before the or-ing of the different parts takes
place.

I think the cltq instruction comes handy to zero out the the high
order bits of the %rax register in the defined case.

> (i know it's ub, but gcc used to handle such shifts "as expected"
> the linux kernel is full of them and c++14 allows this and there
> is a dr to change the semantics for c too
> http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_463.htm
> )

right, so this here can serve as an example why this ain't so easy to
define that behavior.

Jens

-- 
:: INRIA Nancy Grand Est ::: AlGorille ::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]