| 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})") |