use crate::device::capabilities::WORKGROUP_SIZE_1D;
use crate::device::compute_pipeline::ComputeDispatch;
use crate::error::{BarracudaError, Result};
use crate::tensor::Tensor;
const MAX_FFT_DEGREE: u32 = 1 << 24;
#[repr(C)]
#[derive(Debug, Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
pub struct BatchedFftParams {
pub degree: u32,
pub stage: u32,
pub inverse: u32,
pub element_stride: u32,
pub dim1_stride: u32,
pub dim2_stride: u32,
pub dim1_count: u32,
pub dim2_count: u32,
}
#[derive(Debug, Clone, Copy)]
pub struct AxisConfig {
pub degree: u32,
pub element_stride: u32,
pub dim1_stride: u32,
pub dim2_stride: u32,
pub dim1_count: u32,
pub dim2_count: u32,
}
pub const BATCHED_SHADER_F64: &str = include_str!("fft_3d_batched_f64.wgsl");
#[must_use]
pub fn batched_shader_f32() -> &'static str {
static SHADER: std::sync::LazyLock<String> =
std::sync::LazyLock::new(|| BATCHED_SHADER_F64.to_string());
&SHADER
}
#[must_use]
pub fn upload_twiddles_f32(
device: &crate::device::WgpuDevice,
degree: u32,
) -> (wgpu::Buffer, wgpu::Buffer) {
let pi = std::f32::consts::PI;
let (re, im): (Vec<f32>, Vec<f32>) = (0..degree)
.map(|k| {
let angle = -2.0 * pi * (k as f32) / (degree as f32);
(angle.cos(), angle.sin())
})
.unzip();
let re_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("FFT Twiddle Re f32"),
contents: bytemuck::cast_slice(&re),
usage: wgpu::BufferUsages::STORAGE,
});
let im_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("FFT Twiddle Im f32"),
contents: bytemuck::cast_slice(&im),
usage: wgpu::BufferUsages::STORAGE,
});
(re_buf, im_buf)
}
#[must_use]
pub fn upload_twiddles_f64(
device: &crate::device::WgpuDevice,
degree: u32,
) -> (wgpu::Buffer, wgpu::Buffer) {
let pi = std::f64::consts::PI;
let (re, im): (Vec<f64>, Vec<f64>) = (0..degree)
.map(|k| {
let angle = -2.0 * pi * (k as f64) / (degree as f64);
(angle.cos(), angle.sin())
})
.unzip();
let re_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("FFT Twiddle Re f64"),
contents: bytemuck::cast_slice(&re),
usage: wgpu::BufferUsages::STORAGE,
});
let im_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("FFT Twiddle Im f64"),
contents: bytemuck::cast_slice(&im),
usage: wgpu::BufferUsages::STORAGE,
});
(re_buf, im_buf)
}
pub(crate) fn dispatch_axis_inner(
device: &crate::device::WgpuDevice,
shader: &str,
buf_a: &wgpu::Buffer,
buf_b: &wgpu::Buffer,
buffer_bytes: u64,
tw_re: &wgpu::Buffer,
tw_im: &wgpu::Buffer,
axis: &AxisConfig,
inverse: bool,
use_f64: bool,
) -> Result<()> {
let n = axis.degree;
let log_n = (n as f32).log2() as u32;
let num_pencils = axis.dim1_count * axis.dim2_count;
let inv_flag = u32::from(inverse);
let br_params = BatchedFftParams {
degree: n,
stage: 0,
inverse: inv_flag,
element_stride: axis.element_stride,
dim1_stride: axis.dim1_stride,
dim2_stride: axis.dim2_stride,
dim1_count: axis.dim1_count,
dim2_count: axis.dim2_count,
};
let br_params_buf = device.create_uniform_buffer("FFT BR Params", &br_params);
let total_invocations = num_pencils * n;
let workgroups = total_invocations.div_ceil(WORKGROUP_SIZE_1D);
let mut br_dispatch = ComputeDispatch::new(device, "FFT Bit Reverse")
.shader(shader, "bit_reverse")
.storage_read(0, buf_a)
.storage_rw(1, buf_b)
.storage_read(2, tw_re)
.storage_read(3, tw_im)
.uniform(4, &br_params_buf);
if use_f64 {
br_dispatch = br_dispatch.f64();
}
br_dispatch.dispatch(workgroups, 1, 1).submit()?;
{
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("FFT Copy BR"),
});
encoder.copy_buffer_to_buffer(buf_b, 0, buf_a, 0, buffer_bytes);
device.submit_commands(std::iter::once(encoder.finish()));
}
for stage in 0..log_n {
let s_params = BatchedFftParams {
degree: n,
stage,
inverse: inv_flag,
element_stride: axis.element_stride,
dim1_stride: axis.dim1_stride,
dim2_stride: axis.dim2_stride,
dim1_count: axis.dim1_count,
dim2_count: axis.dim2_count,
};
let s_params_buf = device.create_uniform_buffer("FFT Stage Params", &s_params);
let total = num_pencils * (n / 2);
let workgroups = total.div_ceil(WORKGROUP_SIZE_1D);
let mut bf_dispatch = ComputeDispatch::new(device, "FFT Butterfly")
.shader(shader, "main")
.storage_read(0, buf_a)
.storage_rw(1, buf_b)
.storage_read(2, tw_re)
.storage_read(3, tw_im)
.uniform(4, &s_params_buf);
if use_f64 {
bf_dispatch = bf_dispatch.f64();
}
bf_dispatch.dispatch(workgroups, 1, 1).submit()?;
if stage < log_n - 1 {
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("FFT Copy Stage"),
});
encoder.copy_buffer_to_buffer(buf_b, 0, buf_a, 0, buffer_bytes);
device.submit_commands(std::iter::once(encoder.finish()));
}
}
{
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("FFT Copy Final"),
});
encoder.copy_buffer_to_buffer(buf_b, 0, buf_a, 0, buffer_bytes);
device.submit_commands(std::iter::once(encoder.finish()));
}
Ok(())
}
pub fn dispatch_axis(
device: &crate::device::WgpuDevice,
buf_a: &wgpu::Buffer,
buf_b: &wgpu::Buffer,
buffer_bytes: u64,
tw_re: &wgpu::Buffer,
tw_im: &wgpu::Buffer,
axis: &AxisConfig,
inverse: bool,
) -> Result<()> {
dispatch_axis_inner(
device,
batched_shader_f32(),
buf_a,
buf_b,
buffer_bytes,
tw_re,
tw_im,
axis,
inverse,
false,
)
}
pub fn dispatch_axis_f64(
device: &crate::device::WgpuDevice,
buf_a: &wgpu::Buffer,
buf_b: &wgpu::Buffer,
buffer_bytes: u64,
tw_re: &wgpu::Buffer,
tw_im: &wgpu::Buffer,
axis: &AxisConfig,
inverse: bool,
) -> Result<()> {
dispatch_axis_inner(
device,
BATCHED_SHADER_F64,
buf_a,
buf_b,
buffer_bytes,
tw_re,
tw_im,
axis,
inverse,
true,
)
}
pub struct Fft1D {
input: Tensor,
degree: u32,
}
impl Fft1D {
pub fn new(input: Tensor, degree: u32) -> Result<Self> {
if degree == 0 {
return Err(BarracudaError::Device(
"FFT degree must be non-zero".to_string(),
));
}
if degree & (degree - 1) != 0 {
return Err(BarracudaError::Device(format!(
"FFT degree {degree} must be power of 2"
)));
}
if degree > MAX_FFT_DEGREE {
return Err(BarracudaError::Device(format!(
"FFT degree {degree} exceeds MAX_FFT_DEGREE {MAX_FFT_DEGREE}"
)));
}
let shape = input.shape();
if shape.last() != Some(&2) {
return Err(BarracudaError::Device(
"FFT input must have last dimension = 2 (complex)".to_string(),
));
}
let expected_size = (degree as usize) * 2;
let actual_size: usize = shape.iter().product();
if actual_size != expected_size {
return Err(BarracudaError::Device(format!(
"FFT input size {actual_size} doesn't match degree {degree} (expected {expected_size} elements)"
)));
}
Ok(Self { input, degree })
}
pub fn execute(self) -> Result<Tensor> {
self.execute_internal(false)
}
pub(crate) fn execute_internal(self, inverse: bool) -> Result<Tensor> {
let device = self.input.device();
let n = self.degree;
let buffer_bytes = (n as u64) * 2 * std::mem::size_of::<f32>() as u64;
let buf_a = device.device.create_buffer(&wgpu::BufferDescriptor {
label: Some("FFT buf_a"),
size: buffer_bytes,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
});
{
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("FFT Copy Input"),
});
encoder.copy_buffer_to_buffer(self.input.buffer(), 0, &buf_a, 0, buffer_bytes);
device.submit_commands(std::iter::once(encoder.finish()));
}
let buf_b = device.device.create_buffer(&wgpu::BufferDescriptor {
label: Some("FFT buf_b"),
size: buffer_bytes,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
});
let (tw_re, tw_im) = upload_twiddles_f32(device, n);
let axis = AxisConfig {
degree: n,
element_stride: 1,
dim1_stride: n,
dim2_stride: 1,
dim1_count: 1,
dim2_count: 1,
};
dispatch_axis(
device,
&buf_a,
&buf_b,
buffer_bytes,
&tw_re,
&tw_im,
&axis,
inverse,
)?;
Ok(Tensor::from_buffer(
buf_a,
self.input.shape().to_vec(),
device.clone(),
))
}
}
#[cfg(test)]
mod tests {
use super::*;
#[tokio::test]
async fn test_fft_1d_simple() {
let device = crate::device::test_pool::get_test_device().await;
let data = vec![1.0f32, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0];
let tensor = Tensor::from_data(&data, vec![4, 2], device).unwrap();
let fft = Fft1D::new(tensor, 4).unwrap();
let result = fft.execute().unwrap();
let result_data = result.to_vec().unwrap();
assert!((result_data[0] - 1.0).abs() < 1e-5);
assert!((result_data[2] - 1.0).abs() < 1e-5);
}
#[tokio::test]
async fn test_fft_1d_degree_zero_rejected() {
let device = crate::device::test_pool::get_test_device().await;
let data = vec![1.0f32, 0.0, 0.0, 0.0];
let tensor = Tensor::from_data(&data, vec![2, 2], device).unwrap();
assert!(Fft1D::new(tensor, 0).is_err());
}
#[tokio::test]
async fn test_fft_1d_power_of_2_validation() {
let device = crate::device::test_pool::get_test_device().await;
let data = vec![1.0f32, 0.0, 0.0, 0.0, 0.0, 0.0];
let tensor = Tensor::from_data(&data, vec![3, 2], device).unwrap();
assert!(Fft1D::new(tensor, 3).is_err());
}
}