1 /* Random objects */
2
3 /* ------------------------------------------------------------------
4 The code in this module was based on a download from:
5 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
6
7 It was modified in 2002 by Raymond Hettinger as follows:
8
9 * the principal computational lines untouched.
10
11 * renamed genrand_res53() to random_random() and wrapped
12 in python calling/return code.
13
14 * genrand_uint32() and the helper functions, init_genrand()
15 and init_by_array(), were declared static, wrapped in
16 Python calling/return code. also, their global data
17 references were replaced with structure references.
18
19 * unused functions from the original were deleted.
20 new, original C python code was added to implement the
21 Random() interface.
22
23 The following are the verbatim comments from the original code:
24
25 A C-program for MT19937, with initialization improved 2002/1/26.
26 Coded by Takuji Nishimura and Makoto Matsumoto.
27
28 Before using, initialize the state by using init_genrand(seed)
29 or init_by_array(init_key, key_length).
30
31 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
32 All rights reserved.
33
34 Redistribution and use in source and binary forms, with or without
35 modification, are permitted provided that the following conditions
36 are met:
37
38 1. Redistributions of source code must retain the above copyright
39 notice, this list of conditions and the following disclaimer.
40
41 2. Redistributions in binary form must reproduce the above copyright
42 notice, this list of conditions and the following disclaimer in the
43 documentation and/or other materials provided with the distribution.
44
45 3. The names of its contributors may not be used to endorse or promote
46 products derived from this software without specific prior written
47 permission.
48
49 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
50 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
51 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
52 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
53 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
54 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
55 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
56 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
57 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
58 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
59 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
60
61
62 Any feedback is very welcome.
63 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
64 email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
65 */
66
67 /* ---------------------------------------------------------------*/
68
69 #ifndef Py_BUILD_CORE_BUILTIN
70 # define Py_BUILD_CORE_MODULE 1
71 #endif
72
73 #include "Python.h"
74 #include "pycore_long.h" // _PyLong_NumBits()
75 #include "pycore_modsupport.h" // _PyArg_NoKeywords()
76 #include "pycore_moduleobject.h" // _PyModule_GetState()
77 #include "pycore_pylifecycle.h" // _PyOS_URandomNonblock()
78
79 #ifdef HAVE_UNISTD_H
80 # include <unistd.h> // getpid()
81 #endif
82 #ifdef HAVE_PROCESS_H
83 # include <process.h> // getpid()
84 #endif
85 #ifdef MS_WINDOWS
86 # include <windows.h> // GetCurrentProcessId()
87 #endif
88
89 /* Period parameters -- These are all magic. Don't change. */
90 #define N 624
91 #define M 397
92 #define MATRIX_A 0x9908b0dfU /* constant vector a */
93 #define UPPER_MASK 0x80000000U /* most significant w-r bits */
94 #define LOWER_MASK 0x7fffffffU /* least significant r bits */
95
96 typedef struct {
97 PyObject *Random_Type;
98 PyObject *Long___abs__;
99 } _randomstate;
100
101 static inline _randomstate*
get_random_state(PyObject * module)102 get_random_state(PyObject *module)
103 {
104 void *state = _PyModule_GetState(module);
105 assert(state != NULL);
106 return (_randomstate *)state;
107 }
108
109 static struct PyModuleDef _randommodule;
110
111 #define _randomstate_type(type) \
112 (get_random_state(PyType_GetModuleByDef(type, &_randommodule)))
113
114 typedef struct {
115 PyObject_HEAD
116 int index;
117 uint32_t state[N];
118 } RandomObject;
119
120
121 #include "clinic/_randommodule.c.h"
122
123 /*[clinic input]
124 module _random
125 class _random.Random "RandomObject *" "_randomstate_type(type)->Random_Type"
126 [clinic start generated code]*/
127 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=70a2c99619474983]*/
128
129 /* Random methods */
130
131
132 /* generates a random number on [0,0xffffffff]-interval */
133 static uint32_t
genrand_uint32(RandomObject * self)134 genrand_uint32(RandomObject *self)
135 {
136 uint32_t y;
137 static const uint32_t mag01[2] = {0x0U, MATRIX_A};
138 /* mag01[x] = x * MATRIX_A for x=0,1 */
139 uint32_t *mt;
140
141 mt = self->state;
142 if (self->index >= N) { /* generate N words at one time */
143 int kk;
144
145 for (kk=0;kk<N-M;kk++) {
146 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
147 mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
148 }
149 for (;kk<N-1;kk++) {
150 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
151 mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
152 }
153 y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
154 mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
155
156 self->index = 0;
157 }
158
159 y = mt[self->index++];
160 y ^= (y >> 11);
161 y ^= (y << 7) & 0x9d2c5680U;
162 y ^= (y << 15) & 0xefc60000U;
163 y ^= (y >> 18);
164 return y;
165 }
166
167 /* random_random is the function named genrand_res53 in the original code;
168 * generates a random number on [0,1) with 53-bit resolution; note that
169 * 9007199254740992 == 2**53; I assume they're spelling "/2**53" as
170 * multiply-by-reciprocal in the (likely vain) hope that the compiler will
171 * optimize the division away at compile-time. 67108864 is 2**26. In
172 * effect, a contains 27 random bits shifted left 26, and b fills in the
173 * lower 26 bits of the 53-bit numerator.
174 * The original code credited Isaku Wada for this algorithm, 2002/01/09.
175 */
176
177 /*[clinic input]
178 @critical_section
179 _random.Random.random
180
181 self: self(type="RandomObject *")
182
183 random() -> x in the interval [0, 1).
184 [clinic start generated code]*/
185
186 static PyObject *
_random_Random_random_impl(RandomObject * self)187 _random_Random_random_impl(RandomObject *self)
188 /*[clinic end generated code: output=117ff99ee53d755c input=26492e52d26e8b7b]*/
189 {
190 uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;
191 return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
192 }
193
194 /* initializes mt[N] with a seed */
195 static void
init_genrand(RandomObject * self,uint32_t s)196 init_genrand(RandomObject *self, uint32_t s)
197 {
198 int mti;
199 uint32_t *mt;
200
201 mt = self->state;
202 mt[0]= s;
203 for (mti=1; mti<N; mti++) {
204 mt[mti] =
205 (1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
206 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
207 /* In the previous versions, MSBs of the seed affect */
208 /* only MSBs of the array mt[]. */
209 /* 2002/01/09 modified by Makoto Matsumoto */
210 }
211 self->index = mti;
212 return;
213 }
214
215 /* initialize by an array with array-length */
216 /* init_key is the array for initializing keys */
217 /* key_length is its length */
218 static void
init_by_array(RandomObject * self,uint32_t init_key[],size_t key_length)219 init_by_array(RandomObject *self, uint32_t init_key[], size_t key_length)
220 {
221 size_t i, j, k; /* was signed in the original code. RDH 12/16/2002 */
222 uint32_t *mt;
223
224 mt = self->state;
225 init_genrand(self, 19650218U);
226 i=1; j=0;
227 k = (N>key_length ? N : key_length);
228 for (; k; k--) {
229 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U))
230 + init_key[j] + (uint32_t)j; /* non linear */
231 i++; j++;
232 if (i>=N) { mt[0] = mt[N-1]; i=1; }
233 if (j>=key_length) j=0;
234 }
235 for (k=N-1; k; k--) {
236 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U))
237 - (uint32_t)i; /* non linear */
238 i++;
239 if (i>=N) { mt[0] = mt[N-1]; i=1; }
240 }
241
242 mt[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */
243 }
244
245 /*
246 * The rest is Python-specific code, neither part of, nor derived from, the
247 * Twister download.
248 */
249
250 static int
random_seed_urandom(RandomObject * self)251 random_seed_urandom(RandomObject *self)
252 {
253 uint32_t key[N];
254
255 if (_PyOS_URandomNonblock(key, sizeof(key)) < 0) {
256 return -1;
257 }
258 init_by_array(self, key, Py_ARRAY_LENGTH(key));
259 return 0;
260 }
261
262 static int
random_seed_time_pid(RandomObject * self)263 random_seed_time_pid(RandomObject *self)
264 {
265 PyTime_t now;
266 if (PyTime_Time(&now) < 0) {
267 return -1;
268 }
269
270 uint32_t key[5];
271 key[0] = (uint32_t)(now & 0xffffffffU);
272 key[1] = (uint32_t)(now >> 32);
273
274 #if defined(MS_WINDOWS) && !defined(MS_WINDOWS_DESKTOP) && !defined(MS_WINDOWS_SYSTEM)
275 key[2] = (uint32_t)GetCurrentProcessId();
276 #elif defined(HAVE_GETPID)
277 key[2] = (uint32_t)getpid();
278 #else
279 key[2] = 0;
280 #endif
281
282 if (PyTime_Monotonic(&now) < 0) {
283 return -1;
284 }
285 key[3] = (uint32_t)(now & 0xffffffffU);
286 key[4] = (uint32_t)(now >> 32);
287
288 init_by_array(self, key, Py_ARRAY_LENGTH(key));
289 return 0;
290 }
291
292 static int
random_seed(RandomObject * self,PyObject * arg)293 random_seed(RandomObject *self, PyObject *arg)
294 {
295 int result = -1; /* guilty until proved innocent */
296 PyObject *n = NULL;
297 uint32_t *key = NULL;
298 size_t bits, keyused;
299 int res;
300
301 if (arg == NULL || arg == Py_None) {
302 if (random_seed_urandom(self) < 0) {
303 PyErr_Clear();
304
305 /* Reading system entropy failed, fall back on the worst entropy:
306 use the current time and process identifier. */
307 if (random_seed_time_pid(self) < 0) {
308 return -1;
309 }
310 }
311 return 0;
312 }
313
314 /* This algorithm relies on the number being unsigned.
315 * So: if the arg is a PyLong, use its absolute value.
316 * Otherwise use its hash value, cast to unsigned.
317 */
318 if (PyLong_CheckExact(arg)) {
319 n = PyNumber_Absolute(arg);
320 } else if (PyLong_Check(arg)) {
321 /* Calling int.__abs__() prevents calling arg.__abs__(), which might
322 return an invalid value. See issue #31478. */
323 _randomstate *state = _randomstate_type(Py_TYPE(self));
324 n = PyObject_CallOneArg(state->Long___abs__, arg);
325 }
326 else {
327 Py_hash_t hash = PyObject_Hash(arg);
328 if (hash == -1)
329 goto Done;
330 n = PyLong_FromSize_t((size_t)hash);
331 }
332 if (n == NULL)
333 goto Done;
334
335 /* Now split n into 32-bit chunks, from the right. */
336 bits = _PyLong_NumBits(n);
337 if (bits == (size_t)-1 && PyErr_Occurred())
338 goto Done;
339
340 /* Figure out how many 32-bit chunks this gives us. */
341 keyused = bits == 0 ? 1 : (bits - 1) / 32 + 1;
342
343 /* Convert seed to byte sequence. */
344 key = (uint32_t *)PyMem_Malloc((size_t)4 * keyused);
345 if (key == NULL) {
346 PyErr_NoMemory();
347 goto Done;
348 }
349 res = _PyLong_AsByteArray((PyLongObject *)n,
350 (unsigned char *)key, keyused * 4,
351 PY_LITTLE_ENDIAN,
352 0, /* unsigned */
353 1); /* with exceptions */
354 if (res == -1) {
355 goto Done;
356 }
357
358 #if PY_BIG_ENDIAN
359 {
360 size_t i, j;
361 /* Reverse an array. */
362 for (i = 0, j = keyused - 1; i < j; i++, j--) {
363 uint32_t tmp = key[i];
364 key[i] = key[j];
365 key[j] = tmp;
366 }
367 }
368 #endif
369 init_by_array(self, key, keyused);
370
371 result = 0;
372
373 Done:
374 Py_XDECREF(n);
375 PyMem_Free(key);
376 return result;
377 }
378
379 /*[clinic input]
380 @critical_section
381 _random.Random.seed
382
383 self: self(type="RandomObject *")
384 n: object = None
385 /
386
387 seed([n]) -> None.
388
389 Defaults to use urandom and falls back to a combination
390 of the current time and the process identifier.
391 [clinic start generated code]*/
392
393 static PyObject *
_random_Random_seed_impl(RandomObject * self,PyObject * n)394 _random_Random_seed_impl(RandomObject *self, PyObject *n)
395 /*[clinic end generated code: output=0fad1e16ba883681 input=46d01d2ba938c7b1]*/
396 {
397 if (random_seed(self, n) < 0) {
398 return NULL;
399 }
400 Py_RETURN_NONE;
401 }
402
403 /*[clinic input]
404 @critical_section
405 _random.Random.getstate
406
407 self: self(type="RandomObject *")
408
409 getstate() -> tuple containing the current state.
410 [clinic start generated code]*/
411
412 static PyObject *
_random_Random_getstate_impl(RandomObject * self)413 _random_Random_getstate_impl(RandomObject *self)
414 /*[clinic end generated code: output=bf6cef0c092c7180 input=b6621f31eb639694]*/
415 {
416 PyObject *state;
417 PyObject *element;
418 int i;
419
420 state = PyTuple_New(N+1);
421 if (state == NULL)
422 return NULL;
423 for (i=0; i<N ; i++) {
424 element = PyLong_FromUnsignedLong(self->state[i]);
425 if (element == NULL)
426 goto Fail;
427 PyTuple_SET_ITEM(state, i, element);
428 }
429 element = PyLong_FromLong((long)(self->index));
430 if (element == NULL)
431 goto Fail;
432 PyTuple_SET_ITEM(state, i, element);
433 return state;
434
435 Fail:
436 Py_DECREF(state);
437 return NULL;
438 }
439
440
441 /*[clinic input]
442 @critical_section
443 _random.Random.setstate
444
445 self: self(type="RandomObject *")
446 state: object
447 /
448
449 setstate(state) -> None. Restores generator state.
450 [clinic start generated code]*/
451
452 static PyObject *
_random_Random_setstate_impl(RandomObject * self,PyObject * state)453 _random_Random_setstate_impl(RandomObject *self, PyObject *state)
454 /*[clinic end generated code: output=babfc2c2eac6b027 input=358e898ec07469b7]*/
455 {
456 int i;
457 unsigned long element;
458 long index;
459 uint32_t new_state[N];
460
461 if (!PyTuple_Check(state)) {
462 PyErr_SetString(PyExc_TypeError,
463 "state vector must be a tuple");
464 return NULL;
465 }
466 if (PyTuple_Size(state) != N+1) {
467 PyErr_SetString(PyExc_ValueError,
468 "state vector is the wrong size");
469 return NULL;
470 }
471
472 for (i=0; i<N ; i++) {
473 element = PyLong_AsUnsignedLong(PyTuple_GET_ITEM(state, i));
474 if (element == (unsigned long)-1 && PyErr_Occurred())
475 return NULL;
476 new_state[i] = (uint32_t)element;
477 }
478
479 index = PyLong_AsLong(PyTuple_GET_ITEM(state, i));
480 if (index == -1 && PyErr_Occurred())
481 return NULL;
482 if (index < 0 || index > N) {
483 PyErr_SetString(PyExc_ValueError, "invalid state");
484 return NULL;
485 }
486 self->index = (int)index;
487 for (i = 0; i < N; i++)
488 self->state[i] = new_state[i];
489
490 Py_RETURN_NONE;
491 }
492
493 /*[clinic input]
494 @critical_section
495 _random.Random.getrandbits
496
497 self: self(type="RandomObject *")
498 k: int
499 /
500
501 getrandbits(k) -> x. Generates an int with k random bits.
502 [clinic start generated code]*/
503
504 static PyObject *
_random_Random_getrandbits_impl(RandomObject * self,int k)505 _random_Random_getrandbits_impl(RandomObject *self, int k)
506 /*[clinic end generated code: output=b402f82a2158887f input=87603cd60f79f730]*/
507 {
508 int i, words;
509 uint32_t r;
510 uint32_t *wordarray;
511 PyObject *result;
512
513 if (k < 0) {
514 PyErr_SetString(PyExc_ValueError,
515 "number of bits must be non-negative");
516 return NULL;
517 }
518
519 if (k == 0)
520 return PyLong_FromLong(0);
521
522 if (k <= 32) /* Fast path */
523 return PyLong_FromUnsignedLong(genrand_uint32(self) >> (32 - k));
524
525 words = (k - 1) / 32 + 1;
526 wordarray = (uint32_t *)PyMem_Malloc(words * 4);
527 if (wordarray == NULL) {
528 PyErr_NoMemory();
529 return NULL;
530 }
531
532 /* Fill-out bits of long integer, by 32-bit words, from least significant
533 to most significant. */
534 #if PY_LITTLE_ENDIAN
535 for (i = 0; i < words; i++, k -= 32)
536 #else
537 for (i = words - 1; i >= 0; i--, k -= 32)
538 #endif
539 {
540 r = genrand_uint32(self);
541 if (k < 32)
542 r >>= (32 - k); /* Drop least significant bits */
543 wordarray[i] = r;
544 }
545
546 result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,
547 PY_LITTLE_ENDIAN, 0 /* unsigned */);
548 PyMem_Free(wordarray);
549 return result;
550 }
551
552 static int
random_init(RandomObject * self,PyObject * args,PyObject * kwds)553 random_init(RandomObject *self, PyObject *args, PyObject *kwds)
554 {
555 PyObject *arg = NULL;
556 _randomstate *state = _randomstate_type(Py_TYPE(self));
557
558 if ((Py_IS_TYPE(self, (PyTypeObject *)state->Random_Type) ||
559 Py_TYPE(self)->tp_init == ((PyTypeObject*)state->Random_Type)->tp_init) &&
560 !_PyArg_NoKeywords("Random", kwds)) {
561 return -1;
562 }
563
564 if (PyTuple_GET_SIZE(args) > 1) {
565 PyErr_SetString(PyExc_TypeError, "Random() requires 0 or 1 argument");
566 return -1;
567 }
568
569 if (PyTuple_GET_SIZE(args) == 1)
570 arg = PyTuple_GET_ITEM(args, 0);
571
572 return random_seed(self, arg);
573 }
574
575
576 static PyMethodDef random_methods[] = {
577 _RANDOM_RANDOM_RANDOM_METHODDEF
578 _RANDOM_RANDOM_SEED_METHODDEF
579 _RANDOM_RANDOM_GETSTATE_METHODDEF
580 _RANDOM_RANDOM_SETSTATE_METHODDEF
581 _RANDOM_RANDOM_GETRANDBITS_METHODDEF
582 {NULL, NULL} /* sentinel */
583 };
584
585 PyDoc_STRVAR(random_doc,
586 "Random() -> create a random number generator with its own internal state.");
587
588 static PyType_Slot Random_Type_slots[] = {
589 {Py_tp_doc, (void *)random_doc},
590 {Py_tp_methods, random_methods},
591 {Py_tp_new, PyType_GenericNew},
592 {Py_tp_init, random_init},
593 {Py_tp_free, PyObject_Free},
594 {0, 0},
595 };
596
597 static PyType_Spec Random_Type_spec = {
598 "_random.Random",
599 sizeof(RandomObject),
600 0,
601 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
602 Random_Type_slots
603 };
604
605 PyDoc_STRVAR(module_doc,
606 "Module implements the Mersenne Twister random number generator.");
607
608 static int
_random_exec(PyObject * module)609 _random_exec(PyObject *module)
610 {
611 _randomstate *state = get_random_state(module);
612
613 state->Random_Type = PyType_FromModuleAndSpec(
614 module, &Random_Type_spec, NULL);
615 if (state->Random_Type == NULL) {
616 return -1;
617 }
618 if (PyModule_AddType(module, (PyTypeObject *)state->Random_Type) < 0) {
619 return -1;
620 }
621
622 /* Look up and save int.__abs__, which is needed in random_seed(). */
623 PyObject *longval = PyLong_FromLong(0);
624 if (longval == NULL) {
625 return -1;
626 }
627
628 PyObject *longtype = PyObject_Type(longval);
629 Py_DECREF(longval);
630 if (longtype == NULL) {
631 return -1;
632 }
633
634 state->Long___abs__ = PyObject_GetAttrString(longtype, "__abs__");
635 Py_DECREF(longtype);
636 if (state->Long___abs__ == NULL) {
637 return -1;
638 }
639 return 0;
640 }
641
642 static PyModuleDef_Slot _random_slots[] = {
643 {Py_mod_exec, _random_exec},
644 {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},
645 {Py_mod_gil, Py_MOD_GIL_NOT_USED},
646 {0, NULL}
647 };
648
649 static int
_random_traverse(PyObject * module,visitproc visit,void * arg)650 _random_traverse(PyObject *module, visitproc visit, void *arg)
651 {
652 Py_VISIT(get_random_state(module)->Random_Type);
653 return 0;
654 }
655
656 static int
_random_clear(PyObject * module)657 _random_clear(PyObject *module)
658 {
659 Py_CLEAR(get_random_state(module)->Random_Type);
660 Py_CLEAR(get_random_state(module)->Long___abs__);
661 return 0;
662 }
663
664 static void
_random_free(void * module)665 _random_free(void *module)
666 {
667 _random_clear((PyObject *)module);
668 }
669
670 static struct PyModuleDef _randommodule = {
671 PyModuleDef_HEAD_INIT,
672 "_random",
673 module_doc,
674 sizeof(_randomstate),
675 NULL,
676 _random_slots,
677 _random_traverse,
678 _random_clear,
679 _random_free,
680 };
681
682 PyMODINIT_FUNC
PyInit__random(void)683 PyInit__random(void)
684 {
685 return PyModuleDef_Init(&_randommodule);
686 }
687