#![no_std]
#![deny(missing_docs)]
#![deny(missing_debug_implementations)]
#![deny(unsafe_code)]

//! Simple and minimalist randomization.
//!
//! NOT FOR CRYPTOGRAPHIC PURPOSES.
//!
//! ## Basic Usage
//!
//! * Pick a generator, [PCG32] or [PCG64], depending on the output type you
//!   want. `PCG32` runs about 20% faster, so if you usually need 32 bits or
//!   less per use you might as well pick that.
//! * Seed your generator from wherever. However you wanna do it that your
//!   platform supports. Major options would be the
//!   [`getrandom`](https://docs.rs/getrandom) crate, [a hardware
//!   generator](core::arch::x86_64::_rdrand64_step) if available, the [CPU
//!   timing counter](core::arch::x86_64::_rdtsc) if there's no hardware
//!   generator, or even just a user input.
//! * The generators have a `state` and `inc` value. The `state` will change
//!   with each call, the `inc` is like a stream selection value that doesn't
//!   change when you use the generator. If you don't care about stream
//!   selection just pass your seed value to both arguments and it'll all "just
//!   work".
//! * Call [next_u32](PCG32::next_u32) or [next_u64](PCG64::next_u64) to get
//!   your numbers.
//! * You can use [RandRangeU32] for bounded integer randomization.
//!
//! That's it, that's the whole lib. No generics, no traits, no breaking changes
//! issued as patch releases, none of that.
//!
//! ## Any-size Integrals
//!
//! Where generating `u32`s or `u64`s is not enough, you can wrap your generator
//! inside an [AnyPCG] to generate non-floating-point integral values of any
//! size.
//!
//! * Create a fixed-size generator, e.g. `let gen = PCG32::new(…);`
//! * Create an any-size generator from it: `let any = AnyPCG::new(gen);`
//! * Call the provided `next_*` functions for the corresponding integral types,
//!   such as [next_u16](any::AnyPCG::next_u16) to generate a `u16` while only
//!   taking 16 bits out of the random bit streams.
//!
//! The more efficient use of generated bits comes at a barely noticeable cost
//! for [PCG32], and a bigger one for [PCG64]. This only matters for batch
//! generation of big amounts of random data, though.
//!
//! ## Floating Point
//!
//! Unfortunately, there's many possible float distributions a person might
//! want, so you'll have to call one of the float conversion functions yourself.
//! I've included conversions for the five most commonly used floating point
//! ranges.
//!
//! | Range | 32-bit | 64-bit |
//! |:-----:|:-------|:-------|
//! | `[0.0, 1.0)`| [f32_half_open_right] | [f64_half_open_right] |
//! | `(0.0, 1.0]` | [f32_half_open_left] | [f64_half_open_left] |
//! | `(0.0, 1.0)` | [f32_open] | [f64_open] |
//! | `[0.0, 1.0]` | [f32_closed] | [f64_closed] |
//! | `[-1.0, 1.0]` | [f32_closed_neg_pos] | [f64_closed_neg_pos] |

/// Fiddly to use, but totally gets you the minimum without branching.
///
/// Works for any integral type.
macro_rules! branchless_min {
  ($x:expr, $y:expr, $u:ty) => {
    $y ^ (($x ^ $y) & (<$u>::wrapping_neg(($x < $y) as $u)))
  };
}

/// Fiddly to use, but totally gets you the maximum without branching.
///
/// Works for any integral type.
macro_rules! branchless_max {
  ($x:expr, $y:expr, $u:ty) => {
    $x ^ (($x ^ $y) & (<$u>::wrapping_neg(($x < $y) as $u)))
  };
}

#[test]
fn test_branchless_min_and_max() {
  for x in core::u8::MIN..=core::u8::MAX {
    for y in core::u8::MIN..=core::u8::MAX {
      assert_eq!(branchless_min!(x, y, u8), x.min(y));
      assert_eq!(branchless_max!(x, y, u8), x.max(y));
    }
  }
  for x in core::i8::MIN..=core::i8::MAX {
    for y in core::i8::MIN..=core::i8::MAX {
      assert_eq!(branchless_min!(x, y, i8), x.min(y));
      assert_eq!(branchless_max!(x, y, i8), x.max(y));
    }
  }
}

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

use core::ops::*;

pub mod formulas;
pub use formulas::*;

mod any;
pub use any::*;

/// A [permuted congruential
/// generator](https://en.wikipedia.org/wiki/Permuted_congruential_generator)
/// with 32-bit output. Pick this by default.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct PCG32 {
  /// State value. Changes with every use.
  pub state: u64,
  /// Inc value. Selects the output stream ordering.
  ///
  /// This doesn't change as the generator is used. You just set it and forget
  /// it. If this value isn't odd, your generator won't have a full period
  /// before it loops. The [seed](PCG32::seed) constructor will ensure that the
  /// `inc` value is set to be odd, but the `From` constructors will not.
  pub inc: u64,
}
impl Default for PCG32 {
  #[inline]
  fn default() -> Self {
    Self::seed(DEFAULT_PCG_SEED as u64, DEFAULT_PCG_INC as u64)
  }
}
impl From<[u64; 2]> for PCG32 {
  /// Uses the provided values exactly.
  #[inline]
  fn from(value: [u64; 2]) -> Self {
    Self {
      state: value[0],
      inc: value[1],
    }
  }
}
impl From<(u64, u64)> for PCG32 {
  /// Uses the provided values exactly.
  #[inline]
  fn from(value: (u64, u64)) -> Self {
    Self {
      state: value.0,
      inc: value.1,
    }
  }
}
impl From<PCG32> for [u64; 2] {
  #[inline]
  fn from(pcg: PCG32) -> Self {
    [pcg.state, pcg.inc]
  }
}
impl From<PCG32> for (u64, u64) {
  #[inline]
  fn from(pcg: PCG32) -> Self {
    (pcg.state, pcg.inc)
  }
}
impl PCG32 {
  /// Crates a generator from the seed and inc given.
  ///
  /// The precise seeding details are not considered a "stable" part of the API.
  ///
  /// If you wish to exactly create a generator using particular `state` and
  /// `inc` values then use the `From` impl.
  #[inline]
  pub const fn seed(seed: u64, inc: u64) -> Self {
    let inc = (inc << 1) | 1;
    let mut state = pcg_core_state64(0, inc);
    state = state.wrapping_add(seed);
    state = pcg_core_state64(state, inc);
    Self { state, inc }
  }

  /// Runs the generator once and gets a `u32` as output.
  #[inline]
  pub fn next_u32(&mut self) -> u32 {
    let out = xsh_rr_64_32(self.state);
    self.state = pcg_core_state64(self.state, self.inc);
    out
  }

  /// Fill a mutable byte slice from this generator.
  #[inline]
  pub fn fill_bytes(&mut self, bytes: &mut [u8]) {
    let mut i = bytes.chunks_exact_mut(4);
    while let Some(chunk) = i.next() {
      chunk.copy_from_slice(&self.next_u32().to_le_bytes());
    }
    let rem = i.into_remainder();
    let rem_len = rem.len();
    let b = self.next_u32().to_le_bytes();
    rem.copy_from_slice(&b[..rem_len]);
  }

  /// Advances the generator `delta` steps in `log(delta)` time.
  #[inline]
  pub fn jump(&mut self, delta: u64) {
    self.state = jump_lcg64(delta, self.state, PCG_MULTIPLIER_64, self.inc)
  }
}
#[cfg(feature = "rand_core")]
impl rand_core::RngCore for PCG32 {
  fn next_u32(&mut self) -> u32 {
    PCG32::next_u32(self)
  }
  fn next_u64(&mut self) -> u64 {
    let low = PCG32::next_u32(self);
    let high = PCG32::next_u32(self);
    u64::from(low) | u64::from(high) << 32
  }
  fn fill_bytes(&mut self, dest: &mut [u8]) {
    PCG32::fill_bytes(self, dest)
  }
  fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand_core::Error> {
    PCG32::fill_bytes(self, dest);
    Ok(())
  }
}
#[cfg(feature = "rand_core")]
impl rand_core::SeedableRng for PCG32 {
  type Seed = [u8; core::mem::size_of::<[u64; 2]>()];
  fn from_seed(s: Self::Seed) -> Self {
    let state = u64::from_le_bytes([s[0], s[1], s[2], s[3], s[4], s[5], s[6], s[7]]);
    let inc = u64::from_le_bytes([s[8], s[9], s[10], s[11], s[12], s[13], s[14], s[15]]);
    PCG32::seed(state, inc)
  }
  fn seed_from_u64(u: u64) -> Self {
    PCG32::seed(u, u)
  }
  fn from_rng<R: rand_core::RngCore>(mut rng: R) -> Result<Self, rand_core::Error> {
    Ok(PCG32::seed(rng.next_u64(), rng.next_u64()))
  }
}

/// A [permuted congruential
/// generator](https://en.wikipedia.org/wiki/Permuted_congruential_generator)
/// with 64-bit output. Pick this if you want to do stuff with `f64` values.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct PCG64 {
  /// State value. Changes with every use.
  pub state: u128,
  /// Inc value. Selects the output stream ordering.
  ///
  /// This doesn't change as the generator is used. You just set it and forget
  /// it. If this value isn't odd, your generator won't have a full period
  /// before it loops. The [seed](PCG64::seed) constructor will ensure that the
  /// `inc` value is set to be odd, but the `From` constructors will not.
  pub inc: u128,
}
impl Default for PCG64 {
  #[inline]
  fn default() -> Self {
    Self::seed(DEFAULT_PCG_SEED, DEFAULT_PCG_INC)
  }
}
impl From<[u128; 2]> for PCG64 {
  /// Uses the provided values exactly.
  #[inline]
  fn from(value: [u128; 2]) -> Self {
    Self {
      state: value[0],
      inc: value[1],
    }
  }
}
impl From<(u128, u128)> for PCG64 {
  /// Uses the provided values exactly.
  #[inline]
  fn from(value: (u128, u128)) -> Self {
    Self {
      state: value.0,
      inc: value.1,
    }
  }
}
impl From<PCG64> for [u128; 2] {
  #[inline]
  fn from(pcg: PCG64) -> Self {
    [pcg.state, pcg.inc]
  }
}
impl From<PCG64> for (u128, u128) {
  #[inline]
  fn from(pcg: PCG64) -> Self {
    (pcg.state, pcg.inc)
  }
}
impl PCG64 {
  /// Crates a generator from the seed and inc given.
  ///
  /// The precise seeding details are not considered a "stable" part of the API.
  ///
  /// If you wish to exactly create a generator using particular `state` and
  /// `inc` values then use the `From` impl.
  #[inline]
  pub const fn seed(seed: u128, inc: u128) -> Self {
    let inc = (inc << 1) | 1;
    let mut state = pcg_core_state128(0, inc);
    state = state.wrapping_add(seed);
    state = pcg_core_state128(state, inc);
    Self { state, inc }
  }

  /// Runs the generator once and gets a `u64` as output.
  #[inline]
  pub fn next_u64(&mut self) -> u64 {
    let out = xsh_rr_128_64(self.state);
    self.state = pcg_core_state128(self.state, self.inc);
    out
  }

  /// Fill a mutable byte slice from this generator.
  #[inline]
  pub fn fill_bytes(&mut self, bytes: &mut [u8]) {
    let mut i = bytes.chunks_exact_mut(8);
    while let Some(chunk) = i.next() {
      chunk.copy_from_slice(&self.next_u64().to_le_bytes());
    }
    let rem = i.into_remainder();
    let rem_len = rem.len();
    let b = self.next_u64().to_le_bytes();
    rem.copy_from_slice(&b[..rem_len]);
  }

  /// Advances the generator `delta` steps in `log(delta)` time.
  #[inline]
  pub fn jump(&mut self, delta: u128) {
    self.state = jump_lcg128(delta, self.state, PCG_MULTIPLIER_128, self.inc)
  }
}
#[cfg(feature = "rand_core")]
impl rand_core::RngCore for PCG64 {
  fn next_u32(&mut self) -> u32 {
    PCG64::next_u64(self) as u32
  }
  fn next_u64(&mut self) -> u64 {
    PCG64::next_u64(self)
  }
  fn fill_bytes(&mut self, dest: &mut [u8]) {
    PCG64::fill_bytes(self, dest)
  }
  fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand_core::Error> {
    PCG64::fill_bytes(self, dest);
    Ok(())
  }
}
#[cfg(feature = "rand_core")]
impl rand_core::SeedableRng for PCG64 {
  type Seed = [u8; core::mem::size_of::<[u128; 2]>()];
  fn from_seed(s: Self::Seed) -> Self {
    let state = u128::from_le_bytes([
      s[0], s[1], s[2], s[3], s[4], s[5], s[6], s[7], s[8], s[9], s[10], s[11], s[12], s[13],
      s[14], s[15],
    ]);
    let inc = u128::from_le_bytes([
      s[16], s[17], s[18], s[19], s[20], s[21], s[22], s[23], s[24], s[25], s[26], s[27], s[28],
      s[29], s[30], s[31],
    ]);
    PCG64::seed(state, inc)
  }
  fn seed_from_u64(u: u64) -> Self {
    let u = u128::from(u);
    PCG64::seed(u, u)
  }
  fn from_rng<R: rand_core::RngCore>(mut rng: R) -> Result<Self, rand_core::Error> {
    let mut bytes = [0; core::mem::size_of::<[u128; 2]>()];
    rng.fill_bytes(&mut bytes[..]);
    Ok(<PCG64 as rand_core::SeedableRng>::from_seed(bytes))
  }
}

/// An inclusive random range with a `u32` low and high value.
///
/// This type utilizes `u64` math internally, so it's not entirely suitable for
/// 32-bit machines. It'll run, but more slowly than you might like if you're
/// using this in a tight loop.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct RandRangeU32 {
  base: u32,
  width: u32,
  threshold: u32,
}
impl RandRangeU32 {
  /// Attempts to make a new inclusive random range. Inputs can be in either order.
  ///
  /// ## Failure
  ///
  /// If the inputs are `0` and `core::u32::MAX`
  #[inline]
  pub fn try_new(a: u32, b: u32) -> Option<Self> {
    let (base, max) = (a.min(b), a.max(b));
    let width = max.wrapping_sub(base).wrapping_add(1);
    if width > 0 {
      let threshold = width.wrapping_neg() % width;
      Some(Self {
        base,
        width,
        threshold,
      })
    } else {
      None
    }
  }

  /// As [try_new](RandRangeU32::try_new), but `const`, and panics on failure.
  #[inline]
  pub const fn new(a: u32, b: u32) -> Self {
    let (base, max) = (branchless_min!(a, b, u32), branchless_max!(a, b, u32));
    let width = max.wrapping_sub(base).wrapping_add(1);
    let threshold = width.wrapping_neg() % width;
    Self {
      base,
      width,
      threshold,
    }
  }

  /// Inclusive low end of this range.
  #[inline]
  pub const fn low(&self) -> u32 {
    self.base
  }

  /// Inclusive high end of this range.
  #[inline]
  pub const fn high(&self) -> u32 {
    self.base.wrapping_add(self.width).wrapping_sub(1)
  }

  /// Given a uniform input, produces uniform output in range or fails.
  ///
  /// You aren't really intended to use this directly, instead you probably want
  /// to use [sample](RandRangeU32::sample).
  ///
  /// ## Failure
  ///
  /// Most ranges don't evenly distribute across the `u32` space, so some values
  /// will fail to end up in range.
  #[inline]
  pub fn place_in_range(&self, val: u32) -> Option<u32> {
    let mul: u64 = u64::from(val).wrapping_mul(u64::from(self.width));
    let low_part: u32 = mul as u32;
    if low_part < self.threshold {
      None
    } else {
      Some(((mul >> 32) as u32).wrapping_add(self.base))
    }
  }

  /// Sample from a [PCG32](PCG32) one or more times to get a value in range.
  #[inline]
  pub fn sample(&self, gen: &mut PCG32) -> u32 {
    loop {
      if let Some(output) = self.place_in_range(gen.next_u32()) {
        return output;
      }
    }
  }
}

impl From<Range<u32>> for RandRangeU32 {
  #[inline]
  fn from(r: Range<u32>) -> Self {
    Self::new(r.start.min(r.end), r.start.max(r.end) - 1)
  }
}
impl From<RangeFrom<u32>> for RandRangeU32 {
  #[inline]
  fn from(r: RangeFrom<u32>) -> Self {
    Self::new(r.start, core::u32::MAX - 1)
  }
}
impl From<RangeFull> for RandRangeU32 {
  #[inline]
  fn from(_: RangeFull) -> Self {
    Self::new(0, core::u32::MAX - 1)
  }
}
impl From<RangeInclusive<u32>> for RandRangeU32 {
  #[inline]
  fn from(r: RangeInclusive<u32>) -> Self {
    Self::new(*r.start(), *r.end())
  }
}
impl From<RangeTo<u32>> for RandRangeU32 {
  #[inline]
  fn from(r: RangeTo<u32>) -> Self {
    Self::new(0, r.end - 1)
  }
}
impl From<RangeToInclusive<u32>> for RandRangeU32 {
  #[inline]
  fn from(r: RangeToInclusive<u32>) -> Self {
    Self::new(0, r.end)
  }
}