Skip to main content

qualia_audio/features/fft/
radix2.rs

1//! In-place iterative radix-2 Cooley–Tukey FFT (power-of-two `N`).
2//!
3//! Operates on interleaved complex data `[re0, im0, re1, im1, …]`, so the slice
4//! length is `2 * N`. Zero-heap: delegated to [`etalon_signal::dft::fft_radix2_interleaved_f32`].
5
6use crate::types::AudioError;
7
8/// Forward (`inverse == false`) or inverse (`inverse == true`) radix-2 FFT,
9/// in place, over interleaved complex samples.
10///
11/// `data.len()` must equal `2 * N` where `N` is a power of two. The inverse
12/// transform is normalised by `1/N`, so `fft_radix2(x, false)` followed by
13/// `fft_radix2(x, true)` reproduces the original `x`.
14///
15/// Returns [`AudioError::InvalidParameter`] if the length is odd, zero, or the
16/// implied `N` is not a power of two.
17#[inline]
18pub fn fft_radix2(data: &mut [f32], inverse: bool) -> Result<(), AudioError> {
19    etalon_signal::dft::fft_radix2_interleaved_f32(data, inverse)
20        .map_err(|_| AudioError::InvalidParameter)
21}
22
23#[cfg(test)]
24mod tests {
25    use super::*;
26    use core::f32::consts::TAU;
27
28    fn magnitudes(data: &[f32]) -> Vec<f32> {
29        data.chunks_exact(2)
30            .map(|c| (c[0] * c[0] + c[1] * c[1]).sqrt())
31            .collect()
32    }
33
34    #[test]
35    fn peak_bin_matches_cosine_frequency() {
36        // Golden: FFT of cos(2π·k0·n/N) peaks at bins k0 and N-k0.
37        let n = 64usize;
38        let k0 = 5usize;
39        let mut data = vec![0.0f32; 2 * n];
40        for i in 0..n {
41            data[2 * i] = (TAU * k0 as f32 * i as f32 / n as f32).cos();
42            data[2 * i + 1] = 0.0;
43        }
44        fft_radix2(&mut data, false).unwrap();
45        let mags = magnitudes(&data);
46
47        // Peak over lower half (excluding DC) must be at k0.
48        let mut peak = 1usize;
49        for (b, m) in mags.iter().enumerate().take(n / 2 + 1).skip(1) {
50            if *m > mags[peak] {
51                peak = b;
52            }
53        }
54        assert_eq!(peak, k0, "expected peak at k0={k0}, got {peak}");
55        // Mirror image at N-k0 must also be strong.
56        assert!(mags[n - k0] > mags[k0] * 0.5);
57    }
58
59    #[test]
60    fn round_trip_reconstructs_input() {
61        let n = 128usize;
62        let mut data = vec![0.0f32; 2 * n];
63        let orig: Vec<f32> = (0..n)
64            .map(|i| (0.3 * i as f32).sin() + 0.5 * (0.05 * i as f32).cos())
65            .collect();
66        for i in 0..n {
67            data[2 * i] = orig[i];
68            data[2 * i + 1] = 0.0;
69        }
70        fft_radix2(&mut data, false).unwrap();
71        fft_radix2(&mut data, true).unwrap();
72        for i in 0..n {
73            assert!(
74                (data[2 * i] - orig[i]).abs() < 1e-4,
75                "re[{i}] {} vs {}",
76                data[2 * i],
77                orig[i]
78            );
79            assert!(
80                data[2 * i + 1].abs() < 1e-4,
81                "im[{i}] leaked {}",
82                data[2 * i + 1]
83            );
84        }
85    }
86
87    #[test]
88    fn rejects_non_power_of_two() {
89        let mut data = vec![0.0f32; 2 * 6]; // N = 6
90        assert_eq!(
91            fft_radix2(&mut data, false),
92            Err(AudioError::InvalidParameter)
93        );
94    }
95
96    #[test]
97    fn rejects_odd_length() {
98        let mut data = vec![0.0f32; 7];
99        assert_eq!(
100            fft_radix2(&mut data, false),
101            Err(AudioError::InvalidParameter)
102        );
103    }
104}