rustfft/avx/
avx64_butterflies.rs

1use std::arch::x86_64::*;
2use std::marker::PhantomData;
3use std::mem::MaybeUninit;
4
5use num_complex::Complex;
6
7use crate::array_utils::DoubleBuf;
8use crate::{common::FftNum, twiddles};
9use crate::{Direction, Fft, FftDirection, Length};
10
11use super::avx64_utils;
12use super::avx_vector;
13use super::avx_vector::{AvxArray, AvxArrayMut, AvxVector, AvxVector128, AvxVector256, Rotation90};
14
15// Safety: This macro will call `self::perform_fft_f32()` which probably has a #[target_feature(enable = "...")] annotation on it.
16// Calling functions with that annotation is unsafe, because it doesn't actually check if the CPU has the required features.
17// Callers of this macro must guarantee that users can't even obtain an instance of $struct_name if their CPU doesn't have the required CPU features.
18#[allow(unused)]
19macro_rules! boilerplate_fft_simd_butterfly {
20    ($struct_name:ident, $len:expr) => {
21        impl $struct_name<f64> {
22            #[inline]
23            pub fn new(direction: FftDirection) -> Result<Self, ()> {
24                let has_avx = is_x86_feature_detected!("avx");
25                let has_fma = is_x86_feature_detected!("fma");
26                if has_avx && has_fma {
27                    // Safety: new_internal requires the "avx" feature set. Since we know it's present, we're safe
28                    Ok(unsafe { Self::new_with_avx(direction) })
29                } else {
30                    Err(())
31                }
32            }
33        }
34        impl<T: FftNum> Fft<T> for $struct_name<f64> {
35            fn process_immutable_with_scratch(
36                &self,
37                input: &[Complex<T>],
38                output: &mut [Complex<T>],
39                _scratch: &mut [Complex<T>],
40            ) {
41                unsafe {
42                    let simd_input = crate::array_utils::workaround_transmute(input);
43                    let simd_output = crate::array_utils::workaround_transmute_mut(output);
44                    super::avx_fft_helper_immut(
45                        simd_input,
46                        simd_output,
47                        &mut [],
48                        self.len(),
49                        0,
50                        |input, output, _| self.perform_fft_f64(DoubleBuf { input, output }),
51                    );
52                }
53            }
54            fn process_outofplace_with_scratch(
55                &self,
56                input: &mut [Complex<T>],
57                output: &mut [Complex<T>],
58                _scratch: &mut [Complex<T>],
59            ) {
60                unsafe {
61                    let simd_input = crate::array_utils::workaround_transmute_mut(input);
62                    let simd_output = crate::array_utils::workaround_transmute_mut(output);
63                    super::avx_fft_helper_outofplace(
64                        simd_input,
65                        simd_output,
66                        &mut [],
67                        self.len(),
68                        0,
69                        |input, output, _| self.perform_fft_f64(DoubleBuf { input, output }),
70                    );
71                }
72            }
73            fn process_with_scratch(&self, buffer: &mut [Complex<T>], _scratch: &mut [Complex<T>]) {
74                unsafe {
75                    let simd_buffer = crate::array_utils::workaround_transmute_mut(buffer);
76                    super::avx_fft_helper_inplace(
77                        simd_buffer,
78                        &mut [],
79                        self.len(),
80                        0,
81                        |chunk, _| self.perform_fft_f64(chunk),
82                    )
83                }
84            }
85            #[inline(always)]
86            fn get_inplace_scratch_len(&self) -> usize {
87                0
88            }
89            #[inline(always)]
90            fn get_outofplace_scratch_len(&self) -> usize {
91                0
92            }
93            #[inline(always)]
94            fn get_immutable_scratch_len(&self) -> usize {
95                0
96            }
97        }
98        impl<T> Length for $struct_name<T> {
99            #[inline(always)]
100            fn len(&self) -> usize {
101                $len
102            }
103        }
104        impl<T> Direction for $struct_name<T> {
105            #[inline(always)]
106            fn fft_direction(&self) -> FftDirection {
107                self.direction
108            }
109        }
110    };
111}
112
113// Safety: This macro will call `self::column_butterflies_and_transpose()` and `self::row_butterflies()` which probably has a #[target_feature(enable = "...")] annotation on it.
114// Calling functions with that annotation is unsafe, because it doesn't actually check if the CPU has the required features.
115// Callers of this macro must guarantee that users can't even obtain an instance of $struct_name if their CPU doesn't have the required CPU features.
116macro_rules! boilerplate_fft_simd_butterfly_with_scratch {
117    ($struct_name:ident, $len:expr) => {
118        impl $struct_name<f64> {
119            #[inline]
120            pub fn is_supported_by_cpu() -> bool {
121                is_x86_feature_detected!("avx") && is_x86_feature_detected!("fma")
122            }
123            #[inline]
124            pub fn new(direction: FftDirection) -> Result<Self, ()> {
125                if Self::is_supported_by_cpu() {
126                    // Safety: new_internal requires the "avx" feature set. Since we know it's present, we're safe
127                    Ok(unsafe { Self::new_with_avx(direction) })
128                } else {
129                    Err(())
130                }
131            }
132        }
133        impl<T> $struct_name<T> {
134            #[inline]
135            fn perform_fft_inplace(
136                &self,
137                buffer: &mut [Complex<f64>],
138                scratch: &mut [Complex<f64>],
139            ) {
140                // Perform the column FFTs
141                // Safety: self.perform_column_butterflies() requres the "avx" and "fma" instruction sets, and we return Err() in our constructor if the instructions aren't available
142                unsafe { self.column_butterflies_and_transpose(buffer, scratch) };
143
144                // process the row FFTs, and copy from the scratch back to the buffer as we go
145                // Safety: self.transpose() requres the "avx" instruction set, and we return Err() in our constructor if the instructions aren't available
146                unsafe {
147                    self.row_butterflies(DoubleBuf {
148                        input: scratch,
149                        output: buffer,
150                    })
151                };
152            }
153
154            #[inline]
155            fn perform_fft_immut(&self, input: &[Complex<f64>], output: &mut [Complex<f64>]) {
156                // Perform the column FFTs
157                // Safety: self.perform_column_butterflies() requres the "avx" and "fma" instruction sets, and we return Err() in our constructor if the instructions aren't available
158                unsafe { self.column_butterflies_and_transpose(input, output) };
159
160                // process the row FFTs in-place in the output buffer
161                // Safety: self.transpose() requres the "avx" instruction set, and we return Err() in our constructor if the instructions aren't available
162                unsafe { self.row_butterflies(output) };
163            }
164        }
165        impl<T: FftNum> Fft<T> for $struct_name<f64> {
166            fn process_immutable_with_scratch(
167                &self,
168                input: &[Complex<T>],
169                output: &mut [Complex<T>],
170                _scratch: &mut [Complex<T>],
171            ) {
172                unsafe {
173                    let simd_input = crate::array_utils::workaround_transmute(input);
174                    let simd_output = crate::array_utils::workaround_transmute_mut(output);
175                    super::avx_fft_helper_immut(
176                        simd_input,
177                        simd_output,
178                        &mut [],
179                        self.len(),
180                        0,
181                        |input, output, _| self.perform_fft_immut(input, output),
182                    );
183                }
184            }
185            fn process_outofplace_with_scratch(
186                &self,
187                input: &mut [Complex<T>],
188                output: &mut [Complex<T>],
189                _scratch: &mut [Complex<T>],
190            ) {
191                unsafe {
192                    let simd_input = crate::array_utils::workaround_transmute_mut(input);
193                    let simd_output = crate::array_utils::workaround_transmute_mut(output);
194                    super::avx_fft_helper_outofplace(
195                        simd_input,
196                        simd_output,
197                        &mut [],
198                        self.len(),
199                        0,
200                        |input, output, _| self.perform_fft_immut(input, output),
201                    );
202                }
203            }
204            fn process_with_scratch(&self, buffer: &mut [Complex<T>], scratch: &mut [Complex<T>]) {
205                unsafe {
206                    let simd_buffer = crate::array_utils::workaround_transmute_mut(buffer);
207                    let simd_scratch = crate::array_utils::workaround_transmute_mut(scratch);
208                    super::avx_fft_helper_inplace(
209                        simd_buffer,
210                        simd_scratch,
211                        self.len(),
212                        self.len(),
213                        |chunk, scratch| self.perform_fft_inplace(chunk, scratch),
214                    )
215                }
216            }
217            #[inline(always)]
218            fn get_inplace_scratch_len(&self) -> usize {
219                $len
220            }
221            #[inline(always)]
222            fn get_outofplace_scratch_len(&self) -> usize {
223                0
224            }
225            #[inline(always)]
226            fn get_immutable_scratch_len(&self) -> usize {
227                0
228            }
229        }
230        impl<T> Length for $struct_name<T> {
231            #[inline(always)]
232            fn len(&self) -> usize {
233                $len
234            }
235        }
236        impl<T> Direction for $struct_name<T> {
237            #[inline(always)]
238            fn fft_direction(&self) -> FftDirection {
239                self.direction
240            }
241        }
242    };
243}
244
245macro_rules! gen_butterfly_twiddles_interleaved_columns {
246    ($num_rows:expr, $num_cols:expr, $skip_cols:expr, $direction: expr) => {{
247        const FFT_LEN: usize = $num_rows * $num_cols;
248        const TWIDDLE_ROWS: usize = $num_rows - 1;
249        const TWIDDLE_COLS: usize = $num_cols - $skip_cols;
250        const TWIDDLE_VECTOR_COLS: usize = TWIDDLE_COLS / 2;
251        const TWIDDLE_VECTOR_COUNT: usize = TWIDDLE_VECTOR_COLS * TWIDDLE_ROWS;
252        let mut twiddles = [AvxVector::zero(); TWIDDLE_VECTOR_COUNT];
253        for index in 0..TWIDDLE_VECTOR_COUNT {
254            let y = (index / TWIDDLE_VECTOR_COLS) + 1;
255            let x = (index % TWIDDLE_VECTOR_COLS) * 2 + $skip_cols;
256
257            twiddles[index] = AvxVector::make_mixedradix_twiddle_chunk(x, y, FFT_LEN, $direction);
258        }
259        twiddles
260    }};
261}
262
263macro_rules! gen_butterfly_twiddles_separated_columns {
264    ($num_rows:expr, $num_cols:expr, $skip_cols:expr, $direction: expr) => {{
265        const FFT_LEN: usize = $num_rows * $num_cols;
266        const TWIDDLE_ROWS: usize = $num_rows - 1;
267        const TWIDDLE_COLS: usize = $num_cols - $skip_cols;
268        const TWIDDLE_VECTOR_COLS: usize = TWIDDLE_COLS / 2;
269        const TWIDDLE_VECTOR_COUNT: usize = TWIDDLE_VECTOR_COLS * TWIDDLE_ROWS;
270        let mut twiddles = [AvxVector::zero(); TWIDDLE_VECTOR_COUNT];
271        for index in 0..TWIDDLE_VECTOR_COUNT {
272            let y = (index % TWIDDLE_ROWS) + 1;
273            let x = (index / TWIDDLE_ROWS) * 2 + $skip_cols;
274
275            twiddles[index] = AvxVector::make_mixedradix_twiddle_chunk(x, y, FFT_LEN, $direction);
276        }
277        twiddles
278    }};
279}
280
281pub struct Butterfly5Avx64<T> {
282    twiddles: [__m256d; 3],
283    direction: FftDirection,
284    _phantom_t: std::marker::PhantomData<T>,
285}
286boilerplate_fft_simd_butterfly!(Butterfly5Avx64, 5);
287impl Butterfly5Avx64<f64> {
288    #[target_feature(enable = "avx")]
289    unsafe fn new_with_avx(direction: FftDirection) -> Self {
290        let twiddle1 = twiddles::compute_twiddle(1, 5, direction);
291        let twiddle2 = twiddles::compute_twiddle(2, 5, direction);
292        Self {
293            twiddles: [
294                _mm256_set_pd(twiddle1.im, twiddle1.im, twiddle1.re, twiddle1.re),
295                _mm256_set_pd(twiddle2.im, twiddle2.im, twiddle2.re, twiddle2.re),
296                _mm256_set_pd(-twiddle1.im, -twiddle1.im, twiddle1.re, twiddle1.re),
297            ],
298            direction,
299            _phantom_t: PhantomData,
300        }
301    }
302}
303impl<T> Butterfly5Avx64<T> {
304    #[target_feature(enable = "avx", enable = "fma")]
305    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
306        let input0 = _mm256_loadu2_m128d(
307            buffer.input_ptr() as *const f64,
308            buffer.input_ptr() as *const f64,
309        );
310        let input12 = buffer.load_complex(1);
311        let input34 = buffer.load_complex(3);
312
313        // swap elements for inputs 3 and 4
314        let input43 = AvxVector::reverse_complex_elements(input34);
315
316        // do some prep work before we can start applying twiddle factors
317        let [sum12, diff43] = AvxVector::column_butterfly2([input12, input43]);
318
319        let rotation = AvxVector::make_rotation90(FftDirection::Inverse);
320        let rotated43 = AvxVector::rotate90(diff43, rotation);
321
322        let [mid14, mid23] = avx64_utils::transpose_2x2_f64([sum12, rotated43]);
323
324        // to compute the first output, compute the sum of all elements. mid14[0] and mid23[0] already have the sum of 1+4 and 2+3 respectively, so if we add them, we'll get the sum of all 4
325        let sum1234 = AvxVector::add(mid14.lo(), mid23.lo());
326        let output0 = AvxVector::add(input0.lo(), sum1234);
327
328        // apply twiddle factors
329        let twiddled_outer14 = AvxVector::mul(mid14, self.twiddles[0]);
330        let twiddled_inner14 = AvxVector::mul(mid14, self.twiddles[1]);
331        let twiddled14 = AvxVector::fmadd(mid23, self.twiddles[1], twiddled_outer14);
332        let twiddled23 = AvxVector::fmadd(mid23, self.twiddles[2], twiddled_inner14);
333
334        // unpack the data for the last butterfly 2
335        let [twiddled12, twiddled43] = avx64_utils::transpose_2x2_f64([twiddled14, twiddled23]);
336        let [output12, output43] = AvxVector::column_butterfly2([twiddled12, twiddled43]);
337
338        // swap the elements in output43 before writing them out, and add the first input to everything
339        let final12 = AvxVector::add(input0, output12);
340        let output34 = AvxVector::reverse_complex_elements(output43);
341        let final34 = AvxVector::add(input0, output34);
342
343        buffer.store_partial1_complex(output0, 0);
344        buffer.store_complex(final12, 1);
345        buffer.store_complex(final34, 3);
346    }
347}
348
349pub struct Butterfly7Avx64<T> {
350    twiddles: [__m256d; 5],
351    direction: FftDirection,
352    _phantom_t: std::marker::PhantomData<T>,
353}
354boilerplate_fft_simd_butterfly!(Butterfly7Avx64, 7);
355impl Butterfly7Avx64<f64> {
356    #[target_feature(enable = "avx")]
357    unsafe fn new_with_avx(direction: FftDirection) -> Self {
358        let twiddle1 = twiddles::compute_twiddle(1, 7, direction);
359        let twiddle2 = twiddles::compute_twiddle(2, 7, direction);
360        let twiddle3 = twiddles::compute_twiddle(3, 7, direction);
361        Self {
362            twiddles: [
363                _mm256_set_pd(twiddle1.im, twiddle1.im, twiddle1.re, twiddle1.re),
364                _mm256_set_pd(twiddle2.im, twiddle2.im, twiddle2.re, twiddle2.re),
365                _mm256_set_pd(twiddle3.im, twiddle3.im, twiddle3.re, twiddle3.re),
366                _mm256_set_pd(-twiddle3.im, -twiddle3.im, twiddle3.re, twiddle3.re),
367                _mm256_set_pd(-twiddle1.im, -twiddle1.im, twiddle1.re, twiddle1.re),
368            ],
369            direction,
370            _phantom_t: PhantomData,
371        }
372    }
373}
374impl<T> Butterfly7Avx64<T> {
375    #[target_feature(enable = "avx", enable = "fma")]
376    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
377        let input0 = _mm256_loadu2_m128d(
378            buffer.input_ptr() as *const f64,
379            buffer.input_ptr() as *const f64,
380        );
381        let input12 = buffer.load_complex(1);
382        let input3 = buffer.load_partial1_complex(3);
383        let input4 = buffer.load_partial1_complex(4);
384        let input56 = buffer.load_complex(5);
385
386        // reverse the order of input56
387        let input65 = AvxVector::reverse_complex_elements(input56);
388
389        // do some prep work before we can start applying twiddle factors
390        let [sum12, diff65] = AvxVector::column_butterfly2([input12, input65]);
391        let [sum3, diff4] = AvxVector::column_butterfly2([input3, input4]);
392
393        let rotation = AvxVector::make_rotation90(FftDirection::Inverse);
394        let rotated65 = AvxVector::rotate90(diff65, rotation);
395        let rotated4 = AvxVector::rotate90(diff4, rotation.lo());
396
397        let [mid16, mid25] = avx64_utils::transpose_2x2_f64([sum12, rotated65]);
398        let mid34 = AvxVector128::merge(sum3, rotated4);
399
400        // to compute the first output, compute the sum of all elements. mid16[0], mid25[0], and mid34[0] already have the sum of 1+6, 2+5 and 3+4 respectively, so if we add them, we'll get 1+2+3+4+5+6
401        let output0_left = AvxVector::add(mid16.lo(), mid25.lo());
402        let output0_right = AvxVector::add(input0.lo(), mid34.lo());
403        let output0 = AvxVector::add(output0_left, output0_right);
404        buffer.store_partial1_complex(output0, 0);
405
406        // apply twiddle factors
407        let twiddled16_intermediate1 = AvxVector::mul(mid16, self.twiddles[0]);
408        let twiddled25_intermediate1 = AvxVector::mul(mid16, self.twiddles[1]);
409        let twiddled34_intermediate1 = AvxVector::mul(mid16, self.twiddles[2]);
410
411        let twiddled16_intermediate2 =
412            AvxVector::fmadd(mid25, self.twiddles[1], twiddled16_intermediate1);
413        let twiddled25_intermediate2 =
414            AvxVector::fmadd(mid25, self.twiddles[3], twiddled25_intermediate1);
415        let twiddled34_intermediate2 =
416            AvxVector::fmadd(mid25, self.twiddles[4], twiddled34_intermediate1);
417
418        let twiddled16 = AvxVector::fmadd(mid34, self.twiddles[2], twiddled16_intermediate2);
419        let twiddled25 = AvxVector::fmadd(mid34, self.twiddles[4], twiddled25_intermediate2);
420        let twiddled34 = AvxVector::fmadd(mid34, self.twiddles[1], twiddled34_intermediate2);
421
422        // unpack the data for the last butterfly 2
423        let [twiddled12, twiddled65] = avx64_utils::transpose_2x2_f64([twiddled16, twiddled25]);
424
425        // we can save one add if we add input0 to twiddled3 now. normally we'd add input0 to the final output, but the arrangement of data makes that a little awkward
426        let twiddled03 = AvxVector::add(twiddled34.lo(), input0.lo());
427
428        let [output12, output65] = AvxVector::column_butterfly2([twiddled12, twiddled65]);
429        let final12 = AvxVector::add(output12, input0);
430        let output56 = AvxVector::reverse_complex_elements(output65);
431        let final56 = AvxVector::add(output56, input0);
432
433        let [final3, final4] = AvxVector::column_butterfly2([twiddled03, twiddled34.hi()]);
434
435        buffer.store_complex(final12, 1);
436        buffer.store_partial1_complex(final3, 3);
437        buffer.store_partial1_complex(final4, 4);
438        buffer.store_complex(final56, 5);
439    }
440}
441
442pub struct Butterfly11Avx64<T> {
443    twiddles: [__m256d; 10],
444    direction: FftDirection,
445    _phantom_t: std::marker::PhantomData<T>,
446}
447boilerplate_fft_simd_butterfly!(Butterfly11Avx64, 11);
448impl Butterfly11Avx64<f64> {
449    #[target_feature(enable = "avx")]
450    unsafe fn new_with_avx(direction: FftDirection) -> Self {
451        let twiddle1 = twiddles::compute_twiddle(1, 11, direction);
452        let twiddle2 = twiddles::compute_twiddle(2, 11, direction);
453        let twiddle3 = twiddles::compute_twiddle(3, 11, direction);
454        let twiddle4 = twiddles::compute_twiddle(4, 11, direction);
455        let twiddle5 = twiddles::compute_twiddle(5, 11, direction);
456
457        let twiddles = [
458            _mm256_set_pd(twiddle1.im, twiddle1.im, twiddle1.re, twiddle1.re),
459            _mm256_set_pd(twiddle2.im, twiddle2.im, twiddle2.re, twiddle2.re),
460            _mm256_set_pd(twiddle3.im, twiddle3.im, twiddle3.re, twiddle3.re),
461            _mm256_set_pd(twiddle4.im, twiddle4.im, twiddle4.re, twiddle4.re),
462            _mm256_set_pd(twiddle5.im, twiddle5.im, twiddle5.re, twiddle5.re),
463            _mm256_set_pd(-twiddle5.im, -twiddle5.im, twiddle5.re, twiddle5.re),
464            _mm256_set_pd(-twiddle4.im, -twiddle4.im, twiddle4.re, twiddle4.re),
465            _mm256_set_pd(-twiddle3.im, -twiddle3.im, twiddle3.re, twiddle3.re),
466            _mm256_set_pd(-twiddle2.im, -twiddle2.im, twiddle2.re, twiddle2.re),
467            _mm256_set_pd(-twiddle1.im, -twiddle1.im, twiddle1.re, twiddle1.re),
468        ];
469
470        Self {
471            twiddles,
472            direction,
473            _phantom_t: PhantomData,
474        }
475    }
476}
477impl<T> Butterfly11Avx64<T> {
478    #[target_feature(enable = "avx", enable = "fma")]
479    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
480        let input0 = buffer.load_partial1_complex(0);
481        let input12 = buffer.load_complex(1);
482        let input34 = buffer.load_complex(3);
483        let input56 = buffer.load_complex(5);
484        let input78 = buffer.load_complex(7);
485        let input910 = buffer.load_complex(9);
486
487        // reverse the order of input78910, and separate
488        let [input55, input66] = AvxVector::unpack_complex([input56, input56]);
489        let input87 = AvxVector::reverse_complex_elements(input78);
490        let input109 = AvxVector::reverse_complex_elements(input910);
491
492        // do some initial butterflies and rotations
493        let [sum12, diff109] = AvxVector::column_butterfly2([input12, input109]);
494        let [sum34, diff87] = AvxVector::column_butterfly2([input34, input87]);
495        let [sum55, diff66] = AvxVector::column_butterfly2([input55, input66]);
496
497        let rotation = AvxVector::make_rotation90(FftDirection::Inverse);
498        let rotated109 = AvxVector::rotate90(diff109, rotation);
499        let rotated87 = AvxVector::rotate90(diff87, rotation);
500        let rotated66 = AvxVector::rotate90(diff66, rotation);
501
502        // arrange the data into the format to apply twiddles
503        let [mid110, mid29] = AvxVector::unpack_complex([sum12, rotated109]);
504        let [mid38, mid47] = AvxVector::unpack_complex([sum34, rotated87]);
505        let mid56 = AvxVector::unpacklo_complex([sum55, rotated66]);
506
507        // to compute the first output, compute the sum of all elements. mid110[0], mid29[0], mid38[0], mid47 already have the sum of 1+10, 2+9 and so on, so if we add them, we'll get the sum of everything
508        let mid12910 = AvxVector::add(mid110.lo(), mid29.lo());
509        let mid3478 = AvxVector::add(mid38.lo(), mid47.lo());
510        let output0_left = AvxVector::add(input0, mid56.lo());
511        let output0_right = AvxVector::add(mid12910, mid3478);
512        let output0 = AvxVector::add(output0_left, output0_right);
513        buffer.store_partial1_complex(output0, 0);
514
515        // we need to add the first input to each of our 5 twiddles values -- but only the first complex element of each vector. so just use zero for the other element
516        let zero = _mm_setzero_pd();
517        let input0 = AvxVector256::merge(input0, zero);
518
519        // apply twiddle factors
520        let twiddled110 = AvxVector::fmadd(mid110, self.twiddles[0], input0);
521        let twiddled38 = AvxVector::fmadd(mid110, self.twiddles[2], input0);
522        let twiddled29 = AvxVector::fmadd(mid110, self.twiddles[1], input0);
523        let twiddled47 = AvxVector::fmadd(mid110, self.twiddles[3], input0);
524        let twiddled56 = AvxVector::fmadd(mid110, self.twiddles[4], input0);
525
526        let twiddled110 = AvxVector::fmadd(mid29, self.twiddles[1], twiddled110);
527        let twiddled38 = AvxVector::fmadd(mid29, self.twiddles[5], twiddled38);
528        let twiddled29 = AvxVector::fmadd(mid29, self.twiddles[3], twiddled29);
529        let twiddled47 = AvxVector::fmadd(mid29, self.twiddles[7], twiddled47);
530        let twiddled56 = AvxVector::fmadd(mid29, self.twiddles[9], twiddled56);
531
532        let twiddled110 = AvxVector::fmadd(mid38, self.twiddles[2], twiddled110);
533        let twiddled38 = AvxVector::fmadd(mid38, self.twiddles[8], twiddled38);
534        let twiddled29 = AvxVector::fmadd(mid38, self.twiddles[5], twiddled29);
535        let twiddled47 = AvxVector::fmadd(mid38, self.twiddles[0], twiddled47);
536        let twiddled56 = AvxVector::fmadd(mid38, self.twiddles[3], twiddled56);
537
538        let twiddled110 = AvxVector::fmadd(mid47, self.twiddles[3], twiddled110);
539        let twiddled38 = AvxVector::fmadd(mid47, self.twiddles[0], twiddled38);
540        let twiddled29 = AvxVector::fmadd(mid47, self.twiddles[7], twiddled29);
541        let twiddled47 = AvxVector::fmadd(mid47, self.twiddles[4], twiddled47);
542        let twiddled56 = AvxVector::fmadd(mid47, self.twiddles[8], twiddled56);
543
544        let twiddled110 = AvxVector::fmadd(mid56, self.twiddles[4], twiddled110);
545        let twiddled38 = AvxVector::fmadd(mid56, self.twiddles[3], twiddled38);
546        let twiddled29 = AvxVector::fmadd(mid56, self.twiddles[9], twiddled29);
547        let twiddled47 = AvxVector::fmadd(mid56, self.twiddles[8], twiddled47);
548        let twiddled56 = AvxVector::fmadd(mid56, self.twiddles[2], twiddled56);
549
550        // unpack the data for the last butterfly 2
551        let [twiddled12, twiddled109] = AvxVector::unpack_complex([twiddled110, twiddled29]);
552        let [twiddled34, twiddled87] = AvxVector::unpack_complex([twiddled38, twiddled47]);
553        let [twiddled55, twiddled66] = AvxVector::unpack_complex([twiddled56, twiddled56]);
554
555        let [output12, output109] = AvxVector::column_butterfly2([twiddled12, twiddled109]);
556        let [output34, output87] = AvxVector::column_butterfly2([twiddled34, twiddled87]);
557        let [output55, output66] = AvxVector::column_butterfly2([twiddled55, twiddled66]);
558        let output78 = AvxVector::reverse_complex_elements(output87);
559        let output910 = AvxVector::reverse_complex_elements(output109);
560
561        buffer.store_complex(output12, 1);
562        buffer.store_complex(output34, 3);
563        buffer.store_partial1_complex(output55.lo(), 5);
564        buffer.store_partial1_complex(output66.lo(), 6);
565        buffer.store_complex(output78, 7);
566        buffer.store_complex(output910, 9);
567    }
568}
569
570pub struct Butterfly8Avx64<T> {
571    twiddles: [__m256d; 2],
572    twiddles_butterfly4: Rotation90<__m256d>,
573    direction: FftDirection,
574    _phantom_t: std::marker::PhantomData<T>,
575}
576boilerplate_fft_simd_butterfly!(Butterfly8Avx64, 8);
577impl Butterfly8Avx64<f64> {
578    #[target_feature(enable = "avx")]
579    unsafe fn new_with_avx(direction: FftDirection) -> Self {
580        Self {
581            twiddles: gen_butterfly_twiddles_interleaved_columns!(2, 4, 0, direction),
582            twiddles_butterfly4: AvxVector::make_rotation90(direction),
583            direction,
584            _phantom_t: PhantomData,
585        }
586    }
587}
588impl<T> Butterfly8Avx64<T> {
589    #[target_feature(enable = "avx", enable = "fma")]
590    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
591        let row0 = buffer.load_complex(0);
592        let row1 = buffer.load_complex(2);
593        let row2 = buffer.load_complex(4);
594        let row3 = buffer.load_complex(6);
595
596        // Do our butterfly 2's down the columns of a 4x2 array
597        let [mid0, mid2] = AvxVector::column_butterfly2([row0, row2]);
598        let [mid1, mid3] = AvxVector::column_butterfly2([row1, row3]);
599
600        let mid2_twiddled = AvxVector::mul_complex(mid2, self.twiddles[0]);
601        let mid3_twiddled = AvxVector::mul_complex(mid3, self.twiddles[1]);
602
603        // transpose to a 2x4 array
604        let transposed =
605            avx64_utils::transpose_4x2_to_2x4_f64([mid0, mid2_twiddled], [mid1, mid3_twiddled]);
606
607        // butterfly 4's down the transposed array
608        let output_rows = AvxVector::column_butterfly4(transposed, self.twiddles_butterfly4);
609
610        buffer.store_complex(output_rows[0], 0);
611        buffer.store_complex(output_rows[1], 2);
612        buffer.store_complex(output_rows[2], 4);
613        buffer.store_complex(output_rows[3], 6);
614    }
615}
616
617pub struct Butterfly9Avx64<T> {
618    twiddles: [__m256d; 2],
619    twiddles_butterfly3: __m256d,
620    direction: FftDirection,
621    _phantom_t: std::marker::PhantomData<T>,
622}
623boilerplate_fft_simd_butterfly!(Butterfly9Avx64, 9);
624impl Butterfly9Avx64<f64> {
625    #[target_feature(enable = "avx")]
626    unsafe fn new_with_avx(direction: FftDirection) -> Self {
627        Self {
628            twiddles: gen_butterfly_twiddles_interleaved_columns!(3, 3, 1, direction),
629            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
630            direction,
631            _phantom_t: PhantomData,
632        }
633    }
634}
635impl<T> Butterfly9Avx64<T> {
636    #[target_feature(enable = "avx", enable = "fma")]
637    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
638        // we're going to load our input as a 3x3 array. We have to load 3 columns, which is a little awkward
639        // We can reduce the number of multiplies we do if we load the first column as half-width and the second column as full.
640        let mut rows0 = [AvxVector::zero(); 3];
641        let mut rows1 = [AvxVector::zero(); 3];
642
643        for r in 0..3 {
644            rows0[r] = buffer.load_partial1_complex(3 * r);
645            rows1[r] = buffer.load_complex(3 * r + 1);
646        }
647
648        // do butterfly 3's down the columns
649        let mid0 = AvxVector::column_butterfly3(rows0, self.twiddles_butterfly3.lo());
650        let mut mid1 = AvxVector::column_butterfly3(rows1, self.twiddles_butterfly3);
651
652        // apply twiddle factors
653        for n in 1..3 {
654            mid1[n] = AvxVector::mul_complex(mid1[n], self.twiddles[n - 1]);
655        }
656
657        // transpose our 3x3 array
658        let (transposed0, transposed1) = avx64_utils::transpose_3x3_f64(mid0, mid1);
659
660        // apply butterfly 3's down the columns
661        let output0 = AvxVector::column_butterfly3(transposed0, self.twiddles_butterfly3.lo());
662        let output1 = AvxVector::column_butterfly3(transposed1, self.twiddles_butterfly3);
663
664        for r in 0..3 {
665            buffer.store_partial1_complex(output0[r], 3 * r);
666            buffer.store_complex(output1[r], 3 * r + 1);
667        }
668    }
669}
670
671pub struct Butterfly12Avx64<T> {
672    twiddles: [__m256d; 3],
673    twiddles_butterfly3: __m256d,
674    twiddles_butterfly4: Rotation90<__m256d>,
675    direction: FftDirection,
676    _phantom_t: std::marker::PhantomData<T>,
677}
678boilerplate_fft_simd_butterfly!(Butterfly12Avx64, 12);
679impl Butterfly12Avx64<f64> {
680    #[target_feature(enable = "avx")]
681    unsafe fn new_with_avx(direction: FftDirection) -> Self {
682        Self {
683            twiddles: gen_butterfly_twiddles_interleaved_columns!(4, 3, 1, direction),
684            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
685            twiddles_butterfly4: AvxVector::make_rotation90(direction),
686            direction,
687            _phantom_t: PhantomData,
688        }
689    }
690}
691impl<T> Butterfly12Avx64<T> {
692    #[target_feature(enable = "avx", enable = "fma")]
693    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
694        // we're going to load our input as a 3x4 array. We have to load 3 columns, which is a little awkward
695        // We can reduce the number of multiplies we do if we load the first column as half-width and the second column as full.
696        let mut rows0 = [AvxVector::zero(); 4];
697        let mut rows1 = [AvxVector::zero(); 4];
698
699        for n in 0..4 {
700            rows0[n] = buffer.load_partial1_complex(n * 3);
701            rows1[n] = buffer.load_complex(n * 3 + 1);
702        }
703
704        // do butterfly 4's down the columns
705        let mid0 = AvxVector::column_butterfly4(rows0, self.twiddles_butterfly4.lo());
706        let mut mid1 = AvxVector::column_butterfly4(rows1, self.twiddles_butterfly4);
707
708        // apply twiddle factors
709        for n in 1..4 {
710            mid1[n] = AvxVector::mul_complex(mid1[n], self.twiddles[n - 1]);
711        }
712
713        // transpose our 3x4 array to a 4x3 array
714        let (transposed0, transposed1) = avx64_utils::transpose_3x4_to_4x3_f64(mid0, mid1);
715
716        // apply butterfly 3's down the columns
717        let output0 = AvxVector::column_butterfly3(transposed0, self.twiddles_butterfly3);
718        let output1 = AvxVector::column_butterfly3(transposed1, self.twiddles_butterfly3);
719
720        for r in 0..3 {
721            buffer.store_complex(output0[r], 4 * r);
722            buffer.store_complex(output1[r], 4 * r + 2);
723        }
724    }
725}
726
727pub struct Butterfly16Avx64<T> {
728    twiddles: [__m256d; 6],
729    twiddles_butterfly4: Rotation90<__m256d>,
730    direction: FftDirection,
731    _phantom_t: std::marker::PhantomData<T>,
732}
733boilerplate_fft_simd_butterfly!(Butterfly16Avx64, 16);
734impl Butterfly16Avx64<f64> {
735    #[target_feature(enable = "avx")]
736    unsafe fn new_with_avx(direction: FftDirection) -> Self {
737        Self {
738            twiddles: gen_butterfly_twiddles_interleaved_columns!(4, 4, 0, direction),
739            twiddles_butterfly4: AvxVector::make_rotation90(direction),
740            direction,
741            _phantom_t: PhantomData,
742        }
743    }
744}
745impl<T> Butterfly16Avx64<T> {
746    #[target_feature(enable = "avx", enable = "fma")]
747    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
748        let mut rows0 = [AvxVector::zero(); 4];
749        let mut rows1 = [AvxVector::zero(); 4];
750        for r in 0..4 {
751            rows0[r] = buffer.load_complex(4 * r);
752            rows1[r] = buffer.load_complex(4 * r + 2);
753        }
754
755        // We're going to treat our input as a 4x4 2d array. First, do 4 butterfly 4's down the columns of that array.
756        let mut mid0 = AvxVector::column_butterfly4(rows0, self.twiddles_butterfly4);
757        let mut mid1 = AvxVector::column_butterfly4(rows1, self.twiddles_butterfly4);
758
759        // apply twiddle factors
760        for r in 1..4 {
761            mid0[r] = AvxVector::mul_complex(mid0[r], self.twiddles[2 * r - 2]);
762            mid1[r] = AvxVector::mul_complex(mid1[r], self.twiddles[2 * r - 1]);
763        }
764
765        // Transpose our 4x4 array
766        let (transposed0, transposed1) = avx64_utils::transpose_4x4_f64(mid0, mid1);
767
768        // Butterfly 4's down columns of the transposed array
769        let output0 = AvxVector::column_butterfly4(transposed0, self.twiddles_butterfly4);
770        let output1 = AvxVector::column_butterfly4(transposed1, self.twiddles_butterfly4);
771
772        for r in 0..4 {
773            buffer.store_complex(output0[r], 4 * r);
774            buffer.store_complex(output1[r], 4 * r + 2);
775        }
776    }
777}
778
779pub struct Butterfly18Avx64<T> {
780    twiddles: [__m256d; 5],
781    twiddles_butterfly3: __m256d,
782    direction: FftDirection,
783    _phantom_t: std::marker::PhantomData<T>,
784}
785boilerplate_fft_simd_butterfly!(Butterfly18Avx64, 18);
786impl Butterfly18Avx64<f64> {
787    #[target_feature(enable = "avx")]
788    unsafe fn new_with_avx(direction: FftDirection) -> Self {
789        Self {
790            twiddles: gen_butterfly_twiddles_interleaved_columns!(6, 3, 1, direction),
791            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
792            direction,
793            _phantom_t: PhantomData,
794        }
795    }
796}
797impl<T> Butterfly18Avx64<T> {
798    #[target_feature(enable = "avx", enable = "fma")]
799    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
800        // we're going to load our input as a 3x6 array. We have to load 3 columns, which is a little awkward
801        // We can reduce the number of multiplies we do if we load the first column as half-width and the second column as full.
802        let mut rows0 = [AvxVector::zero(); 6];
803        let mut rows1 = [AvxVector::zero(); 6];
804        for n in 0..6 {
805            rows0[n] = buffer.load_partial1_complex(n * 3);
806            rows1[n] = buffer.load_complex(n * 3 + 1);
807        }
808
809        // do butterfly 6's down the columns
810        let mid0 = AvxVector128::column_butterfly6(rows0, self.twiddles_butterfly3);
811        let mut mid1 = AvxVector256::column_butterfly6(rows1, self.twiddles_butterfly3);
812
813        // apply twiddle factors
814        for n in 1..6 {
815            mid1[n] = AvxVector::mul_complex(mid1[n], self.twiddles[n - 1]);
816        }
817
818        // transpose our 3x6 array to a 6x3 array
819        let (transposed0, transposed1, transposed2) =
820            avx64_utils::transpose_3x6_to_6x3_f64(mid0, mid1);
821
822        // apply butterfly 3's down the columns
823        let output0 = AvxVector::column_butterfly3(transposed0, self.twiddles_butterfly3);
824        let output1 = AvxVector::column_butterfly3(transposed1, self.twiddles_butterfly3);
825        let output2 = AvxVector::column_butterfly3(transposed2, self.twiddles_butterfly3);
826
827        for r in 0..3 {
828            buffer.store_complex(output0[r], 6 * r);
829            buffer.store_complex(output1[r], 6 * r + 2);
830            buffer.store_complex(output2[r], 6 * r + 4);
831        }
832    }
833}
834
835pub struct Butterfly24Avx64<T> {
836    twiddles: [__m256d; 9],
837    twiddles_butterfly3: __m256d,
838    twiddles_butterfly4: Rotation90<__m256d>,
839    direction: FftDirection,
840    _phantom_t: std::marker::PhantomData<T>,
841}
842boilerplate_fft_simd_butterfly!(Butterfly24Avx64, 24);
843impl Butterfly24Avx64<f64> {
844    #[target_feature(enable = "avx")]
845    unsafe fn new_with_avx(direction: FftDirection) -> Self {
846        Self {
847            twiddles: gen_butterfly_twiddles_interleaved_columns!(4, 6, 0, direction),
848            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
849            twiddles_butterfly4: AvxVector::make_rotation90(direction),
850            direction,
851            _phantom_t: PhantomData,
852        }
853    }
854}
855impl<T> Butterfly24Avx64<T> {
856    #[target_feature(enable = "avx", enable = "fma")]
857    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
858        let mut rows0 = [AvxVector::zero(); 4];
859        let mut rows1 = [AvxVector::zero(); 4];
860        let mut rows2 = [AvxVector::zero(); 4];
861        for r in 0..4 {
862            rows0[r] = buffer.load_complex(6 * r);
863            rows1[r] = buffer.load_complex(6 * r + 2);
864            rows2[r] = buffer.load_complex(6 * r + 4);
865        }
866
867        // We're going to treat our input as a 6x4 2d array. First, do 6 butterfly 4's down the columns of that array.
868        let mut mid0 = AvxVector::column_butterfly4(rows0, self.twiddles_butterfly4);
869        let mut mid1 = AvxVector::column_butterfly4(rows1, self.twiddles_butterfly4);
870        let mut mid2 = AvxVector::column_butterfly4(rows2, self.twiddles_butterfly4);
871
872        // apply twiddle factors
873        for r in 1..4 {
874            mid0[r] = AvxVector::mul_complex(mid0[r], self.twiddles[3 * r - 3]);
875            mid1[r] = AvxVector::mul_complex(mid1[r], self.twiddles[3 * r - 2]);
876            mid2[r] = AvxVector::mul_complex(mid2[r], self.twiddles[3 * r - 1]);
877        }
878
879        // Transpose our 6x4 array
880        let (transposed0, transposed1) = avx64_utils::transpose_6x4_to_4x6_f64(mid0, mid1, mid2);
881
882        // Butterfly 6's down columns of the transposed array
883        let output0 = AvxVector256::column_butterfly6(transposed0, self.twiddles_butterfly3);
884        let output1 = AvxVector256::column_butterfly6(transposed1, self.twiddles_butterfly3);
885
886        for r in 0..6 {
887            buffer.store_complex(output0[r], 4 * r);
888            buffer.store_complex(output1[r], 4 * r + 2);
889        }
890    }
891}
892
893pub struct Butterfly27Avx64<T> {
894    twiddles: [__m256d; 8],
895    twiddles_butterfly9: [__m256d; 3],
896    twiddles_butterfly9_lo: [__m256d; 2],
897    twiddles_butterfly3: __m256d,
898    direction: FftDirection,
899    _phantom_t: std::marker::PhantomData<T>,
900}
901boilerplate_fft_simd_butterfly!(Butterfly27Avx64, 27);
902impl Butterfly27Avx64<f64> {
903    #[target_feature(enable = "avx")]
904    unsafe fn new_with_avx(direction: FftDirection) -> Self {
905        let twiddle1 = __m128d::broadcast_twiddle(1, 9, direction);
906        let twiddle2 = __m128d::broadcast_twiddle(2, 9, direction);
907        let twiddle4 = __m128d::broadcast_twiddle(4, 9, direction);
908
909        Self {
910            twiddles: gen_butterfly_twiddles_interleaved_columns!(3, 9, 1, direction),
911            twiddles_butterfly9: [
912                AvxVector::broadcast_twiddle(1, 9, direction),
913                AvxVector::broadcast_twiddle(2, 9, direction),
914                AvxVector::broadcast_twiddle(4, 9, direction),
915            ],
916            twiddles_butterfly9_lo: [
917                AvxVector256::merge(twiddle1, twiddle2),
918                AvxVector256::merge(twiddle2, twiddle4),
919            ],
920            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
921            direction,
922            _phantom_t: PhantomData,
923        }
924    }
925}
926impl<T> Butterfly27Avx64<T> {
927    #[target_feature(enable = "avx", enable = "fma")]
928    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
929        // we're going to load our input as a 9x3 array. We have to load 9 columns, which is a little awkward
930        // We can reduce the number of multiplies we do if we load the first column as half-width and the remaining 4 sets of vectors as full.
931        // We can't fit the whole problem into AVX registers at once, so we'll have to spill some things.
932        // By computing chunks of the problem and then not referencing any of it for a while, we're making it easy for the compiler to decide what to spill
933        let mut rows0 = [AvxVector::zero(); 3];
934        for n in 0..3 {
935            rows0[n] = buffer.load_partial1_complex(n * 9);
936        }
937        let mid0 = AvxVector::column_butterfly3(rows0, self.twiddles_butterfly3.lo());
938
939        // First chunk is done and can be spilled, do 2 more chunks
940        let mut rows1 = [AvxVector::zero(); 3];
941        let mut rows2 = [AvxVector::zero(); 3];
942        for n in 0..3 {
943            rows1[n] = buffer.load_complex(n * 9 + 1);
944            rows2[n] = buffer.load_complex(n * 9 + 3);
945        }
946        let mut mid1 = AvxVector::column_butterfly3(rows1, self.twiddles_butterfly3);
947        let mut mid2 = AvxVector::column_butterfly3(rows2, self.twiddles_butterfly3);
948        for r in 1..3 {
949            mid1[r] = AvxVector::mul_complex(mid1[r], self.twiddles[4 * r - 4]);
950            mid2[r] = AvxVector::mul_complex(mid2[r], self.twiddles[4 * r - 3]);
951        }
952
953        // First 3 chunks are done and can be spilled, do the final 2 chunks
954        let mut rows3 = [AvxVector::zero(); 3];
955        let mut rows4 = [AvxVector::zero(); 3];
956        for n in 0..3 {
957            rows3[n] = buffer.load_complex(n * 9 + 5);
958            rows4[n] = buffer.load_complex(n * 9 + 7);
959        }
960        let mut mid3 = AvxVector::column_butterfly3(rows3, self.twiddles_butterfly3);
961        let mut mid4 = AvxVector::column_butterfly3(rows4, self.twiddles_butterfly3);
962        for r in 1..3 {
963            mid3[r] = AvxVector::mul_complex(mid3[r], self.twiddles[4 * r - 2]);
964            mid4[r] = AvxVector::mul_complex(mid4[r], self.twiddles[4 * r - 1]);
965        }
966
967        // transpose our 9x3 array to a 3x9 array
968        let (transposed0, transposed1) =
969            avx64_utils::transpose_9x3_to_3x9_f64(mid0, mid1, mid2, mid3, mid4);
970
971        // apply butterfly 9's down the columns. Again, do the work in chunks to make it easier for the compiler to spill
972        let output0 = AvxVector128::column_butterfly9(
973            transposed0,
974            self.twiddles_butterfly9_lo,
975            self.twiddles_butterfly3,
976        );
977        for r in 0..3 {
978            buffer.store_partial1_complex(output0[r * 3], 9 * r);
979            buffer.store_partial1_complex(output0[r * 3 + 1], 9 * r + 3);
980            buffer.store_partial1_complex(output0[r * 3 + 2], 9 * r + 6);
981        }
982
983        let output1 = AvxVector256::column_butterfly9(
984            transposed1,
985            self.twiddles_butterfly9,
986            self.twiddles_butterfly3,
987        );
988        for r in 0..3 {
989            buffer.store_complex(output1[r * 3], 9 * r + 1);
990            buffer.store_complex(output1[r * 3 + 1], 9 * r + 4);
991            buffer.store_complex(output1[r * 3 + 2], 9 * r + 7);
992        }
993    }
994}
995
996pub struct Butterfly32Avx64<T> {
997    twiddles: [__m256d; 12],
998    twiddles_butterfly4: Rotation90<__m256d>,
999    direction: FftDirection,
1000    _phantom_t: std::marker::PhantomData<T>,
1001}
1002boilerplate_fft_simd_butterfly!(Butterfly32Avx64, 32);
1003impl Butterfly32Avx64<f64> {
1004    #[target_feature(enable = "avx")]
1005    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1006        Self {
1007            twiddles: gen_butterfly_twiddles_interleaved_columns!(4, 8, 0, direction),
1008            twiddles_butterfly4: AvxVector::make_rotation90(direction),
1009            direction,
1010            _phantom_t: PhantomData,
1011        }
1012    }
1013}
1014impl<T> Butterfly32Avx64<T> {
1015    #[target_feature(enable = "avx", enable = "fma")]
1016    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
1017        // We're going to treat our input as a 8x4 2d array. First, do 8 butterfly 4's down the columns of that array.
1018        // We can't fit the whole problem into AVX registers at once, so we'll have to spill some things.
1019        // By computing half of the problem and then not referencing any of it for a while, we're making it easy for the compiler to decide what to spill
1020        let mut rows0 = [AvxVector::zero(); 4];
1021        let mut rows1 = [AvxVector::zero(); 4];
1022        for r in 0..4 {
1023            rows0[r] = buffer.load_complex(8 * r);
1024            rows1[r] = buffer.load_complex(8 * r + 2);
1025        }
1026        let mut mid0 = AvxVector::column_butterfly4(rows0, self.twiddles_butterfly4);
1027        let mut mid1 = AvxVector::column_butterfly4(rows1, self.twiddles_butterfly4);
1028        for r in 1..4 {
1029            mid0[r] = AvxVector::mul_complex(mid0[r], self.twiddles[4 * r - 4]);
1030            mid1[r] = AvxVector::mul_complex(mid1[r], self.twiddles[4 * r - 3]);
1031        }
1032
1033        // One half is done, so the compiler can spill everything above this. Now do the other set of columns
1034        let mut rows2 = [AvxVector::zero(); 4];
1035        let mut rows3 = [AvxVector::zero(); 4];
1036        for r in 0..4 {
1037            rows2[r] = buffer.load_complex(8 * r + 4);
1038            rows3[r] = buffer.load_complex(8 * r + 6);
1039        }
1040        let mut mid2 = AvxVector::column_butterfly4(rows2, self.twiddles_butterfly4);
1041        let mut mid3 = AvxVector::column_butterfly4(rows3, self.twiddles_butterfly4);
1042        for r in 1..4 {
1043            mid2[r] = AvxVector::mul_complex(mid2[r], self.twiddles[4 * r - 2]);
1044            mid3[r] = AvxVector::mul_complex(mid3[r], self.twiddles[4 * r - 1]);
1045        }
1046
1047        // Transpose our 8x4 array to a 4x8 array
1048        let (transposed0, transposed1) =
1049            avx64_utils::transpose_8x4_to_4x8_f64(mid0, mid1, mid2, mid3);
1050
1051        // Do 4 butterfly 8's down columns of the transposed array
1052        // Same thing as above - Do the half of the butterfly 8's separately to give the compiler a better hint about what to spill
1053        let output0 = AvxVector::column_butterfly8(transposed0, self.twiddles_butterfly4);
1054        for r in 0..8 {
1055            buffer.store_complex(output0[r], 4 * r);
1056        }
1057        let output1 = AvxVector::column_butterfly8(transposed1, self.twiddles_butterfly4);
1058        for r in 0..8 {
1059            buffer.store_complex(output1[r], 4 * r + 2);
1060        }
1061    }
1062}
1063
1064pub struct Butterfly36Avx64<T> {
1065    twiddles: [__m256d; 15],
1066    twiddles_butterfly3: __m256d,
1067    direction: FftDirection,
1068    _phantom_t: std::marker::PhantomData<T>,
1069}
1070boilerplate_fft_simd_butterfly!(Butterfly36Avx64, 36);
1071impl Butterfly36Avx64<f64> {
1072    #[target_feature(enable = "avx")]
1073    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1074        Self {
1075            twiddles: gen_butterfly_twiddles_separated_columns!(6, 6, 0, direction),
1076            twiddles_butterfly3: AvxVector::broadcast_twiddle(1, 3, direction),
1077            direction,
1078            _phantom_t: PhantomData,
1079        }
1080    }
1081}
1082impl<T> Butterfly36Avx64<T> {
1083    #[target_feature(enable = "avx", enable = "fma")]
1084    unsafe fn perform_fft_f64(&self, mut buffer: impl AvxArrayMut<f64>) {
1085        // we're going to load our input as a 6x6 array
1086        // We can't fit the whole problem into AVX registers at once, so we'll have to spill some things.
1087        // By computing chunks of the problem and then not referencing any of it for a while, we're making it easy for the compiler to decide what to spill
1088        let mut rows0 = [AvxVector::zero(); 6];
1089        for n in 0..6 {
1090            rows0[n] = buffer.load_complex(n * 6);
1091        }
1092        let mut mid0 = AvxVector256::column_butterfly6(rows0, self.twiddles_butterfly3);
1093        for r in 1..6 {
1094            mid0[r] = AvxVector::mul_complex(mid0[r], self.twiddles[r - 1]);
1095        }
1096
1097        // we're going to load our input as a 6x6 array
1098        let mut rows1 = [AvxVector::zero(); 6];
1099        for n in 0..6 {
1100            rows1[n] = buffer.load_complex(n * 6 + 2);
1101        }
1102        let mut mid1 = AvxVector256::column_butterfly6(rows1, self.twiddles_butterfly3);
1103        for r in 1..6 {
1104            mid1[r] = AvxVector::mul_complex(mid1[r], self.twiddles[r + 4]);
1105        }
1106
1107        // we're going to load our input as a 6x6 array
1108        let mut rows2 = [AvxVector::zero(); 6];
1109        for n in 0..6 {
1110            rows2[n] = buffer.load_complex(n * 6 + 4);
1111        }
1112        let mut mid2 = AvxVector256::column_butterfly6(rows2, self.twiddles_butterfly3);
1113        for r in 1..6 {
1114            mid2[r] = AvxVector::mul_complex(mid2[r], self.twiddles[r + 9]);
1115        }
1116
1117        // Transpose our 6x6 array
1118        let (transposed0, transposed1, transposed2) =
1119            avx64_utils::transpose_6x6_f64(mid0, mid1, mid2);
1120
1121        // Apply butterfly 6's down the columns.  Again, do the work in chunks to make it easier for the compiler to spill
1122        let output0 = AvxVector256::column_butterfly6(transposed0, self.twiddles_butterfly3);
1123        for r in 0..3 {
1124            buffer.store_complex(output0[r * 2], 12 * r);
1125            buffer.store_complex(output0[r * 2 + 1], 12 * r + 6);
1126        }
1127
1128        let output1 = AvxVector256::column_butterfly6(transposed1, self.twiddles_butterfly3);
1129        for r in 0..3 {
1130            buffer.store_complex(output1[r * 2], 12 * r + 2);
1131            buffer.store_complex(output1[r * 2 + 1], 12 * r + 8);
1132        }
1133
1134        let output2 = AvxVector256::column_butterfly6(transposed2, self.twiddles_butterfly3);
1135        for r in 0..3 {
1136            buffer.store_complex(output2[r * 2], 12 * r + 4);
1137            buffer.store_complex(output2[r * 2 + 1], 12 * r + 10);
1138        }
1139    }
1140}
1141
1142pub struct Butterfly64Avx64<T> {
1143    twiddles: [__m256d; 28],
1144    twiddles_butterfly4: Rotation90<__m256d>,
1145    direction: FftDirection,
1146    _phantom_t: std::marker::PhantomData<T>,
1147}
1148boilerplate_fft_simd_butterfly_with_scratch!(Butterfly64Avx64, 64);
1149impl Butterfly64Avx64<f64> {
1150    #[target_feature(enable = "avx")]
1151    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1152        Self {
1153            twiddles: gen_butterfly_twiddles_separated_columns!(8, 8, 0, direction),
1154            twiddles_butterfly4: AvxVector::make_rotation90(direction),
1155            direction,
1156            _phantom_t: PhantomData,
1157        }
1158    }
1159}
1160impl<T> Butterfly64Avx64<T> {
1161    #[target_feature(enable = "avx", enable = "fma")]
1162    unsafe fn column_butterflies_and_transpose(
1163        &self,
1164        input: &[Complex<f64>],
1165        mut output: &mut [Complex<f64>],
1166    ) {
1167        // A size-64 FFT is way too big to fit in registers, so instead we're going to compute it in two phases, storing in scratch in between.
1168
1169        // First phase is to treat this size-64 array like a 8x8 2D array, and do butterfly 8's down the columns
1170        // Then, apply twiddle factors, and finally transpose into the scratch space
1171
1172        // But again, we don't have enough registers to load it all at once, so only load one column of AVX vectors at a time
1173        for columnset in 0..4 {
1174            let mut rows = [AvxVector::zero(); 8];
1175            for r in 0..8 {
1176                rows[r] = input.load_complex(columnset * 2 + 8 * r);
1177            }
1178            // apply butterfly 8
1179            let mut mid = AvxVector::column_butterfly8(rows, self.twiddles_butterfly4);
1180
1181            // apply twiddle factors
1182            for r in 1..8 {
1183                mid[r] = AvxVector::mul_complex(mid[r], self.twiddles[r - 1 + 7 * columnset]);
1184            }
1185
1186            // transpose
1187            let transposed = AvxVector::transpose8_packed(mid);
1188
1189            // write out
1190            for i in 0..4 {
1191                output.store_complex(transposed[i * 2], columnset * 16 + i * 4);
1192                output.store_complex(transposed[i * 2 + 1], columnset * 16 + i * 4 + 2);
1193            }
1194        }
1195    }
1196
1197    #[target_feature(enable = "avx", enable = "fma")]
1198    unsafe fn row_butterflies(&self, mut buffer: impl AvxArrayMut<f64>) {
1199        // Second phase: Butterfly 8's down the columns of our transposed array.
1200        // Thankfully, during the first phase, we set everything up so that all we have to do here is compute the size-8 FFT columns and write them back out where we got them
1201        for columnset in 0usize..4 {
1202            let mut rows = [AvxVector::zero(); 8];
1203            for r in 0..8 {
1204                rows[r] = buffer.load_complex(columnset * 2 + 8 * r);
1205            }
1206            let mid = AvxVector::column_butterfly8(rows, self.twiddles_butterfly4);
1207            for r in 0..8 {
1208                buffer.store_complex(mid[r], columnset * 2 + 8 * r);
1209            }
1210        }
1211    }
1212}
1213
1214pub struct Butterfly128Avx64<T> {
1215    twiddles: [__m256d; 56],
1216    twiddles_butterfly16: [__m256d; 2],
1217    twiddles_butterfly4: Rotation90<__m256d>,
1218    direction: FftDirection,
1219    _phantom_t: std::marker::PhantomData<T>,
1220}
1221boilerplate_fft_simd_butterfly_with_scratch!(Butterfly128Avx64, 128);
1222impl Butterfly128Avx64<f64> {
1223    #[target_feature(enable = "avx")]
1224    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1225        Self {
1226            twiddles: gen_butterfly_twiddles_separated_columns!(8, 16, 0, direction),
1227            twiddles_butterfly16: [
1228                AvxVector::broadcast_twiddle(1, 16, direction),
1229                AvxVector::broadcast_twiddle(3, 16, direction),
1230            ],
1231            twiddles_butterfly4: AvxVector::make_rotation90(direction),
1232            direction,
1233            _phantom_t: PhantomData,
1234        }
1235    }
1236}
1237impl<T> Butterfly128Avx64<T> {
1238    #[target_feature(enable = "avx", enable = "fma")]
1239    unsafe fn column_butterflies_and_transpose(
1240        &self,
1241        input: &[Complex<f64>],
1242        mut output: &mut [Complex<f64>],
1243    ) {
1244        // A size-128 FFT is way too big to fit in registers, so instead we're going to compute it in two phases, storing in scratch in between.
1245
1246        // First phase is to treat this size-128 array like a 16x8 2D array, and do butterfly 8's down the columns
1247        // Then, apply twiddle factors, and finally transpose into the scratch space
1248
1249        // But again, we don't have enough registers to load it all at once, so only load one column of AVX vectors at a time
1250        for columnset in 0..8 {
1251            let mut rows = [AvxVector::zero(); 8];
1252            for r in 0..8 {
1253                rows[r] = input.load_complex(columnset * 2 + 16 * r);
1254            }
1255            // apply butterfly 8
1256            let mut mid = AvxVector::column_butterfly8(rows, self.twiddles_butterfly4);
1257
1258            // apply twiddle factors
1259            for r in 1..8 {
1260                mid[r] = AvxVector::mul_complex(mid[r], self.twiddles[r - 1 + 7 * columnset]);
1261            }
1262
1263            // transpose
1264            let transposed = AvxVector::transpose8_packed(mid);
1265
1266            // write out
1267            for i in 0..4 {
1268                output.store_complex(transposed[i * 2], columnset * 16 + i * 4);
1269                output.store_complex(transposed[i * 2 + 1], columnset * 16 + i * 4 + 2);
1270            }
1271        }
1272    }
1273
1274    #[target_feature(enable = "avx", enable = "fma")]
1275    unsafe fn row_butterflies(&self, mut buffer: impl AvxArrayMut<f64>) {
1276        // Second phase: Butterfly 16's down the columns of our transposed array.
1277        // Thankfully, during the first phase, we set everything up so that all we have to do here is compute the size-16 FFT columns and write them back out where we got them
1278        // We're also using a customized butterfly16 function that is smarter about when it loads/stores data, to reduce register spilling
1279        for columnset in 0usize..4 {
1280            column_butterfly16_loadfn!(
1281                |index: usize| buffer.load_complex(columnset * 2 + index * 8),
1282                |data, index| buffer.store_complex(data, columnset * 2 + index * 8),
1283                self.twiddles_butterfly16,
1284                self.twiddles_butterfly4
1285            );
1286        }
1287    }
1288}
1289
1290pub struct Butterfly256Avx64<T> {
1291    twiddles: [__m256d; 112],
1292    twiddles_butterfly32: [__m256d; 6],
1293    twiddles_butterfly4: Rotation90<__m256d>,
1294    direction: FftDirection,
1295    _phantom_t: std::marker::PhantomData<T>,
1296}
1297boilerplate_fft_simd_butterfly_with_scratch!(Butterfly256Avx64, 256);
1298impl Butterfly256Avx64<f64> {
1299    #[target_feature(enable = "avx")]
1300    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1301        Self {
1302            twiddles: gen_butterfly_twiddles_separated_columns!(8, 32, 0, direction),
1303            twiddles_butterfly32: [
1304                AvxVector::broadcast_twiddle(1, 32, direction),
1305                AvxVector::broadcast_twiddle(2, 32, direction),
1306                AvxVector::broadcast_twiddle(3, 32, direction),
1307                AvxVector::broadcast_twiddle(5, 32, direction),
1308                AvxVector::broadcast_twiddle(6, 32, direction),
1309                AvxVector::broadcast_twiddle(7, 32, direction),
1310            ],
1311            twiddles_butterfly4: AvxVector::make_rotation90(direction),
1312            direction,
1313            _phantom_t: PhantomData,
1314        }
1315    }
1316}
1317impl<T> Butterfly256Avx64<T> {
1318    #[target_feature(enable = "avx", enable = "fma")]
1319    unsafe fn column_butterflies_and_transpose(
1320        &self,
1321        input: &[Complex<f64>],
1322        mut output: &mut [Complex<f64>],
1323    ) {
1324        // A size-256 FFT is way too big to fit in registers, so instead we're going to compute it in two phases, storing in scratch in between.
1325
1326        // First phase is to treeat this size-256 array like a 32x8 2D array, and do butterfly 8's down the columns
1327        // Then, apply twiddle factors, and finally transpose into the scratch space
1328
1329        // But again, we don't have enough registers to load it all at once, so only load one column of AVX vectors at a time
1330        for columnset in 0..16 {
1331            let mut rows = [AvxVector::zero(); 8];
1332            for r in 0..8 {
1333                rows[r] = input.load_complex(columnset * 2 + 32 * r);
1334            }
1335            // apply butterfly 8
1336            let mut mid = AvxVector::column_butterfly8(rows, self.twiddles_butterfly4);
1337
1338            // apply twiddle factors
1339            for r in 1..8 {
1340                mid[r] = AvxVector::mul_complex(mid[r], self.twiddles[r - 1 + 7 * columnset]);
1341            }
1342
1343            // transpose
1344            let transposed = AvxVector::transpose8_packed(mid);
1345
1346            // write out
1347            for i in 0..4 {
1348                output.store_complex(transposed[i * 2], columnset * 16 + i * 4);
1349                output.store_complex(transposed[i * 2 + 1], columnset * 16 + i * 4 + 2);
1350            }
1351        }
1352    }
1353
1354    #[target_feature(enable = "avx", enable = "fma")]
1355    unsafe fn row_butterflies(&self, mut buffer: impl AvxArrayMut<f64>) {
1356        // Second phase: Butterfly 32's down the columns of our transposed array.
1357        // Thankfully, during the first phase, we set everything up so that all we have to do here is compute the size-32 FFT columns and write them back out where we got them
1358        // We're also using a customized butterfly32 function that is smarter about when it loads/stores data, to reduce register spilling
1359        for columnset in 0usize..4 {
1360            column_butterfly32_loadfn!(
1361                |index: usize| buffer.load_complex(columnset * 2 + index * 8),
1362                |data, index| buffer.store_complex(data, columnset * 2 + index * 8),
1363                self.twiddles_butterfly32,
1364                self.twiddles_butterfly4
1365            );
1366        }
1367    }
1368}
1369
1370pub struct Butterfly512Avx64<T> {
1371    twiddles: [__m256d; 240],
1372    twiddles_butterfly32: [__m256d; 6],
1373    twiddles_butterfly16: [__m256d; 2],
1374    twiddles_butterfly4: Rotation90<__m256d>,
1375    direction: FftDirection,
1376    _phantom_t: std::marker::PhantomData<T>,
1377}
1378boilerplate_fft_simd_butterfly_with_scratch!(Butterfly512Avx64, 512);
1379impl Butterfly512Avx64<f64> {
1380    #[target_feature(enable = "avx")]
1381    unsafe fn new_with_avx(direction: FftDirection) -> Self {
1382        Self {
1383            twiddles: gen_butterfly_twiddles_separated_columns!(16, 32, 0, direction),
1384            twiddles_butterfly32: [
1385                AvxVector::broadcast_twiddle(1, 32, direction),
1386                AvxVector::broadcast_twiddle(2, 32, direction),
1387                AvxVector::broadcast_twiddle(3, 32, direction),
1388                AvxVector::broadcast_twiddle(5, 32, direction),
1389                AvxVector::broadcast_twiddle(6, 32, direction),
1390                AvxVector::broadcast_twiddle(7, 32, direction),
1391            ],
1392            twiddles_butterfly16: [
1393                AvxVector::broadcast_twiddle(1, 16, direction),
1394                AvxVector::broadcast_twiddle(3, 16, direction),
1395            ],
1396            twiddles_butterfly4: AvxVector::make_rotation90(direction),
1397            direction,
1398            _phantom_t: PhantomData,
1399        }
1400    }
1401}
1402impl<T> Butterfly512Avx64<T> {
1403    #[target_feature(enable = "avx", enable = "fma")]
1404    unsafe fn column_butterflies_and_transpose(
1405        &self,
1406        input: &[Complex<f64>],
1407        mut output: &mut [Complex<f64>],
1408    ) {
1409        // A size-512 FFT is way too big to fit in registers, so instead we're going to compute it in two phases, storing in scratch in between.
1410
1411        // First phase is to treat this size-512 array like a 32x16 2D array, and do butterfly 16's down the columns
1412        // Then, apply twiddle factors, and finally transpose into the scratch space
1413
1414        // But again, we don't have enough registers to load it all at once, so only load one column of AVX vectors at a time
1415        // We're also using a customized butterfly16 function that is smarter about when it loads/stores data, to reduce register spilling
1416        const TWIDDLES_PER_COLUMN: usize = 15;
1417        for (columnset, twiddle_chunk) in
1418            self.twiddles.chunks_exact(TWIDDLES_PER_COLUMN).enumerate()
1419        {
1420            // Sadly we have to use MaybeUninit here. If we init an array like normal with AvxVector::Zero(), the compiler can't seem to figure out that it can
1421            // eliminate the dead stores of zeroes to the stack. By using uninit here, we avoid those unnecessary writes
1422            let mut mid_uninit: [MaybeUninit<__m256d>; 16] = [MaybeUninit::<__m256d>::uninit(); 16];
1423
1424            column_butterfly16_loadfn!(
1425                |index: usize| input.load_complex(columnset * 2 + 32 * index),
1426                |data, index: usize| {
1427                    mid_uninit[index].as_mut_ptr().write(data);
1428                },
1429                self.twiddles_butterfly16,
1430                self.twiddles_butterfly4
1431            );
1432
1433            // Apply twiddle factors, transpose, and store. Traditionally we apply all the twiddle factors at once and then do all the transposes at once,
1434            // But our data is pushing the limit of what we can store in registers, so the idea here is to get the data out the door with as few spills to the stack as possible
1435            for chunk in 0..4 {
1436                let twiddled = [
1437                    if chunk > 0 {
1438                        AvxVector::mul_complex(
1439                            mid_uninit[4 * chunk].assume_init(),
1440                            twiddle_chunk[4 * chunk - 1],
1441                        )
1442                    } else {
1443                        mid_uninit[4 * chunk].assume_init()
1444                    },
1445                    AvxVector::mul_complex(
1446                        mid_uninit[4 * chunk + 1].assume_init(),
1447                        twiddle_chunk[4 * chunk],
1448                    ),
1449                    AvxVector::mul_complex(
1450                        mid_uninit[4 * chunk + 2].assume_init(),
1451                        twiddle_chunk[4 * chunk + 1],
1452                    ),
1453                    AvxVector::mul_complex(
1454                        mid_uninit[4 * chunk + 3].assume_init(),
1455                        twiddle_chunk[4 * chunk + 2],
1456                    ),
1457                ];
1458
1459                let transposed = AvxVector::transpose4_packed(twiddled);
1460
1461                output.store_complex(transposed[0], columnset * 32 + 4 * chunk);
1462                output.store_complex(transposed[1], columnset * 32 + 4 * chunk + 2);
1463                output.store_complex(transposed[2], columnset * 32 + 4 * chunk + 16);
1464                output.store_complex(transposed[3], columnset * 32 + 4 * chunk + 18);
1465            }
1466        }
1467    }
1468
1469    #[target_feature(enable = "avx", enable = "fma")]
1470    unsafe fn row_butterflies(&self, mut buffer: impl AvxArrayMut<f64>) {
1471        // Second phase: Butterfly 32's down the columns of our transposed array.
1472        // Thankfully, during the first phase, we set everything up so that all we have to do here is compute the size-32 FFT columns and write them back out where we got them
1473        // We're also using a customized butterfly32 function that is smarter about when it loads/stores data, to reduce register spilling
1474        for columnset in 0usize..8 {
1475            column_butterfly32_loadfn!(
1476                |index: usize| buffer.load_complex(columnset * 2 + index * 16),
1477                |data, index| buffer.store_complex(data, columnset * 2 + index * 16),
1478                self.twiddles_butterfly32,
1479                self.twiddles_butterfly4
1480            );
1481        }
1482    }
1483}
1484
1485#[cfg(test)]
1486mod unit_tests {
1487    use super::*;
1488    use crate::test_utils::check_fft_algorithm;
1489
1490    macro_rules! test_avx_butterfly {
1491        ($test_name:ident, $struct_name:ident, $size:expr) => (
1492            #[test]
1493            fn $test_name() {
1494                let butterfly = $struct_name::new(FftDirection::Forward).expect("Can't run test because this machine doesn't have the required instruction sets");
1495                check_fft_algorithm(&butterfly as &dyn Fft<f64>, $size, FftDirection::Forward);
1496
1497                let butterfly_inverse = $struct_name::new(FftDirection::Inverse).expect("Can't run test because this machine doesn't have the required instruction sets");
1498                check_fft_algorithm(&butterfly_inverse as &dyn Fft<f64>, $size, FftDirection::Inverse);
1499            }
1500        )
1501    }
1502
1503    test_avx_butterfly!(test_avx_butterfly5_f64, Butterfly5Avx64, 5);
1504    test_avx_butterfly!(test_avx_butterfly7_f64, Butterfly7Avx64, 7);
1505    test_avx_butterfly!(test_avx_mixedradix8_f64, Butterfly8Avx64, 8);
1506    test_avx_butterfly!(test_avx_mixedradix9_f64, Butterfly9Avx64, 9);
1507    test_avx_butterfly!(test_avx_mixedradix11_f64, Butterfly11Avx64, 11);
1508    test_avx_butterfly!(test_avx_mixedradix12_f64, Butterfly12Avx64, 12);
1509    test_avx_butterfly!(test_avx_mixedradix16_f64, Butterfly16Avx64, 16);
1510    test_avx_butterfly!(test_avx_mixedradix18_f64, Butterfly18Avx64, 18);
1511    test_avx_butterfly!(test_avx_mixedradix24_f64, Butterfly24Avx64, 24);
1512    test_avx_butterfly!(test_avx_mixedradix27_f64, Butterfly27Avx64, 27);
1513    test_avx_butterfly!(test_avx_mixedradix32_f64, Butterfly32Avx64, 32);
1514    test_avx_butterfly!(test_avx_mixedradix36_f64, Butterfly36Avx64, 36);
1515    test_avx_butterfly!(test_avx_mixedradix64_f64, Butterfly64Avx64, 64);
1516    test_avx_butterfly!(test_avx_mixedradix128_f64, Butterfly128Avx64, 128);
1517    test_avx_butterfly!(test_avx_mixedradix256_f64, Butterfly256Avx64, 256);
1518    test_avx_butterfly!(test_avx_mixedradix512_f64, Butterfly512Avx64, 512);
1519}
rustfft/avx/avx64_butterflies.rs

rustfft/avx/
avx64_butterflies.rs
