osom_lib_prng/prngs/
lcg.rs

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

osom_lib_prng/prngs/
lcg.rs
