Debian Codegraph @

.cargo/vendor/rustfft/src/plan.rs

raw
1 use num_integer::gcd;
2 use std::collections::HashMap;
3 use std::sync::Arc;
4
5 use crate::wasm_simd::wasm_simd_planner::FftPlannerWasmSimd;
6 use crate::{common::FftNum, fft_cache::FftCache, FftDirection};
7
8 use crate::algorithm::butterflies::*;
9 use crate::algorithm::*;
10 use crate::Fft;
11
12 use crate::FftPlannerAvx;
13 use crate::FftPlannerNeon;
14 use crate::FftPlannerSse;
15
16 use crate::math_utils::{PrimeFactor, PrimeFactors};
17
18 enum ChosenFftPlanner<T: FftNum> {
19 Scalar(FftPlannerScalar<T>),
20 Avx(FftPlannerAvx<T>),
21 Sse(FftPlannerSse<T>),
22 Neon(FftPlannerNeon<T>),
23 WasmSimd(FftPlannerWasmSimd<T>),
24 // todo: If we add NEON, avx-512 etc support, add more enum variants for them here
25 }
26
27 /// The FFT planner creates new FFT algorithm instances.
28 ///
29 /// RustFFT has several FFT algorithms available. For a given FFT size, the `FftPlanner` decides which of the
30 /// available FFT algorithms to use and then initializes them.
31 ///
32 /// ~~~
33 /// // Perform a forward Fft of size 1234
34 /// use std::sync::Arc;
35 /// use rustfft::{FftPlanner, num_complex::Complex};
36 ///
37 /// let mut planner = FftPlanner::new();
38 /// let fft = planner.plan_fft_forward(1234);
39 ///
40 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234];
41 /// fft.process(&mut buffer);
42 ///
43 /// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`,
44 /// // where T is the numeric type, ie f32 or f64, so it's cheap to clone
45 /// let fft_clone = Arc::clone(&fft);
46 /// ~~~
47 ///
48 /// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This
49 /// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing
50 /// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created
51 /// by a different planner)
52 ///
53 /// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly
54 /// safe to drop the planner after creating Fft instances.
55 ///
56 /// In the constructor, the FftPlanner will detect available CPU features. If AVX, SSE, Neon, or WASM SIMD are available, it will set itself up to plan FFTs with the fastest available instruction set.
57 /// If no SIMD instruction sets are available, the planner will seamlessly fall back to planning non-SIMD FFTs.
58 ///
59 /// If you'd prefer not to compute a FFT at all if a certain SIMD instruction set isn't available, or otherwise specify your own custom fallback, RustFFT exposes dedicated planners for each instruction set:
60 /// - [`FftPlannerAvx`](crate::FftPlannerAvx)
61 /// - [`FftPlannerSse`](crate::FftPlannerSse)
62 /// - [`FftPlannerNeon`](crate::FftPlannerNeon)
63 /// - [`FftPlannerWasmSimd`](crate::FftPlannerWasmSimd)
64 ///
65 /// If you'd prefer to opt out of SIMD algorithms, consider creating a [`FftPlannerScalar`](crate::FftPlannerScalar) instead.
66 pub struct FftPlanner<T: FftNum> {
67 chosen_planner: ChosenFftPlanner<T>,
68 }
69 impl<T: FftNum> FftPlanner<T> {
70 /// Creates a new `FftPlanner` instance.
71 pub fn new() -> Self {
72 if let Ok(avx_planner) = FftPlannerAvx::new() {
73 Self {
74 chosen_planner: ChosenFftPlanner::Avx(avx_planner),
75 }
76 } else if let Ok(sse_planner) = FftPlannerSse::new() {
77 Self {
78 chosen_planner: ChosenFftPlanner::Sse(sse_planner),
79 }
80 } else if let Ok(neon_planner) = FftPlannerNeon::new() {
81 Self {
82 chosen_planner: ChosenFftPlanner::Neon(neon_planner),
83 }
84 } else if let Ok(wasm_simd_planner) = FftPlannerWasmSimd::new() {
85 Self {
86 chosen_planner: ChosenFftPlanner::WasmSimd(wasm_simd_planner),
87 }
88 } else {
89 Self {
90 chosen_planner: ChosenFftPlanner::Scalar(FftPlannerScalar::new()),
91 }
92 }
93 }
94
95 /// Returns a `Fft` instance which computes FFTs of size `len`.
96 ///
97 /// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs.
98 ///
99 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
100 pub fn plan_fft(&mut self, len: usize, direction: FftDirection) -> Arc<dyn Fft<T>> {
101 match &mut self.chosen_planner {
102 ChosenFftPlanner::Scalar(scalar_planner) => scalar_planner.plan_fft(len, direction),
103 ChosenFftPlanner::Avx(avx_planner) => avx_planner.plan_fft(len, direction),
104 ChosenFftPlanner::Sse(sse_planner) => sse_planner.plan_fft(len, direction),
105 ChosenFftPlanner::Neon(neon_planner) => neon_planner.plan_fft(len, direction),
106 ChosenFftPlanner::WasmSimd(wasm_simd_planner) => {
107 wasm_simd_planner.plan_fft(len, direction)
108 }
109 }
110 }
111
112 /// Returns a `Fft` instance which computes forward FFTs of size `len`
113 ///
114 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
115 pub fn plan_fft_forward(&mut self, len: usize) -> Arc<dyn Fft<T>> {
116 self.plan_fft(len, FftDirection::Forward)
117 }
118
119 /// Returns a `Fft` instance which computes inverse FFTs of size `len`
120 ///
121 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
122 pub fn plan_fft_inverse(&mut self, len: usize) -> Arc<dyn Fft<T>> {
123 self.plan_fft(len, FftDirection::Inverse)
124 }
125 }
126
127 const MIN_RADIX4_BITS: u32 = 5; // smallest size to consider radix 4 an option is 2^5 = 32
128 const MIN_RADIX3_FACTORS: u32 = 4; // smallest number of factors of 3 to consider radix 4 an option is 3^4=81. any smaller and we want to use butterflies directly.
129 const MAX_RADER_PRIME_FACTOR: usize = 23; // don't use Raders if the inner fft length has prime factor larger than this
130 const MIN_BLUESTEIN_MIXED_RADIX_LEN: usize = 90; // only use mixed radix for the inner fft of Bluestein if length is larger than this
131
132 /// A Recipe is a structure that describes the design of a FFT, without actually creating it.
133 /// It is used as a middle step in the planning process.
134 #[derive(Debug, PartialEq, Clone)]
135 pub enum Recipe {
136 Dft(usize),
137 MixedRadix {
138 left_fft: Arc<Recipe>,
139 right_fft: Arc<Recipe>,
140 },
141 #[allow(dead_code)]
142 GoodThomasAlgorithm {
143 left_fft: Arc<Recipe>,
144 right_fft: Arc<Recipe>,
145 },
146 MixedRadixSmall {
147 left_fft: Arc<Recipe>,
148 right_fft: Arc<Recipe>,
149 },
150 GoodThomasAlgorithmSmall {
151 left_fft: Arc<Recipe>,
152 right_fft: Arc<Recipe>,
153 },
154 RadersAlgorithm {
155 inner_fft: Arc<Recipe>,
156 },
157 BluesteinsAlgorithm {
158 len: usize,
159 inner_fft: Arc<Recipe>,
160 },
161 Radix3(usize),
162 Radix4(usize),
163 Butterfly2,
164 Butterfly3,
165 Butterfly4,
166 Butterfly5,
167 Butterfly6,
168 Butterfly7,
169 Butterfly8,
170 Butterfly9,
171 Butterfly11,
172 Butterfly13,
173 Butterfly16,
174 Butterfly17,
175 Butterfly19,
176 Butterfly23,
177 Butterfly27,
178 Butterfly29,
179 Butterfly31,
180 Butterfly32,
181 }
182
183 impl Recipe {
184 pub fn len(&self) -> usize {
185 match self {
186 Recipe::Dft(length) => *length,
187 Recipe::Radix3(length) => *length,
188 Recipe::Radix4(length) => *length,
189 Recipe::Butterfly2 => 2,
190 Recipe::Butterfly3 => 3,
191 Recipe::Butterfly4 => 4,
192 Recipe::Butterfly5 => 5,
193 Recipe::Butterfly6 => 6,
194 Recipe::Butterfly7 => 7,
195 Recipe::Butterfly8 => 8,
196 Recipe::Butterfly9 => 9,
197 Recipe::Butterfly11 => 11,
198 Recipe::Butterfly13 => 13,
199 Recipe::Butterfly16 => 16,
200 Recipe::Butterfly17 => 17,
201 Recipe::Butterfly19 => 19,
202 Recipe::Butterfly23 => 23,
203 Recipe::Butterfly27 => 27,
204 Recipe::Butterfly29 => 29,
205 Recipe::Butterfly31 => 31,
206 Recipe::Butterfly32 => 32,
207 Recipe::MixedRadix {
208 left_fft,
209 right_fft,
210 } => left_fft.len() * right_fft.len(),
211 Recipe::GoodThomasAlgorithm {
212 left_fft,
213 right_fft,
214 } => left_fft.len() * right_fft.len(),
215 Recipe::MixedRadixSmall {
216 left_fft,
217 right_fft,
218 } => left_fft.len() * right_fft.len(),
219 Recipe::GoodThomasAlgorithmSmall {
220 left_fft,
221 right_fft,
222 } => left_fft.len() * right_fft.len(),
223 Recipe::RadersAlgorithm { inner_fft } => inner_fft.len() + 1,
224 Recipe::BluesteinsAlgorithm { len, .. } => *len,
225 }
226 }
227 }
228
229 /// The Scalar FFT planner creates new FFT algorithm instances using non-SIMD algorithms.
230 ///
231 /// RustFFT has several FFT algorithms available. For a given FFT size, the `FftPlannerScalar` decides which of the
232 /// available FFT algorithms to use and then initializes them.
233 ///
234 /// Use `FftPlannerScalar` instead of [`FftPlanner`](crate::FftPlanner) or [`FftPlannerAvx`](crate::FftPlannerAvx) when you want to explicitly opt out of using any SIMD-accelerated algorithms.
235 ///
236 /// ~~~
237 /// // Perform a forward Fft of size 1234
238 /// use std::sync::Arc;
239 /// use rustfft::{FftPlannerScalar, num_complex::Complex};
240 ///
241 /// let mut planner = FftPlannerScalar::new();
242 /// let fft = planner.plan_fft_forward(1234);
243 ///
244 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234];
245 /// fft.process(&mut buffer);
246 ///
247 /// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`,
248 /// // where T is the numeric type, ie f32 or f64, so it's cheap to clone
249 /// let fft_clone = Arc::clone(&fft);
250 /// ~~~
251 ///
252 /// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This
253 /// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing
254 /// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created
255 /// by a different planner)
256 ///
257 /// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly
258 /// safe to drop the planner after creating Fft instances.
259 pub struct FftPlannerScalar<T: FftNum> {
260 algorithm_cache: FftCache<T>,
261 recipe_cache: HashMap<usize, Arc<Recipe>>,
262 }
263
264 impl<T: FftNum> FftPlannerScalar<T> {
265 /// Creates a new `FftPlannerScalar` instance.
266 pub fn new() -> Self {
267 Self {
268 algorithm_cache: FftCache::new(),
269 recipe_cache: HashMap::new(),
270 }
271 }
272
273 /// Returns a `Fft` instance which computes FFTs of size `len`.
274 ///
275 /// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs.
276 ///
277 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
278 pub fn plan_fft(&mut self, len: usize, direction: FftDirection) -> Arc<dyn Fft<T>> {
279 // Step 1: Create a "recipe" for this FFT, which will tell us exactly which combination of algorithms to use
280 let recipe = self.design_fft_for_len(len);
281
282 // Step 2: Use our recipe to construct a Fft trait object
283 self.build_fft(&recipe, direction)
284 }
285
286 /// Returns a `Fft` instance which computes forward FFTs of size `len`
287 ///
288 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
289 pub fn plan_fft_forward(&mut self, len: usize) -> Arc<dyn Fft<T>> {
290 self.plan_fft(len, FftDirection::Forward)
291 }
292
293 /// Returns a `Fft` instance which computes inverse FFTs of size `len`
294 ///
295 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
296 pub fn plan_fft_inverse(&mut self, len: usize) -> Arc<dyn Fft<T>> {
297 self.plan_fft(len, FftDirection::Inverse)
298 }
299
300 // Make a recipe for a length
301 fn design_fft_for_len(&mut self, len: usize) -> Arc<Recipe> {
302 if len < 2 {
303 Arc::new(Recipe::Dft(len))
304 } else if let Some(recipe) = self.recipe_cache.get(&len) {
305 Arc::clone(&recipe)
306 } else {
307 let factors = PrimeFactors::compute(len);
308 let recipe = self.design_fft_with_factors(len, factors);
309 self.recipe_cache.insert(len, Arc::clone(&recipe));
310 recipe
311 }
312 }
313
314 // Create the fft from a recipe, take from cache if possible
315 fn build_fft(&mut self, recipe: &Recipe, direction: FftDirection) -> Arc<dyn Fft<T>> {
316 let len = recipe.len();
317 if let Some(instance) = self.algorithm_cache.get(len, direction) {
318 instance
319 } else {
320 let fft = self.build_new_fft(recipe, direction);
321 self.algorithm_cache.insert(&fft);
322 fft
323 }
324 }
325
326 // Create a new fft from a recipe
327 fn build_new_fft(&mut self, recipe: &Recipe, direction: FftDirection) -> Arc<dyn Fft<T>> {
328 match recipe {
329 Recipe::Dft(len) => Arc::new(Dft::new(*len, direction)) as Arc<dyn Fft<T>>,
330 Recipe::Radix3(len) => Arc::new(Radix3::new(*len, direction)) as Arc<dyn Fft<T>>,
331 Recipe::Radix4(len) => Arc::new(Radix4::new(*len, direction)) as Arc<dyn Fft<T>>,
332 Recipe::Butterfly2 => Arc::new(Butterfly2::new(direction)) as Arc<dyn Fft<T>>,
333 Recipe::Butterfly3 => Arc::new(Butterfly3::new(direction)) as Arc<dyn Fft<T>>,
334 Recipe::Butterfly4 => Arc::new(Butterfly4::new(direction)) as Arc<dyn Fft<T>>,
335 Recipe::Butterfly5 => Arc::new(Butterfly5::new(direction)) as Arc<dyn Fft<T>>,
336 Recipe::Butterfly6 => Arc::new(Butterfly6::new(direction)) as Arc<dyn Fft<T>>,
337 Recipe::Butterfly7 => Arc::new(Butterfly7::new(direction)) as Arc<dyn Fft<T>>,
338 Recipe::Butterfly8 => Arc::new(Butterfly8::new(direction)) as Arc<dyn Fft<T>>,
339 Recipe::Butterfly9 => Arc::new(Butterfly9::new(direction)) as Arc<dyn Fft<T>>,
340 Recipe::Butterfly11 => Arc::new(Butterfly11::new(direction)) as Arc<dyn Fft<T>>,
341 Recipe::Butterfly13 => Arc::new(Butterfly13::new(direction)) as Arc<dyn Fft<T>>,
342 Recipe::Butterfly16 => Arc::new(Butterfly16::new(direction)) as Arc<dyn Fft<T>>,
343 Recipe::Butterfly17 => Arc::new(Butterfly17::new(direction)) as Arc<dyn Fft<T>>,
344 Recipe::Butterfly19 => Arc::new(Butterfly19::new(direction)) as Arc<dyn Fft<T>>,
345 Recipe::Butterfly23 => Arc::new(Butterfly23::new(direction)) as Arc<dyn Fft<T>>,
346 Recipe::Butterfly27 => Arc::new(Butterfly27::new(direction)) as Arc<dyn Fft<T>>,
347 Recipe::Butterfly29 => Arc::new(Butterfly29::new(direction)) as Arc<dyn Fft<T>>,
348 Recipe::Butterfly31 => Arc::new(Butterfly31::new(direction)) as Arc<dyn Fft<T>>,
349 Recipe::Butterfly32 => Arc::new(Butterfly32::new(direction)) as Arc<dyn Fft<T>>,
350 Recipe::MixedRadix {
351 left_fft,
352 right_fft,
353 } => {
354 let left_fft = self.build_fft(&left_fft, direction);
355 let right_fft = self.build_fft(&right_fft, direction);
356 Arc::new(MixedRadix::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
357 }
358 Recipe::GoodThomasAlgorithm {
359 left_fft,
360 right_fft,
361 } => {
362 let left_fft = self.build_fft(&left_fft, direction);
363 let right_fft = self.build_fft(&right_fft, direction);
364 Arc::new(GoodThomasAlgorithm::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
365 }
366 Recipe::MixedRadixSmall {
367 left_fft,
368 right_fft,
369 } => {
370 let left_fft = self.build_fft(&left_fft, direction);
371 let right_fft = self.build_fft(&right_fft, direction);
372 Arc::new(MixedRadixSmall::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
373 }
374 Recipe::GoodThomasAlgorithmSmall {
375 left_fft,
376 right_fft,
377 } => {
378 let left_fft = self.build_fft(&left_fft, direction);
379 let right_fft = self.build_fft(&right_fft, direction);
380 Arc::new(GoodThomasAlgorithmSmall::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
381 }
382 Recipe::RadersAlgorithm { inner_fft } => {
383 let inner_fft = self.build_fft(&inner_fft, direction);
384 Arc::new(RadersAlgorithm::new(inner_fft)) as Arc<dyn Fft<T>>
385 }
386 Recipe::BluesteinsAlgorithm { len, inner_fft } => {
387 let inner_fft = self.build_fft(&inner_fft, direction);
388 Arc::new(BluesteinsAlgorithm::new(*len, inner_fft)) as Arc<dyn Fft<T>>
389 }
390 }
391 }
392
393 fn design_fft_with_factors(&mut self, len: usize, factors: PrimeFactors) -> Arc<Recipe> {
394 if let Some(fft_instance) = self.design_butterfly_algorithm(len) {
395 fft_instance
396 } else if factors.is_prime() {
397 self.design_prime(len)
398 } else if len.trailing_zeros() >= MIN_RADIX4_BITS {
399 if len.is_power_of_two() {
400 Arc::new(Recipe::Radix4(len))
401 } else {
402 let non_power_of_two = factors
403 .remove_factors(PrimeFactor {
404 value: 2,
405 count: len.trailing_zeros(),
406 })
407 .unwrap();
408 let power_of_two = PrimeFactors::compute(1 << len.trailing_zeros());
409 self.design_mixed_radix(power_of_two, non_power_of_two)
410 }
411 } else if factors.get_power_of_three() >= MIN_RADIX3_FACTORS {
412 if factors.is_power_of_three() {
413 Arc::new(Recipe::Radix3(len))
414 } else {
415 let power3 = factors.get_power_of_three();
416 let non_power_of_three = factors
417 .remove_factors(PrimeFactor {
418 value: 3,
419 count: power3,
420 })
421 .unwrap();
422 let power_of_three = PrimeFactors::compute(3usize.pow(power3));
423 self.design_mixed_radix(power_of_three, non_power_of_three)
424 }
425 } else {
426 let (left_factors, right_factors) = factors.partition_factors();
427 self.design_mixed_radix(left_factors, right_factors)
428 }
429 }
430
431 fn design_mixed_radix(
432 &mut self,
433 left_factors: PrimeFactors,
434 right_factors: PrimeFactors,
435 ) -> Arc<Recipe> {
436 let left_len = left_factors.get_product();
437 let right_len = right_factors.get_product();
438
439 //neither size is a butterfly, so go with the normal algorithm
440 let left_fft = self.design_fft_with_factors(left_len, left_factors);
441 let right_fft = self.design_fft_with_factors(right_len, right_factors);
442
443 //if both left_len and right_len are small, use algorithms optimized for small FFTs
444 if left_len < 31 && right_len < 31 {
445 // for small FFTs, if gcd is 1, good-thomas is faster
446 if gcd(left_len, right_len) == 1 {
447 Arc::new(Recipe::GoodThomasAlgorithmSmall {
448 left_fft,
449 right_fft,
450 })
451 } else {
452 Arc::new(Recipe::MixedRadixSmall {
453 left_fft,
454 right_fft,
455 })
456 }
457 } else {
458 Arc::new(Recipe::MixedRadix {
459 left_fft,
460 right_fft,
461 })
462 }
463 }
464
465 // Returns Some(instance) if we have a butterfly available for this size. Returns None if there is no butterfly available for this size
466 fn design_butterfly_algorithm(&mut self, len: usize) -> Option<Arc<Recipe>> {
467 match len {
468 2 => Some(Arc::new(Recipe::Butterfly2)),
469 3 => Some(Arc::new(Recipe::Butterfly3)),
470 4 => Some(Arc::new(Recipe::Butterfly4)),
471 5 => Some(Arc::new(Recipe::Butterfly5)),
472 6 => Some(Arc::new(Recipe::Butterfly6)),
473 7 => Some(Arc::new(Recipe::Butterfly7)),
474 8 => Some(Arc::new(Recipe::Butterfly8)),
475 9 => Some(Arc::new(Recipe::Butterfly9)),
476 11 => Some(Arc::new(Recipe::Butterfly11)),
477 13 => Some(Arc::new(Recipe::Butterfly13)),
478 16 => Some(Arc::new(Recipe::Butterfly16)),
479 17 => Some(Arc::new(Recipe::Butterfly17)),
480 19 => Some(Arc::new(Recipe::Butterfly19)),
481 23 => Some(Arc::new(Recipe::Butterfly23)),
482 27 => Some(Arc::new(Recipe::Butterfly27)),
483 29 => Some(Arc::new(Recipe::Butterfly29)),
484 31 => Some(Arc::new(Recipe::Butterfly31)),
485 32 => Some(Arc::new(Recipe::Butterfly32)),
486 _ => None,
487 }
488 }
489
490 fn design_prime(&mut self, len: usize) -> Arc<Recipe> {
491 let inner_fft_len_rader = len - 1;
492 let raders_factors = PrimeFactors::compute(inner_fft_len_rader);
493 // If any of the prime factors is too large, Rader's gets slow and Bluestein's is the better choice
494 if raders_factors
495 .get_other_factors()
496 .iter()
497 .any(|val| val.value > MAX_RADER_PRIME_FACTOR)
498 {
499 let inner_fft_len_pow2 = (2 * len - 1).checked_next_power_of_two().unwrap();
500 // for long ffts a mixed radix inner fft is faster than a longer radix4
501 let min_inner_len = 2 * len - 1;
502 let mixed_radix_len = 3 * inner_fft_len_pow2 / 4;
503 let inner_fft =
504 if mixed_radix_len >= min_inner_len && len >= MIN_BLUESTEIN_MIXED_RADIX_LEN {
505 let mixed_radix_factors = PrimeFactors::compute(mixed_radix_len);
506 self.design_fft_with_factors(mixed_radix_len, mixed_radix_factors)
507 } else {
508 Arc::new(Recipe::Radix4(inner_fft_len_pow2))
509 };
510 Arc::new(Recipe::BluesteinsAlgorithm { len, inner_fft })
511 } else {
512 let inner_fft = self.design_fft_with_factors(inner_fft_len_rader, raders_factors);
513 Arc::new(Recipe::RadersAlgorithm { inner_fft })
514 }
515 }
516 }
517
518 #[cfg(test)]
519 mod unit_tests {
520 use super::*;
521
522 fn is_mixedradix(plan: &Recipe) -> bool {
523 match plan {
524 &Recipe::MixedRadix { .. } => true,
525 _ => false,
526 }
527 }
528
529 fn is_mixedradixsmall(plan: &Recipe) -> bool {
530 match plan {
531 &Recipe::MixedRadixSmall { .. } => true,
532 _ => false,
533 }
534 }
535
536 fn is_goodthomassmall(plan: &Recipe) -> bool {
537 match plan {
538 &Recipe::GoodThomasAlgorithmSmall { .. } => true,
539 _ => false,
540 }
541 }
542
543 fn is_raders(plan: &Recipe) -> bool {
544 match plan {
545 &Recipe::RadersAlgorithm { .. } => true,
546 _ => false,
547 }
548 }
549
550 fn is_bluesteins(plan: &Recipe) -> bool {
551 match plan {
552 &Recipe::BluesteinsAlgorithm { .. } => true,
553 _ => false,
554 }
555 }
556
557 #[test]
558 fn test_plan_scalar_trivial() {
559 // Length 0 and 1 should use Dft
560 let mut planner = FftPlannerScalar::<f64>::new();
561 for len in 0..2 {
562 let plan = planner.design_fft_for_len(len);
563 assert_eq!(*plan, Recipe::Dft(len));
564 assert_eq!(plan.len(), len, "Recipe reports wrong length");
565 }
566 }
567
568 #[test]
569 fn test_plan_scalar_largepoweroftwo() {
570 // Powers of 2 above 64 should use Radix4
571 let mut planner = FftPlannerScalar::<f64>::new();
572 for pow in 6..32 {
573 let len = 1 << pow;
574 let plan = planner.design_fft_for_len(len);
575 assert_eq!(*plan, Recipe::Radix4(len));
576 assert_eq!(plan.len(), len, "Recipe reports wrong length");
577 }
578 }
579
580 #[test]
581 fn test_plan_scalar_butterflies() {
582 // Check that all butterflies are used
583 let mut planner = FftPlannerScalar::<f64>::new();
584 assert_eq!(*planner.design_fft_for_len(2), Recipe::Butterfly2);
585 assert_eq!(*planner.design_fft_for_len(3), Recipe::Butterfly3);
586 assert_eq!(*planner.design_fft_for_len(4), Recipe::Butterfly4);
587 assert_eq!(*planner.design_fft_for_len(5), Recipe::Butterfly5);
588 assert_eq!(*planner.design_fft_for_len(6), Recipe::Butterfly6);
589 assert_eq!(*planner.design_fft_for_len(7), Recipe::Butterfly7);
590 assert_eq!(*planner.design_fft_for_len(8), Recipe::Butterfly8);
591 assert_eq!(*planner.design_fft_for_len(11), Recipe::Butterfly11);
592 assert_eq!(*planner.design_fft_for_len(13), Recipe::Butterfly13);
593 assert_eq!(*planner.design_fft_for_len(16), Recipe::Butterfly16);
594 assert_eq!(*planner.design_fft_for_len(17), Recipe::Butterfly17);
595 assert_eq!(*planner.design_fft_for_len(19), Recipe::Butterfly19);
596 assert_eq!(*planner.design_fft_for_len(23), Recipe::Butterfly23);
597 assert_eq!(*planner.design_fft_for_len(29), Recipe::Butterfly29);
598 assert_eq!(*planner.design_fft_for_len(31), Recipe::Butterfly31);
599 assert_eq!(*planner.design_fft_for_len(32), Recipe::Butterfly32);
600 }
601
602 #[test]
603 fn test_plan_scalar_mixedradix() {
604 // Products of several different primes should become MixedRadix
605 let mut planner = FftPlannerScalar::<f64>::new();
606 for pow2 in 2..5 {
607 for pow3 in 2..5 {
608 for pow5 in 2..5 {
609 for pow7 in 2..5 {
610 let len = 2usize.pow(pow2)
611 * 3usize.pow(pow3)
612 * 5usize.pow(pow5)
613 * 7usize.pow(pow7);
614 let plan = planner.design_fft_for_len(len);
615 assert!(is_mixedradix(&plan), "Expected MixedRadix, got {:?}", plan);
616 assert_eq!(plan.len(), len, "Recipe reports wrong length");
617 }
618 }
619 }
620 }
621 }
622
623 #[test]
624 fn test_plan_scalar_mixedradixsmall() {
625 // Products of two "small" lengths < 31 that have a common divisor >1, and isn't a power of 2 should be MixedRadixSmall
626 let mut planner = FftPlannerScalar::<f64>::new();
627 for len in [5 * 20, 5 * 25].iter() {
628 let plan = planner.design_fft_for_len(*len);
629 assert!(
630 is_mixedradixsmall(&plan),
631 "Expected MixedRadixSmall, got {:?}",
632 plan
633 );
634 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
635 }
636 }
637
638 #[test]
639 fn test_plan_scalar_goodthomasbutterfly() {
640 let mut planner = FftPlannerScalar::<f64>::new();
641 for len in [3 * 4, 3 * 5, 3 * 7, 5 * 7, 11 * 13].iter() {
642 let plan = planner.design_fft_for_len(*len);
643 assert!(
644 is_goodthomassmall(&plan),
645 "Expected GoodThomasAlgorithmSmall, got {:?}",
646 plan
647 );
648 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
649 }
650 }
651
652 #[test]
653 fn test_plan_scalar_bluestein_vs_rader() {
654 let difficultprimes: [usize; 11] = [59, 83, 107, 149, 167, 173, 179, 359, 719, 1439, 2879];
655 let easyprimes: [usize; 24] = [
656 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 151, 157, 163,
657 181, 191, 193, 197, 199,
658 ];
659
660 let mut planner = FftPlannerScalar::<f64>::new();
661 for len in difficultprimes.iter() {
662 let plan = planner.design_fft_for_len(*len);
663 assert!(
664 is_bluesteins(&plan),
665 "Expected BluesteinsAlgorithm, got {:?}",
666 plan
667 );
668 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
669 }
670 for len in easyprimes.iter() {
671 let plan = planner.design_fft_for_len(*len);
672 assert!(is_raders(&plan), "Expected RadersAlgorithm, got {:?}", plan);
673 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
674 }
675 }
676
677 #[test]
678 fn test_scalar_fft_cache() {
679 {
680 // Check that FFTs are reused if they're both forward
681 let mut planner = FftPlannerScalar::<f64>::new();
682 let fft_a = planner.plan_fft(1234, FftDirection::Forward);
683 let fft_b = planner.plan_fft(1234, FftDirection::Forward);
684 assert!(Arc::ptr_eq(&fft_a, &fft_b), "Existing fft was not reused");
685 }
686 {
687 // Check that FFTs are reused if they're both inverse
688 let mut planner = FftPlannerScalar::<f64>::new();
689 let fft_a = planner.plan_fft(1234, FftDirection::Inverse);
690 let fft_b = planner.plan_fft(1234, FftDirection::Inverse);
691 assert!(Arc::ptr_eq(&fft_a, &fft_b), "Existing fft was not reused");
692 }
693 {
694 // Check that FFTs are NOT resued if they don't both have the same direction
695 let mut planner = FftPlannerScalar::<f64>::new();
696 let fft_a = planner.plan_fft(1234, FftDirection::Forward);
697 let fft_b = planner.plan_fft(1234, FftDirection::Inverse);
698 assert!(
699 !Arc::ptr_eq(&fft_a, &fft_b),
700 "Existing fft was reused, even though directions don't match"
701 );
702 }
703 }
704
705 #[test]
706 fn test_scalar_recipe_cache() {
707 // Check that all butterflies are used
708 let mut planner = FftPlannerScalar::<f64>::new();
709 let fft_a = planner.design_fft_for_len(1234);
710 let fft_b = planner.design_fft_for_len(1234);
711 assert!(
712 Arc::ptr_eq(&fft_a, &fft_b),
713 "Existing recipe was not reused"
714 );
715 }
716
717 // We don't need to actually compute anything for a FFT size of zero, but we do need to verify that it doesn't explode
718 #[test]
719 fn test_plan_zero_scalar() {
720 let mut planner32 = FftPlannerScalar::<f32>::new();
721 let fft_zero32 = planner32.plan_fft_forward(0);
722 fft_zero32.process(&mut []);
723
724 let mut planner64 = FftPlannerScalar::<f64>::new();
725 let fft_zero64 = planner64.plan_fft_forward(0);
726 fft_zero64.process(&mut []);
727 }
728
729 // This test is not designed to be run, only to compile.
730 // We cannot make it #[test] since there is a generic parameter.
731 #[allow(dead_code)]
732 fn test_impl_fft_planner_send<T: FftNum>() {
733 fn is_send<T: Send>() {}
734 is_send::<FftPlanner<T>>();
735 is_send::<FftPlannerScalar<T>>();
736 is_send::<FftPlannerSse<T>>();
737 is_send::<FftPlannerAvx<T>>();
738 }
739 }