This is the mail archive of the glibc-bugs@sourceware.org mailing list for the glibc project.

Index Nav: Message Nav: [Date Index] [Subject Index] [Author Index] [Thread Index] [Date Prev] [Date Next] [Thread Prev] [Thread Next] [Raw text]

# [Bug libc/9920] New: use of `long int' in srandom_r changes results under 64bit

• From: "ben at ben dot com" <sourceware-bugzilla at sourceware dot org>
• To: glibc-bugs at sources dot redhat dot com
• Date: 3 Mar 2009 22:43:00 -0000
• Subject: [Bug libc/9920] New: use of `long int' in srandom_r changes results under 64bit
• Reply-to: sourceware-bugzilla at sourceware dot org

srandom_r (random_r.c) initializes a state vector for random_r using a LCRNG
based on a primitive root of 2^31-1 (a Mersenne prime).  The root is 7, and the
LCRNG uses 7^5 (16807).  16807^n % (2^31-1) touches every number in 1..(2^31-1)
as you iterate along n.  srandom_r uses this property to take the input seed
plus 30 more numbers to make a state vector which is subsequently used by
random_r().  The curious case is the first step, where a full 32-bit value is
used as the starting seed.

srandom_r takes an unsigned int seed, but does most of its work in int32_t.
Somewhere in the distant past someone came up with a trick for the modular
multiply by 16807:

long int word;
...
word = seed; /* seed is unsigned int */
...
/* This does:
state[i] = (16807 * state[i - 1]) % 2147483647;
but avoids overflowing 31 bits.  */
long int hi = word / 127773;
long int lo = word % 127773;
word = 16807 * lo - 2836 * hi;
if (word < 0)
word += 2147483647;
*++dst = word;

The problem is that 'long int' changes size between 32bit and 64bit builds.
When 'long int' is 64 bit, the entire unsigned seed value fits, so a seed above
2^31-1 does not fold into a negative.  So 'srandom(0xFFFFFFFFul); x = random()'
produces different results if glibc is built 64bit than if it is built 32bit.

The reason has to do with the multiply under modulo 2^31-1.  0xFFFFFFFFul
smashed into an int32_t acts like -1 which is congruent to 2147483646 (under mod
2^31-1).  When it's smashed into int64_t (long int under the 64 bit build) it
FITS so it's 4294967295 which is congruent to 1.  The seed itself is still
smashed into a 32 bit signed int *in the state vector* so you still get
different random output for a seed of -1 than for 1, just not what you'd get on
a 32 bit system.

I left severity at "normal" because some users of random() really care about
reproducibility with a given seed.  Any who do will be greatly surprised when
moving to 64 bit!

(this bug exists at glibc < 2.8, probably back at least to 2.5 and maybe
forever.  bsd libc has code clearly inspired by the same origins but calls out
the bit widths explicitly and avoids this problem)

--
Summary: use of `long int' in srandom_r changes results under
64bit
Product: glibc
Version: 2.8
Status: NEW
Severity: normal
Priority: P2
Component: libc
AssignedTo: drepper at redhat dot com
ReportedBy: ben at ben dot com
CC: glibc-bugs at sources dot redhat dot com,kenny at the-b
dot org
GCC build triplet: x86_64-redhat-linux
GCC host triplet: x86_64-redhat-linux
GCC target triplet: x86_64-redhat-linux

http://sourceware.org/bugzilla/show_bug.cgi?id=9920

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

Index Nav: Message Nav: [Date Index] [Subject Index] [Author Index] [Thread Index] [Date Prev] [Date Next] [Thread Prev] [Thread Next]