Debian Codegraph @

.cargo/vendor/rustfft/src/wasm_simd/wasm_simd_planner.rs

raw
1 use num_integer::gcd;
2
3 use crate::algorithm::{
4 BluesteinsAlgorithm, Dft, GoodThomasAlgorithm, GoodThomasAlgorithmSmall, MixedRadix,
5 MixedRadixSmall, RadersAlgorithm,
6 };
7 use crate::math_utils::PrimeFactor;
8 use crate::wasm_simd::*;
9 use crate::{fft_cache::FftCache, math_utils::PrimeFactors, Fft, FftDirection, FftNum};
10 use std::{any::TypeId, collections::HashMap, sync::Arc};
11
12 const MIN_RADIX4_BITS: u32 = 6; // smallest size to consider radix 4 an option is 2^6 = 64
13 const MAX_RADER_PRIME_FACTOR: usize = 23; // don't use Raders if the inner fft length has prime factor larger than this
14 const MIN_BLUESTEIN_MIXED_RADIX_LEN: usize = 90; // only use mixed radix for the inner fft of Bluestein if length is larger than this
15
16 /// A Recipe is a structure that describes the design of a FFT, without actually creating it.
17 /// It is used as a middle step in the planning process.
18 #[derive(Debug, PartialEq, Clone)]
19 pub enum Recipe {
20 Dft(usize),
21 MixedRadix {
22 left_fft: Arc<Recipe>,
23 right_fft: Arc<Recipe>,
24 },
25 #[allow(dead_code)]
26 GoodThomasAlgorithm {
27 left_fft: Arc<Recipe>,
28 right_fft: Arc<Recipe>,
29 },
30 MixedRadixSmall {
31 left_fft: Arc<Recipe>,
32 right_fft: Arc<Recipe>,
33 },
34 GoodThomasAlgorithmSmall {
35 left_fft: Arc<Recipe>,
36 right_fft: Arc<Recipe>,
37 },
38 RadersAlgorithm {
39 inner_fft: Arc<Recipe>,
40 },
41 BluesteinsAlgorithm {
42 len: usize,
43 inner_fft: Arc<Recipe>,
44 },
45 Radix4(usize),
46 Butterfly1,
47 Butterfly2,
48 Butterfly3,
49 Butterfly4,
50 Butterfly5,
51 Butterfly6,
52 Butterfly7,
53 Butterfly8,
54 Butterfly9,
55 Butterfly10,
56 Butterfly11,
57 Butterfly12,
58 Butterfly13,
59 Butterfly15,
60 Butterfly16,
61 Butterfly17,
62 Butterfly19,
63 Butterfly23,
64 Butterfly29,
65 Butterfly31,
66 Butterfly32,
67 }
68
69 impl Recipe {
70 pub fn len(&self) -> usize {
71 match self {
72 Recipe::Dft(length) => *length,
73 Recipe::Radix4(length) => *length,
74 Recipe::Butterfly1 => 1,
75 Recipe::Butterfly2 => 2,
76 Recipe::Butterfly3 => 3,
77 Recipe::Butterfly4 => 4,
78 Recipe::Butterfly5 => 5,
79 Recipe::Butterfly6 => 6,
80 Recipe::Butterfly7 => 7,
81 Recipe::Butterfly8 => 8,
82 Recipe::Butterfly9 => 9,
83 Recipe::Butterfly10 => 10,
84 Recipe::Butterfly11 => 11,
85 Recipe::Butterfly12 => 12,
86 Recipe::Butterfly13 => 13,
87 Recipe::Butterfly15 => 15,
88 Recipe::Butterfly16 => 16,
89 Recipe::Butterfly17 => 17,
90 Recipe::Butterfly19 => 19,
91 Recipe::Butterfly23 => 23,
92 Recipe::Butterfly29 => 29,
93 Recipe::Butterfly31 => 31,
94 Recipe::Butterfly32 => 32,
95 Recipe::MixedRadix {
96 left_fft,
97 right_fft,
98 } => left_fft.len() * right_fft.len(),
99 Recipe::GoodThomasAlgorithm {
100 left_fft,
101 right_fft,
102 } => left_fft.len() * right_fft.len(),
103 Recipe::MixedRadixSmall {
104 left_fft,
105 right_fft,
106 } => left_fft.len() * right_fft.len(),
107 Recipe::GoodThomasAlgorithmSmall {
108 left_fft,
109 right_fft,
110 } => left_fft.len() * right_fft.len(),
111 Recipe::RadersAlgorithm { inner_fft } => inner_fft.len() + 1,
112 Recipe::BluesteinsAlgorithm { len, .. } => *len,
113 }
114 }
115 }
116
117 /// The WASM FFT planner creates new FFT algorithm instances using a mix of scalar and WASM SIMD accelerated algorithms.
118 /// WASM SIMD is supported when using fairly recent browser versions as outlined in [the WebAssembly roadmap](https://webassembly.org/roadmap/).
119 ///
120 /// RustFFT has several FFT algorithms available. For a given FFT size, `FftPlannerWasmSimd` decides which of the
121 /// available FFT algorithms to use and then initializes them.
122 ///
123 /// ~~~
124 /// // Perform a forward Fft of size 1234
125 /// use std::sync::Arc;
126 /// use rustfft::{FftPlannerWasmSimd, num_complex::Complex};
127 ///
128 /// if let Ok(mut planner) = FftPlannerWasmSimd::new() {
129 /// let fft = planner.plan_fft_forward(1234);
130 ///
131 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234];
132 /// fft.process(&mut buffer);
133 ///
134 /// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`,
135 /// // where T is the numeric type, ie f32 or f64, so it's cheap to clone
136 /// let fft_clone = Arc::clone(&fft);
137 /// }
138 /// ~~~
139 ///
140 /// If you plan on creating multiple FFT instances, it is recommended to re-use the same planner for all of them. This
141 /// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing
142 /// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created
143 /// by a different planner)
144 ///
145 /// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly
146 /// safe to drop the planner after creating Fft instances.
147 pub struct FftPlannerWasmSimd<T: FftNum> {
148 algorithm_cache: FftCache<T>,
149 recipe_cache: HashMap<usize, Arc<Recipe>>,
150 }
151 impl<T: FftNum> FftPlannerWasmSimd<T> {
152 /// Creates a new `FftPlannerWasmSimd` instance.
153 ///
154 /// Returns `Ok(planner_instance)` if we're compiling for the WASM target and WASM SIMD was enabled in feature flags.
155 /// Returns `Err(())` if WASM SIMD support is not available.
156 pub fn new() -> Result<Self, ()> {
157 let id_f32 = TypeId::of::<f32>();
158 let id_f64 = TypeId::of::<f64>();
159 let id_t = TypeId::of::<T>();
160
161 if id_t != id_f32 && id_t != id_f64 {
162 return Err(());
163 }
164
165 Ok(Self {
166 algorithm_cache: FftCache::new(),
167 recipe_cache: HashMap::new(),
168 })
169 }
170 /// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute FFTs of size `len`.
171 ///
172 /// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs.
173 ///
174 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
175 pub fn plan_fft(&mut self, len: usize, direction: FftDirection) -> Arc<dyn Fft<T>> {
176 let recipe = self.design_fft_for_len(len);
177 self.build_fft(&recipe, direction)
178 }
179 /// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute forward FFTs of size `len`.
180 ///
181 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
182 pub fn plan_fft_forward(&mut self, len: usize) -> Arc<dyn Fft<T>> {
183 self.plan_fft(len, FftDirection::Forward)
184 }
185 /// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute inverse FFTs of size `len.
186 ///
187 /// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time.
188 pub fn plan_fft_inverse(&mut self, _len: usize) -> Arc<dyn Fft<T>> {
189 self.plan_fft(_len, FftDirection::Inverse)
190 }
191 }
192
193 impl<T: FftNum> FftPlannerWasmSimd<T> {
194 fn design_fft_for_len(&mut self, len: usize) -> Arc<Recipe> {
195 if len < 1 {
196 Arc::new(Recipe::Dft(len))
197 } else if let Some(recipe) = self.recipe_cache.get(&len) {
198 Arc::clone(&recipe)
199 } else {
200 let factors = PrimeFactors::compute(len);
201 let recipe = self.design_fft_with_factors(len, factors);
202 self.recipe_cache.insert(len, Arc::clone(&recipe));
203 recipe
204 }
205 }
206
207 fn build_fft(&mut self, recipe: &Recipe, direction: FftDirection) -> Arc<dyn Fft<T>> {
208 let len = recipe.len();
209 if let Some(instance) = self.algorithm_cache.get(len, direction) {
210 instance
211 } else {
212 let fft = self.build_new_fft(recipe, direction);
213 self.algorithm_cache.insert(&fft);
214 fft
215 }
216 }
217
218 fn build_new_fft(&mut self, recipe: &Recipe, direction: FftDirection) -> Arc<dyn Fft<T>> {
219 let id_f32 = TypeId::of::<f32>();
220 let id_f64 = TypeId::of::<f64>();
221 let id_t = TypeId::of::<T>();
222
223 match recipe {
224 Recipe::Dft(len) => Arc::new(Dft::new(*len, direction)) as Arc<dyn Fft<T>>,
225 Recipe::Radix4(len) => {
226 if id_t == id_f32 {
227 Arc::new(WasmSimd32Radix4::new(*len, direction)) as Arc<dyn Fft<T>>
228 } else if id_t == id_f64 {
229 Arc::new(WasmSimd64Radix4::new(*len, direction)) as Arc<dyn Fft<T>>
230 } else {
231 panic!("Not f32 or f64");
232 }
233 }
234 Recipe::Butterfly1 => {
235 if id_t == id_f32 {
236 Arc::new(WasmSimdF32Butterfly1::new(direction)) as Arc<dyn Fft<T>>
237 } else if id_t == id_f64 {
238 Arc::new(WasmSimdF64Butterfly1::new(direction)) as Arc<dyn Fft<T>>
239 } else {
240 panic!("Not f32 or f64");
241 }
242 }
243 Recipe::Butterfly2 => {
244 if id_t == id_f32 {
245 Arc::new(WasmSimdF32Butterfly2::new(direction)) as Arc<dyn Fft<T>>
246 } else if id_t == id_f64 {
247 Arc::new(WasmSimdF64Butterfly2::new(direction)) as Arc<dyn Fft<T>>
248 } else {
249 panic!("Not f32 or f64");
250 }
251 }
252 Recipe::Butterfly3 => {
253 if id_t == id_f32 {
254 Arc::new(WasmSimdF32Butterfly3::new(direction)) as Arc<dyn Fft<T>>
255 } else if id_t == id_f64 {
256 Arc::new(WasmSimdF64Butterfly3::new(direction)) as Arc<dyn Fft<T>>
257 } else {
258 panic!("Not f32 or f64");
259 }
260 }
261 Recipe::Butterfly4 => {
262 if id_t == id_f32 {
263 Arc::new(WasmSimdF32Butterfly4::new(direction)) as Arc<dyn Fft<T>>
264 } else if id_t == id_f64 {
265 Arc::new(WasmSimdF64Butterfly4::new(direction)) as Arc<dyn Fft<T>>
266 } else {
267 panic!("Not f32 or f64");
268 }
269 }
270 Recipe::Butterfly5 => {
271 if id_t == id_f32 {
272 Arc::new(WasmSimdF32Butterfly5::new(direction)) as Arc<dyn Fft<T>>
273 } else if id_t == id_f64 {
274 Arc::new(WasmSimdF64Butterfly5::new(direction)) as Arc<dyn Fft<T>>
275 } else {
276 panic!("Not f32 or f64");
277 }
278 }
279 Recipe::Butterfly6 => {
280 if id_t == id_f32 {
281 Arc::new(WasmSimdF32Butterfly6::new(direction)) as Arc<dyn Fft<T>>
282 } else if id_t == id_f64 {
283 Arc::new(WasmSimdF64Butterfly6::new(direction)) as Arc<dyn Fft<T>>
284 } else {
285 panic!("Not f32 or f64");
286 }
287 }
288 Recipe::Butterfly7 => {
289 if id_t == id_f32 {
290 Arc::new(WasmSimdF32Butterfly7::new(direction)) as Arc<dyn Fft<T>>
291 } else if id_t == id_f64 {
292 Arc::new(WasmSimdF64Butterfly7::new(direction)) as Arc<dyn Fft<T>>
293 } else {
294 panic!("Not f32 or f64");
295 }
296 }
297 Recipe::Butterfly8 => {
298 if id_t == id_f32 {
299 Arc::new(WasmSimdF32Butterfly8::new(direction)) as Arc<dyn Fft<T>>
300 } else if id_t == id_f64 {
301 Arc::new(WasmSimdF64Butterfly8::new(direction)) as Arc<dyn Fft<T>>
302 } else {
303 panic!("Not f32 or f64");
304 }
305 }
306 Recipe::Butterfly9 => {
307 if id_t == id_f32 {
308 Arc::new(WasmSimdF32Butterfly9::new(direction)) as Arc<dyn Fft<T>>
309 } else if id_t == id_f64 {
310 Arc::new(WasmSimdF64Butterfly9::new(direction)) as Arc<dyn Fft<T>>
311 } else {
312 panic!("Not f32 or f64");
313 }
314 }
315 Recipe::Butterfly10 => {
316 if id_t == id_f32 {
317 Arc::new(WasmSimdF32Butterfly10::new(direction)) as Arc<dyn Fft<T>>
318 } else if id_t == id_f64 {
319 Arc::new(WasmSimdF64Butterfly10::new(direction)) as Arc<dyn Fft<T>>
320 } else {
321 panic!("Not f32 or f64");
322 }
323 }
324 Recipe::Butterfly11 => {
325 if id_t == id_f32 {
326 Arc::new(WasmSimdF32Butterfly11::new(direction)) as Arc<dyn Fft<T>>
327 } else if id_t == id_f64 {
328 Arc::new(WasmSimdF64Butterfly11::new(direction)) as Arc<dyn Fft<T>>
329 } else {
330 panic!("Not f32 or f64");
331 }
332 }
333 Recipe::Butterfly12 => {
334 if id_t == id_f32 {
335 Arc::new(WasmSimdF32Butterfly12::new(direction)) as Arc<dyn Fft<T>>
336 } else if id_t == id_f64 {
337 Arc::new(WasmSimdF64Butterfly12::new(direction)) as Arc<dyn Fft<T>>
338 } else {
339 panic!("Not f32 or f64");
340 }
341 }
342 Recipe::Butterfly13 => {
343 if id_t == id_f32 {
344 Arc::new(WasmSimdF32Butterfly13::new(direction)) as Arc<dyn Fft<T>>
345 } else if id_t == id_f64 {
346 Arc::new(WasmSimdF64Butterfly13::new(direction)) as Arc<dyn Fft<T>>
347 } else {
348 panic!("Not f32 or f64");
349 }
350 }
351 Recipe::Butterfly15 => {
352 if id_t == id_f32 {
353 Arc::new(WasmSimdF32Butterfly15::new(direction)) as Arc<dyn Fft<T>>
354 } else if id_t == id_f64 {
355 Arc::new(WasmSimdF64Butterfly15::new(direction)) as Arc<dyn Fft<T>>
356 } else {
357 panic!("Not f32 or f64");
358 }
359 }
360 Recipe::Butterfly16 => {
361 if id_t == id_f32 {
362 Arc::new(WasmSimdF32Butterfly16::new(direction)) as Arc<dyn Fft<T>>
363 } else if id_t == id_f64 {
364 Arc::new(WasmSimdF64Butterfly16::new(direction)) as Arc<dyn Fft<T>>
365 } else {
366 panic!("Not f32 or f64");
367 }
368 }
369 Recipe::Butterfly17 => {
370 if id_t == id_f32 {
371 Arc::new(WasmSimdF32Butterfly17::new(direction)) as Arc<dyn Fft<T>>
372 } else if id_t == id_f64 {
373 Arc::new(WasmSimdF64Butterfly17::new(direction)) as Arc<dyn Fft<T>>
374 } else {
375 panic!("Not f32 or f64");
376 }
377 }
378 Recipe::Butterfly19 => {
379 if id_t == id_f32 {
380 Arc::new(WasmSimdF32Butterfly19::new(direction)) as Arc<dyn Fft<T>>
381 } else if id_t == id_f64 {
382 Arc::new(WasmSimdF64Butterfly19::new(direction)) as Arc<dyn Fft<T>>
383 } else {
384 panic!("Not f32 or f64");
385 }
386 }
387 Recipe::Butterfly23 => {
388 if id_t == id_f32 {
389 Arc::new(WasmSimdF32Butterfly23::new(direction)) as Arc<dyn Fft<T>>
390 } else if id_t == id_f64 {
391 Arc::new(WasmSimdF64Butterfly23::new(direction)) as Arc<dyn Fft<T>>
392 } else {
393 panic!("Not f32 or f64");
394 }
395 }
396 Recipe::Butterfly29 => {
397 if id_t == id_f32 {
398 Arc::new(WasmSimdF32Butterfly29::new(direction)) as Arc<dyn Fft<T>>
399 } else if id_t == id_f64 {
400 Arc::new(WasmSimdF64Butterfly29::new(direction)) as Arc<dyn Fft<T>>
401 } else {
402 panic!("Not f32 or f64");
403 }
404 }
405 Recipe::Butterfly31 => {
406 if id_t == id_f32 {
407 Arc::new(WasmSimdF32Butterfly31::new(direction)) as Arc<dyn Fft<T>>
408 } else if id_t == id_f64 {
409 Arc::new(WasmSimdF64Butterfly31::new(direction)) as Arc<dyn Fft<T>>
410 } else {
411 panic!("Not f32 or f64");
412 }
413 }
414 Recipe::Butterfly32 => {
415 if id_t == id_f32 {
416 Arc::new(WasmSimdF32Butterfly32::new(direction)) as Arc<dyn Fft<T>>
417 } else if id_t == id_f64 {
418 Arc::new(WasmSimdF64Butterfly32::new(direction)) as Arc<dyn Fft<T>>
419 } else {
420 panic!("Not f32 or f64");
421 }
422 }
423 Recipe::MixedRadix {
424 left_fft,
425 right_fft,
426 } => {
427 let left_fft = self.build_fft(&left_fft, direction);
428 let right_fft = self.build_fft(&right_fft, direction);
429 Arc::new(MixedRadix::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
430 }
431 Recipe::GoodThomasAlgorithm {
432 left_fft,
433 right_fft,
434 } => {
435 let left_fft = self.build_fft(&left_fft, direction);
436 let right_fft = self.build_fft(&right_fft, direction);
437 Arc::new(GoodThomasAlgorithm::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
438 }
439 Recipe::MixedRadixSmall {
440 left_fft,
441 right_fft,
442 } => {
443 let left_fft = self.build_fft(&left_fft, direction);
444 let right_fft = self.build_fft(&right_fft, direction);
445 Arc::new(MixedRadixSmall::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
446 }
447 Recipe::GoodThomasAlgorithmSmall {
448 left_fft,
449 right_fft,
450 } => {
451 let left_fft = self.build_fft(&left_fft, direction);
452 let right_fft = self.build_fft(&right_fft, direction);
453 Arc::new(GoodThomasAlgorithmSmall::new(left_fft, right_fft)) as Arc<dyn Fft<T>>
454 }
455 Recipe::RadersAlgorithm { inner_fft } => {
456 let inner_fft = self.build_fft(&inner_fft, direction);
457 Arc::new(RadersAlgorithm::new(inner_fft)) as Arc<dyn Fft<T>>
458 }
459 Recipe::BluesteinsAlgorithm { len, inner_fft } => {
460 let inner_fft = self.build_fft(&inner_fft, direction);
461 Arc::new(BluesteinsAlgorithm::new(*len, inner_fft)) as Arc<dyn Fft<T>>
462 }
463 }
464 }
465
466 fn design_fft_with_factors(&mut self, len: usize, factors: PrimeFactors) -> Arc<Recipe> {
467 if let Some(fft_instance) = self.design_butterfly_algorithm(len) {
468 fft_instance
469 } else if factors.is_prime() {
470 self.design_prime(len)
471 } else if len.trailing_zeros() >= MIN_RADIX4_BITS {
472 if len.is_power_of_two() {
473 Arc::new(Recipe::Radix4(len))
474 } else {
475 let non_power_of_two = factors
476 .remove_factors(PrimeFactor {
477 value: 2,
478 count: len.trailing_zeros(),
479 })
480 .unwrap();
481 let power_of_two = PrimeFactors::compute(1 << len.trailing_zeros());
482 self.design_mixed_radix(power_of_two, non_power_of_two)
483 }
484 } else {
485 // Can we do this as a mixed radix with just two butterflies?
486 // Loop through and find all combinations
487 // If more than one is found, keep the one where the factors are closer together.
488 // For example length 20 where 10x2 and 5x4 are possible, we use 5x4.
489 let butterflies: [usize; 20] = [
490 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 19, 23, 29, 31, 32,
491 ];
492 let mut bf_left = 0;
493 let mut bf_right = 0;
494 // If the length is below 14, or over 1024 we don't need to try this.
495 if len > 13 && len <= 1024 {
496 for (n, bf_l) in butterflies.iter().enumerate() {
497 if len % bf_l == 0 {
498 let bf_r = len / bf_l;
499 if butterflies.iter().skip(n).any(|&m| m == bf_r) {
500 bf_left = *bf_l;
501 bf_right = bf_r;
502 }
503 }
504 }
505 if bf_left > 0 {
506 let fact_l = PrimeFactors::compute(bf_left);
507 let fact_r = PrimeFactors::compute(bf_right);
508 return self.design_mixed_radix(fact_l, fact_r);
509 }
510 }
511 // Not possible with just butterflies, go with the general solution.
512 let (left_factors, right_factors) = factors.partition_factors();
513 self.design_mixed_radix(left_factors, right_factors)
514 }
515 }
516 fn design_mixed_radix(
517 &mut self,
518 left_factors: PrimeFactors,
519 right_factors: PrimeFactors,
520 ) -> Arc<Recipe> {
521 let left_len = left_factors.get_product();
522 let right_len = right_factors.get_product();
523
524 //neither size is a butterfly, so go with the normal algorithm
525 let left_fft = self.design_fft_with_factors(left_len, left_factors);
526 let right_fft = self.design_fft_with_factors(right_len, right_factors);
527
528 //if both left_len and right_len are small, use algorithms optimized for small FFTs
529 if left_len < 33 && right_len < 33 {
530 // for small FFTs, if gcd is 1, good-thomas is faster
531 if gcd(left_len, right_len) == 1 {
532 Arc::new(Recipe::GoodThomasAlgorithmSmall {
533 left_fft,
534 right_fft,
535 })
536 } else {
537 Arc::new(Recipe::MixedRadixSmall {
538 left_fft,
539 right_fft,
540 })
541 }
542 } else {
543 Arc::new(Recipe::MixedRadix {
544 left_fft,
545 right_fft,
546 })
547 }
548 }
549
550 /// Returns Some(instance) if we have a butterfly available for this size. Returns None if there is no butterfly available for this size
551 fn design_butterfly_algorithm(&mut self, len: usize) -> Option<Arc<Recipe>> {
552 match len {
553 1 => Some(Arc::new(Recipe::Butterfly1)),
554 2 => Some(Arc::new(Recipe::Butterfly2)),
555 3 => Some(Arc::new(Recipe::Butterfly3)),
556 4 => Some(Arc::new(Recipe::Butterfly4)),
557 5 => Some(Arc::new(Recipe::Butterfly5)),
558 6 => Some(Arc::new(Recipe::Butterfly6)),
559 7 => Some(Arc::new(Recipe::Butterfly7)),
560 8 => Some(Arc::new(Recipe::Butterfly8)),
561 9 => Some(Arc::new(Recipe::Butterfly9)),
562 10 => Some(Arc::new(Recipe::Butterfly10)),
563 11 => Some(Arc::new(Recipe::Butterfly11)),
564 12 => Some(Arc::new(Recipe::Butterfly12)),
565 13 => Some(Arc::new(Recipe::Butterfly13)),
566 15 => Some(Arc::new(Recipe::Butterfly15)),
567 16 => Some(Arc::new(Recipe::Butterfly16)),
568 17 => Some(Arc::new(Recipe::Butterfly17)),
569 19 => Some(Arc::new(Recipe::Butterfly19)),
570 23 => Some(Arc::new(Recipe::Butterfly23)),
571 29 => Some(Arc::new(Recipe::Butterfly29)),
572 31 => Some(Arc::new(Recipe::Butterfly31)),
573 32 => Some(Arc::new(Recipe::Butterfly32)),
574 _ => None,
575 }
576 }
577
578 fn design_prime(&mut self, len: usize) -> Arc<Recipe> {
579 let inner_fft_len_rader = len - 1;
580 let raders_factors = PrimeFactors::compute(inner_fft_len_rader);
581 // If any of the prime factors is too large, Rader's gets slow and Bluestein's is the better choice
582 if raders_factors
583 .get_other_factors()
584 .iter()
585 .any(|val| val.value > MAX_RADER_PRIME_FACTOR)
586 {
587 let inner_fft_len_pow2 = (2 * len - 1).checked_next_power_of_two().unwrap();
588 // for long ffts a mixed radix inner fft is faster than a longer radix4
589 let min_inner_len = 2 * len - 1;
590 let mixed_radix_len = 3 * inner_fft_len_pow2 / 4;
591 let inner_fft =
592 if mixed_radix_len >= min_inner_len && len >= MIN_BLUESTEIN_MIXED_RADIX_LEN {
593 let mixed_radix_factors = PrimeFactors::compute(mixed_radix_len);
594 self.design_fft_with_factors(mixed_radix_len, mixed_radix_factors)
595 } else {
596 Arc::new(Recipe::Radix4(inner_fft_len_pow2))
597 };
598 Arc::new(Recipe::BluesteinsAlgorithm { len, inner_fft })
599 } else {
600 let inner_fft = self.design_fft_with_factors(inner_fft_len_rader, raders_factors);
601 Arc::new(Recipe::RadersAlgorithm { inner_fft })
602 }
603 }
604 }
605
606 #[cfg(test)]
607 mod unit_tests {
608 use super::*;
609 use wasm_bindgen_test::*;
610
611 fn is_mixedradix(plan: &Recipe) -> bool {
612 match plan {
613 &Recipe::MixedRadix { .. } => true,
614 _ => false,
615 }
616 }
617
618 fn is_mixedradixsmall(plan: &Recipe) -> bool {
619 match plan {
620 &Recipe::MixedRadixSmall { .. } => true,
621 _ => false,
622 }
623 }
624
625 fn is_goodthomassmall(plan: &Recipe) -> bool {
626 match plan {
627 &Recipe::GoodThomasAlgorithmSmall { .. } => true,
628 _ => false,
629 }
630 }
631
632 fn is_raders(plan: &Recipe) -> bool {
633 match plan {
634 &Recipe::RadersAlgorithm { .. } => true,
635 _ => false,
636 }
637 }
638
639 fn is_bluesteins(plan: &Recipe) -> bool {
640 match plan {
641 &Recipe::BluesteinsAlgorithm { .. } => true,
642 _ => false,
643 }
644 }
645
646 #[wasm_bindgen_test]
647 fn test_plan_sse_trivial() {
648 // Length 0 and 1 should use Dft
649 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
650 for len in 0..1 {
651 let plan = planner.design_fft_for_len(len);
652 assert_eq!(*plan, Recipe::Dft(len));
653 assert_eq!(plan.len(), len, "Recipe reports wrong length");
654 }
655 }
656
657 #[wasm_bindgen_test]
658 fn test_plan_sse_largepoweroftwo() {
659 // Powers of 2 above 6 should use Radix4
660 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
661 for pow in 6..32 {
662 let len = 1 << pow;
663 let plan = planner.design_fft_for_len(len);
664 assert_eq!(*plan, Recipe::Radix4(len));
665 assert_eq!(plan.len(), len, "Recipe reports wrong length");
666 }
667 }
668
669 #[wasm_bindgen_test]
670 fn test_plan_sse_butterflies() {
671 // Check that all butterflies are used
672 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
673 assert_eq!(*planner.design_fft_for_len(2), Recipe::Butterfly2);
674 assert_eq!(*planner.design_fft_for_len(3), Recipe::Butterfly3);
675 assert_eq!(*planner.design_fft_for_len(4), Recipe::Butterfly4);
676 assert_eq!(*planner.design_fft_for_len(5), Recipe::Butterfly5);
677 assert_eq!(*planner.design_fft_for_len(6), Recipe::Butterfly6);
678 assert_eq!(*planner.design_fft_for_len(7), Recipe::Butterfly7);
679 assert_eq!(*planner.design_fft_for_len(8), Recipe::Butterfly8);
680 assert_eq!(*planner.design_fft_for_len(9), Recipe::Butterfly9);
681 assert_eq!(*planner.design_fft_for_len(10), Recipe::Butterfly10);
682 assert_eq!(*planner.design_fft_for_len(11), Recipe::Butterfly11);
683 assert_eq!(*planner.design_fft_for_len(12), Recipe::Butterfly12);
684 assert_eq!(*planner.design_fft_for_len(13), Recipe::Butterfly13);
685 assert_eq!(*planner.design_fft_for_len(15), Recipe::Butterfly15);
686 assert_eq!(*planner.design_fft_for_len(16), Recipe::Butterfly16);
687 assert_eq!(*planner.design_fft_for_len(17), Recipe::Butterfly17);
688 assert_eq!(*planner.design_fft_for_len(19), Recipe::Butterfly19);
689 assert_eq!(*planner.design_fft_for_len(23), Recipe::Butterfly23);
690 assert_eq!(*planner.design_fft_for_len(29), Recipe::Butterfly29);
691 assert_eq!(*planner.design_fft_for_len(31), Recipe::Butterfly31);
692 assert_eq!(*planner.design_fft_for_len(32), Recipe::Butterfly32);
693 }
694
695 #[wasm_bindgen_test]
696 fn test_plan_sse_mixedradix() {
697 // Products of several different primes should become MixedRadix
698 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
699 for pow2 in 2..5 {
700 for pow3 in 2..5 {
701 for pow5 in 2..5 {
702 for pow7 in 2..5 {
703 let len = 2usize.pow(pow2)
704 * 3usize.pow(pow3)
705 * 5usize.pow(pow5)
706 * 7usize.pow(pow7);
707 let plan = planner.design_fft_for_len(len);
708 assert!(is_mixedradix(&plan), "Expected MixedRadix, got {:?}", plan);
709 assert_eq!(plan.len(), len, "Recipe reports wrong length");
710 }
711 }
712 }
713 }
714 }
715
716 #[wasm_bindgen_test]
717 fn test_plan_sse_mixedradixsmall() {
718 // Products of two "small" lengths < 31 that have a common divisor >1, and isn't a power of 2 should be MixedRadixSmall
719 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
720 for len in [5 * 20, 5 * 25].iter() {
721 let plan = planner.design_fft_for_len(*len);
722 assert!(
723 is_mixedradixsmall(&plan),
724 "Expected MixedRadixSmall, got {:?}",
725 plan
726 );
727 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
728 }
729 }
730
731 #[wasm_bindgen_test]
732 fn test_plan_sse_goodthomasbutterfly() {
733 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
734 for len in [3 * 7, 5 * 7, 11 * 13, 2 * 29].iter() {
735 let plan = planner.design_fft_for_len(*len);
736 assert!(
737 is_goodthomassmall(&plan),
738 "Expected GoodThomasAlgorithmSmall, got {:?}",
739 plan
740 );
741 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
742 }
743 }
744
745 #[wasm_bindgen_test]
746 fn test_plan_sse_bluestein_vs_rader() {
747 let difficultprimes: [usize; 11] = [59, 83, 107, 149, 167, 173, 179, 359, 719, 1439, 2879];
748 let easyprimes: [usize; 24] = [
749 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 151, 157, 163,
750 181, 191, 193, 197, 199,
751 ];
752
753 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
754 for len in difficultprimes.iter() {
755 let plan = planner.design_fft_for_len(*len);
756 assert!(
757 is_bluesteins(&plan),
758 "Expected BluesteinsAlgorithm, got {:?}",
759 plan
760 );
761 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
762 }
763 for len in easyprimes.iter() {
764 let plan = planner.design_fft_for_len(*len);
765 assert!(is_raders(&plan), "Expected RadersAlgorithm, got {:?}", plan);
766 assert_eq!(plan.len(), *len, "Recipe reports wrong length");
767 }
768 }
769
770 #[wasm_bindgen_test]
771 fn test_sse_fft_cache() {
772 {
773 // Check that FFTs are reused if they're both forward
774 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
775 let fft_a = planner.plan_fft(1234, FftDirection::Forward);
776 let fft_b = planner.plan_fft(1234, FftDirection::Forward);
777 assert!(Arc::ptr_eq(&fft_a, &fft_b), "Existing fft was not reused");
778 }
779 {
780 // Check that FFTs are reused if they're both inverse
781 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
782 let fft_a = planner.plan_fft(1234, FftDirection::Inverse);
783 let fft_b = planner.plan_fft(1234, FftDirection::Inverse);
784 assert!(Arc::ptr_eq(&fft_a, &fft_b), "Existing fft was not reused");
785 }
786 {
787 // Check that FFTs are NOT resued if they don't both have the same direction
788 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
789 let fft_a = planner.plan_fft(1234, FftDirection::Forward);
790 let fft_b = planner.plan_fft(1234, FftDirection::Inverse);
791 assert!(
792 !Arc::ptr_eq(&fft_a, &fft_b),
793 "Existing fft was reused, even though directions don't match"
794 );
795 }
796 }
797
798 #[wasm_bindgen_test]
799 fn test_sse_recipe_cache() {
800 // Check that all butterflies are used
801 let mut planner = FftPlannerWasmSimd::<f64>::new().unwrap();
802 let fft_a = planner.design_fft_for_len(1234);
803 let fft_b = planner.design_fft_for_len(1234);
804 assert!(
805 Arc::ptr_eq(&fft_a, &fft_b),
806 "Existing recipe was not reused"
807 );
808 }
809 }