1#![forbid(unsafe_code)]
2use 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum EntropyPoolError {
37 EmptyRange,
39 SampleTooLarge { sample: u32, population: u32 },
41 PopulationTooLarge { population: u32 },
44 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
66pub 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 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 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 pub fn random_bytes_read(&self) -> u64 {
107 self.count
108 }
109
110 pub fn retained_states(&self) -> u64 {
113 self.m
114 }
115
116 pub fn retained_entropy_bits(&self) -> f64 {
118 (self.m as f64).log2()
119 }
120
121 pub fn rng_mut(&mut self) -> &mut R {
123 &mut self.rng
124 }
125
126 pub fn into_rng(self) -> R {
128 self.rng
129 }
130
131 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 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 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 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 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 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 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}