randomize 3.0.1

//! Provides a wrapper struct for `PCG32` and `PCG64` that generates
//! arbitrarily sized unsigned integers without wasting random bits.

// Note(Lokathor): Evrey made all the stuff in here. If you're confused by
// anything you better ask him.

use crate::{RandRangeU32, PCG32, PCG64};
use core::{char, fmt::Debug, hash::Hash, ops::*};

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

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

mod sealed {
  pub trait Sealed {}
  pub trait Serialize {}
  pub trait Deserialize<'a> {
    fn make_rust_happy() -> &'a str {
      ""
    }
  }
}
impl self::sealed::Sealed for PCG32 {}
impl self::sealed::Sealed for PCG64 {}

#[cfg(not(feature = "serde"))]
impl Serialize for PCG32 {}
#[cfg(not(feature = "serde"))]
impl Serialize for PCG64 {}
#[cfg(not(feature = "serde"))]
impl Serialize for u64 {}
#[cfg(not(feature = "serde"))]
impl Serialize for u128 {}
#[cfg(not(feature = "serde"))]
impl<'a> Deserialize<'a> for PCG32 {}
#[cfg(not(feature = "serde"))]
impl<'a> Deserialize<'a> for PCG64 {}
#[cfg(not(feature = "serde"))]
impl<'a> Deserialize<'a> for u64 {}
#[cfg(not(feature = "serde"))]
impl<'a> Deserialize<'a> for u128 {}

#[doc(hidden)]
pub trait PCG:
  self::sealed::Sealed
  + Sized
  + Eq
  + Hash
  + Debug
  + Clone
  + Default
  + Serialize
  + for<'a> Deserialize<'a>
{
  // Note(Evrey): This all could have been `: Integer`.
  type DoubleState: Copy
    + ShrAssign<u8>
    + Shl<u8, Output = Self::DoubleState>
    + BitAnd<Output = Self::DoubleState>
    + BitOrAssign
    + Sub<Output = Self::DoubleState>
    + Into<u128>
    + Debug
    + Eq
    + Hash
    + Default
    + Serialize
    + for<'a> Deserialize<'a>;
  // Note(Evrey): ^ Because Rust is drunk.

  const ONE: Self::DoubleState;
  const ZERO: Self::DoubleState;
  const SZOF: usize;

  fn next_wide(&mut self) -> Self::DoubleState;
}

impl PCG for PCG32 {
  type DoubleState = u64;

  const ONE: u64 = 1;
  const ZERO: u64 = 0;
  const SZOF: usize = 8;

  #[inline]
  fn next_wide(&mut self) -> u64 {
    u64::from(self.next_u32())
  }
}
impl PCG for PCG64 {
  type DoubleState = u128;

  const ONE: u128 = 1;
  const ZERO: u128 = 0;
  const SZOF: usize = 16;

  #[inline]
  fn next_wide(&mut self) -> u128 {
    u128::from(self.next_u64())
  }
}

/// A wrapper around PCG types that generates any-size outputs without wasting
/// random bits.
///
/// A PCG can be thought of as generating a pseudo-random bit stream, 32 bits at
/// a time for [PCG32], 64 bits for [PCG64], etc. Even if you currently just
/// need 8 bits of random data, you still get 32. That means, that to get a `u8`
/// out of a [PCG32], you end up throwing 24 bits away.
///
/// [AnyPCG] keeps all currently unused bits in a buffer. From a single
/// [PCG32::next_u32] call it can give you four `u8`s, two `u8`s and a `u16`, a
/// `u8` and a `char`, or other combinations. No bit is wasted. So [AnyPCG] can
/// be thought of as generating a pseudo-random bit stream for a variable amount
/// of bits at a time.
///
/// This "no waste" strategy comes with a mild added cost in random number
/// generation. It is up to you to decide what's more important: Generating a
/// lot of random numbers quickly, or making most out of your random bit stream.
/// In any case, only use this wrapper type if you often need random values of
/// bit sizes other than what the [PCG32] and [PCG64] naturally produce.
#[derive(Clone, Eq, PartialEq, Hash, Debug, Default)]
pub struct AnyPCG<T: PCG> {
  pcg: T,
  extracted: <T as PCG>::DoubleState,
  bits: u8, // not enough if PCG256, then do `u16`
}

impl<T: PCG> AnyPCG<T> {
  /// Creates a new any-size generator from a fixed-size one.
  #[inline]
  pub fn new(pcg: T) -> Self {
    // FIXME(Evrey): `const fn` if `#![feature(const_fn)]` for trait bounds
    // other than `Sized` is stable.
    Self {
      pcg,
      extracted: <T as PCG>::ZERO,
      bits: 0,
    }
  }

  /// Runs the generator once, if needed, and gets a `bool` as output.
  #[inline]
  pub fn next_bool(&mut self) -> bool {
    let next: u128 = self.next_bits(1).into();

    0 != (next as u8)
  }

  /// Runs the generator once, if needed, and gets a `char` as output.
  ///
  /// This function tries to use as few random bits as possible.
  ///
  /// There are 1112063, a little over a million, valid Unicode scalar
  /// values that could be generated. The largest valid scalar is
  /// `U+10FFFF`. The surrogate scalars in the middle from `U+D800` to
  /// `U+DFFF` are invalid.
  ///
  /// This amount of state is representable in roughly 20.0848 bits.
  /// Given that and rounding up, this function uses at least 21 random bits.
  /// If the generated bit pattern does not create a valid `char`, then
  /// the least significant bit will be discarded and a new most significant
  /// bit will be generated. This process is repeated until a valid bit
  /// pattern has been generated, wasting only one extra bit at a time.
  ///
  /// This function will always terminate eventually.
  #[inline]
  pub fn next_char(&mut self) -> char {
    // FIXME(Evrey): A way to not waste those 0.9152 bits?
    const LIMIT: u32 = 128;
    const SURR: u32 = 0xD800;
    const DIFF: u32 = 0xE000 - SURR;
    const MAX: u32 = (char::MAX as u32) - DIFF;
    const BITS: u8 = 21;
    const DIST: RandRangeU32 = RandRangeU32::new(0, MAX);
    const _ASSERT_MIN_BIT_USAGE: () =
      [(); 1][(((MAX > (1_u32 << (BITS - 1))) & (MAX <= (1_u32 << BITS))) as isize - 1) as usize];

    let bits: u128 = self.next_bits(BITS).into();
    let mut bits: u32 = bits as u32;

    for _ in 0..LIMIT {
      if let Some(c) = DIST.place_in_range(bits) {
        let c = if c >= SURR { c + DIFF } else { c };
        return char::from_u32(c).unwrap();
      }

      let bit = self.next_bool() as u32;

      bits = (bit << (BITS - 1)) | (bits >> 1);
    }

    // Guarantee this cannot hang.
    char::REPLACEMENT_CHARACTER
  }

  /// 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());
    }
    for byte_mut in i.into_remainder() {
      *byte_mut = self.next_u8();
    }
  }

  /// Runs the generator once, if needed, and gets a `u8` as output.
  #[inline]
  pub fn next_u8(&mut self) -> u8 {
    let next: u128 = self.next_bits(8).into();

    next as u8
  }

  /// Runs the generator once, if needed, and gets a `u16` as output.
  #[inline]
  pub fn next_u16(&mut self) -> u16 {
    let next: u128 = self.next_bits(16).into();

    next as u16
  }

  /// Runs the generator once, if needed, and gets a `u32` as output.
  #[inline]
  pub fn next_u32(&mut self) -> u32 {
    let next: u128 = self.next_bits(32).into();

    next as u32
  }

  const NEW_BITS: u8 = (4 * <T as PCG>::SZOF) as u8;
  const ONE: <T as PCG>::DoubleState = <T as PCG>::ONE;

  fn next_bits(&mut self, n_bits: u8) -> <T as PCG>::DoubleState {
    debug_assert!((n_bits > 0) & (n_bits <= Self::NEW_BITS));

    if n_bits > self.bits {
      self.extracted |= self.pcg.next_wide() << self.bits;
      self.bits = self.bits.wrapping_add(Self::NEW_BITS);
    }

    let mask = (Self::ONE << n_bits) - Self::ONE;
    let ret = self.extracted & mask;

    self.extracted >>= n_bits;
    self.bits -= n_bits;

    ret
  }
}
// FIXME(Evrey): and PCG128 etc. if there will ever be such things
impl AnyPCG<PCG64> {
  /// Runs the generator once, if needed, and gets a `u64` as output.
  #[inline]
  pub fn next_u64(&mut self) -> u64 {
    let next: u128 = self.next_bits(64);

    next as u64
  }

  /// Runs the generator one or two times and gets a `u128` as output.
  #[inline]
  pub fn next_u128(&mut self) -> u128 {
    let lo = u128::from(self.next_u64());
    let hi = u128::from(self.next_u64());

    lo | (hi << 64)
  }
}
impl AnyPCG<PCG32> {
  /// Runs the generator one or two times and gets a `u64` as output.
  #[inline]
  pub fn next_u64(&mut self) -> u64 {
    let lo = u64::from(self.next_u32());
    let hi = u64::from(self.next_u32());

    lo | (hi << 32)
  }

  /// Runs the generator two to four times and gets a `u128` as output.
  #[inline]
  pub fn next_u128(&mut self) -> u128 {
    let lo = u128::from(self.next_u64());
    let hi = u128::from(self.next_u64());

    lo | (hi << 64)
  }
}

// Note(Evrey): Own file?
#[cfg(feature = "serde")]
mod serde_impl {
  use super::{AnyPCG, PCG};
  use core::{fmt, marker::PhantomData};
  use serde::{
    de::{Error, MapAccess, SeqAccess, Unexpected, Visitor},
    ser::SerializeStruct,
    Deserialize, Deserializer, Serialize, Serializer,
  };

  const STRUCT_NAME: &str = "AnyPCG";
  const GENR_FIELD_NAME: &str = "generator";
  const EXTR_FIELD_NAME: &str = "extracted";
  const BITS_FIELD_NAME: &str = "num_bits";

  impl<T: PCG> Serialize for AnyPCG<T> {
    fn serialize<S>(&self, ser: S) -> Result<S::Ok, S::Error>
    where
      S: Serializer,
    {
      let mut s = ser.serialize_struct(STRUCT_NAME, 3)?;

      s.serialize_field(GENR_FIELD_NAME, &self.pcg)?;
      s.serialize_field(EXTR_FIELD_NAME, &self.extracted)?;
      s.serialize_field(BITS_FIELD_NAME, &self.bits)?;

      s.end()
    }
  }

  impl<'de, T: PCG> Deserialize<'de> for AnyPCG<T> {
    fn deserialize<D>(de: D) -> Result<Self, D::Error>
    where
      D: Deserializer<'de>,
    {
      de.deserialize_struct(
        STRUCT_NAME,
        &[GENR_FIELD_NAME, EXTR_FIELD_NAME, BITS_FIELD_NAME],
        AnyPcgVis(PhantomData),
      )
    }
  }

  #[derive(Deserialize)]
  #[serde(field_identifier)]
  #[allow(non_camel_case_types)]
  enum AnyPcgField {
    generator,
    extracted,
    num_bits,
  }

  struct AnyPcgVis<T: PCG>(PhantomData<T>);

  impl<'de, T: PCG> Visitor<'de> for AnyPcgVis<T> {
    type Value = AnyPCG<T>;

    fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
      f.write_str("struct AnyPCG")
    }

    fn visit_seq<V>(self, mut seq: V) -> Result<AnyPCG<T>, V::Error>
    where
      V: SeqAccess<'de>,
    {
      let genr = seq
        .next_element()?
        .ok_or_else(|| Error::invalid_length(0, &self))?;
      let extr = seq
        .next_element()?
        .ok_or_else(|| Error::invalid_length(1, &self))?;
      let bits = seq
        .next_element()?
        .ok_or_else(|| Error::invalid_length(2, &self))?;

      if (bits as usize) > (8 * <T as PCG>::SZOF) {
        return Err(Error::invalid_value(
          Unexpected::Unsigned(bits as u64),
          &"A number between 0 and the number of bits in `extracted`",
        ));
      }

      Ok(AnyPCG {
        pcg: genr,
        extracted: extr,
        bits,
      })
    }

    fn visit_map<V>(self, mut map: V) -> Result<AnyPCG<T>, V::Error>
    where
      V: MapAccess<'de>,
    {
      let mut genr = None;
      let mut extr = None;
      let mut bits = None;

      while let Some(key) = map.next_key()? {
        match key {
          AnyPcgField::generator => {
            if genr.is_some() {
              return Err(Error::duplicate_field(GENR_FIELD_NAME));
            }

            genr = Some(map.next_value()?);
          }

          AnyPcgField::extracted => {
            if extr.is_some() {
              return Err(Error::duplicate_field(EXTR_FIELD_NAME));
            }

            extr = Some(map.next_value()?);
          }

          AnyPcgField::num_bits => {
            if bits.is_some() {
              return Err(Error::duplicate_field(GENR_FIELD_NAME));
            }

            bits = Some(map.next_value()?);
          }
        }
      }

      let pcg = genr.ok_or_else(|| Error::missing_field(GENR_FIELD_NAME))?;
      let extracted = extr.ok_or_else(|| Error::missing_field(EXTR_FIELD_NAME))?;
      let bits = bits.ok_or_else(|| Error::missing_field(BITS_FIELD_NAME))?;

      if (bits as usize) > (8 * <T as PCG>::SZOF) {
        return Err(Error::invalid_value(
          Unexpected::Unsigned(bits as u64),
          &"A number between 0 and the number of bits in `extracted`",
        ));
      }

      Ok(AnyPCG {
        pcg,
        extracted,
        bits,
      })
    }
  }
}
#[cfg(feature = "serde")]
pub use self::serde_impl::*;