Metadata-Version: 2.4
Name: blitzfft
Version: 0.1.0
Classifier: Development Status :: 3 - Alpha
Classifier: Environment :: Console
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: MacOS
Classifier: Operating System :: Microsoft :: Windows
Classifier: Operating System :: POSIX :: Linux
Classifier: Programming Language :: Rust
Classifier: Topic :: Multimedia :: Sound/Audio :: Analysis
License-File: LICENSE
Summary: Native Rust FFT analysis and benchmarking CLI for audio
Author-email: Colby Leider <colby@leider.org>
License-Expression: MIT
Requires-Python: >=3.9
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Homepage, https://github.com/TheColby/BlitzFFT
Project-URL: Issues, https://github.com/TheColby/BlitzFFT/issues
Project-URL: Repository, https://github.com/TheColby/BlitzFFT

# BlitzFFT

`BlitzFFT` is a Rust CLI for audio Fourier analysis and exact whole-signal FFT benchmarking, with a native Rust CPU engine, `64-bit` CPU processing, and an opt-in experimental `128-bit` `binary128` CPU mode for framed analysis on nightly Rust.
It has three complementary jobs:

- framed analysis, similar to an STFT pipeline, with backend auto-selection `CUDA -> Metal -> CPU`
- with frequency estimation errors of ±0.0000028 Hz (vs ±0.023 Hz for 32-bit) on an hour-long window, provide >180 dB SNR for scientific instrumentation applications
- exact whole-file FFT benchmarking on one long real-valued waveform, with a pure-Rust default comparison set and optional foreign-library comparisons

This repository is partly a tool and partly a notebook on FFT implementation tradeoffs. The code is useful on its own, but it is also a compact place to compare:

- framed versus whole-signal analysis
- real-input FFTs versus complex-input FFTs
- stable `64-bit` processing versus experimental `128-bit` processing
- GPU throughput versus CPU planning and execution costs
- simple libraries versus highly tuned planners
- power-of-two framing constraints versus arbitrary-length exact transforms

## Table of Contents

- [Why this repo exists](#why-this-repo-exists)
- [What changed recently](#what-changed-recently)
- [How To Make It Better](#how-to-make-it-better)
- [What an FFT is](#what-an-fft-is)
- [Math conventions used in this repo](#math-conventions-used-in-this-repo)
- [Why real-input FFTs matter](#why-real-input-ffts-matter)
- [How BlitzFFT uses FFTs](#how-blitzfft-uses-ffts)
- [Project architecture](#project-architecture)
- [Install](#install)
- [Build](#build)
- [CLI](#cli)
- [Examples](#examples)
- [Whole-file benchmark methodology](#whole-file-benchmark-methodology)
- [Simulated 60-minute whole-file FFT at 384 kHz](#simulated-60-minute-whole-file-fft-at-384-khz)
- [Estimated scaling to multi-day FFTs at 384 kHz](#estimated-scaling-to-multi-day-ffts-at-384-khz)
- [Roadmap](ROADMAP.md)
- [Repository layout](#repository-layout)
- [Reference map](#reference-map)
- [License](#license)

## Why this repo exists

There are many excellent FFT libraries already. `BlitzFFT` is not trying to replace them all with a single universal implementation. Instead, the repo tries to answer a more practical question:

> For audio work on a real machine, what actually changes when we switch the transform shape, the backend, the planning model, and the library?

That leads to two different workflows:

1. Framed analysis for ordinary audio inspection.
2. Exact whole-file transforms for benchmark and algorithm comparisons.

The framed path is the one most people expect from "audio FFT" software: split a waveform into overlapping windows, apply a tapering function, and transform each frame independently. That is what you want for time-local spectral analysis, spectrogram generation, transient inspection, and quick peak summaries.

The whole-file path is different. It treats the entire waveform as one signal and computes one exact forward FFT over the full sample count. That is useful when you care about:

- exact bin spacing for a long observation interval
- arbitrary, non-power-of-two signal lengths
- comparing library setup cost versus execution cost
- measuring how much work is saved by exploiting real-valued input structure

## What changed recently

- The CPU framed backend now uses the native BlitzFFT engine instead of materializing a full complex `RustFFT` input buffer for every frame.
- Framed results no longer allocate an unused full complex spectrum for each frame.
- The framed `f32` CPU path can batch pairs of real frames by packing one frame into the complex real lane and the next frame into the imaginary lane, then recovering both real spectra from one complex FFT.
- The native `f64` power-of-two CPU FFT path now uses SIMD butterflies on supported `x86_64` and `aarch64` machines.
- Bluestein's arbitrary-length convolution now reuses the native power-of-two SIMD plan and its precomputed twiddles.
- The native power-of-two kernel fuses its first two butterfly stages, and Bluestein avoids separate full-buffer conjugation and scaling passes. On one Apple Silicon release build, the median `f64` execution time at `65,521` samples fell from about `3.19` ms to `3.00` ms across repeated local trials; the `65,536`-sample case fell from about `0.345` ms to `0.320` ms. These are workload-specific measurements, not a general speed claim.
- CPU `--top-bins` output keeps only the requested bins per frame in `f32` and `f64` modes.
- `--precision 32 --backend cpu --summary -f none` now scans peaks directly, avoiding per-frame magnitude arrays.
- The repo now has an exact whole-file benchmark path for long real-valued signals, including non-power-of-two lengths.
- The default whole-file benchmark compares three native-Rust paths side by side: `BlitzFFT native`, `RealFFT`, and `RustFFT complex`.
- Optional `FFTW3f`, `KissFFT`, and `PocketFFT` comparisons can be enabled explicitly with Cargo features.
- The benchmark docs now center a simulated one-hour `384` kHz scenario using a `439.997` Hz sine and a full-signal Hann window.

## How To Make It Better

If we want BlitzFFT to become meaningfully better, the next work should stay focused on a few concrete themes.

### 1. Make the native engine faster where it actually matters

The biggest remaining speed opportunity is the native CPU FFT core, especially the `f64` whole-file path and the arbitrary-length Bluestein path. That means:

- measure and tune the existing `f64` SIMD kernels
- keep reducing copies and scratch churn in the real-input kernels
- benchmark the new Bluestein inner plan across awkward lengths and tune it further
- extend the summary and top-bin memory savings to other precisions and GPU backends

### 2. Keep every speed claim tied to correctness

This repo gets better when optimizations come with tests, not just faster tables. The native engine needs broader randomized checks, more cross-validation against `rustfft` and `realfft`, and clearer documented tolerances for `f32` and `f64`.

### 3. Keep the default build simple

The default story should remain: stable Rust, native CPU path, no required foreign FFT libraries. Optional GPU and comparison backends are valuable, but they should stay optional enough that the core tool remains easy to build and trust.

### 4. Make the CLI do less unnecessary work

The `f32` CPU path computes peak summaries without storing every magnitude when using `--summary -f none`. CPU `--top-bins` output uses bounded per-frame storage in `f32` and `f64` modes. Other precision modes and GPU backends remain opportunities to avoid unnecessary storage and formatting.

### 5. Make benchmark docs even easier to trust

The benchmark presentation is much stronger now than it used to be, but the repo still improves when it makes measured versus simulated results unmistakable, records feature flags and machine details, and ships a reproducible benchmark workflow.

The longer-form plan lives in [ROADMAP.md](ROADMAP.md).

## What an FFT is

An FFT is a fast algorithm for computing the discrete Fourier transform, or DFT.

The DFT takes a finite list of samples and rewrites it as a sum of discrete complex sinusoids. Instead of asking "what is the sample value at time index $n$?", it asks "how much of frequency bin $k$ is present in the signal?"

For a length-$N$ signal $x[n]$, the forward DFT is

```math
X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi k n / N}, \qquad 0 \le k < N
```

and the inverse DFT is

```math
x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j 2 \pi k n / N}
```

If you implement that definition directly, it costs $O(N^2)$ operations. The FFT family of algorithms computes the same result in roughly $O(N \log N)$ time by factoring the problem into smaller transforms.

That is the whole reason FFTs matter. They do not change the transform being computed. They change the cost of computing it.

### Intuition

Some quick intuition helps:

- the time-domain signal is a sequence of samples
- the frequency-domain signal is a sequence of complex coefficients
- each coefficient describes the amplitude and phase of one discrete frequency bin
- a longer observation window gives finer frequency spacing
- a shorter observation window gives better time localization

The bin frequencies are

```math
f_k = \frac{k f_s}{N}
```

where $f_s$ is the sample rate. The frequency resolution is therefore

```math
\Delta f = \frac{f_s}{N}
```

This is why a one-hour signal at $48{,}000$ Hz has extremely fine bin spacing: the observation interval is very long, so the frequency grid is correspondingly dense.

### Why the FFT is "fast"

The most famous FFT family is the Cooley-Tukey decomposition. When $N$ factors as $N = N_1 N_2$, the transform can be reorganized into smaller pieces instead of recomputing every sinusoid against every sample from scratch. There are many variants:

- radix-2 and radix-4 decompositions
- mixed-radix decompositions
- split-radix variants
- prime-factor algorithms
- Bluestein and Rader methods for awkward lengths, especially primes

Different libraries package those ideas differently. Some are tiny and simple. Others, like FFTW, search over many possible plans and choose the fastest measured one for the host machine.

## Math conventions used in this repo

`BlitzFFT` follows the standard forward-transform sign convention with a negative exponential:

```math
e^{-j 2 \pi k n / N}
```

Some practical conventions matter when you compare FFT libraries:

- Most FFT libraries return an unnormalized forward transform.
- Normalization, if desired, is usually applied separately.
- For real-valued input, the negative-frequency half of the spectrum is redundant.

For a real signal,

```math
X[N-k] = \overline{X[k]}
```

so a real-input forward FFT only needs to return the nonnegative-frequency half-spectrum:

```math
k = 0, 1, \dots, \left\lfloor \frac{N}{2} \right\rfloor
```

That is why the positive-frequency output length is

```math
\frac{N}{2} + 1
```

for even $N$.

## Why real-input FFTs matter

Audio samples are real-valued. That sounds obvious, but it changes the implementation story a lot.

If you feed a real signal into a generic complex FFT, you usually have to:

1. allocate a complex buffer of length $N$
2. copy each real sample into the real part
3. set all imaginary parts to zero
4. compute a full complex FFT
5. ignore half the result because it is conjugate-redundant

A real-input FFT avoids most of that waste. In practical terms, that can mean:

- less input marshaling
- less memory traffic
- less output storage
- faster execution
- a cleaner API for audio workloads

`RealFFT` in Rust builds on `RustFFT` but exposes the real-to-complex path directly. `FFTW3f`, `KissFFT`, and `PocketFFT` also provide real-input transforms. This repo makes that comparison explicit.

### Paired real-frame batching

For framed `f32` CPU analysis, BlitzFFT also uses a related two-real-FFTs-in-one-complex-FFT trick. Given two real frames `a[n]` and `b[n]`, the CPU backend packs them as:

```math
z[n] = a[n] + i b[n]
```

It then computes one complex FFT and recovers the two real spectra with conjugate symmetry:

```math
A[k] = \frac{Z[k] + \overline{Z[N-k]}}{2}
```

```math
B[k] = \frac{Z[k] - \overline{Z[N-k]}}{2i}
```

This does not make the whole pipeline twice as fast, because packing, unpacking, magnitudes, memory traffic, and output still cost time. It does reduce transform scheduling overhead for frame-heavy workloads and keeps the all-real signal structure explicit in the native CPU backend.

## How BlitzFFT uses FFTs

There are two very different transform modes in this repository.

### 1. Framed analysis

The framed path is an STFT-style workflow:

1. load or synthesize audio
2. downmix to mono if needed
3. split the signal into overlapping frames
4. apply a Hann window per frame
5. compute one FFT per frame
6. emit magnitudes, summaries, CSV, or binary output

For frame index $m$, hop size $H$, and frame length $N$, the transform is

```math
X_m[k] = \sum_{n=0}^{N-1} x[n + mH] \, w[n] \, e^{-j 2 \pi k n / N}
```

where $w[n]$ is the analysis window.

The Hann window used in this repo is

```math
w[n] = \frac{1}{2} \left(1 - \cos\left(\frac{2 \pi n}{N - 1}\right)\right), \qquad 0 \le n < N
```

In the CPU framed backend, the transform work is done with cached native BlitzFFT plans plus thread-local work buffers. On Apple hardware, the Metal backend applies the frame window on-device. On NVIDIA systems, the CUDA backend is preferred when enabled and available.

### 2. Whole-file exact benchmark

The whole-file mode computes one forward FFT over the entire signal:

```math
X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi k n / N}
```

This is not an STFT. There is no hop size and no time-local frame index. You get one spectrum covering the full observation interval.

That is why the reported frequency resolution for the one-hour example is

```math
\Delta f = \frac{384000}{1382400000} = \frac{1}{3600} \approx 0.0002777778 \text{ Hz}
```

This mode exists to compare transform engines and data-motion costs, not to provide time-local spectral evolution.

### Tuning-theory interpretation of a tiny interval

The value above is a linear frequency-bin spacing in hertz. If, separately, you want to think about a similarly sized interval in logarithmic pitch space, take

```math
\Delta = 0.0002777778
```

interpreted as a base-2 log-frequency interval. The corresponding frequency ratio is

```math
\text{ratio} = 2^{0.0002777778} \approx 1.0001925
```

A cent, written `¢`, is one hundredth of a semitone, or `1/1200` of an octave. The equivalent size here is

```math
1200 \cdot 0.0002777778 = 0.33333336 \, \text{¢}
```

So that target interval is approximately:

- `0.3333 ¢`
- `1.0001925` as a frequency ratio

It is also exactly one step of `3600-EDO`, since

```math
\frac{1200}{3600} = \frac{1}{3} \, \text{¢}
```

per equal division of the octave.

This is smaller than the usual named commas in tuning theory. A useful nearby reference is one sixth of a schisma. Using

```math
\text{schisma} \approx 1.95 \, \text{¢}
```

gives

```math
\frac{1.95}{6} \approx 0.325 \, \text{¢}
```

so

```math
\frac{1}{6}\text{ schisma} \approx 0.325 \, \text{¢}
```

which is very close to `0.3333 ¢`, with an error of about `0.008 ¢`.

## Project architecture

At a high level, the project is organized like this:

- `src/main.rs`
  CLI parsing, input selection, framing, backend selection, and dispatch
- `src/audio.rs`
  WAV loading, mono downmixing, Hann windows, framing, sine synthesis, and bin-to-Hz conversion
- `src/backends/`
  framed FFT backends for CPU, Metal, and CUDA
- `src/benchmark.rs`
  framed benchmark harness comparing the selected backend against the CPU baseline
- `src/whole_fft.rs`
  exact whole-signal benchmark harness across multiple FFT libraries
- `src/native/pocketfft_bridge.cc`
  thin C++ bridge exposing vendored PocketFFT to Rust
- `vendor/kissfft/`
  vendored KISS FFT sources
- `vendor/pocketfft/`
  vendored PocketFFT header-only implementation

### Backend selection

Automatic backend selection is:

```text
CUDA -> Metal -> CPU
```

If you force a backend from the CLI, that explicit choice wins.

### What each whole-file benchmark entry means

The benchmark table compares closely related but not identical implementation styles:

- `BlitzFFT native`
  The repo's own native Rust real-input path with reusable plans, scratch buffers, and output buffers.
- `RealFFT`
  A direct `realfft` crate benchmark path that still uses a real-input transform, but with less aggressive buffer reuse in the harness.
- `RustFFT complex`
  A baseline that converts the real signal into a full complex buffer and runs a standard complex FFT.
- `FFTW3f`
  An optional single-precision real-to-complex FFTW path discovered from the local machine when the `fftw` feature is enabled.
- `KissFFT`
  An optional real FFT path from the vendored KISS FFT C implementation.
- `PocketFFT`
  An optional vendored C++ header-only path accessed through `src/native/pocketfft_bridge.cc`.

That means the benchmark is not just "algorithm A versus algorithm B". It is also measuring planning policy, data layout policy, and buffer-management style.

When `--precision 64` is selected, the whole-file benchmark currently uses the CPU-side `RealFFT` and `RustFFT` double-precision paths plus the repo's reusable native real-input path. The optional `PocketFFT`, `KissFFT`, and `FFTW3f` comparisons remain single-precision-only in this codebase today.

## Install

### pip (after the first PyPI release)

```bash
python3 -m pip install blitzfft
blitzfft --version
blitzfft --list-backends
```

This installs the `blitzfft` command-line executable, **not** a Python importable API. Published wheels contain the default native Rust CPU build; CUDA, Metal, experimental `binary128`, and foreign-library comparisons are still opt-in Cargo builds. PyPI installation is not available until the first release is published.

To install this checkout before then, install a Rust toolchain and run:

```bash
python3 -m pip install .
```

Source installs need Rust because the Python build backend compiles the CLI. Use a virtual environment if you do not want to modify your system Python environment.

### PyPI release registration

The project owner must create a **pending trusted publisher** for the `blitzfft` project on PyPI before the first upload. Set GitHub owner to `TheColby`, repository to `BlitzFFT`, workflow filename to `release.yml`, and environment to `pypi`. The pending publisher does not reserve the project name; confirm name availability and ownership before publishing. Configure a GitHub `pypi` environment, ideally with required reviewers. No PyPI API token is needed in repository secrets.

For a release, verify CI, create a `vX.Y.Z` tag matching `Cargo.toml`, and publish a GitHub Release for that tag. The [release workflow](.github/workflows/release.yml) builds platform wheels and a source distribution, then uploads them through PyPI trusted publishing. Do not publish an unreviewed release: PyPI version files cannot be replaced after upload.

See [PyPI's pending publisher instructions](https://docs.pypi.org/trusted-publishers/creating-a-project-through-oidc/) and [trusted publishing guide](https://docs.pypi.org/trusted-publishers/using-a-publisher/).

### Homebrew

BlitzFFT ships a head-only Homebrew formula in this repository. Until the project has tagged release tarballs, install the current `main` branch with:

```bash
brew install --HEAD ./Formula/blitzfft.rb
```

From outside a clone, you can install directly from the public formula URL:

```bash
brew install --HEAD https://raw.githubusercontent.com/TheColby/BlitzFFT/main/Formula/blitzfft.rb
```

After installation:

```bash
blitzfft --list-backends
blitzfft --generate-sine 440,48000,0.1 --summary -f none
```

The Homebrew formula builds the default native Rust CPU configuration. Optional comparison backends such as FFTW, KISS FFT, PocketFFT, CUDA, and Metal remain Cargo feature builds for now.

## Build

```bash
# Native Rust CPU build
cargo build --release

# Enable the optional foreign-library whole-file comparisons
cargo build --release --features foreign-fft

# Apple GPU backend
cargo build --release --features metal

# NVIDIA GPU backend
cargo build --release --features cuda

# Everything enabled, including optional comparison backends
cargo build --release --features "cuda metal foreign-fft"
```

### Build notes

- The default build is native Rust and does not require FFTW, KISS FFT, or PocketFFT.
- `--features foreign-fft` enables the optional comparison backends used in the larger whole-file benchmark tables.
- `FFTW3f` is only needed when the `fftw` feature is enabled.
- `build.rs` tries `pkg-config --libs --cflags fftw3f` first, then checks `/opt/homebrew/lib` and `/usr/local/lib` for `libfftw3f.dylib`.
- `KissFFT` is only compiled when the `kissfft` feature is enabled.
- `PocketFFT` is only compiled when the `pocketfft` feature is enabled through a small C++ bridge against the vendored header in `vendor/pocketfft/`.
- The Metal shader is built by `build.rs` when the `metal` feature is enabled.
- The CPU path always remains available.
- GitHub Actions now checks the default stable build on Linux and macOS, plus a Linux `foreign-fft` job with FFTW installed.

## CLI

The project name and binary name are both `blitzfft`.

```text
Usage: blitzfft [OPTIONS] [INPUT]

Arguments:
  [INPUT]  Input WAV file (16/24/32-bit PCM or f32)

Options:
      --list-backends                  List backend choices and whether they are compiled into this build
      --list-precisions               List precision modes and their build/runtime requirements
      --list-formats                  List output formats supported by this build
  -n, --fft-size <FFT_SIZE>            FFT frame size (must be a power of two) [default: 2048]
      --hop <HOP>                      Hop size in samples (default = fft_size/2)
      --batch-size <BATCH_SIZE>        Number of frames to process per GPU batch (default = all frames) [default: 0]
  -b, --backend <BACKEND>              Force a specific backend [default: auto]
      --channel <avg|left|right|N>     Input channel selection [default: avg]
      --window <WINDOW>                Window applied to each analysis frame [default: hann] [possible values: rect, hann, hamming, blackman]
      --precision <PRECISION>          Internal processing precision in bits [default: 64] [possible values: 32, 64, 128]
  -o, --output <PATH>                  Output file (optional; stdout if omitted for text/csv)
  -f, --format <FORMAT>                Output format [default: text]
      --min-hz <MIN_HZ>                Only emit bins at or above this frequency
      --max-hz <MAX_HZ>                Only emit bins at or below this frequency
      --top-bins <TOP_BINS>            Only emit the N loudest bins per frame (0 = all bins) [default: 0]
      --benchmark                      Run framed benchmark comparing selected backend against CPU baseline
      --bench-repeats <BENCH_REPEATS>  Number of benchmark repeats [default: 5]
      --whole-file-benchmark           Run one exact FFT over the entire signal
      --generate-sine <Hz,SR,Secs>     Synthesize a sine wave in memory
      --write-generated-wav <PATH>     Persist the generated/loaded mono signal as 32-bit float WAV
      --full-window <FULL_WINDOW>      Apply a window across the entire loaded/generated signal before whole-file FFT
      --apply-full-hann                Apply a Hann window across the entire loaded/generated signal
      --summary                        Print per-frame peak-frequency summary to stdout
```

### Input and output behavior

- WAV input supports 16-bit PCM, 24-bit PCM, 32-bit PCM, and 32-bit float.
- Multi-channel input can be averaged to mono or a single channel can be selected with `--channel`.
- Framed output can be emitted as `text`, `csv`, `json`, `bin`, or `none`.
- `--min-hz` and `--max-hz` limit emitted `text`, `csv`, and `json` bins plus summary peaks to a frequency band.
- `--window` controls framed analysis windows, while `--full-window` applies a whole-signal window before an exact whole-file FFT.
- `--precision 64` enables double-precision CPU processing for framed analysis and a reduced whole-file benchmark set.
- `--precision 128` enables an experimental true `binary128` CPU path for framed analysis when the crate is built with `--features binary128` on nightly Rust.
- `--precision 128` currently does not support `--whole-file-benchmark`, and it does not use GPU backends.
- Whole-file benchmark mode prints a comparison table and exits.
- `--list-backends`, `--list-precisions`, and `--list-formats` work without an input file and report what this build supports.

## Examples

### Show build capabilities

```bash
blitzfft --list-backends
blitzfft --list-precisions
blitzfft --list-formats
```

### Run the parallel Python reference CLI

```bash
python3 scripts/blitzfft_parallel.py --generate-sine 440,48000,0.05 --summary --format none
```

The Python script in `scripts/blitzfft_parallel.py` is a dependency-light framed-analysis reference path. It uses a pure-Python radix-2 FFT and prefers process parallelism, but it automatically falls back to a thread executor on restricted systems where process pools are unavailable.

### Standard framed analysis

```bash
cargo run --release -- input.wav --backend cpu --summary -f none
```

### Analyze only the left channel in a frequency band

```bash
cargo run --release -- input.wav --channel left --min-hz 80 --max-hz 5000 --summary -f none
```

### Run framed analysis in double precision

```bash
cargo run --release -- input.wav --precision 64 --backend cpu --summary -f none
```

### Run framed analysis in experimental true 128-bit precision

```bash
cargo +nightly run --release --features binary128 -- input.wav --precision 128 --backend cpu --summary -f none
```

The current `128-bit` path is intentionally opt-in. It uses Rust's unstable `f128` type behind the `binary128` Cargo feature, with crate-local math helpers for trig and square root. The default build stays on stable Rust; if you pass `--precision 128` without that feature, the CLI exits with a clear error.

### Framed benchmark against the CPU baseline

```bash
cargo run --release -- input.wav --benchmark --bench-repeats 5 -f none
```

### Whole-file exact FFT benchmark on an existing WAV

```bash
cargo run --release -- input.wav --full-window hann --whole-file-benchmark --bench-repeats 1 -f none
```

### Whole-file benchmark in double precision

```bash
cargo run --release -- input.wav --precision 64 --backend cpu --full-window hann --whole-file-benchmark --bench-repeats 1 -f none
```

### Generate a sine wave and benchmark the entire signal

```bash
target/release/blitzfft \
  --generate-sine 439.997,384000,3600 \
  --apply-full-hann \
  --write-generated-wav data/sine_439p997hz_60min_384khz_f32_hann.wav \
  --whole-file-benchmark \
  --bench-repeats 1 \
  -f none
```

### Export framed magnitudes to CSV

```bash
cargo run --release -- input.wav --fft-size 4096 --hop 1024 --format csv --output spectrum.csv
```

### Export filtered spectra as JSON

```bash
cargo run --release -- input.wav --window blackman --min-hz 20 --max-hz 2000 --format json --output spectrum.json
```

## Whole-file benchmark methodology

This section matters because FFT benchmarks are easy to misread.

### Reproduce measured comparisons

The standard-library-only runner builds the release binary and records the Git commit, dirty-tree status, OS, architecture, CPU count, Rust toolchain, Cargo features, signal settings, exact CLI commands, and per-trial results in JSON:

```bash
python3 scripts/measure_whole_fft.py --precision 64 --sizes 1009 1024 4093 4096 65521 65536 --repeats 5 --trials 3 --output /tmp/blitzfft-measured.json
```

The default size pairs contrast awkward Bluestein lengths with nearby power-of-two lengths. Use `--precision 32` and optionally `--features foreign-fft` for other available comparisons. Every JSON row is a measurement on the local machine; it is not the simulated `384` kHz one-hour projection below. The runner uses an unwindowed synthetic sine and records separate setup and execution times. The CLI benchmark runs algorithms in a fixed order, so thermal state and cache effects can influence close results. For a published claim, retain the JSON artifact, use a clean commit, and report the median over trials with the hardware and feature flags.

### What is being timed

The whole-file table reports two times:

- `Setup`
  planner creation, config creation, allocation, or equivalent transform preparation
- `Exec`
  one measured transform call, excluding WAV load time and excluding repeat-to-repeat input restoration performed by the benchmark harness

That distinction is important. A planner-heavy library can look slower in one-shot runs even if it is excellent when a plan is reused many times. Conversely, a lightweight library can look great in a single transform but lose ground when the workload changes shape or dimensionality.

### What the benchmark is not claiming

The table is useful, but it is not a universal ranking of FFT libraries.

It does **not** mean:

- the fastest library here is always fastest for every size and workload
- the slowest library here is poorly engineered
- framed STFT workloads will behave the same way as one giant transform
- setup and execution costs will scale identically on every machine

It **does** show:

- how these exact implementations behave in this repository
- how much real-input optimization changes the picture
- how much data conversion overhead hurts the full complex baseline
- how sharp the frequency resolution becomes when $N$ is very large

### Why the full-signal Hann window is included

The benchmark asset is windowed across the **entire** one-hour signal before the exact whole-file FFT. That is unusual compared with frame-by-frame STFT work, but it makes the benchmarked signal handling explicit and reproducible.

The full-signal Hann is

```math
w[n] = \frac{1}{2} \left(1 - \cos\left(\frac{2 \pi n}{N - 1}\right)\right)
```

applied for $0 \le n < N$ across the entire loaded or synthesized waveform.

## Simulated 60-minute whole-file FFT at 384 kHz

Updated on `2026-04-01` for a mono $384$ kHz, `32-bit` float, one-hour sine-wave scenario with:

- frequency: `439.997 Hz`
- duration: `3600 s`
- samples: `1,382,400,000`
- frequency resolution:

```math
\Delta f = \frac{384000}{1382400000} = \frac{1}{3600} \approx 0.0002777778 \text{ Hz}
```

- nearest-bin frequency to the target sine:

```math
f_{\text{peak}} = \frac{1{,}583{,}989}{3600} \approx 439.996944444444 \text{ Hz}
```

- window: full-signal Hann window applied before the FFT
- command: the reproduction command shown above

The corresponding WAV would be about `5.15 GiB` on disk. In this workspace, the one-hour `384` kHz benchmark is treated as a simulation anchored to the measured `48` kHz run, because a direct six-library exact rerun at `1.3824` billion samples would exceed practical local memory and disk limits.

The table below therefore reports a simulated one-hour anchor. `Exec` is projected with the same $N \log_2 N$ model used in the scaling graph. In the live CLI benchmark table, `Peak est. (Hz)` is a quadratic sub-bin estimate around the loudest FFT bin and is printed to a conservative `12` decimal places to avoid implying more certainty than the `f64` estimate can support. The simulated table below still shows the common nearest-bin center because this `384` kHz one-hour case is modeled rather than freshly rerun.

| Algorithm | Setup (s) | Exec (s) | Peak bin | Peak est. (Hz) |
|---|---:|---:|---:|---:|
| PocketFFT | simulated | 10.776736 | 1,583,989 | 439.996944444444 |
| RealFFT | simulated | 20.514858 | 1,583,989 | 439.996944444444 |
| BlitzFFT native | simulated | 22.263636 | 1,583,989 | 439.996944444444 |
| FFTW3f | simulated | 36.360388 | 1,583,989 | 439.996944444444 |
| RustFFT complex | simulated | 38.872592 | 1,583,989 | 439.996944444444 |
| KissFFT | simulated | 46.515731 | 1,583,989 | 439.996944444444 |

The same numbers are also recorded in [`benchmarks/60min_whole_file_fft.md`](benchmarks/60min_whole_file_fft.md).

On a measured shorter run, the extra resolution does expose tiny implementation differences. For example, with

```bash
cargo run --release -- --generate-sine 439.997,48000,10 --precision 32 --apply-full-hann --whole-file-benchmark --bench-repeats 1 -f none
```

the interpolated peak estimates come out as:

| Algorithm | Peak bin | Peak est. (Hz) |
|---|---:|---:|
| BlitzFFT native | 4,400 | 439.997757311980877 |
| RealFFT | 4,400 | 439.997757311980877 |
| RustFFT complex | 4,400 | 439.997757318645654 |
| FFTW3f | 4,400 | 439.997757317381456 |
| KissFFT | 4,400 | 439.997757313537420 |
| PocketFFT | 4,400 | 439.997757311980877 |

## Estimated scaling to multi-day FFTs at 384 kHz

The simulated table above gives one exact-size anchor point at

```math
N_0 = 1{,}382{,}400{,}000
```

samples, or one hour of mono audio at $384$ kHz.

To visualize how the whole-file execution time should grow as the FFT gets longer, the graph below extrapolates each algorithm's simulated `Exec` time with an $N \log_2 N$ model:

```math
\hat{T}(N) = T(N_0) \frac{N \log_2 N}{N_0 \log_2 N_0}
```

This is an **execution-time scaling estimate**, not a fresh measured benchmark at every duration. The one-hour `384` kHz anchor is itself simulated from the measured `48` kHz benchmark by the same $N \log_2 N$ model. It does not try to model planner heuristics, cache cliffs, allocator behavior, out-of-core I/O, or OS-level memory pressure for truly enormous transforms.

To regenerate the chart after updating the anchor timings, run:

```bash
python3 scripts/generate_whole_fft_scaling_svg.py
```

![Estimated whole-file FFT execution time scaling](benchmarks/whole_file_fft_scaling.svg)

At the multi-day end of that estimate, the projected execution times at $384$ kHz are:

| Duration | Samples | PocketFFT | RealFFT | BlitzFFT native | FFTW3f | RustFFT complex | KissFFT |
|---|---:|---:|---:|---:|---:|---:|---:|
| 24 hr | 33,177,600,000 | 297.696 s | 566.701 s | 615.009 s | 1004.417 s | 1073.814 s | 1284.948 s |
| 48 hr | 66,355,200,000 | 612.428 s | 1165.832 s | 1265.213 s | 2066.312 s | 2209.077 s | 2643.427 s |
| 72 hr | 99,532,800,000 | 933.589 s | 1777.203 s | 1928.700 s | 3149.902 s | 3367.535 s | 4029.660 s |

## Repository layout

```text
BlitzFFT/
|- Formula/
|  `- blitzfft.rb
|- data/
|  `- generated benchmark WAVs (for example, a 384 kHz 60-minute sine asset; not checked in)
|- src/
|  |- main.rs
|  |- audio.rs
|  |- benchmark.rs
|  |- output.rs
|  |- whole_fft.rs
|  |- native/
|  |  `- pocketfft_bridge.cc
|  `- backends/
|     |- mod.rs
|     |- cpu.rs
|     |- cuda.rs
|     `- metal.rs
|- vendor/
|  |- kissfft/
|  `- pocketfft/
`- shaders/
   `- fft.metal
```

## Reference map

This section is intentionally broad and repo-focused. It is not literally the entire FFT literature, but it does collect the main sources relevant to the theory, libraries, and design choices that appear in `BlitzFFT`.

### Core FFT and DFT references

- J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," *Mathematics of Computation*, 1965. DOI: [10.1090/S0025-5718-1965-0178586-1](https://doi.org/10.1090/S0025-5718-1965-0178586-1)
- Matteo Frigo and Steven G. Johnson, "The Design and Implementation of FFTW3," *Proceedings of the IEEE*, 2005. PDF: [fftw-paper-ieee.pdf](https://www.fftw.org/fftw-paper-ieee.pdf)
- FFTW manual, especially "What FFTW Really Computes": [https://www.fftw.org/doc/](https://www.fftw.org/doc/)
- FFTPACK at Netlib, important because PocketFFT is a heavily modified FFTPACK descendant: [https://www.netlib.org/fftpack/](https://www.netlib.org/fftpack/)
- Bluestein-style handling of difficult lengths is summarized in the PocketFFT README and commonly associated with the chirp z-transform family: [https://en.wikipedia.org/wiki/Chirp_Z-transform](https://en.wikipedia.org/wiki/Chirp_Z-transform)

### Windowing and spectral analysis references

- F. J. Harris, "On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform," *Proceedings of the IEEE*, 1978. DOI: [10.1109/PROC.1978.10837](https://doi.org/10.1109/PROC.1978.10837)
- Julius O. Smith III, online DSP references on spectral analysis and windows: [https://ccrma.stanford.edu/~jos/](https://ccrma.stanford.edu/~jos/)

### FFTW references

- FFTW home page: [https://www.fftw.org/](https://www.fftw.org/)
- FFTW manual top page: [https://www.fftw.org/doc/](https://www.fftw.org/doc/)
- FFTW paper: [https://www.fftw.org/fftw-paper-ieee.pdf](https://www.fftw.org/fftw-paper-ieee.pdf)
- Relevant manual topics for this repo:
  - planner and wisdom
  - real-data DFTs
  - "What FFTW Really Computes"

### KISS FFT references

- Upstream repository: [https://github.com/mborgerding/kissfft](https://github.com/mborgerding/kissfft)
- Upstream README: [https://github.com/mborgerding/kissfft/blob/master/README.md](https://github.com/mborgerding/kissfft/blob/master/README.md)
- Vendored copy in this repo: [`vendor/kissfft/README.md`](vendor/kissfft/README.md)
- SIMD notes: [`vendor/kissfft/README.simd`](vendor/kissfft/README.simd)

Why it matters here: KISS FFT is a good contrast case against FFTW. It aims to stay simple and reasonably efficient rather than planner-heavy and maximally optimized for every machine.

### PocketFFT references

- Original upstream noted by the GitHub mirror: [https://gitlab.mpcdf.mpg.de/mtr/pocketfft](https://gitlab.mpcdf.mpg.de/mtr/pocketfft)
- GitHub mirror used as a convenient public reference: [https://github.com/mreineck/pocketfft](https://github.com/mreineck/pocketfft)
- Vendored README in this repo: [`vendor/pocketfft/README.md`](vendor/pocketfft/README.md)
- PocketFFT README highlights relevant to this repo:
  - real-to-complex and complex-to-real transforms
  - mixed support for awkward sizes
  - Bluestein handling for large prime factors
  - plan caching for repeated sizes

Why it matters here: PocketFFT is a strong exact-whole-signal comparison point because it is compact, modern C++, and explicitly optimized for more than just textbook radix-2 cases.

### RustFFT and RealFFT references

- `rustfft` crate docs: [https://docs.rs/crate/rustfft/latest](https://docs.rs/crate/rustfft/latest)
- `realfft` crate docs: [https://docs.rs/crate/realfft/latest](https://docs.rs/crate/realfft/latest)
- `realfft` crate summary: it wraps `rustfft` to expose real-to-complex and complex-to-real transforms directly, avoiding manual real-to-complex expansion in user code

Why they matter here:

- the framed CPU backend uses the native BlitzFFT engine
- the whole-file benchmark compares `RealFFT` and `RustFFT complex` directly
- the repo's native whole-file path is mostly about planner and buffer reuse around a real-input transform, not about inventing a brand-new Fourier algorithm

### Repo-local implementation references

- [`src/audio.rs`](src/audio.rs)
  WAV loading, mono downmixing, Hann window generation, and framing
- [`src/backends/cpu.rs`](src/backends/cpu.rs)
  native BlitzFFT CPU execution paths plus reusable work buffers
- [`src/whole_fft.rs`](src/whole_fft.rs)
  exact whole-signal benchmark harness and per-library bridge code
- [`src/native/pocketfft_bridge.cc`](src/native/pocketfft_bridge.cc)
  Rust-to-PocketFFT bridge
- [`build.rs`](build.rs)
  optional foreign-backend compilation/linking plus Metal shader compilation

## License

MIT

