From 356a4599acd4c835ab88c221bd5da073c9895e83 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Mon, 30 Aug 2004 06:14:31 +0000 Subject: Teach the random module about os.urandom(). * Use it for seeding when it is available. * Provide an alternate generator based on it. --- Doc/lib/librandom.tex | 18 ++++++++- Lib/random.py | 70 +++++++++++++++++++++++++++++---- Lib/test/test_random.py | 102 ++++++++++++++++++++++++++++++++++++++++++++++++ Misc/NEWS | 3 ++ 4 files changed, 183 insertions(+), 10 deletions(-) diff --git a/Doc/lib/librandom.tex b/Doc/lib/librandom.tex index 2b686ec..787e134 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 7ec6583..06990d2 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 ead0dca..0396e58 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 660c49f..58bd464 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 -- cgit v0.12