randomize.rs

// Released to the Public Domain via The Unlicense.

//! Holds PRNG related types and operations.
//!
//! We're not using `rand`, because we don't need no instructions to know how to
//! rock.
//!
//! # PCG Stuff
//!
//! The PRNGs here are all generators from the [Permuted Congruential
//! Generator](https://en.wikipedia.org/wiki/Permuted_congruential_generator)
//! family of generators.
//!
//! * PCG family generators have a period equal to their state size range. For
//!   example, all the generators with a `u64` for state have a period of 2^64 .
//! * In addition to using a `state` value, they also have a "stream selection"
//!   value called `inc`. All streams will give uniform output, but the outputs
//!   will happen in a different order depending on the stream used. The stream
//!   selection can be any value, but the input is bitwise OR'd with 1 before
//!   it's used (it must always be odd). This means that, for example, when
//!   `inc` is a `u64` there will be 2^63 distinct number streams (64 bit `inc`
//!   range - 1 bit always being forced on = 63).
//! * Variations exist where the stream can automatically be selected for you,
//!   either by using a fixed constant or by using the memory address of the
//!   `&mut u64` given to the generator.
//!
//! The "Permuted" part of PCG means that the LCG output is transformed before
//! becoming the final output. This makes the average quality LCG result into a
//! high quality result without needing to use as much state space. As one might
//! expect, the better transforms take slightly longer to perform.
//!
//! * The usual permutation is `xsh_rr`, which is very fast but requires a state
//!   size of at least _twice as big_ as the output size.
//! * There is also a `rxs_m_xs` permutation where the state only needs to be
//!   _as big_ as the output size, but because it is slightly slower it is
//!   normally reserved for when the state available is limited for some reason.
//! * The various transform options and suggested ways to combine them are
//!   explained on the wikipedia page linked above.
//!
//! All of the provided generator variations are available as stand alone
//! functions, and the preferred generator variant also has a struct form for
//! ease of use.

// shout case can flip off.
#![allow(non_upper_case_globals)]

/// Uses the system time to determine a `u64` value.
///
/// This works well if you just want any old `u64` as a seed value for an RNG.
/// However, rapid calls are very likely to produce identical values in
/// succession. If you need several `u64` values quickly, consider making the
/// first one from the time and then the rest from
/// [pcg_rxs_m_xs_64_64_spec](fn.pcg_rxs_m_xs_64_64_spec.html)
///
/// Please also note that using the system time as a random number seed is **not
/// secure**, and that this should only be used when security is not a concern.
/// If you wouldn't be willing to let the program user pick their own seed, you
/// probably don't want to use the system time as the seed source either.
pub fn u64_from_system_time() -> u64 {
    let sys_time = ::std::time::SystemTime::now();
    let duration_result = sys_time.duration_since(::std::time::UNIX_EPOCH);
    let duration = match duration_result {
        Ok(duration) => duration,
        Err(sys_time_error) => sys_time_error.duration(),
    };
    duration.as_secs().wrapping_mul(
        duration.subsec_nanos().max(1) as u64,
    )
}

/// This can be set to any LCG constant. You can check [the Wikipedia
/// entry](https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use)
/// for some commonly used values. Note that not all constants are equally good,
/// so read the rest of that page carefully if you're trying to come up with
/// your own. Test whatever value you pick as well. Changing the LCG multiplier
/// value effectively makes an entirely new generator, it's a much bigger effect
/// than adjusting the number stream by changing the increment value.
const lcg_magic_mult64: u64 = 6364136223846793005;

/// This is an LCG constant that fits into a 32-bit space.
const lcg_magic_mult32: u32 = 134775813;

/// When we "split" a generator we'll do a wrapping add by this much on the
/// `inc` value of the split off generator. The value selected happens to be the
/// step jump that SplitMix64 uses, but any odd value is fine.
const generator_stream_split_add: u64 = 0x9e3779b97f4a7c15;

/// xor the number with itself shifted to the left by the specified amount.
fn xor_64(n: u64, xor_bits: u64) -> u64 {
    n ^ (n >> xor_bits)
}

/// xor the number with itself shifted to the left by the specified amount.
fn xor_32(n: u32, xor_bits: u32) -> u32 {
    n ^ (n >> xor_bits)
}

/// PCG, 64-bit state, 32-bit output, specified stream.
///
/// The output permutation is:
///
/// * Fixed xorshift of the high bits
/// * Downshift the high bits to a `u32`
/// * Randomized right-rotation of the `u32`
///
/// This strikes a good balance between generation quality and generation speed.
/// The `inc` value is bitwise OR'd with 1 before it's used, so there are no
/// restrictions on either of the input values.
///
/// This generator is somewhat hard to predict, but it is **not**
/// cryptographically secure.
pub fn pcg_xsh_rr_64_32_spec(state: &mut u64, inc: u64) -> u32 {
    // Here we have many constants that we will name so that you can understand
    // what's going on. This is all optimized into the same as writing it all
    // inlined, so we might as well give names to things.
    const state_bits: u64 = 64;
    const output_bits: u64 = 32;
    const rotate_bits: u64 = 5;
    const used_bits: u64 = output_bits + rotate_bits;
    const half_used: u64 = used_bits / 2;
    const discard_shift: u64 = state_bits - used_bits;
    const rotation_shift: u64 = state_bits - rotate_bits;
    // make a copy of the state to work with later.
    let st = *state;
    // Set the next state according to the normal LCG style. In rust, if you
    // want wrapping at all times you need to specify it with these funny
    // looking calls. Otherwise, any overflows will panic in debug mode (and the
    // LCG relies on being able to overflow).
    *state = st.wrapping_mul(lcg_magic_mult64).wrapping_add(inc | 1);
    // Create our output with the work copy of the old state, which I guess
    // gives us better ILP according to the PCG wikipedia entry.
    let xord: u64 = xor_64(st, half_used);
    let xord_shifted: u32 = (xord >> discard_shift) as u32;
    let rand_rotate_amount: u32 = (st >> rotation_shift) as u32;
    xord_shifted.rotate_right(rand_rotate_amount)
}

/// PCG, 64-bit state, 32-bit output, memory address stream.
///
/// This is as per [pcg_xsh_rr_64_32_spec](fn.pcg_xsh_rr_64_32_spec.html), but
/// instead of specifying a stream the memory address of the state reference
/// given is converted into a `u64` and then used as the stream selection.
pub fn pcg_xsh_rr_64_32_mem(state: &mut u64) -> u32 {
    // Even if `usize` is not 64 bits, this is fine. We simply need any value to
    // pass along as the stream specifier.
    let mem_inc: u64 = state as *const u64 as usize as u64;
    pcg_xsh_rr_64_32_spec(state, mem_inc)
}

/// PCG, 64-bit state, 32-bit output, fixed stream.
///
/// This is as per [pcg_xsh_rr_64_32_spec](fn.pcg_xsh_rr_64_32_spec.html), but
/// instead of specifying a stream it simply uses a fixed stream value for you.
pub fn pcg_xsh_rr_64_32_fixed(state: &mut u64) -> u32 {
    pcg_xsh_rr_64_32_spec(state, 12345)
}

/// The recommended form of a PCG Generator with 32 bits of output per step.
///
/// This is a simple newtype wrapper over a `[u64; 2]` value. The 0th position
/// is used for the state (which changes for each generator use) and 1st
/// position is used for the inc (which is fixed during the generator's
/// lifetime).
///
/// ```rust
/// use galaxy_break::randomize::PCG32;
/// let mut gen = PCG32::from([234,567]);
/// gen.next_u32();
/// ```
#[derive(Debug, Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PCG32([u64; 2]);

impl From<[u64; 2]> for PCG32 {
    fn from(data: [u64; 2]) -> Self {
        PCG32(data)
    }
}

impl PCG32 {
    /// Advances the generator and returns the output.
    ///
    /// Uses the [pcg_xsh_rr_64_32_spec](fn.pcg_xsh_rr_64_32_spec.html) function.
    pub fn next_u32(&mut self) -> u32 {
        let inc = self.0[1];
        pcg_xsh_rr_64_32_spec(&mut self.0[0],inc)
    }

    // TODO: Jump Ahead
    
    // TODO: Other Features?
}

/// PCG, 32-bit state, 32-bit output, specified stream.
///
/// The output permutation is:
///
/// * Randomized Xorshift
/// * Multiply by a fixed constant
/// * Fixed Xorshift
///
/// This generator uses only 32 bits of state, and so it _cannot possibly_ pass
/// even the basic statistical tests that demand a large amount of output. It
/// should really _only_ be used when you need to get a 32-bit output and you
/// only have 32 bits of state for whatever reason.
///
/// On 32-bit systems it _might_ perform faster than the other PCG variants
/// simply because it only uses 32-bit math, but the loss of output quality and
/// output period is probably not worth the speed gain.
///
/// This generator is somewhat hard to predict, but it is **not**
/// cryptographically secure.
pub fn pcg_rxs_m_xs_32_32_spec(state: &mut u32, inc: u32) -> u32 {
    const state_bits: u32 = 32;
    const output_bits: u32 = 32;
    const rxs_select_bits: u32 = 4;
    const used_bits: u32 = output_bits + rxs_select_bits;
    const half_used: u32 = used_bits / 2;
    const rxs_select_shift: u32 = state_bits - rxs_select_bits;
    const rxs_base_shift: u32 = rxs_select_bits + (32 / state_bits);
    const magic_middle_mult32: u32 = 277803737;
    // we'll work with the old state
    let st = *state;
    // advance the state
    *state = st.wrapping_mul(lcg_magic_mult32).wrapping_add(inc | 1);
    // permute the old state into the final output.
    let rxs_selection = st >> rxs_select_shift;
    let rxsd = xor_32(st, rxs_base_shift + rxs_selection);
    xor_32(rxsd.wrapping_mul(magic_middle_mult32), half_used)
}

/// PCG, 64-bit state, 64-bit output, specified stream.
///
/// The output permutation is:
///
/// * Randomized Xorshift
/// * Multiply by a fixed constant
/// * Fixed Xorshift
///
/// Because Rust doesn't have `u128` support in stable yet, you need to use this
/// whenever you want `u64` output. Later versions of this module will support
/// "extended" generators that can make `u64` values without actually needing
/// `u128` support. For now just deal.
///
/// This generator is somewhat hard to predict, but it is **not**
/// cryptographically secure.
pub fn pcg_rxs_m_xs_64_64_spec(state: &mut u64, inc: u64) -> u64 {
    const state_bits: u64 = 64;
    const output_bits: u64 = 64;
    const rxs_select_bits: u64 = 5;
    const used_bits: u64 = output_bits + rxs_select_bits;
    const half_used: u64 = used_bits / 2;
    const rxs_select_shift: u64 = state_bits - rxs_select_bits;
    const rxs_base_shift: u64 = rxs_select_bits + (32 / state_bits);
    const magic_middle_mult64: u64 = 12605985483714917081;
    // we'll work with the old state
    let st = *state;
    // advance the state
    *state = st.wrapping_mul(lcg_magic_mult64).wrapping_add(inc | 1);
    // permute the old state into the final output.
    let rxs_selection = st >> rxs_select_shift;
    let rxsd = xor_64(st, rxs_base_shift + rxs_selection);
    xor_64(rxsd.wrapping_mul(magic_middle_mult64), half_used)
}

/// Represents a pre-computed range for use with `u32` random number generation.
///
/// This allows you to take random `u32` values and have them uniformly
/// distributed into the appropriate range. Naturally, unless the size of the
/// range divides evenly into the `u32` range, this means that some `u32` values
/// will have to be discarded when checked against a range.
///
/// Please note that this is an *inclusive* range, because any universe where a
/// d6 is written as (1,7) makes me sick.
///
/// ```rust
/// use galaxy_break::randomize::RandRange32;
/// let d6 = RandRange32::new(1,6);
/// assert_eq!(d6.low(), 1);
/// assert_eq!(d6.high(), 6);
/// ```
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RandRange32 {
    low: u32,
    width: u32,
    discard_threshold: u32,
}

impl RandRange32 {
    /// Makes a new `RandRange32` value.
    ///
    /// * If you pass `low == 0` and `high == u32::MAX` then the upper bound of
    ///   the returned range will be cut down by 1 point. This isn't a big deal,
    ///   since if you actually want random values across the entire `u32` type
    ///   you can just use the random functions directly.
    /// * If `low` is greater than `high`, it flips them and gives you that
    ///   `RandRange32` instead.
    ///
    /// ```rust
    /// use galaxy_break::randomize::RandRange32;
    /// use std::u32;
    ///
    /// let big = RandRange32::new(0, u32::MAX);
    /// assert_eq!(big.low(), 0);
    /// assert_eq!(big.high(), u32::MAX - 1);
    ///
    /// let d10 = RandRange32::new(10, 1);
    /// assert_eq!(d10.low(), 1);
    /// assert_eq!(d10.high(), 10);
    /// ```
    pub fn new(low: u32, high: u32) -> Self {
        use std::u32;
        // We can't represent the full `u32` range with this type, so if they
        // try to do that we'll bump it down by one.
        let high = if low == 0 && high == u32::MAX {
            u32::MAX - 1
        } else {
            high
        };
        if low > high {
            Self::new(high, low)
        } else if low == high {
            Self {
                low,
                width: 1,
                discard_threshold: u32::MAX,
            }
        } else {
            let width = high - low + 1;
            let discard_threshold = u32::MAX - (u32::MAX % width);
            Self {
                low,
                width,
                discard_threshold,
            }
        }
    }

    /// The low end of this range.
    pub fn low(&self) -> u32 {
        self.low
    }

    /// The high end of this range.
    pub fn high(&self) -> u32 {
        self.low + self.width - 1
    }

    /// Checks a particular `u32` roll against the range.
    ///
    /// If the `u32` can be uniformly translated to fit in range then you get
    /// `Some(val)` with the in-range value. Otherwise you get `None`.
    ///
    /// We always do a discard check, even if the range would divide evenly into
    /// a `u32` (and thus not require a discard step). It's a little faster to
    /// have a little less branching, and for the commonly used small ranges
    /// that do divide evenly into a `u32` the possibility of discarding when we
    /// didn't have to is relatively small (eg: `4 / u32::MAX`, or `8 /
    /// u32::MAX`), small enough to justify favoring the more common case.
    ///
    /// ```rust
    /// use galaxy_break::randomize::RandRange32;
    /// use std::u32;
    ///
    /// let d20 = RandRange32::new(1, 20);
    /// assert_eq!(d20.for_roll(1337), Some(18));
    /// assert_eq!(d20.for_roll(u32::MAX), None);
    ///
    /// let d6plus3 = RandRange32::new(4, 9);
    /// assert_eq!(d6plus3.for_roll(0xFACE), Some(4));
    ///
    /// let d8 = RandRange32::new(1, 8);
    /// assert_eq!(d8.for_roll(u32::MAX), None);
    /// ```
    pub fn for_roll(&self, roll: u32) -> Option<u32> {
        if roll >= self.discard_threshold {
            None
        } else {
            Some(self.low + roll % self.width)
        }
    }

    /// Given a `PCG32`, runs it until an in-range output is obtained.
    ///
    /// ```rust
    /// use galaxy_break::randomize::{RandRange32, PCG32};
    /// let mut gen = PCG32::from([888,999]);
    /// let range = RandRange32::new(10,20);
    /// let value = range.with_gen(&mut gen);
    /// assert!(value >= 10 && value <= 20);
    /// ```
    pub fn with_gen(&self, gen: &mut PCG32) -> u32 {
        loop {
            if let Some(out) = self.for_roll(gen.next_u32()) {
                return out;
            }
        }
    }
}

/// Checks the "1d6" random range for correct output. This tests every possible
/// `u32` input, since there's really not _that_ many. However, running it in
/// release mode takes a moment or two and running it in debug mode takes so
/// long that I've never bothered to let it run all the way.
///
/// cargo test --release -- --ignored
#[test]
#[ignore]
#[allow(non_snake_case)]
fn test_RandRange32_for_roll_1_6() {
    // Index 0 is the None results, and Index 1 though 6 are the Some results.
    let mut outs = [0; 7];
    let d6 = RandRange32::new(1, 6);
    let mut roll = 0;
    while roll < ::std::u32::MAX {
        match d6.for_roll(roll) {
            Some(val) => outs[val as usize] += 1,
            None => outs[0] += 1,
        }
        roll += 1;
    }
    // Add the max value too.
    match d6.for_roll(::std::u32::MAX) {
        Some(val) => outs[val as usize] += 1,
        None => outs[0] += 1,
    }
    // For now we just measure in-range results, we don't check how many out of
    // range things we had.
    let target = outs[1];
    if !outs.iter().skip(1).all(|&u| u == target) {
        panic!("failure: {:?}", outs);
    }
}