calebzulawski / fourier Goto Github PK

I might have a slightly niche use-case which is running FFT on microcontrollers. I have patched various FFT implementations to not require std or allocation, and it would be nice if I could switch to this crate instead since it seems to have a very sane architecture and should perform better in theory.

Having no_std+no alloc support also has the advantage that it's easier to get consistent behavior in real-time low-latency situations. I'm using FFT for real-time signal processing on a microcontroller, but even someone doing the same in a hosted (OS) environment would benefit from the reduced footprint, too.

Tests are performed on values generated by a Python script and stored in JSON files. These files are huge and make up most of the crate size. The tests could probably just use a naive DFT implementation to compare against.

Constant Q Transform is a transformation for audio that uses a log scale for the frequency instead of a linear scale like FFT does. A fast implementation of Constant Q Transform uses FFT and a kernel.

https://en.wikipedia.org/wiki/Constant-Q_transform
http://academics.wellesley.edu/Physics/brown/pubs/effalgV92P2698-P2701.pdf

CQT is implemented in ffmpeg en mpv and gives intuitive visualization of which notes are being played at a given time.

https://trac.ffmpeg.org/wiki/FancyFilteringExamples#showcqt

The mixed-radix FFT algorithm's performance isn't too bad (at the time of writing, powers of three are something like 60% slower than FFTW on my machine).

However, the mixed-radix algorithm (at least as it exists right now) isn't the best choice for powers of two (approximately 3x slower than FFTW on my machine). I have to imagine the discrepancy here is that FFTW is probably using a modified split-radix algorithm. I'd probably be happy with a standard split-radix implementation for simplicity.

As discussed in #7, precision testing could be done with a high precision DFT.

Since AVX-512 intrinsics are nightly-only, a nightly feature could enable this support.

I believe that this library can get the tempo, pitch/key signature and loudness of an audio file. I am not too sure how would I implement this? Is there some sample code available out there?

When profiling with perf, a huge amount of time (40-60% of the entire transform) seems to be spent in the very first "narrow SIMD" pass, where the stride isn't large enough to fill an entire SIMD vector. Right now there is an optimization for radix-4 on AVX, but even with that the performance is underwhelming.

Since arm/aarch64 intrinsics are nightly-only, a nightly feature could enable this support.

Since I am fairly new to rust, I have a hard time understanding how to use this library.
It would be great if that could be expanded

I'm not a web guy, so I'm not sure what an idiomatic JavaScript/TypeScript interface should look like, but I imagine there's a desire for fast web FFTs and I imagine it should be reasonably easy to build for wasm32-unknown-unknown.

Real-valued FFTs have lots of optimizations and are relevant in some domains (audio?) so this would be a good thing to add. I imagine this should be a new trait that's slightly different than Fft, since it should produce both half- and full-spectrum outputs (maybe an implementation-specific ordered output as well).

This was partially completed, but only fourier-algorithms was released. The fourier crate itself must be updated.

Prompted by rust-lang/rust#79908.

The currently supported radices are 2, 3, 4, and 8. Small primes 5 and 7 should be added for parity with other FFT libraries. Larger powers of two might be desirable for performance.

Not sure if that is something with my setup (did a rustup yesterday), but when I clone this repo and do cargo build, I'm getting:

    Updating crates.io index
    Updating git repository `http://github.com/calebzulawski/multiversion`
error: failed to select a version for the requirement `multiversion = "^0.3"`
  candidate versions found which didn't match: 0.5.0
  location searched: Git repository http://github.com/calebzulawski/multiversion
required by package `fourier-algorithms v0.1.0 (/tmp/fourier/fourier-algorithms)`

The dependency is specified as:

multiversion = { git = "http://github.com/calebzulawski/multiversion", version = "0.3", default-features = false }

I've seen that multiversion has just been updated. Is it possible that cargo fails to handle the git tags somehow? If I remove the version specification it works fine.