Implement lagged Fibonacci PRNG in rust, compatible with hwengine
authorunc0rr
Sat, 13 Oct 2018 18:32:41 +0200
changeset 13910 b6c35ac1c5ba
parent 13909 cd39e87d7a80
child 13911 9ae1184886db
child 13914 5988e73080a3
Implement lagged Fibonacci PRNG in rust, compatible with hwengine
rust/lfprng/Cargo.toml
rust/lfprng/src/lib.rs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/lfprng/Cargo.toml	Sat Oct 13 18:32:41 2018 +0200
@@ -0,0 +1,6 @@
+[package]
+name = "lfprng"
+version = "0.1.0"
+authors = ["Andrey Korotaev <a.korotaev@hedgewars.org>"]
+
+[dependencies]
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/lfprng/src/lib.rs	Sat Oct 13 18:32:41 2018 +0200
@@ -0,0 +1,65 @@
+pub struct LaggedFibonacciPRNG {
+    circular_buffer: [u32; 64],
+    index: usize,
+}
+
+impl LaggedFibonacciPRNG {
+    fn new(init_values: &[u8]) -> Self {
+        let mut buf = [0xa98765 + 68; 64];
+
+        for i in 0..std::cmp::min(init_values.len(), 54) {
+            buf[i] = init_values[i] as u32;
+        }
+
+        let mut prng = Self {
+            circular_buffer: buf,
+            index: 54,
+        };
+
+        for i in 0..2048 {
+            prng.get_next();
+        }
+
+        prng
+    }
+
+    #[inline]
+    fn get_next(&mut self) -> u32 {
+        self.index = (self.index + 1) & 0x3f;
+        self.circular_buffer[self.index] = (self.circular_buffer[(self.index + 40) & 0x3f]
+            + self.circular_buffer[(self.index + 9) & 0x3f])
+            & 0x7fffffff;
+
+        self.circular_buffer[self.index]
+    }
+
+    #[inline]
+    fn get_random(&mut self, modulo: u32) -> u32 {
+        self.get_next();
+        self.get_next() % modulo
+    }
+
+    #[inline]
+    fn add_randomness(&mut self, value: u32) {
+        self.index = (self.index + 1) & 0x3f;
+        self.circular_buffer[self.index] ^= value;
+    }
+}
+
+#[cfg(test)]
+#[test]
+fn compatibility() {
+    let mut prng = LaggedFibonacciPRNG::new("{052e2aee-ce41-4720-97bd-559a413bf866}".as_bytes());
+
+    assert_eq!(prng.get_random(1000), 418);
+    assert_eq!(prng.get_random(1000000), 554064);
+    assert_eq!(prng.get_random(0xffffffff), 239515837);
+
+    prng.add_randomness(123);
+
+    for i in 0..=100000 {
+        prng.get_random(2);
+    }
+
+    assert_eq!(prng.get_random(0xffffffff), 525333582);
+}