rnd 0.1.1

Random
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

use core::num::Wrapping;

use crate::{RandomSource, Seedable};

const DEFAULT_SEED: u32 = 5489;
const STATE_LEN: usize = 624;
const STATE_LEN_M: usize = 397;
const UPPER_MASK: Wrapping<u32> = Wrapping(0x80000000);
const LOWER_MASK: Wrapping<u32> = Wrapping(0x7fffffff);
const TEMPERING_MASK_B: Wrapping<u32> = Wrapping(0x9d2c5680);
const TEMPERING_MASK_C: Wrapping<u32> = Wrapping(0xefc60000);

/// Mersenne Twister RNG
#[derive(Clone,Copy)]
pub struct MT19937 {
    index: u16, /* STATE_LEN is 5489, so a u16 is enough */
    state: [Wrapping<u32>; STATE_LEN],
}

impl Seedable<u32> for MT19937 {
    fn reseed(&mut self, seed: u32) {
        self.index = STATE_LEN as u16;
        self.state[0] = Wrapping(seed);
        for i in 1..STATE_LEN {
            self.state[i] = Wrapping(1812433253)
                            * (self.state[i-1] ^ (self.state[i-1] >> 30))
                            + Wrapping(i as u32);
        }
    }
}

impl Seedable<&[u32]> for MT19937 {
    fn reseed(&mut self, seed: &[u32]) {
        self.reseed(19650218);
        let seed_len = seed.len();

        let mut i = 1;
        let mut j = 0;
        let k = usize::max(STATE_LEN, seed_len);

        for _ in 0..k {
            self.state[i] = (self.state[i] ^ ((self.state[i-1] ^ (self.state[i-1] >> 30))
                            * Wrapping(1664525))) + Wrapping(seed[j]) + Wrapping(j as u32);
            i += 1;
            j += 1;
            if i >= STATE_LEN {
                self.state[0] = self.state[STATE_LEN - 1];
                i = 1;
            }
            if j >= seed_len {
                j = 0;
            }
        }

        for _ in 0..k {
            self.state[i] = (self.state[i] ^ ((self.state[i-1] ^ (self.state[i-1] >> 30))
                            * Wrapping(1566083941))) - Wrapping(i as u32);
            i += 1;
            if i >= STATE_LEN {
                self.state[0] = self.state[STATE_LEN - 1];
                i = 1;
            }
        }
        self.state[0] = UPPER_MASK;
    }
}

impl MT19937 {

    /// Builds a new [MT19937] with the default seed
    pub fn new() -> Self {
        Self::new_with_seed(DEFAULT_SEED)
    }

    /// Builds a new [MT19937] with the given seed
    pub fn new_with_seed<S>(seed: S) -> Self
    where
        Self: Seedable<S>,
    {
        let mut s = Self {
            index: 0,
            state: [Wrapping(0); STATE_LEN],
        };
        s.reseed(seed);
        s
    }

    fn switch_state(&mut self) {
        const N: usize = STATE_LEN;
        const M: usize = STATE_LEN_M;

        const MAG: [Wrapping<u32>; 2] = [Wrapping(0), Wrapping(0x9908b0df)];

        for i in 0..N-M {
            let tmp = (self.state[i] & UPPER_MASK) | (self.state[i+1] & LOWER_MASK);
            self.state[i] = self.state[i+M] ^ (tmp>>1) ^ MAG[tmp.0 as usize & 0x1];
        }
        for i in N-M..N-1 {
            let tmp = (self.state[i] & UPPER_MASK) | (self.state[i+1] & LOWER_MASK);
            self.state[i] = self.state[i + M - N] ^ (tmp>>1) ^ MAG[tmp.0 as usize & 0x1];
        }
        let tmp = (self.state[N-1] & UPPER_MASK) | (self.state[0] & LOWER_MASK);
        self.state[N-1] = self.state[M-1] ^ (tmp>>1) ^ MAG[tmp.0 as usize & 0x1];

        self.index = 0;
    }

    /// Gets the next `u32` from `self`
    pub fn next_u32(&mut self) -> u32 {
        debug_assert!(self.index != 0);

        if self.index as usize >= STATE_LEN {
            self.switch_state();
        }

        let mut n = self.state[self.index as usize];
        self.index += 1;

        n ^= n >> 11;
        n ^= (n << 7) & TEMPERING_MASK_B;
        n ^= (n << 15) & TEMPERING_MASK_C;
        n ^= n >> 18;
        n.0
    }
}

impl Default for MT19937 {
    fn default() -> Self {
        Self::new()
    }
}

impl RandomSource for MT19937 {
    fn fill_bytes(&mut self, bytes: &mut [u8]) {
        bytes.chunks_mut(4).for_each(|chunk| {
            let rand_bytes: [u8; 4] = self.next_u32().to_le_bytes();
            chunk.clone_from_slice(&rand_bytes[..chunk.len()]);
        });
    }
}