Debian Codegraph @

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

raw
1 use core::arch::wasm32::*;
2 use num_complex::Complex;
3
4 use crate::{common::FftNum, FftDirection};
5
6 use crate::array_utils;
7 use crate::array_utils::workaround_transmute_mut;
8 use crate::array_utils::DoubleBuf;
9 use crate::common::{fft_error_inplace, fft_error_outofplace};
10 use crate::twiddles;
11 use crate::{Direction, Fft, Length};
12
13 use super::wasm_simd_common::{assert_f32, assert_f64};
14 use super::wasm_simd_utils::*;
15 use super::wasm_simd_vector::WasmSimdArrayMut;
16
17 #[allow(unused)]
18 macro_rules! boilerplate_fft_wasm_simd_f32_butterfly {
19 ($struct_name:ident, $len:expr, $direction_fn:expr) => {
20 impl<T: FftNum> $struct_name<T> {
21 #[target_feature(enable = "simd128")]
22 pub(crate) unsafe fn perform_fft_butterfly(&self, buffer: &mut [Complex<T>]) {
23 self.perform_fft_contiguous(workaround_transmute_mut::<_, Complex<f32>>(buffer));
24 }
25
26 #[target_feature(enable = "simd128")]
27 pub(crate) unsafe fn perform_parallel_fft_butterfly(&self, buffer: &mut [Complex<T>]) {
28 self.perform_parallel_fft_contiguous(workaround_transmute_mut::<_, Complex<f32>>(
29 buffer,
30 ));
31 }
32
33 // Do multiple ffts over a longer vector inplace, called from "process_with_scratch" of Fft trait
34 #[target_feature(enable = "simd128")]
35 pub(crate) unsafe fn perform_fft_butterfly_multi(
36 &self,
37 buffer: &mut [Complex<T>],
38 ) -> Result<(), ()> {
39 let len = buffer.len();
40 let alldone = array_utils::iter_chunks(buffer, 2 * self.len(), |chunk| {
41 self.perform_parallel_fft_butterfly(chunk)
42 });
43 if alldone.is_err() && buffer.len() >= self.len() {
44 self.perform_fft_butterfly(&mut buffer[len - self.len()..]);
45 }
46 Ok(())
47 }
48
49 // Do multiple ffts over a longer vector outofplace, called from "process_outofplace_with_scratch" of Fft trait
50 #[target_feature(enable = "simd128")]
51 pub(crate) unsafe fn perform_oop_fft_butterfly_multi(
52 &self,
53 input: &mut [Complex<T>],
54 output: &mut [Complex<T>],
55 ) -> Result<(), ()> {
56 let len = input.len();
57 let alldone = array_utils::iter_chunks_zipped(
58 input,
59 output,
60 2 * self.len(),
61 |in_chunk, out_chunk| {
62 let input_slice = workaround_transmute_mut(in_chunk);
63 let output_slice = workaround_transmute_mut(out_chunk);
64 self.perform_parallel_fft_contiguous(DoubleBuf {
65 input: input_slice,
66 output: output_slice,
67 })
68 },
69 );
70 if alldone.is_err() && input.len() >= self.len() {
71 let input_slice = workaround_transmute_mut(input);
72 let output_slice = workaround_transmute_mut(output);
73 self.perform_fft_contiguous(DoubleBuf {
74 input: &mut input_slice[len - self.len()..],
75 output: &mut output_slice[len - self.len()..],
76 })
77 }
78 Ok(())
79 }
80 }
81 };
82 }
83
84 macro_rules! boilerplate_fft_wasm_simd_f64_butterfly {
85 ($struct_name:ident, $len:expr, $direction_fn:expr) => {
86 impl<T: FftNum> $struct_name<T> {
87 // Do a single fft
88 #[target_feature(enable = "simd128")]
89 pub(crate) unsafe fn perform_fft_butterfly(&self, buffer: &mut [Complex<T>]) {
90 self.perform_fft_contiguous(workaround_transmute_mut::<_, Complex<f64>>(buffer));
91 }
92
93 // Do multiple ffts over a longer vector inplace, called from "process_with_scratch" of Fft trait
94 #[target_feature(enable = "simd128")]
95 pub(crate) unsafe fn perform_fft_butterfly_multi(
96 &self,
97 buffer: &mut [Complex<T>],
98 ) -> Result<(), ()> {
99 array_utils::iter_chunks(buffer, self.len(), |chunk| {
100 self.perform_fft_butterfly(chunk)
101 })
102 }
103
104 // Do multiple ffts over a longer vector outofplace, called from "process_outofplace_with_scratch" of Fft trait
105 #[target_feature(enable = "simd128")]
106 pub(crate) unsafe fn perform_oop_fft_butterfly_multi(
107 &self,
108 input: &mut [Complex<T>],
109 output: &mut [Complex<T>],
110 ) -> Result<(), ()> {
111 array_utils::iter_chunks_zipped(input, output, self.len(), |in_chunk, out_chunk| {
112 let input_slice = workaround_transmute_mut(in_chunk);
113 let output_slice = workaround_transmute_mut(out_chunk);
114 self.perform_fft_contiguous(DoubleBuf {
115 input: input_slice,
116 output: output_slice,
117 })
118 })
119 }
120 }
121 };
122 }
123
124 #[allow(unused)]
125 macro_rules! boilerplate_fft_wasm_simd_common_butterfly {
126 ($struct_name:ident, $len:expr, $direction_fn:expr) => {
127 impl<T: FftNum> Fft<T> for $struct_name<T> {
128 fn process_outofplace_with_scratch(
129 &self,
130 input: &mut [Complex<T>],
131 output: &mut [Complex<T>],
132 _scratch: &mut [Complex<T>],
133 ) {
134 if input.len() < self.len() || output.len() != input.len() {
135 // We want to trigger a panic, but we want to avoid doing it in this function to reduce code size, so call a function marked cold and inline(never) that will do it for us
136 fft_error_outofplace(self.len(), input.len(), output.len(), 0, 0);
137 return; // Unreachable, because fft_error_outofplace asserts, but it helps codegen to put it here
138 }
139 let result = unsafe { self.perform_oop_fft_butterfly_multi(input, output) };
140
141 if result.is_err() {
142 // We want to trigger a panic, because the buffer sizes weren't cleanly divisible by the FFT size,
143 // but we want to avoid doing it in this function to reduce code size, so call a function marked cold and inline(never) that will do it for us
144 fft_error_outofplace(self.len(), input.len(), output.len(), 0, 0);
145 }
146 }
147 fn process_with_scratch(&self, buffer: &mut [Complex<T>], _scratch: &mut [Complex<T>]) {
148 if buffer.len() < self.len() {
149 // We want to trigger a panic, but we want to avoid doing it in this function to reduce code size, so call a function marked cold and inline(never) that will do it for us
150 fft_error_inplace(self.len(), buffer.len(), 0, 0);
151 return; // Unreachable, because fft_error_inplace asserts, but it helps codegen to put it here
152 }
153
154 let result = unsafe { self.perform_fft_butterfly_multi(buffer) };
155
156 if result.is_err() {
157 // We want to trigger a panic, because the buffer sizes weren't cleanly divisible by the FFT size,
158 // but we want to avoid doing it in this function to reduce code size, so call a function marked cold and inline(never) that will do it for us
159 fft_error_inplace(self.len(), buffer.len(), 0, 0);
160 }
161 }
162 #[inline(always)]
163 fn get_inplace_scratch_len(&self) -> usize {
164 0
165 }
166 #[inline(always)]
167 fn get_outofplace_scratch_len(&self) -> usize {
168 0
169 }
170 }
171 impl<T> Length for $struct_name<T> {
172 #[inline(always)]
173 fn len(&self) -> usize {
174 $len
175 }
176 }
177 impl<T> Direction for $struct_name<T> {
178 #[inline(always)]
179 fn fft_direction(&self) -> FftDirection {
180 $direction_fn(self)
181 }
182 }
183 };
184 }
185
186 // _ _________ _ _ _
187 // / | |___ /___ \| |__ (_) |_
188 // | | _____ |_ \ __) | '_ \| | __|
189 // | | |_____| ___) / __/| |_) | | |_
190 // |_| |____/_____|_.__/|_|\__|
191 //
192
193 pub struct WasmSimdF32Butterfly1<T> {
194 direction: FftDirection,
195 _phantom: std::marker::PhantomData<T>,
196 }
197
198 boilerplate_fft_wasm_simd_f32_butterfly!(
199 WasmSimdF32Butterfly1,
200 1,
201 |this: &WasmSimdF32Butterfly1<_>| this.direction
202 );
203 boilerplate_fft_wasm_simd_common_butterfly!(
204 WasmSimdF32Butterfly1,
205 1,
206 |this: &WasmSimdF32Butterfly1<_>| this.direction
207 );
208 impl<T: FftNum> WasmSimdF32Butterfly1<T> {
209 #[inline(always)]
210 pub fn new(direction: FftDirection) -> Self {
211 assert_f32::<T>();
212 Self {
213 direction,
214 _phantom: std::marker::PhantomData,
215 }
216 }
217 #[inline(always)]
218 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
219 let value = buffer.load_partial1_complex(0);
220 buffer.store_partial_lo_complex(value, 0);
221 }
222
223 #[inline(always)]
224 pub(crate) unsafe fn perform_parallel_fft_contiguous(
225 &self,
226 mut buffer: impl WasmSimdArrayMut<f32>,
227 ) {
228 let value = buffer.load_complex(0);
229 buffer.store_complex(value, 0);
230 }
231 }
232
233 // _ __ _ _ _ _ _
234 // / | / /_ | || | | |__ (_) |_
235 // | | _____ | '_ \| || |_| '_ \| | __|
236 // | | |_____| | (_) |__ _| |_) | | |_
237 // |_| \___/ |_| |_.__/|_|\__|
238 //
239
240 pub struct WasmSimdF64Butterfly1<T> {
241 direction: FftDirection,
242 _phantom: std::marker::PhantomData<T>,
243 }
244
245 boilerplate_fft_wasm_simd_f64_butterfly!(
246 WasmSimdF64Butterfly1,
247 1,
248 |this: &WasmSimdF64Butterfly1<_>| this.direction
249 );
250 boilerplate_fft_wasm_simd_common_butterfly!(
251 WasmSimdF64Butterfly1,
252 1,
253 |this: &WasmSimdF64Butterfly1<_>| this.direction
254 );
255 impl<T: FftNum> WasmSimdF64Butterfly1<T> {
256 #[inline(always)]
257 pub fn new(direction: FftDirection) -> Self {
258 assert_f64::<T>();
259 Self {
260 direction,
261 _phantom: std::marker::PhantomData,
262 }
263 }
264 #[inline(always)]
265 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
266 let value = buffer.load_complex(0);
267 buffer.store_complex(value, 0);
268 }
269 }
270
271 // ____ _________ _ _ _
272 // |___ \ |___ /___ \| |__ (_) |_
273 // __) | _____ |_ \ __) | '_ \| | __|
274 // / __/ |_____| ___) / __/| |_) | | |_
275 // |_____| |____/_____|_.__/|_|\__|
276 //
277
278 pub struct WasmSimdF32Butterfly2<T> {
279 direction: FftDirection,
280 _phantom: std::marker::PhantomData<T>,
281 }
282
283 boilerplate_fft_wasm_simd_f32_butterfly!(
284 WasmSimdF32Butterfly2,
285 2,
286 |this: &WasmSimdF32Butterfly2<_>| this.direction
287 );
288 boilerplate_fft_wasm_simd_common_butterfly!(
289 WasmSimdF32Butterfly2,
290 2,
291 |this: &WasmSimdF32Butterfly2<_>| this.direction
292 );
293 impl<T: FftNum> WasmSimdF32Butterfly2<T> {
294 #[inline(always)]
295 pub fn new(direction: FftDirection) -> Self {
296 assert_f32::<T>();
297 Self {
298 direction,
299 _phantom: std::marker::PhantomData,
300 }
301 }
302 #[inline(always)]
303 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
304 let values = buffer.load_complex(0);
305
306 let temp = self.perform_fft_direct(values);
307
308 buffer.store_complex(temp, 0);
309 }
310
311 #[inline(always)]
312 pub(crate) unsafe fn perform_parallel_fft_contiguous(
313 &self,
314 mut buffer: impl WasmSimdArrayMut<f32>,
315 ) {
316 let values_a = buffer.load_complex(0);
317 let values_b = buffer.load_complex(2);
318
319 let out = self.perform_parallel_fft_direct(values_a, values_b);
320
321 let [out02, out13] = transpose_complex_2x2_f32(out[0], out[1]);
322
323 buffer.store_complex(out02, 0);
324 buffer.store_complex(out13, 2);
325 }
326
327 // length 2 fft of x, given as [x0, x1]
328 // result is [X0, X1]
329 #[inline(always)]
330 pub(crate) unsafe fn perform_fft_direct(&self, values: v128) -> v128 {
331 solo_fft2_f32(values)
332 }
333
334 // dual length 2 fft of x and y, given as [x0, x1], [y0, y1]
335 // result is [X0, Y0], [X1, Y1]
336 #[inline(always)]
337 pub(crate) unsafe fn perform_parallel_fft_direct(
338 &self,
339 values_x: v128,
340 values_y: v128,
341 ) -> [v128; 2] {
342 parallel_fft2_contiguous_f32(values_x, values_y)
343 }
344 }
345
346 // double lenth 2 fft of a and b, given as [x0, y0], [x1, y1]
347 // result is [X0, Y0], [X1, Y1]
348 #[inline(always)]
349 pub(crate) unsafe fn parallel_fft2_interleaved_f32(val02: v128, val13: v128) -> [v128; 2] {
350 let temp0 = f32x4_add(val02, val13);
351 let temp1 = f32x4_sub(val02, val13);
352 [temp0, temp1]
353 }
354
355 // double lenth 2 fft of a and b, given as [x0, x1], [y0, y1]
356 // result is [X0, Y0], [X1, Y1]
357 #[inline(always)]
358 unsafe fn parallel_fft2_contiguous_f32(left: v128, right: v128) -> [v128; 2] {
359 let [temp02, temp13] = transpose_complex_2x2_f32(left, right);
360 parallel_fft2_interleaved_f32(temp02, temp13)
361 }
362
363 // length 2 fft of x, given as [x0, x1]
364 // result is [X0, X1]
365 #[inline(always)]
366 unsafe fn solo_fft2_f32(values: v128) -> v128 {
367 let high = u64x2_shuffle::<0, 0>(values, values);
368 let low = u64x2_shuffle::<1, 1>(values, values);
369 let low = f32x4_mul(low, f32x4(1.0, 1.0, -1.0, -1.0));
370 f32x4_add(high, low)
371 }
372
373 // ____ __ _ _ _ _ _
374 // |___ \ / /_ | || | | |__ (_) |_
375 // __) | _____ | '_ \| || |_| '_ \| | __|
376 // / __/ |_____| | (_) |__ _| |_) | | |_
377 // |_____| \___/ |_| |_.__/|_|\__|
378 //
379
380 pub struct WasmSimdF64Butterfly2<T> {
381 direction: FftDirection,
382 _phantom: std::marker::PhantomData<T>,
383 }
384
385 boilerplate_fft_wasm_simd_f64_butterfly!(
386 WasmSimdF64Butterfly2,
387 2,
388 |this: &WasmSimdF64Butterfly2<_>| this.direction
389 );
390 boilerplate_fft_wasm_simd_common_butterfly!(
391 WasmSimdF64Butterfly2,
392 2,
393 |this: &WasmSimdF64Butterfly2<_>| this.direction
394 );
395 impl<T: FftNum> WasmSimdF64Butterfly2<T> {
396 #[inline(always)]
397 pub fn new(direction: FftDirection) -> Self {
398 assert_f64::<T>();
399 Self {
400 direction,
401 _phantom: std::marker::PhantomData,
402 }
403 }
404
405 #[inline(always)]
406 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
407 let value0 = buffer.load_complex(0);
408 let value1 = buffer.load_complex(1);
409
410 let out = self.perform_fft_direct(value0, value1);
411
412 buffer.store_complex(out[0], 0);
413 buffer.store_complex(out[1], 1);
414 }
415
416 #[inline(always)]
417 pub(crate) unsafe fn perform_fft_direct(&self, value0: v128, value1: v128) -> [v128; 2] {
418 solo_fft2_f64(value0, value1)
419 }
420 }
421
422 #[inline(always)]
423 pub(crate) unsafe fn solo_fft2_f64(left: v128, right: v128) -> [v128; 2] {
424 let temp0 = f64x2_add(left, right);
425 let temp1 = f64x2_sub(left, right);
426 [temp0, temp1]
427 }
428
429 // _____ _________ _ _ _
430 // |___ / |___ /___ \| |__ (_) |_
431 // |_ \ _____ |_ \ __) | '_ \| | __|
432 // ___) | |_____| ___) / __/| |_) | | |_
433 // |____/ |____/_____|_.__/|_|\__|
434 //
435
436 pub struct WasmSimdF32Butterfly3<T> {
437 direction: FftDirection,
438 _phantom: std::marker::PhantomData<T>,
439 rotate: Rotate90F32,
440 twiddle: v128,
441 twiddle1re: v128,
442 twiddle1im: v128,
443 }
444
445 boilerplate_fft_wasm_simd_f32_butterfly!(
446 WasmSimdF32Butterfly3,
447 3,
448 |this: &WasmSimdF32Butterfly3<_>| this.direction
449 );
450 boilerplate_fft_wasm_simd_common_butterfly!(
451 WasmSimdF32Butterfly3,
452 3,
453 |this: &WasmSimdF32Butterfly3<_>| this.direction
454 );
455 impl<T: FftNum> WasmSimdF32Butterfly3<T> {
456 #[inline(always)]
457 pub fn new(direction: FftDirection) -> Self {
458 assert_f32::<T>();
459 let rotate = Rotate90F32::new(true);
460 let tw1: Complex<f32> = twiddles::compute_twiddle(1, 3, direction);
461 let twiddle = f32x4(tw1.re, tw1.re, -tw1.im, -tw1.im);
462 let twiddle1re = f32x4_splat(tw1.re);
463 let twiddle1im = f32x4_splat(tw1.im);
464 Self {
465 direction,
466 _phantom: std::marker::PhantomData,
467 rotate,
468 twiddle,
469 twiddle1re,
470 twiddle1im,
471 }
472 }
473 #[inline(always)]
474 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
475 let value0x = buffer.load_partial1_complex(0);
476 let value12 = buffer.load_complex(1);
477
478 let out = self.perform_fft_direct(value0x, value12);
479
480 buffer.store_partial_lo_complex(out[0], 0);
481 buffer.store_complex(out[1], 1);
482 }
483
484 #[inline(always)]
485 pub(crate) unsafe fn perform_parallel_fft_contiguous(
486 &self,
487 mut buffer: impl WasmSimdArrayMut<f32>,
488 ) {
489 let valuea0a1 = buffer.load_complex(0);
490 let valuea2b0 = buffer.load_complex(2);
491 let valueb1b2 = buffer.load_complex(4);
492
493 let value0 = extract_lo_hi_f32(valuea0a1, valuea2b0);
494 let value1 = extract_hi_lo_f32(valuea0a1, valueb1b2);
495 let value2 = extract_lo_hi_f32(valuea2b0, valueb1b2);
496
497 let out = self.perform_parallel_fft_direct(value0, value1, value2);
498
499 let out0 = extract_lo_lo_f32(out[0], out[1]);
500 let out1 = extract_lo_hi_f32(out[2], out[0]);
501 let out2 = extract_hi_hi_f32(out[1], out[2]);
502
503 buffer.store_complex(out0, 0);
504 buffer.store_complex(out1, 2);
505 buffer.store_complex(out2, 4);
506 }
507
508 // length 3 fft of a, given as [x0, 0.0], [x1, x2]
509 // result is [X0, Z], [X1, X2]
510 // The value Z should be discarded.
511 #[inline(always)]
512 pub(crate) unsafe fn perform_fft_direct(&self, value0x: v128, value12: v128) -> [v128; 2] {
513 // This is a WasmSimd translation of the scalar 3-point butterfly
514 let rev12 = reverse_complex_and_negate_hi_f32(value12);
515 let temp12pn = self.rotate.rotate_hi(f32x4_add(value12, rev12));
516 let twiddled = f32x4_mul(temp12pn, self.twiddle);
517 let temp = f32x4_add(value0x, twiddled);
518
519 let out12 = solo_fft2_f32(temp);
520 let out0x = f32x4_add(value0x, temp12pn);
521 [out0x, out12]
522 }
523
524 // length 3 dual fft of a, given as (x0, y0), (x1, y1), (x2, y2).
525 // result is [(X0, Y0), (X1, Y1), (X2, Y2)]
526 #[inline(always)]
527 pub(crate) unsafe fn perform_parallel_fft_direct(
528 &self,
529 value0: v128,
530 value1: v128,
531 value2: v128,
532 ) -> [v128; 3] {
533 // This is a WasmSimd translation of the scalar 3-point butterfly
534 let x12p = f32x4_add(value1, value2);
535 let x12n = f32x4_sub(value1, value2);
536 let sum = f32x4_add(value0, x12p);
537
538 let temp_a = f32x4_mul(self.twiddle1re, x12p);
539 let temp_a = f32x4_add(temp_a, value0);
540
541 let n_rot = self.rotate.rotate_both(x12n);
542 let temp_b = f32x4_mul(self.twiddle1im, n_rot);
543
544 let x1 = f32x4_add(temp_a, temp_b);
545 let x2 = f32x4_sub(temp_a, temp_b);
546 [sum, x1, x2]
547 }
548 }
549
550 // _____ __ _ _ _ _ _
551 // |___ / / /_ | || | | |__ (_) |_
552 // |_ \ _____ | '_ \| || |_| '_ \| | __|
553 // ___) | |_____| | (_) |__ _| |_) | | |_
554 // |____/ \___/ |_| |_.__/|_|\__|
555 //
556
557 pub struct WasmSimdF64Butterfly3<T> {
558 direction: FftDirection,
559 _phantom: std::marker::PhantomData<T>,
560 rotate: Rotate90F64,
561 twiddle1re: v128,
562 twiddle1im: v128,
563 }
564
565 boilerplate_fft_wasm_simd_f64_butterfly!(
566 WasmSimdF64Butterfly3,
567 3,
568 |this: &WasmSimdF64Butterfly3<_>| this.direction
569 );
570 boilerplate_fft_wasm_simd_common_butterfly!(
571 WasmSimdF64Butterfly3,
572 3,
573 |this: &WasmSimdF64Butterfly3<_>| this.direction
574 );
575 impl<T: FftNum> WasmSimdF64Butterfly3<T> {
576 #[inline(always)]
577 pub fn new(direction: FftDirection) -> Self {
578 assert_f64::<T>();
579 let rotate = Rotate90F64::new(true);
580 let tw1: Complex<f64> = twiddles::compute_twiddle(1, 3, direction);
581 let twiddle1re = f64x2_splat(tw1.re);
582 let twiddle1im = f64x2_splat(tw1.im);
583
584 Self {
585 direction,
586 _phantom: std::marker::PhantomData,
587 rotate,
588 twiddle1re,
589 twiddle1im,
590 }
591 }
592
593 #[inline(always)]
594 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
595 let value0 = buffer.load_complex(0);
596 let value1 = buffer.load_complex(1);
597 let value2 = buffer.load_complex(2);
598
599 let out = self.perform_fft_direct(value0, value1, value2);
600
601 buffer.store_complex(out[0], 0);
602 buffer.store_complex(out[1], 1);
603 buffer.store_complex(out[2], 2);
604 }
605
606 // length 3 fft of x, given as x0, x1, x2.
607 // result is [X0, X1, X2]
608 #[inline(always)]
609 pub(crate) unsafe fn perform_fft_direct(
610 &self,
611 value0: v128,
612 value1: v128,
613 value2: v128,
614 ) -> [v128; 3] {
615 // This is a WasmSimd translation of the scalar 3-point butterfly
616 let x12p = f64x2_add(value1, value2);
617 let x12n = f64x2_sub(value1, value2);
618 let sum = f64x2_add(value0, x12p);
619
620 // let temp_a = vfmaq_f64(value0, self.twiddle1re, x12p);
621 let temp_a = f64x2_add(value0, f64x2_mul(self.twiddle1re, x12p));
622
623 let n_rot = self.rotate.rotate(x12n);
624 let temp_b = f64x2_mul(self.twiddle1im, n_rot);
625
626 let x1 = f64x2_add(temp_a, temp_b);
627 let x2 = f64x2_sub(temp_a, temp_b);
628 [sum, x1, x2]
629 }
630 }
631
632 // _ _ _________ _ _ _
633 // | || | |___ /___ \| |__ (_) |_
634 // | || |_ _____ |_ \ __) | '_ \| | __|
635 // |__ _| |_____| ___) / __/| |_) | | |_
636 // |_| |____/_____|_.__/|_|\__|
637 //
638
639 pub struct WasmSimdF32Butterfly4<T> {
640 direction: FftDirection,
641 _phantom: std::marker::PhantomData<T>,
642 rotate: Rotate90F32,
643 }
644
645 boilerplate_fft_wasm_simd_f32_butterfly!(
646 WasmSimdF32Butterfly4,
647 4,
648 |this: &WasmSimdF32Butterfly4<_>| this.direction
649 );
650 boilerplate_fft_wasm_simd_common_butterfly!(
651 WasmSimdF32Butterfly4,
652 4,
653 |this: &WasmSimdF32Butterfly4<_>| this.direction
654 );
655 impl<T: FftNum> WasmSimdF32Butterfly4<T> {
656 #[inline(always)]
657 pub fn new(direction: FftDirection) -> Self {
658 assert_f32::<T>();
659 let rotate = if direction == FftDirection::Inverse {
660 Rotate90F32::new(true)
661 } else {
662 Rotate90F32::new(false)
663 };
664 Self {
665 direction,
666 _phantom: std::marker::PhantomData,
667 rotate,
668 }
669 }
670 #[inline(always)]
671 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
672 let value01 = buffer.load_complex(0);
673 let value23 = buffer.load_complex(2);
674
675 let out = self.perform_fft_direct(value01, value23);
676
677 buffer.store_complex(out[0], 0);
678 buffer.store_complex(out[1], 2);
679 }
680
681 #[inline(always)]
682 pub(crate) unsafe fn perform_parallel_fft_contiguous(
683 &self,
684 mut buffer: impl WasmSimdArrayMut<f32>,
685 ) {
686 let value01a = buffer.load_complex(0);
687 let value23a = buffer.load_complex(2);
688 let value01b = buffer.load_complex(4);
689 let value23b = buffer.load_complex(6);
690
691 let [value0ab, value1ab] = transpose_complex_2x2_f32(value01a, value01b);
692 let [value2ab, value3ab] = transpose_complex_2x2_f32(value23a, value23b);
693
694 let out = self.perform_parallel_fft_direct(value0ab, value1ab, value2ab, value3ab);
695
696 let [out0, out1] = transpose_complex_2x2_f32(out[0], out[1]);
697 let [out2, out3] = transpose_complex_2x2_f32(out[2], out[3]);
698
699 buffer.store_complex(out0, 0);
700 buffer.store_complex(out1, 4);
701 buffer.store_complex(out2, 2);
702 buffer.store_complex(out3, 6);
703 }
704
705 // length 4 fft of a, given as [x0, x1], [x2, x3]
706 // result is [[X0, X1], [X2, X3]]
707 #[inline(always)]
708 pub(crate) unsafe fn perform_fft_direct(&self, value01: v128, value23: v128) -> [v128; 2] {
709 //we're going to hardcode a step of mixed radix
710 //aka we're going to do the six step algorithm
711
712 // step 1: transpose
713 // and
714 // step 2: column FFTs
715 let mut temp = parallel_fft2_interleaved_f32(value01, value23);
716
717 // step 3: apply twiddle factors (only one in this case, and it's either 0 + i or 0 - i)
718 temp[1] = self.rotate.rotate_hi(temp[1]);
719
720 // step 4: transpose, which we're skipping because we're the previous FFTs were non-contiguous
721
722 // step 5: row FFTs
723 // and
724 // step 6: transpose by swapping index 1 and 2
725 parallel_fft2_contiguous_f32(temp[0], temp[1])
726 }
727
728 #[inline(always)]
729 pub(crate) unsafe fn perform_parallel_fft_direct(
730 &self,
731 values0: v128,
732 values1: v128,
733 values2: v128,
734 values3: v128,
735 ) -> [v128; 4] {
736 //we're going to hardcode a step of mixed radix
737 //aka we're going to do the six step algorithm
738
739 // step 1: transpose
740 // and
741 // step 2: column FFTs
742 let temp0 = parallel_fft2_interleaved_f32(values0, values2);
743 let mut temp1 = parallel_fft2_interleaved_f32(values1, values3);
744
745 // step 3: apply twiddle factors (only one in this case, and it's either 0 + i or 0 - i)
746 temp1[1] = self.rotate.rotate_both(temp1[1]);
747
748 // step 4: transpose, which we're skipping because we're the previous FFTs were non-contiguous
749
750 // step 5: row FFTs
751 let out0 = parallel_fft2_interleaved_f32(temp0[0], temp1[0]);
752 let out2 = parallel_fft2_interleaved_f32(temp0[1], temp1[1]);
753
754 // step 6: transpose by swapping index 1 and 2
755 [out0[0], out2[0], out0[1], out2[1]]
756 }
757 }
758
759 // _ _ __ _ _ _ _ _
760 // | || | / /_ | || | | |__ (_) |_
761 // | || |_ _____ | '_ \| || |_| '_ \| | __|
762 // |__ _| |_____| | (_) |__ _| |_) | | |_
763 // |_| \___/ |_| |_.__/|_|\__|
764 //
765
766 pub struct WasmSimdF64Butterfly4<T> {
767 direction: FftDirection,
768 _phantom: std::marker::PhantomData<T>,
769 rotate: Rotate90F64,
770 }
771
772 boilerplate_fft_wasm_simd_f64_butterfly!(
773 WasmSimdF64Butterfly4,
774 4,
775 |this: &WasmSimdF64Butterfly4<_>| this.direction
776 );
777 boilerplate_fft_wasm_simd_common_butterfly!(
778 WasmSimdF64Butterfly4,
779 4,
780 |this: &WasmSimdF64Butterfly4<_>| this.direction
781 );
782 impl<T: FftNum> WasmSimdF64Butterfly4<T> {
783 #[inline(always)]
784 pub fn new(direction: FftDirection) -> Self {
785 assert_f64::<T>();
786 let rotate = if direction == FftDirection::Inverse {
787 Rotate90F64::new(true)
788 } else {
789 Rotate90F64::new(false)
790 };
791
792 Self {
793 direction,
794 _phantom: std::marker::PhantomData,
795 rotate,
796 }
797 }
798
799 #[inline(always)]
800 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
801 let value0 = buffer.load_complex(0);
802 let value1 = buffer.load_complex(1);
803 let value2 = buffer.load_complex(2);
804 let value3 = buffer.load_complex(3);
805
806 let out = self.perform_fft_direct(value0, value1, value2, value3);
807
808 buffer.store_complex(out[0], 0);
809 buffer.store_complex(out[1], 1);
810 buffer.store_complex(out[2], 2);
811 buffer.store_complex(out[3], 3);
812 }
813
814 #[inline(always)]
815 pub(crate) unsafe fn perform_fft_direct(
816 &self,
817 value0: v128,
818 value1: v128,
819 value2: v128,
820 value3: v128,
821 ) -> [v128; 4] {
822 //we're going to hardcode a step of mixed radix
823 //aka we're going to do the six step algorithm
824
825 // step 1: transpose
826 // and
827 // step 2: column FFTs
828 let temp0 = solo_fft2_f64(value0, value2);
829 let mut temp1 = solo_fft2_f64(value1, value3);
830
831 // step 3: apply twiddle factors (only one in this case, and it's either 0 + i or 0 - i)
832 temp1[1] = self.rotate.rotate(temp1[1]);
833
834 // step 4: transpose, which we're skipping because we're the previous FFTs were non-contiguous
835
836 // step 5: row FFTs
837 let out0 = solo_fft2_f64(temp0[0], temp1[0]);
838 let out2 = solo_fft2_f64(temp0[1], temp1[1]);
839
840 // step 6: transpose by swapping index 1 and 2
841 [out0[0], out2[0], out0[1], out2[1]]
842 }
843 }
844
845 // ____ _________ _ _ _
846 // | ___| |___ /___ \| |__ (_) |_
847 // |___ \ _____ |_ \ __) | '_ \| | __|
848 // ___) | |_____| ___) / __/| |_) | | |_
849 // |____/ |____/_____|_.__/|_|\__|
850 //
851
852 pub struct WasmSimdF32Butterfly5<T> {
853 direction: FftDirection,
854 _phantom: std::marker::PhantomData<T>,
855 rotate: Rotate90F32,
856 twiddle12re: v128,
857 twiddle21re: v128,
858 twiddle12im: v128,
859 twiddle21im: v128,
860 twiddle1re: v128,
861 twiddle1im: v128,
862 twiddle2re: v128,
863 twiddle2im: v128,
864 }
865
866 boilerplate_fft_wasm_simd_f32_butterfly!(
867 WasmSimdF32Butterfly5,
868 5,
869 |this: &WasmSimdF32Butterfly5<_>| this.direction
870 );
871 boilerplate_fft_wasm_simd_common_butterfly!(
872 WasmSimdF32Butterfly5,
873 5,
874 |this: &WasmSimdF32Butterfly5<_>| this.direction
875 );
876 impl<T: FftNum> WasmSimdF32Butterfly5<T> {
877 #[inline(always)]
878 pub fn new(direction: FftDirection) -> Self {
879 assert_f32::<T>();
880 let rotate = Rotate90F32::new(true);
881 let tw1: Complex<f32> = twiddles::compute_twiddle(1, 5, direction);
882 let tw2: Complex<f32> = twiddles::compute_twiddle(2, 5, direction);
883 let twiddle12re = f32x4(tw1.re, tw1.re, tw2.re, tw2.re);
884 let twiddle21re = f32x4(tw2.re, tw2.re, tw1.re, tw1.re);
885 let twiddle12im = f32x4(tw1.im, tw1.im, tw2.im, tw2.im);
886 let twiddle21im = f32x4(tw2.im, tw2.im, -tw1.im, -tw1.im);
887 let twiddle1re = f32x4_splat(tw1.re);
888 let twiddle1im = f32x4_splat(tw1.im);
889 let twiddle2re = f32x4_splat(tw2.re);
890 let twiddle2im = f32x4_splat(tw2.im);
891
892 Self {
893 direction,
894 _phantom: std::marker::PhantomData,
895 rotate,
896 twiddle12re,
897 twiddle21re,
898 twiddle12im,
899 twiddle21im,
900 twiddle1re,
901 twiddle1im,
902 twiddle2re,
903 twiddle2im,
904 }
905 }
906 #[inline(always)]
907 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
908 let value00 = buffer.load1_complex(0);
909 let value12 = buffer.load_complex(1);
910 let value34 = buffer.load_complex(3);
911
912 let out = self.perform_fft_direct(value00, value12, value34);
913
914 buffer.store_partial_lo_complex(out[0], 0);
915 buffer.store_complex(out[1], 1);
916 buffer.store_complex(out[2], 3);
917 }
918
919 #[inline(always)]
920 pub(crate) unsafe fn perform_parallel_fft_contiguous(
921 &self,
922 mut buffer: impl WasmSimdArrayMut<f32>,
923 ) {
924 let input_packed = read_complex_to_array!(buffer, {0, 2, 4 ,6, 8});
925
926 let value0 = extract_lo_hi_f32(input_packed[0], input_packed[2]);
927 let value1 = extract_hi_lo_f32(input_packed[0], input_packed[3]);
928 let value2 = extract_lo_hi_f32(input_packed[1], input_packed[3]);
929 let value3 = extract_hi_lo_f32(input_packed[1], input_packed[4]);
930 let value4 = extract_lo_hi_f32(input_packed[2], input_packed[4]);
931
932 let out = self.perform_parallel_fft_direct(value0, value1, value2, value3, value4);
933
934 let out_packed = [
935 extract_lo_lo_f32(out[0], out[1]),
936 extract_lo_lo_f32(out[2], out[3]),
937 extract_lo_hi_f32(out[4], out[0]),
938 extract_hi_hi_f32(out[1], out[2]),
939 extract_hi_hi_f32(out[3], out[4]),
940 ];
941
942 write_complex_to_array_strided!(out_packed, buffer, 2, {0, 1, 2, 3, 4});
943 }
944
945 // length 5 fft of a, given as [x0, x0], [x1, x2], [x3, x4].
946 // result is [[X0, Z], [X1, X2], [X3, X4]]
947 // Note that Z should not be used.
948 #[inline(always)]
949 pub(crate) unsafe fn perform_fft_direct(
950 &self,
951 value00: v128,
952 value12: v128,
953 value34: v128,
954 ) -> [v128; 3] {
955 // This is a WasmSimd translation of the scalar 5-point butterfly
956 let temp43 = reverse_complex_elements_f32(value34);
957 let x1423p = f32x4_add(value12, temp43);
958 let x1423n = f32x4_sub(value12, temp43);
959
960 let x1414p = duplicate_lo_f32(x1423p);
961 let x2323p = duplicate_hi_f32(x1423p);
962 let x1414n = duplicate_lo_f32(x1423n);
963 let x2323n = duplicate_hi_f32(x1423n);
964
965 let temp_a1 = f32x4_mul(self.twiddle12re, x1414p);
966 let temp_b1 = f32x4_mul(self.twiddle12im, x1414n);
967
968 let temp_a = f32x4_add(temp_a1, f32x4_mul(self.twiddle21re, x2323p));
969 let temp_a = f32x4_add(value00, temp_a);
970 let temp_b = f32x4_add(temp_b1, f32x4_mul(self.twiddle21im, x2323n));
971
972 let b_rot = self.rotate.rotate_both(temp_b);
973
974 let x00 = f32x4_add(value00, f32x4_add(x1414p, x2323p));
975
976 let x12 = f32x4_add(temp_a, b_rot);
977 let x34 = reverse_complex_elements_f32(f32x4_sub(temp_a, b_rot));
978 [x00, x12, x34]
979 }
980
981 // length 5 dual fft of x and y, given as (x0, y0), (x1, y1) ... (x4, y4).
982 // result is [(X0, Y0), (X1, Y1) ... (X2, Y2)]
983 #[inline(always)]
984 pub(crate) unsafe fn perform_parallel_fft_direct(
985 &self,
986 value0: v128,
987 value1: v128,
988 value2: v128,
989 value3: v128,
990 value4: v128,
991 ) -> [v128; 5] {
992 // This is a WasmSimd translation of the scalar 3-point butterfly
993 let x14p = f32x4_add(value1, value4);
994 let x14n = f32x4_sub(value1, value4);
995 let x23p = f32x4_add(value2, value3);
996 let x23n = f32x4_sub(value2, value3);
997
998 let temp_a1_1 = f32x4_mul(self.twiddle1re, x14p);
999 let temp_a1_2 = f32x4_mul(self.twiddle2re, x23p);
1000 let temp_b1_1 = f32x4_mul(self.twiddle1im, x14n);
1001 let temp_b1_2 = f32x4_mul(self.twiddle2im, x23n);
1002 let temp_a2_1 = f32x4_mul(self.twiddle1re, x23p);
1003 let temp_a2_2 = f32x4_mul(self.twiddle2re, x14p);
1004 let temp_b2_1 = f32x4_mul(self.twiddle2im, x14n);
1005 let temp_b2_2 = f32x4_mul(self.twiddle1im, x23n);
1006
1007 let temp_a1 = f32x4_add(value0, f32x4_add(temp_a1_1, temp_a1_2));
1008 let temp_b1 = f32x4_add(temp_b1_1, temp_b1_2);
1009 let temp_a2 = f32x4_add(value0, f32x4_add(temp_a2_1, temp_a2_2));
1010 let temp_b2 = f32x4_sub(temp_b2_1, temp_b2_2);
1011
1012 [
1013 f32x4_add(value0, f32x4_add(x14p, x23p)),
1014 f32x4_add(temp_a1, self.rotate.rotate_both(temp_b1)),
1015 f32x4_add(temp_a2, self.rotate.rotate_both(temp_b2)),
1016 f32x4_sub(temp_a2, self.rotate.rotate_both(temp_b2)),
1017 f32x4_sub(temp_a1, self.rotate.rotate_both(temp_b1)),
1018 ]
1019 }
1020 }
1021
1022 // ____ __ _ _ _ _ _
1023 // | ___| / /_ | || | | |__ (_) |_
1024 // |___ \ _____ | '_ \| || |_| '_ \| | __|
1025 // ___) | |_____| | (_) |__ _| |_) | | |_
1026 // |____/ \___/ |_| |_.__/|_|\__|
1027 //
1028
1029 pub struct WasmSimdF64Butterfly5<T> {
1030 direction: FftDirection,
1031 _phantom: std::marker::PhantomData<T>,
1032 rotate: Rotate90F64,
1033 twiddle1re: v128,
1034 twiddle1im: v128,
1035 twiddle2re: v128,
1036 twiddle2im: v128,
1037 }
1038
1039 boilerplate_fft_wasm_simd_f64_butterfly!(
1040 WasmSimdF64Butterfly5,
1041 5,
1042 |this: &WasmSimdF64Butterfly5<_>| this.direction
1043 );
1044 boilerplate_fft_wasm_simd_common_butterfly!(
1045 WasmSimdF64Butterfly5,
1046 5,
1047 |this: &WasmSimdF64Butterfly5<_>| this.direction
1048 );
1049 impl<T: FftNum> WasmSimdF64Butterfly5<T> {
1050 #[inline(always)]
1051 pub fn new(direction: FftDirection) -> Self {
1052 assert_f64::<T>();
1053 let rotate = Rotate90F64::new(true);
1054 let tw1: Complex<f64> = twiddles::compute_twiddle(1, 5, direction);
1055 let tw2: Complex<f64> = twiddles::compute_twiddle(2, 5, direction);
1056 let twiddle1re = f64x2_splat(tw1.re);
1057 let twiddle1im = f64x2_splat(tw1.im);
1058 let twiddle2re = f64x2_splat(tw2.re);
1059 let twiddle2im = f64x2_splat(tw2.im);
1060
1061 Self {
1062 direction,
1063 _phantom: std::marker::PhantomData,
1064 rotate,
1065 twiddle1re,
1066 twiddle1im,
1067 twiddle2re,
1068 twiddle2im,
1069 }
1070 }
1071
1072 #[inline(always)]
1073 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
1074 let value0 = buffer.load_complex(0);
1075 let value1 = buffer.load_complex(1);
1076 let value2 = buffer.load_complex(2);
1077 let value3 = buffer.load_complex(3);
1078 let value4 = buffer.load_complex(4);
1079
1080 let out = self.perform_fft_direct(value0, value1, value2, value3, value4);
1081
1082 buffer.store_complex(out[0], 0);
1083 buffer.store_complex(out[1], 1);
1084 buffer.store_complex(out[2], 2);
1085 buffer.store_complex(out[3], 3);
1086 buffer.store_complex(out[4], 4);
1087 }
1088
1089 // length 5 fft of x, given as x0, x1, x2, x3, x4.
1090 // result is [X0, X1, X2, X3, X4]
1091 #[inline(always)]
1092 pub(crate) unsafe fn perform_fft_direct(
1093 &self,
1094 value0: v128,
1095 value1: v128,
1096 value2: v128,
1097 value3: v128,
1098 value4: v128,
1099 ) -> [v128; 5] {
1100 // This is a WasmSimd translation of the scalar 5-point butterfly
1101 let x14p = f64x2_add(value1, value4);
1102 let x14n = f64x2_sub(value1, value4);
1103 let x23p = f64x2_add(value2, value3);
1104 let x23n = f64x2_sub(value2, value3);
1105
1106 let temp_a1_1 = f64x2_mul(self.twiddle1re, x14p);
1107 let temp_a1_2 = f64x2_mul(self.twiddle2re, x23p);
1108 let temp_a2_1 = f64x2_mul(self.twiddle2re, x14p);
1109 let temp_a2_2 = f64x2_mul(self.twiddle1re, x23p);
1110
1111 let temp_b1_1 = f64x2_mul(self.twiddle1im, x14n);
1112 let temp_b1_2 = f64x2_mul(self.twiddle2im, x23n);
1113 let temp_b2_1 = f64x2_mul(self.twiddle2im, x14n);
1114 let temp_b2_2 = f64x2_mul(self.twiddle1im, x23n);
1115
1116 let temp_a1 = f64x2_add(value0, f64x2_add(temp_a1_1, temp_a1_2));
1117 let temp_a2 = f64x2_add(value0, f64x2_add(temp_a2_1, temp_a2_2));
1118
1119 let temp_b1 = f64x2_add(temp_b1_1, temp_b1_2);
1120 let temp_b2 = f64x2_sub(temp_b2_1, temp_b2_2);
1121
1122 let temp_b1_rot = self.rotate.rotate(temp_b1);
1123 let temp_b2_rot = self.rotate.rotate(temp_b2);
1124 [
1125 f64x2_add(value0, f64x2_add(x14p, x23p)),
1126 f64x2_add(temp_a1, temp_b1_rot),
1127 f64x2_add(temp_a2, temp_b2_rot),
1128 f64x2_sub(temp_a2, temp_b2_rot),
1129 f64x2_sub(temp_a1, temp_b1_rot),
1130 ]
1131 }
1132 }
1133
1134 // __ _________ _ _ _
1135 // / /_ |___ /___ \| |__ (_) |_
1136 // | '_ \ _____ |_ \ __) | '_ \| | __|
1137 // | (_) | |_____| ___) / __/| |_) | | |_
1138 // \___/ |____/_____|_.__/|_|\__|
1139 //
1140
1141 pub struct WasmSimdF32Butterfly6<T> {
1142 direction: FftDirection,
1143 _phantom: std::marker::PhantomData<T>,
1144 bf3: WasmSimdF32Butterfly3<T>,
1145 }
1146
1147 boilerplate_fft_wasm_simd_f32_butterfly!(
1148 WasmSimdF32Butterfly6,
1149 6,
1150 |this: &WasmSimdF32Butterfly6<_>| this.direction
1151 );
1152 boilerplate_fft_wasm_simd_common_butterfly!(
1153 WasmSimdF32Butterfly6,
1154 6,
1155 |this: &WasmSimdF32Butterfly6<_>| this.direction
1156 );
1157 impl<T: FftNum> WasmSimdF32Butterfly6<T> {
1158 #[inline(always)]
1159 pub fn new(direction: FftDirection) -> Self {
1160 assert_f32::<T>();
1161 let bf3 = WasmSimdF32Butterfly3::new(direction);
1162
1163 Self {
1164 direction,
1165 _phantom: std::marker::PhantomData,
1166 bf3,
1167 }
1168 }
1169
1170 #[inline(always)]
1171 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
1172 let value01 = buffer.load_complex(0);
1173 let value23 = buffer.load_complex(2);
1174 let value45 = buffer.load_complex(4);
1175
1176 let out = self.perform_fft_direct(value01, value23, value45);
1177
1178 buffer.store_complex(out[0], 0);
1179 buffer.store_complex(out[1], 2);
1180 buffer.store_complex(out[2], 4);
1181 }
1182
1183 #[inline(always)]
1184 pub(crate) unsafe fn perform_parallel_fft_contiguous(
1185 &self,
1186 mut buffer: impl WasmSimdArrayMut<f32>,
1187 ) {
1188 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10});
1189
1190 let values = interleave_complex_f32!(input_packed, 3, {0, 1, 2});
1191
1192 let out = self.perform_parallel_fft_direct(
1193 values[0], values[1], values[2], values[3], values[4], values[5],
1194 );
1195
1196 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4});
1197 write_complex_to_array_strided!(out_sorted, buffer, 2, {0, 1, 2, 3, 4, 5});
1198 }
1199
1200 #[inline(always)]
1201 pub(crate) unsafe fn perform_fft_direct(
1202 &self,
1203 value01: v128,
1204 value23: v128,
1205 value45: v128,
1206 ) -> [v128; 3] {
1207 // Algorithm: 3x2 good-thomas
1208
1209 // Size-3 FFTs down the columns of our reordered array
1210 let reord0 = extract_lo_hi_f32(value01, value23);
1211 let reord1 = extract_lo_hi_f32(value23, value45);
1212 let reord2 = extract_lo_hi_f32(value45, value01);
1213
1214 let mid = self.bf3.perform_parallel_fft_direct(reord0, reord1, reord2);
1215
1216 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
1217
1218 // Transpose the data and do size-2 FFTs down the columns
1219 let [output0, output1] = parallel_fft2_contiguous_f32(mid[0], mid[1]);
1220 let output2 = solo_fft2_f32(mid[2]);
1221
1222 // Reorder into output
1223 [
1224 extract_lo_hi_f32(output0, output1),
1225 extract_lo_lo_f32(output2, output1),
1226 extract_hi_hi_f32(output0, output2),
1227 ]
1228 }
1229
1230 #[inline(always)]
1231 pub(crate) unsafe fn perform_parallel_fft_direct(
1232 &self,
1233 value0: v128,
1234 value1: v128,
1235 value2: v128,
1236 value3: v128,
1237 value4: v128,
1238 value5: v128,
1239 ) -> [v128; 6] {
1240 // Algorithm: 3x2 good-thomas
1241
1242 // Size-3 FFTs down the columns of our reordered array
1243 let mid0 = self.bf3.perform_parallel_fft_direct(value0, value2, value4);
1244 let mid1 = self.bf3.perform_parallel_fft_direct(value3, value5, value1);
1245
1246 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
1247
1248 // Transpose the data and do size-2 FFTs down the columns
1249 let [output0, output1] = parallel_fft2_interleaved_f32(mid0[0], mid1[0]);
1250 let [output2, output3] = parallel_fft2_interleaved_f32(mid0[1], mid1[1]);
1251 let [output4, output5] = parallel_fft2_interleaved_f32(mid0[2], mid1[2]);
1252
1253 // Reorder into output
1254 [output0, output3, output4, output1, output2, output5]
1255 }
1256 }
1257
1258 // __ __ _ _ _ _ _
1259 // / /_ / /_ | || | | |__ (_) |_
1260 // | '_ \ _____ | '_ \| || |_| '_ \| | __|
1261 // | (_) | |_____| | (_) |__ _| |_) | | |_
1262 // \___/ \___/ |_| |_.__/|_|\__|
1263 //
1264
1265 pub struct WasmSimdF64Butterfly6<T> {
1266 direction: FftDirection,
1267 _phantom: std::marker::PhantomData<T>,
1268 bf3: WasmSimdF64Butterfly3<T>,
1269 }
1270
1271 boilerplate_fft_wasm_simd_f64_butterfly!(
1272 WasmSimdF64Butterfly6,
1273 6,
1274 |this: &WasmSimdF64Butterfly6<_>| this.direction
1275 );
1276 boilerplate_fft_wasm_simd_common_butterfly!(
1277 WasmSimdF64Butterfly6,
1278 6,
1279 |this: &WasmSimdF64Butterfly6<_>| this.direction
1280 );
1281 impl<T: FftNum> WasmSimdF64Butterfly6<T> {
1282 #[inline(always)]
1283 pub fn new(direction: FftDirection) -> Self {
1284 assert_f64::<T>();
1285 let bf3 = WasmSimdF64Butterfly3::new(direction);
1286
1287 Self {
1288 direction,
1289 _phantom: std::marker::PhantomData,
1290 bf3,
1291 }
1292 }
1293
1294 #[inline(always)]
1295 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
1296 let value0 = buffer.load_complex(0);
1297 let value1 = buffer.load_complex(1);
1298 let value2 = buffer.load_complex(2);
1299 let value3 = buffer.load_complex(3);
1300 let value4 = buffer.load_complex(4);
1301 let value5 = buffer.load_complex(5);
1302
1303 let out = self.perform_fft_direct(value0, value1, value2, value3, value4, value5);
1304
1305 buffer.store_complex(out[0], 0);
1306 buffer.store_complex(out[1], 1);
1307 buffer.store_complex(out[2], 2);
1308 buffer.store_complex(out[3], 3);
1309 buffer.store_complex(out[4], 4);
1310 buffer.store_complex(out[5], 5);
1311 }
1312
1313 #[inline(always)]
1314 pub(crate) unsafe fn perform_fft_direct(
1315 &self,
1316 value0: v128,
1317 value1: v128,
1318 value2: v128,
1319 value3: v128,
1320 value4: v128,
1321 value5: v128,
1322 ) -> [v128; 6] {
1323 // Algorithm: 3x2 good-thomas
1324
1325 // Size-3 FFTs down the columns of our reordered array
1326 let mid0 = self.bf3.perform_fft_direct(value0, value2, value4);
1327 let mid1 = self.bf3.perform_fft_direct(value3, value5, value1);
1328
1329 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
1330
1331 // Transpose the data and do size-2 FFTs down the columns
1332 let [output0, output1] = solo_fft2_f64(mid0[0], mid1[0]);
1333 let [output2, output3] = solo_fft2_f64(mid0[1], mid1[1]);
1334 let [output4, output5] = solo_fft2_f64(mid0[2], mid1[2]);
1335
1336 // Reorder into output
1337 [output0, output3, output4, output1, output2, output5]
1338 }
1339 }
1340
1341 // ___ _________ _ _ _
1342 // ( _ ) |___ /___ \| |__ (_) |_
1343 // / _ \ _____ |_ \ __) | '_ \| | __|
1344 // | (_) | |_____| ___) / __/| |_) | | |_
1345 // \___/ |____/_____|_.__/|_|\__|
1346 //
1347
1348 pub struct WasmSimdF32Butterfly8<T> {
1349 root2: v128,
1350 root2_dual: v128,
1351 direction: FftDirection,
1352 bf4: WasmSimdF32Butterfly4<T>,
1353 rotate90: Rotate90F32,
1354 }
1355
1356 boilerplate_fft_wasm_simd_f32_butterfly!(
1357 WasmSimdF32Butterfly8,
1358 8,
1359 |this: &WasmSimdF32Butterfly8<_>| this.direction
1360 );
1361 boilerplate_fft_wasm_simd_common_butterfly!(
1362 WasmSimdF32Butterfly8,
1363 8,
1364 |this: &WasmSimdF32Butterfly8<_>| this.direction
1365 );
1366 impl<T: FftNum> WasmSimdF32Butterfly8<T> {
1367 #[inline(always)]
1368 pub fn new(direction: FftDirection) -> Self {
1369 assert_f32::<T>();
1370 let bf4 = WasmSimdF32Butterfly4::new(direction);
1371 let root2 = f32x4(1.0, 1.0, 0.5f32.sqrt(), 0.5f32.sqrt());
1372 let root2_dual = f32x4_splat(0.5f32.sqrt());
1373 let rotate90 = if direction == FftDirection::Inverse {
1374 Rotate90F32::new(true)
1375 } else {
1376 Rotate90F32::new(false)
1377 };
1378 Self {
1379 root2,
1380 root2_dual,
1381 direction,
1382 bf4,
1383 rotate90,
1384 }
1385 }
1386
1387 #[inline(always)]
1388 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
1389 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6});
1390
1391 let out = self.perform_fft_direct(input_packed);
1392
1393 write_complex_to_array_strided!(out, buffer, 2, {0,1,2,3});
1394 }
1395
1396 #[inline(always)]
1397 pub(crate) unsafe fn perform_parallel_fft_contiguous(
1398 &self,
1399 mut buffer: impl WasmSimdArrayMut<f32>,
1400 ) {
1401 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14});
1402
1403 let values = interleave_complex_f32!(input_packed, 4, {0, 1, 2, 3});
1404
1405 let out = self.perform_parallel_fft_direct(values);
1406
1407 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4, 6});
1408
1409 write_complex_to_array_strided!(out_sorted, buffer, 2, {0,1,2,3,4,5,6,7});
1410 }
1411
1412 #[inline(always)]
1413 unsafe fn perform_fft_direct(&self, values: [v128; 4]) -> [v128; 4] {
1414 // we're going to hardcode a step of mixed radix
1415 // step 1: copy and reorder the input into the scratch
1416 let [in02, in13] = transpose_complex_2x2_f32(values[0], values[1]);
1417 let [in46, in57] = transpose_complex_2x2_f32(values[2], values[3]);
1418
1419 // step 2: column FFTs
1420 let val0 = self.bf4.perform_fft_direct(in02, in46);
1421 let mut val2 = self.bf4.perform_fft_direct(in13, in57);
1422
1423 // step 3: apply twiddle factors
1424 let val2b = self.rotate90.rotate_hi(val2[0]);
1425 let val2c = f32x4_add(val2b, val2[0]);
1426 let val2d = f32x4_mul(val2c, self.root2);
1427 val2[0] = extract_lo_hi_f32(val2[0], val2d);
1428
1429 let val3b = self.rotate90.rotate_both(val2[1]);
1430 let val3c = f32x4_sub(val3b, val2[1]);
1431 let val3d = f32x4_mul(val3c, self.root2);
1432 val2[1] = extract_lo_hi_f32(val3b, val3d);
1433
1434 // step 4: transpose -- skipped because we're going to do the next FFTs non-contiguously
1435
1436 // step 5: row FFTs
1437 let out0 = parallel_fft2_interleaved_f32(val0[0], val2[0]);
1438 let out1 = parallel_fft2_interleaved_f32(val0[1], val2[1]);
1439
1440 // step 6: rearrange and copy to buffer
1441 [out0[0], out1[0], out0[1], out1[1]]
1442 }
1443
1444 #[inline(always)]
1445 unsafe fn perform_parallel_fft_direct(&self, values: [v128; 8]) -> [v128; 8] {
1446 // we're going to hardcode a step of mixed radix
1447 // step 1: copy and reorder the input into the scratch
1448 // and
1449 // step 2: column FFTs
1450 let val03 = self
1451 .bf4
1452 .perform_parallel_fft_direct(values[0], values[2], values[4], values[6]);
1453 let mut val47 = self
1454 .bf4
1455 .perform_parallel_fft_direct(values[1], values[3], values[5], values[7]);
1456
1457 // step 3: apply twiddle factors
1458 let val5b = self.rotate90.rotate_both(val47[1]);
1459 let val5c = f32x4_add(val5b, val47[1]);
1460 val47[1] = f32x4_mul(val5c, self.root2_dual);
1461 val47[2] = self.rotate90.rotate_both(val47[2]);
1462 let val7b = self.rotate90.rotate_both(val47[3]);
1463 let val7c = f32x4_sub(val7b, val47[3]);
1464 val47[3] = f32x4_mul(val7c, self.root2_dual);
1465
1466 // step 4: transpose -- skipped because we're going to do the next FFTs non-contiguously
1467
1468 // step 5: row FFTs
1469 let out0 = parallel_fft2_interleaved_f32(val03[0], val47[0]);
1470 let out1 = parallel_fft2_interleaved_f32(val03[1], val47[1]);
1471 let out2 = parallel_fft2_interleaved_f32(val03[2], val47[2]);
1472 let out3 = parallel_fft2_interleaved_f32(val03[3], val47[3]);
1473
1474 // step 6: rearrange and copy to buffer
1475 [
1476 out0[0], out1[0], out2[0], out3[0], out0[1], out1[1], out2[1], out3[1],
1477 ]
1478 }
1479 }
1480
1481 // ___ __ _ _ _ _ _
1482 // ( _ ) / /_ | || | | |__ (_) |_
1483 // / _ \ _____ | '_ \| || |_| '_ \| | __|
1484 // | (_) | |_____| | (_) |__ _| |_) | | |_
1485 // \___/ \___/ |_| |_.__/|_|\__|
1486 //
1487
1488 pub struct WasmSimdF64Butterfly8<T> {
1489 root2: v128,
1490 direction: FftDirection,
1491 bf4: WasmSimdF64Butterfly4<T>,
1492 rotate90: Rotate90F64,
1493 }
1494
1495 boilerplate_fft_wasm_simd_f64_butterfly!(
1496 WasmSimdF64Butterfly8,
1497 8,
1498 |this: &WasmSimdF64Butterfly8<_>| this.direction
1499 );
1500 boilerplate_fft_wasm_simd_common_butterfly!(
1501 WasmSimdF64Butterfly8,
1502 8,
1503 |this: &WasmSimdF64Butterfly8<_>| this.direction
1504 );
1505 impl<T: FftNum> WasmSimdF64Butterfly8<T> {
1506 #[inline(always)]
1507 pub fn new(direction: FftDirection) -> Self {
1508 assert_f64::<T>();
1509 let bf4 = WasmSimdF64Butterfly4::new(direction);
1510 let root2 = f64x2_splat(0.5f64.sqrt());
1511 let rotate90 = if direction == FftDirection::Inverse {
1512 Rotate90F64::new(true)
1513 } else {
1514 Rotate90F64::new(false)
1515 };
1516 Self {
1517 root2,
1518 direction,
1519 bf4,
1520 rotate90,
1521 }
1522 }
1523
1524 #[inline(always)]
1525 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
1526 let values = read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7});
1527
1528 let out = self.perform_fft_direct(values);
1529
1530 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7});
1531 }
1532
1533 #[inline(always)]
1534 unsafe fn perform_fft_direct(&self, values: [v128; 8]) -> [v128; 8] {
1535 // we're going to hardcode a step of mixed radix
1536 // step 1: copy and reorder the input into the scratch
1537 // and
1538 // step 2: column FFTs
1539 let val03 = self
1540 .bf4
1541 .perform_fft_direct(values[0], values[2], values[4], values[6]);
1542 let mut val47 = self
1543 .bf4
1544 .perform_fft_direct(values[1], values[3], values[5], values[7]);
1545
1546 // step 3: apply twiddle factors
1547 let val5b = self.rotate90.rotate(val47[1]);
1548 let val5c = f64x2_add(val5b, val47[1]);
1549 val47[1] = f64x2_mul(val5c, self.root2);
1550 val47[2] = self.rotate90.rotate(val47[2]);
1551 let val7b = self.rotate90.rotate(val47[3]);
1552 let val7c = f64x2_sub(val7b, val47[3]);
1553 val47[3] = f64x2_mul(val7c, self.root2);
1554
1555 // step 4: transpose -- skipped because we're going to do the next FFTs non-contiguously
1556
1557 // step 5: row FFTs
1558 let out0 = solo_fft2_f64(val03[0], val47[0]);
1559 let out1 = solo_fft2_f64(val03[1], val47[1]);
1560 let out2 = solo_fft2_f64(val03[2], val47[2]);
1561 let out3 = solo_fft2_f64(val03[3], val47[3]);
1562
1563 // step 6: rearrange and copy to buffer
1564 [
1565 out0[0], out1[0], out2[0], out3[0], out0[1], out1[1], out2[1], out3[1],
1566 ]
1567 }
1568 }
1569
1570 // ___ _________ _ _ _
1571 // / _ \ |___ /___ \| |__ (_) |_
1572 // | (_) | _____ |_ \ __) | '_ \| | __|
1573 // \__, | |_____| ___) / __/| |_) | | |_
1574 // /_/ |____/_____|_.__/|_|\__|
1575 //
1576 pub struct WasmSimdF32Butterfly9<T> {
1577 direction: FftDirection,
1578 _phantom: std::marker::PhantomData<T>,
1579 bf3: WasmSimdF32Butterfly3<T>,
1580 twiddle1: v128,
1581 twiddle2: v128,
1582 twiddle4: v128,
1583 }
1584
1585 boilerplate_fft_wasm_simd_f32_butterfly!(
1586 WasmSimdF32Butterfly9,
1587 9,
1588 |this: &WasmSimdF32Butterfly9<_>| this.direction
1589 );
1590 boilerplate_fft_wasm_simd_common_butterfly!(
1591 WasmSimdF32Butterfly9,
1592 9,
1593 |this: &WasmSimdF32Butterfly9<_>| this.direction
1594 );
1595 impl<T: FftNum> WasmSimdF32Butterfly9<T> {
1596 #[inline(always)]
1597 pub fn new(direction: FftDirection) -> Self {
1598 assert_f32::<T>();
1599 let bf3 = WasmSimdF32Butterfly3::new(direction);
1600 let tw1: Complex<f32> = twiddles::compute_twiddle(1, 9, direction);
1601 let tw2: Complex<f32> = twiddles::compute_twiddle(2, 9, direction);
1602 let tw4: Complex<f32> = twiddles::compute_twiddle(4, 9, direction);
1603 let twiddle1 = f32x4(tw1.re, tw1.im, tw1.re, tw1.im);
1604 let twiddle2 = f32x4(tw2.re, tw2.im, tw2.re, tw2.im);
1605 let twiddle4 = f32x4(tw4.re, tw4.im, tw4.re, tw4.im);
1606
1607 Self {
1608 direction,
1609 _phantom: std::marker::PhantomData,
1610 bf3,
1611 twiddle1,
1612 twiddle2,
1613 twiddle4,
1614 }
1615 }
1616
1617 #[inline(always)]
1618 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
1619 // A single WasmSimd 9-point will need a lot of shuffling, let's just reuse the dual one
1620 let values = read_partial1_complex_to_array!(buffer, {0,1,2,3,4,5,6,7,8});
1621
1622 let out = self.perform_parallel_fft_direct(values);
1623
1624 for n in 0..9 {
1625 buffer.store_partial_lo_complex(out[n], n);
1626 }
1627 }
1628
1629 #[inline(always)]
1630 pub(crate) unsafe fn perform_parallel_fft_contiguous(
1631 &self,
1632 mut buffer: impl WasmSimdArrayMut<f32>,
1633 ) {
1634 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16});
1635
1636 let values = [
1637 extract_lo_hi_f32(input_packed[0], input_packed[4]),
1638 extract_hi_lo_f32(input_packed[0], input_packed[5]),
1639 extract_lo_hi_f32(input_packed[1], input_packed[5]),
1640 extract_hi_lo_f32(input_packed[1], input_packed[6]),
1641 extract_lo_hi_f32(input_packed[2], input_packed[6]),
1642 extract_hi_lo_f32(input_packed[2], input_packed[7]),
1643 extract_lo_hi_f32(input_packed[3], input_packed[7]),
1644 extract_hi_lo_f32(input_packed[3], input_packed[8]),
1645 extract_lo_hi_f32(input_packed[4], input_packed[8]),
1646 ];
1647
1648 let out = self.perform_parallel_fft_direct(values);
1649
1650 let out_packed = [
1651 extract_lo_lo_f32(out[0], out[1]),
1652 extract_lo_lo_f32(out[2], out[3]),
1653 extract_lo_lo_f32(out[4], out[5]),
1654 extract_lo_lo_f32(out[6], out[7]),
1655 extract_lo_hi_f32(out[8], out[0]),
1656 extract_hi_hi_f32(out[1], out[2]),
1657 extract_hi_hi_f32(out[3], out[4]),
1658 extract_hi_hi_f32(out[5], out[6]),
1659 extract_hi_hi_f32(out[7], out[8]),
1660 ];
1661
1662 write_complex_to_array_strided!(out_packed, buffer, 2, {0,1,2,3,4,5,6,7,8});
1663 }
1664
1665 #[inline(always)]
1666 pub(crate) unsafe fn perform_parallel_fft_direct(&self, values: [v128; 9]) -> [v128; 9] {
1667 // Algorithm: 3x3 mixed radix
1668
1669 // Size-3 FFTs down the columns
1670 let mid0 = self
1671 .bf3
1672 .perform_parallel_fft_direct(values[0], values[3], values[6]);
1673 let mut mid1 = self
1674 .bf3
1675 .perform_parallel_fft_direct(values[1], values[4], values[7]);
1676 let mut mid2 = self
1677 .bf3
1678 .perform_parallel_fft_direct(values[2], values[5], values[8]);
1679
1680 // Apply twiddle factors. Note that we're re-using twiddle2
1681 mid1[1] = mul_complex_f32(self.twiddle1, mid1[1]);
1682 mid1[2] = mul_complex_f32(self.twiddle2, mid1[2]);
1683 mid2[1] = mul_complex_f32(self.twiddle2, mid2[1]);
1684 mid2[2] = mul_complex_f32(self.twiddle4, mid2[2]);
1685
1686 let [output0, output1, output2] = self
1687 .bf3
1688 .perform_parallel_fft_direct(mid0[0], mid1[0], mid2[0]);
1689 let [output3, output4, output5] = self
1690 .bf3
1691 .perform_parallel_fft_direct(mid0[1], mid1[1], mid2[1]);
1692 let [output6, output7, output8] = self
1693 .bf3
1694 .perform_parallel_fft_direct(mid0[2], mid1[2], mid2[2]);
1695
1696 [
1697 output0, output3, output6, output1, output4, output7, output2, output5, output8,
1698 ]
1699 }
1700 }
1701
1702 // ___ __ _ _ _ _ _
1703 // / _ \ / /_ | || | | |__ (_) |_
1704 // | (_) | _____ | '_ \| || |_| '_ \| | __|
1705 // \__, | |_____| | (_) |__ _| |_) | | |_
1706 // /_/ \___/ |_| |_.__/|_|\__|
1707 //
1708
1709 pub struct WasmSimdF64Butterfly9<T> {
1710 direction: FftDirection,
1711 _phantom: std::marker::PhantomData<T>,
1712 bf3: WasmSimdF64Butterfly3<T>,
1713 twiddle1: v128,
1714 twiddle2: v128,
1715 twiddle4: v128,
1716 }
1717
1718 boilerplate_fft_wasm_simd_f64_butterfly!(
1719 WasmSimdF64Butterfly9,
1720 9,
1721 |this: &WasmSimdF64Butterfly9<_>| this.direction
1722 );
1723 boilerplate_fft_wasm_simd_common_butterfly!(
1724 WasmSimdF64Butterfly9,
1725 9,
1726 |this: &WasmSimdF64Butterfly9<_>| this.direction
1727 );
1728 impl<T: FftNum> WasmSimdF64Butterfly9<T> {
1729 #[inline(always)]
1730 pub fn new(direction: FftDirection) -> Self {
1731 assert_f64::<T>();
1732 let bf3 = WasmSimdF64Butterfly3::new(direction);
1733 let tw1: Complex<f64> = twiddles::compute_twiddle(1, 9, direction);
1734 let tw2: Complex<f64> = twiddles::compute_twiddle(2, 9, direction);
1735 let tw4: Complex<f64> = twiddles::compute_twiddle(4, 9, direction);
1736 let twiddle1 = f64x2(tw1.re, tw1.im);
1737 let twiddle2 = f64x2(tw2.re, tw2.im);
1738 let twiddle4 = f64x2(tw4.re, tw4.im);
1739
1740 Self {
1741 direction,
1742 _phantom: std::marker::PhantomData,
1743 bf3,
1744 twiddle1,
1745 twiddle2,
1746 twiddle4,
1747 }
1748 }
1749
1750 #[inline(always)]
1751 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
1752 let values = read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8});
1753
1754 let out = self.perform_fft_direct(values);
1755
1756 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8});
1757 }
1758
1759 #[inline(always)]
1760 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 9]) -> [v128; 9] {
1761 // Algorithm: 3x3 mixed radix
1762
1763 // Size-3 FFTs down the columns
1764 let mid0 = self.bf3.perform_fft_direct(values[0], values[3], values[6]);
1765 let mut mid1 = self.bf3.perform_fft_direct(values[1], values[4], values[7]);
1766 let mut mid2 = self.bf3.perform_fft_direct(values[2], values[5], values[8]);
1767
1768 // Apply twiddle factors. Note that we're re-using twiddle2
1769 mid1[1] = mul_complex_f64(self.twiddle1, mid1[1]);
1770 mid1[2] = mul_complex_f64(self.twiddle2, mid1[2]);
1771 mid2[1] = mul_complex_f64(self.twiddle2, mid2[1]);
1772 mid2[2] = mul_complex_f64(self.twiddle4, mid2[2]);
1773
1774 let [output0, output1, output2] = self.bf3.perform_fft_direct(mid0[0], mid1[0], mid2[0]);
1775 let [output3, output4, output5] = self.bf3.perform_fft_direct(mid0[1], mid1[1], mid2[1]);
1776 let [output6, output7, output8] = self.bf3.perform_fft_direct(mid0[2], mid1[2], mid2[2]);
1777
1778 [
1779 output0, output3, output6, output1, output4, output7, output2, output5, output8,
1780 ]
1781 }
1782 }
1783
1784 // _ ___ _________ _ _ _
1785 // / |/ _ \ |___ /___ \| |__ (_) |_
1786 // | | | | | _____ |_ \ __) | '_ \| | __|
1787 // | | |_| | |_____| ___) / __/| |_) | | |_
1788 // |_|\___/ |____/_____|_.__/|_|\__|
1789 //
1790
1791 pub struct WasmSimdF32Butterfly10<T> {
1792 direction: FftDirection,
1793 _phantom: std::marker::PhantomData<T>,
1794 bf5: WasmSimdF32Butterfly5<T>,
1795 }
1796
1797 boilerplate_fft_wasm_simd_f32_butterfly!(
1798 WasmSimdF32Butterfly10,
1799 10,
1800 |this: &WasmSimdF32Butterfly10<_>| this.direction
1801 );
1802 boilerplate_fft_wasm_simd_common_butterfly!(
1803 WasmSimdF32Butterfly10,
1804 10,
1805 |this: &WasmSimdF32Butterfly10<_>| this.direction
1806 );
1807 impl<T: FftNum> WasmSimdF32Butterfly10<T> {
1808 #[inline(always)]
1809 pub fn new(direction: FftDirection) -> Self {
1810 assert_f32::<T>();
1811 let bf5 = WasmSimdF32Butterfly5::new(direction);
1812 Self {
1813 direction,
1814 _phantom: std::marker::PhantomData,
1815 bf5,
1816 }
1817 }
1818
1819 #[inline(always)]
1820 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
1821 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8});
1822
1823 let out = self.perform_fft_direct(input_packed);
1824
1825 write_complex_to_array_strided!(out, buffer, 2, {0,1,2,3,4});
1826 }
1827
1828 #[inline(always)]
1829 pub(crate) unsafe fn perform_parallel_fft_contiguous(
1830 &self,
1831 mut buffer: impl WasmSimdArrayMut<f32>,
1832 ) {
1833 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18});
1834
1835 let values = interleave_complex_f32!(input_packed, 5, {0, 1, 2, 3, 4});
1836
1837 let out = self.perform_parallel_fft_direct(values);
1838
1839 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4, 6, 8});
1840
1841 write_complex_to_array_strided!(out_sorted, buffer, 2, {0,1,2,3,4,5,6,7,8,9});
1842 }
1843
1844 #[inline(always)]
1845 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 5]) -> [v128; 5] {
1846 // Algorithm: 5x2 good-thomas
1847 // Reorder and pack
1848 let reord0 = extract_lo_hi_f32(values[0], values[2]);
1849 let reord1 = extract_lo_hi_f32(values[1], values[3]);
1850 let reord2 = extract_lo_hi_f32(values[2], values[4]);
1851 let reord3 = extract_lo_hi_f32(values[3], values[0]);
1852 let reord4 = extract_lo_hi_f32(values[4], values[1]);
1853
1854 // Size-5 FFTs down the columns of our reordered array
1855 let mids = self
1856 .bf5
1857 .perform_parallel_fft_direct(reord0, reord1, reord2, reord3, reord4);
1858
1859 // Since this is good-thomas algorithm, we don't need twiddle factors
1860
1861 // Transpose the data and do size-2 FFTs down the columns
1862 let [temp01, temp23] = parallel_fft2_contiguous_f32(mids[0], mids[1]);
1863 let [temp45, temp67] = parallel_fft2_contiguous_f32(mids[2], mids[3]);
1864 let temp89 = solo_fft2_f32(mids[4]);
1865
1866 // Reorder
1867 let out01 = extract_lo_hi_f32(temp01, temp23);
1868 let out23 = extract_lo_hi_f32(temp45, temp67);
1869 let out45 = extract_lo_lo_f32(temp89, temp23);
1870 let out67 = extract_hi_lo_f32(temp01, temp67);
1871 let out89 = extract_hi_hi_f32(temp45, temp89);
1872
1873 [out01, out23, out45, out67, out89]
1874 }
1875
1876 #[inline(always)]
1877 pub(crate) unsafe fn perform_parallel_fft_direct(&self, values: [v128; 10]) -> [v128; 10] {
1878 // Algorithm: 5x2 good-thomas
1879
1880 // Size-5 FFTs down the columns of our reordered array
1881 let mid0 = self
1882 .bf5
1883 .perform_parallel_fft_direct(values[0], values[2], values[4], values[6], values[8]);
1884 let mid1 = self
1885 .bf5
1886 .perform_parallel_fft_direct(values[5], values[7], values[9], values[1], values[3]);
1887
1888 // Since this is good-thomas algorithm, we don't need twiddle factors
1889
1890 // Transpose the data and do size-2 FFTs down the columns
1891 let [output0, output1] = parallel_fft2_interleaved_f32(mid0[0], mid1[0]);
1892 let [output2, output3] = parallel_fft2_interleaved_f32(mid0[1], mid1[1]);
1893 let [output4, output5] = parallel_fft2_interleaved_f32(mid0[2], mid1[2]);
1894 let [output6, output7] = parallel_fft2_interleaved_f32(mid0[3], mid1[3]);
1895 let [output8, output9] = parallel_fft2_interleaved_f32(mid0[4], mid1[4]);
1896
1897 // Reorder and return
1898 [
1899 output0, output3, output4, output7, output8, output1, output2, output5, output6,
1900 output9,
1901 ]
1902 }
1903 }
1904
1905 // _ ___ __ _ _ _ _ _
1906 // / |/ _ \ / /_ | || | | |__ (_) |_
1907 // | | | | | _____ | '_ \| || |_| '_ \| | __|
1908 // | | |_| | |_____| | (_) |__ _| |_) | | |_
1909 // |_|\___/ \___/ |_| |_.__/|_|\__|
1910 //
1911
1912 pub struct WasmSimdF64Butterfly10<T> {
1913 direction: FftDirection,
1914 _phantom: std::marker::PhantomData<T>,
1915 bf2: WasmSimdF64Butterfly2<T>,
1916 bf5: WasmSimdF64Butterfly5<T>,
1917 }
1918
1919 boilerplate_fft_wasm_simd_f64_butterfly!(
1920 WasmSimdF64Butterfly10,
1921 10,
1922 |this: &WasmSimdF64Butterfly10<_>| this.direction
1923 );
1924 boilerplate_fft_wasm_simd_common_butterfly!(
1925 WasmSimdF64Butterfly10,
1926 10,
1927 |this: &WasmSimdF64Butterfly10<_>| this.direction
1928 );
1929 impl<T: FftNum> WasmSimdF64Butterfly10<T> {
1930 #[inline(always)]
1931 pub fn new(direction: FftDirection) -> Self {
1932 assert_f64::<T>();
1933 let bf2 = WasmSimdF64Butterfly2::new(direction);
1934 let bf5 = WasmSimdF64Butterfly5::new(direction);
1935 Self {
1936 direction,
1937 _phantom: std::marker::PhantomData,
1938 bf2,
1939 bf5,
1940 }
1941 }
1942
1943 #[inline(always)]
1944 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
1945 let values = read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
1946
1947 let out = self.perform_fft_direct(values);
1948
1949 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
1950 }
1951
1952 #[inline(always)]
1953 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 10]) -> [v128; 10] {
1954 // Algorithm: 5x2 good-thomas
1955
1956 // Size-5 FFTs down the columns of our reordered array
1957 let mid0 = self
1958 .bf5
1959 .perform_fft_direct(values[0], values[2], values[4], values[6], values[8]);
1960 let mid1 = self
1961 .bf5
1962 .perform_fft_direct(values[5], values[7], values[9], values[1], values[3]);
1963
1964 // Since this is good-thomas algorithm, we don't need twiddle factors
1965
1966 // Transpose the data and do size-2 FFTs down the columns
1967 let [output0, output1] = self.bf2.perform_fft_direct(mid0[0], mid1[0]);
1968 let [output2, output3] = self.bf2.perform_fft_direct(mid0[1], mid1[1]);
1969 let [output4, output5] = self.bf2.perform_fft_direct(mid0[2], mid1[2]);
1970 let [output6, output7] = self.bf2.perform_fft_direct(mid0[3], mid1[3]);
1971 let [output8, output9] = self.bf2.perform_fft_direct(mid0[4], mid1[4]);
1972
1973 // Reorder and return
1974 [
1975 output0, output3, output4, output7, output8, output1, output2, output5, output6,
1976 output9,
1977 ]
1978 }
1979 }
1980
1981 // _ ____ _________ _ _ _
1982 // / |___ \ |___ /___ \| |__ (_) |_
1983 // | | __) | _____ |_ \ __) | '_ \| | __|
1984 // | |/ __/ |_____| ___) / __/| |_) | | |_
1985 // |_|_____| |____/_____|_.__/|_|\__|
1986 //
1987
1988 pub struct WasmSimdF32Butterfly12<T> {
1989 direction: FftDirection,
1990 _phantom: std::marker::PhantomData<T>,
1991 bf3: WasmSimdF32Butterfly3<T>,
1992 bf4: WasmSimdF32Butterfly4<T>,
1993 }
1994
1995 boilerplate_fft_wasm_simd_f32_butterfly!(
1996 WasmSimdF32Butterfly12,
1997 12,
1998 |this: &WasmSimdF32Butterfly12<_>| this.direction
1999 );
2000 boilerplate_fft_wasm_simd_common_butterfly!(
2001 WasmSimdF32Butterfly12,
2002 12,
2003 |this: &WasmSimdF32Butterfly12<_>| this.direction
2004 );
2005 impl<T: FftNum> WasmSimdF32Butterfly12<T> {
2006 #[inline(always)]
2007 pub fn new(direction: FftDirection) -> Self {
2008 assert_f32::<T>();
2009 let bf3 = WasmSimdF32Butterfly3::new(direction);
2010 let bf4 = WasmSimdF32Butterfly4::new(direction);
2011 Self {
2012 direction,
2013 _phantom: std::marker::PhantomData,
2014 bf3,
2015 bf4,
2016 }
2017 }
2018
2019 #[inline(always)]
2020 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
2021 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10 });
2022
2023 let out = self.perform_fft_direct(input_packed);
2024
2025 write_complex_to_array_strided!(out, buffer, 2, {0,1,2,3,4,5});
2026 }
2027
2028 #[inline(always)]
2029 pub(crate) unsafe fn perform_parallel_fft_contiguous(
2030 &self,
2031 mut buffer: impl WasmSimdArrayMut<f32>,
2032 ) {
2033 let input_packed =
2034 read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22});
2035
2036 let values = interleave_complex_f32!(input_packed, 6, {0, 1, 2, 3, 4, 5});
2037
2038 let out = self.perform_parallel_fft_direct(values);
2039
2040 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4, 6, 8, 10});
2041
2042 write_complex_to_array_strided!(out_sorted, buffer, 2, {0,1,2,3,4,5,6,7,8,9, 10, 11});
2043 }
2044
2045 #[inline(always)]
2046 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 6]) -> [v128; 6] {
2047 // Algorithm: 4x3 good-thomas
2048
2049 // Reorder and pack
2050 let packed03 = extract_lo_hi_f32(values[0], values[1]);
2051 let packed47 = extract_lo_hi_f32(values[2], values[3]);
2052 let packed69 = extract_lo_hi_f32(values[3], values[4]);
2053 let packed101 = extract_lo_hi_f32(values[5], values[0]);
2054 let packed811 = extract_lo_hi_f32(values[4], values[5]);
2055 let packed25 = extract_lo_hi_f32(values[1], values[2]);
2056
2057 // Size-4 FFTs down the columns of our reordered array
2058 let mid0 = self.bf4.perform_fft_direct(packed03, packed69);
2059 let mid1 = self.bf4.perform_fft_direct(packed47, packed101);
2060 let mid2 = self.bf4.perform_fft_direct(packed811, packed25);
2061
2062 // Since this is good-thomas algorithm, we don't need twiddle factors
2063
2064 // Transpose the data and do size-3 FFTs down the columns
2065 let [temp03, temp14, temp25] = self
2066 .bf3
2067 .perform_parallel_fft_direct(mid0[0], mid1[0], mid2[0]);
2068 let [temp69, temp710, temp811] = self
2069 .bf3
2070 .perform_parallel_fft_direct(mid0[1], mid1[1], mid2[1]);
2071
2072 // Reorder and return
2073 [
2074 extract_lo_hi_f32(temp03, temp14),
2075 extract_lo_hi_f32(temp811, temp69),
2076 extract_lo_hi_f32(temp14, temp25),
2077 extract_lo_hi_f32(temp69, temp710),
2078 extract_lo_hi_f32(temp25, temp03),
2079 extract_lo_hi_f32(temp710, temp811),
2080 ]
2081 }
2082
2083 #[inline(always)]
2084 pub(crate) unsafe fn perform_parallel_fft_direct(&self, values: [v128; 12]) -> [v128; 12] {
2085 // Algorithm: 4x3 good-thomas
2086
2087 // Size-4 FFTs down the columns of our reordered array
2088 let mid0 = self
2089 .bf4
2090 .perform_parallel_fft_direct(values[0], values[3], values[6], values[9]);
2091 let mid1 = self
2092 .bf4
2093 .perform_parallel_fft_direct(values[4], values[7], values[10], values[1]);
2094 let mid2 = self
2095 .bf4
2096 .perform_parallel_fft_direct(values[8], values[11], values[2], values[5]);
2097
2098 // Since this is good-thomas algorithm, we don't need twiddle factors
2099
2100 // Transpose the data and do size-3 FFTs down the columns
2101 let [output0, output1, output2] = self
2102 .bf3
2103 .perform_parallel_fft_direct(mid0[0], mid1[0], mid2[0]);
2104 let [output3, output4, output5] = self
2105 .bf3
2106 .perform_parallel_fft_direct(mid0[1], mid1[1], mid2[1]);
2107 let [output6, output7, output8] = self
2108 .bf3
2109 .perform_parallel_fft_direct(mid0[2], mid1[2], mid2[2]);
2110 let [output9, output10, output11] = self
2111 .bf3
2112 .perform_parallel_fft_direct(mid0[3], mid1[3], mid2[3]);
2113
2114 // Reorder and return
2115 [
2116 output0, output4, output8, output9, output1, output5, output6, output10, output2,
2117 output3, output7, output11,
2118 ]
2119 }
2120 }
2121
2122 // _ ____ __ _ _ _ _ _
2123 // / |___ \ / /_ | || | | |__ (_) |_
2124 // | | __) | _____ | '_ \| || |_| '_ \| | __|
2125 // | |/ __/ |_____| | (_) |__ _| |_) | | |_
2126 // |_|_____| \___/ |_| |_.__/|_|\__|
2127 //
2128
2129 pub struct WasmSimdF64Butterfly12<T> {
2130 direction: FftDirection,
2131 _phantom: std::marker::PhantomData<T>,
2132 bf3: WasmSimdF64Butterfly3<T>,
2133 bf4: WasmSimdF64Butterfly4<T>,
2134 }
2135
2136 boilerplate_fft_wasm_simd_f64_butterfly!(
2137 WasmSimdF64Butterfly12,
2138 12,
2139 |this: &WasmSimdF64Butterfly12<_>| this.direction
2140 );
2141 boilerplate_fft_wasm_simd_common_butterfly!(
2142 WasmSimdF64Butterfly12,
2143 12,
2144 |this: &WasmSimdF64Butterfly12<_>| this.direction
2145 );
2146 impl<T: FftNum> WasmSimdF64Butterfly12<T> {
2147 #[inline(always)]
2148 pub fn new(direction: FftDirection) -> Self {
2149 assert_f64::<T>();
2150 let bf3 = WasmSimdF64Butterfly3::new(direction);
2151 let bf4 = WasmSimdF64Butterfly4::new(direction);
2152 Self {
2153 direction,
2154 _phantom: std::marker::PhantomData,
2155 bf3,
2156 bf4,
2157 }
2158 }
2159
2160 #[inline(always)]
2161 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
2162 let values = read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11});
2163
2164 let out = self.perform_fft_direct(values);
2165
2166 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11});
2167 }
2168
2169 #[inline(always)]
2170 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 12]) -> [v128; 12] {
2171 // Algorithm: 4x3 good-thomas
2172
2173 // Size-4 FFTs down the columns of our reordered array
2174 let mid0 = self
2175 .bf4
2176 .perform_fft_direct(values[0], values[3], values[6], values[9]);
2177 let mid1 = self
2178 .bf4
2179 .perform_fft_direct(values[4], values[7], values[10], values[1]);
2180 let mid2 = self
2181 .bf4
2182 .perform_fft_direct(values[8], values[11], values[2], values[5]);
2183
2184 // Since this is good-thomas algorithm, we don't need twiddle factors
2185
2186 // Transpose the data and do size-3 FFTs down the columns
2187 let [output0, output1, output2] = self.bf3.perform_fft_direct(mid0[0], mid1[0], mid2[0]);
2188 let [output3, output4, output5] = self.bf3.perform_fft_direct(mid0[1], mid1[1], mid2[1]);
2189 let [output6, output7, output8] = self.bf3.perform_fft_direct(mid0[2], mid1[2], mid2[2]);
2190 let [output9, output10, output11] = self.bf3.perform_fft_direct(mid0[3], mid1[3], mid2[3]);
2191
2192 [
2193 output0, output4, output8, output9, output1, output5, output6, output10, output2,
2194 output3, output7, output11,
2195 ]
2196 }
2197 }
2198
2199 // _ ____ _________ _ _ _
2200 // / | ___| |___ /___ \| |__ (_) |_
2201 // | |___ \ _____ |_ \ __) | '_ \| | __|
2202 // | |___) | |_____| ___) / __/| |_) | | |_
2203 // |_|____/ |____/_____|_.__/|_|\__|
2204 //
2205 pub struct WasmSimdF32Butterfly15<T> {
2206 direction: FftDirection,
2207 _phantom: std::marker::PhantomData<T>,
2208 bf3: WasmSimdF32Butterfly3<T>,
2209 bf5: WasmSimdF32Butterfly5<T>,
2210 }
2211
2212 boilerplate_fft_wasm_simd_f32_butterfly!(
2213 WasmSimdF32Butterfly15,
2214 15,
2215 |this: &WasmSimdF32Butterfly15<_>| this.direction
2216 );
2217 boilerplate_fft_wasm_simd_common_butterfly!(
2218 WasmSimdF32Butterfly15,
2219 15,
2220 |this: &WasmSimdF32Butterfly15<_>| this.direction
2221 );
2222 impl<T: FftNum> WasmSimdF32Butterfly15<T> {
2223 #[inline(always)]
2224 pub fn new(direction: FftDirection) -> Self {
2225 assert_f32::<T>();
2226 let bf3 = WasmSimdF32Butterfly3::new(direction);
2227 let bf5 = WasmSimdF32Butterfly5::new(direction);
2228 Self {
2229 direction,
2230 _phantom: std::marker::PhantomData,
2231 bf3,
2232 bf5,
2233 }
2234 }
2235
2236 #[inline(always)]
2237 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
2238 // A single WasmSimd 15-point will need a lot of shuffling, let's just reuse the dual one
2239 let values = read_partial1_complex_to_array!(buffer, {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14});
2240
2241 let out = self.perform_parallel_fft_direct(values);
2242
2243 for n in 0..15 {
2244 buffer.store_partial_lo_complex(out[n], n);
2245 }
2246 }
2247
2248 #[inline(always)]
2249 pub(crate) unsafe fn perform_parallel_fft_contiguous(
2250 &self,
2251 mut buffer: impl WasmSimdArrayMut<f32>,
2252 ) {
2253 let input_packed =
2254 read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28});
2255
2256 let values = [
2257 extract_lo_hi_f32(input_packed[0], input_packed[7]),
2258 extract_hi_lo_f32(input_packed[0], input_packed[8]),
2259 extract_lo_hi_f32(input_packed[1], input_packed[8]),
2260 extract_hi_lo_f32(input_packed[1], input_packed[9]),
2261 extract_lo_hi_f32(input_packed[2], input_packed[9]),
2262 extract_hi_lo_f32(input_packed[2], input_packed[10]),
2263 extract_lo_hi_f32(input_packed[3], input_packed[10]),
2264 extract_hi_lo_f32(input_packed[3], input_packed[11]),
2265 extract_lo_hi_f32(input_packed[4], input_packed[11]),
2266 extract_hi_lo_f32(input_packed[4], input_packed[12]),
2267 extract_lo_hi_f32(input_packed[5], input_packed[12]),
2268 extract_hi_lo_f32(input_packed[5], input_packed[13]),
2269 extract_lo_hi_f32(input_packed[6], input_packed[13]),
2270 extract_hi_lo_f32(input_packed[6], input_packed[14]),
2271 extract_lo_hi_f32(input_packed[7], input_packed[14]),
2272 ];
2273
2274 let out = self.perform_parallel_fft_direct(values);
2275
2276 let out_packed = [
2277 extract_lo_lo_f32(out[0], out[1]),
2278 extract_lo_lo_f32(out[2], out[3]),
2279 extract_lo_lo_f32(out[4], out[5]),
2280 extract_lo_lo_f32(out[6], out[7]),
2281 extract_lo_lo_f32(out[8], out[9]),
2282 extract_lo_lo_f32(out[10], out[11]),
2283 extract_lo_lo_f32(out[12], out[13]),
2284 extract_lo_hi_f32(out[14], out[0]),
2285 extract_hi_hi_f32(out[1], out[2]),
2286 extract_hi_hi_f32(out[3], out[4]),
2287 extract_hi_hi_f32(out[5], out[6]),
2288 extract_hi_hi_f32(out[7], out[8]),
2289 extract_hi_hi_f32(out[9], out[10]),
2290 extract_hi_hi_f32(out[11], out[12]),
2291 extract_hi_hi_f32(out[13], out[14]),
2292 ];
2293
2294 write_complex_to_array_strided!(out_packed, buffer, 2, {0,1,2,3,4,5,6,7,8,9, 10, 11, 12, 13, 14});
2295 }
2296
2297 #[inline(always)]
2298 pub(crate) unsafe fn perform_parallel_fft_direct(&self, values: [v128; 15]) -> [v128; 15] {
2299 // Algorithm: 5x3 good-thomas
2300
2301 // Size-5 FFTs down the columns of our reordered array
2302 let mid0 = self
2303 .bf5
2304 .perform_parallel_fft_direct(values[0], values[3], values[6], values[9], values[12]);
2305 let mid1 = self
2306 .bf5
2307 .perform_parallel_fft_direct(values[5], values[8], values[11], values[14], values[2]);
2308 let mid2 = self
2309 .bf5
2310 .perform_parallel_fft_direct(values[10], values[13], values[1], values[4], values[7]);
2311
2312 // Since this is good-thomas algorithm, we don't need twiddle factors
2313
2314 // Transpose the data and do size-3 FFTs down the columns
2315 let [output0, output1, output2] = self
2316 .bf3
2317 .perform_parallel_fft_direct(mid0[0], mid1[0], mid2[0]);
2318 let [output3, output4, output5] = self
2319 .bf3
2320 .perform_parallel_fft_direct(mid0[1], mid1[1], mid2[1]);
2321 let [output6, output7, output8] = self
2322 .bf3
2323 .perform_parallel_fft_direct(mid0[2], mid1[2], mid2[2]);
2324 let [output9, output10, output11] = self
2325 .bf3
2326 .perform_parallel_fft_direct(mid0[3], mid1[3], mid2[3]);
2327 let [output12, output13, output14] = self
2328 .bf3
2329 .perform_parallel_fft_direct(mid0[4], mid1[4], mid2[4]);
2330
2331 [
2332 output0, output4, output8, output9, output13, output2, output3, output7, output11,
2333 output12, output1, output5, output6, output10, output14,
2334 ]
2335 }
2336 }
2337
2338 // _ ____ __ _ _ _ _ _
2339 // / | ___| / /_ | || | | |__ (_) |_
2340 // | |___ \ _____ | '_ \| || |_| '_ \| | __|
2341 // | |___) | |_____| | (_) |__ _| |_) | | |_
2342 // |_|____/ \___/ |_| |_.__/|_|\__|
2343 //
2344
2345 pub struct WasmSimdF64Butterfly15<T> {
2346 direction: FftDirection,
2347 _phantom: std::marker::PhantomData<T>,
2348 bf3: WasmSimdF64Butterfly3<T>,
2349 bf5: WasmSimdF64Butterfly5<T>,
2350 }
2351
2352 boilerplate_fft_wasm_simd_f64_butterfly!(
2353 WasmSimdF64Butterfly15,
2354 15,
2355 |this: &WasmSimdF64Butterfly15<_>| this.direction
2356 );
2357 boilerplate_fft_wasm_simd_common_butterfly!(
2358 WasmSimdF64Butterfly15,
2359 15,
2360 |this: &WasmSimdF64Butterfly15<_>| this.direction
2361 );
2362 impl<T: FftNum> WasmSimdF64Butterfly15<T> {
2363 #[inline(always)]
2364 pub fn new(direction: FftDirection) -> Self {
2365 assert_f64::<T>();
2366 let bf3 = WasmSimdF64Butterfly3::new(direction);
2367 let bf5 = WasmSimdF64Butterfly5::new(direction);
2368 Self {
2369 direction,
2370 _phantom: std::marker::PhantomData,
2371 bf3,
2372 bf5,
2373 }
2374 }
2375
2376 #[inline(always)]
2377 pub(crate) unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
2378 let values =
2379 read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14});
2380
2381 let out = self.perform_fft_direct(values);
2382
2383 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14});
2384 }
2385
2386 #[inline(always)]
2387 pub(crate) unsafe fn perform_fft_direct(&self, values: [v128; 15]) -> [v128; 15] {
2388 // Algorithm: 5x3 good-thomas
2389
2390 // Size-5 FFTs down the columns of our reordered array
2391 let mid0 = self
2392 .bf5
2393 .perform_fft_direct(values[0], values[3], values[6], values[9], values[12]);
2394 let mid1 = self
2395 .bf5
2396 .perform_fft_direct(values[5], values[8], values[11], values[14], values[2]);
2397 let mid2 = self
2398 .bf5
2399 .perform_fft_direct(values[10], values[13], values[1], values[4], values[7]);
2400
2401 // Since this is good-thomas algorithm, we don't need twiddle factors
2402
2403 // Transpose the data and do size-3 FFTs down the columns
2404 let [output0, output1, output2] = self.bf3.perform_fft_direct(mid0[0], mid1[0], mid2[0]);
2405 let [output3, output4, output5] = self.bf3.perform_fft_direct(mid0[1], mid1[1], mid2[1]);
2406 let [output6, output7, output8] = self.bf3.perform_fft_direct(mid0[2], mid1[2], mid2[2]);
2407 let [output9, output10, output11] = self.bf3.perform_fft_direct(mid0[3], mid1[3], mid2[3]);
2408 let [output12, output13, output14] = self.bf3.perform_fft_direct(mid0[4], mid1[4], mid2[4]);
2409
2410 [
2411 output0, output4, output8, output9, output13, output2, output3, output7, output11,
2412 output12, output1, output5, output6, output10, output14,
2413 ]
2414 }
2415 }
2416
2417 // _ __ _________ _ _ _
2418 // / |/ /_ |___ /___ \| |__ (_) |_
2419 // | | '_ \ _____ |_ \ __) | '_ \| | __|
2420 // | | (_) | |_____| ___) / __/| |_) | | |_
2421 // |_|\___/ |____/_____|_.__/|_|\__|
2422 //
2423
2424 pub struct WasmSimdF32Butterfly16<T> {
2425 direction: FftDirection,
2426 bf4: WasmSimdF32Butterfly4<T>,
2427 bf8: WasmSimdF32Butterfly8<T>,
2428 rotate90: Rotate90F32,
2429 twiddle01: v128,
2430 twiddle23: v128,
2431 twiddle01conj: v128,
2432 twiddle23conj: v128,
2433 twiddle1: v128,
2434 twiddle2: v128,
2435 twiddle3: v128,
2436 twiddle1c: v128,
2437 twiddle2c: v128,
2438 twiddle3c: v128,
2439 }
2440
2441 boilerplate_fft_wasm_simd_f32_butterfly!(
2442 WasmSimdF32Butterfly16,
2443 16,
2444 |this: &WasmSimdF32Butterfly16<_>| this.direction
2445 );
2446 boilerplate_fft_wasm_simd_common_butterfly!(
2447 WasmSimdF32Butterfly16,
2448 16,
2449 |this: &WasmSimdF32Butterfly16<_>| this.direction
2450 );
2451 impl<T: FftNum> WasmSimdF32Butterfly16<T> {
2452 #[inline(always)]
2453 pub fn new(direction: FftDirection) -> Self {
2454 assert_f32::<T>();
2455 let bf8 = WasmSimdF32Butterfly8::new(direction);
2456 let bf4 = WasmSimdF32Butterfly4::new(direction);
2457 let rotate90 = if direction == FftDirection::Inverse {
2458 Rotate90F32::new(true)
2459 } else {
2460 Rotate90F32::new(false)
2461 };
2462 let tw1: Complex<f32> = twiddles::compute_twiddle(1, 16, direction);
2463 let tw2: Complex<f32> = twiddles::compute_twiddle(2, 16, direction);
2464 let tw3: Complex<f32> = twiddles::compute_twiddle(3, 16, direction);
2465 let twiddle01 = f32x4(1.0, 0.0, tw1.re, tw1.im);
2466 let twiddle23 = f32x4(tw2.re, tw2.im, tw3.re, tw3.im);
2467 let twiddle01conj = f32x4(1.0, 0.0, tw1.re, -tw1.im);
2468 let twiddle23conj = f32x4(tw2.re, -tw2.im, tw3.re, -tw3.im);
2469 let twiddle1 = f32x4(tw1.re, tw1.im, tw1.re, tw1.im);
2470 let twiddle2 = f32x4(tw2.re, tw2.im, tw2.re, tw2.im);
2471 let twiddle3 = f32x4(tw3.re, tw3.im, tw3.re, tw3.im);
2472 let twiddle1c = f32x4(tw1.re, -tw1.im, tw1.re, -tw1.im);
2473 let twiddle2c = f32x4(tw2.re, -tw2.im, tw2.re, -tw2.im);
2474 let twiddle3c = f32x4(tw3.re, -tw3.im, tw3.re, -tw3.im);
2475 Self {
2476 direction,
2477 bf4,
2478 bf8,
2479 rotate90,
2480 twiddle01,
2481 twiddle23,
2482 twiddle01conj,
2483 twiddle23conj,
2484 twiddle1,
2485 twiddle2,
2486 twiddle3,
2487 twiddle1c,
2488 twiddle2c,
2489 twiddle3c,
2490 }
2491 }
2492
2493 #[inline(always)]
2494 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
2495 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14 });
2496
2497 let out = self.perform_fft_direct(input_packed);
2498
2499 write_complex_to_array_strided!(out, buffer, 2, {0,1,2,3,4,5,6,7});
2500 }
2501
2502 #[inline(always)]
2503 pub(crate) unsafe fn perform_parallel_fft_contiguous(
2504 &self,
2505 mut buffer: impl WasmSimdArrayMut<f32>,
2506 ) {
2507 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30});
2508
2509 let values = interleave_complex_f32!(input_packed, 8, {0, 1, 2, 3 ,4 ,5 ,6 ,7});
2510
2511 let out = self.perform_parallel_fft_direct(values);
2512
2513 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4, 6, 8, 10, 12, 14});
2514
2515 write_complex_to_array_strided!(out_sorted, buffer, 2, {0,1,2,3,4,5,6,7,8,9, 10, 11,12,13,14, 15});
2516 }
2517
2518 #[inline(always)]
2519 unsafe fn perform_fft_direct(&self, input: [v128; 8]) -> [v128; 8] {
2520 // we're going to hardcode a step of split radix
2521 // step 1: copy and reorder the input into the scratch
2522 let in0002 = extract_lo_lo_f32(input[0], input[1]);
2523 let in0406 = extract_lo_lo_f32(input[2], input[3]);
2524 let in0810 = extract_lo_lo_f32(input[4], input[5]);
2525 let in1214 = extract_lo_lo_f32(input[6], input[7]);
2526
2527 let in0105 = extract_hi_hi_f32(input[0], input[2]);
2528 let in0913 = extract_hi_hi_f32(input[4], input[6]);
2529 let in1503 = extract_hi_hi_f32(input[7], input[1]);
2530 let in0711 = extract_hi_hi_f32(input[3], input[5]);
2531
2532 let in_evens = [in0002, in0406, in0810, in1214];
2533
2534 // step 2: column FFTs
2535 let evens = self.bf8.perform_fft_direct(in_evens);
2536 let mut odds1 = self.bf4.perform_fft_direct(in0105, in0913);
2537 let mut odds3 = self.bf4.perform_fft_direct(in1503, in0711);
2538
2539 // step 3: apply twiddle factors
2540 odds1[0] = mul_complex_f32(odds1[0], self.twiddle01);
2541 odds3[0] = mul_complex_f32(odds3[0], self.twiddle01conj);
2542
2543 odds1[1] = mul_complex_f32(odds1[1], self.twiddle23);
2544 odds3[1] = mul_complex_f32(odds3[1], self.twiddle23conj);
2545
2546 // step 4: cross FFTs
2547 let mut temp0 = parallel_fft2_interleaved_f32(odds1[0], odds3[0]);
2548 let mut temp1 = parallel_fft2_interleaved_f32(odds1[1], odds3[1]);
2549
2550 // apply the butterfly 4 twiddle factor, which is just a rotation
2551 temp0[1] = self.rotate90.rotate_both(temp0[1]);
2552 temp1[1] = self.rotate90.rotate_both(temp1[1]);
2553
2554 //step 5: copy/add/subtract data back to buffer
2555 [
2556 f32x4_add(evens[0], temp0[0]),
2557 f32x4_add(evens[1], temp1[0]),
2558 f32x4_add(evens[2], temp0[1]),
2559 f32x4_add(evens[3], temp1[1]),
2560 f32x4_sub(evens[0], temp0[0]),
2561 f32x4_sub(evens[1], temp1[0]),
2562 f32x4_sub(evens[2], temp0[1]),
2563 f32x4_sub(evens[3], temp1[1]),
2564 ]
2565 }
2566
2567 #[inline(always)]
2568 unsafe fn perform_parallel_fft_direct(&self, input: [v128; 16]) -> [v128; 16] {
2569 // we're going to hardcode a step of split radix
2570 // step 1: copy and reorder the input into the scratch
2571 // and
2572 // step 2: column FFTs
2573 let evens = self.bf8.perform_parallel_fft_direct([
2574 input[0], input[2], input[4], input[6], input[8], input[10], input[12], input[14],
2575 ]);
2576 let mut odds1 = self
2577 .bf4
2578 .perform_parallel_fft_direct(input[1], input[5], input[9], input[13]);
2579 let mut odds3 = self
2580 .bf4
2581 .perform_parallel_fft_direct(input[15], input[3], input[7], input[11]);
2582
2583 // step 3: apply twiddle factors
2584 odds1[1] = mul_complex_f32(odds1[1], self.twiddle1);
2585 odds3[1] = mul_complex_f32(odds3[1], self.twiddle1c);
2586
2587 odds1[2] = mul_complex_f32(odds1[2], self.twiddle2);
2588 odds3[2] = mul_complex_f32(odds3[2], self.twiddle2c);
2589
2590 odds1[3] = mul_complex_f32(odds1[3], self.twiddle3);
2591 odds3[3] = mul_complex_f32(odds3[3], self.twiddle3c);
2592
2593 // step 4: cross FFTs
2594 let mut temp0 = parallel_fft2_interleaved_f32(odds1[0], odds3[0]);
2595 let mut temp1 = parallel_fft2_interleaved_f32(odds1[1], odds3[1]);
2596 let mut temp2 = parallel_fft2_interleaved_f32(odds1[2], odds3[2]);
2597 let mut temp3 = parallel_fft2_interleaved_f32(odds1[3], odds3[3]);
2598
2599 // apply the butterfly 4 twiddle factor, which is just a rotation
2600 temp0[1] = self.rotate90.rotate_both(temp0[1]);
2601 temp1[1] = self.rotate90.rotate_both(temp1[1]);
2602 temp2[1] = self.rotate90.rotate_both(temp2[1]);
2603 temp3[1] = self.rotate90.rotate_both(temp3[1]);
2604
2605 //step 5: copy/add/subtract data back to buffer
2606 [
2607 f32x4_add(evens[0], temp0[0]),
2608 f32x4_add(evens[1], temp1[0]),
2609 f32x4_add(evens[2], temp2[0]),
2610 f32x4_add(evens[3], temp3[0]),
2611 f32x4_add(evens[4], temp0[1]),
2612 f32x4_add(evens[5], temp1[1]),
2613 f32x4_add(evens[6], temp2[1]),
2614 f32x4_add(evens[7], temp3[1]),
2615 f32x4_sub(evens[0], temp0[0]),
2616 f32x4_sub(evens[1], temp1[0]),
2617 f32x4_sub(evens[2], temp2[0]),
2618 f32x4_sub(evens[3], temp3[0]),
2619 f32x4_sub(evens[4], temp0[1]),
2620 f32x4_sub(evens[5], temp1[1]),
2621 f32x4_sub(evens[6], temp2[1]),
2622 f32x4_sub(evens[7], temp3[1]),
2623 ]
2624 }
2625 }
2626
2627 // _ __ __ _ _ _ _ _
2628 // / |/ /_ / /_ | || | | |__ (_) |_
2629 // | | '_ \ _____ | '_ \| || |_| '_ \| | __|
2630 // | | (_) | |_____| | (_) |__ _| |_) | | |_
2631 // |_|\___/ \___/ |_| |_.__/|_|\__|
2632 //
2633
2634 pub struct WasmSimdF64Butterfly16<T> {
2635 direction: FftDirection,
2636 bf4: WasmSimdF64Butterfly4<T>,
2637 bf8: WasmSimdF64Butterfly8<T>,
2638 rotate90: Rotate90F64,
2639 twiddle1: v128,
2640 twiddle2: v128,
2641 twiddle3: v128,
2642 twiddle1c: v128,
2643 twiddle2c: v128,
2644 twiddle3c: v128,
2645 }
2646
2647 boilerplate_fft_wasm_simd_f64_butterfly!(
2648 WasmSimdF64Butterfly16,
2649 16,
2650 |this: &WasmSimdF64Butterfly16<_>| this.direction
2651 );
2652 boilerplate_fft_wasm_simd_common_butterfly!(
2653 WasmSimdF64Butterfly16,
2654 16,
2655 |this: &WasmSimdF64Butterfly16<_>| this.direction
2656 );
2657 impl<T: FftNum> WasmSimdF64Butterfly16<T> {
2658 #[inline(always)]
2659 pub fn new(direction: FftDirection) -> Self {
2660 assert_f64::<T>();
2661 let bf8 = WasmSimdF64Butterfly8::new(direction);
2662 let bf4 = WasmSimdF64Butterfly4::new(direction);
2663 let rotate90 = if direction == FftDirection::Inverse {
2664 Rotate90F64::new(true)
2665 } else {
2666 Rotate90F64::new(false)
2667 };
2668 let twiddle1 = unsafe {
2669 v128_load(
2670 &twiddles::compute_twiddle::<f64>(1, 16, direction) as *const _ as *const v128,
2671 )
2672 };
2673 let twiddle2 = unsafe {
2674 v128_load(
2675 &twiddles::compute_twiddle::<f64>(2, 16, direction) as *const _ as *const v128,
2676 )
2677 };
2678 let twiddle3 = unsafe {
2679 v128_load(
2680 &twiddles::compute_twiddle::<f64>(3, 16, direction) as *const _ as *const v128,
2681 )
2682 };
2683 let twiddle1c = unsafe {
2684 v128_load(
2685 &twiddles::compute_twiddle::<f64>(1, 16, direction).conj() as *const _
2686 as *const v128,
2687 )
2688 };
2689 let twiddle2c = unsafe {
2690 v128_load(
2691 &twiddles::compute_twiddle::<f64>(2, 16, direction).conj() as *const _
2692 as *const v128,
2693 )
2694 };
2695 let twiddle3c = unsafe {
2696 v128_load(
2697 &twiddles::compute_twiddle::<f64>(3, 16, direction).conj() as *const _
2698 as *const v128,
2699 )
2700 };
2701
2702 Self {
2703 direction,
2704 bf4,
2705 bf8,
2706 rotate90,
2707 twiddle1,
2708 twiddle2,
2709 twiddle3,
2710 twiddle1c,
2711 twiddle2c,
2712 twiddle3c,
2713 }
2714 }
2715
2716 #[inline(always)]
2717 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
2718 let values =
2719 read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
2720
2721 let out = self.perform_fft_direct(values);
2722
2723 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
2724 }
2725
2726 #[inline(always)]
2727 unsafe fn perform_fft_direct(&self, input: [v128; 16]) -> [v128; 16] {
2728 // we're going to hardcode a step of split radix
2729
2730 // step 1: copy and reorder the input into the scratch
2731 // and
2732 // step 2: column FFTs
2733 let evens = self.bf8.perform_fft_direct([
2734 input[0], input[2], input[4], input[6], input[8], input[10], input[12], input[14],
2735 ]);
2736 let mut odds1 = self
2737 .bf4
2738 .perform_fft_direct(input[1], input[5], input[9], input[13]);
2739 let mut odds3 = self
2740 .bf4
2741 .perform_fft_direct(input[15], input[3], input[7], input[11]);
2742
2743 // step 3: apply twiddle factors
2744 odds1[1] = mul_complex_f64(odds1[1], self.twiddle1);
2745 odds3[1] = mul_complex_f64(odds3[1], self.twiddle1c);
2746
2747 odds1[2] = mul_complex_f64(odds1[2], self.twiddle2);
2748 odds3[2] = mul_complex_f64(odds3[2], self.twiddle2c);
2749
2750 odds1[3] = mul_complex_f64(odds1[3], self.twiddle3);
2751 odds3[3] = mul_complex_f64(odds3[3], self.twiddle3c);
2752
2753 // step 4: cross FFTs
2754 let mut temp0 = solo_fft2_f64(odds1[0], odds3[0]);
2755 let mut temp1 = solo_fft2_f64(odds1[1], odds3[1]);
2756 let mut temp2 = solo_fft2_f64(odds1[2], odds3[2]);
2757 let mut temp3 = solo_fft2_f64(odds1[3], odds3[3]);
2758
2759 // apply the butterfly 4 twiddle factor, which is just a rotation
2760 temp0[1] = self.rotate90.rotate(temp0[1]);
2761 temp1[1] = self.rotate90.rotate(temp1[1]);
2762 temp2[1] = self.rotate90.rotate(temp2[1]);
2763 temp3[1] = self.rotate90.rotate(temp3[1]);
2764
2765 //step 5: copy/add/subtract data back to buffer
2766 [
2767 f64x2_add(evens[0], temp0[0]),
2768 f64x2_add(evens[1], temp1[0]),
2769 f64x2_add(evens[2], temp2[0]),
2770 f64x2_add(evens[3], temp3[0]),
2771 f64x2_add(evens[4], temp0[1]),
2772 f64x2_add(evens[5], temp1[1]),
2773 f64x2_add(evens[6], temp2[1]),
2774 f64x2_add(evens[7], temp3[1]),
2775 f64x2_sub(evens[0], temp0[0]),
2776 f64x2_sub(evens[1], temp1[0]),
2777 f64x2_sub(evens[2], temp2[0]),
2778 f64x2_sub(evens[3], temp3[0]),
2779 f64x2_sub(evens[4], temp0[1]),
2780 f64x2_sub(evens[5], temp1[1]),
2781 f64x2_sub(evens[6], temp2[1]),
2782 f64x2_sub(evens[7], temp3[1]),
2783 ]
2784 }
2785 }
2786
2787 // _________ _________ _ _ _
2788 // |___ /___ \ |___ /___ \| |__ (_) |_
2789 // |_ \ __) | _____ |_ \ __) | '_ \| | __|
2790 // ___) / __/ |_____| ___) / __/| |_) | | |_
2791 // |____/_____| |____/_____|_.__/|_|\__|
2792 //
2793
2794 pub struct WasmSimdF32Butterfly32<T> {
2795 direction: FftDirection,
2796 bf8: WasmSimdF32Butterfly8<T>,
2797 bf16: WasmSimdF32Butterfly16<T>,
2798 rotate90: Rotate90F32,
2799 twiddle01: v128,
2800 twiddle23: v128,
2801 twiddle45: v128,
2802 twiddle67: v128,
2803 twiddle01conj: v128,
2804 twiddle23conj: v128,
2805 twiddle45conj: v128,
2806 twiddle67conj: v128,
2807 twiddle1: v128,
2808 twiddle2: v128,
2809 twiddle3: v128,
2810 twiddle4: v128,
2811 twiddle5: v128,
2812 twiddle6: v128,
2813 twiddle7: v128,
2814 twiddle1c: v128,
2815 twiddle2c: v128,
2816 twiddle3c: v128,
2817 twiddle4c: v128,
2818 twiddle5c: v128,
2819 twiddle6c: v128,
2820 twiddle7c: v128,
2821 }
2822
2823 boilerplate_fft_wasm_simd_f32_butterfly!(
2824 WasmSimdF32Butterfly32,
2825 32,
2826 |this: &WasmSimdF32Butterfly32<_>| this.direction
2827 );
2828 boilerplate_fft_wasm_simd_common_butterfly!(
2829 WasmSimdF32Butterfly32,
2830 32,
2831 |this: &WasmSimdF32Butterfly32<_>| this.direction
2832 );
2833 impl<T: FftNum> WasmSimdF32Butterfly32<T> {
2834 #[inline(always)]
2835 pub fn new(direction: FftDirection) -> Self {
2836 assert_f32::<T>();
2837 let bf8 = WasmSimdF32Butterfly8::new(direction);
2838 let bf16 = WasmSimdF32Butterfly16::new(direction);
2839 let rotate90 = if direction == FftDirection::Inverse {
2840 Rotate90F32::new(true)
2841 } else {
2842 Rotate90F32::new(false)
2843 };
2844 let tw1: Complex<f32> = twiddles::compute_twiddle(1, 32, direction);
2845 let tw2: Complex<f32> = twiddles::compute_twiddle(2, 32, direction);
2846 let tw3: Complex<f32> = twiddles::compute_twiddle(3, 32, direction);
2847 let tw4: Complex<f32> = twiddles::compute_twiddle(4, 32, direction);
2848 let tw5: Complex<f32> = twiddles::compute_twiddle(5, 32, direction);
2849 let tw6: Complex<f32> = twiddles::compute_twiddle(6, 32, direction);
2850 let tw7: Complex<f32> = twiddles::compute_twiddle(7, 32, direction);
2851 let twiddle01 = f32x4(1.0, 0.0, tw1.re, tw1.im);
2852 let twiddle23 = f32x4(tw2.re, tw2.im, tw3.re, tw3.im);
2853 let twiddle45 = f32x4(tw4.re, tw4.im, tw5.re, tw5.im);
2854 let twiddle67 = f32x4(tw6.re, tw6.im, tw7.re, tw7.im);
2855 let twiddle01conj = f32x4(1.0, 0.0, tw1.re, -tw1.im);
2856 let twiddle23conj = f32x4(tw2.re, -tw2.im, tw3.re, -tw3.im);
2857 let twiddle45conj = f32x4(tw4.re, -tw4.im, tw5.re, -tw5.im);
2858 let twiddle67conj = f32x4(tw6.re, -tw6.im, tw7.re, -tw7.im);
2859 let twiddle1 = f32x4(tw1.re, tw1.im, tw1.re, tw1.im);
2860 let twiddle2 = f32x4(tw2.re, tw2.im, tw2.re, tw2.im);
2861 let twiddle3 = f32x4(tw3.re, tw3.im, tw3.re, tw3.im);
2862 let twiddle4 = f32x4(tw4.re, tw4.im, tw4.re, tw4.im);
2863 let twiddle5 = f32x4(tw5.re, tw5.im, tw5.re, tw5.im);
2864 let twiddle6 = f32x4(tw6.re, tw6.im, tw6.re, tw6.im);
2865 let twiddle7 = f32x4(tw7.re, tw7.im, tw7.re, tw7.im);
2866 let twiddle1c = f32x4(tw1.re, -tw1.im, tw1.re, -tw1.im);
2867 let twiddle2c = f32x4(tw2.re, -tw2.im, tw2.re, -tw2.im);
2868 let twiddle3c = f32x4(tw3.re, -tw3.im, tw3.re, -tw3.im);
2869 let twiddle4c = f32x4(tw4.re, -tw4.im, tw4.re, -tw4.im);
2870 let twiddle5c = f32x4(tw5.re, -tw5.im, tw5.re, -tw5.im);
2871 let twiddle6c = f32x4(tw6.re, -tw6.im, tw6.re, -tw6.im);
2872 let twiddle7c = f32x4(tw7.re, -tw7.im, tw7.re, -tw7.im);
2873 Self {
2874 direction,
2875 bf8,
2876 bf16,
2877 rotate90,
2878 twiddle01,
2879 twiddle23,
2880 twiddle45,
2881 twiddle67,
2882 twiddle01conj,
2883 twiddle23conj,
2884 twiddle45conj,
2885 twiddle67conj,
2886 twiddle1,
2887 twiddle2,
2888 twiddle3,
2889 twiddle4,
2890 twiddle5,
2891 twiddle6,
2892 twiddle7,
2893 twiddle1c,
2894 twiddle2c,
2895 twiddle3c,
2896 twiddle4c,
2897 twiddle5c,
2898 twiddle6c,
2899 twiddle7c,
2900 }
2901 }
2902
2903 #[inline(always)]
2904 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f32>) {
2905 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 });
2906
2907 let out = self.perform_fft_direct(input_packed);
2908
2909 write_complex_to_array_strided!(out, buffer, 2, {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15});
2910 }
2911
2912 #[inline(always)]
2913 pub(crate) unsafe fn perform_parallel_fft_contiguous(
2914 &self,
2915 mut buffer: impl WasmSimdArrayMut<f32>,
2916 ) {
2917 let input_packed = read_complex_to_array!(buffer, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62});
2918
2919 let values = interleave_complex_f32!(input_packed, 16, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
2920
2921 let out = self.perform_parallel_fft_direct(values);
2922
2923 let out_sorted = separate_interleaved_complex_f32!(out, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30});
2924
2925 write_complex_to_array_strided!(out_sorted, buffer, 2, {0,1,2,3,4,5,6,7,8,9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 });
2926 }
2927
2928 #[inline(always)]
2929 unsafe fn perform_fft_direct(&self, input: [v128; 16]) -> [v128; 16] {
2930 // we're going to hardcode a step of split radix
2931
2932 // step 1: copy and reorder the input into the scratch
2933 let in0002 = extract_lo_lo_f32(input[0], input[1]);
2934 let in0406 = extract_lo_lo_f32(input[2], input[3]);
2935 let in0810 = extract_lo_lo_f32(input[4], input[5]);
2936 let in1214 = extract_lo_lo_f32(input[6], input[7]);
2937 let in1618 = extract_lo_lo_f32(input[8], input[9]);
2938 let in2022 = extract_lo_lo_f32(input[10], input[11]);
2939 let in2426 = extract_lo_lo_f32(input[12], input[13]);
2940 let in2830 = extract_lo_lo_f32(input[14], input[15]);
2941
2942 let in0105 = extract_hi_hi_f32(input[0], input[2]);
2943 let in0913 = extract_hi_hi_f32(input[4], input[6]);
2944 let in1721 = extract_hi_hi_f32(input[8], input[10]);
2945 let in2529 = extract_hi_hi_f32(input[12], input[14]);
2946
2947 let in3103 = extract_hi_hi_f32(input[15], input[1]);
2948 let in0711 = extract_hi_hi_f32(input[3], input[5]);
2949 let in1519 = extract_hi_hi_f32(input[7], input[9]);
2950 let in2327 = extract_hi_hi_f32(input[11], input[13]);
2951
2952 let in_evens = [
2953 in0002, in0406, in0810, in1214, in1618, in2022, in2426, in2830,
2954 ];
2955
2956 // step 2: column FFTs
2957 let evens = self.bf16.perform_fft_direct(in_evens);
2958 let mut odds1 = self
2959 .bf8
2960 .perform_fft_direct([in0105, in0913, in1721, in2529]);
2961 let mut odds3 = self
2962 .bf8
2963 .perform_fft_direct([in3103, in0711, in1519, in2327]);
2964
2965 // step 3: apply twiddle factors
2966 odds1[0] = mul_complex_f32(odds1[0], self.twiddle01);
2967 odds3[0] = mul_complex_f32(odds3[0], self.twiddle01conj);
2968
2969 odds1[1] = mul_complex_f32(odds1[1], self.twiddle23);
2970 odds3[1] = mul_complex_f32(odds3[1], self.twiddle23conj);
2971
2972 odds1[2] = mul_complex_f32(odds1[2], self.twiddle45);
2973 odds3[2] = mul_complex_f32(odds3[2], self.twiddle45conj);
2974
2975 odds1[3] = mul_complex_f32(odds1[3], self.twiddle67);
2976 odds3[3] = mul_complex_f32(odds3[3], self.twiddle67conj);
2977
2978 // step 4: cross FFTs
2979 let mut temp0 = parallel_fft2_interleaved_f32(odds1[0], odds3[0]);
2980 let mut temp1 = parallel_fft2_interleaved_f32(odds1[1], odds3[1]);
2981 let mut temp2 = parallel_fft2_interleaved_f32(odds1[2], odds3[2]);
2982 let mut temp3 = parallel_fft2_interleaved_f32(odds1[3], odds3[3]);
2983
2984 // apply the butterfly 4 twiddle factor, which is just a rotation
2985 temp0[1] = self.rotate90.rotate_both(temp0[1]);
2986 temp1[1] = self.rotate90.rotate_both(temp1[1]);
2987 temp2[1] = self.rotate90.rotate_both(temp2[1]);
2988 temp3[1] = self.rotate90.rotate_both(temp3[1]);
2989
2990 //step 5: copy/add/subtract data back to buffer
2991 [
2992 f32x4_add(evens[0], temp0[0]),
2993 f32x4_add(evens[1], temp1[0]),
2994 f32x4_add(evens[2], temp2[0]),
2995 f32x4_add(evens[3], temp3[0]),
2996 f32x4_add(evens[4], temp0[1]),
2997 f32x4_add(evens[5], temp1[1]),
2998 f32x4_add(evens[6], temp2[1]),
2999 f32x4_add(evens[7], temp3[1]),
3000 f32x4_sub(evens[0], temp0[0]),
3001 f32x4_sub(evens[1], temp1[0]),
3002 f32x4_sub(evens[2], temp2[0]),
3003 f32x4_sub(evens[3], temp3[0]),
3004 f32x4_sub(evens[4], temp0[1]),
3005 f32x4_sub(evens[5], temp1[1]),
3006 f32x4_sub(evens[6], temp2[1]),
3007 f32x4_sub(evens[7], temp3[1]),
3008 ]
3009 }
3010
3011 #[inline(always)]
3012 pub(crate) unsafe fn perform_parallel_fft_direct(&self, input: [v128; 32]) -> [v128; 32] {
3013 // we're going to hardcode a step of split radix
3014
3015 // step 1: copy and reorder the input into the scratch
3016 // and
3017 // step 2: column FFTs
3018 let evens = self.bf16.perform_parallel_fft_direct([
3019 input[0], input[2], input[4], input[6], input[8], input[10], input[12], input[14],
3020 input[16], input[18], input[20], input[22], input[24], input[26], input[28], input[30],
3021 ]);
3022 let mut odds1 = self.bf8.perform_parallel_fft_direct([
3023 input[1], input[5], input[9], input[13], input[17], input[21], input[25], input[29],
3024 ]);
3025 let mut odds3 = self.bf8.perform_parallel_fft_direct([
3026 input[31], input[3], input[7], input[11], input[15], input[19], input[23], input[27],
3027 ]);
3028
3029 // step 3: apply twiddle factors
3030 odds1[1] = mul_complex_f32(odds1[1], self.twiddle1);
3031 odds3[1] = mul_complex_f32(odds3[1], self.twiddle1c);
3032
3033 odds1[2] = mul_complex_f32(odds1[2], self.twiddle2);
3034 odds3[2] = mul_complex_f32(odds3[2], self.twiddle2c);
3035
3036 odds1[3] = mul_complex_f32(odds1[3], self.twiddle3);
3037 odds3[3] = mul_complex_f32(odds3[3], self.twiddle3c);
3038
3039 odds1[4] = mul_complex_f32(odds1[4], self.twiddle4);
3040 odds3[4] = mul_complex_f32(odds3[4], self.twiddle4c);
3041
3042 odds1[5] = mul_complex_f32(odds1[5], self.twiddle5);
3043 odds3[5] = mul_complex_f32(odds3[5], self.twiddle5c);
3044
3045 odds1[6] = mul_complex_f32(odds1[6], self.twiddle6);
3046 odds3[6] = mul_complex_f32(odds3[6], self.twiddle6c);
3047
3048 odds1[7] = mul_complex_f32(odds1[7], self.twiddle7);
3049 odds3[7] = mul_complex_f32(odds3[7], self.twiddle7c);
3050
3051 // step 4: cross FFTs
3052 let mut temp0 = parallel_fft2_interleaved_f32(odds1[0], odds3[0]);
3053 let mut temp1 = parallel_fft2_interleaved_f32(odds1[1], odds3[1]);
3054 let mut temp2 = parallel_fft2_interleaved_f32(odds1[2], odds3[2]);
3055 let mut temp3 = parallel_fft2_interleaved_f32(odds1[3], odds3[3]);
3056 let mut temp4 = parallel_fft2_interleaved_f32(odds1[4], odds3[4]);
3057 let mut temp5 = parallel_fft2_interleaved_f32(odds1[5], odds3[5]);
3058 let mut temp6 = parallel_fft2_interleaved_f32(odds1[6], odds3[6]);
3059 let mut temp7 = parallel_fft2_interleaved_f32(odds1[7], odds3[7]);
3060
3061 // apply the butterfly 4 twiddle factor, which is just a rotation
3062 temp0[1] = self.rotate90.rotate_both(temp0[1]);
3063 temp1[1] = self.rotate90.rotate_both(temp1[1]);
3064 temp2[1] = self.rotate90.rotate_both(temp2[1]);
3065 temp3[1] = self.rotate90.rotate_both(temp3[1]);
3066 temp4[1] = self.rotate90.rotate_both(temp4[1]);
3067 temp5[1] = self.rotate90.rotate_both(temp5[1]);
3068 temp6[1] = self.rotate90.rotate_both(temp6[1]);
3069 temp7[1] = self.rotate90.rotate_both(temp7[1]);
3070
3071 //step 5: copy/add/subtract data back to buffer
3072 [
3073 f32x4_add(evens[0], temp0[0]),
3074 f32x4_add(evens[1], temp1[0]),
3075 f32x4_add(evens[2], temp2[0]),
3076 f32x4_add(evens[3], temp3[0]),
3077 f32x4_add(evens[4], temp4[0]),
3078 f32x4_add(evens[5], temp5[0]),
3079 f32x4_add(evens[6], temp6[0]),
3080 f32x4_add(evens[7], temp7[0]),
3081 f32x4_add(evens[8], temp0[1]),
3082 f32x4_add(evens[9], temp1[1]),
3083 f32x4_add(evens[10], temp2[1]),
3084 f32x4_add(evens[11], temp3[1]),
3085 f32x4_add(evens[12], temp4[1]),
3086 f32x4_add(evens[13], temp5[1]),
3087 f32x4_add(evens[14], temp6[1]),
3088 f32x4_add(evens[15], temp7[1]),
3089 f32x4_sub(evens[0], temp0[0]),
3090 f32x4_sub(evens[1], temp1[0]),
3091 f32x4_sub(evens[2], temp2[0]),
3092 f32x4_sub(evens[3], temp3[0]),
3093 f32x4_sub(evens[4], temp4[0]),
3094 f32x4_sub(evens[5], temp5[0]),
3095 f32x4_sub(evens[6], temp6[0]),
3096 f32x4_sub(evens[7], temp7[0]),
3097 f32x4_sub(evens[8], temp0[1]),
3098 f32x4_sub(evens[9], temp1[1]),
3099 f32x4_sub(evens[10], temp2[1]),
3100 f32x4_sub(evens[11], temp3[1]),
3101 f32x4_sub(evens[12], temp4[1]),
3102 f32x4_sub(evens[13], temp5[1]),
3103 f32x4_sub(evens[14], temp6[1]),
3104 f32x4_sub(evens[15], temp7[1]),
3105 ]
3106 }
3107 }
3108
3109 // _________ __ _ _ _ _ _
3110 // |___ /___ \ / /_ | || | | |__ (_) |_
3111 // |_ \ __) | _____ | '_ \| || |_| '_ \| | __|
3112 // ___) / __/ |_____| | (_) |__ _| |_) | | |_
3113 // |____/_____| \___/ |_| |_.__/|_|\__|
3114 //
3115
3116 pub struct WasmSimdF64Butterfly32<T> {
3117 direction: FftDirection,
3118 bf8: WasmSimdF64Butterfly8<T>,
3119 bf16: WasmSimdF64Butterfly16<T>,
3120 rotate90: Rotate90F64,
3121 twiddle1: v128,
3122 twiddle2: v128,
3123 twiddle3: v128,
3124 twiddle4: v128,
3125 twiddle5: v128,
3126 twiddle6: v128,
3127 twiddle7: v128,
3128 twiddle1c: v128,
3129 twiddle2c: v128,
3130 twiddle3c: v128,
3131 twiddle4c: v128,
3132 twiddle5c: v128,
3133 twiddle6c: v128,
3134 twiddle7c: v128,
3135 }
3136
3137 boilerplate_fft_wasm_simd_f64_butterfly!(
3138 WasmSimdF64Butterfly32,
3139 32,
3140 |this: &WasmSimdF64Butterfly32<_>| this.direction
3141 );
3142 boilerplate_fft_wasm_simd_common_butterfly!(
3143 WasmSimdF64Butterfly32,
3144 32,
3145 |this: &WasmSimdF64Butterfly32<_>| this.direction
3146 );
3147 impl<T: FftNum> WasmSimdF64Butterfly32<T> {
3148 #[inline(always)]
3149 pub fn new(direction: FftDirection) -> Self {
3150 assert_f64::<T>();
3151 let bf8 = WasmSimdF64Butterfly8::new(direction);
3152 let bf16 = WasmSimdF64Butterfly16::new(direction);
3153 let rotate90 = if direction == FftDirection::Inverse {
3154 Rotate90F64::new(true)
3155 } else {
3156 Rotate90F64::new(false)
3157 };
3158 let twiddle1 = unsafe {
3159 v128_load(
3160 &twiddles::compute_twiddle::<f64>(1, 32, direction) as *const _ as *const v128,
3161 )
3162 };
3163 let twiddle2 = unsafe {
3164 v128_load(
3165 &twiddles::compute_twiddle::<f64>(2, 32, direction) as *const _ as *const v128,
3166 )
3167 };
3168 let twiddle3 = unsafe {
3169 v128_load(
3170 &twiddles::compute_twiddle::<f64>(3, 32, direction) as *const _ as *const v128,
3171 )
3172 };
3173 let twiddle4 = unsafe {
3174 v128_load(
3175 &twiddles::compute_twiddle::<f64>(4, 32, direction) as *const _ as *const v128,
3176 )
3177 };
3178 let twiddle5 = unsafe {
3179 v128_load(
3180 &twiddles::compute_twiddle::<f64>(5, 32, direction) as *const _ as *const v128,
3181 )
3182 };
3183 let twiddle6 = unsafe {
3184 v128_load(
3185 &twiddles::compute_twiddle::<f64>(6, 32, direction) as *const _ as *const v128,
3186 )
3187 };
3188 let twiddle7 = unsafe {
3189 v128_load(
3190 &twiddles::compute_twiddle::<f64>(7, 32, direction) as *const _ as *const v128,
3191 )
3192 };
3193 let twiddle1c = unsafe {
3194 v128_load(
3195 &twiddles::compute_twiddle::<f64>(1, 32, direction).conj() as *const _
3196 as *const v128,
3197 )
3198 };
3199 let twiddle2c = unsafe {
3200 v128_load(
3201 &twiddles::compute_twiddle::<f64>(2, 32, direction).conj() as *const _
3202 as *const v128,
3203 )
3204 };
3205 let twiddle3c = unsafe {
3206 v128_load(
3207 &twiddles::compute_twiddle::<f64>(3, 32, direction).conj() as *const _
3208 as *const v128,
3209 )
3210 };
3211 let twiddle4c = unsafe {
3212 v128_load(
3213 &twiddles::compute_twiddle::<f64>(4, 32, direction).conj() as *const _
3214 as *const v128,
3215 )
3216 };
3217 let twiddle5c = unsafe {
3218 v128_load(
3219 &twiddles::compute_twiddle::<f64>(5, 32, direction).conj() as *const _
3220 as *const v128,
3221 )
3222 };
3223 let twiddle6c = unsafe {
3224 v128_load(
3225 &twiddles::compute_twiddle::<f64>(6, 32, direction).conj() as *const _
3226 as *const v128,
3227 )
3228 };
3229 let twiddle7c = unsafe {
3230 v128_load(
3231 &twiddles::compute_twiddle::<f64>(7, 32, direction).conj() as *const _
3232 as *const v128,
3233 )
3234 };
3235
3236 Self {
3237 direction,
3238 bf8,
3239 bf16,
3240 rotate90,
3241 twiddle1,
3242 twiddle2,
3243 twiddle3,
3244 twiddle4,
3245 twiddle5,
3246 twiddle6,
3247 twiddle7,
3248 twiddle1c,
3249 twiddle2c,
3250 twiddle3c,
3251 twiddle4c,
3252 twiddle5c,
3253 twiddle6c,
3254 twiddle7c,
3255 }
3256 }
3257
3258 #[inline(always)]
3259 unsafe fn perform_fft_contiguous(&self, mut buffer: impl WasmSimdArrayMut<f64>) {
3260 let values = read_complex_to_array!(buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31});
3261
3262 let out = self.perform_fft_direct(values);
3263
3264 write_complex_to_array!(out, buffer, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31});
3265 }
3266
3267 #[inline(always)]
3268 unsafe fn perform_fft_direct(&self, input: [v128; 32]) -> [v128; 32] {
3269 // we're going to hardcode a step of split radix
3270
3271 // step 1: copy and reorder the input into the scratch
3272 // and
3273 // step 2: column FFTs
3274 let evens = self.bf16.perform_fft_direct([
3275 input[0], input[2], input[4], input[6], input[8], input[10], input[12], input[14],
3276 input[16], input[18], input[20], input[22], input[24], input[26], input[28], input[30],
3277 ]);
3278 let mut odds1 = self.bf8.perform_fft_direct([
3279 input[1], input[5], input[9], input[13], input[17], input[21], input[25], input[29],
3280 ]);
3281 let mut odds3 = self.bf8.perform_fft_direct([
3282 input[31], input[3], input[7], input[11], input[15], input[19], input[23], input[27],
3283 ]);
3284
3285 // step 3: apply twiddle factors
3286 odds1[1] = mul_complex_f64(odds1[1], self.twiddle1);
3287 odds3[1] = mul_complex_f64(odds3[1], self.twiddle1c);
3288
3289 odds1[2] = mul_complex_f64(odds1[2], self.twiddle2);
3290 odds3[2] = mul_complex_f64(odds3[2], self.twiddle2c);
3291
3292 odds1[3] = mul_complex_f64(odds1[3], self.twiddle3);
3293 odds3[3] = mul_complex_f64(odds3[3], self.twiddle3c);
3294
3295 odds1[4] = mul_complex_f64(odds1[4], self.twiddle4);
3296 odds3[4] = mul_complex_f64(odds3[4], self.twiddle4c);
3297
3298 odds1[5] = mul_complex_f64(odds1[5], self.twiddle5);
3299 odds3[5] = mul_complex_f64(odds3[5], self.twiddle5c);
3300
3301 odds1[6] = mul_complex_f64(odds1[6], self.twiddle6);
3302 odds3[6] = mul_complex_f64(odds3[6], self.twiddle6c);
3303
3304 odds1[7] = mul_complex_f64(odds1[7], self.twiddle7);
3305 odds3[7] = mul_complex_f64(odds3[7], self.twiddle7c);
3306
3307 // step 4: cross FFTs
3308 let mut temp0 = solo_fft2_f64(odds1[0], odds3[0]);
3309 let mut temp1 = solo_fft2_f64(odds1[1], odds3[1]);
3310 let mut temp2 = solo_fft2_f64(odds1[2], odds3[2]);
3311 let mut temp3 = solo_fft2_f64(odds1[3], odds3[3]);
3312 let mut temp4 = solo_fft2_f64(odds1[4], odds3[4]);
3313 let mut temp5 = solo_fft2_f64(odds1[5], odds3[5]);
3314 let mut temp6 = solo_fft2_f64(odds1[6], odds3[6]);
3315 let mut temp7 = solo_fft2_f64(odds1[7], odds3[7]);
3316
3317 // apply the butterfly 4 twiddle factor, which is just a rotation
3318 temp0[1] = self.rotate90.rotate(temp0[1]);
3319 temp1[1] = self.rotate90.rotate(temp1[1]);
3320 temp2[1] = self.rotate90.rotate(temp2[1]);
3321 temp3[1] = self.rotate90.rotate(temp3[1]);
3322 temp4[1] = self.rotate90.rotate(temp4[1]);
3323 temp5[1] = self.rotate90.rotate(temp5[1]);
3324 temp6[1] = self.rotate90.rotate(temp6[1]);
3325 temp7[1] = self.rotate90.rotate(temp7[1]);
3326
3327 //step 5: copy/add/subtract data back to buffer
3328 [
3329 f64x2_add(evens[0], temp0[0]),
3330 f64x2_add(evens[1], temp1[0]),
3331 f64x2_add(evens[2], temp2[0]),
3332 f64x2_add(evens[3], temp3[0]),
3333 f64x2_add(evens[4], temp4[0]),
3334 f64x2_add(evens[5], temp5[0]),
3335 f64x2_add(evens[6], temp6[0]),
3336 f64x2_add(evens[7], temp7[0]),
3337 f64x2_add(evens[8], temp0[1]),
3338 f64x2_add(evens[9], temp1[1]),
3339 f64x2_add(evens[10], temp2[1]),
3340 f64x2_add(evens[11], temp3[1]),
3341 f64x2_add(evens[12], temp4[1]),
3342 f64x2_add(evens[13], temp5[1]),
3343 f64x2_add(evens[14], temp6[1]),
3344 f64x2_add(evens[15], temp7[1]),
3345 f64x2_sub(evens[0], temp0[0]),
3346 f64x2_sub(evens[1], temp1[0]),
3347 f64x2_sub(evens[2], temp2[0]),
3348 f64x2_sub(evens[3], temp3[0]),
3349 f64x2_sub(evens[4], temp4[0]),
3350 f64x2_sub(evens[5], temp5[0]),
3351 f64x2_sub(evens[6], temp6[0]),
3352 f64x2_sub(evens[7], temp7[0]),
3353 f64x2_sub(evens[8], temp0[1]),
3354 f64x2_sub(evens[9], temp1[1]),
3355 f64x2_sub(evens[10], temp2[1]),
3356 f64x2_sub(evens[11], temp3[1]),
3357 f64x2_sub(evens[12], temp4[1]),
3358 f64x2_sub(evens[13], temp5[1]),
3359 f64x2_sub(evens[14], temp6[1]),
3360 f64x2_sub(evens[15], temp7[1]),
3361 ]
3362 }
3363 }
3364
3365 #[cfg(test)]
3366 mod unit_tests {
3367 use super::*;
3368 use crate::algorithm::Dft;
3369 use crate::test_utils::{check_fft_algorithm, compare_vectors};
3370 use wasm_bindgen_test::wasm_bindgen_test;
3371
3372 //the tests for all butterflies will be identical except for the identifiers used and size
3373 //so it's ideal for a macro
3374 macro_rules! test_butterfly_32_func {
3375 ($test_name:ident, $struct_name:ident, $size:expr) => {
3376 #[wasm_bindgen_test]
3377 fn $test_name() {
3378 let butterfly = $struct_name::new(FftDirection::Forward);
3379 check_fft_algorithm::<f32>(&butterfly, $size, FftDirection::Forward);
3380
3381 let butterfly_direction = $struct_name::new(FftDirection::Inverse);
3382 check_fft_algorithm::<f32>(&butterfly_direction, $size, FftDirection::Inverse);
3383 }
3384 };
3385 }
3386 test_butterfly_32_func!(test_wasm_simdf32_butterfly1, WasmSimdF32Butterfly1, 1);
3387 test_butterfly_32_func!(test_wasm_simdf32_butterfly2, WasmSimdF32Butterfly2, 2);
3388 test_butterfly_32_func!(test_wasm_simdf32_butterfly3, WasmSimdF32Butterfly3, 3);
3389 test_butterfly_32_func!(test_wasm_simdf32_butterfly4, WasmSimdF32Butterfly4, 4);
3390 test_butterfly_32_func!(test_wasm_simdf32_butterfly5, WasmSimdF32Butterfly5, 5);
3391 test_butterfly_32_func!(test_wasm_simdf32_butterfly6, WasmSimdF32Butterfly6, 6);
3392 test_butterfly_32_func!(test_wasm_simdf32_butterfly8, WasmSimdF32Butterfly8, 8);
3393 test_butterfly_32_func!(test_wasm_simdf32_butterfly9, WasmSimdF32Butterfly9, 9);
3394 test_butterfly_32_func!(test_wasm_simdf32_butterfly10, WasmSimdF32Butterfly10, 10);
3395 test_butterfly_32_func!(test_wasm_simdf32_butterfly12, WasmSimdF32Butterfly12, 12);
3396 test_butterfly_32_func!(test_wasm_simdf32_butterfly15, WasmSimdF32Butterfly15, 15);
3397 test_butterfly_32_func!(test_wasm_simdf32_butterfly16, WasmSimdF32Butterfly16, 16);
3398 test_butterfly_32_func!(test_wasm_simdf32_butterfly32, WasmSimdF32Butterfly32, 32);
3399
3400 //the tests for all butterflies will be identical except for the identifiers used and size
3401 //so it's ideal for a macro
3402 macro_rules! test_butterfly_64_func {
3403 ($test_name:ident, $struct_name:ident, $size:expr) => {
3404 #[wasm_bindgen_test]
3405 fn $test_name() {
3406 let butterfly = $struct_name::new(FftDirection::Forward);
3407 check_fft_algorithm::<f64>(&butterfly, $size, FftDirection::Forward);
3408
3409 let butterfly_direction = $struct_name::new(FftDirection::Inverse);
3410 check_fft_algorithm::<f64>(&butterfly_direction, $size, FftDirection::Inverse);
3411 }
3412 };
3413 }
3414 test_butterfly_64_func!(test_wasm_simdf64_butterfly1, WasmSimdF64Butterfly1, 1);
3415 test_butterfly_64_func!(test_wasm_simdf64_butterfly2, WasmSimdF64Butterfly2, 2);
3416 test_butterfly_64_func!(test_wasm_simdf64_butterfly3, WasmSimdF64Butterfly3, 3);
3417 test_butterfly_64_func!(test_wasm_simdf64_butterfly4, WasmSimdF64Butterfly4, 4);
3418 test_butterfly_64_func!(test_wasm_simdf64_butterfly5, WasmSimdF64Butterfly5, 5);
3419 test_butterfly_64_func!(test_wasm_simdf64_butterfly6, WasmSimdF64Butterfly6, 6);
3420 test_butterfly_64_func!(test_wasm_simdf64_butterfly8, WasmSimdF64Butterfly8, 8);
3421 test_butterfly_64_func!(test_wasm_simdf64_butterfly9, WasmSimdF64Butterfly9, 9);
3422 test_butterfly_64_func!(test_wasm_simdf64_butterfly10, WasmSimdF64Butterfly10, 10);
3423 test_butterfly_64_func!(test_wasm_simdf64_butterfly12, WasmSimdF64Butterfly12, 12);
3424 test_butterfly_64_func!(test_wasm_simdf64_butterfly15, WasmSimdF64Butterfly15, 15);
3425 test_butterfly_64_func!(test_wasm_simdf64_butterfly16, WasmSimdF64Butterfly16, 16);
3426 test_butterfly_64_func!(test_wasm_simdf64_butterfly32, WasmSimdF64Butterfly32, 32);
3427
3428 #[wasm_bindgen_test]
3429 fn test_solo_fft2_32() {
3430 unsafe {
3431 let val1 = Complex::<f32>::new(1.0, 2.5);
3432 let val2 = Complex::<f32>::new(3.2, 4.2);
3433
3434 let mut val = vec![val1, val2];
3435
3436 let in_packed = v128_load(val.as_ptr() as *const v128);
3437
3438 let dft = Dft::new(2, FftDirection::Forward);
3439
3440 let bf2 = WasmSimdF32Butterfly2::<f32>::new(FftDirection::Forward);
3441
3442 dft.process(&mut val);
3443 let res_packed = bf2.perform_fft_direct(in_packed);
3444
3445 let res = std::mem::transmute::<v128, [Complex<f32>; 2]>(res_packed);
3446 assert_eq!(val[0], res[0]);
3447 assert_eq!(val[1], res[1]);
3448 }
3449 }
3450
3451 #[wasm_bindgen_test]
3452 fn test_parallel_fft2_32() {
3453 unsafe {
3454 let val_a1 = Complex::<f32>::new(1.0, 2.5);
3455 let val_a2 = Complex::<f32>::new(3.2, 4.2);
3456
3457 let val_b1 = Complex::<f32>::new(6.0, 24.5);
3458 let val_b2 = Complex::<f32>::new(4.3, 34.2);
3459
3460 let mut val_a = vec![val_a1, val_a2];
3461 let mut val_b = vec![val_b1, val_b2];
3462
3463 let p1 = v128_load(val_a.as_ptr() as *const v128);
3464 let p2 = v128_load(val_b.as_ptr() as *const v128);
3465
3466 let dft = Dft::new(2, FftDirection::Forward);
3467
3468 let bf2 = WasmSimdF32Butterfly2::<f32>::new(FftDirection::Forward);
3469
3470 dft.process(&mut val_a);
3471 dft.process(&mut val_b);
3472 let res_both = bf2.perform_parallel_fft_direct(p1, p2);
3473
3474 let res = std::mem::transmute::<[v128; 2], [Complex<f32>; 4]>(res_both);
3475 let wasmsimd_res_a = [res[0], res[2]];
3476 let wasmsimd_res_b = [res[1], res[3]];
3477 assert!(compare_vectors(&val_a, &wasmsimd_res_a));
3478 assert!(compare_vectors(&val_b, &wasmsimd_res_b));
3479 }
3480 }
3481 }