Debian Codegraph @

.cargo/vendor/rustfft/src/wasm_simd/wasm_simd_radix4.rs

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