Skip to main content

qualia_audio/features/fft/
mixed_radix.rs

1//! Bounded non-power-of-two fallback: a direct DFT floor.
2//!
3//! This is the documented O(N²) floor used when `N` is not a power of two, so
4//! the pipeline always has a correct transform available. It is caller-buffered
5//! and zero-heap: the caller supplies both the interleaved-complex input and a
6//! separate interleaved-complex output buffer of the same length. For large `N`
7//! prefer [`super::radix2::fft_radix2`]; this exists for correctness on awkward
8//! sizes, not speed.
9
10use crate::types::AudioError;
11
12/// Direct DFT (or inverse DFT) of arbitrary length `N`.
13///
14/// `input` and `output` are interleaved complex `[re, im, …]` of length `2 * N`
15/// and must be distinct buffers of equal length. Forward uses `e^{-j2πkn/N}`;
16/// when `inverse` is true it uses `e^{+j2πkn/N}` and normalises by `1/N`, so a
17/// forward followed by an inverse round-trips the signal.
18///
19/// Returns [`AudioError::InvalidParameter`] if the lengths differ, are odd, or
20/// are zero.
21pub fn dft_direct(input: &[f32], output: &mut [f32], inverse: bool) -> Result<(), AudioError> {
22    if input.len() != output.len() || input.is_empty() || !input.len().is_multiple_of(2) {
23        return Err(AudioError::InvalidParameter);
24    }
25    let n = input.len() / 2;
26    let sign: f64 = if inverse { 1.0 } else { -1.0 };
27    let base = sign * core::f64::consts::TAU / n as f64;
28
29    for k in 0..n {
30        let mut acc_r = 0.0f64;
31        let mut acc_i = 0.0f64;
32        for m in 0..n {
33            let ang = base * (k as f64) * (m as f64);
34            let wr = ang.cos();
35            let wi = ang.sin();
36            let xr = input[2 * m] as f64;
37            let xi = input[2 * m + 1] as f64;
38            // x · w
39            acc_r += xr * wr - xi * wi;
40            acc_i += xr * wi + xi * wr;
41        }
42        if inverse {
43            acc_r /= n as f64;
44            acc_i /= n as f64;
45        }
46        output[2 * k] = acc_r as f32;
47        output[2 * k + 1] = acc_i as f32;
48    }
49    Ok(())
50}
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55    use core::f32::consts::TAU;
56
57    #[test]
58    fn dft_peak_bin_non_power_of_two() {
59        // N = 12 (not a power of two): cosine at k0 must peak at k0.
60        let n = 12usize;
61        let k0 = 3usize;
62        let mut input = vec![0.0f32; 2 * n];
63        let mut output = vec![0.0f32; 2 * n];
64        for i in 0..n {
65            input[2 * i] = (TAU * k0 as f32 * i as f32 / n as f32).cos();
66        }
67        dft_direct(&input, &mut output, false).unwrap();
68        let mags: Vec<f32> = output
69            .chunks_exact(2)
70            .map(|c| (c[0] * c[0] + c[1] * c[1]).sqrt())
71            .collect();
72        let mut peak = 1usize;
73        for (b, m) in mags.iter().enumerate().take(n / 2 + 1).skip(1) {
74            if *m > mags[peak] {
75                peak = b;
76            }
77        }
78        assert_eq!(peak, k0);
79    }
80
81    #[test]
82    fn dft_round_trip() {
83        let n = 9usize;
84        let orig: Vec<f32> = (0..n).map(|i| (0.7 * i as f32).sin()).collect();
85        let mut input = vec![0.0f32; 2 * n];
86        let mut fwd = vec![0.0f32; 2 * n];
87        let mut back = vec![0.0f32; 2 * n];
88        for i in 0..n {
89            input[2 * i] = orig[i];
90        }
91        dft_direct(&input, &mut fwd, false).unwrap();
92        dft_direct(&fwd, &mut back, true).unwrap();
93        for i in 0..n {
94            assert!((back[2 * i] - orig[i]).abs() < 1e-4);
95            assert!(back[2 * i + 1].abs() < 1e-4);
96        }
97    }
98
99    #[test]
100    fn rejects_mismatched_lengths() {
101        let input = vec![0.0f32; 8];
102        let mut output = vec![0.0f32; 6];
103        assert_eq!(
104            dft_direct(&input, &mut output, false),
105            Err(AudioError::InvalidParameter)
106        );
107    }
108}