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