Debian Codegraph @

.cargo/vendor/rustfft/src/neon/neon_radix4.rs

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