#ifndef Py_BUILD_CORE_BUILTIN

# define Py_BUILD_CORE_MODULE 1

#include "Python.h"

#include "pycore_long.h" // _PyLong_NumBits()

#include "pycore_modsupport.h" // _PyArg_NoKeywords()

#include "pycore_moduleobject.h" // _PyModule_GetState()

#include "pycore_pylifecycle.h" // _PyOS_URandomNonblock()

#ifdef HAVE_UNISTD_H

# include <unistd.h> // getpid()

#ifdef HAVE_PROCESS_H

# include <process.h> // getpid()

#ifdef MS_WINDOWS

# include <windows.h> // GetCurrentProcessId()

#define N 624

#define M 397

#define MATRIX_A 0x9908b0dfU /* constant vector a */

#define UPPER_MASK 0x80000000U /* most significant w-r bits */

#define LOWER_MASK 0x7fffffffU /* least significant r bits */

typedef struct {

PyObject *Random_Type;

PyObject *Long___abs__;

} _randomstate;

static inline _randomstate*

get_random_state(PyObject *module)

{

void *state = _PyModule_GetState(module);

assert(state != NULL);

return (_randomstate *)state;

}

static struct PyModuleDef _randommodule;

#define _randomstate_type(type) \

(get_random_state(PyType_GetModuleByDef(type, &_randommodule)))

typedef struct {

PyObject_HEAD

int index;

uint32_t state[N];

} RandomObject;

#define RandomObject_CAST(op) ((RandomObject *)(op))

#include "clinic/_randommodule.c.h"

static uint32_t

genrand_uint32(RandomObject *self)

{

uint32_t y;

static const uint32_t mag01[2] = {0x0U, MATRIX_A};

/* mag01[x] = x * MATRIX_A for x=0,1 */

uint32_t *mt;

mt = self->state;

if (self->index >= N) { /* generate N words at one time */

int kk;

for (kk=0;kk<N-M;kk++) {

y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);

mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];

}

for (;kk<N-1;kk++) {

y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);

mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];

}

y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);

mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];

self->index = 0;

}

y = mt[self->index++];

y ^= (y >> 11);

y ^= (y << 7) & 0x9d2c5680U;

y ^= (y << 15) & 0xefc60000U;

y ^= (y >> 18);

return y;

}

static PyObject *

_random_Random_random_impl(RandomObject *self)

{

uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;

return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));

}

static void

init_genrand(RandomObject *self, uint32_t s)

{

int mti;

uint32_t *mt;

mt = self->state;

mt[0]= s;

for (mti=1; mti<N; mti++) {

mt[mti] =

(1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);

/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */

/* In the previous versions, MSBs of the seed affect */

/* only MSBs of the array mt[]. */

/* 2002/01/09 modified by Makoto Matsumoto */

}

self->index = mti;

return;

}

static void

init_by_array(RandomObject *self, uint32_t init_key[], size_t key_length)

{

size_t i, j, k; /* was signed in the original code. RDH 12/16/2002 */

uint32_t *mt;

mt = self->state;

init_genrand(self, 19650218U);

i=1; j=0;

k = (N>key_length ? N : key_length);

for (; k; k--) {

mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U))

+ init_key[j] + (uint32_t)j; /* non linear */

i++; j++;

if (i>=N) { mt[0] = mt[N-1]; i=1; }

if (j>=key_length) j=0;

}

for (k=N-1; k; k--) {

mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U))

- (uint32_t)i; /* non linear */

i++;

if (i>=N) { mt[0] = mt[N-1]; i=1; }

}

mt[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */

}

static int

random_seed_urandom(RandomObject *self)

{

uint32_t key[N];

if (_PyOS_URandomNonblock(key, sizeof(key)) < 0) {

return -1;

}

init_by_array(self, key, Py_ARRAY_LENGTH(key));

return 0;

}

static int

random_seed_time_pid(RandomObject *self)

{

PyTime_t now;

if (PyTime_Time(&now) < 0) {

return -1;

}

uint32_t key[5];

key[0] = (uint32_t)(now & 0xffffffffU);

key[1] = (uint32_t)(now >> 32);

#if defined(MS_WINDOWS) && !defined(MS_WINDOWS_DESKTOP) && !defined(MS_WINDOWS_SYSTEM)

key[2] = (uint32_t)GetCurrentProcessId();

#elif defined(HAVE_GETPID)

key[2] = (uint32_t)getpid();

key[2] = 0;

if (PyTime_Monotonic(&now) < 0) {

return -1;

}

key[3] = (uint32_t)(now & 0xffffffffU);

key[4] = (uint32_t)(now >> 32);

init_by_array(self, key, Py_ARRAY_LENGTH(key));

return 0;

}

static int

random_seed(RandomObject *self, PyObject *arg)

{

int result = -1; /* guilty until proved innocent */

PyObject *n = NULL;

uint32_t *key = NULL;

int64_t bits;

size_t keyused;

int res;

if (arg == NULL || arg == Py_None) {

if (random_seed_urandom(self) < 0) {

PyErr_Clear();

/* Reading system entropy failed, fall back on the worst entropy:

if (random_seed_time_pid(self) < 0) {

return -1;

}

}

return 0;

}

/* This algorithm relies on the number being unsigned.

if (PyLong_CheckExact(arg)) {

n = PyNumber_Absolute(arg);

} else if (PyLong_Check(arg)) {

/* Calling int.__abs__() prevents calling arg.__abs__(), which might

_randomstate *state = _randomstate_type(Py_TYPE(self));

n = PyObject_CallOneArg(state->Long___abs__, arg);

}

else {

Py_hash_t hash = PyObject_Hash(arg);

if (hash == -1)

goto Done;

n = PyLong_FromSize_t((size_t)hash);

}

if (n == NULL)

goto Done;

/* Now split n into 32-bit chunks, from the right. */

bits = _PyLong_NumBits(n);

assert(bits >= 0);

assert(!PyErr_Occurred());

/* Figure out how many 32-bit chunks this gives us. */

keyused = bits == 0 ? 1 : (size_t)((bits - 1) / 32 + 1);

/* Convert seed to byte sequence. */

key = (uint32_t *)PyMem_Malloc((size_t)4 * keyused);

if (key == NULL) {

PyErr_NoMemory();

goto Done;

}

res = _PyLong_AsByteArray((PyLongObject *)n,

(unsigned char *)key, keyused * 4,

PY_LITTLE_ENDIAN,

0, /* unsigned */

1); /* with exceptions */

if (res == -1) {

goto Done;

}

#if PY_BIG_ENDIAN

{

size_t i, j;

/* Reverse an array. */

for (i = 0, j = keyused - 1; i < j; i++, j--) {

uint32_t tmp = key[i];

key[i] = key[j];

key[j] = tmp;

}

}

init_by_array(self, key, keyused);

result = 0;

Done:

Py_XDECREF(n);

PyMem_Free(key);

return result;

}

static PyObject *

_random_Random_seed_impl(RandomObject *self, PyObject *n)

{

if (random_seed(self, n) < 0) {

return NULL;

}

Py_RETURN_NONE;

}

static PyObject *

_random_Random_getstate_impl(RandomObject *self)

{

PyObject *state;

PyObject *element;

int i;

state = PyTuple_New(N+1);

if (state == NULL)

return NULL;

for (i=0; i<N ; i++) {

element = PyLong_FromUnsignedLong(self->state[i]);

if (element == NULL)

goto Fail;

PyTuple_SET_ITEM(state, i, element);

}

element = PyLong_FromLong((long)(self->index));

if (element == NULL)

goto Fail;

PyTuple_SET_ITEM(state, i, element);

return state;

Fail:

Py_DECREF(state);

return NULL;

}

static PyObject *

_random_Random_setstate_impl(RandomObject *self, PyObject *state)

{

int i;

unsigned long element;

long index;

uint32_t new_state[N];

if (!PyTuple_Check(state)) {

PyErr_SetString(PyExc_TypeError,

"state vector must be a tuple");

return NULL;

}

if (PyTuple_Size(state) != N+1) {

PyErr_SetString(PyExc_ValueError,

"state vector is the wrong size");

return NULL;

}

for (i=0; i<N ; i++) {

element = PyLong_AsUnsignedLong(PyTuple_GET_ITEM(state, i));

if (element == (unsigned long)-1 && PyErr_Occurred())

return NULL;

new_state[i] = (uint32_t)element;

}

index = PyLong_AsLong(PyTuple_GET_ITEM(state, i));

if (index == -1 && PyErr_Occurred())

return NULL;

if (index < 0 || index > N) {

PyErr_SetString(PyExc_ValueError, "invalid state");

return NULL;

}

self->index = (int)index;

for (i = 0; i < N; i++)

self->state[i] = new_state[i];

Py_RETURN_NONE;

}

static PyObject *

_random_Random_getrandbits_impl(RandomObject *self, uint64_t k)

{

Py_ssize_t i, words;

uint32_t r;

uint32_t *wordarray;

PyObject *result;

if (k == 0)

return PyLong_FromLong(0);

if (k <= 32) /* Fast path */

return PyLong_FromUnsignedLong(genrand_uint32(self) >> (32 - k));

if ((k - 1u) / 32u + 1u > PY_SSIZE_T_MAX / 4u) {

PyErr_NoMemory();

return NULL;

}

words = (Py_ssize_t)((k - 1u) / 32u + 1u);

wordarray = (uint32_t *)PyMem_Malloc(words * 4);

if (wordarray == NULL) {

PyErr_NoMemory();

return NULL;

}

/* Fill-out bits of long integer, by 32-bit words, from least significant

#if PY_LITTLE_ENDIAN

for (i = 0; i < words; i++, k -= 32)

for (i = words - 1; i >= 0; i--, k -= 32)

{

r = genrand_uint32(self);

if (k < 32)

r >>= (32 - k); /* Drop least significant bits */

wordarray[i] = r;

}

result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,

PY_LITTLE_ENDIAN, 0 /* unsigned */);

PyMem_Free(wordarray);

return result;

}

static int

random_init_impl(RandomObject *self, PyObject *seed)

{

return random_seed(self, seed);

}

static PyMethodDef random_methods[] = {

_RANDOM_RANDOM_RANDOM_METHODDEF

_RANDOM_RANDOM_SEED_METHODDEF

_RANDOM_RANDOM_GETSTATE_METHODDEF

_RANDOM_RANDOM_SETSTATE_METHODDEF

_RANDOM_RANDOM_GETRANDBITS_METHODDEF

{NULL, NULL} /* sentinel */

};

PyDoc_STRVAR(random_doc,

"Random() -> create a random number generator with its own internal state.");

static PyType_Slot Random_Type_slots[] = {

{Py_tp_doc, (void *)random_doc},

{Py_tp_methods, random_methods},

{Py_tp_new, PyType_GenericNew},

{Py_tp_init, random_init},

{Py_tp_free, PyObject_Free},

{0, 0},

};

static PyType_Spec Random_Type_spec = {

.name = "_random.Random",

.basicsize = sizeof(RandomObject),

.flags = (

Py_TPFLAGS_DEFAULT

| Py_TPFLAGS_BASETYPE

| Py_TPFLAGS_IMMUTABLETYPE

),

.slots = Random_Type_slots

};

PyDoc_STRVAR(module_doc,

"Module implements the Mersenne Twister random number generator.");

static int

_random_exec(PyObject *module)

{

_randomstate *state = get_random_state(module);

state->Random_Type = PyType_FromModuleAndSpec(

module, &Random_Type_spec, NULL);

if (state->Random_Type == NULL) {

return -1;

}

if (PyModule_AddType(module, (PyTypeObject *)state->Random_Type) < 0) {

return -1;

}

/* Look up and save int.__abs__, which is needed in random_seed(). */

PyObject *longval = PyLong_FromLong(0);

if (longval == NULL) {

return -1;

}

PyObject *longtype = PyObject_Type(longval);

Py_DECREF(longval);

if (longtype == NULL) {

return -1;

}

state->Long___abs__ = PyObject_GetAttrString(longtype, "__abs__");

Py_DECREF(longtype);

if (state->Long___abs__ == NULL) {

return -1;

}

return 0;

}

static PyModuleDef_Slot _random_slots[] = {

_Py_ABI_SLOT,

{Py_mod_exec, _random_exec},

{Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},

{Py_mod_gil, Py_MOD_GIL_NOT_USED},

{0, NULL}

};

static int

_random_traverse(PyObject *module, visitproc visit, void *arg)

{

Py_VISIT(get_random_state(module)->Random_Type);

return 0;

}

static int

_random_clear(PyObject *module)

{

Py_CLEAR(get_random_state(module)->Random_Type);

Py_CLEAR(get_random_state(module)->Long___abs__);

return 0;

}

static void

_random_free(void *module)

{

(void)_random_clear((PyObject *)module);

}

static struct PyModuleDef _randommodule = {

PyModuleDef_HEAD_INIT,

"_random",

module_doc,

sizeof(_randomstate),

NULL,

_random_slots,

_random_traverse,

_random_clear,

_random_free,

};

PyInit__random(void)

{

return PyModuleDef_Init(&_randommodule);

}