Skip to main content

qualia_audio/features/fft/
real_fft.rs

1//! Real-input forward FFT producing the `N/2 + 1` magnitude spectrum.
2//!
3//! Built on [`super::radix2::fft_radix2`]. Caller-buffered and zero-heap: the
4//! caller supplies a `2 * N` interleaved-complex scratch buffer (overwritten)
5//! and an `N/2 + 1` magnitude output buffer.
6
7use crate::features::fft::radix2::fft_radix2;
8use crate::types::AudioError;
9
10/// Forward FFT of `N` real samples, writing the magnitude of the first
11/// `N/2 + 1` bins (the non-redundant half for real input).
12///
13/// - `input`: `N` real samples, `N` a power of two.
14/// - `scratch`: exactly `2 * N` floats; used as interleaved complex work space
15///   and clobbered on return.
16/// - `out_mags`: at least `N/2 + 1` floats; magnitudes `|X[k]|` for
17///   `k = 0..=N/2` are written into the first `N/2 + 1` slots.
18///
19/// Returns [`AudioError::InvalidParameter`] if `N` is 0 or not a power of two,
20/// or [`AudioError::OutputBufferTooSmall`] if `scratch` or `out_mags` are short.
21pub fn real_fft_magnitude(
22    input: &[f32],
23    scratch: &mut [f32],
24    out_mags: &mut [f32],
25) -> Result<(), AudioError> {
26    let n = input.len();
27    if n == 0 || !n.is_power_of_two() {
28        return Err(AudioError::InvalidParameter);
29    }
30    let bins = n / 2 + 1;
31    if scratch.len() < 2 * n || out_mags.len() < bins {
32        return Err(AudioError::OutputBufferTooSmall);
33    }
34
35    // Pack real input into interleaved complex [re, 0].
36    for i in 0..n {
37        scratch[2 * i] = input[i];
38        scratch[2 * i + 1] = 0.0;
39    }
40    fft_radix2(&mut scratch[..2 * n], false)?;
41
42    for k in 0..bins {
43        let re = scratch[2 * k];
44        let im = scratch[2 * k + 1];
45        out_mags[k] = (re * re + im * im).sqrt();
46    }
47    Ok(())
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53    use core::f32::consts::TAU;
54
55    #[test]
56    fn tone_energy_lands_in_expected_bin() {
57        // 440 Hz-like tone: choose N and fs, pick the bin nearest 440 Hz, and
58        // synthesise exactly at that bin's centre frequency so it lands cleanly.
59        let n = 1024usize;
60        let fs = 44_100.0f32;
61        let k0 = (440.0 * n as f32 / fs).round() as usize; // ≈ bin 10
62        let freq = k0 as f32 * fs / n as f32; // exact bin-centre freq (~430.7 Hz)
63
64        let input: Vec<f32> = (0..n).map(|i| (TAU * freq * i as f32 / fs).cos()).collect();
65        let mut scratch = vec![0.0f32; 2 * n];
66        let mut mags = vec![0.0f32; n / 2 + 1];
67        real_fft_magnitude(&input, &mut scratch, &mut mags).unwrap();
68
69        let mut peak = 1usize;
70        for (b, m) in mags.iter().enumerate().skip(1) {
71            if *m > mags[peak] {
72                peak = b;
73            }
74        }
75        assert_eq!(peak, k0, "tone energy expected in bin {k0}, found {peak}");
76    }
77
78    #[test]
79    fn dc_input_peaks_at_bin_zero() {
80        let n = 16usize;
81        let input = vec![1.0f32; n];
82        let mut scratch = vec![0.0f32; 2 * n];
83        let mut mags = vec![0.0f32; n / 2 + 1];
84        real_fft_magnitude(&input, &mut scratch, &mut mags).unwrap();
85        assert!((mags[0] - n as f32).abs() < 1e-3);
86        for m in &mags[1..] {
87            assert!(*m < 1e-3);
88        }
89    }
90
91    #[test]
92    fn rejects_short_scratch() {
93        let input = vec![0.0f32; 8];
94        let mut scratch = vec![0.0f32; 8]; // needs 16
95        let mut mags = vec![0.0f32; 5];
96        assert_eq!(
97            real_fft_magnitude(&input, &mut scratch, &mut mags),
98            Err(AudioError::OutputBufferTooSmall)
99        );
100    }
101}