This is the mail archive of the glibc-bugs@sourceware.org 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
                    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: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]