Module fft 

WGSL radix-2 Cooley-Tukey FFT (Cooley & Tukey 1965) — host plan + shader.

Implements the P2 roadmap item shader/fft_wgsl.rs: a compute-only FFT dispatch suitable for browsers, expressed as a single iterative Cooley-Tukey butterfly kernel plus a host-side WgslFftPlan that carries the bit-reversal permutation and the twiddle-factor table.

The plan (bit-reversal indices, twiddle factors) is pure CPU arithmetic and is fully unit-tested here. The shader-source generation is likewise CPU-testable structurally. Actually running the kernel on a GPU is gated on a real adapter and is not exercised here.

Layout

Complex data is stored interleaved: element i occupies indices 2*i (real) and 2*i + 1 (imaginary). An in-place radix-2 DIT FFT proceeds in log2(n) stages; each stage applies butterflies with stride m = 2^stage.

The host first bit-reverses the input into the natural-order scratch buffer (or vice-versa), then dispatches one fft_stage_wgsl pass per stage with a FftStageParams uniform carrying the current half_size and the per-stage twiddle base. Twiddles W_N^k = exp(-2πi k / N) are precomputed by WgslFftPlan::twiddles so the shader needs no sin/cos.

Structs

WgslFftPlan

A host-side plan for a power-of-two radix-2 Cooley-Tukey FFT of length n.

Enums

FftDirection

FFT transform direction.

Functions

fft_bitreverse_wgsl

Generate WGSL for the bit-reversal reorder pass.

fft_stage_wgsl

Generate WGSL for a single radix-2 Cooley-Tukey butterfly stage (DIT).

reverse_bits

Reverse the low bits bits of value.