Debian Codegraph @

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

raw
1 use std::any::TypeId;
2 use std::sync::Arc;
3
4 use num_complex::Complex;
5 use num_integer::div_ceil;
6 use num_traits::Zero;
7
8 use crate::common::{fft_error_inplace, fft_error_outofplace};
9 use crate::{array_utils, twiddles, FftDirection};
10 use crate::{Direction, Fft, FftNum, Length};
11
12 use super::CommonSimdData;
13 use super::{
14 avx_vector::{AvxArray, AvxArrayMut, AvxVector, AvxVector128, AvxVector256},
15 AvxNum,
16 };
17
18 /// Implementation of Bluestein's Algorithm
19 ///
20 /// This algorithm computes an arbitrary-sized FFT in O(nlogn) time. It does this by converting this size n FFT into a
21 /// size M where M >= 2N - 1. The most obvious choice for M is a power of two, although that isn't a requirement.
22 ///
23 /// It requires a large scratch space, so it's probably inconvenient to use as an inner FFT to other algorithms.
24 ///
25 /// Bluestein's Algorithm is relatively expensive compared to other FFT algorithms. Benchmarking shows that it is up to
26 /// an order of magnitude slower than similar composite sizes.
27
28 pub struct BluesteinsAvx<A: AvxNum, T> {
29 inner_fft_multiplier: Box<[A::VectorType]>,
30 common_data: CommonSimdData<T, A::VectorType>,
31 _phantom: std::marker::PhantomData<T>,
32 }
33 boilerplate_avx_fft_commondata!(BluesteinsAvx);
34
35 impl<A: AvxNum, T: FftNum> BluesteinsAvx<A, T> {
36 /// Pairwise multiply the complex numbers in `left` with the complex numbers in `right`.
37 /// This is exactly the same as `mul_complex` in `AvxVector`, but this implementation also conjugates the `left` input before multiplying
38 #[inline(always)]
39 unsafe fn mul_complex_conjugated<V: AvxVector>(left: V, right: V) -> V {
40 // Extract the real and imaginary components from left into 2 separate registers
41 let (left_real, left_imag) = V::duplicate_complex_components(left);
42
43 // create a shuffled version of right where the imaginary values are swapped with the reals
44 let right_shuffled = V::swap_complex_components(right);
45
46 // multiply our duplicated imaginary left vector by our shuffled right vector. that will give us the right side of the traditional complex multiplication formula
47 let output_right = V::mul(left_imag, right_shuffled);
48
49 // 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
50 // By using subadd instead of addsub, we can conjugate the left side for free.
51 V::fmsubadd(left_real, right, output_right)
52 }
53
54 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute the FFT
55 /// Returns Ok() if this machine has the required instruction sets, Err() if some instruction sets are missing
56 #[inline]
57 pub fn new(len: usize, inner_fft: Arc<dyn Fft<T>>) -> Result<Self, ()> {
58 // Internal sanity check: Make sure that A == T.
59 // This struct has two generic parameters A and T, but they must always be the same, and are only kept separate to help work around the lack of specialization.
60 // It would be cool if we could do this as a static_assert instead
61 let id_a = TypeId::of::<A>();
62 let id_t = TypeId::of::<T>();
63 assert_eq!(id_a, id_t);
64
65 let has_avx = is_x86_feature_detected!("avx");
66 let has_fma = is_x86_feature_detected!("fma");
67 if has_avx && has_fma {
68 // Safety: new_with_avx requires the "avx" feature set. Since we know it's present, we're safe
69 Ok(unsafe { Self::new_with_avx(len, inner_fft) })
70 } else {
71 Err(())
72 }
73 }
74
75 #[target_feature(enable = "avx")]
76 unsafe fn new_with_avx(len: usize, inner_fft: Arc<dyn Fft<T>>) -> Self {
77 let inner_fft_len = inner_fft.len();
78 assert!(len * 2 - 1 <= inner_fft_len, "Bluestein's algorithm requires inner_fft.len() >= self.len() * 2 - 1. Expected >= {}, got {}", len * 2 - 1, inner_fft_len);
79 assert_eq!(inner_fft_len % A::VectorType::COMPLEX_PER_VECTOR, 0, "BluesteinsAvx requires its inner_fft.len() to be a multiple of {} (IE the number of complex numbers in a single vector) inner_fft.len() = {}", A::VectorType::COMPLEX_PER_VECTOR, inner_fft_len);
80
81 // when computing FFTs, we're going to run our inner multiply pairwise by some precomputed data, then run an inverse inner FFT. We need to precompute that inner data here
82 let inner_fft_scale = A::one() / A::from_usize(inner_fft_len).unwrap();
83 let direction = inner_fft.fft_direction();
84
85 // Compute twiddle factors that we'll run our inner FFT on
86 let mut inner_fft_input = vec![Complex::zero(); inner_fft_len];
87 twiddles::fill_bluesteins_twiddles(
88 &mut inner_fft_input[..len],
89 direction.opposite_direction(),
90 );
91
92 // Scale the computed twiddles and copy them to the end of the array
93 inner_fft_input[0] = inner_fft_input[0] * inner_fft_scale;
94 for i in 1..len {
95 let twiddle = inner_fft_input[i] * inner_fft_scale;
96 inner_fft_input[i] = twiddle;
97 inner_fft_input[inner_fft_len - i] = twiddle;
98 }
99
100 //Compute the inner fft
101 let mut inner_fft_scratch = vec![Complex::zero(); inner_fft.get_inplace_scratch_len()];
102
103 {
104 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
105 let transmuted_input: &mut [Complex<T>] =
106 array_utils::workaround_transmute_mut(&mut inner_fft_input);
107
108 inner_fft.process_with_scratch(transmuted_input, &mut inner_fft_scratch);
109 }
110
111 // When computing the FFT, we'll want this array to be pre-conjugated, so conjugate it now
112 let conjugation_mask =
113 AvxVector256::broadcast_complex_elements(Complex::new(A::zero(), -A::zero()));
114 let inner_fft_multiplier = inner_fft_input
115 .chunks_exact(A::VectorType::COMPLEX_PER_VECTOR)
116 .map(|chunk| {
117 let chunk_vector = chunk.load_complex(0);
118 AvxVector::xor(chunk_vector, conjugation_mask) // compute our conjugation by xoring our data with a precomputed mask
119 })
120 .collect::<Vec<_>>()
121 .into_boxed_slice();
122
123 // also compute some more mundane twiddle factors to start and end with.
124 let chunk_count = div_ceil(len, A::VectorType::COMPLEX_PER_VECTOR);
125 let twiddle_count = chunk_count * A::VectorType::COMPLEX_PER_VECTOR;
126 let mut twiddles_scalar: Vec<Complex<A>> = vec![Complex::zero(); twiddle_count];
127 twiddles::fill_bluesteins_twiddles(&mut twiddles_scalar[..len], direction);
128
129 // We have the twiddles in scalar format, last step is to copy them over to AVX vectors
130 let twiddles: Vec<_> = twiddles_scalar
131 .chunks_exact(A::VectorType::COMPLEX_PER_VECTOR)
132 .map(|chunk| chunk.load_complex(0))
133 .collect();
134
135 let required_scratch = inner_fft_input.len() + inner_fft_scratch.len();
136
137 Self {
138 inner_fft_multiplier,
139 common_data: CommonSimdData {
140 inner_fft,
141 twiddles: twiddles.into_boxed_slice(),
142
143 len,
144
145 inplace_scratch_len: required_scratch,
146 outofplace_scratch_len: required_scratch,
147
148 direction,
149 },
150 _phantom: std::marker::PhantomData,
151 }
152 }
153
154 // Do the necessary setup for bluestein's algorithm: copy the data to the inner buffers, apply some twiddle factors, zero out the rest of the inner buffer
155 #[target_feature(enable = "avx", enable = "fma")]
156 unsafe fn prepare_bluesteins(
157 &self,
158 input: &[Complex<A>],
159 mut inner_fft_buffer: &mut [Complex<A>],
160 ) {
161 let chunk_count = self.common_data.twiddles.len() - 1;
162 let remainder = self.len() - chunk_count * A::VectorType::COMPLEX_PER_VECTOR;
163
164 // Copy the buffer into our inner FFT input, applying twiddle factors as we go. the buffer will only fill part of the FFT input, so zero fill the rest
165 for (i, twiddle) in self.common_data.twiddles[..chunk_count].iter().enumerate() {
166 let index = i * A::VectorType::COMPLEX_PER_VECTOR;
167 let input_vector = input.load_complex(index);
168 let product_vector = AvxVector::mul_complex(input_vector, *twiddle);
169 inner_fft_buffer.store_complex(product_vector, index);
170 }
171
172 // the buffer will almost certainly have a remainder. it's so likely, in fact, that we're just going to apply a remainder unconditionally
173 // it uses a couple more instructions in the rare case when our FFT size is a multiple of 4, but saves instructions when it's not
174 {
175 let remainder_twiddle = self.common_data.twiddles[chunk_count];
176
177 let remainder_index = chunk_count * A::VectorType::COMPLEX_PER_VECTOR;
178 let remainder_data = match remainder {
179 1 => input.load_partial1_complex(remainder_index).zero_extend(),
180 2 => {
181 if A::VectorType::COMPLEX_PER_VECTOR == 2 {
182 input.load_complex(remainder_index)
183 } else {
184 input.load_partial2_complex(remainder_index).zero_extend()
185 }
186 }
187 3 => input.load_partial3_complex(remainder_index),
188 4 => input.load_complex(remainder_index),
189 _ => unreachable!(),
190 };
191
192 let twiddled_remainder = AvxVector::mul_complex(remainder_twiddle, remainder_data);
193 inner_fft_buffer.store_complex(twiddled_remainder, remainder_index);
194 }
195
196 // zero fill the rest of the `inner` array
197 let zerofill_start = chunk_count + 1;
198 for i in zerofill_start..(inner_fft_buffer.len() / A::VectorType::COMPLEX_PER_VECTOR) {
199 let index = i * A::VectorType::COMPLEX_PER_VECTOR;
200 inner_fft_buffer.store_complex(AvxVector::zero(), index);
201 }
202 }
203
204 // Do the necessary finalization for bluestein's algorithm: Conjugate the inner FFT buffer, apply some twiddle factors, zero out the rest of the inner buffer
205 #[target_feature(enable = "avx", enable = "fma")]
206 unsafe fn finalize_bluesteins(
207 &self,
208 inner_fft_buffer: &[Complex<A>],
209 mut output: &mut [Complex<A>],
210 ) {
211 let chunk_count = self.common_data.twiddles.len() - 1;
212 let remainder = self.len() - chunk_count * A::VectorType::COMPLEX_PER_VECTOR;
213
214 // copy our data to the output, applying twiddle factors again as we go. Also conjugate inner_fft_buffer to complete the inverse FFT
215 for (i, twiddle) in self.common_data.twiddles[..chunk_count].iter().enumerate() {
216 let index = i * A::VectorType::COMPLEX_PER_VECTOR;
217 let inner_vector = inner_fft_buffer.load_complex(index);
218 let product_vector = Self::mul_complex_conjugated(inner_vector, *twiddle);
219 output.store_complex(product_vector, index);
220 }
221
222 // again, unconditionally apply a remainder
223 {
224 let remainder_twiddle = self.common_data.twiddles[chunk_count];
225
226 let remainder_index = chunk_count * A::VectorType::COMPLEX_PER_VECTOR;
227 let inner_vector = inner_fft_buffer.load_complex(remainder_index);
228 let product_vector = Self::mul_complex_conjugated(inner_vector, remainder_twiddle);
229
230 match remainder {
231 1 => output.store_partial1_complex(product_vector.lo(), remainder_index),
232 2 => {
233 if A::VectorType::COMPLEX_PER_VECTOR == 2 {
234 output.store_complex(product_vector, remainder_index)
235 } else {
236 output.store_partial2_complex(product_vector.lo(), remainder_index)
237 }
238 }
239 3 => output.store_partial3_complex(product_vector, remainder_index),
240 4 => output.store_complex(product_vector, remainder_index),
241 _ => unreachable!(),
242 };
243 }
244 }
245
246 // compute buffer[i] = buffer[i].conj() * multiplier[i] pairwise complex multiplication for each element.
247 #[target_feature(enable = "avx", enable = "fma")]
248 unsafe fn pairwise_complex_multiply_conjugated(
249 mut buffer: impl AvxArrayMut<A>,
250 multiplier: &[A::VectorType],
251 ) {
252 for (i, right) in multiplier.iter().enumerate() {
253 let left = buffer.load_complex(i * A::VectorType::COMPLEX_PER_VECTOR);
254
255 // Do a complex multiplication between `left` and `right`
256 let product = Self::mul_complex_conjugated(left, *right);
257
258 // Store the result
259 buffer.store_complex(product, i * A::VectorType::COMPLEX_PER_VECTOR);
260 }
261 }
262
263 fn perform_fft_inplace(&self, buffer: &mut [Complex<T>], scratch: &mut [Complex<T>]) {
264 let (inner_input, inner_scratch) = scratch
265 .split_at_mut(self.inner_fft_multiplier.len() * A::VectorType::COMPLEX_PER_VECTOR);
266
267 // do the necessary setup for bluestein's algorithm: copy the data to the inner buffers, apply some twiddle factors, zero out the rest of the inner buffer
268 unsafe {
269 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
270 let transmuted_buffer: &mut [Complex<A>] =
271 array_utils::workaround_transmute_mut(buffer);
272 let transmuted_inner_input: &mut [Complex<A>] =
273 array_utils::workaround_transmute_mut(inner_input);
274
275 self.prepare_bluesteins(transmuted_buffer, transmuted_inner_input);
276 }
277
278 // run our inner forward FFT
279 self.common_data
280 .inner_fft
281 .process_with_scratch(inner_input, inner_scratch);
282
283 // Multiply our inner FFT output by our precomputed data. Then, conjugate the result to set up for an inverse FFT.
284 // We can conjugate the result of multiplication by conjugating both inputs. We pre-conjugated the multiplier array,
285 // so we just need to conjugate inner_input, which the pairwise_complex_multiply_conjugated function will handle
286 unsafe {
287 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
288 let transmuted_inner_input: &mut [Complex<A>] =
289 array_utils::workaround_transmute_mut(inner_input);
290
291 Self::pairwise_complex_multiply_conjugated(
292 transmuted_inner_input,
293 &self.inner_fft_multiplier,
294 )
295 };
296
297 // inverse FFT. we're computing a forward but we're massaging it into an inverse by conjugating the inputs and outputs
298 self.common_data
299 .inner_fft
300 .process_with_scratch(inner_input, inner_scratch);
301
302 // finalize the result
303 unsafe {
304 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
305 let transmuted_buffer: &mut [Complex<A>] =
306 array_utils::workaround_transmute_mut(buffer);
307 let transmuted_inner_input: &mut [Complex<A>] =
308 array_utils::workaround_transmute_mut(inner_input);
309
310 self.finalize_bluesteins(transmuted_inner_input, transmuted_buffer);
311 }
312 }
313
314 fn perform_fft_out_of_place(
315 &self,
316 input: &[Complex<T>],
317 output: &mut [Complex<T>],
318 scratch: &mut [Complex<T>],
319 ) {
320 let (inner_input, inner_scratch) = scratch
321 .split_at_mut(self.inner_fft_multiplier.len() * A::VectorType::COMPLEX_PER_VECTOR);
322
323 // do the necessary setup for bluestein's algorithm: copy the data to the inner buffers, apply some twiddle factors, zero out the rest of the inner buffer
324 unsafe {
325 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
326 let transmuted_input: &[Complex<A>] = array_utils::workaround_transmute(input);
327 let transmuted_inner_input: &mut [Complex<A>] =
328 array_utils::workaround_transmute_mut(inner_input);
329
330 self.prepare_bluesteins(transmuted_input, transmuted_inner_input)
331 }
332
333 // run our inner forward FFT
334 self.common_data
335 .inner_fft
336 .process_with_scratch(inner_input, inner_scratch);
337
338 // Multiply our inner FFT output by our precomputed data. Then, conjugate the result to set up for an inverse FFT.
339 // We can conjugate the result of multiplication by conjugating both inputs. We pre-conjugated the multiplier array,
340 // so we just need to conjugate inner_input, which the pairwise_complex_multiply_conjugated function will handle
341 unsafe {
342 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
343 let transmuted_inner_input: &mut [Complex<A>] =
344 array_utils::workaround_transmute_mut(inner_input);
345
346 Self::pairwise_complex_multiply_conjugated(
347 transmuted_inner_input,
348 &self.inner_fft_multiplier,
349 )
350 };
351
352 // inverse FFT. we're computing a forward but we're massaging it into an inverse by conjugating the inputs and outputs
353 self.common_data
354 .inner_fft
355 .process_with_scratch(inner_input, inner_scratch);
356
357 // finalize the result
358 unsafe {
359 // Specialization workaround: See the comments in FftPlannerAvx::new() for why these calls to array_utils::workaround_transmute are necessary
360 let transmuted_output: &mut [Complex<A>] =
361 array_utils::workaround_transmute_mut(output);
362 let transmuted_inner_input: &mut [Complex<A>] =
363 array_utils::workaround_transmute_mut(inner_input);
364
365 self.finalize_bluesteins(transmuted_inner_input, transmuted_output)
366 }
367 }
368 }
369
370 #[cfg(test)]
371 mod unit_tests {
372 use num_traits::Float;
373 use rand::distributions::uniform::SampleUniform;
374
375 use super::*;
376 use crate::algorithm::Dft;
377 use crate::test_utils::check_fft_algorithm;
378 use std::sync::Arc;
379
380 #[test]
381 fn test_bluesteins_avx_f32() {
382 for len in 2..16 {
383 // for this len, compute the range of inner FFT lengths we'll use.
384 // Bluesteins AVX f32 requires a multiple of 4 for the inner FFT, so we need to go up to the next multiple of 4 from the minimum
385 let minimum_inner: usize = len * 2 - 1;
386 let remainder = minimum_inner % 4;
387
388 // remainder will never be 0, because "n * 2 - 1" is guaranteed to be odd. so we can just subtract the remainder and add 4.
389 let next_multiple_of_4 = minimum_inner - remainder + 4;
390 let maximum_inner = minimum_inner.checked_next_power_of_two().unwrap() + 1;
391
392 // start at the next multiple of 4, and increment by 4 unti lwe get to the next power of 2.
393 for inner_len in (next_multiple_of_4..maximum_inner).step_by(4) {
394 test_bluesteins_avx_with_length::<f32>(len, inner_len, FftDirection::Forward);
395 test_bluesteins_avx_with_length::<f32>(len, inner_len, FftDirection::Inverse);
396 }
397 }
398 }
399
400 #[test]
401 fn test_bluesteins_avx_f64() {
402 for len in 2..16 {
403 // for this len, compute the range of inner FFT lengths we'll use.
404 // Bluesteins AVX f64 requires a multiple of 2 for the inner FFT, so we need to go up to the next multiple of 2 from the minimum
405 let minimum_inner: usize = len * 2 - 1;
406 let remainder = minimum_inner % 2;
407
408 let next_multiple_of_2 = minimum_inner + remainder;
409 let maximum_inner = minimum_inner.checked_next_power_of_two().unwrap() + 1;
410
411 // start at the next multiple of 2, and increment by 2 unti lwe get to the next power of 2.
412 for inner_len in (next_multiple_of_2..maximum_inner).step_by(2) {
413 test_bluesteins_avx_with_length::<f64>(len, inner_len, FftDirection::Forward);
414 test_bluesteins_avx_with_length::<f64>(len, inner_len, FftDirection::Inverse);
415 }
416 }
417 }
418
419 fn test_bluesteins_avx_with_length<T: AvxNum + Float + SampleUniform>(
420 len: usize,
421 inner_len: usize,
422 direction: FftDirection,
423 ) {
424 let inner_fft = Arc::new(Dft::new(inner_len, direction));
425 let fft: BluesteinsAvx<T, T> = BluesteinsAvx::new(len, inner_fft).expect(
426 "Can't run test because this machine doesn't have the required instruction sets",
427 );
428
429 check_fft_algorithm::<T>(&fft, len, direction);
430 }
431 }