Debian Codegraph @

.cargo/vendor/rustfft/src/sse/sse_butterflies.rs

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