Crate rustfft

RustFFT is a high-performance FFT library written in pure Rust.

This is an experimental release of RustFFT that enables AVX acceleration. It currently requires a nightly compiler, mainly for the min_specialization feature. The eventual plan is to release this experimental version as version 5.0 of RustFFT, but that will not happen until it compiles on stable Rust.

Usage

The recommended way to use RustFFT is to create a FftPlanner instance and then call its plan_fft method. This method will automatically choose which FFT algorithms are best for a given size and initialize the required buffers and precomputed data.

// Perform a forward FFT of size 1234
use rustfft::{FftPlanner, num_complex::Complex};

let mut planner = FftPlanner::new(false);
let fft = planner.plan_fft(1234);

let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234];
fft.process_inplace(&mut buffer);

The planner returns trait objects of the Fft trait, allowing for FFT sizes that aren't known until runtime.

RustFFT also exposes individual FFT algorithms. For example, if you know beforehand that you need a power-of-two FFT, you can avoid the overhead of the planner and trait object by directly creating instances of the Radix4 algorithm:

// Computes a forward FFT of size 4096
use rustfft::{Fft, num_complex::Complex, algorithm::Radix4};

let fft = Radix4::new(4096, false);

let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 4096];
fft.process_inplace(&mut buffer);

For the vast majority of situations, simply using the FftPlanner will be enough, but advanced users may have better insight than the planner into which algorithms are best for a specific size. See the algorithm module for a complete list of scalar (non-AVX) algorithms implemented by RustFFT. As noted below, bypassing the planner will prevent any use of AVX instructions.

AVX Acceleration

RustFFT includes algorithms designed to take advantage of the AVX instruction set. To use AVX, simply plan a FFT through the FftPlanner on a machine which supports the avx and fma features. Benchmarking shows that while using AVX, RustFFT computes FFTs at equal or faster speeds than FFTW!

If your machine doesn't support AVX, the FftPlanner will fall back to scalar algorithms. If you'd rather just not compute a FFT at all if AVX isn't available, you can instead create an instance of the FftPlannerAvx struct and plan through that.

For the time being, individual AVX algorithms can't be constructed outside of the planner. This may change eventually.

AVX Performance Tips

The performance of any given FFT size is heavily dependent on that size's prime factorization. It's common in FFT libraries (including RustFFT's scalar implementation) for powers of two to be the fastest, but that's not the case for RustFFT's AVX implementation. RustFFT's AVX implementation is fastest when computing any size of the form 2^n * 3^m -- which includes powers of two, but isn't restricted to them.

Any FFT where all prime factors are 11 or smaller (For example, 10164 = 2*2*3*7*11*11) can be computed very quickly.

All other FFT sizes, such as prime numbers, and composite numbers where the largest prime factor is greater than 11, will be noticeably slower. For example, 1201 (prime number) takes 3x longer to compute than 1200 = 2*2*2*2*3*5*5. However, they will still be computed in O(nlogn) time, they still benefit from AVX acceleration, and according to benchmarks we've run, are still faster than the same size computed by FFTW.

Normalization

RustFFT does not normalize outputs. Callers must manually normalize the results by scaling each element by 1/len().sqrt(). Multiple normalization steps can be merged into one via pairwise multiplication, so when doing a forward FFT followed by an inverse callers can normalize once by scaling each element by 1/len()

Output Order

Elements in the output are ordered by ascending frequency, with the first element corresponding to frequency 0.

Re-exports

pub use num_complex;

pub use num_traits;

Modules

algorithm

Individual FFT algorithms

Structs

FftPlanner	The FFT planner is used to make new FFT algorithm instances.
FftPlannerAvx	The FFT planner is used to make new FFT algorithm instances. Specifically, FftPlannerAvx generates FFT algorithms that are designed with the AVX instruction set in mind.

Traits

FFTnum	Generic floating point number, implemented for f32 and f64
Fft	Trait for algorithms that compute FFTs.
IsInverse	A trait that allows FFT algorithms to report whether they compute forward FFTs or inverse FFTs
Length	A trait that allows FFT algorithms to report their expected input/output size