rand_krull/

krull64.rs

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
use wrapping_arithmetic::wrappit;

// Krull64 features
// -"trivially strong" design by Sami Perttu
// -64-bit output, 192-bit state and footprint
// -full 192-bit state space with no bad states and no bad seeds
// -2**64 pairwise independent streams of length 2**128
// -streams are equidistributed with each 64-bit number appearing 2**64 times
// -random access inside streams
// -generation takes approximately 3.0 ns (where PCG-128 is 2.4 ns and Krull65 is 4.6 ns)

/// Krull64 non-cryptographic RNG. 64-bit output, 192-bit state.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct Krull64 {
    /// LCG state low bits.
    lcg0: u64,
    /// LCG state high bits.
    lcg1: u64,
    /// Stream number.
    stream: u64,
}

// Stream position is measured in relation to an origin LCG state at position 0.
// We define the origin as equal to the stream number XOR some arbitrary constant
// in order to desynchronize the streams. Here we invert all the bits,
// which potentially enhances compression of RNGs at position 0 when serialized.
#[inline]
fn origin_0(stream: u64) -> u64 {
    !stream
}

#[inline]
fn origin_128(stream: u64) -> u128 {
    origin_0(stream) as u128
}

impl Krull64 {
    #[inline]
    fn lcg_128(&self) -> u128 {
        self.lcg0 as u128 | ((self.lcg1 as u128) << 64)
    }

    #[inline]
    fn multiplier(&self) -> u64 {
        super::LCG_M65_1 as u64
    }

    #[inline]
    fn multiplier_128(&self) -> u128 {
        super::LCG_M65_1
    }

    #[inline]
    fn increment_128(&self) -> u128 {
        // LCG increment is odd in full period sequences.
        // Unlike with LCG multipliers, any odd increment works fine.
        // Flip of increment bit B causes changes with a period of 2**(128 - B):
        // LCG sequences that differ only in high bits of the increment are correlated.
        // So it's important to rely on the low increment bits only.
        // The increment is a mirror image of the state in this sense,
        // as in state it is the low bits that repeat.
        ((self.stream as u128) << 1) | 1
    }

    /// Origin is LCG state at position 0 in current stream.
    #[inline]
    fn origin_0(&self) -> u64 {
        origin_0(self.stream)
    }

    /// Origin is LCG state at position 0 in current stream.
    #[inline]
    fn origin_128(&self) -> u128 {
        origin_128(self.stream)
    }

    /// Generates the next 64-bit random number.
    #[wrappit]
    #[inline]
    pub fn step(&mut self) -> u64 {
        // We can get a widening 64-to-128-bit multiply by casting the arguments from 64 bits.
        // We also add the increment in 128-bit to get the carry for free.
        let lcg = (self.lcg0 as u128) * self.multiplier() as u128 + self.increment_128();
        self.lcg1 = ((lcg >> 64) as u64) + self.lcg1 * self.multiplier() + self.lcg0;
        self.lcg0 = lcg as u64;
        self.get()
    }

    /// Generates the next 128-bit random number.
    #[inline]
    pub fn step_128(&mut self) -> u128 {
        self.step() as u128 | ((self.step() as u128) << 64)
    }

    /// Returns the current 64-bit output.
    #[wrappit]
    #[inline]
    pub fn get(&self) -> u64 {
        // Take high 64 bits from the LCG, they are the most random.
        // The 1-to-1 mapping guarantees equidistribution
        // as the rest of the pipeline is bijective.
        let x = self.lcg1;

        // We want the output stage to pass tests also as an indexed RNG.
        // It was tested with PractRand to 1 TB in this use.
        // The output hash is a combination of stages from SplitMix64
        // combined with a final stage from a hash by degski.
        let x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        let x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        let x = (x ^ (x >> 31)) * 0xd6e8feb86659fd93;
        x ^ (x >> 32)
    }

    /// 128-bit version of step() for benchmarking.
    #[wrappit]
    #[inline]
    pub fn step_slow(&mut self) -> u64 {
        let lcg = self.lcg_128() * self.multiplier_128() + self.increment_128();
        self.lcg0 = lcg as u64;
        self.lcg1 = (lcg >> 64) as u64;
        self.get()
    }

    /// Creates a new Krull64 RNG.
    /// Stream and position are set to 0.
    #[allow(clippy::new_without_default)]
    pub fn new() -> Self {
        Krull64 {
            lcg0: origin_0(0),
            lcg1: 0,
            stream: 0,
        }
    }

    /// Creates a new Krull64 RNG from a 32-bit seed.
    /// Stream is set to the given seed and position is set to 0.
    /// All seeds work equally well.
    pub fn from_32(seed: u32) -> Self {
        Krull64::from_64(seed as u64)
    }

    /// Creates a new Krull64 RNG from a 64-bit seed.
    /// Stream is set to the given seed and position is set to 0.
    /// All seeds work equally well.
    pub fn from_64(seed: u64) -> Self {
        Krull64 {
            lcg0: origin_0(seed),
            lcg1: 0,
            stream: seed,
        }
    }

    /// Creates a new Krull64 RNG from a 128-bit seed.
    /// Each seed accesses a unique sequence of length 2**64.
    /// All seeds work equally well.
    /// Sets stream to a XOR of the high and low bits of seed
    /// to decorrelate nearby seeds in both arguments.
    /// Sets high bits of position from low bits of seed.
    pub fn from_128(seed: u128) -> Self {
        let mut krull = Krull64::from_64(((seed >> 64) ^ seed) as u64);
        krull.set_position((seed as u128) << 64);
        krull
    }

    /// Jumps forward (if steps > 0) or backward (if steps < 0) or does nothing (if steps = 0).
    /// The stream wraps around, so signed steps can be interpreted as unsigned.
    pub fn jump(&mut self, steps: i128) {
        let lcg = crate::lcg::get_state(
            self.multiplier_128(),
            self.increment_128(),
            self.lcg_128(),
            steps as u128,
        );
        self.lcg0 = lcg as u64;
        self.lcg1 = (lcg >> 64) as u64;
    }

    /// Returns current position in stream. The full state of the generator is (stream, position).
    pub fn position(&self) -> u128 {
        crate::lcg::get_iterations(
            self.multiplier_128(),
            self.increment_128(),
            self.origin_128(),
            self.lcg_128(),
        )
    }

    /// Sets position in stream.
    pub fn set_position(&mut self, position: u128) {
        let lcg = crate::lcg::get_state(
            self.multiplier_128(),
            self.increment_128(),
            self.origin_128(),
            position,
        );
        self.lcg0 = lcg as u64;
        self.lcg1 = (lcg >> 64) as u64;
    }

    /// Resets stream position to 0. Equivalent to set_position(0).
    #[inline]
    pub fn reset(&mut self) {
        self.lcg0 = self.origin_0();
        self.lcg1 = 0;
    }

    /// Returns current stream. The full state of the generator is (stream, position).
    #[inline]
    pub fn stream(&self) -> u64 {
        self.stream
    }

    /// Sets stream and initializes position to 0.
    pub fn set_stream(&mut self, stream: u64) {
        self.stream = stream;
        self.reset();
    }
}

use super::{Error, RngCore, SeedableRng};

impl RngCore for Krull64 {
    fn next_u32(&mut self) -> u32 {
        self.step() as u32
    }

    fn next_u64(&mut self) -> u64 {
        self.step()
    }

    fn fill_bytes(&mut self, dest: &mut [u8]) {
        let bytes = dest.len();
        let mut i = 0;
        while i < bytes {
            let x = self.step();
            let j = bytes.min(i + 8);
            // Always use Little-Endian.
            dest[i..j].copy_from_slice(&x.to_le_bytes()[0..(j - i)]);
            i = j;
        }
    }

    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> {
        self.fill_bytes(dest);
        Ok(())
    }
}

impl SeedableRng for Krull64 {
    type Seed = [u8; 16];

    /// Creates a new Krull64 RNG from a seed.
    /// All seeds work equally well.
    fn from_seed(seed: Self::Seed) -> Self {
        // Always use Little-Endian.
        Krull64::from_128(u128::from_le_bytes(seed))
    }
}

#[cfg(test)]
mod tests {
    use super::super::*;
    use super::*;

    #[test]
    pub fn run_tests() {
        let krull64_expected: [u64; 16] = [
            0x57c1b6c1df5ed4d2,
            0x1efdba83398cf412,
            0xa02d8dfda06ac9ce,
            0xf6e3f32be5e81841,
            0xc2a690083e597e0d,
            0x3b1b2ed3fa6c15aa,
            0x241c691340a479b2,
            0x88c24c8d79bb67c1,
            0x09f213c4fc2b61dc,
            0xa4b6ad95c713c951,
            0xa43904ae3341edf7,
            0xee2dca4d5fd5f8fa,
            0x27bdddbeaa4aadb0,
            0x98c78e68dbf634b2,
            0xf0edc57017a0d5a5,
            0x8647ea5de51eca23,
        ];
        let mut krull64 = Krull64::from_64(0);
        for x in krull64_expected {
            assert_eq!(x, krull64.next_u64());
        }

        let mut r: u128 = 0;
        let mut rnd = || -> u128 {
            r = r.wrapping_mul(LCG_M128_1).wrapping_add(0xffff);
            r
        };

        for _ in 0..1 << 12 {
            let seed = rnd() as u64;
            let mut krull1 = Krull64::new();
            assert_eq!(0, krull1.stream());
            assert_eq!(0, krull1.position());
            krull1.set_stream(seed);
            assert_eq!(seed, krull1.stream());
            assert_eq!(0, krull1.position());
            let mut krull2 = Krull64::from_64(seed);
            assert_eq!(seed, krull2.stream());
            assert_eq!(0, krull2.position());

            let pos2 = rnd();
            let pos1 = pos2 & rnd();
            krull1.set_position(pos1);
            krull2.set_position(pos2);
            assert_eq!(pos1, krull1.position());
            assert_eq!(pos2, krull2.position());
            krull1.jump((pos2 - pos1) as i128);
            assert_eq!(pos2, krull1.position());
            assert_eq!(krull1.next_u64(), krull2.next_u64());
            krull1.jump(-1);
            assert_eq!(pos2, krull1.position());
            krull2.jump(-1);
            assert_eq!(pos2, krull2.position());
            krull1.jump(-((pos2 - pos1) as i128));
            assert_eq!(pos1, krull1.position());

            let n = 1 + (rnd() & 0x3ff);
            for _ in 0..n {
                krull1.next_u64();
            }
            assert_eq!(pos1 + n, krull1.position());

            assert_eq!(seed, krull1.stream());

            let bytes = 1 + (rnd() & 0x7f);
            let mut buffer1 = [0u8; 0x80];
            let mut buffer2 = [0u8; 0x80];
            krull1.reset();
            assert_eq!(0, krull1.position());
            krull1.fill_bytes(&mut buffer1[0..bytes as usize]);
            krull2.reset();
            for i in 0..0x10 {
                let x = krull2.next_u64();
                buffer2[(i << 3)..((i + 1) << 3)].copy_from_slice(&x.to_le_bytes());
            }
            assert!(buffer1[0..bytes as usize]
                .iter()
                .zip(buffer2[0..bytes as usize].iter())
                .all(|(x, y)| x == y));
        }
    }
}