zond_engine/model/order.rs
1// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
2//
3// This file is part of Zond Engine, licensed under the GNU Affero General
4// Public License, version 3 or later. See the LICENSE file for details, or
5// <https://www.gnu.org/licenses/agpl-3.0.html>.
6//
7// SPDX-License-Identifier: AGPL-3.0-or-later
8
9//! # The order a plan's targets are asked in
10//!
11//! A scan that walks its plan in order is easy to recognise: whatever is done to make
12//! each probe look ordinary, the run as a whole is a monotonic sweep across an address
13//! range, which is what a correlating sensor keys on.
14//!
15//! [`Permutation`] is a keyed rearrangement of the plan's whole index space, so
16//! consecutive questions land in unrelated parts of the network.
17//!
18//! ## Computed, not shuffled
19//!
20//! A `/8` on a thousand ports is sixteen billion targets, which is why
21//! [`TargetSet`](crate::model::target::TargetSet) describes a plan without holding
22//! one. Shuffling needs the list in memory, so it can only shuffle a window at a time,
23//! and the window is itself a signature: batches of eight thousand spread a `/24`
24//! well but walk a `/16` in address order. A computed permutation has no window and
25//! costs three words and a handful of arithmetic per target.
26//!
27//! ## Keyed and reproducible
28//!
29//! A [`TargetSet`](crate::model::target::TargetSet) is canonical from construction, so
30//! the nth target is the same on every run, and
31//! [`TargetIndex`](crate::model::target::TargetIndex) resolves a position back to it.
32//! The order is therefore a pure function of a seed: a journal records the seed, and a
33//! resumed sitting asks its remaining targets in the same relative order.
34//!
35//! ## Not cryptography
36//!
37//! The construction is a small Feistel network over the index space, a permutation by
38//! its shape, with a bit mixer as round function. It defeats a sensor correlating a
39//! monotonic walk; it would not survive someone looking for it.
40//!
41//! The one hard requirement is never to skip or repeat a target, which makes
42//! [`Permutation`] a bijection, checked by `is_a_permutation_of_the_whole_domain`.
43
44/// How many rounds the network runs.
45///
46/// Four is where a Feistel construction stops visibly resembling its input: with three,
47/// the low half of the output stays correlated with the low half of the index, so
48/// neighbouring targets still arrive near each other.
49const ROUNDS: u32 = 4;
50
51/// Knuth's golden-ratio constant, which separates the rounds from each other.
52///
53/// Without it every round mixes the same key with the same value and the network
54/// collapses to a much weaker function of two rounds.
55const GOLDEN: u64 = 0x9E37_79B9_7F4A_7C15;
56
57/// A keyed rearrangement of `0..len`.
58///
59/// Every index in the range maps to a distinct value in the range, and the whole range
60/// is covered.
61///
62/// ```
63/// use zond_engine::model::order::Permutation;
64///
65/// let order = Permutation::new(0x5EED, 1_000);
66///
67/// let mut asked: Vec<u64> = order.iter().collect();
68/// assert_eq!(asked.len(), 1_000);
69///
70/// asked.sort_unstable();
71/// assert!(asked.iter().copied().eq(0..1_000), "every target, asked once");
72/// ```
73#[derive(Debug, Clone, Copy, PartialEq, Eq)]
74pub struct Permutation {
75 /// The key the order is a function of.
76 seed: u64,
77 /// How many positions are rearranged.
78 len: u64,
79 /// Half the width of the domain the network runs over, in bits.
80 ///
81 /// Zero for a domain of one position or none, where there is nothing to
82 /// rearrange and the permutation is the identity.
83 half: u32,
84}
85
86impl Permutation {
87 /// The rearrangement of `0..len` that `seed` names.
88 ///
89 /// The same pair produces the same order on any build, since a seed recorded in a
90 /// journal has to mean the same order when the scan is continued. The mixing is
91 /// written out here because a library hasher's output may change between
92 /// releases.
93 pub fn new(seed: u64, len: u64) -> Self {
94 Self {
95 seed,
96 len,
97 half: half_width(len),
98 }
99 }
100
101 /// How many positions are rearranged.
102 pub fn len(&self) -> u64 {
103 self.len
104 }
105
106 /// Whether nothing is.
107 pub fn is_empty(&self) -> bool {
108 self.len == 0
109 }
110
111 /// The position asked about `index`th, or [`None`] for an index outside the
112 /// range this rearranges.
113 ///
114 /// The bound matters: the walk lands inside `0..len` from anywhere in the domain,
115 /// so an index past the end would repeat a position some index inside it answers.
116 pub fn at(&self, index: u64) -> Option<u64> {
117 (index < self.len).then(|| self.walk(index))
118 }
119
120 /// The key this order is a function of.
121 pub fn seed(&self) -> u64 {
122 self.seed
123 }
124
125 /// When `position` is asked about: the index [`at`](Self::at) names it
126 /// at, or [`None`] for a position outside the range.
127 ///
128 /// The inverse of [`at`](Self::at), and as cheap. Lets progress be counted in the
129 /// order the scan asks while answers arrive numbered by plan position.
130 ///
131 /// ```
132 /// use zond_engine::model::order::Permutation;
133 ///
134 /// let order = Permutation::new(0x5EED, 1_000);
135 /// let position = order.at(417).expect("inside the range");
136 ///
137 /// assert_eq!(order.index_of(position), Some(417));
138 /// assert_eq!(order.index_of(1_000), None);
139 /// ```
140 pub fn index_of(&self, position: u64) -> Option<u64> {
141 (position < self.len).then(|| self.unwalk(position))
142 }
143
144 /// Every position, in the order the scan asks about them.
145 pub fn iter(&self) -> impl Iterator<Item = u64> + Send + 'static {
146 self.iter_from(0)
147 }
148
149 /// The positions from the `start`th on, in the order the scan asks about
150 /// them: the rest of a walk an earlier sitting got `start` positions into.
151 pub(crate) fn iter_from(&self, start: u64) -> impl Iterator<Item = u64> + Send + 'static {
152 let order = *self;
153 (start.min(order.len)..order.len).map(move |index| order.walk(index))
154 }
155
156 /// [`at`](Self::at) without the bound, for an index already known to be
157 /// inside the range.
158 ///
159 /// Walks the network until it lands inside the range (cycle walking), the standard
160 /// way to cut a permutation of a power of two down to an arbitrary count. It always
161 /// terminates: the network is a bijection, so repeated application traces the
162 /// cycle `index` sits on, which contains `index` itself.
163 ///
164 /// The domain is under four times the range, so it usually lands on the first try
165 /// and essentially always by the fourth.
166 fn walk(&self, index: u64) -> u64 {
167 if self.half == 0 {
168 return index;
169 }
170
171 let mut position = index;
172 loop {
173 position = self.round_trip(position);
174 if position < self.len {
175 return position;
176 }
177 }
178 }
179
180 /// [`walk`](Self::walk) backwards: the index whose walk lands on
181 /// `position`, for a position already known to be inside the range.
182 ///
183 /// The same cycle traced the other way: stepping back through values outside the
184 /// range arrives at the index, the first value inside it.
185 fn unwalk(&self, position: u64) -> u64 {
186 if self.half == 0 {
187 return position;
188 }
189
190 let mut index = position;
191 loop {
192 index = self.round_trip_back(index);
193 if index < self.len {
194 return index;
195 }
196 }
197 }
198
199 /// [`round_trip`](Self::round_trip) undone: the rounds in reverse, each
200 /// `(l, r) -> (r ^ f(l), l)`.
201 fn round_trip_back(&self, value: u64) -> u64 {
202 let mask = (1u64 << self.half) - 1;
203 let mut left = (value >> self.half) & mask;
204 let mut right = value & mask;
205
206 for round in (0..ROUNDS).rev() {
207 let earlier_right = left;
208 left = right ^ (mix(self.seed, round, earlier_right) & mask);
209 right = earlier_right;
210 }
211
212 (left << self.half) | right
213 }
214
215 /// One pass of the network: [`ROUNDS`] rounds of `(l, r) -> (r, l ^ f(r))`.
216 ///
217 /// A bijection over `0..2^(2 * half)` whatever the round function does, since each
218 /// round can be undone, so no two inputs collide.
219 fn round_trip(&self, value: u64) -> u64 {
220 let mask = (1u64 << self.half) - 1;
221 let mut left = (value >> self.half) & mask;
222 let mut right = value & mask;
223
224 for round in 0..ROUNDS {
225 let mixed = left ^ (mix(self.seed, round, right) & mask);
226 left = right;
227 right = mixed;
228 }
229
230 (left << self.half) | right
231 }
232}
233
234/// Half the width of the smallest domain that holds `len`, in bits.
235///
236/// Rounded up to an even number of bits so the two halves have the same width. That
237/// costs at most one extra bit of domain, so [`Permutation::walk`] discards under three
238/// quarters of its landings in the worst case.
239///
240/// Zero for a range of one position or none, which has one arrangement.
241fn half_width(len: u64) -> u32 {
242 if len <= 1 {
243 return 0;
244 }
245
246 // The smallest width whose domain holds `len`, then rounded up to even.
247 let width = u64::BITS - (len - 1).leading_zeros();
248 (width + (width & 1)) / 2
249}
250
251/// The round function: the key, the round and the half, mixed into a value the
252/// round exclusive-ors into the other half.
253///
254/// A well-known 64-bit avalanche step (SplitMix64's finaliser), written out for the
255/// reason [`Permutation::new`] gives.
256const fn mix(seed: u64, round: u32, value: u64) -> u64 {
257 let mut mixed = value
258 .wrapping_add(seed)
259 .wrapping_add((round as u64).wrapping_mul(GOLDEN));
260
261 mixed ^= mixed >> 30;
262 mixed = mixed.wrapping_mul(0xBF58_476D_1CE4_E5B9);
263 mixed ^= mixed >> 27;
264 mixed = mixed.wrapping_mul(0x94D0_49BB_1331_11EB);
265 mixed ^ (mixed >> 31)
266}
267
268// ╔════════════════════════════════════════════╗
269// ║ ████████╗███████╗███████╗████████╗███████╗ ║
270// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
271// ║ ██║ █████╗ ███████╗ ██║ ███████╗ ║
272// ║ ██║ ██╔══╝ ╚════██║ ██║ ╚════██║ ║
273// ║ ██║ ███████╗███████║ ██║ ███████║ ║
274// ║ ╚═╝ ╚══════╝╚══════╝ ╚═╝ ╚══════╝ ║
275// ╚════════════════════════════════════════════╝
276
277#[cfg(test)]
278mod tests {
279 use super::*;
280
281 /// The bijection holds at every awkward length: either side of each power of two,
282 /// where the walk discards the most.
283 #[test]
284 fn is_a_permutation_of_the_whole_domain() {
285 let mut lengths: Vec<u64> = (0..=64).collect();
286 for power in 3..14u32 {
287 let size = 1u64 << power;
288 lengths.extend([size - 1, size, size + 1]);
289 }
290
291 for len in lengths {
292 for seed in [0, 1, 0x5EED, u64::MAX] {
293 let order = Permutation::new(seed, len);
294 let mut asked: Vec<u64> = order.iter().collect();
295
296 assert_eq!(asked.len() as u64, len, "len {len}, seed {seed}");
297 asked.sort_unstable();
298 assert!(
299 asked.iter().copied().eq(0..len),
300 "len {len}, seed {seed}: a target was asked twice or not at all"
301 );
302 }
303 }
304 }
305
306 /// A seed names one order, every time.
307 #[test]
308 fn a_seed_names_the_same_order_every_time() {
309 let once: Vec<u64> = Permutation::new(0xC0FFEE, 5_000).iter().collect();
310 let again: Vec<u64> = Permutation::new(0xC0FFEE, 5_000).iter().collect();
311
312 assert_eq!(once, again);
313 }
314
315 /// Two seeds name different orders.
316 #[test]
317 fn two_seeds_name_different_orders() {
318 let one: Vec<u64> = Permutation::new(1, 5_000).iter().collect();
319 let other: Vec<u64> = Permutation::new(2, 5_000).iter().collect();
320
321 assert_ne!(one, other);
322 }
323
324 /// Consecutive questions land far apart. The bound is loose: it rules out the
325 /// identity or a local rearrangement of it without testing the mixer itself.
326 #[test]
327 fn consecutive_questions_land_in_unrelated_parts_of_the_plan() {
328 const LEN: u64 = 65_536;
329 const NEAR: u64 = 256;
330
331 let asked: Vec<u64> = Permutation::new(0x5EED, LEN).iter().collect();
332 let near = asked
333 .windows(2)
334 .filter(|pair| pair[0].abs_diff(pair[1]) < NEAR)
335 .count();
336
337 // A uniform order lands within 256 of its predecessor about 0.8% of the
338 // time, which on 65,535 pairs is around 500.
339 assert!(
340 near < 2_000,
341 "{near} of {} consecutive pairs landed within {NEAR} of each other, \
342 which is a walk rather than a rearrangement",
343 asked.len() - 1
344 );
345 }
346
347 /// A range of one position or none is the identity.
348 #[test]
349 fn a_range_too_small_to_rearrange_is_the_identity() {
350 assert!(Permutation::new(7, 0).iter().next().is_none());
351 assert_eq!(Permutation::new(7, 1).iter().collect::<Vec<_>>(), vec![0]);
352 assert!(Permutation::new(7, 0).is_empty());
353 }
354
355 /// An index outside the range names no position.
356 #[test]
357 fn an_index_past_the_end_names_no_position() {
358 let order = Permutation::new(3, 10);
359
360 assert!(order.at(9).is_some());
361 assert_eq!(order.at(10), None);
362 assert_eq!(order.at(u64::MAX), None);
363 }
364
365 /// `index_of` inverts `at` for every position.
366 #[test]
367 fn index_of_undoes_at_over_every_awkward_length() {
368 for len in [0u64, 1, 2, 3, 7, 8, 9, 255, 256, 257, 1_000, 4_097] {
369 for seed in [0, 0x5EED, u64::MAX] {
370 let order = Permutation::new(seed, len);
371 for index in 0..len {
372 let position = order.at(index).expect("inside the range");
373 assert_eq!(
374 order.index_of(position),
375 Some(index),
376 "len {len}, seed {seed}, index {index}"
377 );
378 }
379 assert_eq!(order.index_of(len), None, "len {len}: past the end");
380 }
381 }
382 }
383
384 /// The inverse holds across the widest domain too.
385 #[test]
386 fn index_of_undoes_at_in_the_widest_range() {
387 let order = Permutation::new(0x5EED, u64::MAX);
388 for index in [0, 1, 2, u64::MAX / 2, u64::MAX - 1] {
389 let position = order.at(index).expect("inside the range");
390 assert_eq!(order.index_of(position), Some(index));
391 }
392 }
393
394 /// A walk resumed part way through asks what the whole walk had left, in
395 /// the same order.
396 #[test]
397 fn a_walk_resumed_part_way_asks_the_rest_in_the_same_order() {
398 let order = Permutation::new(0xC0FFEE, 1_000);
399 let whole: Vec<u64> = order.iter().collect();
400
401 assert_eq!(order.iter_from(417).collect::<Vec<_>>(), whole[417..]);
402 assert_eq!(order.iter_from(5_000).count(), 0);
403 }
404
405 /// The widest domain there is, where the halves are 32 bits each and the
406 /// shifts are one step from overflowing.
407 #[test]
408 fn the_widest_range_rearranges_without_overflowing_a_shift() {
409 let order = Permutation::new(0x5EED, u64::MAX);
410
411 assert_eq!(order.len(), u64::MAX);
412 for index in [0, 1, 2, u64::MAX / 2, u64::MAX - 1] {
413 let position = order.at(index).expect("inside the range");
414 assert!(position < u64::MAX);
415 }
416 }
417}