Debian Codegraph @

.cargo/vendor/rustfft/src/avx/avx_vector.rs

raw
1 use std::arch::x86_64::*;
2 use std::fmt::Debug;
3 use std::ops::{Deref, DerefMut};
4
5 use num_complex::Complex;
6 use num_traits::Zero;
7
8 use crate::{array_utils::DoubleBuf, twiddles, FftDirection};
9
10 use super::AvxNum;
11
12 /// A SIMD vector of complex numbers, stored with the real values and imaginary values interleaved.
13 /// Implemented for __m128, __m128d, __m256, __m256d, but these all require the AVX instruction set.
14 ///
15 /// The goal of this trait is to reduce code duplication by letting code be generic over the vector type
16 pub trait AvxVector: Copy + Debug + Send + Sync {
17 const SCALAR_PER_VECTOR: usize;
18 const COMPLEX_PER_VECTOR: usize;
19
20 // useful constants
21 unsafe fn zero() -> Self;
22 unsafe fn half_root2() -> Self; // an entire vector filled with 0.5.sqrt()
23
24 // Basic operations that map directly to 1-2 AVX intrinsics
25 unsafe fn add(left: Self, right: Self) -> Self;
26 unsafe fn sub(left: Self, right: Self) -> Self;
27 unsafe fn xor(left: Self, right: Self) -> Self;
28 unsafe fn neg(self) -> Self;
29 unsafe fn mul(left: Self, right: Self) -> Self;
30 unsafe fn fmadd(left: Self, right: Self, add: Self) -> Self;
31 unsafe fn fnmadd(left: Self, right: Self, add: Self) -> Self;
32 unsafe fn fmaddsub(left: Self, right: Self, add: Self) -> Self;
33 unsafe fn fmsubadd(left: Self, right: Self, add: Self) -> Self;
34
35 // More basic operations that end up being implemented in 1-2 intrinsics, but unlike the ones above, these have higher-level meaning than just arithmetic
36 /// Swap each real number with its corresponding imaginary number
37 unsafe fn swap_complex_components(self) -> Self;
38
39 /// first return is the reals duplicated into the imaginaries, second return is the imaginaries duplicated into the reals
40 unsafe fn duplicate_complex_components(self) -> (Self, Self);
41
42 /// Reverse the order of complex numbers in the vector, so that the last is the first and the first is the last
43 unsafe fn reverse_complex_elements(self) -> Self;
44
45 /// Copies the even elements of rows[1] into the corresponding odd elements of rows[0] and returns the result.
46 unsafe fn unpacklo_complex(rows: [Self; 2]) -> Self;
47 /// Copies the odd elements of rows[0] into the corresponding even elements of rows[1] and returns the result.
48 unsafe fn unpackhi_complex(rows: [Self; 2]) -> Self;
49
50 #[inline(always)]
51 unsafe fn unpack_complex(rows: [Self; 2]) -> [Self; 2] {
52 [Self::unpacklo_complex(rows), Self::unpackhi_complex(rows)]
53 }
54
55 /// Fill a vector by computing a twiddle factor and repeating it across the whole vector
56 unsafe fn broadcast_twiddle(index: usize, len: usize, direction: FftDirection) -> Self;
57
58 /// create a Rotator90 instance to rotate complex numbers either 90 or 270 degrees, based on the value of `inverse`
59 unsafe fn make_rotation90(direction: FftDirection) -> Rotation90<Self>;
60
61 /// Generates a chunk of twiddle factors starting at (X,Y) and incrementing X `COMPLEX_PER_VECTOR` times.
62 /// The result will be [twiddle(x*y, len), twiddle((x+1)*y, len), twiddle((x+2)*y, len), ...] for as many complex numbers fit in a vector
63 unsafe fn make_mixedradix_twiddle_chunk(
64 x: usize,
65 y: usize,
66 len: usize,
67 direction: FftDirection,
68 ) -> Self;
69
70 /// Packed transposes. Used by mixed radix. These all take a NxC array, where C is COMPLEX_PER_VECTOR, and transpose it to a CxN array.
71 /// But they also pack the result into as few vectors as possible, with the goal of writing the transposed data out contiguously.
72 unsafe fn transpose2_packed(rows: [Self; 2]) -> [Self; 2];
73 unsafe fn transpose3_packed(rows: [Self; 3]) -> [Self; 3];
74 unsafe fn transpose4_packed(rows: [Self; 4]) -> [Self; 4];
75 unsafe fn transpose5_packed(rows: [Self; 5]) -> [Self; 5];
76 unsafe fn transpose6_packed(rows: [Self; 6]) -> [Self; 6];
77 unsafe fn transpose7_packed(rows: [Self; 7]) -> [Self; 7];
78 unsafe fn transpose8_packed(rows: [Self; 8]) -> [Self; 8];
79 unsafe fn transpose9_packed(rows: [Self; 9]) -> [Self; 9];
80 unsafe fn transpose11_packed(rows: [Self; 11]) -> [Self; 11];
81 unsafe fn transpose12_packed(rows: [Self; 12]) -> [Self; 12];
82 unsafe fn transpose16_packed(rows: [Self; 16]) -> [Self; 16];
83
84 /// Pairwise multiply the complex numbers in `left` with the complex numbers in `right`.
85 #[inline(always)]
86 unsafe fn mul_complex(left: Self, right: Self) -> Self {
87 // Extract the real and imaginary components from left into 2 separate registers
88 let (left_real, left_imag) = Self::duplicate_complex_components(left);
89
90 // create a shuffled version of right where the imaginary values are swapped with the reals
91 let right_shuffled = Self::swap_complex_components(right);
92
93 // multiply our duplicated imaginary left vector by our shuffled right vector. that will give us the right side of the traditional complex multiplication formula
94 let output_right = Self::mul(left_imag, right_shuffled);
95
96 // use a FMA instruction to multiply together left side of the complex multiplication formula, then alternatingly add and subtract the left side from the right
97 Self::fmaddsub(left_real, right, output_right)
98 }
99
100 #[inline(always)]
101 unsafe fn rotate90(self, rotation: Rotation90<Self>) -> Self {
102 // Use the pre-computed vector stored in the Rotation90 instance to negate either the reals or imaginaries
103 let negated = Self::xor(self, rotation.0);
104
105 // Our goal is to swap the reals with the imaginaries, then negate either the reals or the imaginaries, based on whether we're an inverse or not
106 Self::swap_complex_components(negated)
107 }
108
109 #[inline(always)]
110 unsafe fn column_butterfly2(rows: [Self; 2]) -> [Self; 2] {
111 [Self::add(rows[0], rows[1]), Self::sub(rows[0], rows[1])]
112 }
113
114 #[inline(always)]
115 unsafe fn column_butterfly3(rows: [Self; 3], twiddles: Self) -> [Self; 3] {
116 // This algorithm is derived directly from the definition of the Dft of size 3
117 // We'd theoretically have to do 4 complex multiplications, but all of the twiddles we'd be multiplying by are conjugates of each other
118 // By doing some algebra to expand the complex multiplications and factor out the multiplications, we get this
119
120 let [mut mid1, mid2] = Self::column_butterfly2([rows[1], rows[2]]);
121 let output0 = Self::add(rows[0], mid1);
122
123 let (twiddle_real, twiddle_imag) = Self::duplicate_complex_components(twiddles);
124
125 mid1 = Self::fmadd(mid1, twiddle_real, rows[0]);
126
127 let rotation = Self::make_rotation90(FftDirection::Inverse);
128 let mid2_rotated = Self::rotate90(mid2, rotation);
129
130 let output1 = Self::fmadd(mid2_rotated, twiddle_imag, mid1);
131 let output2 = Self::fnmadd(mid2_rotated, twiddle_imag, mid1);
132
133 [output0, output1, output2]
134 }
135
136 #[inline(always)]
137 unsafe fn column_butterfly4(rows: [Self; 4], rotation: Rotation90<Self>) -> [Self; 4] {
138 // Algorithm: 2x2 mixed radix
139
140 // Perform the first set of size-2 FFTs.
141 let [mid0, mid2] = Self::column_butterfly2([rows[0], rows[2]]);
142 let [mid1, mid3] = Self::column_butterfly2([rows[1], rows[3]]);
143
144 // Apply twiddle factors (in this case just a rotation)
145 let mid3_rotated = mid3.rotate90(rotation);
146
147 // Transpose the data and do size-2 FFTs down the columns
148 let [output0, output1] = Self::column_butterfly2([mid0, mid1]);
149 let [output2, output3] = Self::column_butterfly2([mid2, mid3_rotated]);
150
151 // Swap outputs 1 and 2 in the output to do a square transpose
152 [output0, output2, output1, output3]
153 }
154
155 // A niche variant of column_butterfly4 that negates row 3 before performing the FFT. It's able to roll it into existing instructions, so the negation is free
156 #[inline(always)]
157 unsafe fn column_butterfly4_negaterow3(
158 rows: [Self; 4],
159 rotation: Rotation90<Self>,
160 ) -> [Self; 4] {
161 // Algorithm: 2x2 mixed radix
162
163 // Perform the first set of size-2 FFTs.
164 let [mid0, mid2] = Self::column_butterfly2([rows[0], rows[2]]);
165 let (mid1, mid3) = (Self::sub(rows[1], rows[3]), Self::add(rows[1], rows[3])); // to negate row 3, swap add and sub in the butterfly 2
166
167 // Apply twiddle factors (in this case just a rotation)
168 let mid3_rotated = mid3.rotate90(rotation);
169
170 // Transpose the data and do size-2 FFTs down the columns
171 let [output0, output1] = Self::column_butterfly2([mid0, mid1]);
172 let [output2, output3] = Self::column_butterfly2([mid2, mid3_rotated]);
173
174 // Swap outputs 1 and 2 in the output to do a square transpose
175 [output0, output2, output1, output3]
176 }
177
178 #[inline(always)]
179 unsafe fn column_butterfly5(rows: [Self; 5], twiddles: [Self; 2]) -> [Self; 5] {
180 // This algorithm is derived directly from the definition of the Dft of size 5
181 // We'd theoretically have to do 16 complex multiplications for the Dft, but many of the twiddles we'd be multiplying by are conjugates of each other
182 // By doing some algebra to expand the complex multiplications and factor out the real multiplications, we get this faster formula where we only do the equivalent of 4 multiplications
183
184 // do some prep work before we can start applying twiddle factors
185 let [sum1, diff4] = Self::column_butterfly2([rows[1], rows[4]]);
186 let [sum2, diff3] = Self::column_butterfly2([rows[2], rows[3]]);
187
188 let rotation = Self::make_rotation90(FftDirection::Inverse);
189 let rotated4 = Self::rotate90(diff4, rotation);
190 let rotated3 = Self::rotate90(diff3, rotation);
191
192 // to compute the first output, compute the sum of all elements. sum1 and sum2 already have the sum of 1+4 and 2+3 respectively, so if we add them, we'll get the sum of all 4
193 let sum1234 = Self::add(sum1, sum2);
194 let output0 = Self::add(rows[0], sum1234);
195
196 // apply twiddle factors
197 let (twiddles0_re, twiddles0_im) = Self::duplicate_complex_components(twiddles[0]);
198 let (twiddles1_re, twiddles1_im) = Self::duplicate_complex_components(twiddles[1]);
199
200 let twiddled1_mid = Self::fmadd(twiddles0_re, sum1, rows[0]);
201 let twiddled2_mid = Self::fmadd(twiddles1_re, sum1, rows[0]);
202 let twiddled3_mid = Self::mul(twiddles1_im, rotated4);
203 let twiddled4_mid = Self::mul(twiddles0_im, rotated4);
204
205 let twiddled1 = Self::fmadd(twiddles1_re, sum2, twiddled1_mid);
206 let twiddled2 = Self::fmadd(twiddles0_re, sum2, twiddled2_mid);
207 let twiddled3 = Self::fnmadd(twiddles0_im, rotated3, twiddled3_mid); // fnmadd instead of fmadd because we're actually re-using twiddle0 here. remember that this algorithm is all about factoring out conjugated multiplications -- this negation of the twiddle0 imaginaries is a reflection of one of those conugations
208 let twiddled4 = Self::fmadd(twiddles1_im, rotated3, twiddled4_mid);
209
210 // Post-processing to mix the twiddle factors between the rest of the output
211 let [output1, output4] = Self::column_butterfly2([twiddled1, twiddled4]);
212 let [output2, output3] = Self::column_butterfly2([twiddled2, twiddled3]);
213
214 [output0, output1, output2, output3, output4]
215 }
216
217 #[inline(always)]
218 unsafe fn column_butterfly7(rows: [Self; 7], twiddles: [Self; 3]) -> [Self; 7] {
219 // This algorithm is derived directly from the definition of the Dft of size 7
220 // We'd theoretically have to do 36 complex multiplications for the Dft, but many of the twiddles we'd be multiplying by are conjugates of each other
221 // By doing some algebra to expand the complex multiplications and factor out the real multiplications, we get this faster formula where we only do the equivalent of 9 multiplications
222
223 // do some prep work before we can start applying twiddle factors
224 let [sum1, diff6] = Self::column_butterfly2([rows[1], rows[6]]);
225 let [sum2, diff5] = Self::column_butterfly2([rows[2], rows[5]]);
226 let [sum3, diff4] = Self::column_butterfly2([rows[3], rows[4]]);
227
228 let rotation = Self::make_rotation90(FftDirection::Inverse);
229 let rotated4 = Self::rotate90(diff4, rotation);
230 let rotated5 = Self::rotate90(diff5, rotation);
231 let rotated6 = Self::rotate90(diff6, rotation);
232
233 // to compute the first output, compute the sum of all elements. sum1, sum2, and sum3 already have the sum of 1+6 and 2+5 and 3+4 respectively, so if we add them, we'll get the sum of all 6
234 let output0_left = Self::add(sum1, sum2);
235 let output0_right = Self::add(sum3, rows[0]);
236 let output0 = Self::add(output0_left, output0_right);
237
238 // apply twiddle factors. This is probably pushing the limit of how much we should do with this technique.
239 // We probably shouldn't do a size-11 FFT with this technique, for example, because this block of multiplies would grow quadratically
240 let (twiddles0_re, twiddles0_im) = Self::duplicate_complex_components(twiddles[0]);
241 let (twiddles1_re, twiddles1_im) = Self::duplicate_complex_components(twiddles[1]);
242 let (twiddles2_re, twiddles2_im) = Self::duplicate_complex_components(twiddles[2]);
243
244 // Let's do a plain 7-point Dft
245 // | X0 | | W0 W0 W0 W0 W0 W0 W0 | | x0 |
246 // | X1 | | W0 W1 W2 W3 W4 W5 W6 | | x1 |
247 // | X2 | | W0 W2 W4 W6 W8 W10 W12 | | x2 |
248 // | X3 | | W0 W3 W6 W9 W12 W15 W18 | | x3 |
249 // | X4 | | W0 W4 W8 W12 W16 W20 W24 | | x4 |
250 // | X5 | | W0 W5 W10 W15 W20 W25 W30 | | x5 |
251 // | X6 | | W0 W6 W12 W18 W24 W30 W36 | | x6 |
252 // where Wn = exp(-2*pi*n/7) for a forward transform, and exp(+2*pi*n/7) for an inverse.
253
254 // Next, take advantage of the fact that twiddle factor indexes for a size-7 Dft are cyclical mod 7
255 // | X0 | | W0 W0 W0 W0 W0 W0 W0 | | x0 |
256 // | X1 | | W0 W1 W2 W3 W4 W5 W6 | | x1 |
257 // | X2 | | W0 W2 W4 W6 W1 W3 W5 | | x2 |
258 // | X3 | | W0 W3 W6 W2 W5 W1 W4 | | x3 |
259 // | X4 | | W0 W4 W1 W5 W2 W6 W3 | | x4 |
260 // | X5 | | W0 W5 W3 W1 W6 W4 W2 | | x5 |
261 // | X6 | | W0 W6 W5 W4 W3 W2 W1 | | x6 |
262
263 // Finally, take advantage of the fact that for a size-7 Dft,
264 // twiddles 4 through 6 are conjugates of twiddes 3 through 0 (Asterisk marks conjugates)
265 // | X0 | | W0 W0 W0 W0 W0 W0 W0 | | x0 |
266 // | X1 | | W0 W1 W2 W3 W3* W2* W1* | | x1 |
267 // | X2 | | W0 W2 W3* W1* W1 W3 W2* | | x2 |
268 // | X3 | | W0 W3 W1* W2 W2* W1 W3* | | x3 |
269 // | X4 | | W0 W3* W1 W2* W2 W1* W3 | | x4 |
270 // | X5 | | W0 W2* W3 W1 W1* W3* W2 | | x5 |
271 // | X6 | | W0 W1* W2* W3* W3 W2 W1 | | x6 |
272
273 let twiddled1_mid = Self::fmadd(twiddles0_re, sum1, rows[0]);
274 let twiddled2_mid = Self::fmadd(twiddles1_re, sum1, rows[0]);
275 let twiddled3_mid = Self::fmadd(twiddles2_re, sum1, rows[0]);
276 let twiddled4_mid = Self::mul(twiddles2_im, rotated6);
277 let twiddled5_mid = Self::mul(twiddles1_im, rotated6);
278 let twiddled6_mid = Self::mul(twiddles0_im, rotated6);
279
280 let twiddled1_mid2 = Self::fmadd(twiddles1_re, sum2, twiddled1_mid);
281 let twiddled2_mid2 = Self::fmadd(twiddles2_re, sum2, twiddled2_mid);
282 let twiddled3_mid2 = Self::fmadd(twiddles0_re, sum2, twiddled3_mid);
283 let twiddled4_mid2 = Self::fnmadd(twiddles0_im, rotated5, twiddled4_mid); // fnmadd instead of fmadd because we're actually re-using twiddle0 here. remember that this algorithm is all about factoring out conjugated multiplications -- this negation of the twiddle0 imaginaries is a reflection of one of those conugations
284 let twiddled5_mid2 = Self::fnmadd(twiddles2_im, rotated5, twiddled5_mid);
285 let twiddled6_mid2 = Self::fmadd(twiddles1_im, rotated5, twiddled6_mid);
286
287 let twiddled1 = Self::fmadd(twiddles2_re, sum3, twiddled1_mid2);
288 let twiddled2 = Self::fmadd(twiddles0_re, sum3, twiddled2_mid2);
289 let twiddled3 = Self::fmadd(twiddles1_re, sum3, twiddled3_mid2);
290 let twiddled4 = Self::fmadd(twiddles1_im, rotated4, twiddled4_mid2);
291 let twiddled5 = Self::fnmadd(twiddles0_im, rotated4, twiddled5_mid2);
292 let twiddled6 = Self::fmadd(twiddles2_im, rotated4, twiddled6_mid2);
293
294 // Post-processing to mix the twiddle factors between the rest of the output
295 let [output1, output6] = Self::column_butterfly2([twiddled1, twiddled6]);
296 let [output2, output5] = Self::column_butterfly2([twiddled2, twiddled5]);
297 let [output3, output4] = Self::column_butterfly2([twiddled3, twiddled4]);
298
299 [
300 output0, output1, output2, output3, output4, output5, output6,
301 ]
302 }
303
304 #[inline(always)]
305 unsafe fn column_butterfly8(rows: [Self; 8], rotation: Rotation90<Self>) -> [Self; 8] {
306 // Algorithm: 4x2 mixed radix
307
308 // Size-4 FFTs down the columns
309 let mid0 = Self::column_butterfly4([rows[0], rows[2], rows[4], rows[6]], rotation);
310 let mut mid1 = Self::column_butterfly4([rows[1], rows[3], rows[5], rows[7]], rotation);
311
312 // Apply twiddle factors
313 mid1[1] = apply_butterfly8_twiddle1(mid1[1], rotation);
314 mid1[2] = mid1[2].rotate90(rotation);
315 mid1[3] = apply_butterfly8_twiddle3(mid1[3], rotation);
316
317 // Transpose the data and do size-2 FFTs down the columns
318 let [output0, output1] = Self::column_butterfly2([mid0[0], mid1[0]]);
319 let [output2, output3] = Self::column_butterfly2([mid0[1], mid1[1]]);
320 let [output4, output5] = Self::column_butterfly2([mid0[2], mid1[2]]);
321 let [output6, output7] = Self::column_butterfly2([mid0[3], mid1[3]]);
322
323 [
324 output0, output2, output4, output6, output1, output3, output5, output7,
325 ]
326 }
327
328 #[inline(always)]
329 unsafe fn column_butterfly11(rows: [Self; 11], twiddles: [Self; 5]) -> [Self; 11] {
330 // This algorithm is derived directly from the definition of the Dft of size 11
331 // We'd theoretically have to do 100 complex multiplications for the Dft, but many of the twiddles we'd be multiplying by are conjugates of each other
332 // By doing some algebra to expand the complex multiplications and factor out the real multiplications, we get this faster formula where we only do the equivalent of 9 multiplications
333
334 // do some prep work before we can start applying twiddle factors
335 let [sum1, diff10] = Self::column_butterfly2([rows[1], rows[10]]);
336 let [sum2, diff9] = Self::column_butterfly2([rows[2], rows[9]]);
337 let [sum3, diff8] = Self::column_butterfly2([rows[3], rows[8]]);
338 let [sum4, diff7] = Self::column_butterfly2([rows[4], rows[7]]);
339 let [sum5, diff6] = Self::column_butterfly2([rows[5], rows[6]]);
340
341 let rotation = Self::make_rotation90(FftDirection::Inverse);
342 let rotated10 = Self::rotate90(diff10, rotation);
343 let rotated9 = Self::rotate90(diff9, rotation);
344 let rotated8 = Self::rotate90(diff8, rotation);
345 let rotated7 = Self::rotate90(diff7, rotation);
346 let rotated6 = Self::rotate90(diff6, rotation);
347
348 // to compute the first output, compute the sum of all elements. sum1, sum2, and sum3 already have the sum of 1+6 and 2+5 and 3+4 respectively, so if we add them, we'll get the sum of all 6
349 let sum01 = Self::add(rows[0], sum1);
350 let sum23 = Self::add(sum2, sum3);
351 let sum45 = Self::add(sum4, sum5);
352 let sum0123 = Self::add(sum01, sum23);
353 let output0 = Self::add(sum0123, sum45);
354
355 // apply twiddle factors. This is probably pushing the limit of how much we should do with this technique.
356 // We probably shouldn't do a size-11 FFT with this technique, for example, because this block of multiplies would grow quadratically
357 let (twiddles0_re, twiddles0_im) = Self::duplicate_complex_components(twiddles[0]);
358 let (twiddles1_re, twiddles1_im) = Self::duplicate_complex_components(twiddles[1]);
359 let (twiddles2_re, twiddles2_im) = Self::duplicate_complex_components(twiddles[2]);
360 let (twiddles3_re, twiddles3_im) = Self::duplicate_complex_components(twiddles[3]);
361 let (twiddles4_re, twiddles4_im) = Self::duplicate_complex_components(twiddles[4]);
362
363 let twiddled1 = Self::fmadd(twiddles0_re, sum1, rows[0]);
364 let twiddled2 = Self::fmadd(twiddles1_re, sum1, rows[0]);
365 let twiddled3 = Self::fmadd(twiddles2_re, sum1, rows[0]);
366 let twiddled4 = Self::fmadd(twiddles3_re, sum1, rows[0]);
367 let twiddled5 = Self::fmadd(twiddles4_re, sum1, rows[0]);
368 let twiddled6 = Self::mul(twiddles4_im, rotated10);
369 let twiddled7 = Self::mul(twiddles3_im, rotated10);
370 let twiddled8 = Self::mul(twiddles2_im, rotated10);
371 let twiddled9 = Self::mul(twiddles1_im, rotated10);
372 let twiddled10 = Self::mul(twiddles0_im, rotated10);
373
374 let twiddled1 = Self::fmadd(twiddles1_re, sum2, twiddled1);
375 let twiddled2 = Self::fmadd(twiddles3_re, sum2, twiddled2);
376 let twiddled3 = Self::fmadd(twiddles4_re, sum2, twiddled3);
377 let twiddled4 = Self::fmadd(twiddles2_re, sum2, twiddled4);
378 let twiddled5 = Self::fmadd(twiddles0_re, sum2, twiddled5);
379 let twiddled6 = Self::fnmadd(twiddles0_im, rotated9, twiddled6);
380 let twiddled7 = Self::fnmadd(twiddles2_im, rotated9, twiddled7);
381 let twiddled8 = Self::fnmadd(twiddles4_im, rotated9, twiddled8);
382 let twiddled9 = Self::fmadd(twiddles3_im, rotated9, twiddled9);
383 let twiddled10 = Self::fmadd(twiddles1_im, rotated9, twiddled10);
384
385 let twiddled1 = Self::fmadd(twiddles2_re, sum3, twiddled1);
386 let twiddled2 = Self::fmadd(twiddles4_re, sum3, twiddled2);
387 let twiddled3 = Self::fmadd(twiddles1_re, sum3, twiddled3);
388 let twiddled4 = Self::fmadd(twiddles0_re, sum3, twiddled4);
389 let twiddled5 = Self::fmadd(twiddles3_re, sum3, twiddled5);
390 let twiddled6 = Self::fmadd(twiddles3_im, rotated8, twiddled6);
391 let twiddled7 = Self::fmadd(twiddles0_im, rotated8, twiddled7);
392 let twiddled8 = Self::fnmadd(twiddles1_im, rotated8, twiddled8);
393 let twiddled9 = Self::fnmadd(twiddles4_im, rotated8, twiddled9);
394 let twiddled10 = Self::fmadd(twiddles2_im, rotated8, twiddled10);
395
396 let twiddled1 = Self::fmadd(twiddles3_re, sum4, twiddled1);
397 let twiddled2 = Self::fmadd(twiddles2_re, sum4, twiddled2);
398 let twiddled3 = Self::fmadd(twiddles0_re, sum4, twiddled3);
399 let twiddled4 = Self::fmadd(twiddles4_re, sum4, twiddled4);
400 let twiddled5 = Self::fmadd(twiddles1_re, sum4, twiddled5);
401 let twiddled6 = Self::fnmadd(twiddles1_im, rotated7, twiddled6);
402 let twiddled7 = Self::fmadd(twiddles4_im, rotated7, twiddled7);
403 let twiddled8 = Self::fmadd(twiddles0_im, rotated7, twiddled8);
404 let twiddled9 = Self::fnmadd(twiddles2_im, rotated7, twiddled9);
405 let twiddled10 = Self::fmadd(twiddles3_im, rotated7, twiddled10);
406
407 let twiddled1 = Self::fmadd(twiddles4_re, sum5, twiddled1);
408 let twiddled2 = Self::fmadd(twiddles0_re, sum5, twiddled2);
409 let twiddled3 = Self::fmadd(twiddles3_re, sum5, twiddled3);
410 let twiddled4 = Self::fmadd(twiddles1_re, sum5, twiddled4);
411 let twiddled5 = Self::fmadd(twiddles2_re, sum5, twiddled5);
412 let twiddled6 = Self::fmadd(twiddles2_im, rotated6, twiddled6);
413 let twiddled7 = Self::fnmadd(twiddles1_im, rotated6, twiddled7);
414 let twiddled8 = Self::fmadd(twiddles3_im, rotated6, twiddled8);
415 let twiddled9 = Self::fnmadd(twiddles0_im, rotated6, twiddled9);
416 let twiddled10 = Self::fmadd(twiddles4_im, rotated6, twiddled10);
417
418 // Post-processing to mix the twiddle factors between the rest of the output
419 let [output1, output10] = Self::column_butterfly2([twiddled1, twiddled10]);
420 let [output2, output9] = Self::column_butterfly2([twiddled2, twiddled9]);
421 let [output3, output8] = Self::column_butterfly2([twiddled3, twiddled8]);
422 let [output4, output7] = Self::column_butterfly2([twiddled4, twiddled7]);
423 let [output5, output6] = Self::column_butterfly2([twiddled5, twiddled6]);
424
425 [
426 output0, output1, output2, output3, output4, output5, output6, output7, output8,
427 output9, output10,
428 ]
429 }
430
431 #[inline(always)]
432 unsafe fn column_butterfly16(
433 rows: [Self; 16],
434 twiddles: [Self; 2],
435 rotation: Rotation90<Self>,
436 ) -> [Self; 16] {
437 // Algorithm: 4x4 mixed radix
438
439 // Size-4 FFTs down the columns
440 let mid0 = Self::column_butterfly4([rows[0], rows[4], rows[8], rows[12]], rotation);
441 let mut mid1 = Self::column_butterfly4([rows[1], rows[5], rows[9], rows[13]], rotation);
442 let mut mid2 = Self::column_butterfly4([rows[2], rows[6], rows[10], rows[14]], rotation);
443 let mut mid3 = Self::column_butterfly4([rows[3], rows[7], rows[11], rows[15]], rotation);
444
445 // Apply twiddle factors
446 mid1[1] = Self::mul_complex(mid1[1], twiddles[0]);
447
448 // for twiddle(2, 16), we can use the butterfly8 twiddle1 instead, which takes fewer instructions and fewer multiplies
449 mid2[1] = apply_butterfly8_twiddle1(mid2[1], rotation);
450 mid1[2] = apply_butterfly8_twiddle1(mid1[2], rotation);
451
452 // for twiddle(3,16), we can use twiddle(1,16), sort of, but we'd need a branch, and at this point it's easier to just have another vector
453 mid3[1] = Self::mul_complex(mid3[1], twiddles[1]);
454 mid1[3] = Self::mul_complex(mid1[3], twiddles[1]);
455
456 // twiddle(4,16) is just a rotate
457 mid2[2] = mid2[2].rotate90(rotation);
458
459 // for twiddle(6, 16), we can use the butterfly8 twiddle3 instead, which takes fewer instructions and fewer multiplies
460 mid3[2] = apply_butterfly8_twiddle3(mid3[2], rotation);
461 mid2[3] = apply_butterfly8_twiddle3(mid2[3], rotation);
462
463 // twiddle(9, 16) is twiddle (1,16) negated. we're just going to use the same twiddle for now, and apply the negation as a part of our subsequent butterfly 4's
464 mid3[3] = Self::mul_complex(mid3[3], twiddles[0]);
465
466 // Up next is a transpose, but since everything is already in registers, we don't actually have to transpose anything!
467 // "transpose" and thne apply butterfly 4's across the columns of our 4x4 array
468 let output0 = Self::column_butterfly4([mid0[0], mid1[0], mid2[0], mid3[0]], rotation);
469 let output1 = Self::column_butterfly4([mid0[1], mid1[1], mid2[1], mid3[1]], rotation);
470 let output2 = Self::column_butterfly4([mid0[2], mid1[2], mid2[2], mid3[2]], rotation);
471 let output3 =
472 Self::column_butterfly4_negaterow3([mid0[3], mid1[3], mid2[3], mid3[3]], rotation); // finish the twiddle of the last row by negating it
473
474 // finally, one more transpose
475 [
476 output0[0], output1[0], output2[0], output3[0], output0[1], output1[1], output2[1],
477 output3[1], output0[2], output1[2], output2[2], output3[2], output0[3], output1[3],
478 output2[3], output3[3],
479 ]
480 }
481 }
482
483 /// A 256-bit SIMD vector of complex numbers, stored with the real values and imaginary values interleaved.
484 /// Implemented for __m256, __m256d
485 ///
486 /// This trait implements things specific to 256-types, like splitting a 256 vector into 128 vectors
487 /// For compiler-placation reasons, all interactions/awareness the scalar type go here
488 pub trait AvxVector256: AvxVector {
489 type HalfVector: AvxVector128<FullVector = Self>;
490 type ScalarType: AvxNum<VectorType = Self>;
491
492 unsafe fn lo(self) -> Self::HalfVector;
493 unsafe fn hi(self) -> Self::HalfVector;
494 unsafe fn split(self) -> (Self::HalfVector, Self::HalfVector) {
495 (self.lo(), self.hi())
496 }
497 unsafe fn merge(lo: Self::HalfVector, hi: Self::HalfVector) -> Self;
498
499 /// Fill a vector by repeating the provided complex number as many times as possible
500 unsafe fn broadcast_complex_elements(value: Complex<Self::ScalarType>) -> Self;
501
502 /// Adds all complex elements from this vector horizontally
503 unsafe fn hadd_complex(self) -> Complex<Self::ScalarType>;
504
505 // loads/stores of complex numbers
506 unsafe fn load_complex(ptr: *const Complex<Self::ScalarType>) -> Self;
507 unsafe fn store_complex(ptr: *mut Complex<Self::ScalarType>, data: Self);
508
509 // Gather 4 complex numbers (for f32) or 2 complex numbers (for f64) using 4 i32 indexes (for index32) or 4 i64 indexes (for index64).
510 // For f32, there should be 1 index per complex. For f64, there should be 2 indexes, each duplicated
511 // (So to load the complex<f64> at index 5 and 7, the index vector should contain 5,5,7,7. this api sucks but it's internal so whatever.)
512 unsafe fn gather_complex_avx2_index32(
513 ptr: *const Complex<Self::ScalarType>,
514 indexes: __m128i,
515 ) -> Self;
516 unsafe fn gather_complex_avx2_index64(
517 ptr: *const Complex<Self::ScalarType>,
518 indexes: __m256i,
519 ) -> Self;
520
521 // loads/stores of partial vectors of complex numbers. When loading, empty elements are zeroed
522 // unimplemented!() if Self::COMPLEX_PER_VECTOR is not greater than the partial count
523 unsafe fn load_partial1_complex(ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector;
524 unsafe fn load_partial2_complex(ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector;
525 unsafe fn load_partial3_complex(ptr: *const Complex<Self::ScalarType>) -> Self;
526 unsafe fn store_partial1_complex(ptr: *mut Complex<Self::ScalarType>, data: Self::HalfVector);
527 unsafe fn store_partial2_complex(ptr: *mut Complex<Self::ScalarType>, data: Self::HalfVector);
528 unsafe fn store_partial3_complex(ptr: *mut Complex<Self::ScalarType>, data: Self);
529
530 #[inline(always)]
531 unsafe fn column_butterfly6(rows: [Self; 6], twiddles: Self) -> [Self; 6] {
532 // Algorithm: 3x2 good-thomas
533
534 // Size-3 FFTs down the columns of our reordered array
535 let mid0 = Self::column_butterfly3([rows[0], rows[2], rows[4]], twiddles);
536 let mid1 = Self::column_butterfly3([rows[3], rows[5], rows[1]], twiddles);
537
538 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
539
540 // Transpose the data and do size-2 FFTs down the columns
541 let [output0, output1] = Self::column_butterfly2([mid0[0], mid1[0]]);
542 let [output2, output3] = Self::column_butterfly2([mid0[1], mid1[1]]);
543 let [output4, output5] = Self::column_butterfly2([mid0[2], mid1[2]]);
544
545 // Reorder into output
546 [output0, output3, output4, output1, output2, output5]
547 }
548
549 #[inline(always)]
550 unsafe fn column_butterfly9(
551 rows: [Self; 9],
552 twiddles: [Self; 3],
553 butterfly3_twiddles: Self,
554 ) -> [Self; 9] {
555 // Algorithm: 3x3 mixed radix
556
557 // Size-3 FFTs down the columns
558 let mid0 = Self::column_butterfly3([rows[0], rows[3], rows[6]], butterfly3_twiddles);
559 let mut mid1 = Self::column_butterfly3([rows[1], rows[4], rows[7]], butterfly3_twiddles);
560 let mut mid2 = Self::column_butterfly3([rows[2], rows[5], rows[8]], butterfly3_twiddles);
561
562 // Apply twiddle factors. Note that we're re-using twiddles[1]
563 mid1[1] = Self::mul_complex(twiddles[0], mid1[1]);
564 mid1[2] = Self::mul_complex(twiddles[1], mid1[2]);
565 mid2[1] = Self::mul_complex(twiddles[1], mid2[1]);
566 mid2[2] = Self::mul_complex(twiddles[2], mid2[2]);
567
568 let [output0, output1, output2] =
569 Self::column_butterfly3([mid0[0], mid1[0], mid2[0]], butterfly3_twiddles);
570 let [output3, output4, output5] =
571 Self::column_butterfly3([mid0[1], mid1[1], mid2[1]], butterfly3_twiddles);
572 let [output6, output7, output8] =
573 Self::column_butterfly3([mid0[2], mid1[2], mid2[2]], butterfly3_twiddles);
574
575 [
576 output0, output3, output6, output1, output4, output7, output2, output5, output8,
577 ]
578 }
579
580 #[inline(always)]
581 unsafe fn column_butterfly12(
582 rows: [Self; 12],
583 butterfly3_twiddles: Self,
584 rotation: Rotation90<Self>,
585 ) -> [Self; 12] {
586 // Algorithm: 4x3 good-thomas
587
588 // Size-4 FFTs down the columns of our reordered array
589 let mid0 = Self::column_butterfly4([rows[0], rows[3], rows[6], rows[9]], rotation);
590 let mid1 = Self::column_butterfly4([rows[4], rows[7], rows[10], rows[1]], rotation);
591 let mid2 = Self::column_butterfly4([rows[8], rows[11], rows[2], rows[5]], rotation);
592
593 // Since this is good-thomas algorithm, we don't need twiddle factors
594
595 // Transpose the data and do size-2 FFTs down the columns
596 let [output0, output1, output2] =
597 Self::column_butterfly3([mid0[0], mid1[0], mid2[0]], butterfly3_twiddles);
598 let [output3, output4, output5] =
599 Self::column_butterfly3([mid0[1], mid1[1], mid2[1]], butterfly3_twiddles);
600 let [output6, output7, output8] =
601 Self::column_butterfly3([mid0[2], mid1[2], mid2[2]], butterfly3_twiddles);
602 let [output9, output10, output11] =
603 Self::column_butterfly3([mid0[3], mid1[3], mid2[3]], butterfly3_twiddles);
604
605 [
606 output0, output4, output8, output9, output1, output5, output6, output10, output2,
607 output3, output7, output11,
608 ]
609 }
610 }
611
612 /// A 128-bit SIMD vector of complex numbers, stored with the real values and imaginary values interleaved.
613 /// Implemented for __m128, __m128d, but these are all oriented around AVX, so don't call methods on these from a SSE-only context
614 ///
615 /// This trait implements things specific to 128-types, like merging 2 128 vectors into a 256 vector
616 pub trait AvxVector128: AvxVector {
617 type FullVector: AvxVector256<HalfVector = Self>;
618
619 unsafe fn merge(lo: Self, hi: Self) -> Self::FullVector;
620 unsafe fn zero_extend(self) -> Self::FullVector;
621
622 unsafe fn lo(input: Self::FullVector) -> Self;
623 unsafe fn hi(input: Self::FullVector) -> Self;
624 unsafe fn split(input: Self::FullVector) -> (Self, Self) {
625 (Self::lo(input), Self::hi(input))
626 }
627 unsafe fn lo_rotation(input: Rotation90<Self::FullVector>) -> Rotation90<Self>;
628
629 /// Fill a vector by repeating the provided complex number as many times as possible
630 unsafe fn broadcast_complex_elements(
631 value: Complex<<<Self as AvxVector128>::FullVector as AvxVector256>::ScalarType>,
632 ) -> Self;
633
634 // Gather 2 complex numbers (for f32) or 1 complex number (for f64) using 2 i32 indexes (for gather32) or 2 i64 indexes (for gather64).
635 // For f32, there should be 1 index per complex. For f64, there should be 2 indexes, each duplicated
636 // (So to load the complex<f64> at index 5, the index vector should contain 5,5. this api sucks but it's internal so whatever.)
637 unsafe fn gather32_complex_avx2(
638 ptr: *const Complex<<Self::FullVector as AvxVector256>::ScalarType>,
639 indexes: __m128i,
640 ) -> Self;
641 unsafe fn gather64_complex_avx2(
642 ptr: *const Complex<<Self::FullVector as AvxVector256>::ScalarType>,
643 indexes: __m128i,
644 ) -> Self;
645
646 #[inline(always)]
647 unsafe fn column_butterfly6(rows: [Self; 6], twiddles: Self::FullVector) -> [Self; 6] {
648 // Algorithm: 3x2 good-thomas
649
650 // if we merge some of our 128 registers into 256 registers, we can do 1 inner butterfly3 instead of 2
651 let rows03 = Self::merge(rows[0], rows[3]);
652 let rows25 = Self::merge(rows[2], rows[5]);
653 let rows41 = Self::merge(rows[4], rows[1]);
654
655 // Size-3 FFTs down the columns of our reordered array
656 let mid = Self::FullVector::column_butterfly3([rows03, rows25, rows41], twiddles);
657
658 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
659
660 // we can't use our merged columns anymore. so split them back into half vectors
661 let (mid0_0, mid1_0) = Self::split(mid[0]);
662 let (mid0_1, mid1_1) = Self::split(mid[1]);
663 let (mid0_2, mid1_2) = Self::split(mid[2]);
664
665 // Transpose the data and do size-2 FFTs down the columns
666 let [output0, output1] = Self::column_butterfly2([mid0_0, mid1_0]);
667 let [output2, output3] = Self::column_butterfly2([mid0_1, mid1_1]);
668 let [output4, output5] = Self::column_butterfly2([mid0_2, mid1_2]);
669
670 // Reorder into output
671 [output0, output3, output4, output1, output2, output5]
672 }
673
674 #[inline(always)]
675 unsafe fn column_butterfly9(
676 rows: [Self; 9],
677 twiddles_merged: [Self::FullVector; 2],
678 butterfly3_twiddles: Self::FullVector,
679 ) -> [Self; 9] {
680 // Algorithm: 3x3 mixed radix
681
682 // if we merge some of our 128 registers into 256 registers, we can do 2 inner butterfly3's instead of 3
683 let rows12 = Self::merge(rows[1], rows[2]);
684 let rows45 = Self::merge(rows[4], rows[5]);
685 let rows78 = Self::merge(rows[7], rows[8]);
686
687 let mid0 =
688 Self::column_butterfly3([rows[0], rows[3], rows[6]], Self::lo(butterfly3_twiddles));
689 let mut mid12 =
690 Self::FullVector::column_butterfly3([rows12, rows45, rows78], butterfly3_twiddles);
691
692 // Apply twiddle factors. we're applying them on the merged set of vectors, so we need slightly different twiddle factors
693 mid12[1] = Self::FullVector::mul_complex(twiddles_merged[0], mid12[1]);
694 mid12[2] = Self::FullVector::mul_complex(twiddles_merged[1], mid12[2]);
695
696 // we can't use our merged columns anymore. so split them back into half vectors
697 let (mid1_0, mid2_0) = Self::split(mid12[0]);
698 let (mid1_1, mid2_1) = Self::split(mid12[1]);
699 let (mid1_2, mid2_2) = Self::split(mid12[2]);
700
701 // Re-merge our half vectors into different, transposed full vectors. Thankfully the compiler is smart enough to combine these inserts and extracts into permutes
702 let transposed12 = Self::merge(mid0[1], mid0[2]);
703 let transposed45 = Self::merge(mid1_1, mid1_2);
704 let transposed78 = Self::merge(mid2_1, mid2_2);
705
706 let [output0, output1, output2] =
707 Self::column_butterfly3([mid0[0], mid1_0, mid2_0], Self::lo(butterfly3_twiddles));
708 let [output36, output47, output58] = Self::FullVector::column_butterfly3(
709 [transposed12, transposed45, transposed78],
710 butterfly3_twiddles,
711 );
712
713 // Finally, extract our second set of merged columns
714 let (output3, output6) = Self::split(output36);
715 let (output4, output7) = Self::split(output47);
716 let (output5, output8) = Self::split(output58);
717
718 [
719 output0, output3, output6, output1, output4, output7, output2, output5, output8,
720 ]
721 }
722
723 #[inline(always)]
724 unsafe fn column_butterfly12(
725 rows: [Self; 12],
726 butterfly3_twiddles: Self::FullVector,
727 rotation: Rotation90<Self::FullVector>,
728 ) -> [Self; 12] {
729 // Algorithm: 4x3 good-thomas
730
731 // if we merge some of our 128 registers into 256 registers, we can do 2 inner butterfly4's instead of 3
732 let rows48 = Self::merge(rows[4], rows[8]);
733 let rows711 = Self::merge(rows[7], rows[11]);
734 let rows102 = Self::merge(rows[10], rows[2]);
735 let rows15 = Self::merge(rows[1], rows[5]);
736
737 // Size-4 FFTs down the columns of our reordered array
738 let mid0 = Self::column_butterfly4(
739 [rows[0], rows[3], rows[6], rows[9]],
740 Self::lo_rotation(rotation),
741 );
742 let mid12 =
743 Self::FullVector::column_butterfly4([rows48, rows711, rows102, rows15], rotation);
744
745 // We normally would put twiddle factors right here, but since this is good-thomas algorithm, we don't need twiddle factors
746
747 // we can't use our merged columns anymore. so split them back into half vectors
748 let (mid1_0, mid2_0) = Self::split(mid12[0]);
749 let (mid1_1, mid2_1) = Self::split(mid12[1]);
750 let (mid1_2, mid2_2) = Self::split(mid12[2]);
751 let (mid1_3, mid2_3) = Self::split(mid12[3]);
752
753 // Re-merge our half vectors into different, transposed full vectors. This will let us do 2 inner butterfly 3's instead of 4!
754 // Thankfully the compiler is smart enough to combine these inserts and extracts into permutes
755 let transposed03 = Self::merge(mid0[0], mid0[1]);
756 let transposed14 = Self::merge(mid1_0, mid1_1);
757 let transposed25 = Self::merge(mid2_0, mid2_1);
758
759 let transposed69 = Self::merge(mid0[2], mid0[3]);
760 let transposed710 = Self::merge(mid1_2, mid1_3);
761 let transposed811 = Self::merge(mid2_2, mid2_3);
762
763 // Transpose the data and do size-2 FFTs down the columns
764 let [output03, output14, output25] = Self::FullVector::column_butterfly3(
765 [transposed03, transposed14, transposed25],
766 butterfly3_twiddles,
767 );
768 let [output69, output710, output811] = Self::FullVector::column_butterfly3(
769 [transposed69, transposed710, transposed811],
770 butterfly3_twiddles,
771 );
772
773 // Finally, extract our second set of merged columns
774 let (output0, output3) = Self::split(output03);
775 let (output1, output4) = Self::split(output14);
776 let (output2, output5) = Self::split(output25);
777 let (output6, output9) = Self::split(output69);
778 let (output7, output10) = Self::split(output710);
779 let (output8, output11) = Self::split(output811);
780
781 [
782 output0, output4, output8, output9, output1, output5, output6, output10, output2,
783 output3, output7, output11,
784 ]
785 }
786 }
787
788 #[inline(always)]
789 pub unsafe fn apply_butterfly8_twiddle1<V: AvxVector>(input: V, rotation: Rotation90<V>) -> V {
790 let rotated = input.rotate90(rotation);
791 let combined = V::add(rotated, input);
792 V::mul(V::half_root2(), combined)
793 }
794 #[inline(always)]
795 pub unsafe fn apply_butterfly8_twiddle3<V: AvxVector>(input: V, rotation: Rotation90<V>) -> V {
796 let rotated = input.rotate90(rotation);
797 let combined = V::sub(rotated, input);
798 V::mul(V::half_root2(), combined)
799 }
800
801 #[repr(transparent)]
802 #[derive(Clone, Copy, Debug)]
803 pub struct Rotation90<V>(V);
804 impl<V: AvxVector256> Rotation90<V> {
805 #[inline(always)]
806 pub unsafe fn lo(self) -> Rotation90<V::HalfVector> {
807 Rotation90(self.0.lo())
808 }
809 }
810
811 impl AvxVector for __m256 {
812 const SCALAR_PER_VECTOR: usize = 8;
813 const COMPLEX_PER_VECTOR: usize = 4;
814
815 #[inline(always)]
816 unsafe fn zero() -> Self {
817 _mm256_setzero_ps()
818 }
819 #[inline(always)]
820 unsafe fn half_root2() -> Self {
821 // note: we're computing a square root here, but checking the assembly says the compiler is smart enough to turn this into a constant
822 _mm256_broadcast_ss(&0.5f32.sqrt())
823 }
824
825 #[inline(always)]
826 unsafe fn xor(left: Self, right: Self) -> Self {
827 _mm256_xor_ps(left, right)
828 }
829 #[inline(always)]
830 unsafe fn neg(self) -> Self {
831 _mm256_xor_ps(self, _mm256_broadcast_ss(&-0.0))
832 }
833 #[inline(always)]
834 unsafe fn add(left: Self, right: Self) -> Self {
835 _mm256_add_ps(left, right)
836 }
837 #[inline(always)]
838 unsafe fn sub(left: Self, right: Self) -> Self {
839 _mm256_sub_ps(left, right)
840 }
841 #[inline(always)]
842 unsafe fn mul(left: Self, right: Self) -> Self {
843 _mm256_mul_ps(left, right)
844 }
845 #[inline(always)]
846 unsafe fn fmadd(left: Self, right: Self, add: Self) -> Self {
847 _mm256_fmadd_ps(left, right, add)
848 }
849 #[inline(always)]
850 unsafe fn fnmadd(left: Self, right: Self, add: Self) -> Self {
851 _mm256_fnmadd_ps(left, right, add)
852 }
853 #[inline(always)]
854 unsafe fn fmaddsub(left: Self, right: Self, add: Self) -> Self {
855 _mm256_fmaddsub_ps(left, right, add)
856 }
857 #[inline(always)]
858 unsafe fn fmsubadd(left: Self, right: Self, add: Self) -> Self {
859 _mm256_fmsubadd_ps(left, right, add)
860 }
861 #[inline(always)]
862 unsafe fn reverse_complex_elements(self) -> Self {
863 // swap the elements in-lane
864 let permuted = _mm256_permute_ps(self, 0x4E);
865 // swap the lanes
866 _mm256_permute2f128_ps(permuted, permuted, 0x01)
867 }
868 #[inline(always)]
869 unsafe fn unpacklo_complex(rows: [Self; 2]) -> Self {
870 let row0_double = _mm256_castps_pd(rows[0]);
871 let row1_double = _mm256_castps_pd(rows[1]);
872 let unpacked = _mm256_unpacklo_pd(row0_double, row1_double);
873 _mm256_castpd_ps(unpacked)
874 }
875 #[inline(always)]
876 unsafe fn unpackhi_complex(rows: [Self; 2]) -> Self {
877 let row0_double = _mm256_castps_pd(rows[0]);
878 let row1_double = _mm256_castps_pd(rows[1]);
879 let unpacked = _mm256_unpackhi_pd(row0_double, row1_double);
880 _mm256_castpd_ps(unpacked)
881 }
882
883 #[inline(always)]
884 unsafe fn swap_complex_components(self) -> Self {
885 _mm256_permute_ps(self, 0xB1)
886 }
887
888 #[inline(always)]
889 unsafe fn duplicate_complex_components(self) -> (Self, Self) {
890 (_mm256_moveldup_ps(self), _mm256_movehdup_ps(self))
891 }
892
893 #[inline(always)]
894 unsafe fn make_rotation90(direction: FftDirection) -> Rotation90<Self> {
895 let broadcast = match direction {
896 FftDirection::Forward => Complex::new(-0.0, 0.0),
897 FftDirection::Inverse => Complex::new(0.0, -0.0),
898 };
899 Rotation90(Self::broadcast_complex_elements(broadcast))
900 }
901
902 #[inline(always)]
903 unsafe fn make_mixedradix_twiddle_chunk(
904 x: usize,
905 y: usize,
906 len: usize,
907 direction: FftDirection,
908 ) -> Self {
909 let mut twiddle_chunk = [Complex::<f32>::zero(); Self::COMPLEX_PER_VECTOR];
910 for i in 0..Self::COMPLEX_PER_VECTOR {
911 twiddle_chunk[i] = twiddles::compute_twiddle(y * (x + i), len, direction);
912 }
913
914 twiddle_chunk.as_slice().load_complex(0)
915 }
916
917 #[inline(always)]
918 unsafe fn broadcast_twiddle(index: usize, len: usize, direction: FftDirection) -> Self {
919 Self::broadcast_complex_elements(twiddles::compute_twiddle(index, len, direction))
920 }
921
922 #[inline(always)]
923 unsafe fn transpose2_packed(rows: [Self; 2]) -> [Self; 2] {
924 let unpacked = Self::unpack_complex(rows);
925 let output0 = _mm256_permute2f128_ps(unpacked[0], unpacked[1], 0x20);
926 let output1 = _mm256_permute2f128_ps(unpacked[0], unpacked[1], 0x31);
927
928 [output0, output1]
929 }
930 #[inline(always)]
931 unsafe fn transpose3_packed(rows: [Self; 3]) -> [Self; 3] {
932 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
933 let unpacked2 = Self::unpackhi_complex([rows[1], rows[2]]);
934
935 // output0 and output2 each need to swap some elements. thankfully we can blend those elements into the same intermediate value, and then do a permute 128 from there
936 let blended = _mm256_blend_ps(rows[0], rows[2], 0x33);
937
938 let output1 = _mm256_permute2f128_ps(unpacked0, unpacked2, 0x12);
939
940 let output0 = _mm256_permute2f128_ps(unpacked0, blended, 0x20);
941 let output2 = _mm256_permute2f128_ps(unpacked2, blended, 0x13);
942
943 [output0, output1, output2]
944 }
945 #[inline(always)]
946 unsafe fn transpose4_packed(rows: [Self; 4]) -> [Self; 4] {
947 let permute0 = _mm256_permute2f128_ps(rows[0], rows[2], 0x20);
948 let permute1 = _mm256_permute2f128_ps(rows[1], rows[3], 0x20);
949 let permute2 = _mm256_permute2f128_ps(rows[0], rows[2], 0x31);
950 let permute3 = _mm256_permute2f128_ps(rows[1], rows[3], 0x31);
951
952 let [unpacked0, unpacked1] = Self::unpack_complex([permute0, permute1]);
953 let [unpacked2, unpacked3] = Self::unpack_complex([permute2, permute3]);
954
955 [unpacked0, unpacked1, unpacked2, unpacked3]
956 }
957 #[inline(always)]
958 unsafe fn transpose5_packed(rows: [Self; 5]) -> [Self; 5] {
959 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
960 let unpacked1 = Self::unpackhi_complex([rows[1], rows[2]]);
961 let unpacked2 = Self::unpacklo_complex([rows[2], rows[3]]);
962 let unpacked3 = Self::unpackhi_complex([rows[3], rows[4]]);
963 let blended04 = _mm256_blend_ps(rows[0], rows[4], 0x33);
964
965 [
966 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x20),
967 _mm256_permute2f128_ps(blended04, unpacked1, 0x20),
968 _mm256_blend_ps(unpacked0, unpacked3, 0x0f),
969 _mm256_permute2f128_ps(unpacked2, blended04, 0x31),
970 _mm256_permute2f128_ps(unpacked1, unpacked3, 0x31),
971 ]
972 }
973 #[inline(always)]
974 unsafe fn transpose6_packed(rows: [Self; 6]) -> [Self; 6] {
975 let [unpacked0, unpacked1] = Self::unpack_complex([rows[0], rows[1]]);
976 let [unpacked2, unpacked3] = Self::unpack_complex([rows[2], rows[3]]);
977 let [unpacked4, unpacked5] = Self::unpack_complex([rows[4], rows[5]]);
978
979 [
980 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x20),
981 _mm256_permute2f128_ps(unpacked1, unpacked4, 0x02),
982 _mm256_permute2f128_ps(unpacked3, unpacked5, 0x20),
983 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x31),
984 _mm256_permute2f128_ps(unpacked1, unpacked4, 0x13),
985 _mm256_permute2f128_ps(unpacked3, unpacked5, 0x31),
986 ]
987 }
988 #[inline(always)]
989 unsafe fn transpose7_packed(rows: [Self; 7]) -> [Self; 7] {
990 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
991 let unpacked1 = Self::unpackhi_complex([rows[1], rows[2]]);
992 let unpacked2 = Self::unpacklo_complex([rows[2], rows[3]]);
993 let unpacked3 = Self::unpackhi_complex([rows[3], rows[4]]);
994 let unpacked4 = Self::unpacklo_complex([rows[4], rows[5]]);
995 let unpacked5 = Self::unpackhi_complex([rows[5], rows[6]]);
996 let blended06 = _mm256_blend_ps(rows[0], rows[6], 0x33);
997
998 [
999 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x20),
1000 _mm256_permute2f128_ps(unpacked4, blended06, 0x20),
1001 _mm256_permute2f128_ps(unpacked1, unpacked3, 0x20),
1002 _mm256_blend_ps(unpacked0, unpacked5, 0x0f),
1003 _mm256_permute2f128_ps(unpacked2, unpacked4, 0x31),
1004 _mm256_permute2f128_ps(blended06, unpacked1, 0x31),
1005 _mm256_permute2f128_ps(unpacked3, unpacked5, 0x31),
1006 ]
1007 }
1008 #[inline(always)]
1009 unsafe fn transpose8_packed(rows: [Self; 8]) -> [Self; 8] {
1010 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1011 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1012
1013 let output0 = Self::transpose4_packed(chunk0);
1014 let output1 = Self::transpose4_packed(chunk1);
1015
1016 [
1017 output0[0], output1[0], output0[1], output1[1], output0[2], output1[2], output0[3],
1018 output1[3],
1019 ]
1020 }
1021 #[inline(always)]
1022 unsafe fn transpose9_packed(rows: [Self; 9]) -> [Self; 9] {
1023 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
1024 let unpacked1 = Self::unpackhi_complex([rows[1], rows[2]]);
1025 let unpacked2 = Self::unpacklo_complex([rows[2], rows[3]]);
1026 let unpacked3 = Self::unpackhi_complex([rows[3], rows[4]]);
1027 let unpacked5 = Self::unpacklo_complex([rows[4], rows[5]]);
1028 let unpacked6 = Self::unpackhi_complex([rows[5], rows[6]]);
1029 let unpacked7 = Self::unpacklo_complex([rows[6], rows[7]]);
1030 let unpacked8 = Self::unpackhi_complex([rows[7], rows[8]]);
1031 let blended9 = _mm256_blend_ps(rows[0], rows[8], 0x33);
1032
1033 [
1034 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x20),
1035 _mm256_permute2f128_ps(unpacked5, unpacked7, 0x20),
1036 _mm256_permute2f128_ps(blended9, unpacked1, 0x20),
1037 _mm256_permute2f128_ps(unpacked3, unpacked6, 0x20),
1038 _mm256_blend_ps(unpacked0, unpacked8, 0x0f),
1039 _mm256_permute2f128_ps(unpacked2, unpacked5, 0x31),
1040 _mm256_permute2f128_ps(unpacked7, blended9, 0x31),
1041 _mm256_permute2f128_ps(unpacked1, unpacked3, 0x31),
1042 _mm256_permute2f128_ps(unpacked6, unpacked8, 0x31),
1043 ]
1044 }
1045 #[inline(always)]
1046 unsafe fn transpose11_packed(rows: [Self; 11]) -> [Self; 11] {
1047 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
1048 let unpacked1 = Self::unpackhi_complex([rows[1], rows[2]]);
1049 let unpacked2 = Self::unpacklo_complex([rows[2], rows[3]]);
1050 let unpacked3 = Self::unpackhi_complex([rows[3], rows[4]]);
1051 let unpacked4 = Self::unpacklo_complex([rows[4], rows[5]]);
1052 let unpacked5 = Self::unpackhi_complex([rows[5], rows[6]]);
1053 let unpacked6 = Self::unpacklo_complex([rows[6], rows[7]]);
1054 let unpacked7 = Self::unpackhi_complex([rows[7], rows[8]]);
1055 let unpacked8 = Self::unpacklo_complex([rows[8], rows[9]]);
1056 let unpacked9 = Self::unpackhi_complex([rows[9], rows[10]]);
1057 let blended10 = _mm256_blend_ps(rows[0], rows[10], 0x33);
1058
1059 [
1060 _mm256_permute2f128_ps(unpacked0, unpacked2, 0x20),
1061 _mm256_permute2f128_ps(unpacked4, unpacked6, 0x20),
1062 _mm256_permute2f128_ps(unpacked8, blended10, 0x20),
1063 _mm256_permute2f128_ps(unpacked1, unpacked3, 0x20),
1064 _mm256_permute2f128_ps(unpacked5, unpacked7, 0x20),
1065 _mm256_blend_ps(unpacked0, unpacked9, 0x0f),
1066 _mm256_permute2f128_ps(unpacked2, unpacked4, 0x31),
1067 _mm256_permute2f128_ps(unpacked6, unpacked8, 0x31),
1068 _mm256_permute2f128_ps(blended10, unpacked1, 0x31),
1069 _mm256_permute2f128_ps(unpacked3, unpacked5, 0x31),
1070 _mm256_permute2f128_ps(unpacked7, unpacked9, 0x31),
1071 ]
1072 }
1073 #[inline(always)]
1074 unsafe fn transpose12_packed(rows: [Self; 12]) -> [Self; 12] {
1075 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1076 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1077 let chunk2 = [rows[8], rows[9], rows[10], rows[11]];
1078
1079 let output0 = Self::transpose4_packed(chunk0);
1080 let output1 = Self::transpose4_packed(chunk1);
1081 let output2 = Self::transpose4_packed(chunk2);
1082
1083 [
1084 output0[0], output1[0], output2[0], output0[1], output1[1], output2[1], output0[2],
1085 output1[2], output2[2], output0[3], output1[3], output2[3],
1086 ]
1087 }
1088 #[inline(always)]
1089 unsafe fn transpose16_packed(rows: [Self; 16]) -> [Self; 16] {
1090 let chunk0 = [
1091 rows[0], rows[1], rows[2], rows[3], rows[4], rows[5], rows[6], rows[7],
1092 ];
1093 let chunk1 = [
1094 rows[8], rows[9], rows[10], rows[11], rows[12], rows[13], rows[14], rows[15],
1095 ];
1096
1097 let output0 = Self::transpose8_packed(chunk0);
1098 let output1 = Self::transpose8_packed(chunk1);
1099
1100 [
1101 output0[0], output0[1], output1[0], output1[1], output0[2], output0[3], output1[2],
1102 output1[3], output0[4], output0[5], output1[4], output1[5], output0[6], output0[7],
1103 output1[6], output1[7],
1104 ]
1105 }
1106 }
1107 impl AvxVector256 for __m256 {
1108 type ScalarType = f32;
1109 type HalfVector = __m128;
1110
1111 #[inline(always)]
1112 unsafe fn lo(self) -> Self::HalfVector {
1113 _mm256_castps256_ps128(self)
1114 }
1115 #[inline(always)]
1116 unsafe fn hi(self) -> Self::HalfVector {
1117 _mm256_extractf128_ps(self, 1)
1118 }
1119 #[inline(always)]
1120 unsafe fn merge(lo: Self::HalfVector, hi: Self::HalfVector) -> Self {
1121 _mm256_insertf128_ps(_mm256_castps128_ps256(lo), hi, 1)
1122 }
1123
1124 #[inline(always)]
1125 unsafe fn broadcast_complex_elements(value: Complex<Self::ScalarType>) -> Self {
1126 _mm256_set_ps(
1127 value.im, value.re, value.im, value.re, value.im, value.re, value.im, value.re,
1128 )
1129 }
1130
1131 #[inline(always)]
1132 unsafe fn hadd_complex(self) -> Complex<Self::ScalarType> {
1133 let lo = self.lo();
1134 let hi = self.hi();
1135 let sum = _mm_add_ps(lo, hi);
1136 let shuffled_sum = Self::HalfVector::unpackhi_complex([sum, sum]);
1137 let result = _mm_add_ps(sum, shuffled_sum);
1138
1139 let mut result_storage = [Complex::zero(); 1];
1140 result_storage
1141 .as_mut_slice()
1142 .store_partial1_complex(result, 0);
1143 result_storage[0]
1144 }
1145
1146 #[inline(always)]
1147 unsafe fn load_complex(ptr: *const Complex<Self::ScalarType>) -> Self {
1148 _mm256_loadu_ps(ptr as *const Self::ScalarType)
1149 }
1150 #[inline(always)]
1151 unsafe fn store_complex(ptr: *mut Complex<Self::ScalarType>, data: Self) {
1152 _mm256_storeu_ps(ptr as *mut Self::ScalarType, data)
1153 }
1154 #[inline(always)]
1155 unsafe fn gather_complex_avx2_index32(
1156 ptr: *const Complex<Self::ScalarType>,
1157 indexes: __m128i,
1158 ) -> Self {
1159 _mm256_castpd_ps(_mm256_i32gather_pd(ptr as *const f64, indexes, 8))
1160 }
1161 #[inline(always)]
1162 unsafe fn gather_complex_avx2_index64(
1163 ptr: *const Complex<Self::ScalarType>,
1164 indexes: __m256i,
1165 ) -> Self {
1166 _mm256_castpd_ps(_mm256_i64gather_pd(ptr as *const f64, indexes, 8))
1167 }
1168
1169 #[inline(always)]
1170 unsafe fn load_partial1_complex(ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector {
1171 let data = _mm_load_sd(ptr as *const f64);
1172 _mm_castpd_ps(data)
1173 }
1174 #[inline(always)]
1175 unsafe fn load_partial2_complex(ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector {
1176 _mm_loadu_ps(ptr as *const f32)
1177 }
1178 #[inline(always)]
1179 unsafe fn load_partial3_complex(ptr: *const Complex<Self::ScalarType>) -> Self {
1180 let lo = Self::load_partial2_complex(ptr);
1181 let hi = Self::load_partial1_complex(ptr.add(2));
1182 Self::merge(lo, hi)
1183 }
1184 #[inline(always)]
1185 unsafe fn store_partial1_complex(ptr: *mut Complex<Self::ScalarType>, data: Self::HalfVector) {
1186 _mm_store_sd(ptr as *mut f64, _mm_castps_pd(data));
1187 }
1188 #[inline(always)]
1189 unsafe fn store_partial2_complex(ptr: *mut Complex<Self::ScalarType>, data: Self::HalfVector) {
1190 _mm_storeu_ps(ptr as *mut f32, data);
1191 }
1192 #[inline(always)]
1193 unsafe fn store_partial3_complex(ptr: *mut Complex<Self::ScalarType>, data: Self) {
1194 Self::store_partial2_complex(ptr, data.lo());
1195 Self::store_partial1_complex(ptr.add(2), data.hi());
1196 }
1197 }
1198
1199 impl AvxVector for __m128 {
1200 const SCALAR_PER_VECTOR: usize = 4;
1201 const COMPLEX_PER_VECTOR: usize = 2;
1202
1203 #[inline(always)]
1204 unsafe fn zero() -> Self {
1205 _mm_setzero_ps()
1206 }
1207 #[inline(always)]
1208 unsafe fn half_root2() -> Self {
1209 // note: we're computing a square root here, but checking the assembly says the compiler is smart enough to turn this into a constant
1210 _mm_broadcast_ss(&0.5f32.sqrt())
1211 }
1212
1213 #[inline(always)]
1214 unsafe fn xor(left: Self, right: Self) -> Self {
1215 _mm_xor_ps(left, right)
1216 }
1217 #[inline(always)]
1218 unsafe fn neg(self) -> Self {
1219 _mm_xor_ps(self, _mm_broadcast_ss(&-0.0))
1220 }
1221 #[inline(always)]
1222 unsafe fn add(left: Self, right: Self) -> Self {
1223 _mm_add_ps(left, right)
1224 }
1225 #[inline(always)]
1226 unsafe fn sub(left: Self, right: Self) -> Self {
1227 _mm_sub_ps(left, right)
1228 }
1229 #[inline(always)]
1230 unsafe fn mul(left: Self, right: Self) -> Self {
1231 _mm_mul_ps(left, right)
1232 }
1233 #[inline(always)]
1234 unsafe fn fmadd(left: Self, right: Self, add: Self) -> Self {
1235 _mm_fmadd_ps(left, right, add)
1236 }
1237 #[inline(always)]
1238 unsafe fn fnmadd(left: Self, right: Self, add: Self) -> Self {
1239 _mm_fnmadd_ps(left, right, add)
1240 }
1241 #[inline(always)]
1242 unsafe fn fmaddsub(left: Self, right: Self, add: Self) -> Self {
1243 _mm_fmaddsub_ps(left, right, add)
1244 }
1245 #[inline(always)]
1246 unsafe fn fmsubadd(left: Self, right: Self, add: Self) -> Self {
1247 _mm_fmsubadd_ps(left, right, add)
1248 }
1249
1250 #[inline(always)]
1251 unsafe fn reverse_complex_elements(self) -> Self {
1252 // swap the elements in-lane
1253 _mm_permute_ps(self, 0x4E)
1254 }
1255
1256 #[inline(always)]
1257 unsafe fn unpacklo_complex(rows: [Self; 2]) -> Self {
1258 let row0_double = _mm_castps_pd(rows[0]);
1259 let row1_double = _mm_castps_pd(rows[1]);
1260 let unpacked = _mm_unpacklo_pd(row0_double, row1_double);
1261 _mm_castpd_ps(unpacked)
1262 }
1263 #[inline(always)]
1264 unsafe fn unpackhi_complex(rows: [Self; 2]) -> Self {
1265 let row0_double = _mm_castps_pd(rows[0]);
1266 let row1_double = _mm_castps_pd(rows[1]);
1267 let unpacked = _mm_unpackhi_pd(row0_double, row1_double);
1268 _mm_castpd_ps(unpacked)
1269 }
1270
1271 #[inline(always)]
1272 unsafe fn swap_complex_components(self) -> Self {
1273 _mm_permute_ps(self, 0xB1)
1274 }
1275 #[inline(always)]
1276 unsafe fn duplicate_complex_components(self) -> (Self, Self) {
1277 (_mm_moveldup_ps(self), _mm_movehdup_ps(self))
1278 }
1279
1280 #[inline(always)]
1281 unsafe fn make_rotation90(direction: FftDirection) -> Rotation90<Self> {
1282 let broadcast = match direction {
1283 FftDirection::Forward => Complex::new(-0.0, 0.0),
1284 FftDirection::Inverse => Complex::new(0.0, -0.0),
1285 };
1286 Rotation90(Self::broadcast_complex_elements(broadcast))
1287 }
1288 #[inline(always)]
1289 unsafe fn make_mixedradix_twiddle_chunk(
1290 x: usize,
1291 y: usize,
1292 len: usize,
1293 direction: FftDirection,
1294 ) -> Self {
1295 let mut twiddle_chunk = [Complex::<f32>::zero(); Self::COMPLEX_PER_VECTOR];
1296 for i in 0..Self::COMPLEX_PER_VECTOR {
1297 twiddle_chunk[i] = twiddles::compute_twiddle(y * (x + i), len, direction);
1298 }
1299
1300 _mm_loadu_ps(twiddle_chunk.as_ptr() as *const f32)
1301 }
1302 #[inline(always)]
1303 unsafe fn broadcast_twiddle(index: usize, len: usize, direction: FftDirection) -> Self {
1304 Self::broadcast_complex_elements(twiddles::compute_twiddle(index, len, direction))
1305 }
1306
1307 #[inline(always)]
1308 unsafe fn transpose2_packed(rows: [Self; 2]) -> [Self; 2] {
1309 Self::unpack_complex(rows)
1310 }
1311 #[inline(always)]
1312 unsafe fn transpose3_packed(rows: [Self; 3]) -> [Self; 3] {
1313 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
1314 let blended = _mm_blend_ps(rows[0], rows[2], 0x03);
1315 let unpacked2 = Self::unpackhi_complex([rows[1], rows[2]]);
1316
1317 [unpacked0, blended, unpacked2]
1318 }
1319 #[inline(always)]
1320 unsafe fn transpose4_packed(rows: [Self; 4]) -> [Self; 4] {
1321 let [unpacked0, unpacked1] = Self::unpack_complex([rows[0], rows[1]]);
1322 let [unpacked2, unpacked3] = Self::unpack_complex([rows[2], rows[3]]);
1323
1324 [unpacked0, unpacked2, unpacked1, unpacked3]
1325 }
1326 #[inline(always)]
1327 unsafe fn transpose5_packed(rows: [Self; 5]) -> [Self; 5] {
1328 [
1329 Self::unpacklo_complex([rows[0], rows[1]]),
1330 Self::unpacklo_complex([rows[2], rows[3]]),
1331 _mm_blend_ps(rows[0], rows[4], 0x03),
1332 Self::unpackhi_complex([rows[1], rows[2]]),
1333 Self::unpackhi_complex([rows[3], rows[4]]),
1334 ]
1335 }
1336 #[inline(always)]
1337 unsafe fn transpose6_packed(rows: [Self; 6]) -> [Self; 6] {
1338 let [unpacked0, unpacked1] = Self::unpack_complex([rows[0], rows[1]]);
1339 let [unpacked2, unpacked3] = Self::unpack_complex([rows[2], rows[3]]);
1340 let [unpacked4, unpacked5] = Self::unpack_complex([rows[4], rows[5]]);
1341
1342 [
1343 unpacked0, unpacked2, unpacked4, unpacked1, unpacked3, unpacked5,
1344 ]
1345 }
1346 #[inline(always)]
1347 unsafe fn transpose7_packed(rows: [Self; 7]) -> [Self; 7] {
1348 [
1349 Self::unpacklo_complex([rows[0], rows[1]]),
1350 Self::unpacklo_complex([rows[2], rows[3]]),
1351 Self::unpacklo_complex([rows[4], rows[5]]),
1352 _mm_shuffle_ps(rows[6], rows[0], 0xE4),
1353 Self::unpackhi_complex([rows[1], rows[2]]),
1354 Self::unpackhi_complex([rows[3], rows[4]]),
1355 Self::unpackhi_complex([rows[5], rows[6]]),
1356 ]
1357 }
1358 #[inline(always)]
1359 unsafe fn transpose8_packed(rows: [Self; 8]) -> [Self; 8] {
1360 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1361 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1362
1363 let output0 = Self::transpose4_packed(chunk0);
1364 let output1 = Self::transpose4_packed(chunk1);
1365
1366 [
1367 output0[0], output0[1], output1[0], output1[1], output0[2], output0[3], output1[2],
1368 output1[3],
1369 ]
1370 }
1371 #[inline(always)]
1372 unsafe fn transpose9_packed(rows: [Self; 9]) -> [Self; 9] {
1373 [
1374 Self::unpacklo_complex([rows[0], rows[1]]),
1375 Self::unpacklo_complex([rows[2], rows[3]]),
1376 Self::unpacklo_complex([rows[4], rows[5]]),
1377 Self::unpacklo_complex([rows[6], rows[7]]),
1378 _mm_shuffle_ps(rows[8], rows[0], 0xE4),
1379 Self::unpackhi_complex([rows[1], rows[2]]),
1380 Self::unpackhi_complex([rows[3], rows[4]]),
1381 Self::unpackhi_complex([rows[5], rows[6]]),
1382 Self::unpackhi_complex([rows[7], rows[8]]),
1383 ]
1384 }
1385 #[inline(always)]
1386 unsafe fn transpose11_packed(rows: [Self; 11]) -> [Self; 11] {
1387 [
1388 Self::unpacklo_complex([rows[0], rows[1]]),
1389 Self::unpacklo_complex([rows[2], rows[3]]),
1390 Self::unpacklo_complex([rows[4], rows[5]]),
1391 Self::unpacklo_complex([rows[6], rows[7]]),
1392 Self::unpacklo_complex([rows[8], rows[9]]),
1393 _mm_shuffle_ps(rows[10], rows[0], 0xE4),
1394 Self::unpackhi_complex([rows[1], rows[2]]),
1395 Self::unpackhi_complex([rows[3], rows[4]]),
1396 Self::unpackhi_complex([rows[5], rows[6]]),
1397 Self::unpackhi_complex([rows[7], rows[8]]),
1398 Self::unpackhi_complex([rows[9], rows[10]]),
1399 ]
1400 }
1401 #[inline(always)]
1402 unsafe fn transpose12_packed(rows: [Self; 12]) -> [Self; 12] {
1403 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1404 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1405 let chunk2 = [rows[8], rows[9], rows[10], rows[11]];
1406
1407 let output0 = Self::transpose4_packed(chunk0);
1408 let output1 = Self::transpose4_packed(chunk1);
1409 let output2 = Self::transpose4_packed(chunk2);
1410
1411 [
1412 output0[0], output0[1], output1[0], output1[1], output2[0], output2[1], output0[2],
1413 output0[3], output1[2], output1[3], output2[2], output2[3],
1414 ]
1415 }
1416 #[inline(always)]
1417 unsafe fn transpose16_packed(rows: [Self; 16]) -> [Self; 16] {
1418 let chunk0 = [
1419 rows[0], rows[1], rows[2], rows[3], rows[4], rows[5], rows[6], rows[7],
1420 ];
1421 let chunk1 = [
1422 rows[8], rows[9], rows[10], rows[11], rows[12], rows[13], rows[14], rows[15],
1423 ];
1424
1425 let output0 = Self::transpose8_packed(chunk0);
1426 let output1 = Self::transpose8_packed(chunk1);
1427
1428 [
1429 output0[0], output0[1], output0[2], output0[3], output1[0], output1[1], output1[2],
1430 output1[3], output0[4], output0[5], output0[6], output0[7], output1[4], output1[5],
1431 output1[6], output1[7],
1432 ]
1433 }
1434 }
1435 impl AvxVector128 for __m128 {
1436 type FullVector = __m256;
1437
1438 #[inline(always)]
1439 unsafe fn lo(input: Self::FullVector) -> Self {
1440 _mm256_castps256_ps128(input)
1441 }
1442 #[inline(always)]
1443 unsafe fn hi(input: Self::FullVector) -> Self {
1444 _mm256_extractf128_ps(input, 1)
1445 }
1446 #[inline(always)]
1447 unsafe fn merge(lo: Self, hi: Self) -> Self::FullVector {
1448 _mm256_insertf128_ps(_mm256_castps128_ps256(lo), hi, 1)
1449 }
1450 #[inline(always)]
1451 unsafe fn zero_extend(self) -> Self::FullVector {
1452 _mm256_zextps128_ps256(self)
1453 }
1454 #[inline(always)]
1455 unsafe fn lo_rotation(input: Rotation90<Self::FullVector>) -> Rotation90<Self> {
1456 input.lo()
1457 }
1458 #[inline(always)]
1459 unsafe fn broadcast_complex_elements(value: Complex<f32>) -> Self {
1460 _mm_set_ps(value.im, value.re, value.im, value.re)
1461 }
1462 #[inline(always)]
1463 unsafe fn gather32_complex_avx2(ptr: *const Complex<f32>, indexes: __m128i) -> Self {
1464 _mm_castpd_ps(_mm_i32gather_pd(ptr as *const f64, indexes, 8))
1465 }
1466 #[inline(always)]
1467 unsafe fn gather64_complex_avx2(ptr: *const Complex<f32>, indexes: __m128i) -> Self {
1468 _mm_castpd_ps(_mm_i64gather_pd(ptr as *const f64, indexes, 8))
1469 }
1470 }
1471
1472 impl AvxVector for __m256d {
1473 const SCALAR_PER_VECTOR: usize = 4;
1474 const COMPLEX_PER_VECTOR: usize = 2;
1475
1476 #[inline(always)]
1477 unsafe fn zero() -> Self {
1478 _mm256_setzero_pd()
1479 }
1480 #[inline(always)]
1481 unsafe fn half_root2() -> Self {
1482 // note: we're computing a square root here, but checking the assembly says the compiler is smart enough to turn this into a constant
1483 _mm256_broadcast_sd(&0.5f64.sqrt())
1484 }
1485
1486 #[inline(always)]
1487 unsafe fn xor(left: Self, right: Self) -> Self {
1488 _mm256_xor_pd(left, right)
1489 }
1490 #[inline(always)]
1491 unsafe fn neg(self) -> Self {
1492 _mm256_xor_pd(self, _mm256_broadcast_sd(&-0.0))
1493 }
1494 #[inline(always)]
1495 unsafe fn add(left: Self, right: Self) -> Self {
1496 _mm256_add_pd(left, right)
1497 }
1498 #[inline(always)]
1499 unsafe fn sub(left: Self, right: Self) -> Self {
1500 _mm256_sub_pd(left, right)
1501 }
1502 #[inline(always)]
1503 unsafe fn mul(left: Self, right: Self) -> Self {
1504 _mm256_mul_pd(left, right)
1505 }
1506 #[inline(always)]
1507 unsafe fn fmadd(left: Self, right: Self, add: Self) -> Self {
1508 _mm256_fmadd_pd(left, right, add)
1509 }
1510 #[inline(always)]
1511 unsafe fn fnmadd(left: Self, right: Self, add: Self) -> Self {
1512 _mm256_fnmadd_pd(left, right, add)
1513 }
1514 #[inline(always)]
1515 unsafe fn fmaddsub(left: Self, right: Self, add: Self) -> Self {
1516 _mm256_fmaddsub_pd(left, right, add)
1517 }
1518 #[inline(always)]
1519 unsafe fn fmsubadd(left: Self, right: Self, add: Self) -> Self {
1520 _mm256_fmsubadd_pd(left, right, add)
1521 }
1522
1523 #[inline(always)]
1524 unsafe fn reverse_complex_elements(self) -> Self {
1525 _mm256_permute2f128_pd(self, self, 0x01)
1526 }
1527 #[inline(always)]
1528 unsafe fn unpacklo_complex(rows: [Self; 2]) -> Self {
1529 _mm256_permute2f128_pd(rows[0], rows[1], 0x20)
1530 }
1531 #[inline(always)]
1532 unsafe fn unpackhi_complex(rows: [Self; 2]) -> Self {
1533 _mm256_permute2f128_pd(rows[0], rows[1], 0x31)
1534 }
1535
1536 #[inline(always)]
1537 unsafe fn swap_complex_components(self) -> Self {
1538 _mm256_permute_pd(self, 0x05)
1539 }
1540 #[inline(always)]
1541 unsafe fn duplicate_complex_components(self) -> (Self, Self) {
1542 (_mm256_movedup_pd(self), _mm256_permute_pd(self, 0x0F))
1543 }
1544
1545 #[inline(always)]
1546 unsafe fn make_rotation90(direction: FftDirection) -> Rotation90<Self> {
1547 let broadcast = match direction {
1548 FftDirection::Forward => Complex::new(-0.0, 0.0),
1549 FftDirection::Inverse => Complex::new(0.0, -0.0),
1550 };
1551 Rotation90(Self::broadcast_complex_elements(broadcast))
1552 }
1553 #[inline(always)]
1554 unsafe fn make_mixedradix_twiddle_chunk(
1555 x: usize,
1556 y: usize,
1557 len: usize,
1558 direction: FftDirection,
1559 ) -> Self {
1560 let mut twiddle_chunk = [Complex::<f64>::zero(); Self::COMPLEX_PER_VECTOR];
1561 for i in 0..Self::COMPLEX_PER_VECTOR {
1562 twiddle_chunk[i] = twiddles::compute_twiddle(y * (x + i), len, direction);
1563 }
1564
1565 twiddle_chunk.as_slice().load_complex(0)
1566 }
1567 #[inline(always)]
1568 unsafe fn broadcast_twiddle(index: usize, len: usize, direction: FftDirection) -> Self {
1569 Self::broadcast_complex_elements(twiddles::compute_twiddle(index, len, direction))
1570 }
1571
1572 #[inline(always)]
1573 unsafe fn transpose2_packed(rows: [Self; 2]) -> [Self; 2] {
1574 Self::unpack_complex(rows)
1575 }
1576 #[inline(always)]
1577 unsafe fn transpose3_packed(rows: [Self; 3]) -> [Self; 3] {
1578 let unpacked0 = Self::unpacklo_complex([rows[0], rows[1]]);
1579 let blended = _mm256_blend_pd(rows[0], rows[2], 0x03);
1580 let unpacked2 = Self::unpackhi_complex([rows[1], rows[2]]);
1581
1582 [unpacked0, blended, unpacked2]
1583 }
1584 #[inline(always)]
1585 unsafe fn transpose4_packed(rows: [Self; 4]) -> [Self; 4] {
1586 let [unpacked0, unpacked1] = Self::unpack_complex([rows[0], rows[1]]);
1587 let [unpacked2, unpacked3] = Self::unpack_complex([rows[2], rows[3]]);
1588
1589 [unpacked0, unpacked2, unpacked1, unpacked3]
1590 }
1591 #[inline(always)]
1592 unsafe fn transpose5_packed(rows: [Self; 5]) -> [Self; 5] {
1593 [
1594 Self::unpacklo_complex([rows[0], rows[1]]),
1595 Self::unpacklo_complex([rows[2], rows[3]]),
1596 _mm256_blend_pd(rows[0], rows[4], 0x03),
1597 Self::unpackhi_complex([rows[1], rows[2]]),
1598 Self::unpackhi_complex([rows[3], rows[4]]),
1599 ]
1600 }
1601 #[inline(always)]
1602 unsafe fn transpose6_packed(rows: [Self; 6]) -> [Self; 6] {
1603 let [unpacked0, unpacked1] = Self::unpack_complex([rows[0], rows[1]]);
1604 let [unpacked2, unpacked3] = Self::unpack_complex([rows[2], rows[3]]);
1605 let [unpacked4, unpacked5] = Self::unpack_complex([rows[4], rows[5]]);
1606
1607 [
1608 unpacked0, unpacked2, unpacked4, unpacked1, unpacked3, unpacked5,
1609 ]
1610 }
1611 #[inline(always)]
1612 unsafe fn transpose7_packed(rows: [Self; 7]) -> [Self; 7] {
1613 [
1614 Self::unpacklo_complex([rows[0], rows[1]]),
1615 Self::unpacklo_complex([rows[2], rows[3]]),
1616 Self::unpacklo_complex([rows[4], rows[5]]),
1617 _mm256_blend_pd(rows[0], rows[6], 0x03),
1618 Self::unpackhi_complex([rows[1], rows[2]]),
1619 Self::unpackhi_complex([rows[3], rows[4]]),
1620 Self::unpackhi_complex([rows[5], rows[6]]),
1621 ]
1622 }
1623 #[inline(always)]
1624 unsafe fn transpose8_packed(rows: [Self; 8]) -> [Self; 8] {
1625 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1626 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1627
1628 let output0 = Self::transpose4_packed(chunk0);
1629 let output1 = Self::transpose4_packed(chunk1);
1630
1631 [
1632 output0[0], output0[1], output1[0], output1[1], output0[2], output0[3], output1[2],
1633 output1[3],
1634 ]
1635 }
1636 #[inline(always)]
1637 unsafe fn transpose9_packed(rows: [Self; 9]) -> [Self; 9] {
1638 [
1639 _mm256_permute2f128_pd(rows[0], rows[1], 0x20),
1640 _mm256_permute2f128_pd(rows[2], rows[3], 0x20),
1641 _mm256_permute2f128_pd(rows[4], rows[5], 0x20),
1642 _mm256_permute2f128_pd(rows[6], rows[7], 0x20),
1643 _mm256_permute2f128_pd(rows[8], rows[0], 0x30),
1644 _mm256_permute2f128_pd(rows[1], rows[2], 0x31),
1645 _mm256_permute2f128_pd(rows[3], rows[4], 0x31),
1646 _mm256_permute2f128_pd(rows[5], rows[6], 0x31),
1647 _mm256_permute2f128_pd(rows[7], rows[8], 0x31),
1648 ]
1649 }
1650 #[inline(always)]
1651 unsafe fn transpose11_packed(rows: [Self; 11]) -> [Self; 11] {
1652 [
1653 _mm256_permute2f128_pd(rows[0], rows[1], 0x20),
1654 _mm256_permute2f128_pd(rows[2], rows[3], 0x20),
1655 _mm256_permute2f128_pd(rows[4], rows[5], 0x20),
1656 _mm256_permute2f128_pd(rows[6], rows[7], 0x20),
1657 _mm256_permute2f128_pd(rows[8], rows[9], 0x20),
1658 _mm256_permute2f128_pd(rows[10], rows[0], 0x30),
1659 _mm256_permute2f128_pd(rows[1], rows[2], 0x31),
1660 _mm256_permute2f128_pd(rows[3], rows[4], 0x31),
1661 _mm256_permute2f128_pd(rows[5], rows[6], 0x31),
1662 _mm256_permute2f128_pd(rows[7], rows[8], 0x31),
1663 _mm256_permute2f128_pd(rows[9], rows[10], 0x31),
1664 ]
1665 }
1666 #[inline(always)]
1667 unsafe fn transpose12_packed(rows: [Self; 12]) -> [Self; 12] {
1668 let chunk0 = [rows[0], rows[1], rows[2], rows[3]];
1669 let chunk1 = [rows[4], rows[5], rows[6], rows[7]];
1670 let chunk2 = [rows[8], rows[9], rows[10], rows[11]];
1671
1672 let output0 = Self::transpose4_packed(chunk0);
1673 let output1 = Self::transpose4_packed(chunk1);
1674 let output2 = Self::transpose4_packed(chunk2);
1675
1676 [
1677 output0[0], output0[1], output1[0], output1[1], output2[0], output2[1], output0[2],
1678 output0[3], output1[2], output1[3], output2[2], output2[3],
1679 ]
1680 }
1681 #[inline(always)]
1682 unsafe fn transpose16_packed(rows: [Self; 16]) -> [Self; 16] {
1683 let chunk0 = [
1684 rows[0], rows[1], rows[2], rows[3], rows[4], rows[5], rows[6], rows[7],
1685 ];
1686 let chunk1 = [
1687 rows[8], rows[9], rows[10], rows[11], rows[12], rows[13], rows[14], rows[15],
1688 ];
1689
1690 let output0 = Self::transpose8_packed(chunk0);
1691 let output1 = Self::transpose8_packed(chunk1);
1692
1693 [
1694 output0[0], output0[1], output0[2], output0[3], output1[0], output1[1], output1[2],
1695 output1[3], output0[4], output0[5], output0[6], output0[7], output1[4], output1[5],
1696 output1[6], output1[7],
1697 ]
1698 }
1699 }
1700 impl AvxVector256 for __m256d {
1701 type ScalarType = f64;
1702 type HalfVector = __m128d;
1703
1704 #[inline(always)]
1705 unsafe fn lo(self) -> Self::HalfVector {
1706 _mm256_castpd256_pd128(self)
1707 }
1708 #[inline(always)]
1709 unsafe fn hi(self) -> Self::HalfVector {
1710 _mm256_extractf128_pd(self, 1)
1711 }
1712 #[inline(always)]
1713 unsafe fn merge(lo: Self::HalfVector, hi: Self::HalfVector) -> Self {
1714 _mm256_insertf128_pd(_mm256_castpd128_pd256(lo), hi, 1)
1715 }
1716
1717 #[inline(always)]
1718 unsafe fn broadcast_complex_elements(value: Complex<Self::ScalarType>) -> Self {
1719 _mm256_set_pd(value.im, value.re, value.im, value.re)
1720 }
1721
1722 #[inline(always)]
1723 unsafe fn hadd_complex(self) -> Complex<Self::ScalarType> {
1724 let lo = self.lo();
1725 let hi = self.hi();
1726 let sum = _mm_add_pd(lo, hi);
1727
1728 let mut result_storage = [Complex::zero(); 1];
1729 result_storage.as_mut_slice().store_partial1_complex(sum, 0);
1730 result_storage[0]
1731 }
1732
1733 #[inline(always)]
1734 unsafe fn load_complex(ptr: *const Complex<Self::ScalarType>) -> Self {
1735 _mm256_loadu_pd(ptr as *const Self::ScalarType)
1736 }
1737 #[inline(always)]
1738 unsafe fn store_complex(ptr: *mut Complex<Self::ScalarType>, data: Self) {
1739 _mm256_storeu_pd(ptr as *mut Self::ScalarType, data)
1740 }
1741 #[inline(always)]
1742 unsafe fn gather_complex_avx2_index32(
1743 ptr: *const Complex<Self::ScalarType>,
1744 indexes: __m128i,
1745 ) -> Self {
1746 let offsets = _mm_set_epi32(1, 0, 1, 0);
1747 let shifted = _mm_slli_epi32(indexes, 1);
1748 let modified_indexes = _mm_add_epi32(offsets, shifted);
1749
1750 _mm256_i32gather_pd(ptr as *const f64, modified_indexes, 8)
1751 }
1752 #[inline(always)]
1753 unsafe fn gather_complex_avx2_index64(
1754 ptr: *const Complex<Self::ScalarType>,
1755 indexes: __m256i,
1756 ) -> Self {
1757 let offsets = _mm256_set_epi64x(1, 0, 1, 0);
1758 let shifted = _mm256_slli_epi64(indexes, 1);
1759 let modified_indexes = _mm256_add_epi64(offsets, shifted);
1760
1761 _mm256_i64gather_pd(ptr as *const f64, modified_indexes, 8)
1762 }
1763 #[inline(always)]
1764 unsafe fn load_partial1_complex(ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector {
1765 _mm_loadu_pd(ptr as *const f64)
1766 }
1767 #[inline(always)]
1768 unsafe fn load_partial2_complex(_ptr: *const Complex<Self::ScalarType>) -> Self::HalfVector {
1769 unimplemented!("Impossible to do a partial load of 2 complex f64's")
1770 }
1771 #[inline(always)]
1772 unsafe fn load_partial3_complex(_ptr: *const Complex<Self::ScalarType>) -> Self {
1773 unimplemented!("Impossible to do a partial load of 3 complex f64's")
1774 }
1775 #[inline(always)]
1776 unsafe fn store_partial1_complex(ptr: *mut Complex<Self::ScalarType>, data: Self::HalfVector) {
1777 _mm_storeu_pd(ptr as *mut f64, data);
1778 }
1779 #[inline(always)]
1780 unsafe fn store_partial2_complex(
1781 _ptr: *mut Complex<Self::ScalarType>,
1782 _data: Self::HalfVector,
1783 ) {
1784 unimplemented!("Impossible to do a partial store of 2 complex f64's")
1785 }
1786 #[inline(always)]
1787 unsafe fn store_partial3_complex(_ptr: *mut Complex<Self::ScalarType>, _data: Self) {
1788 unimplemented!("Impossible to do a partial store of 3 complex f64's")
1789 }
1790 }
1791
1792 impl AvxVector for __m128d {
1793 const SCALAR_PER_VECTOR: usize = 2;
1794 const COMPLEX_PER_VECTOR: usize = 1;
1795
1796 #[inline(always)]
1797 unsafe fn zero() -> Self {
1798 _mm_setzero_pd()
1799 }
1800 #[inline(always)]
1801 unsafe fn half_root2() -> Self {
1802 // note: we're computing a square root here, but checking the assembly says the compiler is smart enough to turn this into a constant
1803 _mm_load1_pd(&0.5f64.sqrt())
1804 }
1805
1806 #[inline(always)]
1807 unsafe fn xor(left: Self, right: Self) -> Self {
1808 _mm_xor_pd(left, right)
1809 }
1810 #[inline(always)]
1811 unsafe fn neg(self) -> Self {
1812 _mm_xor_pd(self, _mm_load1_pd(&-0.0))
1813 }
1814 #[inline(always)]
1815 unsafe fn add(left: Self, right: Self) -> Self {
1816 _mm_add_pd(left, right)
1817 }
1818 #[inline(always)]
1819 unsafe fn sub(left: Self, right: Self) -> Self {
1820 _mm_sub_pd(left, right)
1821 }
1822 #[inline(always)]
1823 unsafe fn mul(left: Self, right: Self) -> Self {
1824 _mm_mul_pd(left, right)
1825 }
1826 #[inline(always)]
1827 unsafe fn fmadd(left: Self, right: Self, add: Self) -> Self {
1828 _mm_fmadd_pd(left, right, add)
1829 }
1830 #[inline(always)]
1831 unsafe fn fnmadd(left: Self, right: Self, add: Self) -> Self {
1832 _mm_fnmadd_pd(left, right, add)
1833 }
1834 #[inline(always)]
1835 unsafe fn fmaddsub(left: Self, right: Self, add: Self) -> Self {
1836 _mm_fmaddsub_pd(left, right, add)
1837 }
1838 #[inline(always)]
1839 unsafe fn fmsubadd(left: Self, right: Self, add: Self) -> Self {
1840 _mm_fmsubadd_pd(left, right, add)
1841 }
1842
1843 #[inline(always)]
1844 unsafe fn reverse_complex_elements(self) -> Self {
1845 // nothing to reverse
1846 self
1847 }
1848 #[inline(always)]
1849 unsafe fn unpacklo_complex(_rows: [Self; 2]) -> Self {
1850 unimplemented!(); // this operation doesn't make sense with one element. TODO: I don't know if it would be more useful to error here or to just return the inputs unchanged. If returning the inputs is useful, do that.
1851 }
1852 #[inline(always)]
1853 unsafe fn unpackhi_complex(_rows: [Self; 2]) -> Self {
1854 unimplemented!(); // this operation doesn't make sense with one element. TODO: I don't know if it would be more useful to error here or to just return the inputs unchanged. If returning the inputs is useful, do that.
1855 }
1856
1857 #[inline(always)]
1858 unsafe fn swap_complex_components(self) -> Self {
1859 _mm_permute_pd(self, 0x01)
1860 }
1861 #[inline(always)]
1862 unsafe fn duplicate_complex_components(self) -> (Self, Self) {
1863 (_mm_movedup_pd(self), _mm_permute_pd(self, 0x03))
1864 }
1865
1866 #[inline(always)]
1867 unsafe fn make_rotation90(direction: FftDirection) -> Rotation90<Self> {
1868 let broadcast = match direction {
1869 FftDirection::Forward => Complex::new(-0.0, 0.0),
1870 FftDirection::Inverse => Complex::new(0.0, -0.0),
1871 };
1872 Rotation90(Self::broadcast_complex_elements(broadcast))
1873 }
1874 #[inline(always)]
1875 unsafe fn make_mixedradix_twiddle_chunk(
1876 x: usize,
1877 y: usize,
1878 len: usize,
1879 direction: FftDirection,
1880 ) -> Self {
1881 let mut twiddle_chunk = [Complex::<f64>::zero(); Self::COMPLEX_PER_VECTOR];
1882 for i in 0..Self::COMPLEX_PER_VECTOR {
1883 twiddle_chunk[i] = twiddles::compute_twiddle(y * (x + i), len, direction);
1884 }
1885
1886 _mm_loadu_pd(twiddle_chunk.as_ptr() as *const f64)
1887 }
1888 #[inline(always)]
1889 unsafe fn broadcast_twiddle(index: usize, len: usize, direction: FftDirection) -> Self {
1890 Self::broadcast_complex_elements(twiddles::compute_twiddle(index, len, direction))
1891 }
1892
1893 #[inline(always)]
1894 unsafe fn transpose2_packed(rows: [Self; 2]) -> [Self; 2] {
1895 rows
1896 }
1897 #[inline(always)]
1898 unsafe fn transpose3_packed(rows: [Self; 3]) -> [Self; 3] {
1899 rows
1900 }
1901 #[inline(always)]
1902 unsafe fn transpose4_packed(rows: [Self; 4]) -> [Self; 4] {
1903 rows
1904 }
1905 #[inline(always)]
1906 unsafe fn transpose5_packed(rows: [Self; 5]) -> [Self; 5] {
1907 rows
1908 }
1909 #[inline(always)]
1910 unsafe fn transpose6_packed(rows: [Self; 6]) -> [Self; 6] {
1911 rows
1912 }
1913 #[inline(always)]
1914 unsafe fn transpose7_packed(rows: [Self; 7]) -> [Self; 7] {
1915 rows
1916 }
1917 #[inline(always)]
1918 unsafe fn transpose8_packed(rows: [Self; 8]) -> [Self; 8] {
1919 rows
1920 }
1921 #[inline(always)]
1922 unsafe fn transpose9_packed(rows: [Self; 9]) -> [Self; 9] {
1923 rows
1924 }
1925 #[inline(always)]
1926 unsafe fn transpose11_packed(rows: [Self; 11]) -> [Self; 11] {
1927 rows
1928 }
1929 #[inline(always)]
1930 unsafe fn transpose12_packed(rows: [Self; 12]) -> [Self; 12] {
1931 rows
1932 }
1933 #[inline(always)]
1934 unsafe fn transpose16_packed(rows: [Self; 16]) -> [Self; 16] {
1935 rows
1936 }
1937 }
1938 impl AvxVector128 for __m128d {
1939 type FullVector = __m256d;
1940
1941 #[inline(always)]
1942 unsafe fn lo(input: Self::FullVector) -> Self {
1943 _mm256_castpd256_pd128(input)
1944 }
1945 #[inline(always)]
1946 unsafe fn hi(input: Self::FullVector) -> Self {
1947 _mm256_extractf128_pd(input, 1)
1948 }
1949 #[inline(always)]
1950 unsafe fn merge(lo: Self, hi: Self) -> Self::FullVector {
1951 _mm256_insertf128_pd(_mm256_castpd128_pd256(lo), hi, 1)
1952 }
1953 #[inline(always)]
1954 unsafe fn zero_extend(self) -> Self::FullVector {
1955 _mm256_zextpd128_pd256(self)
1956 }
1957 #[inline(always)]
1958 unsafe fn lo_rotation(input: Rotation90<Self::FullVector>) -> Rotation90<Self> {
1959 input.lo()
1960 }
1961 #[inline(always)]
1962 unsafe fn broadcast_complex_elements(value: Complex<f64>) -> Self {
1963 _mm_set_pd(value.im, value.re)
1964 }
1965 #[inline(always)]
1966 unsafe fn gather32_complex_avx2(ptr: *const Complex<f64>, indexes: __m128i) -> Self {
1967 let mut index_storage: [i32; 4] = [0; 4];
1968 _mm_storeu_si128(index_storage.as_mut_ptr() as *mut __m128i, indexes);
1969
1970 _mm_loadu_pd(ptr.offset(index_storage[0] as isize) as *const f64)
1971 }
1972 #[inline(always)]
1973 unsafe fn gather64_complex_avx2(ptr: *const Complex<f64>, indexes: __m128i) -> Self {
1974 let mut index_storage: [i64; 4] = [0; 4];
1975 _mm_storeu_si128(index_storage.as_mut_ptr() as *mut __m128i, indexes);
1976
1977 _mm_loadu_pd(ptr.offset(index_storage[0] as isize) as *const f64)
1978 }
1979 }
1980
1981 pub trait AvxArray<T: AvxNum>: Deref {
1982 unsafe fn load_complex(&self, index: usize) -> T::VectorType;
1983 unsafe fn load_partial1_complex(
1984 &self,
1985 index: usize,
1986 ) -> <T::VectorType as AvxVector256>::HalfVector;
1987 unsafe fn load_partial2_complex(
1988 &self,
1989 index: usize,
1990 ) -> <T::VectorType as AvxVector256>::HalfVector;
1991 unsafe fn load_partial3_complex(&self, index: usize) -> T::VectorType;
1992
1993 // some avx operations need bespoke one-off things that don't fit into the methods above, so we should provide an escape hatch for them
1994 fn input_ptr(&self) -> *const Complex<T>;
1995 }
1996 pub trait AvxArrayMut<T: AvxNum>: AvxArray<T> + DerefMut {
1997 unsafe fn store_complex(&mut self, data: T::VectorType, index: usize);
1998 unsafe fn store_partial1_complex(
1999 &mut self,
2000 data: <T::VectorType as AvxVector256>::HalfVector,
2001 index: usize,
2002 );
2003 unsafe fn store_partial2_complex(
2004 &mut self,
2005 data: <T::VectorType as AvxVector256>::HalfVector,
2006 index: usize,
2007 );
2008 unsafe fn store_partial3_complex(&mut self, data: T::VectorType, index: usize);
2009
2010 // some avx operations need bespoke one-off things that don't fit into the methods above, so we should provide an escape hatch for them
2011 fn output_ptr(&mut self) -> *mut Complex<T>;
2012 }
2013
2014 impl<T: AvxNum> AvxArray<T> for &[Complex<T>] {
2015 #[inline(always)]
2016 unsafe fn load_complex(&self, index: usize) -> T::VectorType {
2017 debug_assert!(self.len() >= index + T::VectorType::COMPLEX_PER_VECTOR);
2018 T::VectorType::load_complex(self.as_ptr().add(index))
2019 }
2020 #[inline(always)]
2021 unsafe fn load_partial1_complex(
2022 &self,
2023 index: usize,
2024 ) -> <T::VectorType as AvxVector256>::HalfVector {
2025 debug_assert!(self.len() >= index + 1);
2026 T::VectorType::load_partial1_complex(self.as_ptr().add(index))
2027 }
2028 #[inline(always)]
2029 unsafe fn load_partial2_complex(
2030 &self,
2031 index: usize,
2032 ) -> <T::VectorType as AvxVector256>::HalfVector {
2033 debug_assert!(self.len() >= index + 2);
2034 T::VectorType::load_partial2_complex(self.as_ptr().add(index))
2035 }
2036 #[inline(always)]
2037 unsafe fn load_partial3_complex(&self, index: usize) -> T::VectorType {
2038 debug_assert!(self.len() >= index + 3);
2039 T::VectorType::load_partial3_complex(self.as_ptr().add(index))
2040 }
2041 #[inline(always)]
2042 fn input_ptr(&self) -> *const Complex<T> {
2043 self.as_ptr()
2044 }
2045 }
2046 impl<T: AvxNum> AvxArray<T> for &mut [Complex<T>] {
2047 #[inline(always)]
2048 unsafe fn load_complex(&self, index: usize) -> T::VectorType {
2049 debug_assert!(self.len() >= index + T::VectorType::COMPLEX_PER_VECTOR);
2050 T::VectorType::load_complex(self.as_ptr().add(index))
2051 }
2052 #[inline(always)]
2053 unsafe fn load_partial1_complex(
2054 &self,
2055 index: usize,
2056 ) -> <T::VectorType as AvxVector256>::HalfVector {
2057 debug_assert!(self.len() >= index + 1);
2058 T::VectorType::load_partial1_complex(self.as_ptr().add(index))
2059 }
2060 #[inline(always)]
2061 unsafe fn load_partial2_complex(
2062 &self,
2063 index: usize,
2064 ) -> <T::VectorType as AvxVector256>::HalfVector {
2065 debug_assert!(self.len() >= index + 2);
2066 T::VectorType::load_partial2_complex(self.as_ptr().add(index))
2067 }
2068 #[inline(always)]
2069 unsafe fn load_partial3_complex(&self, index: usize) -> T::VectorType {
2070 debug_assert!(self.len() >= index + 3);
2071 T::VectorType::load_partial3_complex(self.as_ptr().add(index))
2072 }
2073 #[inline(always)]
2074 fn input_ptr(&self) -> *const Complex<T> {
2075 self.as_ptr()
2076 }
2077 }
2078 impl<'a, T: AvxNum> AvxArray<T> for DoubleBuf<'a, T>
2079 where
2080 &'a [Complex<T>]: AvxArray<T>,
2081 {
2082 #[inline(always)]
2083 unsafe fn load_complex(&self, index: usize) -> T::VectorType {
2084 self.input.load_complex(index)
2085 }
2086 #[inline(always)]
2087 unsafe fn load_partial1_complex(
2088 &self,
2089 index: usize,
2090 ) -> <T::VectorType as AvxVector256>::HalfVector {
2091 self.input.load_partial1_complex(index)
2092 }
2093 #[inline(always)]
2094 unsafe fn load_partial2_complex(
2095 &self,
2096 index: usize,
2097 ) -> <T::VectorType as AvxVector256>::HalfVector {
2098 self.input.load_partial2_complex(index)
2099 }
2100 #[inline(always)]
2101 unsafe fn load_partial3_complex(&self, index: usize) -> T::VectorType {
2102 self.input.load_partial3_complex(index)
2103 }
2104 #[inline(always)]
2105 fn input_ptr(&self) -> *const Complex<T> {
2106 self.input.input_ptr()
2107 }
2108 }
2109
2110 impl<T: AvxNum> AvxArrayMut<T> for &mut [Complex<T>] {
2111 #[inline(always)]
2112 unsafe fn store_complex(&mut self, data: T::VectorType, index: usize) {
2113 debug_assert!(self.len() >= index + T::VectorType::COMPLEX_PER_VECTOR);
2114 T::VectorType::store_complex(self.as_mut_ptr().add(index), data);
2115 }
2116 #[inline(always)]
2117 unsafe fn store_partial1_complex(
2118 &mut self,
2119 data: <T::VectorType as AvxVector256>::HalfVector,
2120 index: usize,
2121 ) {
2122 debug_assert!(self.len() >= index + 1);
2123 T::VectorType::store_partial1_complex(self.as_mut_ptr().add(index), data);
2124 }
2125 #[inline(always)]
2126 unsafe fn store_partial2_complex(
2127 &mut self,
2128 data: <T::VectorType as AvxVector256>::HalfVector,
2129 index: usize,
2130 ) {
2131 debug_assert!(self.len() >= index + 2);
2132 T::VectorType::store_partial2_complex(self.as_mut_ptr().add(index), data);
2133 }
2134 #[inline(always)]
2135 unsafe fn store_partial3_complex(&mut self, data: T::VectorType, index: usize) {
2136 debug_assert!(self.len() >= index + 3);
2137 T::VectorType::store_partial3_complex(self.as_mut_ptr().add(index), data);
2138 }
2139 #[inline(always)]
2140 fn output_ptr(&mut self) -> *mut Complex<T> {
2141 self.as_mut_ptr()
2142 }
2143 }
2144 impl<'a, T: AvxNum> AvxArrayMut<T> for DoubleBuf<'a, T>
2145 where
2146 Self: AvxArray<T>,
2147 &'a mut [Complex<T>]: AvxArrayMut<T>,
2148 {
2149 #[inline(always)]
2150 unsafe fn store_complex(&mut self, data: T::VectorType, index: usize) {
2151 self.output.store_complex(data, index);
2152 }
2153 #[inline(always)]
2154 unsafe fn store_partial1_complex(
2155 &mut self,
2156 data: <T::VectorType as AvxVector256>::HalfVector,
2157 index: usize,
2158 ) {
2159 self.output.store_partial1_complex(data, index);
2160 }
2161 #[inline(always)]
2162 unsafe fn store_partial2_complex(
2163 &mut self,
2164 data: <T::VectorType as AvxVector256>::HalfVector,
2165 index: usize,
2166 ) {
2167 self.output.store_partial2_complex(data, index);
2168 }
2169 #[inline(always)]
2170 unsafe fn store_partial3_complex(&mut self, data: T::VectorType, index: usize) {
2171 self.output.store_partial3_complex(data, index);
2172 }
2173 #[inline(always)]
2174 fn output_ptr(&mut self) -> *mut Complex<T> {
2175 self.output.output_ptr()
2176 }
2177 }
2178
2179 // A custom butterfly-16 function that calls a lambda to load/store data instead of taking an array
2180 // This is particularly useful for butterfly 16, because the whole problem doesn't fit into registers, and the compiler isn't smart enough to only load data when it's needed
2181 // So the version that takes an array ends up loading data and immediately re-storing it on the stack. By lazily loading and storing exactly when we need to, we can avoid some data reshuffling
2182 macro_rules! column_butterfly16_loadfn{
2183 ($load_expr: expr, $store_expr: expr, $twiddles: expr, $rotation: expr) => (
2184 // Size-4 FFTs down the columns
2185 let input1 = [$load_expr(1), $load_expr(5), $load_expr(9), $load_expr(13)];
2186 let mut mid1 = AvxVector::column_butterfly4(input1, $rotation);
2187
2188 mid1[1] = AvxVector::mul_complex(mid1[1], $twiddles[0]);
2189 mid1[2] = avx_vector::apply_butterfly8_twiddle1(mid1[2], $rotation);
2190 mid1[3] = AvxVector::mul_complex(mid1[3], $twiddles[1]);
2191
2192 let input2 = [$load_expr(2), $load_expr(6), $load_expr(10), $load_expr(14)];
2193 let mut mid2 = AvxVector::column_butterfly4(input2, $rotation);
2194
2195 mid2[1] = avx_vector::apply_butterfly8_twiddle1(mid2[1], $rotation);
2196 mid2[2] = mid2[2].rotate90($rotation);
2197 mid2[3] = avx_vector::apply_butterfly8_twiddle3(mid2[3], $rotation);
2198
2199 let input3 = [$load_expr(3), $load_expr(7), $load_expr(11), $load_expr(15)];
2200 let mut mid3 = AvxVector::column_butterfly4(input3, $rotation);
2201
2202 mid3[1] = AvxVector::mul_complex(mid3[1], $twiddles[1]);
2203 mid3[2] = avx_vector::apply_butterfly8_twiddle3(mid3[2], $rotation);
2204 mid3[3] = AvxVector::mul_complex(mid3[3], $twiddles[0].neg());
2205
2206 // do the first row last, because it doesn't need twiddles and therefore requires fewer intermediates
2207 let input0 = [$load_expr(0), $load_expr(4), $load_expr(8), $load_expr(12)];
2208 let mid0 = AvxVector::column_butterfly4(input0, $rotation);
2209
2210 // All of the data is now in the right format to just do a bunch of butterfly 8's.
2211 // Write the data out to the final output as we go so that the compiler can stop worrying about finding stack space for it
2212 for i in 0..4 {
2213 let output = AvxVector::column_butterfly4([mid0[i], mid1[i], mid2[i], mid3[i]], $rotation);
2214 $store_expr(output[0], i);
2215 $store_expr(output[1], i + 4);
2216 $store_expr(output[2], i + 8);
2217 $store_expr(output[3], i + 12);
2218 }
2219 )
2220 }
2221
2222 // A custom butterfly-32 function that calls a lambda to load/store data instead of taking an array
2223 // This is particularly useful for butterfly 32, because the whole problem doesn't fit into registers, and the compiler isn't smart enough to only load data when it's needed
2224 // So the version that takes an array ends up loading data and immediately re-storing it on the stack. By lazily loading and storing exactly when we need to, we can avoid some data reshuffling
2225 macro_rules! column_butterfly32_loadfn{
2226 ($load_expr: expr, $store_expr: expr, $twiddles: expr, $rotation: expr) => (
2227 // Size-4 FFTs down the columns
2228 let input1 = [$load_expr(1), $load_expr(9), $load_expr(17), $load_expr(25)];
2229 let mut mid1 = AvxVector::column_butterfly4(input1, $rotation);
2230
2231 mid1[1] = AvxVector::mul_complex(mid1[1], $twiddles[0]);
2232 mid1[2] = AvxVector::mul_complex(mid1[2], $twiddles[1]);
2233 mid1[3] = AvxVector::mul_complex(mid1[3], $twiddles[2]);
2234
2235 let input2 = [$load_expr(2), $load_expr(10), $load_expr(18), $load_expr(26)];
2236 let mut mid2 = AvxVector::column_butterfly4(input2, $rotation);
2237
2238 mid2[1] = AvxVector::mul_complex(mid2[1], $twiddles[1]);
2239 mid2[2] = avx_vector::apply_butterfly8_twiddle1(mid2[2], $rotation);
2240 mid2[3] = AvxVector::mul_complex(mid2[3], $twiddles[4]);
2241
2242 let input3 = [$load_expr(3), $load_expr(11), $load_expr(19), $load_expr(27)];
2243 let mut mid3 = AvxVector::column_butterfly4(input3, $rotation);
2244
2245 mid3[1] = AvxVector::mul_complex(mid3[1], $twiddles[2]);
2246 mid3[2] = AvxVector::mul_complex(mid3[2], $twiddles[4]);
2247 mid3[3] = AvxVector::mul_complex(mid3[3], $twiddles[0].rotate90($rotation));
2248
2249 let input4 = [$load_expr(4), $load_expr(12), $load_expr(20), $load_expr(28)];
2250 let mut mid4 = AvxVector::column_butterfly4(input4, $rotation);
2251
2252 mid4[1] = avx_vector::apply_butterfly8_twiddle1(mid4[1], $rotation);
2253 mid4[2] = mid4[2].rotate90($rotation);
2254 mid4[3] = avx_vector::apply_butterfly8_twiddle3(mid4[3], $rotation);
2255
2256 let input5 = [$load_expr(5), $load_expr(13), $load_expr(21), $load_expr(29)];
2257 let mut mid5 = AvxVector::column_butterfly4(input5, $rotation);
2258
2259 mid5[1] = AvxVector::mul_complex(mid5[1], $twiddles[3]);
2260 mid5[2] = AvxVector::mul_complex(mid5[2], $twiddles[1].rotate90($rotation));
2261 mid5[3] = AvxVector::mul_complex(mid5[3], $twiddles[5].rotate90($rotation));
2262
2263 let input6 = [$load_expr(6), $load_expr(14), $load_expr(22), $load_expr(30)];
2264 let mut mid6 = AvxVector::column_butterfly4(input6, $rotation);
2265
2266 mid6[1] = AvxVector::mul_complex(mid6[1], $twiddles[4]);
2267 mid6[2] = avx_vector::apply_butterfly8_twiddle3(mid6[2], $rotation);
2268 mid6[3] = AvxVector::mul_complex(mid6[3], $twiddles[1].neg());
2269
2270 let input7 = [$load_expr(7), $load_expr(15), $load_expr(23), $load_expr(31)];
2271 let mut mid7 = AvxVector::column_butterfly4(input7, $rotation);
2272
2273 mid7[1] = AvxVector::mul_complex(mid7[1], $twiddles[5]);
2274 mid7[2] = AvxVector::mul_complex(mid7[2], $twiddles[4].rotate90($rotation));
2275 mid7[3] = AvxVector::mul_complex(mid7[3], $twiddles[3].neg());
2276
2277 let input0 = [$load_expr(0), $load_expr(8), $load_expr(16), $load_expr(24)];
2278 let mid0 = AvxVector::column_butterfly4(input0, $rotation);
2279
2280 // All of the data is now in the right format to just do a bunch of butterfly 8's in a loop.
2281 // Write the data out to the final output as we go so that the compiler can stop worrying about finding stack space for it
2282 for i in 0..4 {
2283 let output = AvxVector::column_butterfly8([mid0[i], mid1[i], mid2[i], mid3[i], mid4[i], mid5[i], mid6[i], mid7[i]], $rotation);
2284 $store_expr(output[0], i);
2285 $store_expr(output[1], i + 4);
2286 $store_expr(output[2], i + 8);
2287 $store_expr(output[3], i + 12);
2288 $store_expr(output[4], i + 16);
2289 $store_expr(output[5], i + 20);
2290 $store_expr(output[6], i + 24);
2291 $store_expr(output[7], i + 28);
2292 }
2293 )
2294 }
2295
2296 /// Multiply the complex numbers in `left` by the complex numbers in `right`.
2297 /// This is exactly the same as `mul_complex` in `AvxVector`, but this implementation also conjugates the `left` input before multiplying
2298 #[inline(always)]
2299 unsafe fn mul_complex_conjugated<V: AvxVector>(left: V, right: V) -> V {
2300 // Extract the real and imaginary components from left into 2 separate registers
2301 let (left_real, left_imag) = V::duplicate_complex_components(left);
2302
2303 // create a shuffled version of right where the imaginary values are swapped with the reals
2304 let right_shuffled = V::swap_complex_components(right);
2305
2306 // multiply our duplicated imaginary left vector by our shuffled right vector. that will give us the right side of the traditional complex multiplication formula
2307 let output_right = V::mul(left_imag, right_shuffled);
2308
2309 // use a FMA instruction to multiply together left side of the complex multiplication formula, then alternatingly add and subtract the left side from the right
2310 // By using subadd instead of addsub, we can conjugate the left side for free.
2311 V::fmsubadd(left_real, right, output_right)
2312 }
2313
2314 // compute buffer[i] = buffer[i].conj() * multiplier[i] pairwise complex multiplication for each element.
2315 #[target_feature(enable = "avx", enable = "fma")]
2316 pub unsafe fn pairwise_complex_mul_assign_conjugated<T: AvxNum>(
2317 mut buffer: &mut [Complex<T>],
2318 multiplier: &[T::VectorType],
2319 ) {
2320 assert!(multiplier.len() * T::VectorType::COMPLEX_PER_VECTOR >= buffer.len()); // Assert to convince the compiler to omit bounds checks inside the loop
2321
2322 for (i, mut buffer_chunk) in buffer
2323 .chunks_exact_mut(T::VectorType::COMPLEX_PER_VECTOR)
2324 .enumerate()
2325 {
2326 let left = buffer_chunk.load_complex(0);
2327
2328 // Do a complex multiplication between `left` and `right`
2329 let product = mul_complex_conjugated(left, multiplier[i]);
2330
2331 // Store the result
2332 buffer_chunk.store_complex(product, 0);
2333 }
2334
2335 // Process the remainder, if there is one
2336 let remainder_count = buffer.len() % T::VectorType::COMPLEX_PER_VECTOR;
2337 if remainder_count > 0 {
2338 let remainder_index = buffer.len() - remainder_count;
2339 let remainder_multiplier = multiplier.last().unwrap();
2340 match remainder_count {
2341 1 => {
2342 let left = buffer.load_partial1_complex(remainder_index);
2343 let product = mul_complex_conjugated(left, remainder_multiplier.lo());
2344 buffer.store_partial1_complex(product, remainder_index);
2345 }
2346 2 => {
2347 let left = buffer.load_partial2_complex(remainder_index);
2348 let product = mul_complex_conjugated(left, remainder_multiplier.lo());
2349 buffer.store_partial2_complex(product, remainder_index);
2350 }
2351 3 => {
2352 let left = buffer.load_partial3_complex(remainder_index);
2353 let product = mul_complex_conjugated(left, *remainder_multiplier);
2354 buffer.store_partial3_complex(product, remainder_index);
2355 }
2356 _ => unreachable!(),
2357 }
2358 }
2359 }
2360
2361 // compute output[i] = input[i].conj() * multiplier[i] pairwise complex multiplication for each element.
2362 #[target_feature(enable = "avx", enable = "fma")]
2363 pub unsafe fn pairwise_complex_mul_conjugated<T: AvxNum>(
2364 input: &[Complex<T>],
2365 mut output: &mut [Complex<T>],
2366 multiplier: &[T::VectorType],
2367 ) {
2368 assert!(
2369 multiplier.len() * T::VectorType::COMPLEX_PER_VECTOR >= input.len(),
2370 "multiplier len = {}, input len = {}",
2371 multiplier.len(),
2372 input.len()
2373 ); // Assert to convince the compiler to omit bounds checks inside the loop
2374 assert!(input.len() == output.len()); // Assert to convince the compiler to omit bounds checks inside the loop
2375 let main_loop_count = input.len() / T::VectorType::COMPLEX_PER_VECTOR;
2376 let remainder_count = input.len() % T::VectorType::COMPLEX_PER_VECTOR;
2377
2378 for (i, m) in (&multiplier[..main_loop_count]).iter().enumerate() {
2379 let left = input.load_complex(i * T::VectorType::COMPLEX_PER_VECTOR);
2380
2381 // Do a complex multiplication between `left` and `right`
2382 let product = mul_complex_conjugated(left, *m);
2383
2384 // Store the result
2385 output.store_complex(product, i * T::VectorType::COMPLEX_PER_VECTOR);
2386 }
2387
2388 // Process the remainder, if there is one
2389 if remainder_count > 0 {
2390 let remainder_index = input.len() - remainder_count;
2391 let remainder_multiplier = multiplier.last().unwrap();
2392 match remainder_count {
2393 1 => {
2394 let left = input.load_partial1_complex(remainder_index);
2395 let product = mul_complex_conjugated(left, remainder_multiplier.lo());
2396 output.store_partial1_complex(product, remainder_index);
2397 }
2398 2 => {
2399 let left = input.load_partial2_complex(remainder_index);
2400 let product = mul_complex_conjugated(left, remainder_multiplier.lo());
2401 output.store_partial2_complex(product, remainder_index);
2402 }
2403 3 => {
2404 let left = input.load_partial3_complex(remainder_index);
2405 let product = mul_complex_conjugated(left, *remainder_multiplier);
2406 output.store_partial3_complex(product, remainder_index);
2407 }
2408 _ => unreachable!(),
2409 }
2410 }
2411 }