Debian Codegraph @

.cargo/vendor/rustfft/src/algorithm/radix4.rs

raw
1 use std::sync::Arc;
2
3 use num_complex::Complex;
4 use num_traits::Zero;
5
6 use crate::algorithm::butterflies::{Butterfly1, Butterfly16, Butterfly2, Butterfly4, Butterfly8};
7 use crate::array_utils;
8 use crate::common::{fft_error_inplace, fft_error_outofplace};
9 use crate::{common::FftNum, twiddles, FftDirection};
10 use crate::{Direction, Fft, Length};
11
12 /// FFT algorithm optimized for power-of-two sizes
13 ///
14 /// ~~~
15 /// // Computes a forward FFT of size 4096
16 /// use rustfft::algorithm::Radix4;
17 /// use rustfft::{Fft, FftDirection};
18 /// use rustfft::num_complex::Complex;
19 ///
20 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 4096];
21 ///
22 /// let fft = Radix4::new(4096, FftDirection::Forward);
23 /// fft.process(&mut buffer);
24 /// ~~~
25
26 pub struct Radix4<T> {
27 twiddles: Box<[Complex<T>]>,
28
29 base_fft: Arc<dyn Fft<T>>,
30 base_len: usize,
31
32 len: usize,
33 direction: FftDirection,
34 }
35
36 impl<T: FftNum> Radix4<T> {
37 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute the power-of-two FFT
38 pub fn new(len: usize, direction: FftDirection) -> Self {
39 assert!(
40 len.is_power_of_two(),
41 "Radix4 algorithm requires a power-of-two input size. Got {}",
42 len
43 );
44
45 // figure out which base length we're going to use
46 let num_bits = len.trailing_zeros();
47 let (base_len, base_fft) = match num_bits {
48 0 => (len, Arc::new(Butterfly1::new(direction)) as Arc<dyn Fft<T>>),
49 1 => (len, Arc::new(Butterfly2::new(direction)) as Arc<dyn Fft<T>>),
50 2 => (len, Arc::new(Butterfly4::new(direction)) as Arc<dyn Fft<T>>),
51 _ => {
52 if num_bits % 2 == 1 {
53 (8, Arc::new(Butterfly8::new(direction)) as Arc<dyn Fft<T>>)
54 } else {
55 (16, Arc::new(Butterfly16::new(direction)) as Arc<dyn Fft<T>>)
56 }
57 }
58 };
59
60 // precompute the twiddle factors this algorithm will use.
61 // we're doing the same precomputation of twiddle factors as the mixed radix algorithm where width=4 and height=len/4
62 // but mixed radix only does one step and then calls itself recusrively, and this algorithm does every layer all the way down
63 // so we're going to pack all the "layers" of twiddle factors into a single array, starting with the bottom layer and going up
64 let mut twiddle_stride = len / (base_len * 4);
65 let mut twiddle_factors = Vec::with_capacity(len * 2);
66 while twiddle_stride > 0 {
67 let num_rows = len / (twiddle_stride * 4);
68 for i in 0..num_rows {
69 for k in 1..4 {
70 let twiddle = twiddles::compute_twiddle(i * k * twiddle_stride, len, direction);
71 twiddle_factors.push(twiddle);
72 }
73 }
74 twiddle_stride /= 4;
75 }
76
77 Self {
78 twiddles: twiddle_factors.into_boxed_slice(),
79
80 base_fft,
81 base_len,
82
83 len,
84 direction,
85 }
86 }
87
88 fn perform_fft_out_of_place(
89 &self,
90 signal: &[Complex<T>],
91 spectrum: &mut [Complex<T>],
92 _scratch: &mut [Complex<T>],
93 ) {
94 // copy the data into the spectrum vector
95 if self.len() == self.base_len {
96 spectrum.copy_from_slice(signal);
97 } else {
98 bitreversed_transpose(self.base_len, signal, spectrum);
99 }
100
101 // Base-level FFTs
102 self.base_fft.process_with_scratch(spectrum, &mut []);
103
104 // cross-FFTs
105 let mut current_size = self.base_len * 4;
106 let mut layer_twiddles: &[Complex<T>] = &self.twiddles;
107
108 while current_size <= signal.len() {
109 let num_rows = signal.len() / current_size;
110
111 for i in 0..num_rows {
112 unsafe {
113 butterfly_4(
114 &mut spectrum[i * current_size..],
115 layer_twiddles,
116 current_size / 4,
117 self.direction,
118 )
119 }
120 }
121
122 //skip past all the twiddle factors used in this layer
123 let twiddle_offset = (current_size * 3) / 4;
124 layer_twiddles = &layer_twiddles[twiddle_offset..];
125
126 current_size *= 4;
127 }
128 }
129 }
130 boilerplate_fft_oop!(Radix4, |this: &Radix4<_>| this.len);
131
132 // Preparing for radix 4 is similar to a transpose, where the column index is bit reversed.
133 // Use a lookup table to avoid repeating the slow bit reverse operations.
134 // Unrolling the outer loop by a factor 4 helps speed things up.
135 pub fn bitreversed_transpose<T: Copy>(height: usize, input: &[T], output: &mut [T]) {
136 let width = input.len() / height;
137 let quarter_width = width / 4;
138
139 let rev_digits = (width.trailing_zeros() / 2) as usize;
140
141 // Let's make sure the arguments are ok
142 assert!(input.len() == output.len());
143 for x in 0..quarter_width {
144 let x0 = 4 * x;
145 let x1 = 4 * x + 1;
146 let x2 = 4 * x + 2;
147 let x3 = 4 * x + 3;
148
149 let x_rev = [
150 reverse_bits(x0, rev_digits),
151 reverse_bits(x1, rev_digits),
152 reverse_bits(x2, rev_digits),
153 reverse_bits(x3, rev_digits),
154 ];
155
156 // Assert that the the bit reversed indices will not exceed the length of the output.
157 // The highest index the loop reaches is: (x_rev[n] + 1)*height - 1
158 // The last element of the data is at index: width*height - 1
159 // Thus it is sufficient to assert that x_rev[n]<width.
160 assert!(x_rev[0] < width && x_rev[1] < width && x_rev[2] < width && x_rev[3] < width);
161
162 for y in 0..height {
163 let input_index0 = x0 + y * width;
164 let input_index1 = x1 + y * width;
165 let input_index2 = x2 + y * width;
166 let input_index3 = x3 + y * width;
167 let output_index0 = y + x_rev[0] * height;
168 let output_index1 = y + x_rev[1] * height;
169 let output_index2 = y + x_rev[2] * height;
170 let output_index3 = y + x_rev[3] * height;
171
172 unsafe {
173 let temp0 = *input.get_unchecked(input_index0);
174 let temp1 = *input.get_unchecked(input_index1);
175 let temp2 = *input.get_unchecked(input_index2);
176 let temp3 = *input.get_unchecked(input_index3);
177
178 *output.get_unchecked_mut(output_index0) = temp0;
179 *output.get_unchecked_mut(output_index1) = temp1;
180 *output.get_unchecked_mut(output_index2) = temp2;
181 *output.get_unchecked_mut(output_index3) = temp3;
182 }
183 }
184 }
185 }
186
187 // Reverse bits of value, in pairs.
188 // For 8 bits: abcdefgh -> ghefcdab
189 pub fn reverse_bits(value: usize, bitpairs: usize) -> usize {
190 let mut result: usize = 0;
191 let mut value = value;
192 for _ in 0..bitpairs {
193 result = (result << 2) + (value & 0x03);
194 value = value >> 2;
195 }
196 result
197 }
198
199 unsafe fn butterfly_4<T: FftNum>(
200 data: &mut [Complex<T>],
201 twiddles: &[Complex<T>],
202 num_ffts: usize,
203 direction: FftDirection,
204 ) {
205 let butterfly4 = Butterfly4::new(direction);
206
207 let mut idx = 0usize;
208 let mut tw_idx = 0usize;
209 let mut scratch = [Zero::zero(); 4];
210 for _ in 0..num_ffts {
211 scratch[0] = *data.get_unchecked(idx);
212 scratch[1] = *data.get_unchecked(idx + 1 * num_ffts) * twiddles[tw_idx];
213 scratch[2] = *data.get_unchecked(idx + 2 * num_ffts) * twiddles[tw_idx + 1];
214 scratch[3] = *data.get_unchecked(idx + 3 * num_ffts) * twiddles[tw_idx + 2];
215
216 butterfly4.perform_fft_butterfly(&mut scratch);
217
218 *data.get_unchecked_mut(idx) = scratch[0];
219 *data.get_unchecked_mut(idx + 1 * num_ffts) = scratch[1];
220 *data.get_unchecked_mut(idx + 2 * num_ffts) = scratch[2];
221 *data.get_unchecked_mut(idx + 3 * num_ffts) = scratch[3];
222
223 tw_idx += 3;
224 idx += 1;
225 }
226 }
227
228 #[cfg(test)]
229 mod unit_tests {
230 use super::*;
231 use crate::test_utils::check_fft_algorithm;
232
233 #[test]
234 fn test_radix4() {
235 for pow in 1..12 {
236 let len = 1 << pow;
237 test_radix4_with_length(len, FftDirection::Forward);
238 //test_radix4_with_length(len, FftDirection::Inverse);
239 }
240 }
241
242 fn test_radix4_with_length(len: usize, direction: FftDirection) {
243 let fft = Radix4::new(len, direction);
244
245 check_fft_algorithm::<f32>(&fft, len, direction);
246 }
247 }