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

Side by Side Diff: Python/random.c

Issue 13704: Random number generator in Python core
Patch Set: Created 8 years ago
Left:
Right:
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 unified diff | Download patch
OLDNEW
(Empty)
1 #include "Python.h"
2 #include "pyrandom.h"
3 #include <time.h>
4
5 #ifndef DEV_URANDOM
6 #define DEV_URANDOM "/dev/urandom"
7 #endif
8
9 /* raise a fatal error when the interpreter is in the early initialization
10 * phase
11 * XXX: replace with something better than Py_RndHashSeed == -1
12 * */
13
14 #define error_string(exc, msg) do { \
15 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
16 Py_FatalError(msg); \
17 } else { \
18 PyErr_SetString(exc, msg); \
19 } \
20 } while(0)
21
22 #define error_errno(exc, filename, msg) do { \
23 if (Py_RndHashSeed == -1) { \
24 Py_FatalError(msg); \
25 } else { \
26 PyErr_SetFromErrnoWithFilename(exc, filename); \
27 } \
28 } while(0)
29
30
31 #ifdef MS_WINDOWS
32
33 #define win32_error(function, filename) do { \
34 if (Py_RndHashSeed == -1) { \
35 Py_FatalError(function); \
36 } else { \
37 errno = GetLastError(); \
38 PyErr_SetFromWindowsErr(errno) \
39 } \
40 } while(0)
41
42 typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTA)(HCRYPTPROV *phProv,\
43 LPCSTR pszContainer, LPCSTR pszProvider, DWORD dwProvType,\
44 DWORD dwFlags );
45 typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV hProv, DWORD dwLen,\
46 BYTE *pbBuffer );
47
48 static CRYPTGENRANDOM pCryptGenRandom = NULL;
49 /* This handle is never explicitly released. Instead, the operating
50 system will release it when the process terminates. */
51 static HCRYPTPROV hCryptProv = 0;
52
53 /*
54 * Read random data with CryptGenRandom()
55 *
56 * In case of error, an exception is set
57 *
58 * @param buf: input buffer
59 * @param len: how many bytes to read into buf
60 * @return: 0 on success, -1 on error
61 */
62 int
63 PyOS_URandom(unsigned char *buf, Py_ssize_t len)
64 {
65 if (len < 0) {
66 error_string(PyExc_ValueError,
67 "negative argument not allowed");
68 return -1;
69 }
70
71 if (hCryptProv == 0) {
loewis 2012/01/03 23:52:35 Since using a RNG becomes essentially mandatory wi
72 HINSTANCE hAdvAPI32 = NULL;
73 CRYPTACQUIRECONTEXTA pCryptAcquireContext = NULL;
74
75 /* Obtain handle to the DLL containing CryptoAPI
76 This should not fail */
77 hAdvAPI32 = GetModuleHandle("advapi32.dll");
78 if (hAdvAPI32 == NULL) {
79 win32_error("GetModuleHandle", NULL);
80 return -1
81 }
82
83 /* Obtain pointers to the CryptoAPI functions
84 This will fail on some early versions of Win95 */
85 pCryptAcquireContext = (CRYPTACQUIRECONTEXTA)GetProcAddress(
86 hAdvAPI32,
87 "CryptAcquireContextA");
88 if (pCryptAcquireContext == NULL) {
89 error_string(PyExc_NotImplementedError,
90 "CryptAcquireContextA not found");
91 return -1;
92 }
93
94 pCryptGenRandom = (CRYPTGENRANDOM)GetProcAddress(
95 hAdvAPI32, "CryptGenRandom");
96 if (pCryptGenRandom == NULL) {
97 error_string(PyExc_NotImplementedError,
98 "CryptGenRandom not found");
99 return -1;
100 }
101
102 /* Acquire context */
103 if (! pCryptAcquireContext(&hCryptProv, NULL, NULL,
104 PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) {
105 win32_error("CryptAcquireContext", NULL);
106 return -1;
107 }
108 }
109
110 /* Get random data */
111 memset(buf, 0, len); /* zero seed */
112 if (!pCryptGenRandom(hCryptProv, len, buf)) {
113 win32_error("CryptGenRandom", NULL);
114 return -1;
115 }
116 }
117 return 0;
118 }
119 #else
120
121 #include <sys/types.h>
122 #include <sys/stat.h>
123 #include <fcntl.h>
124
125 /*
126 * Read random data from /dev/urandom
127 *
128 * In case of error, an exception is set
129 *
130 * @param buf: input buffer
131 * @param len: how many bytes to read into buf
132 * @return: 0 on success, -1 on error
133 */
134 int
135 PyOS_URandom(unsigned char *buf, Py_ssize_t len) {
136 int fd;
137 ssize_t pos, result = 0;
138
139 if (len < 0) {
140 error_string(PyExc_ValueError,
141 "negative argument not allowed");
142 return -1;
143 }
144
145 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
146 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
147 return -1;
148 }
149
150 while (pos < len) {
151 if ((result = read(fd, buf+pos, len-pos)) == -1) {
152 close(fd);
153 error_errno(PyExc_OSError, DEV_URANDOM, "Error reading from /dev/ura ndom");
154 return -1;
155 }
156 pos += result;
157 }
158 close(fd);
159 return 0;
160 }
161
162 #endif
163
164
165 /* ------------------------------------------------------------------
166 The code in this module was based on a download from:
167 http://www.math.keio.ac.jp/~matumoto/MT2002/emt19937ar.html
168
169 It was modified in 2002 by Raymond Hettinger as follows:
170
171 * the principal computational lines untouched.
172
173 * renamed genrand_res53() to random_random() and wrapped
174 in python calling/return code.
175
176 * genrand_int32() and the helper functions, init_genrand()
177 and init_by_array(), were declared static, wrapped in
178 Python calling/return code. also, their global data
179 references were replaced with structure references.
180
181 * unused functions from the original were deleted.
182 new, original C python code was added to implement the
183 Random() interface.
184
185 The following are the verbatim comments from the original code:
186
187 A C-program for MT19937, with initialization improved 2002/1/26.
188 Coded by Takuji Nishimura and Makoto Matsumoto.
189
190 Before using, initialize the state by using init_genrand(seed)
191 or init_by_array(init_key, key_length).
192
193 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
194 All rights reserved.
195
196 Redistribution and use in source and binary forms, with or without
197 modification, are permitted provided that the following conditions
198 are met:
199
200 1. Redistributions of source code must retain the above copyright
201 notice, this list of conditions and the following disclaimer.
202
203 2. Redistributions in binary form must reproduce the above copyright
204 notice, this list of conditions and the following disclaimer in the
205 documentation and/or other materials provided with the distribution.
206
207 3. The names of its contributors may not be used to endorse or promote
208 products derived from this software without specific prior written
209 permission.
210
211 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
212 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
213 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
214 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER O R
215 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
216 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
217 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
218 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
219 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
220 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
221 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
222
223
224 Any feedback is very welcome.
225 http://www.math.keio.ac.jp/matumoto/emt.html
226 email: matumoto@math.keio.ac.jp
227 */
228
229 /* ---------------------------------------------------------------*/
230
231 /* Period parameters -- These are all magic. Don't change. */
232 #define N _Py_MT_N
233 #define M 397
234 #define MATRIX_A 0x9908b0dfUL /* constant vector a */
235 #define UPPER_MASK 0x80000000UL /* most significant w-r bits */
236 #define LOWER_MASK 0x7fffffffUL /* least significant r bits */
237
238 /* Random methods */
239
240 /* generates a random number on [0,0xffffffff]-interval */
241 unsigned long
242 _Py_MT_GenRand_Int32(_Py_MT_RandomState *state)
243 {
244 unsigned long y;
245 static unsigned long mag01[2]={0x0UL, MATRIX_A};
246 /* mag01[x] = x * MATRIX_A for x=0,1 */
247 unsigned long *mt;
248
249 mt = state->state;
250 if (state->index >= N) { /* generate N words at one time */
251 int kk;
252
253 for (kk=0;kk<N-M;kk++) {
254 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
255 mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
256 }
257 for (;kk<N-1;kk++) {
258 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
259 mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
260 }
261 y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
262 mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
263
264 state->index = 0;
265 }
266
267 y = mt[state->index++];
268 y ^= (y >> 11);
269 y ^= (y << 7) & 0x9d2c5680UL;
270 y ^= (y << 15) & 0xefc60000UL;
271 y ^= (y >> 18);
272 return y;
273 }
274
275 /* random_random is the function named genrand_res53 in the original code;
276 * generates a random number on [0,1) with 53-bit resolution; note that
277 * 9007199254740992 == 2**53; I assume they're spelling "/2**53" as
278 * multiply-by-reciprocal in the (likely vain) hope that the compiler will
279 * optimize the division away at compile-time. 67108864 is 2**26. In
280 * effect, a contains 27 random bits shifted left 26, and b fills in the
281 * lower 26 bits of the 53-bit numerator.
282 * The orginal code credited Isaku Wada for this algorithm, 2002/01/09.
283 */
284 double
285 _Py_MT_GenRand_Res53(_Py_MT_RandomState *state)
286 {
287 unsigned long a=_Py_MT_GenRand_Int32(state)>>5, b=_Py_MT_GenRand_Int32(state )>>6;
288 return (a*67108864.0+b)*(1.0/9007199254740992.0);
289 }
290
291 /* initializes mt[N] with a seed */
292 void
293 _Py_MT_GenRand_Init(_Py_MT_RandomState *state, unsigned long s)
294 {
295 int mti;
296 unsigned long *mt;
297
298 mt = state->state;
299 mt[0]= s & 0xffffffffUL;
300 for (mti=1; mti<N; mti++) {
301 mt[mti] =
302 (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
303 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
304 /* In the previous versions, MSBs of the seed affect */
305 /* only MSBs of the array mt[]. */
306 /* 2002/01/09 modified by Makoto Matsumoto */
307 mt[mti] &= 0xffffffffUL;
308 /* for >32 bit machines */
309 }
310 state->index = mti;
311 return;
312 }
313
314 /* initialize by an array with array-length */
315 /* init_key is the array for initializing keys */
316 /* key_length is its length */
317 void
318 _Py_MT_GenRand_InitArray(_Py_MT_RandomState *state, unsigned long init_key[], un signed long key_length)
319 {
320 unsigned int i, j, k; /* was signed in the original code. RDH 12/16/20 02 */
321 unsigned long *mt;
322
323 mt = state->state;
324 _Py_MT_GenRand_Init(state, 19650218UL);
325 i=1; j=0;
326 k = (N>key_length ? N : key_length);
327 for (; k; k--) {
328 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
329 + init_key[j] + j; /* non linear */
330 mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
331 i++; j++;
332 if (i>=N) { mt[0] = mt[N-1]; i=1; }
333 if (j>=key_length) j=0;
334 }
335 for (k=N-1; k; k--) {
336 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
337 - i; /* non linear */
338 mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
339 i++;
340 if (i>=N) { mt[0] = mt[N-1]; i=1; }
341 }
342
343 mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
344 }
OLDNEW
« 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+