randomize 1.0.0

//! A dead simple to use randomization library for rust.
//!
//! NOT FOR CRYPTOGRAPHIC PURPOSES.
//!
//! The crate is specific to my personal needs for building small games and
//! such. I don't want to or try to cover all use cases. If you need a highly
//! general crate for randomization you should use the
//! [rand](https://crates.io/crates/rand) crate, which is the "official" way to
//! do randomization in rust.

#![forbid(missing_debug_implementations)]
#![warn(missing_docs)]
#![allow(non_upper_case_globals)]

extern crate serde;

#[macro_use]
extern crate serde_derive;

use std::num::NonZeroU64;
use std::ops::{Bound, RangeBounds};
use std::ptr::null_mut;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::sync::{Mutex, MutexGuard};

static GLOBAL_GENERATOR_MUTEX: AtomicPtr<Mutex<PCG32>> = AtomicPtr::new(null_mut());

macro_rules! doc_comment {
    ($x:expr, $($tt:tt)*) => {
        #[doc = $x]
        $($tt)*
    };
}

macro_rules! make_dX_const_randrange32 {
  ($name:ident, $sides:expr) => {
    doc_comment!(
      concat!("A constant for rolling a 1d", stringify!($sides)),
      pub const $name: RandRangeU32 = RandRangeU32 {
        base: 1,
        width: $sides,
        reject: ::std::u32::MAX - (::std::u32::MAX % $sides),
      };
    );
  };
}

make_dX_const_randrange32!(d4, 4);
make_dX_const_randrange32!(d6, 6);
make_dX_const_randrange32!(d8, 8);
make_dX_const_randrange32!(d10, 10);
make_dX_const_randrange32!(d12, 12);
make_dX_const_randrange32!(d20, 20);

#[test]
fn const_generating_macro_test() {
  assert_eq!(d4, RandRangeU32::new(1..=4));
  assert_eq!(d6, RandRangeU32::new(1..=6));
  assert_eq!(d8, RandRangeU32::new(1..=8));
  assert_eq!(d10, RandRangeU32::new(1..=10));
  assert_eq!(d12, RandRangeU32::new(1..=12));
  assert_eq!(d20, RandRangeU32::new(1..=20));
}

/// Produces a `u64` value using the system clock.
///
/// It can easily be the case that two calls to this method in a row will give
/// identical results, because it can run faster than the resolution of your
/// system clock.
pub fn u64_from_time() -> u64 {
  use std::time::{SystemTime, UNIX_EPOCH};
  let unix_delta = match SystemTime::now().duration_since(UNIX_EPOCH) {
    Ok(duration) => duration,
    Err(system_time_error) => system_time_error.duration(),
  };
  if unix_delta.subsec_nanos() != 0 {
    unix_delta.as_secs().wrapping_mul(unix_delta.subsec_nanos() as u64)
  } else {
    unix_delta.as_secs()
  }
}

/// A [Permuted Congruential
/// Generator](https://en.wikipedia.org/wiki/Permuted_congruential_generator)
/// that generates 32 bits of output per use.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct PCG32 {
  inc: NonZeroU64,
  state: u64,
}
impl PCG32 {
  /// Constructs a new generator from the values given.
  ///
  /// The `inc` value of the generator must be odd, so whatever number you give
  /// is OR'd with 1 to ensure this.
  pub fn new(state: u64, inc: u64) -> Self {
    Self {
      state,
      inc: unsafe { NonZeroU64::new_unchecked(inc | 1) },
    }
  }

  /// The current `state` of the generator.
  ///
  /// Changes over time.
  pub fn state(&self) -> u64 {
    self.state
  }

  /// The `inc` of the generator.
  ///
  /// Does not change during the life of the generator.
  pub fn inc(&self) -> u64 {
    self.inc.get()
  }

  /// Gives the next 32 bits of output.
  pub fn next_u32(&mut self) -> u32 {
    debug_assert!(self.inc.get() != 0);
    // xsh_rr_64_32
    const MAGIC_LCG_MULT: u64 = 6364136223846793005;
    let new_state: u64 = self.state.wrapping_mul(MAGIC_LCG_MULT).wrapping_add(self.inc.get());
    let xor_shifted: u32 = (((self.state >> 18) ^ self.state) >> 27) as u32;
    let rot: u32 = (self.state >> 59) as u32;
    let output = xor_shifted.rotate_right(rot);
    self.state = new_state;
    output
  }

  /// Gives the next `usize` worth of output.
  ///
  /// These docs were compiled for a 32-bit machine, so it'll run the generator
  /// once.
  #[cfg(target_pointer_width = "32")]
  pub fn next_usize(&mut self) -> usize {
    self.next_u32() as usize
  }

  /// Gives the next `usize` worth of output.
  ///
  /// These docs were compiled for a 64-bit machine, so it'll run the generator
  /// twice to get some low bits and some high bits and then put them together.
  #[cfg(target_pointer_width = "64")]
  pub fn next_usize(&mut self) -> usize {
    let low_bits = self.next_u32();
    let high_bits = self.next_u32();
    (high_bits as usize) | ((low_bits as usize) << 32)
  }
}
impl Default for PCG32 {
  fn default() -> Self {
    Self::new(0xabcdef0123456789, 1)
  }
}

/// Gets you a `MutexGuard` around a global `PCG32`.
///
/// The global generator is lazily initialized using the system clock whenever
/// this is first called. You can then `DerefMut` that into the inner `PCG32`
/// value.
///
/// ```rust
/// use randomize::*;
/// let gen: &mut PCG32 = &mut global_gen();
/// d6.sample(gen);
/// ```
pub fn global_gen() -> MutexGuard<'static, PCG32> {
  unsafe {
    let mutex_ref = match GLOBAL_GENERATOR_MUTEX.load(Ordering::SeqCst).as_ref() {
      Some(mutex_ref) => mutex_ref,
      None => {
        let u = u64_from_time();
        let mutex_box_raw = Box::into_raw(Box::new(Mutex::new(PCG32::new(u, u))));
        match GLOBAL_GENERATOR_MUTEX
          .compare_and_swap(null_mut(), mutex_box_raw, Ordering::SeqCst)
          .as_ref()
        {
          Some(mutex_ref) => {
            let _mutex_box_reconstructed = Box::from_raw(mutex_box_raw);
            mutex_ref
          }
          None => mutex_box_raw.as_ref().unwrap(),
        }
      }
    };
    match mutex_ref.lock() {
      Ok(guard) => guard,
      Err(poison_error_guard) => poison_error_guard.into_inner(),
    }
  }
}

/// Trait for types that can perform a random distribution via `&self`.
pub trait RefDistribution<T> {
  /// Uses the provided generator to give you the next output of the
  /// distribution.
  ///
  /// Depending on the distribution, the generator might be used any number of
  /// times to arrive at a value.
  fn sample(&self, gen: &mut PCG32) -> T;
}

fn convert_rangebound32_to_min_and_max(r: impl RangeBounds<u32>) -> (u32, u32) {
  let start = match r.start_bound() {
    Bound::Included(&x) => x,
    Bound::Excluded(&x) => x + 1,
    Bound::Unbounded => 0,
  };
  let end = match r.end_bound() {
    Bound::Included(&x) => x,
    Bound::Excluded(&x) => x - 1,
    Bound::Unbounded => ::std::u32::MAX,
  };
  (start, end)
}

fn convert_rangeboundusize_to_min_and_max(r: impl RangeBounds<usize>) -> (usize, usize) {
  let start = match r.start_bound() {
    Bound::Included(&x) => x,
    Bound::Excluded(&x) => x + 1,
    Bound::Unbounded => 0,
  };
  let end = match r.end_bound() {
    Bound::Included(&x) => x,
    Bound::Excluded(&x) => x - 1,
    Bound::Unbounded => ::std::usize::MAX,
  };
  (start, end)
}

/// A random range that produces `u32` values in a specified (inclusive) range.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct RandRangeU32 {
  base: u32,
  width: u32,
  reject: u32,
}

impl RandRangeU32 {
  /// Makes a new value using the specified bounds.
  ///
  /// The `RangeBounds` trait is used here so that you can specify the desired
  /// range with either an exclusive range operator or an inclusive range
  /// operator. The resulting RandRange32 is always inclusive.
  ///
  /// ```rust
  /// use randomize::*;
  /// let inclusive = RandRangeU32::new(1..=6);
  /// let exclusive = RandRangeU32::new(1..7);
  /// assert_eq!(inclusive.high(), exclusive.high());
  /// ```
  ///
  /// # Panics
  ///
  /// If you attempt to specify the entire `u32` range this will panic.
  pub fn new(r: impl RangeBounds<u32>) -> Self {
    let (a, b) = convert_rangebound32_to_min_and_max(r);
    let low = a.min(b);
    let high = a.max(b);
    let base = low;
    let width = (high - low) + 1;
    assert!(width > 0);
    let width_count = ::std::u32::MAX / width;
    let reject = width_count * width;
    RandRangeU32 { base, width, reject }
  }

  /// Gives the low inclusive end of the range.
  pub fn low(&self) -> u32 {
    self.base
  }

  /// Gives the high inclusive end of the range.
  pub fn high(&self) -> u32 {
    self.base + (self.width - 1)
  }

  fn convert(&self, roll: u32) -> Option<u32> {
    if roll >= self.reject {
      None
    } else {
      Some(self.base + (roll % self.width))
    }
  }
}

impl RefDistribution<u32> for RandRangeU32 {
  fn sample(&self, gen: &mut PCG32) -> u32 {
    loop {
      match self.convert(gen.next_u32()) {
        Some(output) => return output,
        None => continue,
      }
    }
  }
}

/// A random range that produces `usize` values in a specified (inclusive)
/// range.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RandRangeUsize {
  base: usize,
  width: usize,
  reject: usize,
}

impl RandRangeUsize {
  /// Makes a new value using the specified bounds.
  ///
  /// The `RangeBounds` trait is used here so that you can specify the desired
  /// range with either an exclusive range operator or an inclusive range
  /// operator. The resulting RandRangeUsize is always inclusive.
  ///
  /// ```rust
  /// use randomize::*;
  /// let inclusive = RandRangeUsize::new(1..=6);
  /// let exclusive = RandRangeUsize::new(1..7);
  /// assert_eq!(inclusive.high(), exclusive.high());
  /// ```
  ///
  /// # Panics
  ///
  /// If you attempt to specify the entire `usize` range this will panic.
  pub fn new(r: impl RangeBounds<usize>) -> Self {
    let (a, b) = convert_rangeboundusize_to_min_and_max(r);
    let low = a.min(b);
    let high = a.max(b);
    let base = low;
    let width = (high - low) + 1;
    assert!(width > 0);
    let width_count = ::std::usize::MAX / width;
    let reject = width_count * width;
    RandRangeUsize { base, width, reject }
  }

  /// Gives the low inclusive end of the range.
  pub fn low(&self) -> usize {
    self.base
  }

  /// Gives the high inclusive end of the range.
  pub fn high(&self) -> usize {
    self.base + (self.width - 1)
  }

  fn convert(&self, roll: usize) -> Option<usize> {
    if roll >= self.reject {
      None
    } else {
      Some(self.base + (roll % self.width))
    }
  }
}

impl RefDistribution<usize> for RandRangeUsize {
  fn sample(&self, gen: &mut PCG32) -> usize {
    loop {
      match self.convert(gen.next_usize()) {
        Some(output) => return output,
        None => continue,
      }
    }
  }
}

// // //
// Tests for private functions / methods
// // //

#[test]
#[ignore]
fn range_range_inclusive_32_sample_validity_test_d6() {
  let check_d6 = RandRangeU32::new(1..=6);
  assert_eq!(check_d6, d6);
  let the_range = d6;
  let mut outputs: [u32; 7] = [0; 7];
  for u in 0..=::std::u32::MAX {
    let opt = the_range.convert(u);
    match opt {
      Some(roll) => outputs[roll as usize] += 1,
      None => outputs[0] += 1,
    };
  }
  assert!(outputs[0] < 6);
  let ones = outputs[1];
  assert_eq!(ones, outputs[2], "{:?}", outputs);
  assert_eq!(ones, outputs[3], "{:?}", outputs);
  assert_eq!(ones, outputs[4], "{:?}", outputs);
  assert_eq!(ones, outputs[5], "{:?}", outputs);
  assert_eq!(ones, outputs[6], "{:?}", outputs);
}

#[test]
#[ignore]
fn range_range_inclusive_32_sample_validity_test_d8() {
  let check_d8 = RandRangeU32::new(1..=8);
  assert_eq!(check_d8, d8);
  let the_range = d8;
  let mut outputs: [u32; 9] = [0; 9];
  for u in 0..=::std::u32::MAX {
    let opt = the_range.convert(u);
    match opt {
      Some(roll) => outputs[roll as usize] += 1,
      None => outputs[0] += 1,
    };
  }
  assert!(outputs[0] <= 8, "{:?}", outputs);
  let ones = outputs[1];
  assert_eq!(ones, outputs[2], "{:?}", outputs);
  assert_eq!(ones, outputs[3], "{:?}", outputs);
  assert_eq!(ones, outputs[4], "{:?}", outputs);
  assert_eq!(ones, outputs[5], "{:?}", outputs);
  assert_eq!(ones, outputs[6], "{:?}", outputs);
}