osom_lib_prng/prngs/
lcg.rs

1#![allow(
2    clippy::cast_possible_truncation,
3    clippy::cast_possible_wrap,
4)]
5
6use core::{convert::Infallible, ops::RangeBounds};
7
8use osom_lib_reprc::macros::reprc;
9use osom_lib_try_clone::TryClone;
10
11use crate::{
12    errors::{DeserializeError, SerializeError},
13    prngs::helpers::{
14        calculate_crc8, fill_raw_from_array_generator, generate_f32_in_range, generate_f64_in_range,
15        generate_i32_in_range, generate_i64_in_range, generate_u32_in_range, generate_u64_in_range
16    },
17    traits::{
18        DeserializationResult, PRNConcreteBoundedGenerator, PRNConcreteGenerator, PRNGSerialize, PRNGenerator, Seedable, Splittable
19    }
20};
21
22/// The general linear congruential generator. Internally it holds
23/// `u128` state and follows the `next_state = A*old_state + C` formula
24/// (over 128-bit modulo arithmetic).
25/// 
26/// Additionally all LCGs implement [`Splittable`] through an ad-hoc method.
27/// However users should be warned that statistical properties of this method
28/// are barely verified.
29#[derive(Debug, PartialEq, Eq, Clone, Copy)]
30#[reprc]
31#[repr(transparent)]
32#[must_use]
33pub struct GeneralLinearCongruentialGenerator128<const A: u128, const C: u128> {
34    state: u128,
35}
36
37impl<const A: u128, const C: u128> TryClone for GeneralLinearCongruentialGenerator128<A, C> {
38    type Error = Infallible;
39
40    fn try_clone(&self) -> Result<Self, Self::Error> {
41        Ok(*self)
42    }
43}
44
45impl<const A: u128, const C: u128> GeneralLinearCongruentialGenerator128<A, C> {
46    /// Generates a new pseudo-random `u128` value.
47    #[inline(always)]
48    pub const fn next(&mut self) -> u128 {
49        let new_value = self.state.wrapping_mul(A).wrapping_add(C);
50        self.state = new_value;
51        new_value
52    }
53}
54
55impl<const A: u128, const C: u128> Seedable<u128> for GeneralLinearCongruentialGenerator128<A, C> {
56    fn with_seed(seed: u128) -> Self {
57        let state = core::hint::select_unpredictable(seed != 0, seed, 1);
58        Self { state }
59    }
60}
61
62impl<const A: u128, const C: u128> Seedable<u64> for GeneralLinearCongruentialGenerator128<A, C> {
63    fn with_seed(seed: u64) -> Self {
64        let mut splitmix = crate::prngs::SplitMix64::with_seed(seed);
65        let upper = u128::from(splitmix.next());
66        let lower = u128::from(splitmix.next());
67        Self::with_seed((upper << 64) + lower)
68    }
69}
70
71impl<const A: u128, const C: u128> PRNGenerator for GeneralLinearCongruentialGenerator128<A, C> {
72    unsafe fn fill_raw(&mut self, dst_ptr: *mut u8, dst_len: usize) {
73        fill_raw_from_array_generator(|| self.next().to_le_bytes(), dst_ptr, dst_len);
74    }
75}
76
77impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for bool {
78    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
79        (generator.next() & 1) == 1
80    }
81}
82
83impl<const N: usize, const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for [u8; N] {
84    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
85        if N == 0 {
86            return [0u8; N];
87        }
88        let mut item = core::mem::MaybeUninit::<Self>::uninit();
89        unsafe {
90            generator.fill_raw(item.as_mut_ptr().cast(), size_of::<Self>());
91            item.assume_init()
92        }
93    }
94}
95
96impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u8 {
97    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
98        u8::from_le_bytes(generator.generate::<[u8; 1]>())
99    }
100}
101
102impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i8 {
103    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
104        i8::from_le_bytes(generator.generate::<[u8; 1]>())
105    }
106}
107
108impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u32 {
109    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
110        u32::from_le_bytes(generator.generate::<[u8; 4]>())
111    }
112}
113
114impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i32 {
115    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
116        i32::from_le_bytes(generator.generate::<[u8; 4]>())
117    }
118}
119
120impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u64 {
121    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
122        u64::from_le_bytes(generator.generate::<[u8; 8]>())
123    }
124}
125
126impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i64 {
127    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
128        i64::from_le_bytes(generator.generate::<[u8; 8]>())
129    }
130}
131
132impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u128 {
133    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
134        generator.next()
135    }
136}
137
138impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i128 {
139    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
140        generator.generate::<u128>() as i128
141    }
142}
143
144
145impl<const A: u128, const C: u128> PRNGSerialize for GeneralLinearCongruentialGenerator128<A, C> {
146    type SerializeError = SerializeError;
147
148    type DeserializeError = DeserializeError;
149
150    const MAX_SERIALIZED_SIZE: usize = size_of::<u128>() + 4;
151
152    fn serialize(&self, buffer: &mut [u8]) -> Result<usize, Self::SerializeError> {
153        if buffer.len() < Self::MAX_SERIALIZED_SIZE {
154            return Err(SerializeError::BufferTooSmall);
155        }
156        buffer[0] = b'L';
157        buffer[1] = b'C';
158        buffer[2] = b'G';
159        let state = self.state.to_le_bytes();
160        buffer[3] = calculate_crc8(&state);
161        buffer[4..Self::MAX_SERIALIZED_SIZE].copy_from_slice(&state);
162        Ok(Self::MAX_SERIALIZED_SIZE)
163    }
164
165    fn deserialize(buffer: &[u8]) -> Result<DeserializationResult<Self>, Self::DeserializeError> {
166        if buffer.len() < Self::MAX_SERIALIZED_SIZE {
167            return Err(DeserializeError::BufferTooSmall);
168        }
169
170        if buffer[0..3] != [b'L', b'C', b'G'] {
171            return Err(DeserializeError::InvalidFormat);
172        }
173
174        let crc8_expected_value = buffer[3];
175
176        let mut data = [0u8; size_of::<u128>()];
177        data.copy_from_slice(&buffer[4..Self::MAX_SERIALIZED_SIZE]);
178        let crc8_value = calculate_crc8(&data);
179        if crc8_expected_value != crc8_value {
180            return Err(DeserializeError::InvalidFormat);
181        }
182
183        let state = u128::from_le_bytes(data);
184
185        let result = DeserializationResult {
186            read_bytes: Self::MAX_SERIALIZED_SIZE,
187            value: Self::with_seed(state),
188        };
189        Ok(result)
190    }
191}
192
193impl<const A: u128, const C: u128> Splittable for GeneralLinearCongruentialGenerator128<A, C> {
194    fn split(&mut self) -> Self {
195        let next = self.generate::<u64>();
196        Self::with_seed(next)
197    }
198}
199
200impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u32 {
201    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
202        generate_u32_in_range(generator, range)
203    }
204}
205
206impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u64 {
207    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
208        generate_u64_in_range(generator, range)
209    }
210}
211
212impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i32 {
213    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
214        generate_i32_in_range(generator, range)
215    }
216}
217
218impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i64 {
219    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
220        generate_i64_in_range(generator, range)
221    }
222}
223
224
225impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for f32 {
226    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
227        generate_f32_in_range(generator, range)
228    }
229}
230
231impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for f64 {
232    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
233        generate_f64_in_range(generator, range)
234    }
235}
236
237/// Alias for the default 128-bit [`GeneralLinearCongruentialGenerator128`]
238/// with carefully chosen `A` and `C`.
239/// 
240/// # Notes
241/// 
242/// The `A` multiplier is chosen based on "Computationally Easy, Spectrally
243/// Good Multipliers for Congruential Pseudorandom Number Generators" paper
244/// by Guy Steele & Sebastiano Vigna.
245/// 
246/// The `C` constant is a prime not dividing `A`, chosen based on
247/// "The Art of Computer Programming, Volume 2: Seminumerical Algorithms"
248/// by Donald E. Knuth.
249/// 
250/// With those parameters, and thanks to the internal state being 128-bit, the
251/// generator has a excellent statistical properties. And can be safely used
252/// in any simulation scenario. Note that it is not cryptographically secure.
253pub type LinearCongruentialGenerator128 = GeneralLinearCongruentialGenerator128<
254    0xdb36357734e34abb0050d0761fcdfc15,
255    0x86e9>;
osom_lib_prng/prngs/lcg.rs

osom_lib_prng/prngs/
lcg.rs
