1use 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#[derive(Debug, PartialEq, Eq, Clone, Copy)]
40pub enum FftError {
41 NotPowerOfTwo { size: usize },
43 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#[derive(Debug, Clone, PartialEq)]
68pub struct Fft<T> {
69 twiddles: Vec<Complex<T>>,
71 bit_reversal: Vec<usize>,
73 size: usize,
74}
75
76impl<T: Float> Fft<T> {
77 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 #[must_use]
97 #[inline]
98 pub const fn size(&self) -> usize {
99 self.size
100 }
101
102 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 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 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 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 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 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 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 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 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 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 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 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}