Debian Codegraph @

.cargo/vendor/rustfft/tests/accuracy.rs

raw
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 }