Debian Codegraph @

.cargo/vendor/rustfft/tools/genbutterflies.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 len = int(sys.argv[1])
52
53 halflen = int((len+1)/2)
54
55 for n in range(1, halflen):
56 print(f"let x{n}{len-n}p = buffer.load({n}) + buffer.load({len-n});")
57 print(f"let x{n}{len-n}n = buffer.load({n}) - buffer.load({len-n});")
58
59 row = ["let sum = buffer.load(0)"]
60 for n in range(1, halflen):
61 row.append(f"x{n}{len-n}p")
62 print(" + ".join(row) + ";")
63
64 for n in range(1, halflen):
65 row = [f"let b{n}{len-n}re_a = buffer.load(0).re"]
66 for m in range(1, halflen):
67 mn = (m*n)%len
68 if mn > len/2:
69 mn = len-mn
70 row.append(f"self.twiddle{mn}.re*x{m}{len-m}p.re")
71 print(" + ".join(row) + ";")
72 row = []
73 for m in range(1, halflen):
74 mn = (m*n)%len
75 if mn > len/2:
76 mn = len-mn
77 row.append(f"-self.twiddle{mn}.im*x{m}{len-m}n.im")
78 else:
79 row.append(f"self.twiddle{mn}.im*x{m}{len-m}n.im")
80 print(f"let b{n}{len-n}re_b = " + " + ".join(row) + ";")
81 print("")
82
83 for n in range(1, halflen):
84 row = [f"let b{n}{len-n}im_a = buffer.load(0).im"]
85 for m in range(1, halflen):
86 mn = (m*n)%len
87 if mn > len/2:
88 mn = len-mn
89 row.append(f"self.twiddle{mn}.re*x{m}{len-m}p.im")
90 print(" + ".join(row) + ";")
91 row = []
92 for m in range(1, halflen):
93 mn = (m*n)%len
94 if mn > len/2:
95 mn = len-mn
96 row.append(f"-self.twiddle{mn}.im*x{m}{len-m}n.re")
97 else:
98 row.append(f"self.twiddle{mn}.im*x{m}{len-m}n.re")
99 print(f"let b{n}{len-n}im_b = " + " + ".join(row) + ";")
100 print("")
101
102 for n in range(1,len):
103 nfold = n
104 sign_re = "-"
105 sign_im = "+"
106 if n > len/2:
107 nfold = len-n
108 sign_re = "+"
109 sign_im = "-"
110 print(f"let out{n}re = b{nfold}{len-nfold}re_a {sign_re} b{nfold}{len-nfold}re_b;")
111 print(f"let out{n}im = b{nfold}{len-nfold}im_a {sign_im} b{nfold}{len-nfold}im_b;")
112
113 print("buffer.store(sum, 0);")
114 for n in range(1,len):
115 print(f"buffer.store(Complex{{ re: out{n}re, im: out{n}im }}, {n})")