entropy-pool 1.0.0

A simple entropy pool
Documentation
  • Coverage
  • 86.96%
    20 out of 23 items documented1 out of 16 items with examples
  • Size
  • Source code size: 110.5 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 336.1 kB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 3s Average build duration of successful builds.
  • all releases: 11s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • yingqi-z20/entropy-pool
    1 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • yingqi-z20

entropy-pool

entropy-pool is a small Rust crate for drawing bounded random values, partial permutations, and combinations while keeping unused randomness in an internal entropy pool.

The main idea is simple: every random byte that is read expands an internal uniform state space. When a draw cannot use that space exactly, the leftover states are not thrown away. They are mapped back into the pool and reused by later draws.

Example

use entropy_pool::EntropyPool;

let mut pool = EntropyPool::new();

// Uniform value in 0..6.
let die_roll = pool.gen_range(6) + 1;

// Three distinct values from 0..10, in random order.
let sample = pool.permutation(3, 10);

// Five distinct values from 0..20, returned as a sorted BTreeSet.
let chosen = pool.combination(5, 20);

API

EntropyPool::new()

Creates a new pool backed by rand::rng(). The pool starts by reading one random byte.

EntropyPool::with_rng(rng)

Creates a new pool backed by a caller-provided RNG implementing rand::Rng. This is useful for deterministic tests, seeded generators, or specialized randomness sources.

gen_range(n: u32) -> u32

Returns a uniform integer in 0..n.

Panics if n == 0.

Use try_gen_range(n) to get Result<u32, EntropyPoolError> instead.

permutation(m: u32, n: u32) -> Vec<u32>

Returns m distinct values from 0..n in random order.

This is a partial Fisher-Yates shuffle driven by gen_range.

Panics if m > n.

Use try_permutation(m, n) to get Result<Vec<u32>, EntropyPoolError> instead.

combination(m: u32, n: u32) -> BTreeSet<u32>

Returns m distinct values from 0..n as a sorted set.

The implementation uses Floyd's sampling algorithm with online rank recycling. It performs min(m, n - m) bounded draws and keeps only the sampled set, using O(min(m, n - m)) auxiliary space. For large selections it samples the smaller excluded set and returns the complement.

Panics if m > n.

Use try_combination(m, n) to get Result<BTreeSet<u32>, EntropyPoolError> instead.

Statistics

random_bytes_read() returns how many bytes have been read from the backing RNG. retained_states() returns the current pool radix m, and retained_entropy_bits() returns log2(m).

How The Entropy Pool Works

The pool stores a pair (b, m) with this invariant:

b is uniformly distributed in 0..m

To draw a value in 0..n, the algorithm writes:

m = q * n + r

If b falls in the first q * n states, the draw is exact:

output = b % n
new_pool = (b / n, q)

If b falls in the remaining r states, those rejected states are converted back into a uniform state in 0..r and the draw continues. Before each trial, the pool is expanded until the rejection probability is below 2^-32. While the internal u64 state can hold the expanded radix, this appends one byte:

new_b = old_b * 256 + random_byte
new_m = old_m * 256

If another byte would overflow the u64 radix and the rejection bound is still not met, the implementation discards the old retained state and refills the pool with a full-width uniform state on 0..u64::MAX.

This is a byte-oriented entropy recycling method: modulo bias is avoided, but the rejection branch keeps the unused entropy instead of discarding it.

Mathematical Proof

Write [k] for the set {0, 1, ..., k - 1}. The panicking methods require the documented preconditions; the try_* methods report invalid arguments with EntropyPoolError.

Entropy-pool invariant

At every public draw boundary, the pool state (B, M) satisfies:

B is uniform on [M].

Future bytes produced by rand::rng() are independent of B.

When the implementation appends one random byte U, where U is uniform on [256], it replaces:

B' = 256B + U
M' = 256M

The map

(B, U) -> 256B + U

is a bijection from [M] x [256] to [256M]. Therefore B' is uniform on [M'], so appending bytes preserves the invariant.

If appending another byte would overflow the internal u64 radix, the implementation may instead draw a u64 value X until X != u64::MAX, then store:

B' = X
M' = u64::MAX

Conditioned on X != u64::MAX, X is uniform on [u64::MAX]. This full-width refill discards older retained entropy, but it preserves the invariant and keeps the u32 range sampler on fast u64 arithmetic.

Correctness of gen_range

Let the current pool state be (B, M), with B uniform on [M]. For a requested range size n > 0, write:

M = qn + r, 0 <= r < n.

The algorithm accepts when:

B < qn.

On the accepted set [qn], define:

Y = B mod n
C = floor(B / n)

The map

B -> (Y, C)

is a bijection from [qn] to [n] x [q], with inverse:

(Y, C) -> Cn + Y.

Conditioned on acceptance, B is uniform on [qn]; by the bijection, (Y, C) is uniform on [n] x [q]. Hence:

  • Y is uniform on [n];
  • C is uniform on [q];
  • Y and C are independent.

The implementation returns Y and stores (C, q) as the new pool state, so the returned value is unbiased and the pool invariant is preserved.

If the algorithm rejects, then B lies in:

{qn, qn + 1, ..., M - 1},

which has size r. The implementation stores:

D = M - B - 1

and M = r. The map B -> D is a bijection from the rejected set to [r]. Conditioned on rejection, D is therefore uniform on [r], so the pool invariant is again preserved and the loop can retry. No modulo-biased value is ever returned.

The byte-extension loop is separate from the acceptance bijection above: it ensures there is an accepted region and bounds the rejection probability. Once the loop condition is false:

2^32 * (M mod n) < M,

so the next trial rejects with probability:

r / M < 2^-32.

Thus, within the finite-size limits of this implementation, repeated rejection has probability zero in the ideal random-byte model.

Correctness of permutation

permutation(m, n) is a partial Fisher-Yates shuffle. At step i, the suffix before i is already fixed, and the array positions i..n contain exactly the remaining n - i items. The call:

gen_range(n - i) + i

chooses one of those remaining positions uniformly, and the swap moves that chosen item into position i.

By the gen_range proof, each choice is uniform and leaves a pool state independent of the chosen index. Therefore the probability of any ordered m-tuple of distinct values is:

1 / n * 1 / (n - 1) * ... * 1 / (n - m + 1)
= 1 / P(n, m),

where:

P(n, m) = n! / (n - m)!.

So permutation(m, n) is uniform over all ordered length-m samples without replacement.

Correctness of recycle

Suppose the current pool state is (B, M), with B uniform on [M]. Suppose D is independent of B and uniform on [d]. recycle(D, d) stores:

B' = Bd + D
M' = Md

The map:

(B, D) -> Bd + D

is a bijection from [M] x [d] to [Md]. Therefore B' is uniform on [M']. So, when Md fits in the internal u64 state, recycling an independent base-d digit preserves the pool invariant while adding exactly log2(d) bits of state space.

If Md would overflow u64, the implementation discards the older retained state and stores only:

B' = D
M' = d

Since D is uniform on [d], the pool invariant is still preserved. This fallback can lose retained entropy, but it cannot bias future outputs.

Correctness of combination

Let k be the number of items actually sampled:

k = min(m, n - m).

The implementation applies Floyd's transition. Starting with the empty set S, for:

j = n-k, n-k+1, ..., n-1

it draws T uniformly from [j+1] and updates:

if T is in S:  S' = S union {j}
otherwise:    S' = S union {T}

In both branches T belongs to S'. If the new set has size r, the implementation recycles:

D = rank of T inside S',    D in [r].

The important detail is that a collision inserts j, but the recycled digit is the rank of the original draw T, not the rank of j.

We prove the following invariant after round r: S' is uniform over the r-subsets of [j+1], and the entropy-pool state is uniform and independent of S'.

Before round r, assume S is a uniform (r-1)-subset of [j]. The pool is independent of S, and gen_range(j+1) returns a uniform T while leaving a pool state independent of (S, T). Consider the transition:

(S, T) -> (S', D).

It has the following explicit inverse. Given an r-subset S' of [j+1] and D in [r], let T be the D-th smallest element of S', then set:

if j is in S':  S = S' without j
otherwise:      S = S' without T

If j is absent, T was not in S and the non-collision branch inserted it. If j is present, removing j reconstructs the old set: either T = j was inserted directly, or T was already present and caused the collision. Thus the inverse is valid and unique in every case, so the transition is a bijection. Equivalently:

C(j, r-1) * (j+1) = C(j+1, r) * r.

Because (S, T) is uniform over the left-hand side, (S', D) is uniform over the Cartesian product on the right. Consequently S' is uniform, D is uniform on [r], and they are independent. The residual pool was already independent of (S', D), so:

recycle(D, r)

preserves a uniform pool independent of S'. This completes the induction. There is no hidden candidate ordering in Floyd's algorithm: the complete state that affects the next round is the set S' covered by the invariant. This is essential. A Fisher-Yates candidate array can be correlated with a recycled rank even when the final rank tuple is independent of the final set, so the global ordered-sample bijection alone is not sufficient for online recycling.

The recycle multiplication in this loop cannot overflow. If the working radix immediately before the successful gen_range(j+1) split is M_work, the residual radix is floor(M_work / (j+1)). Multiplying it by r <= j+1 cannot exceed M_work <= u64::MAX.

Across all k rounds:

product of draw radices     = (n-k+1) * ... * n = P(n, k)
product of recycled radices = 1 * 2 * ... * k   = k!

Since P(n, k) = C(n, k) * k!, the returned set accounts for exactly log2 C(n, k) bits and the recycled ranks account for exactly log2(k!) bits.

When the requested m is larger than n / 2, the implementation samples the excluded set of size n - m and returns its complement. The complement map is a bijection between (n - m)-subsets and m-subsets, so uniformity is preserved. The pool is independent of the excluded set and therefore also independent of its complement.

Entropy lower bound

Any exact sampler for m elements from n must produce one of:

C(n, m)

outputs uniformly. Thus the output itself contains:

log2 C(n, m)

bits of entropy. The tests compare this information-theoretic lower bound with the number of random bytes actually read. For a pool state (B, M), the remaining reusable entropy is:

log2 M.

So the useful entropy after a combination draw is measured as:

log2 C(n, m) + log2 M.

divided by the consumed random bits. Values close to 1 mean the consumed randomness has been converted almost entirely into either the returned combination or reusable pool state.

Correctness And Entropy Tests

Run the test suite with:

cargo test -- --nocapture

The tests include:

  • deterministic custom-RNG sampling;
  • checked error handling for invalid arguments;
  • u64 recycle-overflow fallback;
  • exhaustive uniformity for permutation(2, 3);
  • exhaustive uniformity for combination(2, 4);
  • verification that combination(2, 4) recycles the discarded order bit;
  • the combination(3, 6) regression that detects feedback from a hidden candidate ordering;
  • exhaustive output/pool independence for every combination with n <= 8;
  • edge cases for empty, full, direct, and complement combinations;
  • a large entropy-utilization check against the binomial lower bound.

Example output from the large test:

combination(20000, 30000): lower_bound=27541.20 bits, retained=50.80 bits,
consumed=27592 bits (3449 bytes), output_efficiency=99.8159%,
retained_efficiency=100.0000%

The exact byte count can vary with random rejection paths, but the test asserts that output entropy stays above 99.5% of the information-theoretic lower bound. When retained pool entropy is included, the accounting should be very close to 100%.

Notes

  • The default pool uses ThreadRng, but EntropyPool::with_rng accepts any rand::Rng.
  • Public sampling APIs use u32 ranges and the internal pool state is u64. This keeps the hot path on native-width arithmetic. If expansion or recycling cannot keep older retained entropy inside u64, the implementation keeps correctness by discarding that older retained entropy.
  • permutation builds a Vec<u32> for the whole population. combination keeps an order-statistics set of size min(m, n - m) and therefore uses O(min(m, n - m)) auxiliary space, excluding the returned set.
  • The non-try_* methods are convenience wrappers that panic on invalid arguments. Use the checked methods for library-facing error handling.

License

AGPL-3.0-only