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}