[−][src]Crate rustfft

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

RustFFT supports the AVX instruction set for increased performance. No special code is needed to activate AVX: Simply plan a FFT using the FftPlanner on a machine that supports the avx and fma CPU features, and RustFFT will automatically switch to faster AVX-accelerated algorithms.

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();
let fft = planner.plan_fft_forward(1234);

let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234];
fft.process(&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, FftDirection, num_complex::Complex, algorithm::Radix4};

let fft = Radix4::new(4096, FftDirection::Forward);

let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 4096];
fft.process(&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 algorithms implemented by RustFFT.

Users should beware, however, that bypassing the planner will disable all AVX optimizations.

Feature Flags

avx (Enabled by default)

On x86_64, the avx feature enables compilation of AVX-accelerated code. Enabling it greatly improves performance if the client CPU supports AVX, while disabling it reduces compile time and binary size. On every other platform, this feature does nothing, and RustFFT will behave like it's not set.

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.

AVX Performance Tips

In any FFT computation, the time required to compute a FFT of size N relies heavily on the prime factorization of N. If N's prime factors are all very small, computing a FFT of size N will be fast, and it'll be slow if N has large prime factors, or if N is a prime number.

In most FFT libraries (Including RustFFT when using non-AVX code), power-of-two FFT sizes are the fastest, and users see a steep falloff in performance when using non-power-of-two sizes. Thankfully, RustFFT using AVX acceleration is not quite as restrictive:

Any FFT whose size is of the form 2^n * 3^m can be considered the "fastest" in RustFFT.
Any FFT whose prime factors are all 11 or smaller will also be very fast, but the fewer the factors of 2 and 3 the slower it will be. For example, computing a FFT of size 13552 (2^4*7*11*11) is takes 12% longer to compute than 13824 (2^9 * 3^3), and computing a FFT of size 2541 (3*7*11*11) takes 65% longer to compute than 2592 (2^5 * 3^4)
Any other FFT size will be noticeably slower. A considerable amount of effort has been put into making these FFT sizes as fast as they can be, but some FFT sizes just take more work than others. For example, computing a FFT of size 5183 (71 * 73) takes about 5x longer than computing a FFT of size 5184 (2^6 * 3^4).

In most cases, even prime-sized FFTs will be fast enough for your application. In the example of 5183 above, even that "slow" FFT only takes a few tens of microseconds to compute.

Our advice is to start by trying the size that's most convenient to your application. If that's too slow, see if you can find a nearby size whose prime factors are all 11 or smaller, and you can expect a 2x-5x speedup. If that's still too slow, find a nearby size whose prime factors are all 2 or 3, and you can expect a 1.1x-1.5x speedup.

FftPlanner	The FFT planner creates new FFT algorithm instances.
FftPlannerAvx	The AVX FFT planner creates new FFT algorithm instances which take advantage of the AVX instruction set.
FftPlannerScalar	The Scalar FFT planner creates new FFT algorithm instances using non-SIMD algorithms.

Enums

FftDirection

Represents a FFT direction, IE a forward FFT or an inverse FFT

Traits

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