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