const ROUNDS: u32 = 4;
const GOLDEN: u64 = 0x9E37_79B9_7F4A_7C15;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Permutation {
seed: u64,
len: u64,
half: u32,
}
impl Permutation {
pub fn new(seed: u64, len: u64) -> Self {
Self {
seed,
len,
half: half_width(len),
}
}
pub fn len(&self) -> u64 {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn at(&self, index: u64) -> Option<u64> {
(index < self.len).then(|| self.walk(index))
}
pub fn iter(&self) -> impl Iterator<Item = u64> + Send + 'static {
let order = *self;
(0..order.len).map(move |index| order.walk(index))
}
fn walk(&self, index: u64) -> u64 {
if self.half == 0 {
return index;
}
let mut position = index;
loop {
position = self.round_trip(position);
if position < self.len {
return position;
}
}
}
fn round_trip(&self, value: u64) -> u64 {
let mask = (1u64 << self.half) - 1;
let mut left = (value >> self.half) & mask;
let mut right = value & mask;
for round in 0..ROUNDS {
let mixed = left ^ (mix(self.seed, round, right) & mask);
left = right;
right = mixed;
}
(left << self.half) | right
}
}
fn half_width(len: u64) -> u32 {
if len <= 1 {
return 0;
}
let width = u64::BITS - (len - 1).leading_zeros();
(width + (width & 1)) / 2
}
const fn mix(seed: u64, round: u32, value: u64) -> u64 {
let mut mixed = value
.wrapping_add(seed)
.wrapping_add((round as u64).wrapping_mul(GOLDEN));
mixed ^= mixed >> 30;
mixed = mixed.wrapping_mul(0xBF58_476D_1CE4_E5B9);
mixed ^= mixed >> 27;
mixed = mixed.wrapping_mul(0x94D0_49BB_1331_11EB);
mixed ^ (mixed >> 31)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn is_a_permutation_of_the_whole_domain() {
let mut lengths: Vec<u64> = (0..=64).collect();
for power in 3..14u32 {
let size = 1u64 << power;
lengths.extend([size - 1, size, size + 1]);
}
for len in lengths {
for seed in [0, 1, 0x5EED, u64::MAX] {
let order = Permutation::new(seed, len);
let mut asked: Vec<u64> = order.iter().collect();
assert_eq!(asked.len() as u64, len, "len {len}, seed {seed}");
asked.sort_unstable();
assert!(
asked.iter().copied().eq(0..len),
"len {len}, seed {seed}: a target was asked twice or not at all"
);
}
}
}
#[test]
fn a_seed_names_the_same_order_every_time() {
let once: Vec<u64> = Permutation::new(0xC0FFEE, 5_000).iter().collect();
let again: Vec<u64> = Permutation::new(0xC0FFEE, 5_000).iter().collect();
assert_eq!(once, again);
}
#[test]
fn two_seeds_name_different_orders() {
let one: Vec<u64> = Permutation::new(1, 5_000).iter().collect();
let other: Vec<u64> = Permutation::new(2, 5_000).iter().collect();
assert_ne!(one, other);
}
#[test]
fn consecutive_questions_land_in_unrelated_parts_of_the_plan() {
const LEN: u64 = 65_536;
const NEAR: u64 = 256;
let asked: Vec<u64> = Permutation::new(0x5EED, LEN).iter().collect();
let near = asked
.windows(2)
.filter(|pair| pair[0].abs_diff(pair[1]) < NEAR)
.count();
assert!(
near < 2_000,
"{near} of {} consecutive pairs landed within {NEAR} of each other, \
which is a walk rather than a rearrangement",
asked.len() - 1
);
}
#[test]
fn a_range_too_small_to_rearrange_is_the_identity() {
assert!(Permutation::new(7, 0).iter().next().is_none());
assert_eq!(Permutation::new(7, 1).iter().collect::<Vec<_>>(), vec![0]);
assert!(Permutation::new(7, 0).is_empty());
}
#[test]
fn an_index_past_the_end_names_no_position() {
let order = Permutation::new(3, 10);
assert!(order.at(9).is_some());
assert_eq!(order.at(10), None);
assert_eq!(order.at(u64::MAX), None);
}
#[test]
fn the_widest_range_rearranges_without_overflowing_a_shift() {
let order = Permutation::new(0x5EED, u64::MAX);
assert_eq!(order.len(), u64::MAX);
for index in [0, 1, 2, u64::MAX / 2, u64::MAX - 1] {
let position = order.at(index).expect("inside the range");
assert!(position < u64::MAX);
}
}
}