This is the mail archive of the mailing list for the glibc project.

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

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

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

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

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