feistel_permutation_rs/
permutation.rs

1// SPDX-License-Identifier: Apache-2.0
2use std::hash::BuildHasher;
3
4use crate::{Feistel, DefaultBuildHasher};
5
6/// An object of constructing random access permutations.
7pub struct Permutation<B = DefaultBuildHasher>
8where
9    B: BuildHasher,
10{
11    n: u64,
12    feistel: Feistel<B>,
13}
14
15impl<B> Permutation<B>
16where
17    B: BuildHasher,
18{
19    /// Construct a new permutation over the range `0..n`.
20    pub fn new(n: u64, seed: u64, bob: B) -> Permutation<B> {
21        let mut keys = Vec::new();
22        let mut k = seed;
23        for _i in 0..5 {
24            k = bob.hash_one(k);
25            keys.push(k);
26        }
27        //println!("keys = {:?}", keys);
28
29        // Code assumes an even number of bits. Rounding up
30        // increases the constant factor in [`get`] but doesn't
31        // alter the big-O complexity.
32        let z = 64 - n.leading_zeros() as usize;
33        let bits = z + (z & 1);
34
35        Permutation {
36            n,
37            feistel: Feistel::new(bob, bits, &keys),
38        }
39    }
40
41    /// Get the xth element of the permutation.
42    pub fn get(&self, x: u64) -> u64 {
43        assert!(x < self.n);
44        let mut res = self.feistel.encrypt(x);
45        while res >= self.n {
46            res = self.feistel.encrypt(res);
47        }
48        res
49    }
50
51    /// Construct an iterator over the entire permutation.
52    pub fn iter(&self) -> PermutationIterator<'_, B> {
53        PermutationIterator::new(self, 0, self.n)
54    }
55
56    /// Construct an iterator over the subset `begin..end` of the permutation.
57    pub fn range(&self, begin: u64, end: u64) -> PermutationIterator<'_, B> {
58        assert!(begin <= end);
59        assert!(end <= self.n);
60        PermutationIterator::new(self, begin, end)
61    }
62}
63
64/// An iterator over a [`Permutation`] object.
65pub struct PermutationIterator<'a, B>
66where
67    B: BuildHasher,
68{
69    source: &'a Permutation<B>,
70    curr: u64,
71    end: u64,
72}
73
74impl<'a, B> PermutationIterator<'a, B>
75where
76    B: BuildHasher,
77{
78    fn new(source: &'a Permutation<B>, begin: u64, end: u64) -> PermutationIterator<'a, B> {
79        PermutationIterator {
80            source,
81            curr: begin,
82            end,
83        }
84    }
85}
86
87impl<'a, B> Iterator for PermutationIterator<'a, B>
88where
89    B: BuildHasher,
90{
91    type Item = u64;
92
93    fn next(&mut self) -> Option<Self::Item> {
94        if self.curr == self.end {
95            None
96        } else {
97            let res = self.source.get(self.curr);
98            self.curr += 1;
99            Some(res)
100        }
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use xxhash_rust::xxh64;
107
108    use super::*;
109
110    #[test]
111    fn test_1() {
112        let n = 1000;
113        let bob = xxh64::Xxh64Builder::new(19);
114        let perm = Permutation::new(n, 19, bob);
115        let mut xs = Vec::new();
116        for i in 0..n {
117            let x = perm.get(i);
118            //println!("{i}\t{x}");
119            xs.push(x);
120        }
121        let mut lt = 0;
122        for i in 1..n as usize {
123            if xs[i - 1] < xs[i] {
124                lt += 1;
125            }
126        }
127        assert_eq!(lt, n / 2);
128
129        xs.sort();
130        for i in 0..n {
131            assert_eq!(xs[i as usize], i);
132        }
133    }
134
135    #[test]
136    fn test_2() {
137        let n = 1000000;
138        let seed = 29;
139        let perm = Permutation::new(n, seed, DefaultBuildHasher::new());
140        for j in perm.range(100, 200) {
141            println!("{}", j);
142        }
143        for j in perm.iter().take(10) {
144            println!("{}", j);
145        }
146    }
147}
feistel_permutation_rs/permutation.rs

feistel_permutation_rs/
permutation.rs
