Skip to main content

entropy_pool/
lib.rs

1#![forbid(unsafe_code)]
2//! Entropy-efficient bounded random sampling.
3//!
4//! `EntropyPool` keeps an internal uniform state `(b, m)` and recycles the
5//! parts of that state that a bounded draw does not consume. This avoids modulo
6//! bias while allowing later draws to reuse residual entropy.
7//!
8//! # Example
9//!
10//! ```
11//! use entropy_pool::EntropyPool;
12//!
13//! let mut pool = EntropyPool::new();
14//!
15//! let value = pool.gen_range(6);
16//! assert!(value < 6);
17//!
18//! let permutation = pool.permutation(3, 10);
19//! assert_eq!(permutation.len(), 3);
20//!
21//! let combination = pool.combination(5, 20);
22//! assert_eq!(combination.len(), 5);
23//! ```
24
25use rand::{Rng, RngExt};
26use std::collections::BTreeSet;
27use std::error::Error;
28use std::fmt;
29use wabi_tree::OSBTreeSet;
30
31const BYTE_RADIX: u64 = 256;
32const REJECTION_BOUND: u64 = 1u64 << 32;
33
34/// Errors returned by the checked sampling methods.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum EntropyPoolError {
37    /// `gen_range` was asked to sample from an empty range.
38    EmptyRange,
39    /// The requested sample is larger than the population.
40    SampleTooLarge { sample: u32, population: u32 },
41    /// The requested population cannot be represented or allocated on this
42    /// platform.
43    PopulationTooLarge { population: u32 },
44    /// The byte counter overflowed.
45    ByteCountOverflow,
46}
47
48impl fmt::Display for EntropyPoolError {
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        match *self {
51            EntropyPoolError::EmptyRange => write!(f, "range size must be greater than zero"),
52            EntropyPoolError::SampleTooLarge { sample, population } => write!(
53                f,
54                "sample size {sample} is larger than population size {population}"
55            ),
56            EntropyPoolError::PopulationTooLarge { population } => {
57                write!(f, "population size {population} is too large")
58            }
59            EntropyPoolError::ByteCountOverflow => write!(f, "random byte counter overflowed"),
60        }
61    }
62}
63
64impl Error for EntropyPoolError {}
65
66/// A bounded sampler that reuses residual entropy between draws.
67///
68/// The default type parameter uses [`rand::rngs::ThreadRng`]. Use
69/// [`EntropyPool::with_rng`] to provide a deterministic or custom RNG.
70pub struct EntropyPool<R = rand::rngs::ThreadRng> {
71    rng: R,
72    b: u64,
73    m: u64,
74    count: u64,
75}
76
77impl EntropyPool<rand::rngs::ThreadRng> {
78    /// Creates a new pool backed by [`rand::rng()`].
79    pub fn new() -> Self {
80        Self::with_rng(rand::rng())
81    }
82}
83
84impl Default for EntropyPool<rand::rngs::ThreadRng> {
85    fn default() -> Self {
86        Self::new()
87    }
88}
89
90impl<R: Rng> EntropyPool<R> {
91    /// Creates a new pool backed by `rng`.
92    ///
93    /// The pool reads one random byte immediately so that its initial state is
94    /// uniform on `0..256`.
95    pub fn with_rng(mut rng: R) -> Self {
96        let b: u8 = rng.random();
97        EntropyPool {
98            rng,
99            b: u64::from(b),
100            m: BYTE_RADIX,
101            count: 1,
102        }
103    }
104
105    /// Returns the number of random bytes read from the backing RNG.
106    pub fn random_bytes_read(&self) -> u64 {
107        self.count
108    }
109
110    /// Returns the number of equiprobable states currently retained by the
111    /// pool.
112    pub fn retained_states(&self) -> u64 {
113        self.m
114    }
115
116    /// Returns `log2(retained_states())`.
117    pub fn retained_entropy_bits(&self) -> f64 {
118        (self.m as f64).log2()
119    }
120
121    /// Returns a mutable reference to the backing RNG.
122    pub fn rng_mut(&mut self) -> &mut R {
123        &mut self.rng
124    }
125
126    /// Consumes the pool and returns the backing RNG.
127    pub fn into_rng(self) -> R {
128        self.rng
129    }
130
131    /// Returns a uniform integer in `0..n`.
132    pub fn try_gen_range(&mut self, n: u32) -> Result<u32, EntropyPoolError> {
133        if n == 0 {
134            return Err(EntropyPoolError::EmptyRange);
135        }
136
137        let n = u64::from(n);
138        loop {
139            while (self.m % n) * REJECTION_BOUND >= self.m {
140                self.append_random_byte()?;
141            }
142
143            let r = self.m % n;
144            let q = self.m / n;
145            if self.b < self.m - r {
146                let b = self.b;
147                self.m = q;
148                self.b = b / n;
149                return Ok((b % n) as u32);
150            }
151
152            self.b = self.m - self.b - 1;
153            self.m = r;
154        }
155    }
156
157    /// Returns a uniform integer in `0..n`.
158    ///
159    /// Panics if `n == 0`. Use [`Self::try_gen_range`] to handle invalid input
160    /// without panicking.
161    pub fn gen_range(&mut self, n: u32) -> u32 {
162        self.try_gen_range(n)
163            .expect("entropy-pool gen_range precondition failed")
164    }
165
166    /// Returns `m` distinct values from `0..n` in random order.
167    pub fn try_permutation(&mut self, m: u32, n: u32) -> Result<Vec<u32>, EntropyPoolError> {
168        if m > n {
169            return Err(EntropyPoolError::SampleTooLarge {
170                sample: m,
171                population: n,
172            });
173        }
174        if m == 0 {
175            return Ok(Vec::new());
176        }
177
178        let take = usize::try_from(m)
179            .map_err(|_| EntropyPoolError::PopulationTooLarge { population: n })?;
180        let mut c = population_vec(n)?;
181        for i in 0..m {
182            let r = self.try_gen_range(n - i)? + i;
183            c.swap(i as usize, r as usize);
184        }
185        c.truncate(take);
186        Ok(c)
187    }
188
189    /// Returns `m` distinct values from `0..n` in random order.
190    ///
191    /// Panics if `m > n`. Use [`Self::try_permutation`] to handle invalid input
192    /// without panicking.
193    pub fn permutation(&mut self, m: u32, n: u32) -> Vec<u32> {
194        self.try_permutation(m, n)
195            .expect("entropy-pool permutation precondition failed")
196    }
197
198    /// Returns `m` distinct values from `0..n` as a sorted set.
199    pub fn try_combination(&mut self, m: u32, n: u32) -> Result<BTreeSet<u32>, EntropyPoolError> {
200        if m > n {
201            return Err(EntropyPoolError::SampleTooLarge {
202                sample: m,
203                population: n,
204            });
205        }
206        if m == 0 {
207            return Ok(BTreeSet::new());
208        }
209        if m == n {
210            return Ok(BTreeSet::from_iter(0..n));
211        }
212
213        let complement = m > n - m;
214        let sample_size = if complement { n - m } else { m };
215        let start = n - sample_size;
216        let mut selected = OSBTreeSet::new();
217
218        // Floyd's transition keeps no candidate ordering hidden from the
219        // returned set. This makes the recycled rank safe for the next round.
220        for j in start..n {
221            let t = self.try_gen_range(j + 1)?;
222            if !selected.insert(t) {
223                let inserted = selected.insert(j);
224                debug_assert!(inserted, "Floyd replacement should be new");
225            }
226
227            let rank = selected
228                .rank_of(&t)
229                .expect("the sampled value should remain in the set") as u32;
230            let radix = j - start + 1;
231            self.recycle(rank, radix);
232        }
233
234        if !complement {
235            Ok(BTreeSet::from_iter(selected))
236        } else {
237            let mut excluded = selected.into_iter().peekable();
238            let mut result = BTreeSet::new();
239            for value in 0..n {
240                if excluded.peek() == Some(&value) {
241                    excluded.next();
242                } else {
243                    result.insert(value);
244                }
245            }
246            Ok(result)
247        }
248    }
249
250    /// Returns `m` distinct values from `0..n` as a sorted set.
251    ///
252    /// Panics if `m > n`. Use [`Self::try_combination`] to handle invalid input
253    /// without panicking.
254    pub fn combination(&mut self, m: u32, n: u32) -> BTreeSet<u32> {
255        self.try_combination(m, n)
256            .expect("entropy-pool combination precondition failed")
257    }
258
259    fn append_random_byte(&mut self) -> Result<(), EntropyPoolError> {
260        let Some(next_m) = self.m.checked_mul(BYTE_RADIX) else {
261            return self.refill_full_width();
262        };
263        let next_count = self
264            .count
265            .checked_add(1)
266            .ok_or(EntropyPoolError::ByteCountOverflow)?;
267        let r: u8 = self.rng.random();
268
269        self.b = self.b * BYTE_RADIX + u64::from(r);
270        self.m = next_m;
271        self.count = next_count;
272        Ok(())
273    }
274
275    fn refill_full_width(&mut self) -> Result<(), EntropyPoolError> {
276        loop {
277            self.count = self
278                .count
279                .checked_add(8)
280                .ok_or(EntropyPoolError::ByteCountOverflow)?;
281            let b = self.rng.next_u64();
282            if b != u64::MAX {
283                self.b = b;
284                self.m = u64::MAX;
285                return Ok(());
286            }
287        }
288    }
289
290    fn recycle(&mut self, b: u32, m: u32) {
291        debug_assert!(m > 0);
292        debug_assert!(b < m);
293
294        let b = u64::from(b);
295        let m = u64::from(m);
296        if let Some(next_m) = self.m.checked_mul(m) {
297            self.b = self.b * m + b;
298            self.m = next_m;
299        } else {
300            self.b = b;
301            self.m = m;
302        }
303    }
304}
305
306fn population_vec(n: u32) -> Result<Vec<u32>, EntropyPoolError> {
307    let capacity =
308        usize::try_from(n).map_err(|_| EntropyPoolError::PopulationTooLarge { population: n })?;
309    let mut c = Vec::new();
310    c.try_reserve_exact(capacity)
311        .map_err(|_| EntropyPoolError::PopulationTooLarge { population: n })?;
312    c.extend(0..n);
313    Ok(c)
314}
315
316#[cfg(test)]
317mod tests {
318    use super::*;
319    use std::collections::BTreeMap;
320    use std::convert::Infallible;
321
322    #[derive(Clone)]
323    struct ByteRng {
324        next: u8,
325    }
326
327    impl ByteRng {
328        fn new(seed: u8) -> Self {
329            Self { next: seed }
330        }
331
332        fn next_byte(&mut self) -> u8 {
333            let byte = self.next;
334            self.next = self.next.wrapping_add(73);
335            byte
336        }
337    }
338
339    impl rand::TryRng for ByteRng {
340        type Error = Infallible;
341
342        fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
343            let mut bytes = [0; 4];
344            self.try_fill_bytes(&mut bytes)?;
345            Ok(u32::from_le_bytes(bytes))
346        }
347
348        fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
349            let mut bytes = [0; 8];
350            self.try_fill_bytes(&mut bytes)?;
351            Ok(u64::from_le_bytes(bytes))
352        }
353
354        fn try_fill_bytes(&mut self, dst: &mut [u8]) -> Result<(), Self::Error> {
355            for byte in dst {
356                *byte = self.next_byte();
357            }
358            Ok(())
359        }
360    }
361
362    fn pool_with_state(b: u64, m: u64) -> EntropyPool {
363        EntropyPool {
364            rng: rand::rng(),
365            b,
366            m,
367            count: 0,
368        }
369    }
370
371    fn log2_choose(n: u64, k: u64) -> f64 {
372        let k = k.min(n - k);
373        (1..=k)
374            .map(|i| ((n - k + i) as f64).log2() - (i as f64).log2())
375            .sum()
376    }
377
378    fn factorial(n: u32) -> u64 {
379        (1..=u64::from(n)).product()
380    }
381
382    fn exact_choose(n: u32, k: u32) -> u64 {
383        factorial(n) / (factorial(k) * factorial(n - k))
384    }
385
386    #[test]
387    fn custom_rng_makes_sampling_reproducible() {
388        let rng = ByteRng::new(17);
389        let mut a = EntropyPool::with_rng(rng.clone());
390        let mut b = EntropyPool::with_rng(rng);
391
392        assert_eq!(a.permutation(5, 20), b.permutation(5, 20));
393        assert_eq!(a.combination(4, 12), b.combination(4, 12));
394        assert_eq!(a.random_bytes_read(), b.random_bytes_read());
395        assert_eq!(a.retained_states(), b.retained_states());
396    }
397
398    #[test]
399    fn try_methods_report_invalid_arguments() {
400        let mut ep = EntropyPool::new();
401
402        assert_eq!(ep.try_gen_range(0), Err(EntropyPoolError::EmptyRange));
403        assert_eq!(
404            ep.try_permutation(3, 2),
405            Err(EntropyPoolError::SampleTooLarge {
406                sample: 3,
407                population: 2
408            })
409        );
410        assert_eq!(
411            ep.try_combination(3, 2),
412            Err(EntropyPoolError::SampleTooLarge {
413                sample: 3,
414                population: 2
415            })
416        );
417    }
418
419    #[test]
420    fn recycle_overflow_discards_old_pool_without_biasing_state() {
421        let mut ep = pool_with_state(0, u64::MAX);
422
423        ep.recycle(1, 2);
424
425        assert_eq!(ep.retained_states(), 2);
426        assert_eq!(ep.b, 1);
427        assert_eq!(ep.gen_range(2), 1);
428        assert_eq!(ep.retained_states(), 1);
429    }
430
431    #[test]
432    fn max_u32_range_uses_full_width_refill_without_u128() {
433        let mut ep = EntropyPool::with_rng(ByteRng::new(11));
434
435        let value = ep.gen_range(u32::MAX);
436
437        assert!(value < u32::MAX);
438        assert_eq!(ep.retained_states(), u64::from(u32::MAX) + 2);
439    }
440
441    #[test]
442    fn permutation_2_of_3_is_exactly_uniform_when_pool_has_6_states() {
443        let mut counts = BTreeMap::new();
444
445        for seed in 0..6 {
446            let mut ep = pool_with_state(seed, 6);
447            let permutation = ep.permutation(2, 3);
448
449            assert_eq!(
450                ep.random_bytes_read(),
451                0,
452                "seed {seed} should not need extra bytes"
453            );
454            assert_eq!(
455                ep.retained_states(),
456                1,
457                "seed {seed} should consume all entropy"
458            );
459            assert_eq!(ep.b, 0, "seed {seed} should leave the only residual state");
460            *counts.entry(permutation).or_insert(0) += 1;
461        }
462
463        assert_eq!(counts.len(), 6);
464        assert!(counts.values().all(|&count| count == 1), "{counts:#?}");
465    }
466
467    #[test]
468    fn combination_2_of_4_is_uniform_and_recycles_order_entropy() {
469        let mut observations = BTreeMap::new();
470
471        for seed in 0..12 {
472            let mut ep = pool_with_state(seed, 12);
473            let combination = Vec::from_iter(ep.combination(2, 4));
474
475            assert_eq!(
476                ep.random_bytes_read(),
477                0,
478                "seed {seed} should not need extra bytes"
479            );
480            assert_eq!(
481                ep.retained_states(),
482                2,
483                "seed {seed} should retain the discarded order bit"
484            );
485            assert!(ep.b < ep.m, "seed {seed} left invalid residual state");
486            observations
487                .entry(combination)
488                .or_insert_with(Vec::new)
489                .push(ep.b);
490        }
491
492        assert_eq!(observations.len(), 6);
493        for (combination, mut residuals) in observations {
494            residuals.sort_unstable();
495            assert_eq!(
496                residuals,
497                vec![0, 1],
498                "combination {combination:?} should appear once per recycled order state"
499            );
500        }
501    }
502
503    #[test]
504    fn combination_3_of_6_is_uniform_and_pool_independent() {
505        let mut observations = BTreeMap::new();
506
507        for seed in 0..120 {
508            let mut ep = pool_with_state(seed, 120);
509            let combination = Vec::from_iter(ep.combination(3, 6));
510
511            assert_eq!(
512                ep.random_bytes_read(),
513                0,
514                "seed {seed} should not need extra bytes"
515            );
516            assert_eq!(
517                ep.retained_states(),
518                6,
519                "seed {seed} should retain all six ordering states"
520            );
521            observations
522                .entry(combination)
523                .or_insert_with(Vec::new)
524                .push(ep.b);
525        }
526
527        assert_eq!(observations.len(), 20);
528        for (combination, mut residuals) in observations {
529            residuals.sort_unstable();
530            assert_eq!(
531                residuals,
532                Vec::from_iter(0..6),
533                "combination {combination:?} should be independent of the residual pool"
534            );
535        }
536    }
537
538    #[test]
539    fn all_combinations_up_to_8_form_an_exact_output_pool_product() {
540        for n in 0..=8 {
541            let input_states = factorial(n);
542
543            for m in 0..=n {
544                let expected_outputs = exact_choose(n, m);
545                let expected_residual_states = factorial(m) * factorial(n - m);
546                let mut output_counts = BTreeMap::new();
547                let mut output_pool_pairs = BTreeSet::new();
548
549                for seed in 0..input_states {
550                    let mut ep = pool_with_state(seed, input_states);
551                    let combination = Vec::from_iter(ep.combination(m, n));
552
553                    assert_eq!(
554                        ep.random_bytes_read(),
555                        0,
556                        "combination({m}, {n}), seed {seed} unexpectedly read random bytes"
557                    );
558                    assert_eq!(
559                        ep.retained_states(),
560                        expected_residual_states,
561                        "combination({m}, {n}), seed {seed} retained the wrong state count"
562                    );
563                    assert!(
564                        output_pool_pairs.insert((combination.clone(), ep.b)),
565                        "combination({m}, {n}), seed {seed} duplicated an output-pool pair"
566                    );
567                    *output_counts.entry(combination).or_insert(0_u64) += 1;
568                }
569
570                assert_eq!(output_counts.len() as u64, expected_outputs);
571                assert!(
572                    output_counts
573                        .values()
574                        .all(|&count| count == expected_residual_states),
575                    "combination({m}, {n}) was not exactly uniform: {output_counts:#?}"
576                );
577                assert_eq!(output_pool_pairs.len() as u64, input_states);
578            }
579        }
580    }
581
582    #[test]
583    fn combination_handles_edges_and_complements() {
584        let mut ep = EntropyPool::new();
585
586        assert_eq!(ep.combination(0, 10), BTreeSet::new());
587        assert_eq!(
588            ep.combination(10, 10),
589            BTreeSet::from_iter(0..10),
590            "selecting the full population should return every item"
591        );
592
593        for (m, n) in [(1, 10), (3, 10), (7, 10), (9, 10)] {
594            let combination = ep.combination(m, n);
595            assert_eq!(combination.len(), m as usize);
596            assert!(
597                combination.iter().all(|&value| value < n),
598                "combination({m}, {n}) returned an out-of-range value: {combination:?}"
599            );
600        }
601    }
602
603    #[test]
604    fn large_combination_uses_entropy_near_the_binomial_limit() {
605        let selected: u32 = 20_000;
606        let population: u32 = 30_000;
607        let mut ep = EntropyPool::new();
608
609        let combination = ep.combination(selected, population);
610        let minimum_bits = log2_choose(u64::from(population), u64::from(selected));
611        let consumed_bits = ep.random_bytes_read() as f64 * 8.0;
612        let retained_bits = ep.retained_entropy_bits();
613        let output_efficiency = minimum_bits / consumed_bits;
614        let retained_efficiency = (minimum_bits + retained_bits) / consumed_bits;
615
616        assert_eq!(combination.len(), selected as usize);
617        assert!(combination.iter().all(|&value| value < population));
618        println!(
619            "combination({selected}, {population}): lower_bound={minimum_bits:.2} bits, \
620             retained={retained_bits:.2} bits, consumed={consumed_bits:.0} bits \
621             ({} bytes), output_efficiency={:.4}%, retained_efficiency={:.4}%",
622            ep.random_bytes_read(),
623            output_efficiency * 100.0,
624            retained_efficiency * 100.0
625        );
626
627        assert!(
628            output_efficiency > 0.995,
629            "entropy efficiency was {:.4}%, lower_bound={minimum_bits:.2}, consumed={consumed_bits:.0}",
630            output_efficiency * 100.0
631        );
632    }
633}