use num_bigint::{BigInt, Sign};
use std::cell::RefCell;
use std::collections::HashMap;
const N: usize = 624;
const M: usize = 397;
const MATRIX_A: u32 = 0x9908_b0df;
const UMASK: u32 = 0x8000_0000;
const LMASK: u32 = 0x7fff_ffff;
fn twist(u: u32, v: u32) -> u32 {
(((u & UMASK) | (v & LMASK)) >> 1) ^ if v & 1 != 0 { MATRIX_A } else { 0 }
}
#[derive(Clone)]
pub struct Mt {
state: [u32; N],
next: usize,
left: i32,
}
impl Mt {
fn init_genrand(s: u32) -> Mt {
let mut state = [0u32; N];
state[0] = s;
for j in 1..N {
state[j] = 1_812_433_253u32
.wrapping_mul(state[j - 1] ^ (state[j - 1] >> 30))
.wrapping_add(j as u32);
}
Mt {
state,
next: N,
left: 1,
}
}
fn init_by_array(key: &[u32]) -> Mt {
let mut mt = Mt::init_genrand(19_650_218);
let st = &mut mt.state;
let (mut i, mut j) = (1usize, 0usize);
let mut k = N.max(key.len());
while k > 0 {
st[i] = (st[i] ^ (st[i - 1] ^ (st[i - 1] >> 30)).wrapping_mul(1_664_525))
.wrapping_add(key[j])
.wrapping_add(j as u32);
i += 1;
j += 1;
if i >= N {
st[0] = st[N - 1];
i = 1;
}
if j >= key.len() {
j = 0;
}
k -= 1;
}
k = N - 1;
while k > 0 {
st[i] = (st[i] ^ (st[i - 1] ^ (st[i - 1] >> 30)).wrapping_mul(1_566_083_941))
.wrapping_sub(i as u32);
i += 1;
if i >= N {
st[0] = st[N - 1];
i = 1;
}
k -= 1;
}
st[0] = 0x8000_0000;
mt
}
fn next_state(&mut self) {
let s = &mut self.state;
self.left = N as i32;
self.next = 0;
for p in 0..N - M {
s[p] = s[p + M] ^ twist(s[p], s[p + 1]);
}
for p in N - M..N - 1 {
s[p] = s[p + M - N] ^ twist(s[p], s[p + 1]);
}
s[N - 1] = s[M - 1] ^ twist(s[N - 1], s[0]);
}
fn genrand_int32(&mut self) -> u32 {
self.left -= 1;
if self.left <= 0 {
self.next_state();
}
let mut y = self.state[self.next];
self.next += 1;
y ^= y >> 11;
y ^= (y << 7) & 0x9d2c_5680;
y ^= (y << 15) & 0xefc6_0000;
y ^= y >> 18;
y
}
pub fn from_seed(seed: &BigInt) -> Mt {
let (_, mut words) = seed.to_u32_digits();
if words.is_empty() {
words.push(0);
}
if words.len() == 1 {
return Mt::init_genrand(words[0]);
}
if words.last() == Some(&1) {
words.pop();
}
Mt::init_by_array(&words)
}
}
#[derive(Clone, Copy)]
pub enum Gen {
Default,
Instance(u32),
}
thread_local! {
static DEFAULT: RefCell<Option<(Mt, BigInt)>> = const { RefCell::new(None) };
static INSTANCES: RefCell<HashMap<u32, Mt>> = RefCell::new(HashMap::new());
}
pub fn new_seed() -> BigInt {
use std::hash::{BuildHasher, Hasher};
let mut words = [0u32; 4];
for (i, w) in words.iter_mut().enumerate() {
let mut h = std::collections::hash_map::RandomState::new().build_hasher();
h.write_u128(
std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.map(|d| d.as_nanos())
.unwrap_or(0),
);
h.write_usize(i);
*w = h.finish() as u32;
}
BigInt::from_slice(Sign::Plus, &words)
}
fn with_mt<R>(g: Gen, f: impl FnOnce(&mut Mt) -> R) -> R {
match g {
Gen::Default => DEFAULT.with(|d| {
let mut d = d.borrow_mut();
let (mt, _) = d.get_or_insert_with(|| {
let seed = new_seed();
(Mt::from_seed(&seed), seed)
});
f(mt)
}),
Gen::Instance(id) => INSTANCES.with(|m| {
let mut m = m.borrow_mut();
let mt = m.entry(id).or_insert_with(|| Mt::from_seed(&new_seed()));
f(mt)
}),
}
}
pub fn srand(seed: BigInt) -> BigInt {
let mt = Mt::from_seed(&seed);
DEFAULT.with(|d| {
let old = d.borrow_mut().replace((mt, seed));
match old {
Some((_, s)) => s,
None => new_seed(),
}
})
}
pub fn seed_instance(id: u32, seed: &BigInt) {
let mt = Mt::from_seed(seed);
INSTANCES.with(|m| m.borrow_mut().insert(id, mt));
}
pub fn int32(g: Gen) -> u32 {
with_mt(g, |mt| mt.genrand_int32())
}
fn make_mask(mut x: u64) -> u64 {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
x
}
pub fn limited(g: Gen, limit: u64) -> u64 {
if limit == 0 {
return 0;
}
let mask = make_mask(limit);
with_mt(g, |mt| {
if limit > 0xffff_ffff {
'retry: loop {
let mut val = 0u64;
for i in (0..=1).rev() {
if (mask >> (i * 32)) & 0xffff_ffff != 0 {
val |= (mt.genrand_int32() as u64) << (i * 32);
val &= mask;
if limit < val {
continue 'retry;
}
}
}
return val;
}
}
loop {
let val = mt.genrand_int32() as u64 & mask;
if val <= limit {
return val;
}
}
})
}
pub fn limited_big(g: Gen, limit: &BigInt) -> BigInt {
let (_, lim) = limit.to_u32_digits();
let len = lim.len();
let mut out = vec![0u32; len];
with_mt(g, |mt| 'retry: loop {
let mut mask = 0u32;
let mut boundary = true;
for i in (0..len).rev() {
let l = lim[i];
mask = if mask != 0 {
0xffff_ffff
} else {
make_mask(l as u64) as u32
};
let mut r = 0u32;
if mask != 0 {
r = mt.genrand_int32() & mask;
if boundary {
if l < r {
continue 'retry;
}
if r < l {
boundary = false;
}
}
}
out[i] = r;
}
return;
});
BigInt::from_slice(Sign::Plus, &out)
}
pub fn real(g: Gen, excl: bool) -> f64 {
let (a, b) = with_mt(g, |mt| (mt.genrand_int32(), mt.genrand_int32()));
if excl {
let (a, b) = (a >> 5, b >> 6);
(a as f64 * (1u64 << 26) as f64 + b as f64) * (1.0 / (1u64 << 53) as f64)
} else {
let m: u128 = (1u128 << 53) | 1;
let x: u128 = ((a as u128) << 32) | b as u128;
let r = ((x.wrapping_mul(m)) >> 64) as u64 as f64;
r * (1.0 / (1u64 << 53) as f64)
}
}