Debian Codegraph @

.cargo/vendor/rustfft/src/algorithm/dft.rs

raw
1 use num_complex::Complex;
2 use num_traits::Zero;
3
4 use crate::array_utils;
5 use crate::common::{fft_error_inplace, fft_error_outofplace};
6 use crate::{twiddles, FftDirection};
7 use crate::{Direction, Fft, FftNum, Length};
8
9 /// Naive O(n^2 ) Discrete Fourier Transform implementation
10 ///
11 /// This implementation is primarily used to test other FFT algorithms.
12 ///
13 /// ~~~
14 /// // Computes a naive DFT of size 123
15 /// use rustfft::algorithm::Dft;
16 /// use rustfft::{Fft, FftDirection};
17 /// use rustfft::num_complex::Complex;
18 ///
19 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 123];
20 ///
21 /// let dft = Dft::new(123, FftDirection::Forward);
22 /// dft.process(&mut buffer);
23 /// ~~~
24 pub struct Dft<T> {
25 twiddles: Vec<Complex<T>>,
26 direction: FftDirection,
27 }
28
29 impl<T: FftNum> Dft<T> {
30 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute Dft
31 pub fn new(len: usize, direction: FftDirection) -> Self {
32 let twiddles = (0..len)
33 .map(|i| twiddles::compute_twiddle(i, len, direction))
34 .collect();
35 Self {
36 twiddles,
37 direction,
38 }
39 }
40
41 fn perform_fft_out_of_place(
42 &self,
43 signal: &[Complex<T>],
44 spectrum: &mut [Complex<T>],
45 _scratch: &mut [Complex<T>],
46 ) {
47 for k in 0..spectrum.len() {
48 let output_cell = spectrum.get_mut(k).unwrap();
49
50 *output_cell = Zero::zero();
51 let mut twiddle_index = 0;
52
53 for input_cell in signal {
54 let twiddle = self.twiddles[twiddle_index];
55 *output_cell = *output_cell + twiddle * input_cell;
56
57 twiddle_index += k;
58 if twiddle_index >= self.twiddles.len() {
59 twiddle_index -= self.twiddles.len();
60 }
61 }
62 }
63 }
64 }
65 boilerplate_fft_oop!(Dft, |this: &Dft<_>| this.twiddles.len());
66
67 #[cfg(test)]
68 mod unit_tests {
69 use super::*;
70 use crate::test_utils::{compare_vectors, random_signal};
71 use num_complex::Complex;
72 use num_traits::Zero;
73 use std::f32;
74
75 fn dft(signal: &[Complex<f32>], spectrum: &mut [Complex<f32>]) {
76 for (k, spec_bin) in spectrum.iter_mut().enumerate() {
77 let mut sum = Zero::zero();
78 for (i, &x) in signal.iter().enumerate() {
79 let angle = -1f32 * (i * k) as f32 * 2f32 * f32::consts::PI / signal.len() as f32;
80 let twiddle = Complex::from_polar(1f32, angle);
81
82 sum = sum + twiddle * x;
83 }
84 *spec_bin = sum;
85 }
86 }
87
88 #[test]
89 fn test_matches_dft() {
90 let n = 4;
91
92 for len in 1..20 {
93 let dft_instance = Dft::new(len, FftDirection::Forward);
94 assert_eq!(
95 dft_instance.len(),
96 len,
97 "Dft instance reported incorrect length"
98 );
99
100 let input = random_signal(len * n);
101 let mut expected_output = input.clone();
102
103 // Compute the control data using our simplified Dft definition
104 for (input_chunk, output_chunk) in
105 input.chunks(len).zip(expected_output.chunks_mut(len))
106 {
107 dft(input_chunk, output_chunk);
108 }
109
110 // test process()
111 {
112 let mut inplace_buffer = input.clone();
113
114 dft_instance.process(&mut inplace_buffer);
115
116 assert!(
117 compare_vectors(&expected_output, &inplace_buffer),
118 "process() failed, length = {}",
119 len
120 );
121 }
122
123 // test process_with_scratch()
124 {
125 let mut inplace_with_scratch_buffer = input.clone();
126 let mut inplace_scratch =
127 vec![Zero::zero(); dft_instance.get_inplace_scratch_len()];
128
129 dft_instance
130 .process_with_scratch(&mut inplace_with_scratch_buffer, &mut inplace_scratch);
131
132 assert!(
133 compare_vectors(&expected_output, &inplace_with_scratch_buffer),
134 "process_inplace() failed, length = {}",
135 len
136 );
137
138 // one more thing: make sure that the Dft algorithm even works with dirty scratch space
139 for item in inplace_scratch.iter_mut() {
140 *item = Complex::new(100.0, 100.0);
141 }
142 inplace_with_scratch_buffer.copy_from_slice(&input);
143
144 dft_instance
145 .process_with_scratch(&mut inplace_with_scratch_buffer, &mut inplace_scratch);
146
147 assert!(
148 compare_vectors(&expected_output, &inplace_with_scratch_buffer),
149 "process_with_scratch() failed the 'dirty scratch' test for len = {}",
150 len
151 );
152 }
153
154 // test process_outofplace_with_scratch
155 {
156 let mut outofplace_input = input.clone();
157 let mut outofplace_output = expected_output.clone();
158
159 dft_instance.process_outofplace_with_scratch(
160 &mut outofplace_input,
161 &mut outofplace_output,
162 &mut [],
163 );
164
165 assert!(
166 compare_vectors(&expected_output, &outofplace_output),
167 "process_outofplace_with_scratch() failed, length = {}",
168 len
169 );
170 }
171 }
172
173 //verify that it doesn't crash or infinite loop if we have a length of 0
174 let zero_dft = Dft::new(0, FftDirection::Forward);
175 let mut zero_input: Vec<Complex<f32>> = Vec::new();
176 let mut zero_output: Vec<Complex<f32>> = Vec::new();
177 let mut zero_scratch: Vec<Complex<f32>> = Vec::new();
178
179 zero_dft.process(&mut zero_input);
180 zero_dft.process_with_scratch(&mut zero_input, &mut zero_scratch);
181 zero_dft.process_outofplace_with_scratch(
182 &mut zero_input,
183 &mut zero_output,
184 &mut zero_scratch,
185 );
186 }
187
188 /// Returns true if our `dft` function calculates the given output from the
189 /// given input, and if rustfft's Dft struct does the same
190 fn test_dft_correct(input: &[Complex<f32>], expected_output: &[Complex<f32>]) {
191 assert_eq!(input.len(), expected_output.len());
192 let len = input.len();
193
194 let mut reference_output = vec![Zero::zero(); len];
195 dft(&input, &mut reference_output);
196 assert!(
197 compare_vectors(expected_output, &reference_output),
198 "Reference implementation failed for len={}",
199 len
200 );
201
202 let dft_instance = Dft::new(len, FftDirection::Forward);
203
204 // test process()
205 {
206 let mut inplace_buffer = input.to_vec();
207
208 dft_instance.process(&mut inplace_buffer);
209
210 assert!(
211 compare_vectors(&expected_output, &inplace_buffer),
212 "process() failed, length = {}",
213 len
214 );
215 }
216
217 // test process_with_scratch()
218 {
219 let mut inplace_with_scratch_buffer = input.to_vec();
220 let mut inplace_scratch = vec![Zero::zero(); dft_instance.get_inplace_scratch_len()];
221
222 dft_instance
223 .process_with_scratch(&mut inplace_with_scratch_buffer, &mut inplace_scratch);
224
225 assert!(
226 compare_vectors(&expected_output, &inplace_with_scratch_buffer),
227 "process_inplace() failed, length = {}",
228 len
229 );
230
231 // one more thing: make sure that the Dft algorithm even works with dirty scratch space
232 for item in inplace_scratch.iter_mut() {
233 *item = Complex::new(100.0, 100.0);
234 }
235 inplace_with_scratch_buffer.copy_from_slice(&input);
236
237 dft_instance
238 .process_with_scratch(&mut inplace_with_scratch_buffer, &mut inplace_scratch);
239
240 assert!(
241 compare_vectors(&expected_output, &inplace_with_scratch_buffer),
242 "process_with_scratch() failed the 'dirty scratch' test for len = {}",
243 len
244 );
245 }
246
247 // test process_outofplace_with_scratch
248 {
249 let mut outofplace_input = input.to_vec();
250 let mut outofplace_output = expected_output.to_vec();
251
252 dft_instance.process_outofplace_with_scratch(
253 &mut outofplace_input,
254 &mut outofplace_output,
255 &mut [],
256 );
257
258 assert!(
259 compare_vectors(&expected_output, &outofplace_output),
260 "process_outofplace_with_scratch() failed, length = {}",
261 len
262 );
263 }
264 }
265
266 #[test]
267 fn test_dft_known_len_2() {
268 let signal = [
269 Complex { re: 1f32, im: 0f32 },
270 Complex {
271 re: -1f32,
272 im: 0f32,
273 },
274 ];
275 let spectrum = [
276 Complex { re: 0f32, im: 0f32 },
277 Complex { re: 2f32, im: 0f32 },
278 ];
279 test_dft_correct(&signal[..], &spectrum[..]);
280 }
281
282 #[test]
283 fn test_dft_known_len_3() {
284 let signal = [
285 Complex { re: 1f32, im: 1f32 },
286 Complex {
287 re: 2f32,
288 im: -3f32,
289 },
290 Complex {
291 re: -1f32,
292 im: 4f32,
293 },
294 ];
295 let spectrum = [
296 Complex { re: 2f32, im: 2f32 },
297 Complex {
298 re: -5.562177f32,
299 im: -2.098076f32,
300 },
301 Complex {
302 re: 6.562178f32,
303 im: 3.09807f32,
304 },
305 ];
306 test_dft_correct(&signal[..], &spectrum[..]);
307 }
308
309 #[test]
310 fn test_dft_known_len_4() {
311 let signal = [
312 Complex { re: 0f32, im: 1f32 },
313 Complex {
314 re: 2.5f32,
315 im: -3f32,
316 },
317 Complex {
318 re: -1f32,
319 im: -1f32,
320 },
321 Complex { re: 4f32, im: 0f32 },
322 ];
323 let spectrum = [
324 Complex {
325 re: 5.5f32,
326 im: -3f32,
327 },
328 Complex {
329 re: -2f32,
330 im: 3.5f32,
331 },
332 Complex {
333 re: -7.5f32,
334 im: 3f32,
335 },
336 Complex {
337 re: 4f32,
338 im: 0.5f32,
339 },
340 ];
341 test_dft_correct(&signal[..], &spectrum[..]);
342 }
343
344 #[test]
345 fn test_dft_known_len_6() {
346 let signal = [
347 Complex { re: 1f32, im: 1f32 },
348 Complex { re: 2f32, im: 2f32 },
349 Complex { re: 3f32, im: 3f32 },
350 Complex { re: 4f32, im: 4f32 },
351 Complex { re: 5f32, im: 5f32 },
352 Complex { re: 6f32, im: 6f32 },
353 ];
354 let spectrum = [
355 Complex {
356 re: 21f32,
357 im: 21f32,
358 },
359 Complex {
360 re: -8.16f32,
361 im: 2.16f32,
362 },
363 Complex {
364 re: -4.76f32,
365 im: -1.24f32,
366 },
367 Complex {
368 re: -3f32,
369 im: -3f32,
370 },
371 Complex {
372 re: -1.24f32,
373 im: -4.76f32,
374 },
375 Complex {
376 re: 2.16f32,
377 im: -8.16f32,
378 },
379 ];
380 test_dft_correct(&signal[..], &spectrum[..]);
381 }
382 }