1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
//! Types for bounded randomization.
/// Allows sampling a `u32` number in `0 .. N`.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct BoundedRandU32 {
/// number of possible outputs. outputs will be in `0 .. count`
count: u32,
/// Multiplication threshold thing.
///
/// <https://arxiv.org/abs/1805.10941>
threshold: u32,
}
impl BoundedRandU32 {
#[allow(missing_docs)]
pub const _4: Self = Self::new(4);
#[allow(missing_docs)]
pub const _6: Self = Self::new(6);
#[allow(missing_docs)]
pub const _8: Self = Self::new(8);
#[allow(missing_docs)]
pub const _10: Self = Self::new(10);
#[allow(missing_docs)]
pub const _12: Self = Self::new(12);
#[allow(missing_docs)]
pub const _20: Self = Self::new(20);
/// Constructs a new value.
///
/// ## Panics
/// If the count is 0.
#[inline]
pub const fn new(count: u32) -> Self {
let threshold = count.wrapping_neg() % count;
Self { count, threshold }
}
/// Constructs a new value, or `None` on failure.
///
/// ## Failure
/// If the count is 0.
#[inline]
pub const fn try_new(count: u32) -> Option<Self> {
if count > 0 {
Some(Self::new(count))
} else {
None
}
}
/// The number of possible outputs.
#[inline]
pub const fn count(self) -> u32 {
self.count
}
/// Given a `u32`, try to place it into this bounded range.
///
/// ## Failure
/// * If the value is such that it doesn't fit evenly it is rejected.
#[inline]
pub const fn place_in_range(self, val: u32) -> Option<u32> {
let mul: u64 = (val as u64).wrapping_mul(self.count as u64);
let low_part: u32 = mul as u32;
if low_part < self.threshold {
None
} else {
debug_assert!(((mul >> 32) as u32) < self.count());
Some((mul >> 32) as u32)
}
}
/// Given a generator function, call it until
/// [`place_in_range`](Self::place_in_range) succeeds.
#[inline]
pub fn sample<F: FnMut() -> u32>(self, mut f: F) -> u32 {
loop {
if let Some(output) = self.place_in_range(f()) {
return output;
}
}
}
}
/// Allows sampling a `u16` number in `0 .. N`.
///
/// The primary advantage of this type over [BoundedRandU32] is that this type
/// samples using only 32-bit multiplications rather than 64-bit
/// multiplications, so on a 32-bit CPU this will perform much faster.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct BoundedRandU16 {
/// number of possible outputs. outputs will be in `0 .. count`
count: u16,
/// Multiplication threshold thing.
///
/// <https://arxiv.org/abs/1805.10941>
threshold: u16,
}
impl BoundedRandU16 {
#[allow(missing_docs)]
pub const _4: Self = Self::new(4);
#[allow(missing_docs)]
pub const _6: Self = Self::new(6);
#[allow(missing_docs)]
pub const _8: Self = Self::new(8);
#[allow(missing_docs)]
pub const _10: Self = Self::new(10);
#[allow(missing_docs)]
pub const _12: Self = Self::new(12);
#[allow(missing_docs)]
pub const _20: Self = Self::new(20);
/// Constructs a new value.
///
/// ## Panics
/// If the count is 0.
#[inline]
pub const fn new(count: u16) -> Self {
let threshold = count.wrapping_neg() % count;
Self { count, threshold }
}
/// Constructs a new value, or `None` on failure.
///
/// ## Failure
/// If the count is 0.
#[inline]
pub const fn try_new(count: u16) -> Option<Self> {
if count > 0 {
Some(Self::new(count))
} else {
None
}
}
/// The number of possible outputs.
#[inline]
pub const fn count(self) -> u16 {
self.count
}
/// Given a `u16`, try to place it into this bounded range.
///
/// ## Failure
/// * If the value is such that it doesn't fit evenly it is rejected.
#[inline]
pub const fn place_in_range(self, val: u16) -> Option<u16> {
let mul: u32 = (val as u32).wrapping_mul(self.count as u32);
let low_part: u16 = mul as u16;
if low_part < self.threshold {
None
} else {
debug_assert!(((mul >> 16) as u16) < self.count());
Some((mul >> 16) as u16)
}
}
/// Given a generator function, call it until
/// [`place_in_range`](Self::place_in_range) succeeds.
#[inline]
pub fn sample<F: FnMut() -> u16>(self, mut f: F) -> u16 {
loop {
if let Some(output) = self.place_in_range(f()) {
return output;
}
}
}
}