Skip to main content

consistent_choose_k/
consistent_permutation.rs

1//! Per-key consistent permutation iterator over `0..n`, driven by an
2//! independently-keyed Feistel network per layer (2 bits per layer).
3//!
4//! Given a 64-bit `seed` and a universe size `n`, the iterator emits
5//! each integer in `0..n` exactly once in a key-dependent order. The
6//! sequence is `n`-consistent: when `n` grows by one, the new sequence
7//! agrees with the old except for the at most one position where the
8//! new element is inserted.
9//!
10//! # Layered design
11//!
12//! Each layer `j` is a Feistel bijection on `[0, 2^(2j + 2))`. After
13//! one Feistel pass we look at the **top two bits** of the output:
14//!
15//! * `00` (one quadrant) → descend to layer `j - 1` (or, at the
16//!   bottom layer, the output is `0` itself, which we emit).
17//! * `01` / `10` / `11` (three quadrants) → emit the raw value
18//!   (subject to the `< n` range check).
19//!
20//! So every layer-`j` call has a `3/4` chance of producing an emission,
21//! versus `1/2` in a one-bit-per-layer scheme. That cuts both the
22//! number of layers (`j_max ≈ ⌈log₂(n)/2⌉ - 1`) and the expected
23//! number of `layer_apply` calls per emission (from `≈ 2` to `≈ 4/3`).
24//! Even `n_bits` also means the Feistel never needs cycle-walking.
25//!
26//! See [`docs/permutation-design.md`] in the crate for the full
27//! design rationale, including why an independently-keyed per-layer
28//! Feistel network beats the (now removed) chunk-prefix-permutation
29//! approach on choose-2 set uniformity at small `n` while staying
30//! cheaper than multi-round PCG.
31//!
32//! [`docs/permutation-design.md`]: ../../docs/permutation-design.md
33//!
34//! # Round-count policy
35//!
36//! The number of Feistel rounds is chosen automatically per layer as a
37//! function of `n_bits` (see [`rounds_for_n_bits`]). Small layers have
38//! a tiny F-function input space (`2^half_bits` distinct values),
39//! which limits the per-round permutation family; they compensate with
40//! extra rounds. Large layers already see a wide F input and reach the
41//! random-perm floor with `4` rounds. Conveniently the small layers
42//! are called rarely (level `j` contributes `≈ 4^j` emissions), so the
43//! extra rounds there are essentially free, while the top layer —
44//! which dominates per-iterator cost — uses the fewest rounds.
45//!
46//! # Iterator
47//!
48//! Start at the top layer `j_max` and walk its counter. If the top
49//! two bits are `00`, descend one layer (and walk *that* layer's
50//! counter on the next step); otherwise emit. The iterator stops once
51//! it has emitted `n` values.
52
53/// Smallest Feistel round count we trust to deliver near-random-perm
54/// statistics for a layer of width `n_bits`, based on the
55/// `statistical_comparison` chi² experiments. Tiny layers
56/// (`n_bits = 2`) have a F-input space of only 2 values and need
57/// many rounds; large layers reach the floor with 4 rounds.
58pub(crate) fn rounds_for_n_bits(n_bits: u32) -> usize {
59    match n_bits {
60        2 => 12,
61        4 => 10,
62        6 => 6,
63        _ => 4,
64    }
65}
66
67/// SplitMix64 — strong per-bit avalanche, useful as a seed
68/// pre-mixer for callers that only have a low-entropy seed.
69#[cfg(test)]
70#[inline]
71fn splitmix64(seed: u64) -> u64 {
72    let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
73    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
74    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
75    z ^ (z >> 31)
76}
77
78/// Apply the per-layer Feistel bijection on `[0, 2^n_bits)`.
79/// `master_key` must be well-avalanched: two near-identical keys
80/// will yield two highly correlated permutations.
81///
82/// All per-layer geometry (`half_bits`, mask, round count) is derived
83/// from `n_bits` on each call. `n_bits` is small (≤ 32) and the
84/// constants are a handful of trivial bit ops, so this stays well off
85/// the hot path of the Feistel loop itself.
86///
87/// `n_bits` must be **even** and in `2..=30`.
88#[inline]
89pub(crate) fn layer_apply(n_bits: u32, master_key: u64, x: u32) -> u32 {
90    debug_assert!((2..=30).contains(&n_bits) && n_bits.is_multiple_of(2));
91    let rounds = rounds_for_n_bits(n_bits) as u32;
92    let half_bits = n_bits / 2;
93    let half_mask = (1u32 << half_bits) - 1;
94    let n_mask = (1u32 << n_bits) - 1;
95    let shift = 2 * half_bits;
96
97    debug_assert!(x <= n_mask, "input out of range");
98    let mut l = (x >> half_bits) & half_mask;
99    let mut r = x & half_mask;
100    let mut k = master_key;
101    for _ in 0..rounds {
102        // Split each 64-bit (rotated) master into two *independent*
103        // 32-bit sub-keys: the low half is an additive offset, the
104        // high half (forced odd) is the multiplier. Higher bits stay
105        // set on purpose — they contribute via the multiplicative
106        // mix.
107        let k_xor = k & 0xFFFF_FFFF;
108        let k_mul = (k >> 32) | 1;
109        let mixed = ((r as u64) ^ k_xor).wrapping_mul(k_mul);
110        let f = (mixed as u32).wrapping_add((mixed >> 32) as u32) & half_mask;
111        let new_l = r;
112        let new_r = l ^ f;
113        l = new_l;
114        r = new_r;
115        // Rotate the master key by exactly the per-round "consumed"
116        // bit count so that each round sees a fresh slice of the
117        // master in its low positions, plus a Weyl increment to
118        // decorrelate consecutive rounds (rotation alone leaves
119        // 60+ bits in common between adjacent rounds).
120        k = k.rotate_right(shift).wrapping_add(0x9E37_79B9_7F4A_7C15);
121    }
122    ((l << half_bits) | r) & n_mask
123}
124
125/// `n`-consistent permutation iterator over `0..n` driven by one
126/// bijection per level (see module docs).
127pub struct ConsistentPermutation {
128    /// Master key driving every layer's Feistel. Must be supplied
129    /// already avalanched (see [`ConsistentPermutation::new`]).
130    /// Layers stay distinct because their geometry
131    /// (`n_bits`, `half_bits`, rotation amount, round count) differs.
132    master_key: u64,
133    /// `counters[j]` is the next index to feed into the layer-`j`
134    /// bijection. Walks the full domain `[0, 2^(2j + 2))`. With
135    /// `n <= 2^30`, `j_max <= 14` so the top counter caps at
136    /// `2^30 <= u32::MAX`.
137    counters: Vec<u32>,
138    n: u32,
139}
140
141impl ConsistentPermutation {
142    /// Construct an iterator over `0..n` from a single 64-bit
143    /// `master_key`. Each layer's Feistel round count is chosen
144    /// automatically by [`rounds_for_n_bits`] given that layer's bit
145    /// width.
146    ///
147    /// `n` must satisfy `n <= 2^30`.
148    ///
149    /// `master_key` is used directly as the Feistel key — the
150    /// constructor does **not** avalanche it. Pass a high-entropy
151    /// value (e.g. the output of a cryptographic or strong
152    /// non-cryptographic hash like SplitMix64); sequential or
153    /// low-entropy keys will produce visibly correlated permutations
154    /// across consecutive iterators.
155    pub fn new(n: u32, master_key: u64) -> Self {
156        assert!(n <= 1u32 << 30, "n must be at most 2^30");
157        // Smallest `j_max` such that `4^(j_max + 1) >= n`. For
158        // `n >= 2`, `(n-1).ilog2() = ceil(log2(n)) - 1`, so dividing
159        // by 2 gives `ceil(ceil(log2(n)) / 2) - 1` — the right value
160        // for both even and odd bit-widths.
161        let j_max = if n <= 1 { 0 } else { (n - 1).ilog2() / 2 };
162        let counters = vec![0u32; (j_max + 1) as usize];
163        Self {
164            master_key,
165            counters,
166            n,
167        }
168    }
169
170    /// Universe size.
171    pub fn n(&self) -> u32 {
172        self.n
173    }
174}
175
176impl Iterator for ConsistentPermutation {
177    type Item = u32;
178
179    fn next(&mut self) -> Option<u32> {
180        if self.n == 0 {
181            return None;
182        }
183        let num_layers = self.counters.len();
184        let j_max = (num_layers - 1) as u32;
185        let n = self.n;
186        let mk = self.master_key;
187
188        // Phase 1: walk the top layer (where skips and exhaustion
189        // happen) until we either emit an in-range value or descend.
190        let n_bits_top = 2 * num_layers as u32;
191        let top_shift = 2 * j_max;
192        let top_cap = 1u32 << n_bits_top;
193        loop {
194            let counter = self.counters[j_max as usize];
195            if counter >= top_cap {
196                return None;
197            }
198            let raw = layer_apply(n_bits_top, mk, counter);
199            self.counters[j_max as usize] = counter + 1;
200            let top_bits = (raw >> top_shift) & 0b11;
201            if top_bits != 0 {
202                // `raw` lies in `[4^j_max, 4^(j_max+1))`. May be out
203                // of range (only the top layer can exceed `n`).
204                if raw < n {
205                    return Some(raw);
206                }
207                continue;
208            }
209            // Descend. At `j_max == 0` the top layer *is* the bottom
210            // layer and `top_bits == 0` means `raw == 0`.
211            if j_max == 0 {
212                return Some(0);
213            }
214            break;
215        }
216
217        // Phase 2: descend through lower layers. Their counters can
218        // never exhaust within a single walk, and their raw values
219        // are always in `[4^j, 4^(j+1)) ⊂ [0, n)`, so neither
220        // exhaustion nor range checks are needed.
221        for j in (0..j_max).rev() {
222            let counter = self.counters[j as usize];
223            let n_bits = 2 * j + 2;
224            let raw = layer_apply(n_bits, mk, counter);
225            self.counters[j as usize] = counter + 1;
226            let top_shift = 2 * j;
227            let top_bits = (raw >> top_shift) & 0b11;
228            if top_bits != 0 {
229                return Some(raw);
230            }
231        }
232        Some(0)
233    }
234}
235
236#[cfg(test)]
237mod tests {
238    use std::collections::HashSet;
239
240    use super::*;
241
242    /// Across many seeds, `layer_apply(_, key, 0)` must not always
243    /// collapse to the same value (regression test for the "F(0, k) =
244    /// 0" symmetry bug).
245    #[test]
246    fn layer_apply_zero_input_is_key_sensitive() {
247        for n_bits in [2u32, 4, 6, 8, 10] {
248            let outputs: HashSet<u32> = (0..1000u64)
249                .map(|seed| layer_apply(n_bits, splitmix64(seed), 0))
250                .collect();
251            let domain = 1u32 << n_bits;
252            assert!(
253                outputs.len() >= (domain as usize / 2).min(50),
254                "n_bits={n_bits}: only {} distinct values from layer_apply(_, _, 0) across 1000 seeds",
255                outputs.len()
256            );
257        }
258    }
259
260    /// `layer_apply` must be a bijection on `[0, 2^n_bits)` for every
261    /// even supported `n_bits`.
262    #[test]
263    fn layer_apply_is_bijection() {
264        for n_bits in [2u32, 4, 6, 8, 10] {
265            for seed in 0..16u64 {
266                let key = splitmix64(seed);
267                let domain: u32 = 1 << n_bits;
268                let outputs: HashSet<u32> =
269                    (0..domain).map(|x| layer_apply(n_bits, key, x)).collect();
270                assert_eq!(
271                    outputs.len(),
272                    domain as usize,
273                    "n_bits={n_bits} seed={seed}: not a bijection"
274                );
275                for &o in &outputs {
276                    assert!(
277                        o < domain,
278                        "n_bits={n_bits} seed={seed}: output {o} out of range"
279                    );
280                }
281            }
282        }
283    }
284
285    /// Collecting the iterator must yield values in `0..n` without
286    /// duplicates, and must yield **exactly** `n` of them.
287    #[test]
288    fn no_duplicates_within_universe() {
289        for seed in 0..32u64 {
290            for n in [0u32, 1, 2, 3, 4, 5, 7, 8, 9, 16, 17, 31, 32, 33, 100, 1000] {
291                let iter = ConsistentPermutation::new(n, 0x9E37_79B9_7F4A_7C15 ^ seed);
292                let emitted: Vec<u32> = iter.collect();
293                assert_eq!(
294                    emitted.len(),
295                    n as usize,
296                    "seed={seed} n={n}: wrong emission count: {emitted:?}"
297                );
298                assert!(
299                    emitted.iter().all(|&v| v < n),
300                    "seed={seed} n={n}: out-of-range value emitted: {emitted:?}"
301                );
302                let unique: HashSet<u32> = emitted.iter().copied().collect();
303                assert_eq!(
304                    unique.len(),
305                    emitted.len(),
306                    "seed={seed} n={n}: duplicate emitted: {emitted:?}"
307                );
308            }
309        }
310    }
311}