Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(4)

Unified Diff: Python/random.c

Issue 13704: Random number generator in Python core
Patch Set: Created 8 years ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« Python/hash.c ('K') | « Python/pythonrun.c ('k') | Python/sysmodule.c » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/Python/random.c Tue Jan 03 21:48:43 2012 +0100
@@ -0,0 +1,344 @@
+#include "Python.h"
+#include "pyrandom.h"
+#include <time.h>
+
+#ifndef DEV_URANDOM
+#define DEV_URANDOM "/dev/urandom"
+#endif
+
+/* raise a fatal error when the interpreter is in the early initialization
+ * phase
+ * XXX: replace with something better than Py_RndHashSeed == -1
+ * */
+
+#define error_string(exc, msg) do { \
+ if (Py_RndHashSeed == -1) { \
AntoinePitrou 2012/01/04 18:54:01 These macros obscure the code. Why do you want to
gregory.p.smith 2012/01/15 02:18:38 Agreed, don't force a fatal error. -1 is a perfec
+ Py_FatalError(msg); \
+ } else { \
+ PyErr_SetString(exc, msg); \
+ } \
+ } while(0)
+
+#define error_errno(exc, filename, msg) do { \
+ if (Py_RndHashSeed == -1) { \
+ Py_FatalError(msg); \
+ } else { \
+ PyErr_SetFromErrnoWithFilename(exc, filename); \
+ } \
+ } while(0)
+
+
+#ifdef MS_WINDOWS
+
+#define win32_error(function, filename) do { \
+ if (Py_RndHashSeed == -1) { \
+ Py_FatalError(function); \
+ } else { \
+ errno = GetLastError(); \
+ PyErr_SetFromWindowsErr(errno) \
+ } \
+ } while(0)
+
+typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTA)(HCRYPTPROV *phProv,\
+ LPCSTR pszContainer, LPCSTR pszProvider, DWORD dwProvType,\
+ DWORD dwFlags );
+typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV hProv, DWORD dwLen,\
+ BYTE *pbBuffer );
+
+static CRYPTGENRANDOM pCryptGenRandom = NULL;
+/* This handle is never explicitly released. Instead, the operating
+ system will release it when the process terminates. */
+static HCRYPTPROV hCryptProv = 0;
+
+/*
+ * Read random data with CryptGenRandom()
+ *
+ * In case of error, an exception is set
+ *
+ * @param buf: input buffer
+ * @param len: how many bytes to read into buf
+ * @return: 0 on success, -1 on error
+ */
+int
+PyOS_URandom(unsigned char *buf, Py_ssize_t len)
+{
+ if (len < 0) {
+ error_string(PyExc_ValueError,
+ "negative argument not allowed");
+ return -1;
+ }
+
+ if (hCryptProv == 0) {
loewis 2012/01/03 23:52:35 Since using a RNG becomes essentially mandatory wi
+ HINSTANCE hAdvAPI32 = NULL;
+ CRYPTACQUIRECONTEXTA pCryptAcquireContext = NULL;
+
+ /* Obtain handle to the DLL containing CryptoAPI
+ This should not fail */
+ hAdvAPI32 = GetModuleHandle("advapi32.dll");
+ if (hAdvAPI32 == NULL) {
+ win32_error("GetModuleHandle", NULL);
+ return -1
+ }
+
+ /* Obtain pointers to the CryptoAPI functions
+ This will fail on some early versions of Win95 */
+ pCryptAcquireContext = (CRYPTACQUIRECONTEXTA)GetProcAddress(
+ hAdvAPI32,
+ "CryptAcquireContextA");
+ if (pCryptAcquireContext == NULL) {
+ error_string(PyExc_NotImplementedError,
+ "CryptAcquireContextA not found");
+ return -1;
+ }
+
+ pCryptGenRandom = (CRYPTGENRANDOM)GetProcAddress(
+ hAdvAPI32, "CryptGenRandom");
+ if (pCryptGenRandom == NULL) {
+ error_string(PyExc_NotImplementedError,
+ "CryptGenRandom not found");
+ return -1;
+ }
+
+ /* Acquire context */
+ if (! pCryptAcquireContext(&hCryptProv, NULL, NULL,
+ PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) {
+ win32_error("CryptAcquireContext", NULL);
+ return -1;
+ }
+ }
+
+ /* Get random data */
+ memset(buf, 0, len); /* zero seed */
+ if (!pCryptGenRandom(hCryptProv, len, buf)) {
+ win32_error("CryptGenRandom", NULL);
+ return -1;
+ }
+ }
+ return 0;
+}
+#else
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+/*
+ * Read random data from /dev/urandom
+ *
+ * In case of error, an exception is set
+ *
+ * @param buf: input buffer
+ * @param len: how many bytes to read into buf
+ * @return: 0 on success, -1 on error
+ */
+int
+PyOS_URandom(unsigned char *buf, Py_ssize_t len) {
+ int fd;
+ ssize_t pos, result = 0;
+
+ if (len < 0) {
+ error_string(PyExc_ValueError,
+ "negative argument not allowed");
+ return -1;
+ }
+
+ if ((fd = open(DEV_URANDOM, O_RDONLY)) == -1) {
AntoinePitrou 2012/01/04 18:54:01 You may want to release the GIL when doing I/O.
gregory.p.smith 2012/01/15 02:18:38 Agreed... But be careful! This is going to be cal
+ error_errno(PyExc_OSError, DEV_URANDOM, "Can't open /dev/urandom");
AntoinePitrou 2012/01/04 18:54:01 If DEV_URANDOM can be overriden, the error message
gregory.p.smith 2012/01/15 02:18:38 agreed. implicit string concatenation is your fri
+ return -1;
+ }
+
+ while (pos < len) {
+ if ((result = read(fd, buf+pos, len-pos)) == -1) {
+ close(fd);
+ error_errno(PyExc_OSError, DEV_URANDOM, "Error reading from /dev/urandom");
+ return -1;
+ }
+ pos += result;
+ }
+ close(fd);
+ return 0;
+}
+
+#endif
+
+
+/* ------------------------------------------------------------------
+ The code in this module was based on a download from:
+ http://www.math.keio.ac.jp/~matumoto/MT2002/emt19937ar.html
+
+ It was modified in 2002 by Raymond Hettinger as follows:
+
+ * the principal computational lines untouched.
+
+ * renamed genrand_res53() to random_random() and wrapped
+ in python calling/return code.
+
+ * genrand_int32() and the helper functions, init_genrand()
+ and init_by_array(), were declared static, wrapped in
+ Python calling/return code. also, their global data
+ references were replaced with structure references.
+
+ * unused functions from the original were deleted.
+ new, original C python code was added to implement the
+ Random() interface.
+
+ The following are the verbatim comments from the original code:
+
+ A C-program for MT19937, with initialization improved 2002/1/26.
+ Coded by Takuji Nishimura and Makoto Matsumoto.
+
+ Before using, initialize the state by using init_genrand(seed)
+ or init_by_array(init_key, key_length).
+
+ Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+
+ 1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+
+ 2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ 3. The names of its contributors may not be used to endorse or promote
+ products derived from this software without specific prior written
+ permission.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+ Any feedback is very welcome.
+ http://www.math.keio.ac.jp/matumoto/emt.html
+ email: matumoto@math.keio.ac.jp
+*/
+
+/* ---------------------------------------------------------------*/
+
+/* Period parameters -- These are all magic. Don't change. */
+#define N _Py_MT_N
+#define M 397
+#define MATRIX_A 0x9908b0dfUL /* constant vector a */
+#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
+#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
+
+/* Random methods */
+
+/* generates a random number on [0,0xffffffff]-interval */
+unsigned long
+_Py_MT_GenRand_Int32(_Py_MT_RandomState *state)
+{
+ unsigned long y;
+ static unsigned long mag01[2]={0x0UL, MATRIX_A};
+ /* mag01[x] = x * MATRIX_A for x=0,1 */
+ unsigned long *mt;
+
+ mt = state->state;
+ if (state->index >= N) { /* generate N words at one time */
+ int kk;
+
+ for (kk=0;kk<N-M;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ for (;kk<N-1;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
+ mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+
+ state->index = 0;
+ }
+
+ y = mt[state->index++];
+ y ^= (y >> 11);
+ y ^= (y << 7) & 0x9d2c5680UL;
+ y ^= (y << 15) & 0xefc60000UL;
+ y ^= (y >> 18);
+ return y;
+}
+
+/* random_random is the function named genrand_res53 in the original code;
+ * generates a random number on [0,1) with 53-bit resolution; note that
+ * 9007199254740992 == 2**53; I assume they're spelling "/2**53" as
+ * multiply-by-reciprocal in the (likely vain) hope that the compiler will
+ * optimize the division away at compile-time. 67108864 is 2**26. In
+ * effect, a contains 27 random bits shifted left 26, and b fills in the
+ * lower 26 bits of the 53-bit numerator.
+ * The orginal code credited Isaku Wada for this algorithm, 2002/01/09.
+ */
+double
+_Py_MT_GenRand_Res53(_Py_MT_RandomState *state)
+{
+ unsigned long a=_Py_MT_GenRand_Int32(state)>>5, b=_Py_MT_GenRand_Int32(state)>>6;
+ return (a*67108864.0+b)*(1.0/9007199254740992.0);
+}
+
+/* initializes mt[N] with a seed */
+void
+_Py_MT_GenRand_Init(_Py_MT_RandomState *state, unsigned long s)
+{
+ int mti;
+ unsigned long *mt;
+
+ mt = state->state;
+ mt[0]= s & 0xffffffffUL;
+ for (mti=1; mti<N; mti++) {
+ mt[mti] =
+ (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
+ /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+ /* In the previous versions, MSBs of the seed affect */
+ /* only MSBs of the array mt[]. */
+ /* 2002/01/09 modified by Makoto Matsumoto */
+ mt[mti] &= 0xffffffffUL;
+ /* for >32 bit machines */
+ }
+ state->index = mti;
+ return;
+}
+
+/* initialize by an array with array-length */
+/* init_key is the array for initializing keys */
+/* key_length is its length */
+void
+_Py_MT_GenRand_InitArray(_Py_MT_RandomState *state, unsigned long init_key[], unsigned long key_length)
+{
+ unsigned int i, j, k; /* was signed in the original code. RDH 12/16/2002 */
+ unsigned long *mt;
+
+ mt = state->state;
+ _Py_MT_GenRand_Init(state, 19650218UL);
+ i=1; j=0;
+ k = (N>key_length ? N : key_length);
+ for (; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
+ + init_key[j] + j; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++; j++;
+ if (i>=N) { mt[0] = mt[N-1]; i=1; }
+ if (j>=key_length) j=0;
+ }
+ for (k=N-1; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
+ - i; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++;
+ if (i>=N) { mt[0] = mt[N-1]; i=1; }
+ }
+
+ mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
+}
« Python/hash.c ('K') | « Python/pythonrun.c ('k') | Python/sysmodule.c » ('j') | no next file with comments »

RSS Feeds Recent Issues | This issue
This is Rietveld 894c83f36cb7+