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_moduleobject.h" // _PyModule_GetState()
75 #include "pycore_runtime.h"
76 #ifdef HAVE_PROCESS_H
77 # include <process.h> // getpid()
78 #endif
79
80 #ifdef MS_WINDOWS
81 # include <windows.h>
82 #endif
83
84 /* Period parameters -- These are all magic. Don't change. */
85 #define N 624
86 #define M 397
87 #define MATRIX_A 0x9908b0dfU /* constant vector a */
88 #define UPPER_MASK 0x80000000U /* most significant w-r bits */
89 #define LOWER_MASK 0x7fffffffU /* least significant r bits */
90
91 typedef struct {
92 PyObject *Random_Type;
93 PyObject *Long___abs__;
94 } _randomstate;
95
96 static inline _randomstate*
97 get_random_state(PyObject *module)
98 {
99 void *state = _PyModule_GetState(module);
100 assert(state != NULL);
101 return (_randomstate *)state;
102 }
103
104 static struct PyModuleDef _randommodule;
105
106 #define _randomstate_type(type) \
107 (get_random_state(PyType_GetModuleByDef(type, &_randommodule)))
108
109 typedef struct {
110 PyObject_HEAD
111 int index;
112 uint32_t state[N];
113 } RandomObject;
114
115
116 #include "clinic/_randommodule.c.h"
117
118 /*[clinic input]
119 module _random
120 class _random.Random "RandomObject *" "_randomstate_type(type)->Random_Type"
121 [clinic start generated code]*/
122 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=70a2c99619474983]*/
123
124 /* Random methods */
125
126
127 /* generates a random number on [0,0xffffffff]-interval */
128 static uint32_t
129 genrand_uint32(RandomObject *self)
130 {
131 uint32_t y;
132 static const uint32_t mag01[2] = {0x0U, MATRIX_A};
133 /* mag01[x] = x * MATRIX_A for x=0,1 */
134 uint32_t *mt;
135
136 mt = self->state;
137 if (self->index >= N) { /* generate N words at one time */
138 int kk;
139
140 for (kk=0;kk<N-M;kk++) {
141 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
142 mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
143 }
144 for (;kk<N-1;kk++) {
145 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
146 mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
147 }
148 y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
149 mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
150
151 self->index = 0;
152 }
153
154 y = mt[self->index++];
155 y ^= (y >> 11);
156 y ^= (y << 7) & 0x9d2c5680U;
157 y ^= (y << 15) & 0xefc60000U;
158 y ^= (y >> 18);
159 return y;
160 }
161
162 /* random_random is the function named genrand_res53 in the original code;
163 * generates a random number on [0,1) with 53-bit resolution; note that
164 * 9007199254740992 == 2**53; I assume they're spelling "/2**53" as
165 * multiply-by-reciprocal in the (likely vain) hope that the compiler will
166 * optimize the division away at compile-time. 67108864 is 2**26. In
167 * effect, a contains 27 random bits shifted left 26, and b fills in the
168 * lower 26 bits of the 53-bit numerator.
169 * The original code credited Isaku Wada for this algorithm, 2002/01/09.
170 */
171
172 /*[clinic input]
173 _random.Random.random
174
175 self: self(type="RandomObject *")
176
177 random() -> x in the interval [0, 1).
178 [clinic start generated code]*/
179
180 static PyObject *
181 _random_Random_random_impl(RandomObject *self)
182 /*[clinic end generated code: output=117ff99ee53d755c input=afb2a59cbbb00349]*/
183 {
184 uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;
185 return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
186 }
187
188 /* initializes mt[N] with a seed */
189 static void
190 init_genrand(RandomObject *self, uint32_t s)
191 {
192 int mti;
193 uint32_t *mt;
194
195 mt = self->state;
196 mt[0]= s;
197 for (mti=1; mti<N; mti++) {
198 mt[mti] =
199 (1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
200 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
201 /* In the previous versions, MSBs of the seed affect */
202 /* only MSBs of the array mt[]. */
203 /* 2002/01/09 modified by Makoto Matsumoto */
204 }
205 self->index = mti;
206 return;
207 }
208
209 /* initialize by an array with array-length */
210 /* init_key is the array for initializing keys */
211 /* key_length is its length */
212 static void
213 init_by_array(RandomObject *self, uint32_t init_key[], size_t key_length)
214 {
215 size_t i, j, k; /* was signed in the original code. RDH 12/16/2002 */
216 uint32_t *mt;
217
218 mt = self->state;
219 init_genrand(self, 19650218U);
220 i=1; j=0;
221 k = (N>key_length ? N : key_length);
222 for (; k; k--) {
223 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U))
224 + init_key[j] + (uint32_t)j; /* non linear */
225 i++; j++;
226 if (i>=N) { mt[0] = mt[N-1]; i=1; }
227 if (j>=key_length) j=0;
228 }
229 for (k=N-1; k; k--) {
230 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U))
231 - (uint32_t)i; /* non linear */
232 i++;
233 if (i>=N) { mt[0] = mt[N-1]; i=1; }
234 }
235
236 mt[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */
237 }
238
239 /*
240 * The rest is Python-specific code, neither part of, nor derived from, the
241 * Twister download.
242 */
243
244 static int
245 random_seed_urandom(RandomObject *self)
246 {
247 uint32_t key[N];
248
249 if (_PyOS_URandomNonblock(key, sizeof(key)) < 0) {
250 return -1;
251 }
252 init_by_array(self, key, Py_ARRAY_LENGTH(key));
253 return 0;
254 }
255
256 static void
257 random_seed_time_pid(RandomObject *self)
258 {
259 _PyTime_t now;
260 uint32_t key[5];
261
262 now = _PyTime_GetSystemClock();
263 key[0] = (uint32_t)(now & 0xffffffffU);
264 key[1] = (uint32_t)(now >> 32);
265
266 #if defined(MS_WINDOWS) && !defined(MS_WINDOWS_DESKTOP) && !defined(MS_WINDOWS_SYSTEM)
267 key[2] = (uint32_t)GetCurrentProcessId();
268 #elif defined(HAVE_GETPID)
269 key[2] = (uint32_t)getpid();
270 #else
271 key[2] = 0;
272 #endif
273
274 now = _PyTime_GetMonotonicClock();
275 key[3] = (uint32_t)(now & 0xffffffffU);
276 key[4] = (uint32_t)(now >> 32);
277
278 init_by_array(self, key, Py_ARRAY_LENGTH(key));
279 }
280
281 static int
282 random_seed(RandomObject *self, PyObject *arg)
283 {
284 int result = -1; /* guilty until proved innocent */
285 PyObject *n = NULL;
286 uint32_t *key = NULL;
287 size_t bits, keyused;
288 int res;
289
290 if (arg == NULL || arg == Py_None) {
291 if (random_seed_urandom(self) < 0) {
292 PyErr_Clear();
293
294 /* Reading system entropy failed, fall back on the worst entropy:
295 use the current time and process identifier. */
296 random_seed_time_pid(self);
297 }
298 return 0;
299 }
300
301 /* This algorithm relies on the number being unsigned.
302 * So: if the arg is a PyLong, use its absolute value.
303 * Otherwise use its hash value, cast to unsigned.
304 */
305 if (PyLong_CheckExact(arg)) {
306 n = PyNumber_Absolute(arg);
307 } else if (PyLong_Check(arg)) {
308 /* Calling int.__abs__() prevents calling arg.__abs__(), which might
309 return an invalid value. See issue #31478. */
310 _randomstate *state = _randomstate_type(Py_TYPE(self));
311 n = PyObject_CallOneArg(state->Long___abs__, arg);
312 }
313 else {
314 Py_hash_t hash = PyObject_Hash(arg);
315 if (hash == -1)
316 goto Done;
317 n = PyLong_FromSize_t((size_t)hash);
318 }
319 if (n == NULL)
320 goto Done;
321
322 /* Now split n into 32-bit chunks, from the right. */
323 bits = _PyLong_NumBits(n);
324 if (bits == (size_t)-1 && PyErr_Occurred())
325 goto Done;
326
327 /* Figure out how many 32-bit chunks this gives us. */
328 keyused = bits == 0 ? 1 : (bits - 1) / 32 + 1;
329
330 /* Convert seed to byte sequence. */
331 key = (uint32_t *)PyMem_Malloc((size_t)4 * keyused);
332 if (key == NULL) {
333 PyErr_NoMemory();
334 goto Done;
335 }
336 res = _PyLong_AsByteArray((PyLongObject *)n,
337 (unsigned char *)key, keyused * 4,
338 PY_LITTLE_ENDIAN,
339 0); /* unsigned */
340 if (res == -1) {
341 goto Done;
342 }
343
344 #if PY_BIG_ENDIAN
345 {
346 size_t i, j;
347 /* Reverse an array. */
348 for (i = 0, j = keyused - 1; i < j; i++, j--) {
349 uint32_t tmp = key[i];
350 key[i] = key[j];
351 key[j] = tmp;
352 }
353 }
354 #endif
355 init_by_array(self, key, keyused);
356
357 result = 0;
358
359 Done:
360 Py_XDECREF(n);
361 PyMem_Free(key);
362 return result;
363 }
364
365 /*[clinic input]
366 _random.Random.seed
367
368 self: self(type="RandomObject *")
369 n: object = None
370 /
371
372 seed([n]) -> None.
373
374 Defaults to use urandom and falls back to a combination
375 of the current time and the process identifier.
376 [clinic start generated code]*/
377
378 static PyObject *
379 _random_Random_seed_impl(RandomObject *self, PyObject *n)
380 /*[clinic end generated code: output=0fad1e16ba883681 input=78d6ef0d52532a54]*/
381 {
382 if (random_seed(self, n) < 0) {
383 return NULL;
384 }
385 Py_RETURN_NONE;
386 }
387
388 /*[clinic input]
389 _random.Random.getstate
390
391 self: self(type="RandomObject *")
392
393 getstate() -> tuple containing the current state.
394 [clinic start generated code]*/
395
396 static PyObject *
397 _random_Random_getstate_impl(RandomObject *self)
398 /*[clinic end generated code: output=bf6cef0c092c7180 input=b937a487928c0e89]*/
399 {
400 PyObject *state;
401 PyObject *element;
402 int i;
403
404 state = PyTuple_New(N+1);
405 if (state == NULL)
406 return NULL;
407 for (i=0; i<N ; i++) {
408 element = PyLong_FromUnsignedLong(self->state[i]);
409 if (element == NULL)
410 goto Fail;
411 PyTuple_SET_ITEM(state, i, element);
412 }
413 element = PyLong_FromLong((long)(self->index));
414 if (element == NULL)
415 goto Fail;
416 PyTuple_SET_ITEM(state, i, element);
417 return state;
418
419 Fail:
420 Py_DECREF(state);
421 return NULL;
422 }
423
424
425 /*[clinic input]
426 _random.Random.setstate
427
428 self: self(type="RandomObject *")
429 state: object
430 /
431
432 setstate(state) -> None. Restores generator state.
433 [clinic start generated code]*/
434
435 static PyObject *
436 _random_Random_setstate(RandomObject *self, PyObject *state)
437 /*[clinic end generated code: output=fd1c3cd0037b6681 input=b3b4efbb1bc66af8]*/
438 {
439 int i;
440 unsigned long element;
441 long index;
442 uint32_t new_state[N];
443
444 if (!PyTuple_Check(state)) {
445 PyErr_SetString(PyExc_TypeError,
446 "state vector must be a tuple");
447 return NULL;
448 }
449 if (PyTuple_Size(state) != N+1) {
450 PyErr_SetString(PyExc_ValueError,
451 "state vector is the wrong size");
452 return NULL;
453 }
454
455 for (i=0; i<N ; i++) {
456 element = PyLong_AsUnsignedLong(PyTuple_GET_ITEM(state, i));
457 if (element == (unsigned long)-1 && PyErr_Occurred())
458 return NULL;
459 new_state[i] = (uint32_t)element;
460 }
461
462 index = PyLong_AsLong(PyTuple_GET_ITEM(state, i));
463 if (index == -1 && PyErr_Occurred())
464 return NULL;
465 if (index < 0 || index > N) {
466 PyErr_SetString(PyExc_ValueError, "invalid state");
467 return NULL;
468 }
469 self->index = (int)index;
470 for (i = 0; i < N; i++)
471 self->state[i] = new_state[i];
472
473 Py_RETURN_NONE;
474 }
475
476 /*[clinic input]
477
478 _random.Random.getrandbits
479
480 self: self(type="RandomObject *")
481 k: int
482 /
483
484 getrandbits(k) -> x. Generates an int with k random bits.
485 [clinic start generated code]*/
486
487 static PyObject *
488 _random_Random_getrandbits_impl(RandomObject *self, int k)
489 /*[clinic end generated code: output=b402f82a2158887f input=8c0e6396dd176fc0]*/
490 {
491 int i, words;
492 uint32_t r;
493 uint32_t *wordarray;
494 PyObject *result;
495
496 if (k < 0) {
497 PyErr_SetString(PyExc_ValueError,
498 "number of bits must be non-negative");
499 return NULL;
500 }
501
502 if (k == 0)
503 return PyLong_FromLong(0);
504
505 if (k <= 32) /* Fast path */
506 return PyLong_FromUnsignedLong(genrand_uint32(self) >> (32 - k));
507
508 words = (k - 1) / 32 + 1;
509 wordarray = (uint32_t *)PyMem_Malloc(words * 4);
510 if (wordarray == NULL) {
511 PyErr_NoMemory();
512 return NULL;
513 }
514
515 /* Fill-out bits of long integer, by 32-bit words, from least significant
516 to most significant. */
517 #if PY_LITTLE_ENDIAN
518 for (i = 0; i < words; i++, k -= 32)
519 #else
520 for (i = words - 1; i >= 0; i--, k -= 32)
521 #endif
522 {
523 r = genrand_uint32(self);
524 if (k < 32)
525 r >>= (32 - k); /* Drop least significant bits */
526 wordarray[i] = r;
527 }
528
529 result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,
530 PY_LITTLE_ENDIAN, 0 /* unsigned */);
531 PyMem_Free(wordarray);
532 return result;
533 }
534
535 static int
536 random_init(RandomObject *self, PyObject *args, PyObject *kwds)
537 {
538 PyObject *arg = NULL;
539 _randomstate *state = _randomstate_type(Py_TYPE(self));
540
541 if ((Py_IS_TYPE(self, (PyTypeObject *)state->Random_Type) ||
542 Py_TYPE(self)->tp_init == ((PyTypeObject*)state->Random_Type)->tp_init) &&
543 !_PyArg_NoKeywords("Random", kwds)) {
544 return -1;
545 }
546
547 if (PyTuple_GET_SIZE(args) > 1) {
548 PyErr_SetString(PyExc_TypeError, "Random() requires 0 or 1 argument");
549 return -1;
550 }
551
552 if (PyTuple_GET_SIZE(args) == 1)
553 arg = PyTuple_GET_ITEM(args, 0);
554
555 return random_seed(self, arg);
556 }
557
558
559 static PyMethodDef random_methods[] = {
560 _RANDOM_RANDOM_RANDOM_METHODDEF
561 _RANDOM_RANDOM_SEED_METHODDEF
562 _RANDOM_RANDOM_GETSTATE_METHODDEF
563 _RANDOM_RANDOM_SETSTATE_METHODDEF
564 _RANDOM_RANDOM_GETRANDBITS_METHODDEF
565 {NULL, NULL} /* sentinel */
566 };
567
568 PyDoc_STRVAR(random_doc,
569 "Random() -> create a random number generator with its own internal state.");
570
571 static PyType_Slot Random_Type_slots[] = {
572 {Py_tp_doc, (void *)random_doc},
573 {Py_tp_methods, random_methods},
574 {Py_tp_new, PyType_GenericNew},
575 {Py_tp_init, random_init},
576 {Py_tp_free, PyObject_Free},
577 {0, 0},
578 };
579
580 static PyType_Spec Random_Type_spec = {
581 "_random.Random",
582 sizeof(RandomObject),
583 0,
584 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
585 Random_Type_slots
586 };
587
588 PyDoc_STRVAR(module_doc,
589 "Module implements the Mersenne Twister random number generator.");
590
591 static int
592 _random_exec(PyObject *module)
593 {
594 _randomstate *state = get_random_state(module);
595
596 state->Random_Type = PyType_FromModuleAndSpec(
597 module, &Random_Type_spec, NULL);
598 if (state->Random_Type == NULL) {
599 return -1;
600 }
601 if (PyModule_AddType(module, (PyTypeObject *)state->Random_Type) < 0) {
602 return -1;
603 }
604
605 /* Look up and save int.__abs__, which is needed in random_seed(). */
606 PyObject *longval = PyLong_FromLong(0);
607 if (longval == NULL) {
608 return -1;
609 }
610
611 PyObject *longtype = PyObject_Type(longval);
612 Py_DECREF(longval);
613 if (longtype == NULL) {
614 return -1;
615 }
616
617 state->Long___abs__ = PyObject_GetAttrString(longtype, "__abs__");
618 Py_DECREF(longtype);
619 if (state->Long___abs__ == NULL) {
620 return -1;
621 }
622 return 0;
623 }
624
625 static PyModuleDef_Slot _random_slots[] = {
626 {Py_mod_exec, _random_exec},
627 {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},
628 {0, NULL}
629 };
630
631 static int
632 _random_traverse(PyObject *module, visitproc visit, void *arg)
633 {
634 Py_VISIT(get_random_state(module)->Random_Type);
635 return 0;
636 }
637
638 static int
639 _random_clear(PyObject *module)
640 {
641 Py_CLEAR(get_random_state(module)->Random_Type);
642 Py_CLEAR(get_random_state(module)->Long___abs__);
643 return 0;
644 }
645
646 static void
647 _random_free(void *module)
648 {
649 _random_clear((PyObject *)module);
650 }
651
652 static struct PyModuleDef _randommodule = {
653 PyModuleDef_HEAD_INIT,
654 "_random",
655 module_doc,
656 sizeof(_randomstate),
657 NULL,
658 _random_slots,
659 _random_traverse,
660 _random_clear,
661 _random_free,
662 };
663
664 PyMODINIT_FUNC
665 PyInit__random(void)
666 {
667 return PyModuleDef_Init(&_randommodule);
668 }