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        let mut item = core::mem::MaybeUninit::<Self>::uninit();
77        unsafe {
78            generator.fill_raw(item.as_mut_ptr().cast(), size_of::<Self>());
79            item.assume_init()
80        }
81    }
82}
83
84impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u8 {
85    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
86        u8::from_le_bytes(generator.generate::<[u8; 1]>())
87    }
88}
89
90impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i8 {
91    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
92        i8::from_le_bytes(generator.generate::<[u8; 1]>())
93    }
94}
95
96impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u32 {
97    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
98        u32::from_le_bytes(generator.generate::<[u8; 4]>())
99    }
100}
101
102impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i32 {
103    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
104        i32::from_le_bytes(generator.generate::<[u8; 4]>())
105    }
106}
107
108impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u64 {
109    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
110        u64::from_le_bytes(generator.generate::<[u8; 8]>())
111    }
112}
113
114impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i64 {
115    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
116        i64::from_le_bytes(generator.generate::<[u8; 8]>())
117    }
118}
119
120impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u128 {
121    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
122        generator.next()
123    }
124}
125
126impl<const A: u128, const C: u128> PRNConcreteGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i128 {
127    fn generate(generator: &mut GeneralLinearCongruentialGenerator128<A, C>) -> Self {
128        generator.generate::<u128>() as i128
129    }
130}
131
132
133impl<const A: u128, const C: u128> PRNGSerialize for GeneralLinearCongruentialGenerator128<A, C> {
134    type SerializeError = SerializeError;
135
136    type DeserializeError = DeserializeError;
137
138    const MAX_SERIALIZED_SIZE: usize = size_of::<u128>() + 4;
139
140    fn serialize(&self, buffer: &mut [u8]) -> Result<usize, Self::SerializeError> {
141        if buffer.len() < Self::MAX_SERIALIZED_SIZE {
142            return Err(SerializeError::BufferTooSmall);
143        }
144        buffer[0] = b'L';
145        buffer[1] = b'C';
146        buffer[2] = b'G';
147        let state = self.state.to_le_bytes();
148        buffer[3] = calculate_crc8(&state);
149        buffer[4..Self::MAX_SERIALIZED_SIZE].copy_from_slice(&state);
150        Ok(Self::MAX_SERIALIZED_SIZE)
151    }
152
153    fn deserialize(buffer: &[u8]) -> Result<DeserializationResult<Self>, Self::DeserializeError> {
154        if buffer.len() < Self::MAX_SERIALIZED_SIZE {
155            return Err(DeserializeError::BufferTooSmall);
156        }
157
158        if buffer[0..3] != [b'L', b'C', b'G'] {
159            return Err(DeserializeError::InvalidFormat);
160        }
161
162        let crc8_expected_value = buffer[3];
163
164        let mut data = [0u8; size_of::<u128>()];
165        data.copy_from_slice(&buffer[4..Self::MAX_SERIALIZED_SIZE]);
166        let crc8_value = calculate_crc8(&data);
167        if crc8_expected_value != crc8_value {
168            return Err(DeserializeError::InvalidFormat);
169        }
170
171        let state = u128::from_le_bytes(data);
172
173        let result = DeserializationResult {
174            read_bytes: Self::MAX_SERIALIZED_SIZE,
175            value: Self::with_seed(state),
176        };
177        Ok(result)
178    }
179}
180
181impl<const A: u128, const C: u128> Splittable for GeneralLinearCongruentialGenerator128<A, C> {
182    fn split(&mut self) -> Self {
183        let next = self.generate::<u64>();
184        Self::with_seed(next)
185    }
186}
187
188impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u32 {
189    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
190        generate_u32_in_range(generator, range)
191    }
192}
193
194impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for u64 {
195    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
196        generate_u64_in_range(generator, range)
197    }
198}
199
200impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i32 {
201    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
202        generate_i32_in_range(generator, range)
203    }
204}
205
206impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for i64 {
207    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
208        generate_i64_in_range(generator, range)
209    }
210}
211
212
213impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for f32 {
214    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
215        generate_f32_in_range(generator, range)
216    }
217}
218
219impl<const A: u128, const C: u128> PRNConcreteBoundedGenerator<GeneralLinearCongruentialGenerator128<A, C>> for f64 {
220    fn generate<TBounds: RangeBounds<Self>>(generator: &mut GeneralLinearCongruentialGenerator128<A, C>, range: TBounds) -> Self {
221        generate_f64_in_range(generator, range)
222    }
223}
224
225/// Alias for the default 128-bit [`GeneralLinearCongruentialGenerator128`]
226/// with carefully chosen `A` and `C`.
227/// 
228/// # Notes
229/// 
230/// The `A` multiplier is chosen based on "Computationally Easy, Spectrally
231/// Good Multipliers for Congruential Pseudorandom Number Generators" paper
232/// by Guy Steele & Sebastiano Vigna.
233/// 
234/// The `C` constant is a prime not dividing `A`, chosen based on
235/// "The Art of Computer Programming, Volume 2: Seminumerical Algorithms"
236/// by Donald E. Knuth.
237/// 
238/// With those parameters, and thanks to the internal state being 128-bit, the
239/// generator has a excelent statistical properties. And can be safely used
240/// in any simulation scenario. Note that it is not cryptographically secure.
241pub type LinearCongruentialGenerator128 = GeneralLinearCongruentialGenerator128<
242    0xdb36357734e34abb0050d0761fcdfc15,
243    0x86e9>;
osom_lib_prng/prngs/lcg.rs

osom_lib_prng/prngs/
lcg.rs
