microfft 0.1.0

Embedded-friendly Fast Fourier Transforms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#! /usr/bin/env python3

"""
Script for generating the pre-computed tables used by microfft:
  - radix-2 FFT twiddle tables
  - bit reversal tables

Used to create the file `src/tables.rs`.
"""

import argparse
import cmath
import math


def parse_args():
    parser = argparse.ArgumentParser()
    parser.add_argument("N", type=int, help="Max FFT size")
    return parser.parse_args()


def iter_n(max_n):
    n = 1
    while n <= max_n:
        yield n
        n *= 2


def emit_uses():
    print("use num_complex::Complex32;")
    print()


def emit_twiddle(max_n):
    print("#[allow(clippy::approx_constant)]")
    print("#[allow(clippy::excessive_precision)]")
    print("#[allow(clippy::unreadable_literal)]")
    print("pub(crate) const TWIDDLE: &[&[Complex32]] = &[")
    for n in iter_n(max_n):
        emit_twiddle_table(n)
    print("];")
    print()


def emit_twiddle_table(n):
    print("    &[")
    for k in range(n // 2):
        twiddle = cmath.exp(-2j * math.pi * k / n)
        print(f"        Complex32::new({twiddle.real}, {twiddle.imag}),")
    print("    ],")


def emit_bitrev(max_n):
    print("pub(crate) const BITREV: &[&[u16]] = &[")
    for n in iter_n(max_n):
        emit_bitrev_table(n)
    print("];")
    print()


def emit_bitrev_table(n):
    print("    &[")
    nbits = int(math.log2(n))
    for i in range(n):
        rev = reverse_bits(i, nbits)
        entry = rev if rev > i else i
        print(f"        {entry},")
    print("    ],")


def reverse_bits(num, nbits):
    reverse = 0
    for i in range(nbits):
        if num & (1 << i):
            reverse |= 1 << (nbits - 1 - i)
    return reverse


def main():
    args = parse_args()
    emit_uses()
    emit_twiddle(args.N)
    emit_bitrev(args.N)


if __name__ == "__main__":
    main()