From 42103921cf938b44072e60e8f7a7d092cafa7ae3 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Sun, 5 Apr 2015 03:03:24 -0400
Subject: problem 21

---
 src/lib.rs    |  3 +++
 src/random.rs | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 tests/lib.rs  | 13 +++++++++++-
 3 files changed, 82 insertions(+), 1 deletion(-)
 create mode 100644 src/random.rs

diff --git a/src/lib.rs b/src/lib.rs
index 6d04106..1704c8b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,5 +1,6 @@
 extern crate rustc_serialize as serialize;
 extern crate openssl;
+extern crate rand;
 
 mod aes;
 mod base64;
@@ -7,6 +8,7 @@ mod crack;
 mod data;
 mod http;
 mod primitives;
+mod random;
 
 pub use aes::decrypt_aes_128_ecb;
 pub use aes::decrypt_aes_128_cbc;
@@ -20,6 +22,7 @@ pub use primitives::fixed_xor;
 pub use primitives::pad_pkcs7;
 pub use primitives::unpad_pkcs7;
 pub use primitives::repeating_key_xor;
+pub use random::MersenneTwister;
 pub use crack::BlockCipherMode;
 pub use crack::find_aes_128_ecb_encrypted_string;
 pub use crack::detect_ecb_cbc;
diff --git a/src/random.rs b/src/random.rs
new file mode 100644
index 0000000..fcc1967
--- /dev/null
+++ b/src/random.rs
@@ -0,0 +1,67 @@
+use rand::{Rand, Rng, SeedableRng};
+
+pub struct MersenneTwister {
+    state: [u32; 624],
+    index: usize,
+}
+
+impl MersenneTwister {
+    fn new_unseeded () -> MersenneTwister {
+        MersenneTwister { state: [0; 624], index: 0 }
+    }
+}
+
+impl Rng for MersenneTwister {
+    fn next_u32 (&mut self) -> u32 {
+        if self.index == 0 {
+            for i in 0..624 {
+                let y = (self.state[i] & 0x80000000)
+                    .wrapping_add(self.state[(i + 1) % 624] & 0x7fffffff);
+                self.state[i] = self.state[(i + 397) % 624] ^ (y >> 1);
+                if (y % 2) != 0 {
+                    self.state[i] = self.state[i] ^ 0x9908b0df;
+                }
+            }
+        }
+
+        let mut y = self.state[self.index];
+        y = y ^ (y >> 11);
+        y = y ^ ((y << 7) & 0x9d2c5680);
+        y = y ^ ((y << 15) & 0xefc60000);
+        y = y ^ (y >> 18);
+
+        self.index = (self.index + 1) % 624;
+
+        return y;
+    }
+}
+
+impl SeedableRng<u32> for MersenneTwister {
+    fn reseed (&mut self, seed: u32) {
+        self.state[0] = seed;
+        for i in 1..624 {
+            let prev = self.state[i - 1];
+            self.state[i] = 1812433253u32
+                .wrapping_mul(prev ^ (prev >> 30))
+                .wrapping_add(i as u32);
+        }
+    }
+
+    fn from_seed (seed: u32) -> MersenneTwister {
+        let mut mt = MersenneTwister::new_unseeded();
+        mt.reseed(seed);
+        mt
+    }
+}
+
+impl Rand for MersenneTwister {
+    fn rand<R: Rng> (other: &mut R) -> MersenneTwister {
+        MersenneTwister::from_seed(other.next_u32())
+    }
+}
+
+impl Clone for MersenneTwister {
+    fn clone (&self) -> MersenneTwister {
+        MersenneTwister { state: self.state, index: self.index }
+    }
+}
diff --git a/tests/lib.rs b/tests/lib.rs
index ec214f4..a304873 100644
--- a/tests/lib.rs
+++ b/tests/lib.rs
@@ -8,7 +8,7 @@ use std::collections::HashMap;
 use std::io::prelude::*;
 use std::fs::File;
 
-use rand::{Rng, thread_rng};
+use rand::{Rng, SeedableRng, thread_rng};
 use serialize::base64::FromBase64;
 use serialize::hex::FromHex;
 
@@ -462,3 +462,14 @@ fn problem_20 () {
         normalize(expected, 27)
     );
 }
+
+#[test]
+fn problem_21 () {
+    let mut mt = matasano::MersenneTwister::from_seed(0x12345678);
+    let got: Vec<u32> = mt.gen_iter().take(10).collect();
+    let expected: Vec<u32> = vec![
+        0xC6979343, 0x0962D2FA, 0xA73A24A4, 0xE118A180, 0xB5475ABB,
+        0x64613C7C, 0x6F32F4DB, 0xF27BF199, 0x464DD8DC, 0x95C1FED6,
+    ];
+    assert_eq!(&got[..], &expected[..]);
+}
-- 
cgit v1.2.3-54-g00ecf