Teach the random module about os.urandom().

* Use it for seeding when it is available.
* Provide an alternate generator based on it.

4 files changed, 183 insertions, 10 deletions

diff --git a/Doc/lib/librandom.tex b/Doc/lib/librandom.tex
index 2b686ec4ff..787e13489c 100644
--- a/Doc/lib/librandom.tex
+++ b/Doc/lib/librandom.tex
@@ -61,7 +61,10 @@ Bookkeeping functions:
   Optional argument \var{x} can be any hashable object.
   If \var{x} is omitted or \code{None}, current system time is used;
   current system time is also used to initialize the generator when the
-  module is first imported.
+  module is first imported.  If hardware random sources are available,
+  they are used instead of the system time (see the \function{os.urandom()}
+  function for details on availability).  \versionchanged[formerly,
+  hardward sources were not used]{2.4}
   If \var{x} is not \code{None} or an int or long,
   \code{hash(\var{x})} is used instead.
   If \var{x} is an int or long, \var{x} is used directly.
@@ -227,7 +230,7 @@ these equations can be found in any statistics text.
   \var{beta} is the shape parameter.
 \end{funcdesc}
 
-Alternative Generator
+Alternative Generators
 
 \begin{classdesc}{WichmannHill}{\optional{seed}}
 Class that implements the Wichmann-Hill algorithm as the core generator.
@@ -246,6 +249,17 @@ require care that two independent random sequences do not overlap.
   yield no more than about 2**24 distinct internal states in all.
 \end{funcdesc}
 
+\begin{classdesc}{HardwareRandom}{\optional{seed}}
+Class that uses the \function{os.urandom()} function for generating
+random numbers from hardware.  Not available on all systems.
+Does not rely on software state and sequences are not reproducible.
+Accordingly, the \method{seed()} and \method{jumpahead()} methods
+have no effect and are ignored.  The \method{getstate()} and
+\method{setstate()} methods raise \exception{NotImplementedError} if
+called.
+\versionadded{2.4}
+\end{classdesc}
+
 \begin{seealso}
   \seetext{M. Matsumoto and T. Nishimura, ``Mersenne Twister: A
 	   623-dimensionally equidistributed uniform pseudorandom
diff --git a/Lib/random.py b/Lib/random.py
index 7ec6583af4..06990d243a 100644
--- a/Lib/random.py
+++ b/Lib/random.py
@@ -49,7 +49,8 @@ __all__ = ["Random","seed","random","uniform","randint","choice","sample",
            "randrange","shuffle","normalvariate","lognormvariate",
            "expovariate","vonmisesvariate","gammavariate",
            "gauss","betavariate","paretovariate","weibullvariate",
-           "getstate","setstate","jumpahead", "WichmannHill", "getrandbits"]
+           "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
+           "HardwareRandom"]
 
 NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
 TWOPI = 2.0*_pi
@@ -57,6 +58,15 @@ LOG4 = _log(4.0)
 SG_MAGICCONST = 1.0 + _log(4.5)
 BPF = 53        # Number of bits in a float
 
+try:
+    from os import urandom as _urandom
+    from binascii import hexlify as _hexlify
+except ImportError:
+    _urandom = None
+else:
+    _tofloat = 2.0 ** (-7*8)    # converts 7 byte integers to floats
+
+
 # Translated by Guido van Rossum from C source provided by
 # Adrian Baddeley.  Adapted by Raymond Hettinger for use with
 # the Mersenne Twister core generator.
@@ -94,14 +104,19 @@ class Random(_random.Random):
     def seed(self, a=None):
         """Initialize internal state from hashable object.
 
-        None or no argument seeds from current time.
+        None or no argument seeds from current time or from a hardware
+        randomness source if available.
 
         If a is not None or an int or long, hash(a) is used instead.
         """
 
         if a is None:
-            import time
-            a = long(time.time() * 256) # use fractional seconds
+            if _urandom is None:
+                import time
+                a = long(time.time() * 256) # use fractional seconds
+            else:
+                a = long(_hexlify(_urandom(16)), 16)
+
         super(Random, self).seed(a)
         self.gauss_next = None
 
@@ -593,7 +608,8 @@ class WichmannHill(Random):
     def seed(self, a=None):
         """Initialize internal state from hashable object.
 
-        None or no argument seeds from current time.
+        None or no argument seeds from current time or from a hardware
+        randomness source if available.
 
         If a is not None or an int or long, hash(a) is used instead.
 
@@ -604,9 +620,11 @@ class WichmannHill(Random):
         """
 
         if a is None:
-            # Initialize from current time
-            import time
-            a = long(time.time() * 256)
+            if _urandom is None:
+                import time
+                a = long(time.time() * 256) # use fractional seconds
+            else:
+                a = long(_hexlify(_urandom(16)), 16)
 
         if not isinstance(a, (int, long)):
             a = hash(a)
@@ -731,6 +749,42 @@ class WichmannHill(Random):
         z = (z + a) % 256 or 1
         self.__whseed(x, y, z)
 
+## -------------------- Hardware Random Source  -------------------
+
+class HardwareRandom(Random):
+    """Alternate random number generator using hardware sources.
+
+     Not available on all systems (see os.urandom() for details).
+    """
+
+    def random(self):
+        """Get the next random number in the range [0.0, 1.0)."""
+        if _urandom is None:
+            raise NotImplementedError('Cannot find hardware entropy source')
+        return long(_hexlify(_urandom(7)), 16) * _tofloat
+
+    def getrandbits(self, k):
+        """getrandbits(k) -> x.  Generates a long int with k random bits."""
+        if _urandom is None:
+            raise NotImplementedError('Cannot find hardware entropy source')
+        if k <= 0:
+            raise ValueError('number of bits must be greater than zero')
+        if k != int(k):
+            raise TypeError('number of bits should be an integer')
+        bytes = (k + 7) // 8                    # bits / 8 and rounded up
+        x = long(_hexlify(_urandom(bytes)), 16)
+        return x >> (bytes * 8 - k)             # trim excess bits
+
+    def _stub(self, *args, **kwds):
+        "Stub method.  Not used for a hardware random number generator."
+        return None
+    seed = jumpahead = _stub
+
+    def _notimplemented(self, *args, **kwds):
+        "Method should not be called for a hardware random number generator."
+        raise NotImplementedError('Hardware entropy source does not have state.')
+    getstate = setstate = _notimplemented
+
 ## -------------------- test program --------------------
 
 def _test_generator(n, func, args):
diff --git a/Lib/test/test_random.py b/Lib/test/test_random.py
index ead0dca67c..0396e586ce 100644
--- a/Lib/test/test_random.py
+++ b/Lib/test/test_random.py
@@ -164,6 +164,107 @@ class WichmannHill_TestBasicOps(TestBasicOps):
         self.assertRaises(UserWarning, self.gen.randrange, 2**60)
         warnings.filters[:] = oldfilters
 
+class HardwareRandom_TestBasicOps(TestBasicOps):
+    gen = random.HardwareRandom()
+
+    def test_autoseed(self):
+        # Doesn't need to do anything except not fail
+        self.gen.seed()
+
+    def test_saverestore(self):
+        self.assertRaises(NotImplementedError, self.gen.getstate)
+        self.assertRaises(NotImplementedError, self.gen.setstate, None)
+
+    def test_seedargs(self):
+        # Doesn't need to do anything except not fail
+        self.gen.seed(100)
+
+    def test_jumpahead(self):
+        # Doesn't need to do anything except not fail
+        self.gen.jumpahead(100)
+
+    def test_gauss(self):
+        self.gen.gauss_next = None
+        self.gen.seed(100)
+        self.assertEqual(self.gen.gauss_next, None)
+
+    def test_pickling(self):
+        self.assertRaises(NotImplementedError, pickle.dumps, self.gen)
+
+    def test_53_bits_per_float(self):
+        # This should pass whenever a C double has 53 bit precision.
+        span = 2 ** 53
+        cum = 0
+        for i in xrange(100):
+            cum |= int(self.gen.random() * span)
+        self.assertEqual(cum, span-1)
+
+    def test_bigrand(self):
+        # The randrange routine should build-up the required number of bits
+        # in stages so that all bit positions are active.
+        span = 2 ** 500
+        cum = 0
+        for i in xrange(100):
+            r = self.gen.randrange(span)
+            self.assert_(0 <= r < span)
+            cum |= r
+        self.assertEqual(cum, span-1)
+
+    def test_bigrand_ranges(self):
+        for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
+            start = self.gen.randrange(2 ** i)
+            stop = self.gen.randrange(2 ** (i-2))
+            if stop <= start:
+                return
+            self.assert_(start <= self.gen.randrange(start, stop) < stop)
+
+    def test_rangelimits(self):
+        for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
+            self.assertEqual(set(range(start,stop)),
+                set([self.gen.randrange(start,stop) for i in xrange(100)]))
+
+    def test_genrandbits(self):
+        # Verify ranges
+        for k in xrange(1, 1000):
+            self.assert_(0 <= self.gen.getrandbits(k) < 2**k)
+
+        # Verify all bits active
+        getbits = self.gen.getrandbits
+        for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
+            cum = 0
+            for i in xrange(100):
+                cum |= getbits(span)
+            self.assertEqual(cum, 2**span-1)
+
+        # Verify argument checking
+        self.assertRaises(TypeError, self.gen.getrandbits)
+        self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
+        self.assertRaises(ValueError, self.gen.getrandbits, 0)
+        self.assertRaises(ValueError, self.gen.getrandbits, -1)
+        self.assertRaises(TypeError, self.gen.getrandbits, 10.1)
+
+    def test_randbelow_logic(self, _log=log, int=int):
+        # check bitcount transition points:  2**i and 2**(i+1)-1
+        # show that: k = int(1.001 + _log(n, 2))
+        # is equal to or one greater than the number of bits in n
+        for i in xrange(1, 1000):
+            n = 1L << i # check an exact power of two
+            numbits = i+1
+            k = int(1.00001 + _log(n, 2))
+            self.assertEqual(k, numbits)
+            self.assert_(n == 2**(k-1))
+
+            n += n - 1      # check 1 below the next power of two
+            k = int(1.00001 + _log(n, 2))
+            self.assert_(k in [numbits, numbits+1])
+            self.assert_(2**k > n > 2**(k-2))
+
+            n -= n >> 15     # check a little farther below the next power of two
+            k = int(1.00001 + _log(n, 2))
+            self.assertEqual(k, numbits)        # note the stronger assertion
+            self.assert_(2**k > n > 2**(k-1))   # note the stronger assertion
+
+
 class MersenneTwister_TestBasicOps(TestBasicOps):
     gen = random.Random()
 
@@ -391,6 +492,7 @@ class TestModule(unittest.TestCase):
 def test_main(verbose=None):
     testclasses =    (WichmannHill_TestBasicOps,
                       MersenneTwister_TestBasicOps,
+                      HardwareRandom_TestBasicOps,
                       TestDistributions,
                       TestModule)
     test_support.run_unittest(*testclasses)
diff --git a/Misc/NEWS b/Misc/NEWS
index 660c49fa75..58bd46460a 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -79,6 +79,9 @@ Extension modules
 Library
 -------
 
+- the random module now uses os.urandom() for seeding if it is available.
+  Added a new generator based on os.urandom().
+
 - difflib and diff.py can now generate HTML.
 
 - bdist_rpm now includes version and release in the BuildRoot, and