1use crate::modulus::WordOps;
 2use crate::ring::Ring;
 3use num::Unsigned;
 4use utils::map::Map;
 5
 6pub struct AutoPermMap(Map<usize, AutoPerm>);
 7
 8impl AutoPermMap {
 9    pub fn new() -> Self {
10        Self {
11            0: Map::<usize, AutoPerm>::new(),
12        }
13    }
14
15    pub fn insert(&mut self, perm: AutoPerm) -> usize {
16        let gal_el: usize = perm.gal_el;
17        self.0.insert(perm.gal_el, perm);
18        gal_el
19    }
20
21    pub fn gen<O: Unsigned, const NTT: bool>(
22        &mut self,
23        ring: &Ring<O>,
24        gen_1: usize,
25        gen_2: bool,
26    ) -> usize {
27        self.insert(AutoPerm::new::<O, NTT>(ring, gen_1, gen_2))
28    }
29
30    pub fn get(&self, gal_el: &usize) -> Option<&AutoPerm> {
31        self.0.get(gal_el)
32    }
33}
34
35#[derive(Debug)]
36pub struct AutoPerm {
37    pub ntt: bool,
38    pub gal_el: usize,
39    pub permutation: Vec<usize>,
40}
41
42impl AutoPerm {
43    /// Returns a lookup table for the automorphism X^{i} -> X^{i * k mod nth_root}.
44    /// Method will panic if n or nth_root are not power-of-two.
45    /// Method will panic if gal_el is not coprime with nth_root.
46    pub fn new<O: Unsigned, const NTT: bool>(ring: &Ring<O>, gen_1: usize, gen_2: bool) -> Self {
47        let n = ring.n();
48        let cyclotomic_order = ring.cyclotomic_order();
49
50        let gal_el = ring.galois_element(gen_1, gen_2);
51
52        let mut permutation: Vec<usize> = Vec::with_capacity(n);
53
54        if NTT {
55            let mask = cyclotomic_order - 1;
56            let log_cyclotomic_order_half: u32 = cyclotomic_order.log2() as u32 - 1;
57            for i in 0..n {
58                let i_rev: usize = 2 * i.reverse_bits_msb(log_cyclotomic_order_half) + 1;
59                let gal_el_i: usize = ((gal_el * i_rev) & mask) >> 1;
60                permutation.push(gal_el_i.reverse_bits_msb(log_cyclotomic_order_half));
61            }
62        } else {
63            let log_n: usize = n.log2();
64            let mask: usize = (n - 1) as usize;
65            for i in 0..n {
66                let gal_el_i: usize = i as usize * gal_el;
67                let sign: usize = (gal_el_i >> log_n) & 1;
68                let i_out: usize = (gal_el_i & mask) | (sign << (usize::BITS - 1));
69                permutation.push(i_out)
70            }
71        }
72
73        Self {
74            ntt: NTT,
75            gal_el: gal_el,
76            permutation: permutation,
77        }
78    }
79}