Skip to main content

spektra_fft/
lib.rs

1//! A radix-2 Cooley-Tukey Fast Fourier Transform, generic over `f32` and
2//! `f64`.
3//!
4//! A [`Fft`] is a plan: it precomputes the twiddle factors and the
5//! bit-reversal permutation for one transform length, and every transform of
6//! that length then reuses them. Planning takes `&self`, so a single plan can
7//! be shared across threads and across channels.
8//!
9//! ```
10//! use spektra_fft::{Fft, numbers::complex::Complex};
11//!
12//! let plan = Fft::<f64>::new(8)?;
13//!
14//! let mut signal = [Complex::new(1.0, 0.0); 8];
15//! plan.transform_in_place(&mut signal)?;
16//!
17//! // A constant signal puts all of its energy in the DC bin.
18//! assert!((signal[0].re - 8.0).abs() < 1e-12);
19//! assert!(signal[1].norm() < 1e-12);
20//! # Ok::<(), spektra_fft::FftError>(())
21//! ```
22//!
23//! # Normalization
24//!
25//! The forward transform is unnormalized and the inverse divides by `n`, so a
26//! forward followed by an inverse returns the original signal. This is the
27//! same convention as `NumPy` and `FFTW`.
28
29use std::error::Error;
30use std::fmt::{self, Display};
31
32use float::Float;
33use numbers::complex::Complex;
34
35pub mod float;
36pub mod numbers;
37
38/// Why a transform could not run.
39#[derive(Debug, PartialEq, Eq, Clone, Copy)]
40pub enum FftError {
41    /// The requested length is not a power of two.
42    NotPowerOfTwo { size: usize },
43    /// The buffer handed to a transform is not the length this plan was built
44    /// for.
45    LengthMismatch { expected: usize, actual: usize },
46}
47
48impl Display for FftError {
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        match *self {
51            Self::NotPowerOfTwo { size } => {
52                write!(f, "transform length {size} is not a power of two")
53            }
54            Self::LengthMismatch { expected, actual } => {
55                write!(f, "this plan transforms {expected} samples, got {actual}")
56            }
57        }
58    }
59}
60
61impl Error for FftError {}
62
63/// A planned Fast Fourier Transform of one fixed length.
64///
65/// Build it once with [`Fft::new`] and transform many times. Nothing here is
66/// mutated by a transform, so `&self` is enough and a plan is `Sync`.
67#[derive(Debug, Clone, PartialEq)]
68pub struct Fft<T> {
69    /// `n / 2` twiddle factors, `exp(-2*pi*i*k/n)` for `k` in `0..n/2`.
70    twiddles: Vec<Complex<T>>,
71    /// `bit_reversal[i]` is `i` with its `log2(n)` low bits reversed.
72    bit_reversal: Vec<usize>,
73    size: usize,
74}
75
76impl<T: Float> Fft<T> {
77    /// Plan a transform of `size` samples.
78    ///
79    /// # Errors
80    ///
81    /// [`FftError::NotPowerOfTwo`] if `size` is not a power of two. Zero is
82    /// rejected for the same reason.
83    pub fn new(size: usize) -> Result<Self, FftError> {
84        if size == 0 || !size.is_power_of_two() {
85            return Err(FftError::NotPowerOfTwo { size });
86        }
87
88        Ok(Self {
89            twiddles: Self::twiddles(size),
90            bit_reversal: Self::bit_reversal(size),
91            size,
92        })
93    }
94
95    /// The transform length this plan was built for.
96    #[must_use]
97    #[inline]
98    pub const fn size(&self) -> usize {
99        self.size
100    }
101
102    /// Transform `data` in place, leaving the spectrum in natural bin order.
103    ///
104    /// # Errors
105    ///
106    /// [`FftError::LengthMismatch`] if `data` is not [`Fft::size`] long.
107    pub fn transform_in_place(&self, data: &mut [Complex<T>]) -> Result<(), FftError> {
108        if data.len() != self.size {
109            return Err(FftError::LengthMismatch {
110                expected: self.size,
111                actual: data.len(),
112            });
113        }
114
115        self.permute(data);
116        self.butterflies(data);
117
118        Ok(())
119    }
120
121    /// Widen a real signal into `dst` and transform it in place.
122    ///
123    /// This is the naive real transform: it runs a full complex FFT with the
124    /// imaginary parts zeroed, which costs twice what a split-radix real
125    /// transform would.
126    ///
127    /// # Errors
128    ///
129    /// [`FftError::LengthMismatch`] if either slice is not [`Fft::size`] long.
130    pub fn transform_into(&self, signal: &[T], dst: &mut [Complex<T>]) -> Result<(), FftError> {
131        if signal.len() != self.size {
132            return Err(FftError::LengthMismatch {
133                expected: self.size,
134                actual: signal.len(),
135            });
136        }
137        if dst.len() != self.size {
138            return Err(FftError::LengthMismatch {
139                expected: self.size,
140                actual: dst.len(),
141            });
142        }
143
144        for (slot, &sample) in dst.iter_mut().zip(signal) {
145            *slot = Complex::new(sample, T::ZERO);
146        }
147
148        self.transform_in_place(dst)
149    }
150
151    /// Invert a spectrum in place, scaling by `1/n`.
152    ///
153    /// Implemented as conjugate, forward transform, conjugate and scale, so it
154    /// reuses the same twiddles as the forward direction.
155    ///
156    /// # Errors
157    ///
158    /// [`FftError::LengthMismatch`] if `data` is not [`Fft::size`] long.
159    pub fn inverse_in_place(&self, data: &mut [Complex<T>]) -> Result<(), FftError> {
160        for value in data.iter_mut() {
161            *value = value.conj();
162        }
163
164        self.transform_in_place(data)?;
165
166        let n = T::from_usize(self.size);
167        for value in data.iter_mut() {
168            *value = value.conj() / n;
169        }
170
171        Ok(())
172    }
173
174    /// Transform a complex signal, allocating the output.
175    ///
176    /// Convenience over [`Fft::transform_in_place`] for callers not in a hot
177    /// loop; a signal chain should own its buffer and use the in-place form.
178    ///
179    /// # Errors
180    ///
181    /// [`FftError::LengthMismatch`] if `signal` is not [`Fft::size`] long.
182    pub fn transform(&self, signal: &[Complex<T>]) -> Result<Vec<Complex<T>>, FftError> {
183        let mut data = signal.to_vec();
184        self.transform_in_place(&mut data)?;
185
186        Ok(data)
187    }
188
189    /// Transform a real signal, allocating the output.
190    ///
191    /// # Errors
192    ///
193    /// [`FftError::LengthMismatch`] if `signal` is not [`Fft::size`] long.
194    pub fn transform_real(&self, signal: &[T]) -> Result<Vec<Complex<T>>, FftError> {
195        let mut data = vec![Complex::new(T::ZERO, T::ZERO); self.size];
196        self.transform_into(signal, &mut data)?;
197
198        Ok(data)
199    }
200
201    /// `exp(-2*pi*i*k/n)` for `k` in `0..n/2`.
202    ///
203    /// Each factor comes from its own `sin_cos` rather than from repeatedly
204    /// multiplying a step, whose relative error grows with `n` and shows up
205    /// first at `f32`.
206    fn twiddles(size: usize) -> Vec<Complex<T>> {
207        let half = size / 2;
208        let base = -(T::PI + T::PI) / T::from_usize(size);
209
210        (0..half)
211            .map(|k| {
212                let (sin, cos) = (base * T::from_usize(k)).sin_cos();
213
214                Complex::new(cos, sin)
215            })
216            .collect()
217    }
218
219    /// The bit-reversal permutation, built once per plan.
220    ///
221    /// Each index is derived from its predecessor by incrementing a reversed
222    /// counter, so the table costs O(n) rather than the O(n log n) of
223    /// reversing every index from scratch.
224    fn bit_reversal(size: usize) -> Vec<usize> {
225        let mut table = vec![0_usize; size];
226        let mut reversed = 0_usize;
227
228        for (index, slot) in table.iter_mut().enumerate() {
229            *slot = reversed;
230
231            // Increment `reversed` as if its bits ran the other way: carry
232            // from the top down instead of from the bottom up.
233            let mut bit = size >> 1;
234            while bit != 0 && reversed & bit != 0 {
235                reversed ^= bit;
236                bit >>= 1;
237            }
238            reversed |= bit;
239
240            debug_assert!(index < size);
241        }
242
243        table
244    }
245
246    /// Reorder `data` into bit-reversed order using the planned table.
247    fn permute(&self, data: &mut [Complex<T>]) {
248        for (index, &target) in self.bit_reversal.iter().enumerate() {
249            if target > index {
250                data.swap(index, target);
251            }
252        }
253    }
254
255    /// The log2(n) butterfly stages, in place, over bit-reversed input.
256    fn butterflies(&self, data: &mut [Complex<T>]) {
257        let n = data.len();
258        let mut size = 2;
259
260        while size <= n {
261            let half = size / 2;
262            let step = n / size;
263
264            for block in (0..n).step_by(size) {
265                for offset in 0..half {
266                    let Some(&twiddle) = self.twiddles.get(offset * step) else {
267                        continue;
268                    };
269                    let Some(&even) = data.get(block + offset) else {
270                        continue;
271                    };
272                    let Some(&odd) = data.get(block + offset + half) else {
273                        continue;
274                    };
275                    let odd = odd * twiddle;
276
277                    if let Some(slot) = data.get_mut(block + offset) {
278                        *slot = even + odd;
279                    }
280                    if let Some(slot) = data.get_mut(block + offset + half) {
281                        *slot = even - odd;
282                    }
283                }
284            }
285
286            size *= 2;
287        }
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    #![expect(
294        clippy::cast_precision_loss,
295        clippy::cast_possible_truncation,
296        reason = "the reference DFT and the test signal generator are written straight from the definition, and narrowing to f32 is the point of one of the tests"
297    )]
298
299    use super::*;
300
301    /// The O(n^2) definition, used as the reference the fast path is checked
302    /// against. Deliberately written straight from the formula.
303    fn naive_dft(signal: &[Complex<f64>]) -> Vec<Complex<f64>> {
304        let n = signal.len();
305        let base = -2.0 * std::f64::consts::PI / n as f64;
306
307        (0..n)
308            .map(|k| {
309                let mut sum = Complex::new(0.0, 0.0);
310                for (index, &sample) in signal.iter().enumerate() {
311                    let angle = base * (k * index) as f64;
312                    let (sin, cos) = angle.sin_cos();
313
314                    sum += sample * Complex::new(cos, sin);
315                }
316
317                sum
318            })
319            .collect()
320    }
321
322    /// A deterministic pseudo-random signal, so a failure reproduces.
323    fn signal(n: usize) -> Vec<Complex<f64>> {
324        let mut state = 0x2545_F491_4F6C_DD1D_u64;
325        let mut next = || {
326            state ^= state << 13;
327            state ^= state >> 7;
328            state ^= state << 17;
329
330            (state >> 11) as f64 / (1_u64 << 53) as f64 - 0.5
331        };
332
333        (0..n).map(|_| Complex::new(next(), next())).collect()
334    }
335
336    #[test]
337    fn rejects_non_power_of_two() {
338        assert_eq!(Fft::<f64>::new(6), Err(FftError::NotPowerOfTwo { size: 6 }));
339        assert_eq!(Fft::<f64>::new(0), Err(FftError::NotPowerOfTwo { size: 0 }));
340    }
341
342    #[test]
343    fn rejects_a_buffer_of_the_wrong_length() {
344        let plan = Fft::<f64>::new(8).expect("8 is a power of two");
345        let mut data = vec![Complex::new(0.0, 0.0); 4];
346
347        assert_eq!(
348            plan.transform_in_place(&mut data),
349            Err(FftError::LengthMismatch {
350                expected: 8,
351                actual: 4
352            })
353        );
354    }
355
356    #[test]
357    fn matches_the_naive_dft() {
358        for bits in 1..=10 {
359            let n = 1_usize << bits;
360            let input = signal(n);
361            let expected = naive_dft(&input);
362
363            let plan = Fft::<f64>::new(n).expect("a power of two");
364            let actual = plan.transform(&input).expect("matching length");
365
366            for (bin, (a, b)) in expected.iter().zip(&actual).enumerate() {
367                assert!((*a - *b).norm() < 1e-9, "n = {n}, bin {bin}: {a} != {b}");
368            }
369        }
370    }
371
372    #[test]
373    fn matches_the_naive_dft_in_f32() {
374        let n = 256;
375        let input = signal(n);
376        let expected = naive_dft(&input);
377
378        let narrowed: Vec<Complex<f32>> = input
379            .iter()
380            .map(|z| Complex::new(z.re as f32, z.im as f32))
381            .collect();
382
383        let plan = Fft::<f32>::new(n).expect("a power of two");
384        let actual = plan.transform(&narrowed).expect("matching length");
385
386        for (bin, (a, b)) in expected.iter().zip(&actual).enumerate() {
387            let widened = Complex::new(f64::from(b.re), f64::from(b.im));
388
389            assert!((*a - widened).norm() < 1e-3, "bin {bin}: {a} != {widened}");
390        }
391    }
392
393    #[test]
394    fn round_trips_through_the_inverse() {
395        let n = 512;
396        let input = signal(n);
397
398        let plan = Fft::<f64>::new(n).expect("a power of two");
399        let mut data = input.clone();
400
401        plan.transform_in_place(&mut data).expect("forward");
402        plan.inverse_in_place(&mut data).expect("inverse");
403
404        for (index, (a, b)) in input.iter().zip(&data).enumerate() {
405            assert!((*a - *b).norm() < 1e-12, "sample {index}: {a} != {b}");
406        }
407    }
408
409    #[test]
410    fn preserves_energy() {
411        let n = 256;
412        let input = signal(n);
413
414        let plan = Fft::<f64>::new(n).expect("a power of two");
415        let spectrum = plan.transform(&input).expect("matching length");
416
417        let time: f64 = input.iter().map(|z| z.norm_sqr()).sum();
418        let frequency: f64 = spectrum.iter().map(|z| z.norm_sqr()).sum::<f64>() / n as f64;
419
420        assert!(
421            (time - frequency).abs() < 1e-9,
422            "Parseval: {time} != {frequency}"
423        );
424    }
425
426    #[test]
427    fn is_linear() {
428        let n = 64;
429        let a = signal(n);
430        let b: Vec<Complex<f64>> = signal(n)
431            .iter()
432            .map(|z| *z * Complex::new(2.0, 1.0))
433            .collect();
434
435        let plan = Fft::<f64>::new(n).expect("a power of two");
436
437        let sum: Vec<Complex<f64>> = a.iter().zip(&b).map(|(x, y)| *x + *y).collect();
438        let transformed_sum = plan.transform(&sum).expect("matching length");
439
440        let sum_of_transforms: Vec<Complex<f64>> = plan
441            .transform(&a)
442            .expect("matching length")
443            .iter()
444            .zip(&plan.transform(&b).expect("matching length"))
445            .map(|(x, y)| *x + *y)
446            .collect();
447
448        for (x, y) in transformed_sum.iter().zip(&sum_of_transforms) {
449            assert!((*x - *y).norm() < 1e-9);
450        }
451    }
452
453    #[test]
454    fn an_impulse_has_a_flat_spectrum() {
455        let n = 32;
456        let plan = Fft::<f64>::new(n).expect("a power of two");
457
458        let mut input = vec![Complex::new(0.0, 0.0); n];
459        input[0] = Complex::new(1.0, 0.0);
460
461        let spectrum = plan.transform(&input).expect("matching length");
462        for bin in &spectrum {
463            assert!((bin.norm() - 1.0).abs() < 1e-12);
464        }
465    }
466
467    #[test]
468    fn a_sinusoid_lands_in_one_bin() {
469        let n = 64;
470        let k = 7;
471        let plan = Fft::<f64>::new(n).expect("a power of two");
472
473        let input: Vec<Complex<f64>> = (0..n)
474            .map(|index| {
475                let angle = 2.0 * std::f64::consts::PI * (k * index) as f64 / n as f64;
476                let (sin, cos) = angle.sin_cos();
477
478                Complex::new(cos, sin)
479            })
480            .collect();
481
482        let spectrum = plan.transform(&input).expect("matching length");
483
484        for (bin, value) in spectrum.iter().enumerate() {
485            let expected = if bin == k { n as f64 } else { 0.0 };
486
487            assert!(
488                (value.norm() - expected).abs() < 1e-9,
489                "bin {bin} held {value}"
490            );
491        }
492    }
493
494    #[test]
495    fn real_and_complex_paths_agree() {
496        let n = 128;
497        let real: Vec<f64> = signal(n).iter().map(|z| z.re).collect();
498        let widened: Vec<Complex<f64>> = real.iter().map(|&x| Complex::new(x, 0.0)).collect();
499
500        let plan = Fft::<f64>::new(n).expect("a power of two");
501
502        let from_real = plan.transform_real(&real).expect("matching length");
503        let from_complex = plan.transform(&widened).expect("matching length");
504
505        for (a, b) in from_real.iter().zip(&from_complex) {
506            assert!((*a - *b).norm() < 1e-12);
507        }
508    }
509}