| 1 |
#![cfg_attr(all(feature = "bench", test), feature(test))] |
| 2 |
|
| 3 |
//! RustFFT is a high-performance FFT library written in pure Rust. |
| 4 |
//! |
| 5 |
//! On X86_64, RustFFT supports the AVX instruction set for increased performance. No special code is needed to activate AVX: |
| 6 |
//! Simply plan a FFT using the FftPlanner on a machine that supports the `avx` and `fma` CPU features, and RustFFT |
| 7 |
//! will automatically switch to faster AVX-accelerated algorithms. |
| 8 |
//! |
| 9 |
//! For machines that do not have AVX, RustFFT also supports the SSE4.1 instruction set. |
| 10 |
//! As for AVX, this is enabled automatically when using the FftPlanner. |
| 11 |
//! |
| 12 |
//! Additionally, there is automatic support for the Neon instruction set on AArch64, |
| 13 |
//! and support for WASM SIMD when compiling for WASM targets. |
| 14 |
//! |
| 15 |
//! ### Usage |
| 16 |
//! |
| 17 |
//! The recommended way to use RustFFT is to create a [`FftPlanner`](crate::FftPlanner) instance and then call its |
| 18 |
//! [`plan_fft`](crate::FftPlanner::plan_fft) method. This method will automatically choose which FFT algorithms are best |
| 19 |
//! for a given size and initialize the required buffers and precomputed data. |
| 20 |
//! |
| 21 |
//! ``` |
| 22 |
//! // Perform a forward FFT of size 1234 |
| 23 |
//! use rustfft::{FftPlanner, num_complex::Complex}; |
| 24 |
//! |
| 25 |
//! let mut planner = FftPlanner::new(); |
| 26 |
//! let fft = planner.plan_fft_forward(1234); |
| 27 |
//! |
| 28 |
//! let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234]; |
| 29 |
//! fft.process(&mut buffer); |
| 30 |
//! ``` |
| 31 |
//! The planner returns trait objects of the [`Fft`](crate::Fft) trait, allowing for FFT sizes that aren't known |
| 32 |
//! until runtime. |
| 33 |
//! |
| 34 |
//! RustFFT also exposes individual FFT algorithms. For example, if you know beforehand that you need a power-of-two FFT, you can |
| 35 |
//! avoid the overhead of the planner and trait object by directly creating instances of the [`Radix4`](crate::algorithm::Radix4) algorithm: |
| 36 |
//! |
| 37 |
//! ``` |
| 38 |
//! // Computes a forward FFT of size 4096 |
| 39 |
//! use rustfft::{Fft, FftDirection, num_complex::Complex, algorithm::Radix4}; |
| 40 |
//! |
| 41 |
//! let fft = Radix4::new(4096, FftDirection::Forward); |
| 42 |
//! |
| 43 |
//! let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 4096]; |
| 44 |
//! fft.process(&mut buffer); |
| 45 |
//! ``` |
| 46 |
//! |
| 47 |
//! For the vast majority of situations, simply using the [`FftPlanner`](crate::FftPlanner) will be enough, but |
| 48 |
//! advanced users may have better insight than the planner into which algorithms are best for a specific size. See the |
| 49 |
//! [`algorithm`](crate::algorithm) module for a complete list of scalar algorithms implemented by RustFFT. |
| 50 |
//! |
| 51 |
//! Users should beware, however, that bypassing the planner will disable all AVX, SSE, Neon, and WASM SIMD optimizations. |
| 52 |
//! |
| 53 |
//! ### Feature Flags |
| 54 |
//! |
| 55 |
//! * `avx` (Enabled by default) |
| 56 |
//! |
| 57 |
//! On x86_64, the `avx` feature enables compilation of AVX-accelerated code. Enabling it greatly improves performance if the |
| 58 |
//! client CPU supports AVX and FMA, while disabling it reduces compile time and binary size. |
| 59 |
//! |
| 60 |
//! On every platform besides x86_64, this feature does nothing, and RustFFT will behave like it's not set. |
| 61 |
//! * `sse` (Enabled by default) |
| 62 |
//! |
| 63 |
//! On x86_64, the `sse` feature enables compilation of SSE4.1-accelerated code. Enabling it improves performance |
| 64 |
//! if the client CPU supports SSE4.1, while disabling it reduces compile time and binary size. If AVX is also |
| 65 |
//! supported and its feature flag is enabled, RustFFT will use AVX instead of SSE4.1. |
| 66 |
//! |
| 67 |
//! On every platform besides x86_64, this feature does nothing, and RustFFT will behave like it's not set. |
| 68 |
//! * `neon` (Enabled by default) |
| 69 |
//! |
| 70 |
//! On AArch64 (64-bit ARM) the `neon` feature enables compilation of Neon-accelerated code. Enabling it improves |
| 71 |
//! performance, while disabling it reduces compile time and binary size. |
| 72 |
//! |
| 73 |
//! On every platform besides AArch64, this feature does nothing, and RustFFT will behave like it's not set. |
| 74 |
//! * `wasm_simd` (Disabled by default) |
| 75 |
//! |
| 76 |
//! On the WASM platform, this feature enables compilation of WASM SIMD accelerated code. |
| 77 |
//! |
| 78 |
//! To execute binaries compiled with `wasm_simd`, you need a [target browser or runtime which supports `fixed-width SIMD`](https://webassembly.org/roadmap/). |
| 79 |
//! If you run your SIMD accelerated code on an unsupported platform, WebAssembly will specify a [trap](https://webassembly.github.io/spec/core/intro/overview.html#trap) leading to immediate execution cancelation. |
| 80 |
//! |
| 81 |
//! On every platform besides WASM, this feature does nothing and RustFFT will behave like it is not set. |
| 82 |
//! |
| 83 |
//! ### Normalization |
| 84 |
//! |
| 85 |
//! RustFFT does not normalize outputs. Callers must manually normalize the results by scaling each element by |
| 86 |
//! `1/len().sqrt()`. Multiple normalization steps can be merged into one via pairwise multiplication, so when |
| 87 |
//! doing a forward FFT followed by an inverse callers can normalize once by scaling each element by `1/len()` |
| 88 |
//! |
| 89 |
//! ### Output Order |
| 90 |
//! |
| 91 |
//! Elements in the output are ordered by ascending frequency, with the first element corresponding to frequency 0. |
| 92 |
//! |
| 93 |
//! ### AVX Performance Tips |
| 94 |
//! |
| 95 |
//! In any FFT computation, the time required to compute a FFT of size N relies heavily on the [prime factorization](https://en.wikipedia.org/wiki/Integer_factorization) of N. |
| 96 |
//! 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 |
| 97 |
//! factors, or if N is a prime number. |
| 98 |
//! |
| 99 |
//! In most FFT libraries (Including RustFFT when using non-AVX code), power-of-two FFT sizes are the fastest, and users see a steep |
| 100 |
//! falloff in performance when using non-power-of-two sizes. Thankfully, RustFFT using AVX acceleration is not quite as restrictive: |
| 101 |
//! |
| 102 |
//! - Any FFT whose size is of the form `2^n * 3^m` can be considered the "fastest" in RustFFT. |
| 103 |
//! - 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. |
| 104 |
//! 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)`, |
| 105 |
//! and computing a FFT of size 2541 `(3*7*11*11)` takes 65% longer to compute than 2592 `(2^5 * 3^4)` |
| 106 |
//! - Any other FFT size will be noticeably slower. A considerable amount of effort has been put into making these FFT sizes as fast as |
| 107 |
//! 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 |
| 108 |
//! 5x longer than computing a FFT of size 5184 `(2^6 * 3^4)`. |
| 109 |
//! |
| 110 |
//! In most cases, even prime-sized FFTs will be fast enough for your application. In the example of 5183 above, even that "slow" FFT |
| 111 |
//! only takes a few tens of microseconds to compute. |
| 112 |
//! |
| 113 |
//! Some applications of the FFT allow for choosing an arbitrary FFT size (In many applications the size is pre-determined by whatever you're computing). |
| 114 |
//! If your application supports choosing your own size, our advice is still to start by trying the size that's most convenient to your application. |
| 115 |
//! 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. |
| 116 |
//! 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. |
| 117 |
|
| 118 |
use std::fmt::Display; |
| 119 |
|
| 120 |
pub use num_complex; |
| 121 |
pub use num_traits; |
| 122 |
|
| 123 |
#[macro_use] |
| 124 |
mod common; |
| 125 |
|
| 126 |
/// Individual FFT algorithms |
| 127 |
pub mod algorithm; |
| 128 |
mod array_utils; |
| 129 |
mod fft_cache; |
| 130 |
mod math_utils; |
| 131 |
mod plan; |
| 132 |
mod twiddles; |
| 133 |
|
| 134 |
use num_complex::Complex; |
| 135 |
use num_traits::Zero; |
| 136 |
|
| 137 |
pub use crate::common::FftNum; |
| 138 |
pub use crate::plan::{FftPlanner, FftPlannerScalar}; |
| 139 |
|
| 140 |
/// A trait that allows FFT algorithms to report their expected input/output size |
| 141 |
pub trait Length { |
| 142 |
/// The FFT size that this algorithm can process |
| 143 |
fn len(&self) -> usize; |
| 144 |
} |
| 145 |
|
| 146 |
/// Represents a FFT direction, IE a forward FFT or an inverse FFT |
| 147 |
#[derive(Copy, Clone, PartialEq, Eq, Debug)] |
| 148 |
pub enum FftDirection { |
| 149 |
Forward, |
| 150 |
Inverse, |
| 151 |
} |
| 152 |
impl FftDirection { |
| 153 |
/// Returns the opposite direction of `self`. |
| 154 |
/// |
| 155 |
/// - If `self` is `FftDirection::Forward`, returns `FftDirection::Inverse` |
| 156 |
/// - If `self` is `FftDirection::Inverse`, returns `FftDirection::Forward` |
| 157 |
#[inline] |
| 158 |
pub fn opposite_direction(&self) -> FftDirection { |
| 159 |
match self { |
| 160 |
Self::Forward => Self::Inverse, |
| 161 |
Self::Inverse => Self::Forward, |
| 162 |
} |
| 163 |
} |
| 164 |
} |
| 165 |
impl Display for FftDirection { |
| 166 |
fn fmt(&self, f: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> { |
| 167 |
match self { |
| 168 |
Self::Forward => f.write_str("Forward"), |
| 169 |
Self::Inverse => f.write_str("Inverse"), |
| 170 |
} |
| 171 |
} |
| 172 |
} |
| 173 |
|
| 174 |
/// A trait that allows FFT algorithms to report whether they compute forward FFTs or inverse FFTs |
| 175 |
pub trait Direction { |
| 176 |
/// Returns FftDirection::Forward if this instance computes forward FFTs, or FftDirection::Inverse for inverse FFTs |
| 177 |
fn fft_direction(&self) -> FftDirection; |
| 178 |
} |
| 179 |
|
| 180 |
/// Trait for algorithms that compute FFTs. |
| 181 |
/// |
| 182 |
/// This trait has a few methods for computing FFTs. Its most conveinent method is [`process(slice)`](crate::Fft::process). |
| 183 |
/// It takes in a slice of `Complex<T>` and computes a FFT on that slice, in-place. It may copy the data over to internal scratch buffers |
| 184 |
/// if that speeds up the computation, but the output will always end up in the same slice as the input. |
| 185 |
pub trait Fft<T: FftNum>: Length + Direction + Sync + Send { |
| 186 |
/// Computes a FFT in-place. |
| 187 |
/// |
| 188 |
/// Convenience method that allocates a `Vec` with the required scratch space and calls `self.process_with_scratch`. |
| 189 |
/// If you want to re-use that allocation across multiple FFT computations, consider calling `process_with_scratch` instead. |
| 190 |
/// |
| 191 |
/// # Panics |
| 192 |
/// |
| 193 |
/// This method panics if: |
| 194 |
/// - `buffer.len() % self.len() > 0` |
| 195 |
/// - `buffer.len() < self.len()` |
| 196 |
fn process(&self, buffer: &mut [Complex<T>]) { |
| 197 |
let mut scratch = vec![Complex::zero(); self.get_inplace_scratch_len()]; |
| 198 |
self.process_with_scratch(buffer, &mut scratch); |
| 199 |
} |
| 200 |
|
| 201 |
/// Divides `buffer` into chunks of size `self.len()`, and computes a FFT on each chunk. |
| 202 |
/// |
| 203 |
/// Uses the `scratch` buffer as scratch space, so the contents of `scratch` should be considered garbage |
| 204 |
/// after calling. |
| 205 |
/// |
| 206 |
/// # Panics |
| 207 |
/// |
| 208 |
/// This method panics if: |
| 209 |
/// - `buffer.len() % self.len() > 0` |
| 210 |
/// - `buffer.len() < self.len()` |
| 211 |
/// - `scratch.len() < self.get_inplace_scratch_len()` |
| 212 |
fn process_with_scratch(&self, buffer: &mut [Complex<T>], scratch: &mut [Complex<T>]); |
| 213 |
|
| 214 |
/// Divides `input` and `output` into chunks of size `self.len()`, and computes a FFT on each chunk. |
| 215 |
/// |
| 216 |
/// This method uses both the `input` buffer and `scratch` buffer as scratch space, so the contents of both should be |
| 217 |
/// considered garbage after calling. |
| 218 |
/// |
| 219 |
/// This is a more niche way of computing a FFT. It's useful to avoid a `copy_from_slice()` if you need the output |
| 220 |
/// in a different buffer than the input for some reason. This happens frequently in RustFFT internals, but is probably |
| 221 |
/// less common among RustFFT users. |
| 222 |
/// |
| 223 |
/// For many FFT sizes, `self.get_outofplace_scratch_len()` returns 0 |
| 224 |
/// |
| 225 |
/// # Panics |
| 226 |
/// |
| 227 |
/// This method panics if: |
| 228 |
/// - `output.len() != input.len()` |
| 229 |
/// - `input.len() % self.len() > 0` |
| 230 |
/// - `input.len() < self.len()` |
| 231 |
/// - `scratch.len() < self.get_outofplace_scratch_len()` |
| 232 |
fn process_outofplace_with_scratch( |
| 233 |
&self, |
| 234 |
input: &mut [Complex<T>], |
| 235 |
output: &mut [Complex<T>], |
| 236 |
scratch: &mut [Complex<T>], |
| 237 |
); |
| 238 |
|
| 239 |
/// Returns the size of the scratch buffer required by `process_with_scratch` |
| 240 |
/// |
| 241 |
/// For most FFT sizes, this method will return `self.len()`. For a few small sizes it will return 0, and for some special FFT sizes |
| 242 |
/// (Sizes that require the use of Bluestein's Algorithm), this may return a scratch size larger than `self.len()`. |
| 243 |
/// The returned value may change from one version of RustFFT to the next. |
| 244 |
fn get_inplace_scratch_len(&self) -> usize; |
| 245 |
|
| 246 |
/// Returns the size of the scratch buffer required by `process_outofplace_with_scratch` |
| 247 |
/// |
| 248 |
/// For most FFT sizes, this method will return 0. For some special FFT sizes |
| 249 |
/// (Sizes that require the use of Bluestein's Algorithm), this may return a scratch size larger than `self.len()`. |
| 250 |
/// The returned value may change from one version of RustFFT to the next. |
| 251 |
fn get_outofplace_scratch_len(&self) -> usize; |
| 252 |
} |
| 253 |
|
| 254 |
// Algorithms implemented to use AVX instructions. Only compiled on x86_64, and only compiled if the "avx" feature flag is set. |
| 255 |
#[cfg(all(target_arch = "x86_64", feature = "avx"))] |
| 256 |
mod avx; |
| 257 |
|
| 258 |
// If we're not on x86_64, or if the "avx" feature was disabled, keep a stub implementation around that has the same API, but does nothing |
| 259 |
// That way, users can write code using the AVX planner and compile it on any platform |
| 260 |
#[cfg(not(all(target_arch = "x86_64", feature = "avx")))] |
| 261 |
mod avx { |
| 262 |
pub mod avx_planner { |
| 263 |
use crate::{Fft, FftDirection, FftNum}; |
| 264 |
use std::sync::Arc; |
| 265 |
|
| 266 |
/// The AVX FFT planner creates new FFT algorithm instances which take advantage of the AVX instruction set. |
| 267 |
/// |
| 268 |
/// Creating an instance of `FftPlannerAvx` requires the `avx` and `fma` instructions to be available on the current machine, and it requires RustFFT's |
| 269 |
/// `avx` feature flag to be set. A few algorithms will use `avx2` if it's available, but it isn't required. |
| 270 |
/// |
| 271 |
/// For the time being, AVX acceleration is black box, and AVX accelerated algorithms are not available without a planner. This may change in the future. |
| 272 |
/// |
| 273 |
/// ~~~ |
| 274 |
/// // Perform a forward Fft of size 1234, accelerated by AVX |
| 275 |
/// use std::sync::Arc; |
| 276 |
/// use rustfft::{FftPlannerAvx, num_complex::Complex}; |
| 277 |
/// |
| 278 |
/// // If FftPlannerAvx::new() returns Ok(), we'll know AVX algorithms are available |
| 279 |
/// // on this machine, and that RustFFT was compiled with the `avx` feature flag |
| 280 |
/// if let Ok(mut planner) = FftPlannerAvx::new() { |
| 281 |
/// let fft = planner.plan_fft_forward(1234); |
| 282 |
/// |
| 283 |
/// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234]; |
| 284 |
/// fft.process(&mut buffer); |
| 285 |
/// |
| 286 |
/// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`, |
| 287 |
/// // where T is the numeric type, ie f32 or f64, so it's cheap to clone |
| 288 |
/// let fft_clone = Arc::clone(&fft); |
| 289 |
/// } |
| 290 |
/// ~~~ |
| 291 |
/// |
| 292 |
/// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This |
| 293 |
/// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing |
| 294 |
/// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created |
| 295 |
/// by a different planner) |
| 296 |
/// |
| 297 |
/// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly |
| 298 |
/// safe to drop the planner after creating Fft instances. |
| 299 |
pub struct FftPlannerAvx<T: FftNum> { |
| 300 |
_phantom: std::marker::PhantomData<T>, |
| 301 |
} |
| 302 |
impl<T: FftNum> FftPlannerAvx<T> { |
| 303 |
/// Constructs a new `FftPlannerAvx` instance. |
| 304 |
/// |
| 305 |
/// Returns `Ok(planner_instance)` if this machine has the required instruction sets and the `avx` feature flag is set. |
| 306 |
/// Returns `Err(())` if some instruction sets are missing, or if the `avx` feature flag is not set. |
| 307 |
pub fn new() -> Result<Self, ()> { |
| 308 |
Err(()) |
| 309 |
} |
| 310 |
/// Returns a `Fft` instance which uses AVX instructions to compute FFTs of size `len`. |
| 311 |
/// |
| 312 |
/// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs. |
| 313 |
/// |
| 314 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 315 |
pub fn plan_fft(&mut self, _len: usize, _direction: FftDirection) -> Arc<dyn Fft<T>> { |
| 316 |
unreachable!() |
| 317 |
} |
| 318 |
/// Returns a `Fft` instance which uses AVX instructions to compute forward FFTs of size `len`. |
| 319 |
/// |
| 320 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 321 |
pub fn plan_fft_forward(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 322 |
unreachable!() |
| 323 |
} |
| 324 |
/// Returns a `Fft` instance which uses AVX instructions to compute inverse FFTs of size `len. |
| 325 |
/// |
| 326 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 327 |
pub fn plan_fft_inverse(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 328 |
unreachable!() |
| 329 |
} |
| 330 |
} |
| 331 |
} |
| 332 |
} |
| 333 |
|
| 334 |
pub use self::avx::avx_planner::FftPlannerAvx; |
| 335 |
|
| 336 |
// Algorithms implemented to use SSE4.1 instructions. Only compiled on x86_64, and only compiled if the "sse" feature flag is set. |
| 337 |
#[cfg(all(target_arch = "x86_64", feature = "sse"))] |
| 338 |
mod sse; |
| 339 |
|
| 340 |
// If we're not on x86_64, or if the "sse" feature was disabled, keep a stub implementation around that has the same API, but does nothing |
| 341 |
// That way, users can write code using the SSE planner and compile it on any platform |
| 342 |
#[cfg(not(all(target_arch = "x86_64", feature = "sse")))] |
| 343 |
mod sse { |
| 344 |
pub mod sse_planner { |
| 345 |
use crate::{Fft, FftDirection, FftNum}; |
| 346 |
use std::sync::Arc; |
| 347 |
|
| 348 |
/// The SSE FFT planner creates new FFT algorithm instances using a mix of scalar and SSE accelerated algorithms. |
| 349 |
/// It requires at least SSE4.1, which is available on all reasonably recent x86_64 cpus. |
| 350 |
/// |
| 351 |
/// RustFFT has several FFT algorithms available. For a given FFT size, the `FftPlannerSse` decides which of the |
| 352 |
/// available FFT algorithms to use and then initializes them. |
| 353 |
/// |
| 354 |
/// ~~~ |
| 355 |
/// // Perform a forward Fft of size 1234 |
| 356 |
/// use std::sync::Arc; |
| 357 |
/// use rustfft::{FftPlannerSse, num_complex::Complex}; |
| 358 |
/// |
| 359 |
/// if let Ok(mut planner) = FftPlannerSse::new() { |
| 360 |
/// let fft = planner.plan_fft_forward(1234); |
| 361 |
/// |
| 362 |
/// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234]; |
| 363 |
/// fft.process(&mut buffer); |
| 364 |
/// |
| 365 |
/// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`, |
| 366 |
/// // where T is the numeric type, ie f32 or f64, so it's cheap to clone |
| 367 |
/// let fft_clone = Arc::clone(&fft); |
| 368 |
/// } |
| 369 |
/// ~~~ |
| 370 |
/// |
| 371 |
/// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This |
| 372 |
/// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing |
| 373 |
/// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created |
| 374 |
/// by a different planner) |
| 375 |
/// |
| 376 |
/// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly |
| 377 |
/// safe to drop the planner after creating Fft instances. |
| 378 |
pub struct FftPlannerSse<T: FftNum> { |
| 379 |
_phantom: std::marker::PhantomData<T>, |
| 380 |
} |
| 381 |
impl<T: FftNum> FftPlannerSse<T> { |
| 382 |
/// Creates a new `FftPlannerSse` instance. |
| 383 |
/// |
| 384 |
/// Returns `Ok(planner_instance)` if this machine has the required instruction sets. |
| 385 |
/// Returns `Err(())` if some instruction sets are missing. |
| 386 |
pub fn new() -> Result<Self, ()> { |
| 387 |
Err(()) |
| 388 |
} |
| 389 |
/// Returns a `Fft` instance which uses SSE4.1 instructions to compute FFTs of size `len`. |
| 390 |
/// |
| 391 |
/// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs. |
| 392 |
/// |
| 393 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 394 |
pub fn plan_fft(&mut self, _len: usize, _direction: FftDirection) -> Arc<dyn Fft<T>> { |
| 395 |
unreachable!() |
| 396 |
} |
| 397 |
/// Returns a `Fft` instance which uses SSE4.1 instructions to compute forward FFTs of size `len`. |
| 398 |
/// |
| 399 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 400 |
pub fn plan_fft_forward(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 401 |
unreachable!() |
| 402 |
} |
| 403 |
/// Returns a `Fft` instance which uses SSE4.1 instructions to compute inverse FFTs of size `len. |
| 404 |
/// |
| 405 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 406 |
pub fn plan_fft_inverse(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 407 |
unreachable!() |
| 408 |
} |
| 409 |
} |
| 410 |
} |
| 411 |
} |
| 412 |
|
| 413 |
pub use self::sse::sse_planner::FftPlannerSse; |
| 414 |
|
| 415 |
// Algorithms implemented to use Neon instructions. Only compiled on AArch64, and only compiled if the "neon" feature flag is set. |
| 416 |
#[cfg(all(target_arch = "aarch64", feature = "neon"))] |
| 417 |
mod neon; |
| 418 |
|
| 419 |
// If we're not on AArch64, or if the "neon" feature was disabled, keep a stub implementation around that has the same API, but does nothing |
| 420 |
// That way, users can write code using the Neon planner and compile it on any platform |
| 421 |
#[cfg(not(all(target_arch = "aarch64", feature = "neon")))] |
| 422 |
mod neon { |
| 423 |
pub mod neon_planner { |
| 424 |
use crate::{Fft, FftDirection, FftNum}; |
| 425 |
use std::sync::Arc; |
| 426 |
|
| 427 |
/// The Neon FFT planner creates new FFT algorithm instances using a mix of scalar and Neon accelerated algorithms. |
| 428 |
/// It is supported when using the 64-bit AArch64 instruction set. |
| 429 |
/// |
| 430 |
/// RustFFT has several FFT algorithms available. For a given FFT size, the `FftPlannerNeon` decides which of the |
| 431 |
/// available FFT algorithms to use and then initializes them. |
| 432 |
/// |
| 433 |
/// ~~~ |
| 434 |
/// // Perform a forward Fft of size 1234 |
| 435 |
/// use std::sync::Arc; |
| 436 |
/// use rustfft::{FftPlannerNeon, num_complex::Complex}; |
| 437 |
/// |
| 438 |
/// if let Ok(mut planner) = FftPlannerNeon::new() { |
| 439 |
/// let fft = planner.plan_fft_forward(1234); |
| 440 |
/// |
| 441 |
/// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234]; |
| 442 |
/// fft.process(&mut buffer); |
| 443 |
/// |
| 444 |
/// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`, |
| 445 |
/// // where T is the numeric type, ie f32 or f64, so it's cheap to clone |
| 446 |
/// let fft_clone = Arc::clone(&fft); |
| 447 |
/// } |
| 448 |
/// ~~~ |
| 449 |
/// |
| 450 |
/// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This |
| 451 |
/// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing |
| 452 |
/// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created |
| 453 |
/// by a different planner) |
| 454 |
/// |
| 455 |
/// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly |
| 456 |
/// safe to drop the planner after creating Fft instances. |
| 457 |
pub struct FftPlannerNeon<T: FftNum> { |
| 458 |
_phantom: std::marker::PhantomData<T>, |
| 459 |
} |
| 460 |
impl<T: FftNum> FftPlannerNeon<T> { |
| 461 |
/// Creates a new `FftPlannerNeon` instance. |
| 462 |
/// |
| 463 |
/// Returns `Ok(planner_instance)` if this machine has the required instruction sets. |
| 464 |
/// Returns `Err(())` if some instruction sets are missing. |
| 465 |
pub fn new() -> Result<Self, ()> { |
| 466 |
Err(()) |
| 467 |
} |
| 468 |
/// Returns a `Fft` instance which uses Neon instructions to compute FFTs of size `len`. |
| 469 |
/// |
| 470 |
/// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs. |
| 471 |
/// |
| 472 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 473 |
pub fn plan_fft(&mut self, _len: usize, _direction: FftDirection) -> Arc<dyn Fft<T>> { |
| 474 |
unreachable!() |
| 475 |
} |
| 476 |
/// Returns a `Fft` instance which uses Neon instructions to compute forward FFTs of size `len`. |
| 477 |
/// |
| 478 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 479 |
pub fn plan_fft_forward(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 480 |
unreachable!() |
| 481 |
} |
| 482 |
/// Returns a `Fft` instance which uses Neon instructions to compute inverse FFTs of size `len. |
| 483 |
/// |
| 484 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 485 |
pub fn plan_fft_inverse(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 486 |
unreachable!() |
| 487 |
} |
| 488 |
} |
| 489 |
} |
| 490 |
} |
| 491 |
|
| 492 |
pub use self::neon::neon_planner::FftPlannerNeon; |
| 493 |
|
| 494 |
#[cfg(all(target_arch = "wasm32", feature = "wasm_simd"))] |
| 495 |
mod wasm_simd; |
| 496 |
|
| 497 |
// If we're not compiling to WebAssembly, or if the "wasm_simd" feature was disabled, keep a stub implementation around that has the same API, but does nothing |
| 498 |
// That way, users can write code using the WASM planner and compile it on any platform |
| 499 |
#[cfg(not(all(target_arch = "wasm32", feature = "wasm_simd")))] |
| 500 |
mod wasm_simd { |
| 501 |
pub mod wasm_simd_planner { |
| 502 |
use crate::{Fft, FftDirection, FftNum}; |
| 503 |
use std::sync::Arc; |
| 504 |
|
| 505 |
/// The WASM FFT planner creates new FFT algorithm instances using a mix of scalar and WASM SIMD accelerated algorithms. |
| 506 |
/// It is supported when using fairly recent browser versions as outlined in [the WebAssembly roadmap](https://webassembly.org/roadmap/). |
| 507 |
/// |
| 508 |
/// RustFFT has several FFT algorithms available. For a given FFT size, `FftPlannerWasmSimd` decides which of the |
| 509 |
/// available FFT algorithms to use and then initializes them. |
| 510 |
/// |
| 511 |
/// ~~~ |
| 512 |
/// // Perform a forward Fft of size 1234 |
| 513 |
/// use std::sync::Arc; |
| 514 |
/// use rustfft::{FftPlannerWasmSimd, num_complex::Complex}; |
| 515 |
/// |
| 516 |
/// if let Ok(mut planner) = FftPlannerWasmSimd::new() { |
| 517 |
/// let fft = planner.plan_fft_forward(1234); |
| 518 |
/// |
| 519 |
/// let mut buffer = vec![Complex{ re: 0.0f32, im: 0.0f32 }; 1234]; |
| 520 |
/// fft.process(&mut buffer); |
| 521 |
/// |
| 522 |
/// // The FFT instance returned by the planner has the type `Arc<dyn Fft<T>>`, |
| 523 |
/// // where T is the numeric type, ie f32 or f64, so it's cheap to clone |
| 524 |
/// let fft_clone = Arc::clone(&fft); |
| 525 |
/// } |
| 526 |
/// ~~~ |
| 527 |
/// |
| 528 |
/// If you plan on creating multiple FFT instances, it is recommended to reuse the same planner for all of them. This |
| 529 |
/// is because the planner re-uses internal data across FFT instances wherever possible, saving memory and reducing |
| 530 |
/// setup time. (FFT instances created with one planner will never re-use data and buffers with FFT instances created |
| 531 |
/// by a different planner) |
| 532 |
/// |
| 533 |
/// Each FFT instance owns [`Arc`s](std::sync::Arc) to its internal data, rather than borrowing it from the planner, so it's perfectly |
| 534 |
/// safe to drop the planner after creating Fft instances. |
| 535 |
pub struct FftPlannerWasmSimd<T: FftNum> { |
| 536 |
_phantom: std::marker::PhantomData<T>, |
| 537 |
} |
| 538 |
impl<T: FftNum> FftPlannerWasmSimd<T> { |
| 539 |
/// Creates a new `FftPlannerWasmSimd` instance. |
| 540 |
/// |
| 541 |
/// Returns `Ok(planner_instance)` if this machine has the required instruction sets. |
| 542 |
/// Returns `Err(())` if some instruction sets are missing. |
| 543 |
pub fn new() -> Result<Self, ()> { |
| 544 |
Err(()) |
| 545 |
} |
| 546 |
/// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute FFTs of size `len`. |
| 547 |
/// |
| 548 |
/// If the provided `direction` is `FftDirection::Forward`, the returned instance will compute forward FFTs. If it's `FftDirection::Inverse`, it will compute inverse FFTs. |
| 549 |
/// |
| 550 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 551 |
pub fn plan_fft(&mut self, _len: usize, _direction: FftDirection) -> Arc<dyn Fft<T>> { |
| 552 |
unreachable!() |
| 553 |
} |
| 554 |
/// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute forward FFTs of size `len`. |
| 555 |
/// |
| 556 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 557 |
pub fn plan_fft_forward(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 558 |
unreachable!() |
| 559 |
} |
| 560 |
/// Returns a `Fft` instance which uses WebAssembly SIMD instructions to compute inverse FFTs of size `len. |
| 561 |
/// |
| 562 |
/// If this is called multiple times, the planner will attempt to re-use internal data between calls, reducing memory usage and FFT initialization time. |
| 563 |
pub fn plan_fft_inverse(&mut self, _len: usize) -> Arc<dyn Fft<T>> { |
| 564 |
unreachable!() |
| 565 |
} |
| 566 |
} |
| 567 |
} |
| 568 |
} |
| 569 |
|
| 570 |
pub use self::wasm_simd::wasm_simd_planner::FftPlannerWasmSimd; |
| 571 |
|
| 572 |
#[cfg(test)] |
| 573 |
mod test_utils; |