| 1 |
//! To test the accuracy of our FFT algorithm, we first test that our |
| 2 |
//! naive Dft function is correct by comparing its output against several |
| 3 |
//! known signal/spectrum relationships. Then, we generate random signals |
| 4 |
//! for a variety of lengths, and test that our FFT algorithm matches our |
| 5 |
//! Dft calculation for those signals. |
| 6 |
|
| 7 |
use std::sync::Arc; |
| 8 |
|
| 9 |
use num_traits::Float; |
| 10 |
use rustfft::{ |
| 11 |
algorithm::{BluesteinsAlgorithm, Radix4}, |
| 12 |
num_complex::Complex, |
| 13 |
Fft, FftNum, FftPlanner, |
| 14 |
}; |
| 15 |
use rustfft::{num_traits::Zero, FftDirection}; |
| 16 |
|
| 17 |
use rand::distributions::{uniform::SampleUniform, Distribution, Uniform}; |
| 18 |
use rand::{rngs::StdRng, SeedableRng}; |
| 19 |
|
| 20 |
/// The seed for the random number generator used to generate |
| 21 |
/// random signals. It's defined here so that we have deterministic |
| 22 |
/// tests |
| 23 |
const RNG_SEED: [u8; 32] = [ |
| 24 |
1, 9, 1, 0, 1, 1, 4, 3, 1, 4, 9, 8, 4, 1, 4, 8, 2, 8, 1, 2, 2, 2, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, |
| 25 |
]; |
| 26 |
|
| 27 |
/// Returns true if the mean difference in the elements of the two vectors |
| 28 |
/// is small |
| 29 |
fn compare_vectors<T: rustfft::FftNum + Float>(vec1: &[Complex<T>], vec2: &[Complex<T>]) -> bool { |
| 30 |
assert_eq!(vec1.len(), vec2.len()); |
| 31 |
let mut error = T::zero(); |
| 32 |
for (&a, &b) in vec1.iter().zip(vec2.iter()) { |
| 33 |
error = error + (a - b).norm(); |
| 34 |
} |
| 35 |
return (error / T::from_usize(vec1.len()).unwrap()) < T::from_f32(0.1).unwrap(); |
| 36 |
} |
| 37 |
|
| 38 |
fn fft_matches_control<T: FftNum + Float>(control: Arc<dyn Fft<T>>, input: &[Complex<T>]) -> bool { |
| 39 |
let mut control_input = input.to_vec(); |
| 40 |
let mut test_input = input.to_vec(); |
| 41 |
|
| 42 |
let mut planner = FftPlanner::new(); |
| 43 |
let fft = planner.plan_fft(control.len(), control.fft_direction()); |
| 44 |
assert_eq!( |
| 45 |
fft.len(), |
| 46 |
control.len(), |
| 47 |
"FFTplanner created FFT of wrong length" |
| 48 |
); |
| 49 |
assert_eq!( |
| 50 |
fft.fft_direction(), |
| 51 |
control.fft_direction(), |
| 52 |
"FFTplanner created FFT of wrong direction" |
| 53 |
); |
| 54 |
|
| 55 |
let scratch_max = std::cmp::max( |
| 56 |
control.get_inplace_scratch_len(), |
| 57 |
fft.get_inplace_scratch_len(), |
| 58 |
); |
| 59 |
let mut scratch = vec![Zero::zero(); scratch_max]; |
| 60 |
|
| 61 |
control.process_with_scratch(&mut control_input, &mut scratch); |
| 62 |
fft.process_with_scratch(&mut test_input, &mut scratch); |
| 63 |
|
| 64 |
return compare_vectors(&test_input, &control_input); |
| 65 |
} |
| 66 |
|
| 67 |
fn random_signal<T: FftNum + SampleUniform>(length: usize) -> Vec<Complex<T>> { |
| 68 |
let mut sig = Vec::with_capacity(length); |
| 69 |
let dist: Uniform<T> = Uniform::new(T::zero(), T::from_f64(10.0).unwrap()); |
| 70 |
let mut rng: StdRng = SeedableRng::from_seed(RNG_SEED); |
| 71 |
for _ in 0..length { |
| 72 |
sig.push(Complex { |
| 73 |
re: (dist.sample(&mut rng)), |
| 74 |
im: (dist.sample(&mut rng)), |
| 75 |
}); |
| 76 |
} |
| 77 |
return sig; |
| 78 |
} |
| 79 |
|
| 80 |
// A cache that makes setup for integration tests faster |
| 81 |
struct ControlCache<T: FftNum> { |
| 82 |
fft_cache: Vec<Arc<dyn Fft<T>>>, |
| 83 |
} |
| 84 |
impl<T: FftNum> ControlCache<T> { |
| 85 |
pub fn new(max_outer_len: usize, direction: FftDirection) -> Self { |
| 86 |
let max_inner_len = (max_outer_len * 2 - 1).checked_next_power_of_two().unwrap(); |
| 87 |
let max_power = max_inner_len.trailing_zeros() as usize; |
| 88 |
|
| 89 |
Self { |
| 90 |
fft_cache: (0..=max_power) |
| 91 |
.map(|i| { |
| 92 |
let len = 1 << i; |
| 93 |
Arc::new(Radix4::new(len, direction)) as Arc<dyn Fft<_>> |
| 94 |
}) |
| 95 |
.collect(), |
| 96 |
} |
| 97 |
} |
| 98 |
|
| 99 |
pub fn plan_fft(&self, len: usize) -> Arc<dyn Fft<T>> { |
| 100 |
let inner_fft_len = (len * 2 - 1).checked_next_power_of_two().unwrap(); |
| 101 |
let inner_fft_index = inner_fft_len.trailing_zeros() as usize; |
| 102 |
let inner_fft = Arc::clone(&self.fft_cache[inner_fft_index]); |
| 103 |
Arc::new(BluesteinsAlgorithm::new(len, inner_fft)) |
| 104 |
} |
| 105 |
} |
| 106 |
|
| 107 |
const TEST_MAX: usize = 1001; |
| 108 |
|
| 109 |
/// Integration tests that verify our FFT output matches the direct Dft calculation |
| 110 |
/// for random signals. |
| 111 |
#[test] |
| 112 |
fn test_planned_fft_forward_f32() { |
| 113 |
let direction = FftDirection::Forward; |
| 114 |
let cache: ControlCache<f32> = ControlCache::new(TEST_MAX, direction); |
| 115 |
|
| 116 |
for len in 1..TEST_MAX { |
| 117 |
let control = cache.plan_fft(len); |
| 118 |
assert_eq!(control.len(), len); |
| 119 |
assert_eq!(control.fft_direction(), direction); |
| 120 |
|
| 121 |
let signal = random_signal(len); |
| 122 |
assert!(fft_matches_control(control, &signal), "length = {}", len); |
| 123 |
} |
| 124 |
} |
| 125 |
|
| 126 |
#[test] |
| 127 |
fn test_planned_fft_inverse_f32() { |
| 128 |
let direction = FftDirection::Inverse; |
| 129 |
let cache: ControlCache<f32> = ControlCache::new(TEST_MAX, direction); |
| 130 |
|
| 131 |
for len in 1..TEST_MAX { |
| 132 |
let control = cache.plan_fft(len); |
| 133 |
assert_eq!(control.len(), len); |
| 134 |
assert_eq!(control.fft_direction(), direction); |
| 135 |
|
| 136 |
let signal = random_signal(len); |
| 137 |
assert!(fft_matches_control(control, &signal), "length = {}", len); |
| 138 |
} |
| 139 |
} |
| 140 |
|
| 141 |
#[test] |
| 142 |
fn test_planned_fft_forward_f64() { |
| 143 |
let direction = FftDirection::Forward; |
| 144 |
let cache: ControlCache<f64> = ControlCache::new(TEST_MAX, direction); |
| 145 |
|
| 146 |
for len in 1..TEST_MAX { |
| 147 |
let control = cache.plan_fft(len); |
| 148 |
assert_eq!(control.len(), len); |
| 149 |
assert_eq!(control.fft_direction(), direction); |
| 150 |
|
| 151 |
let signal = random_signal(len); |
| 152 |
assert!(fft_matches_control(control, &signal), "length = {}", len); |
| 153 |
} |
| 154 |
} |
| 155 |
|
| 156 |
#[test] |
| 157 |
fn test_planned_fft_inverse_f64() { |
| 158 |
let direction = FftDirection::Inverse; |
| 159 |
let cache: ControlCache<f64> = ControlCache::new(TEST_MAX, direction); |
| 160 |
|
| 161 |
for len in 1..TEST_MAX { |
| 162 |
let control = cache.plan_fft(len); |
| 163 |
assert_eq!(control.len(), len); |
| 164 |
assert_eq!(control.fft_direction(), direction); |
| 165 |
|
| 166 |
let signal = random_signal(len); |
| 167 |
assert!(fft_matches_control(control, &signal), "length = {}", len); |
| 168 |
} |
| 169 |
} |