Debian Codegraph @

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

raw
1 use num_complex::Complex;
2
3 use core::arch::x86_64::*;
4
5 use crate::algorithm::bitreversed_transpose;
6 use crate::array_utils::{self, workaround_transmute_mut};
7 use crate::common::{fft_error_inplace, fft_error_outofplace};
8 use crate::sse::sse_butterflies::{
9 SseF32Butterfly1, SseF32Butterfly16, SseF32Butterfly2, SseF32Butterfly32, SseF32Butterfly4,
10 SseF32Butterfly8,
11 };
12 use crate::sse::sse_butterflies::{
13 SseF64Butterfly1, SseF64Butterfly16, SseF64Butterfly2, SseF64Butterfly32, SseF64Butterfly4,
14 SseF64Butterfly8,
15 };
16 use crate::{common::FftNum, twiddles, FftDirection};
17 use crate::{Direction, Fft, Length};
18
19 use super::sse_common::{assert_f32, assert_f64};
20 use super::sse_utils::*;
21
22 use super::sse_vector::{SseArray, SseArrayMut};
23
24 /// FFT algorithm optimized for power-of-two sizes, SSE accelerated version.
25 /// This is designed to be used via a Planner, and not created directly.
26
27 const USE_BUTTERFLY32_FROM: usize = 262144; // Use length 32 butterfly starting from this length
28
29 enum Sse32Butterfly<T> {
30 Len1(SseF32Butterfly1<T>),
31 Len2(SseF32Butterfly2<T>),
32 Len4(SseF32Butterfly4<T>),
33 Len8(SseF32Butterfly8<T>),
34 Len16(SseF32Butterfly16<T>),
35 Len32(SseF32Butterfly32<T>),
36 }
37
38 enum Sse64Butterfly<T> {
39 Len1(SseF64Butterfly1<T>),
40 Len2(SseF64Butterfly2<T>),
41 Len4(SseF64Butterfly4<T>),
42 Len8(SseF64Butterfly8<T>),
43 Len16(SseF64Butterfly16<T>),
44 Len32(SseF64Butterfly32<T>),
45 }
46
47 pub struct Sse32Radix4<T> {
48 _phantom: std::marker::PhantomData<T>,
49 twiddles: Box<[__m128]>,
50
51 base_fft: Sse32Butterfly<T>,
52 base_len: usize,
53
54 len: usize,
55 direction: FftDirection,
56 bf4: SseF32Butterfly4<T>,
57 }
58
59 impl<T: FftNum> Sse32Radix4<T> {
60 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute the power-of-two FFT
61 pub fn new(len: usize, direction: FftDirection) -> Self {
62 assert!(
63 len.is_power_of_two(),
64 "Radix4 algorithm requires a power-of-two input size. Got {}",
65 len
66 );
67 assert_f32::<T>();
68
69 // figure out which base length we're going to use
70 let num_bits = len.trailing_zeros();
71 let (base_len, base_fft) = match num_bits {
72 0 => (len, Sse32Butterfly::Len1(SseF32Butterfly1::new(direction))),
73 1 => (len, Sse32Butterfly::Len2(SseF32Butterfly2::new(direction))),
74 2 => (len, Sse32Butterfly::Len4(SseF32Butterfly4::new(direction))),
75 3 => (len, Sse32Butterfly::Len8(SseF32Butterfly8::new(direction))),
76 _ => {
77 if num_bits % 2 == 1 {
78 if len < USE_BUTTERFLY32_FROM {
79 (8, Sse32Butterfly::Len8(SseF32Butterfly8::new(direction)))
80 } else {
81 (32, Sse32Butterfly::Len32(SseF32Butterfly32::new(direction)))
82 }
83 } else {
84 (16, Sse32Butterfly::Len16(SseF32Butterfly16::new(direction)))
85 }
86 }
87 };
88
89 // precompute the twiddle factors this algorithm will use.
90 // we're doing the same precomputation of twiddle factors as the mixed radix algorithm where width=4 and height=len/4
91 // but mixed radix only does one step and then calls itself recusrively, and this algorithm does every layer all the way down
92 // so we're going to pack all the "layers" of twiddle factors into a single array, starting with the bottom layer and going up
93 let mut twiddle_stride = len / (base_len * 4);
94 let mut twiddle_factors = Vec::with_capacity(len * 2);
95 while twiddle_stride > 0 {
96 let num_rows = len / (twiddle_stride * 4);
97 for i in 0..num_rows / 2 {
98 for k in 1..4 {
99 unsafe {
100 let twiddle_a =
101 twiddles::compute_twiddle(2 * i * k * twiddle_stride, len, direction);
102 let twiddle_b = twiddles::compute_twiddle(
103 (2 * i + 1) * k * twiddle_stride,
104 len,
105 direction,
106 );
107 let twiddles_packed =
108 _mm_set_ps(twiddle_b.im, twiddle_b.re, twiddle_a.im, twiddle_a.re);
109 twiddle_factors.push(twiddles_packed);
110 }
111 }
112 }
113 twiddle_stride >>= 2;
114 }
115
116 Self {
117 twiddles: twiddle_factors.into_boxed_slice(),
118
119 base_fft,
120 base_len,
121
122 len,
123 direction,
124 _phantom: std::marker::PhantomData,
125 bf4: SseF32Butterfly4::<T>::new(direction),
126 }
127 }
128
129 #[target_feature(enable = "sse4.1")]
130 unsafe fn perform_fft_out_of_place(
131 &self,
132 signal: &[Complex<T>],
133 spectrum: &mut [Complex<T>],
134 _scratch: &mut [Complex<T>],
135 ) {
136 // copy the data into the spectrum vector
137 if self.len() == self.base_len {
138 spectrum.copy_from_slice(signal);
139 } else {
140 bitreversed_transpose(self.base_len, signal, spectrum);
141 }
142
143 // Base-level FFTs
144 match &self.base_fft {
145 Sse32Butterfly::Len1(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
146 Sse32Butterfly::Len2(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
147 Sse32Butterfly::Len4(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
148 Sse32Butterfly::Len8(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
149 Sse32Butterfly::Len16(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
150 Sse32Butterfly::Len32(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
151 };
152
153 // cross-FFTs
154 let mut current_size = self.base_len * 4;
155 let mut layer_twiddles: &[__m128] = &self.twiddles;
156
157 while current_size <= signal.len() {
158 let num_rows = signal.len() / current_size;
159
160 for i in 0..num_rows {
161 butterfly_4_32(
162 &mut spectrum[i * current_size..],
163 layer_twiddles,
164 current_size / 4,
165 &self.bf4,
166 )
167 }
168
169 //skip past all the twiddle factors used in this layer
170 let twiddle_offset = (current_size * 3) / 8;
171 layer_twiddles = &layer_twiddles[twiddle_offset..];
172
173 current_size *= 4;
174 }
175 }
176 }
177 boilerplate_fft_sse_oop!(Sse32Radix4, |this: &Sse32Radix4<_>| this.len);
178
179 #[target_feature(enable = "sse4.1")]
180 unsafe fn butterfly_4_32<T: FftNum>(
181 data: &mut [Complex<T>],
182 twiddles: &[__m128],
183 num_ffts: usize,
184 bf4: &SseF32Butterfly4<T>,
185 ) {
186 let mut idx = 0usize;
187 let mut buffer: &mut [Complex<f32>] = workaround_transmute_mut(data);
188 for tw in twiddles.chunks_exact(6).take(num_ffts / 4) {
189 let scratch0 = buffer.load_complex(idx);
190 let scratch0b = buffer.load_complex(idx + 2);
191 let mut scratch1 = buffer.load_complex(idx + 1 * num_ffts);
192 let mut scratch1b = buffer.load_complex(idx + 2 + 1 * num_ffts);
193 let mut scratch2 = buffer.load_complex(idx + 2 * num_ffts);
194 let mut scratch2b = buffer.load_complex(idx + 2 + 2 * num_ffts);
195 let mut scratch3 = buffer.load_complex(idx + 3 * num_ffts);
196 let mut scratch3b = buffer.load_complex(idx + 2 + 3 * num_ffts);
197
198 scratch1 = mul_complex_f32(scratch1, tw[0]);
199 scratch2 = mul_complex_f32(scratch2, tw[1]);
200 scratch3 = mul_complex_f32(scratch3, tw[2]);
201 scratch1b = mul_complex_f32(scratch1b, tw[3]);
202 scratch2b = mul_complex_f32(scratch2b, tw[4]);
203 scratch3b = mul_complex_f32(scratch3b, tw[5]);
204
205 let scratch = bf4.perform_parallel_fft_direct(scratch0, scratch1, scratch2, scratch3);
206 let scratchb = bf4.perform_parallel_fft_direct(scratch0b, scratch1b, scratch2b, scratch3b);
207
208 buffer.store_complex(scratch[0], idx);
209 buffer.store_complex(scratchb[0], idx + 2);
210 buffer.store_complex(scratch[1], idx + 1 * num_ffts);
211 buffer.store_complex(scratchb[1], idx + 2 + 1 * num_ffts);
212 buffer.store_complex(scratch[2], idx + 2 * num_ffts);
213 buffer.store_complex(scratchb[2], idx + 2 + 2 * num_ffts);
214 buffer.store_complex(scratch[3], idx + 3 * num_ffts);
215 buffer.store_complex(scratchb[3], idx + 2 + 3 * num_ffts);
216
217 idx += 4;
218 }
219 }
220
221 pub struct Sse64Radix4<T> {
222 _phantom: std::marker::PhantomData<T>,
223 twiddles: Box<[__m128d]>,
224
225 base_fft: Sse64Butterfly<T>,
226 base_len: usize,
227
228 len: usize,
229 direction: FftDirection,
230 bf4: SseF64Butterfly4<T>,
231 }
232
233 impl<T: FftNum> Sse64Radix4<T> {
234 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute the power-of-two FFT
235 pub fn new(len: usize, direction: FftDirection) -> Self {
236 assert!(
237 len.is_power_of_two(),
238 "Radix4 algorithm requires a power-of-two input size. Got {}",
239 len
240 );
241
242 assert_f64::<T>();
243
244 // figure out which base length we're going to use
245 let num_bits = len.trailing_zeros();
246 let (base_len, base_fft) = match num_bits {
247 0 => (len, Sse64Butterfly::Len1(SseF64Butterfly1::new(direction))),
248 1 => (len, Sse64Butterfly::Len2(SseF64Butterfly2::new(direction))),
249 2 => (len, Sse64Butterfly::Len4(SseF64Butterfly4::new(direction))),
250 3 => (len, Sse64Butterfly::Len8(SseF64Butterfly8::new(direction))),
251 _ => {
252 if num_bits % 2 == 1 {
253 if len < USE_BUTTERFLY32_FROM {
254 (8, Sse64Butterfly::Len8(SseF64Butterfly8::new(direction)))
255 } else {
256 (32, Sse64Butterfly::Len32(SseF64Butterfly32::new(direction)))
257 }
258 } else {
259 (16, Sse64Butterfly::Len16(SseF64Butterfly16::new(direction)))
260 }
261 }
262 };
263
264 // precompute the twiddle factors this algorithm will use.
265 // we're doing the same precomputation of twiddle factors as the mixed radix algorithm where width=4 and height=len/4
266 // but mixed radix only does one step and then calls itself recusrively, and this algorithm does every layer all the way down
267 // so we're going to pack all the "layers" of twiddle factors into a single array, starting with the bottom layer and going up
268 let mut twiddle_stride = len / (base_len * 4);
269 let mut twiddle_factors = Vec::with_capacity(len * 2);
270 while twiddle_stride > 0 {
271 let num_rows = len / (twiddle_stride * 4);
272 for i in 0..num_rows {
273 for k in 1..4 {
274 unsafe {
275 let twiddle =
276 twiddles::compute_twiddle(i * k * twiddle_stride, len, direction);
277 let twiddle_packed = _mm_set_pd(twiddle.im, twiddle.re);
278 twiddle_factors.push(twiddle_packed);
279 }
280 }
281 }
282 twiddle_stride >>= 2;
283 }
284
285 Self {
286 twiddles: twiddle_factors.into_boxed_slice(),
287
288 base_fft,
289 base_len,
290
291 len,
292 direction,
293 _phantom: std::marker::PhantomData,
294 bf4: SseF64Butterfly4::<T>::new(direction),
295 }
296 }
297
298 #[target_feature(enable = "sse4.1")]
299 unsafe fn perform_fft_out_of_place(
300 &self,
301 signal: &[Complex<T>],
302 spectrum: &mut [Complex<T>],
303 _scratch: &mut [Complex<T>],
304 ) {
305 // copy the data into the spectrum vector
306 if self.len() == self.base_len {
307 spectrum.copy_from_slice(signal);
308 } else {
309 bitreversed_transpose(self.base_len, signal, spectrum);
310 }
311
312 // Base-level FFTs
313 match &self.base_fft {
314 Sse64Butterfly::Len1(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
315 Sse64Butterfly::Len2(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
316 Sse64Butterfly::Len4(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
317 Sse64Butterfly::Len8(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
318 Sse64Butterfly::Len16(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
319 Sse64Butterfly::Len32(bf) => bf.perform_fft_butterfly_multi(spectrum).unwrap(),
320 }
321
322 // cross-FFTs
323 let mut current_size = self.base_len * 4;
324 let mut layer_twiddles: &[__m128d] = &self.twiddles;
325
326 while current_size <= signal.len() {
327 let num_rows = signal.len() / current_size;
328
329 for i in 0..num_rows {
330 butterfly_4_64(
331 &mut spectrum[i * current_size..],
332 layer_twiddles,
333 current_size / 4,
334 &self.bf4,
335 )
336 }
337
338 //skip past all the twiddle factors used in this layer
339 let twiddle_offset = (current_size * 3) / 4;
340 layer_twiddles = &layer_twiddles[twiddle_offset..];
341
342 current_size *= 4;
343 }
344 }
345 }
346 boilerplate_fft_sse_oop!(Sse64Radix4, |this: &Sse64Radix4<_>| this.len);
347
348 #[target_feature(enable = "sse4.1")]
349 unsafe fn butterfly_4_64<T: FftNum>(
350 data: &mut [Complex<T>],
351 twiddles: &[__m128d],
352 num_ffts: usize,
353 bf4: &SseF64Butterfly4<T>,
354 ) {
355 let mut idx = 0usize;
356 let mut buffer: &mut [Complex<f64>] = workaround_transmute_mut(data);
357 for tw in twiddles.chunks_exact(6).take(num_ffts / 2) {
358 let scratch0 = buffer.load_complex(idx);
359 let scratch0b = buffer.load_complex(idx + 1);
360 let mut scratch1 = buffer.load_complex(idx + 1 * num_ffts);
361 let mut scratch1b = buffer.load_complex(idx + 1 + 1 * num_ffts);
362 let mut scratch2 = buffer.load_complex(idx + 2 * num_ffts);
363 let mut scratch2b = buffer.load_complex(idx + 1 + 2 * num_ffts);
364 let mut scratch3 = buffer.load_complex(idx + 3 * num_ffts);
365 let mut scratch3b = buffer.load_complex(idx + 1 + 3 * num_ffts);
366
367 scratch1 = mul_complex_f64(scratch1, tw[0]);
368 scratch2 = mul_complex_f64(scratch2, tw[1]);
369 scratch3 = mul_complex_f64(scratch3, tw[2]);
370 scratch1b = mul_complex_f64(scratch1b, tw[3]);
371 scratch2b = mul_complex_f64(scratch2b, tw[4]);
372 scratch3b = mul_complex_f64(scratch3b, tw[5]);
373
374 let scratch = bf4.perform_fft_direct(scratch0, scratch1, scratch2, scratch3);
375 let scratchb = bf4.perform_fft_direct(scratch0b, scratch1b, scratch2b, scratch3b);
376
377 buffer.store_complex(scratch[0], idx);
378 buffer.store_complex(scratchb[0], idx + 1);
379 buffer.store_complex(scratch[1], idx + 1 * num_ffts);
380 buffer.store_complex(scratchb[1], idx + 1 + 1 * num_ffts);
381 buffer.store_complex(scratch[2], idx + 2 * num_ffts);
382 buffer.store_complex(scratchb[2], idx + 1 + 2 * num_ffts);
383 buffer.store_complex(scratch[3], idx + 3 * num_ffts);
384 buffer.store_complex(scratchb[3], idx + 1 + 3 * num_ffts);
385
386 idx += 2;
387 }
388 }
389
390 #[cfg(test)]
391 mod unit_tests {
392 use super::*;
393 use crate::test_utils::check_fft_algorithm;
394
395 #[test]
396 fn test_sse_radix4_64() {
397 for pow in 4..12 {
398 let len = 1 << pow;
399 test_sse_radix4_64_with_length(len, FftDirection::Forward);
400 test_sse_radix4_64_with_length(len, FftDirection::Inverse);
401 }
402 }
403
404 fn test_sse_radix4_64_with_length(len: usize, direction: FftDirection) {
405 let fft = Sse64Radix4::new(len, direction);
406 check_fft_algorithm::<f64>(&fft, len, direction);
407 }
408
409 #[test]
410 fn test_sse_radix4_32() {
411 for pow in 0..12 {
412 let len = 1 << pow;
413 test_sse_radix4_32_with_length(len, FftDirection::Forward);
414 test_sse_radix4_32_with_length(len, FftDirection::Inverse);
415 }
416 }
417
418 fn test_sse_radix4_32_with_length(len: usize, direction: FftDirection) {
419 let fft = Sse32Radix4::new(len, direction);
420 check_fft_algorithm::<f32>(&fft, len, direction);
421 }
422 }