Debian Codegraph @

.cargo/vendor/rustfft/tools/gen_sse_butterflies.py

raw
1 # A simple Python script to generate the code for odd-sized optimized DFTs
2 # The generated code is simply printed in the terminal.
3 # This is only intended for prime lengths, where the usual tricks can't be used.
4 # The generated code is O(n^2), but for short lengths this is still faster than fancier algorithms.
5 # Example, make a length 5 Dft:
6 # > python genbutterflies.py 5
7 # Output:
8 # let x14p = *buffer.get_unchecked(1) + *buffer.get_unchecked(4);
9 # let x14n = *buffer.get_unchecked(1) - *buffer.get_unchecked(4);
10 # let x23p = *buffer.get_unchecked(2) + *buffer.get_unchecked(3);
11 # let x23n = *buffer.get_unchecked(2) - *buffer.get_unchecked(3);
12 # let sum = *buffer.get_unchecked(0) + x14p + x23p;
13 # let b14re_a = buffer.get_unchecked(0).re + self.twiddle1.re*x14p.re + self.twiddle2.re*x23p.re;
14 # let b14re_b = self.twiddle1.im*x14n.im + self.twiddle2.im*x23n.im;
15 # let b23re_a = buffer.get_unchecked(0).re + self.twiddle2.re*x14p.re + self.twiddle1.re*x23p.re;
16 # let b23re_b = self.twiddle2.im*x14n.im + -self.twiddle1.im*x23n.im;
17 #
18 # let b14im_a = buffer.get_unchecked(0).im + self.twiddle1.re*x14p.im + self.twiddle2.re*x23p.im;
19 # let b14im_b = self.twiddle1.im*x14n.re + self.twiddle2.im*x23n.re;
20 # let b23im_a = buffer.get_unchecked(0).im + self.twiddle2.re*x14p.im + self.twiddle1.re*x23p.im;
21 # let b23im_b = self.twiddle2.im*x14n.re + -self.twiddle1.im*x23n.re;
22 #
23 # let out1re = b14re_a - b14re_b;
24 # let out1im = b14im_a + b14im_b;
25 # let out2re = b23re_a - b23re_b;
26 # let out2im = b23im_a + b23im_b;
27 # let out3re = b23re_a + b23re_b;
28 # let out3im = b23im_a - b23im_b;
29 # let out4re = b14re_a + b14re_b;
30 # let out4im = b14im_a - b14im_b;
31 # *buffer.get_unchecked_mut(0) = sum;
32 # *buffer.get_unchecked_mut(1) = Complex{ re: out1re, im: out1im };
33 # *buffer.get_unchecked_mut(2) = Complex{ re: out2re, im: out2im };
34 # *buffer.get_unchecked_mut(3) = Complex{ re: out3re, im: out3im };
35 # *buffer.get_unchecked_mut(4) = Complex{ re: out4re, im: out4im };
36 #
37 #
38 # This required the Butterfly5 to already exist, with twiddles defined like this:
39 # pub struct Butterfly5<T> {
40 # twiddle1: Complex<T>,
41 # twiddle2: Complex<T>,
42 # direction: FftDirection,
43 # }
44 #
45 # With twiddle values:
46 # twiddle1: Complex<T> = twiddles::single_twiddle(1, 5, direction);
47 # twiddle2: Complex<T> = twiddles::single_twiddle(2, 5, direction);
48
49 import sys
50
51 def make_shuffling_single_f64(len):
52 inputs = ", ".join([str(n) for n in range(len)])
53 print(f"let values = read_complex_to_array!(buffer, {{{inputs}}});")
54 print("")
55 print("let out = self.perform_fft_direct(values);")
56 print("")
57 print(f"write_complex_to_array!(out, buffer, {{{inputs}}});")
58
59 def make_shuffling_single_f32(len):
60 inputs = ", ".join([str(n) for n in range(len)])
61 print(f"let values = read_partial1_complex_to_array!(buffer, {{{inputs}}});")
62 print("")
63 print("let out = self.perform_parallel_fft_direct(values);")
64 print("")
65 print(f"write_partial_lo_complex_to_array!(out, buffer, {{{inputs}}});")
66
67
68 def make_shuffling_parallel_f32(len):
69 inputs = ", ".join([str(2*n) for n in range(len)])
70 outputs = ", ".join([str(n) for n in range(len)])
71 print(f"let input_packed = read_complex_to_array!(buffer, {{{inputs}}});")
72 print("")
73 print("let values = [")
74 for n in range(int(len/2)):
75 print(f" extract_lo_hi_f32(input_packed[{int(n)}], input_packed[{int(len/2 + n)}]),")
76 print(f" extract_hi_lo_f32(input_packed[{int(n)}], input_packed[{int(len/2 + n+1)}]),")
77 print(f" extract_lo_hi_f32(input_packed[{int(len/2)}], input_packed[{int(len-1)}]),")
78 print("];")
79 print("")
80 print("let out = self.perform_parallel_fft_direct(values);")
81 print("")
82 print("let out_packed = [")
83 for n in range(int(len/2)):
84 print(f" extract_lo_lo_f32(out[{int(2*n)}], out[{int(2*n+1)}]),")
85 print(f" extract_lo_hi_f32(out[{int(len-1)}], out[0]),")
86 for n in range(int(len/2)):
87 print(f" extract_hi_hi_f32(out[{int(2*n+1)}], out[{int(2*n+2)}]),")
88 print("];")
89 print("")
90 print(f"write_complex_to_array_strided!(out_packed, buffer, 2, {{{outputs}}});")
91
92
93 def make_butterfly(len, fft2func, calcfunc, mulfunc, rotatefunc):
94
95
96 halflen = int((fftlen+1)/2)
97
98 for n in range(1, halflen):
99 print(f"let [x{n}p{fftlen-n}, x{n}m{fftlen-n}] = {fft2func}(values[{n}], values[{fftlen-n}]);")
100
101
102
103 print("")
104 items = []
105 for m in range (1, halflen):
106 for n in range(1, halflen):
107 mn = (m*n)%fftlen
108 if mn > fftlen/2:
109 mn = fftlen-mn
110 print(f"let t_a{m}_{n} = {mulfunc}(self.twiddle{mn}re, x{n}p{fftlen-n});")
111
112 print("")
113 items = []
114 for m in range (1, halflen):
115 for n in range(1, halflen):
116 mn = (m*n)%fftlen
117 if mn > fftlen/2:
118 mn = fftlen-mn
119 print(f"let t_b{m}_{n} = {mulfunc}(self.twiddle{mn}im, x{n}m{fftlen-n});")
120
121
122 print("")
123 print("let x0 = values[0];")
124 for m in range(1, halflen):
125 items = ["x0"]
126 for n in range(1, halflen):
127 items.append(f"t_a{m}_{n}")
128 terms = " + ".join(items)
129 print(f'let t_a{m} = {calcfunc}({terms});')
130
131
132 print("")
133 for m in range(1, halflen):
134 terms = f"t_b{m}_1"
135 for n in range(2, halflen):
136 mn = (m*n)%fftlen
137 if mn > fftlen/2:
138 sign = " - "
139 else:
140 sign = " + "
141 terms = terms + sign + f"t_b{m}_{n}"
142 print(f'let t_b{m} = {calcfunc}({terms});')
143
144 print("")
145 for m in range(1, halflen):
146 print(f'let t_b{m}_rot = self.rotate.{rotatefunc}(t_b{m});')
147
148 print("")
149 items = ["x0"]
150 for n in range(1, halflen):
151 items.append(f"x{n}p{fftlen-n}")
152 terms = " + ".join(items)
153 print(f'let y0 = {calcfunc}({terms});')
154
155 for m in range(1, halflen):
156 print(f"let [y{m}, y{fftlen-m}] = {fft2func}(t_a{m}, t_b{m}_rot);")
157
158 items = []
159 for n in range(0, fftlen):
160 items.append(f"y{n}")
161 print(f'[{", ".join(items)}]')
162
163
164 if __name__ == "__main__":
165 fftlen = int(sys.argv[1])
166 print("\n\n--------------- f32 ---------------")
167 print("\n ----- perform_fft_contiguous -----")
168 make_shuffling_single_f32(fftlen)
169 print("\n ----- perform_parallel_fft_contiguous -----")
170 make_shuffling_parallel_f32(fftlen)
171 print("\n ----- perform_parallel_fft_direct -----")
172 make_butterfly(fftlen, "parallel_fft2_interleaved_f32", "calc_f32!", "_mm_mul_ps", "rotate_both")
173
174 print("\n\n--------------- f64 ---------------")
175 print("\n ----- perform_fft_contiguous -----")
176 make_shuffling_single_f64(fftlen)
177 print("\n ----- perform_parallel_fft_direct -----")
178 make_butterfly(fftlen, "solo_fft2_f64", "calc_f64!", "_mm_mul_pd", "rotate")