1use std::{marker::PhantomData, ptr::NonNull};
 2
 3use crate::GALOISGENERATOR;
 4
 5#[allow(clippy::missing_safety_doc)]
 6pub trait Backend: Sized {
 7    type Handle: 'static;
 8    unsafe fn destroy(handle: NonNull<Self::Handle>);
 9}
10
11pub struct Module<B: Backend> {
12    ptr: NonNull<B::Handle>,
13    n: u64,
14    _marker: PhantomData<B>,
15}
16
17impl<B: Backend> Module<B> {
18    /// Construct from a raw pointer managed elsewhere.
19    /// SAFETY: `ptr` must be non-null and remain valid for the lifetime of this Module.
20    #[inline]
21    #[allow(clippy::missing_safety_doc)]
22    pub unsafe fn from_raw_parts(ptr: *mut B::Handle, n: u64) -> Self {
23        Self {
24            ptr: NonNull::new(ptr).expect("null module ptr"),
25            n,
26            _marker: PhantomData,
27        }
28    }
29
30    #[allow(clippy::missing_safety_doc)]
31    #[inline]
32    pub unsafe fn ptr(&self) -> *mut <B as Backend>::Handle {
33        self.ptr.as_ptr()
34    }
35
36    #[inline]
37    pub fn n(&self) -> usize {
38        self.n as usize
39    }
40    #[inline]
41    pub fn as_mut_ptr(&self) -> *mut B::Handle {
42        self.ptr.as_ptr()
43    }
44
45    #[inline]
46    pub fn log_n(&self) -> usize {
47        (usize::BITS - (self.n() - 1).leading_zeros()) as _
48    }
49
50    #[inline]
51    pub fn cyclotomic_order(&self) -> u64 {
52        (self.n() << 1) as _
53    }
54
55    // Returns GALOISGENERATOR^|generator| * sign(generator)
56    #[inline]
57    pub fn galois_element(&self, generator: i64) -> i64 {
58        if generator == 0 {
59            return 1;
60        }
61        ((mod_exp_u64(GALOISGENERATOR, generator.unsigned_abs() as usize) & (self.cyclotomic_order() - 1)) as i64)
62            * generator.signum()
63    }
64
65    // Returns gen^-1
66    #[inline]
67    pub fn galois_element_inv(&self, gal_el: i64) -> i64 {
68        if gal_el == 0 {
69            panic!("cannot invert 0")
70        }
71        ((mod_exp_u64(
72            gal_el.unsigned_abs(),
73            (self.cyclotomic_order() - 1) as usize,
74        ) & (self.cyclotomic_order() - 1)) as i64)
75            * gal_el.signum()
76    }
77}
78
79impl<B: Backend> Drop for Module<B> {
80    fn drop(&mut self) {
81        unsafe { B::destroy(self.ptr) }
82    }
83}
84
85pub fn mod_exp_u64(x: u64, e: usize) -> u64 {
86    let mut y: u64 = 1;
87    let mut x_pow: u64 = x;
88    let mut exp = e;
89    while exp > 0 {
90        if exp & 1 == 1 {
91            y = y.wrapping_mul(x_pow);
92        }
93        x_pow = x_pow.wrapping_mul(x_pow);
94        exp >>= 1;
95    }
96    y
97}