Skip to main content

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}