mod compute;
#[cfg(test)]
mod tests;
use crate::error::{BarracudaError, Result};
use crate::tensor::Tensor;
pub struct FheIntt {
input: Tensor,
degree: u32,
modulus: u64,
inv_root_of_unity: u64,
barrett_mu: u64,
inv_twiddle_factors: Vec<u64>,
inv_n: u64,
pipeline_butterfly: wgpu::ComputePipeline,
pipeline_bit_reverse: wgpu::ComputePipeline,
pipeline_scale: wgpu::ComputePipeline,
bind_group_layout: wgpu::BindGroupLayout,
}
impl FheIntt {
pub fn new(input: Tensor, degree: u32, modulus: u64, inv_root_of_unity: u64) -> Result<Self> {
let expected_size = (degree as usize) * 2;
if input.len() != expected_size {
return Err(BarracudaError::Device(format!(
"Input length {} doesn't match expected {} (degree {} * 2)",
input.len(),
expected_size,
degree
)));
}
if !degree.is_power_of_two() {
return Err(BarracudaError::Device(format!(
"Degree {degree} must be a power of 2 for INTT"
)));
}
if modulus == 0 {
return Err(BarracudaError::Device(
"Modulus must be non-zero".to_string(),
));
}
let barrett_mu = u64::MAX.checked_div(modulus).unwrap_or(0);
let inv_twiddle_factors = compute_twiddle_factors(degree, modulus, inv_root_of_unity);
let inv_n = compute_modular_inverse(degree as u64, modulus);
let device = input.device();
let shader =
device.compile_shader(include_str!("../fhe_intt.wgsl"), Some("FHE INTT Shader"));
let bind_group_layout =
device
.device
.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: Some("FHE INTT Bind Group Layout"),
entries: &[
wgpu::BindGroupLayoutEntry {
binding: 0,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 1,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: false },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 2,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 3,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Uniform,
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
],
});
let pipeline_layout =
device
.device
.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("FHE INTT Pipeline Layout"),
bind_group_layouts: &[&bind_group_layout],
immediate_size: 0,
});
let pipeline_butterfly =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("FHE INTT Butterfly Pipeline"),
layout: Some(&pipeline_layout),
module: &shader,
entry_point: Some("main"),
cache: None,
compilation_options: Default::default(),
});
let pipeline_bit_reverse =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("FHE INTT Bit Reverse Pipeline"),
layout: Some(&pipeline_layout),
module: &shader,
entry_point: Some("bit_reverse"),
cache: None,
compilation_options: Default::default(),
});
let pipeline_scale =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("FHE INTT Scale Pipeline"),
layout: Some(&pipeline_layout),
module: &shader,
entry_point: Some("scale_by_n"),
cache: None,
compilation_options: Default::default(),
});
Ok(Self {
input,
degree,
modulus,
inv_root_of_unity,
barrett_mu,
inv_twiddle_factors,
inv_n,
pipeline_butterfly,
pipeline_bit_reverse,
pipeline_scale,
bind_group_layout,
})
}
pub(super) fn input(&self) -> &Tensor {
&self.input
}
pub(super) fn degree(&self) -> u32 {
self.degree
}
pub(super) fn modulus(&self) -> u64 {
self.modulus
}
pub(super) fn inv_root_of_unity(&self) -> u64 {
self.inv_root_of_unity
}
pub(super) fn barrett_mu(&self) -> u64 {
self.barrett_mu
}
pub(super) fn inv_twiddle_factors(&self) -> &[u64] {
&self.inv_twiddle_factors
}
pub(super) fn inv_n(&self) -> u64 {
self.inv_n
}
pub(super) fn pipeline_butterfly(&self) -> &wgpu::ComputePipeline {
&self.pipeline_butterfly
}
pub(super) fn pipeline_bit_reverse(&self) -> &wgpu::ComputePipeline {
&self.pipeline_bit_reverse
}
pub(super) fn pipeline_scale(&self) -> &wgpu::ComputePipeline {
&self.pipeline_scale
}
pub(super) fn bind_group_layout(&self) -> &wgpu::BindGroupLayout {
&self.bind_group_layout
}
}
fn compute_twiddle_factors(degree: u32, modulus: u64, root: u64) -> Vec<u64> {
let mut factors = Vec::with_capacity(degree as usize);
let mut power = 1u64;
for _ in 0..degree {
factors.push(power);
power = (power as u128 * root as u128 % modulus as u128) as u64;
}
factors
}
pub(crate) fn compute_modular_inverse(a: u64, m: u64) -> u64 {
let (mut t, mut new_t) = (0i128, 1i128);
let (mut r, mut new_r) = (m as i128, a as i128);
while new_r != 0 {
let quotient = r / new_r;
(t, new_t) = (new_t, t - quotient * new_t);
(r, new_r) = (new_r, r - quotient * new_r);
}
if r > 1 {
return 0;
}
if t < 0 {
t += m as i128;
}
t as u64
}
#[must_use]
pub fn compute_inverse_root(_degree: u32, modulus: u64, root: u64) -> u64 {
compute_modular_inverse(root, modulus)
}