Debian Codegraph @

.cargo/vendor/rustfft/src/algorithm/radix3.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, Butterfly27, Butterfly3, Butterfly9};
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-three sizes
13 ///
14 /// ~~~
15 /// // Computes a forward FFT of size 2187
16 /// use rustfft::algorithm::Radix3;
17 /// use rustfft::{Fft, FftDirection};
18 /// use rustfft::num_complex::Complex;
19 ///
20 /// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 2187];
21 ///
22 /// let fft = Radix3::new(2187, FftDirection::Forward);
23 /// fft.process(&mut buffer);
24 /// ~~~
25
26 pub struct Radix3<T> {
27 twiddles: Box<[Complex<T>]>,
28 butterfly3: Butterfly3<T>,
29
30 base_fft: Arc<dyn Fft<T>>,
31 base_len: usize,
32
33 len: usize,
34 direction: FftDirection,
35 }
36
37 impl<T: FftNum> Radix3<T> {
38 /// Preallocates necessary arrays and precomputes necessary data to efficiently compute the power-of-three FFT
39 pub fn new(len: usize, direction: FftDirection) -> Self {
40 // Compute the total power of 3 for this length. IE, len = 3^exponent
41 let exponent = compute_logarithm(len, 3).unwrap_or_else(|| {
42 panic!(
43 "Radix3 algorithm requires a power-of-three input size. Got {}",
44 len
45 )
46 });
47
48 // figure out which base length we're going to use
49 let (base_len, base_fft) = match exponent {
50 0 => (len, Arc::new(Butterfly1::new(direction)) as Arc<dyn Fft<T>>),
51 1 => (len, Arc::new(Butterfly3::new(direction)) as Arc<dyn Fft<T>>),
52 2 => (len, Arc::new(Butterfly9::new(direction)) as Arc<dyn Fft<T>>),
53 _ => (27, Arc::new(Butterfly27::new(direction)) as Arc<dyn Fft<T>>),
54 };
55
56 // precompute the twiddle factors this algorithm will use.
57 // we're doing the same precomputation of twiddle factors as the mixed radix algorithm where width=3 and height=len/3
58 // but mixed radix only does one step and then calls itself recusrively, and this algorithm does every layer all the way down
59 // so we're going to pack all the "layers" of twiddle factors into a single array, starting with the bottom layer and going up
60 let mut twiddle_stride = len / (base_len * 3);
61 let mut twiddle_factors = Vec::with_capacity(len * 2);
62 while twiddle_stride > 0 {
63 let num_rows = len / (twiddle_stride * 3);
64 for i in 0..num_rows {
65 for k in 1..3 {
66 let twiddle = twiddles::compute_twiddle(i * k * twiddle_stride, len, direction);
67 twiddle_factors.push(twiddle);
68 }
69 }
70 twiddle_stride /= 3;
71 }
72
73 Self {
74 twiddles: twiddle_factors.into_boxed_slice(),
75 butterfly3: Butterfly3::new(direction),
76
77 base_fft,
78 base_len,
79
80 len,
81 direction,
82 }
83 }
84
85 fn perform_fft_out_of_place(
86 &self,
87 signal: &[Complex<T>],
88 spectrum: &mut [Complex<T>],
89 _scratch: &mut [Complex<T>],
90 ) {
91 // copy the data into the spectrum vector
92 if self.len() == self.base_len {
93 spectrum.copy_from_slice(signal);
94 } else {
95 bitreversed_transpose(self.base_len, signal, spectrum);
96 }
97
98 // Base-level FFTs
99 self.base_fft.process_with_scratch(spectrum, &mut []);
100
101 // cross-FFTs
102 let mut current_size = self.base_len * 3;
103 let mut layer_twiddles: &[Complex<T>] = &self.twiddles;
104
105 while current_size <= signal.len() {
106 let num_rows = signal.len() / current_size;
107
108 for i in 0..num_rows {
109 unsafe {
110 butterfly_3(
111 &mut spectrum[i * current_size..],
112 layer_twiddles,
113 current_size / 3,
114 &self.butterfly3,
115 )
116 }
117 }
118
119 //skip past all the twiddle factors used in this layer
120 let twiddle_offset = (current_size * 2) / 3;
121 layer_twiddles = &layer_twiddles[twiddle_offset..];
122
123 current_size *= 3;
124 }
125 }
126 }
127 boilerplate_fft_oop!(Radix3, |this: &Radix3<_>| this.len);
128
129 // Preparing for radix 3 is similar to a transpose, where the column index is bit reversed.
130 // Use a lookup table to avoid repeating the slow bit reverse operations.
131 // Unrolling the outer loop by a factor 4 helps speed things up.
132 pub fn bitreversed_transpose<T: Copy>(height: usize, input: &[T], output: &mut [T]) {
133 let width = input.len() / height;
134 let third_width = width / 3;
135
136 let rev_digits = compute_logarithm(width, 3).unwrap();
137
138 // Let's make sure the arguments are ok
139 assert!(input.len() == output.len());
140 for x in 0..third_width {
141 let x0 = 3 * x;
142 let x1 = 3 * x + 1;
143 let x2 = 3 * x + 2;
144
145 let x_rev = [
146 reverse_bits(x0, rev_digits),
147 reverse_bits(x1, rev_digits),
148 reverse_bits(x2, rev_digits),
149 ];
150
151 // Assert that the the bit reversed indices will not exceed the length of the output.
152 // The highest index the loop reaches is: (x_rev[n] + 1)*height - 1
153 // The last element of the data is at index: width*height - 1
154 // Thus it is sufficient to assert that x_rev[n]<width.
155 assert!(x_rev[0] < width && x_rev[1] < width && x_rev[2] < width);
156
157 for y in 0..height {
158 let input_index0 = x0 + y * width;
159 let input_index1 = x1 + y * width;
160 let input_index2 = x2 + y * width;
161 let output_index0 = y + x_rev[0] * height;
162 let output_index1 = y + x_rev[1] * height;
163 let output_index2 = y + x_rev[2] * height;
164
165 unsafe {
166 let temp0 = *input.get_unchecked(input_index0);
167 let temp1 = *input.get_unchecked(input_index1);
168 let temp2 = *input.get_unchecked(input_index2);
169
170 *output.get_unchecked_mut(output_index0) = temp0;
171 *output.get_unchecked_mut(output_index1) = temp1;
172 *output.get_unchecked_mut(output_index2) = temp2;
173 }
174 }
175 }
176 }
177
178 // computes `n` such that `base ^ n == value`. Returns `None` if `value` is not a perfect power of `base`, otherwise returns `Some(n)`
179 fn compute_logarithm(value: usize, base: usize) -> Option<usize> {
180 if value == 0 || base == 0 {
181 return None;
182 }
183
184 let mut current_exponent = 0;
185 let mut current_value = value;
186
187 while current_value % base == 0 {
188 current_exponent += 1;
189 current_value /= base;
190 }
191
192 if current_value == 1 {
193 Some(current_exponent)
194 } else {
195 None
196 }
197 }
198
199 // Sort of like reversing bits in radix4. We're not actually reversing bits, but the algorithm is exactly the same.
200 // Radix4's bit reversal does divisions by 4, multiplications by 4, and modulo 4 - all of which are easily represented by bit manipulation.
201 // As a result, it can be thought of as a bit reversal. But really, the "bit reversal"-ness of it is a special case of a more general "remainder reversal"
202 // IE, it's repeatedly taking the remainder of dividing by N, and building a new number where those remainders are reversed.
203 // So this algorithm does all the things that bit reversal does, but replaces the multiplications by 4 with multiplications by 3, etc, and ends up with the same conceptual result as a bit reversal.
204 pub fn reverse_bits(value: usize, reversal_iters: usize) -> usize {
205 let mut result: usize = 0;
206 let mut value = value;
207 for _ in 0..reversal_iters {
208 result = (result * 3) + (value % 3);
209 value /= 3;
210 }
211 result
212 }
213
214 unsafe fn butterfly_3<T: FftNum>(
215 data: &mut [Complex<T>],
216 twiddles: &[Complex<T>],
217 num_ffts: usize,
218 butterfly3: &Butterfly3<T>,
219 ) {
220 let mut idx = 0usize;
221 let mut tw_idx = 0usize;
222 let mut scratch = [Zero::zero(); 3];
223 for _ in 0..num_ffts {
224 scratch[0] = *data.get_unchecked(idx);
225 scratch[1] = *data.get_unchecked(idx + 1 * num_ffts) * twiddles[tw_idx];
226 scratch[2] = *data.get_unchecked(idx + 2 * num_ffts) * twiddles[tw_idx + 1];
227
228 butterfly3.perform_fft_butterfly(&mut scratch);
229
230 *data.get_unchecked_mut(idx) = scratch[0];
231 *data.get_unchecked_mut(idx + 1 * num_ffts) = scratch[1];
232 *data.get_unchecked_mut(idx + 2 * num_ffts) = scratch[2];
233
234 tw_idx += 2;
235 idx += 1;
236 }
237 }
238
239 #[cfg(test)]
240 mod unit_tests {
241 use super::*;
242 use crate::test_utils::check_fft_algorithm;
243
244 #[test]
245 fn test_radix3() {
246 for pow in 0..8 {
247 let len = 3usize.pow(pow);
248 test_3adix3_with_length(len, FftDirection::Forward);
249 test_3adix3_with_length(len, FftDirection::Inverse);
250 }
251 }
252
253 fn test_3adix3_with_length(len: usize, direction: FftDirection) {
254 let fft = Radix3::new(len, direction);
255
256 check_fft_algorithm::<f32>(&fft, len, direction);
257 }
258 }