For a music visualizer to respond dynamically to a song, it must understand the structure of the sound. Real-time audio arrives in the time domain as a stream of raw pressure amplitudes (PCM samples). To extract individual pitches — separating a thumping bassline from a high-pitched hi-hat — we must convert this signal into the frequency domain.
In ShoggothOx, this conversion is performed using a high-performance Fast Fourier Transform (FFT) algorithm. Specifically, we implement an in-place radix-2 decimation-in-time algorithm to extract the frequency spectrum of 1024 audio samples at a time.
Formally, a discrete audio signal is mapped to its frequency components via the Discrete Fourier Transform (DFT). Given N complex samples xn, the transform is defined as:
Xk = ∑n=0 N-1 xn e-i 2π k n / N
Evaluating this formula directly for N samples requires O(N2) arithmetic operations, which is too slow for low-power devices and embedded platforms. The FFT reduces this cost to O(N log N) by recursively dividing the signal into even and odd halves, a method originally developed by Cooley and Tukey.
Because the FFT assumes the input buffer represents one period of an infinitely repeating signal, any mismatch between the start and end of the audio buffer introduces a sharp step discontinuity. In the frequency domain, this artificial discontinuity smears energy across all frequency bins — a problem known as spectral leakage.
To prevent this, ShoggothOx applies a Hann window function to the audio buffer before running the FFT. The window smoothly tapers the ends of the PCM sample array to zero, eliminating the boundary step:
w(n) = 0.5 × (1 - cos(2π n / (N - 1)))
ShoggothOx is designed to run efficiently on low-power targets, such as embedded STM32 microcontrollers. Because floating-point math can be expensive on these platforms, our FFT implementation uses fixed-point Q14 arithmetic. Twiddle factors (sine and cosine values) are precomputed and scaled by 214 (16384).
Below is the core implementation of the radix-2 FFT in ShoggothOx:
/// In-place radix-2 DIT FFT on 1024 complex samples.
/// Uses fixed-point Q14 twiddle factors.
#[allow(clippy::cast_possible_truncation)]
pub fn fft1024(re: &mut [i16; 1024], im: &mut [i16; 1024], tw: &TwiddleTable) {
const N: usize = 1024;
const LOG2N: usize = 10;
for ii in 0..N {
let jj = bit_reverse_index(ii, LOG2N);
if ii < jj {
re.swap(ii, jj);
im.swap(ii, jj);
}
}
let mut half = 1usize;
let mut twiddle_step = N / 2;
while half < N {
let full = half * 2;
for kk in (0..N).step_by(full) {
for jj in 0..half {
let tw_idx = jj * twiddle_step;
let wr = i32::from(tw.cos[tw_idx]);
let wi = i32::from(tw.sin[tw_idx]);
let uu_re = i32::from(re[kk + jj]);
let uu_im = i32::from(im[kk + jj]);
let vv_re =
(i32::from(re[kk + jj + half]) * wr - i32::from(im[kk + jj + half]) * wi) >> 14;
let vv_im =
(i32::from(re[kk + jj + half]) * wi + i32::from(im[kk + jj + half]) * wr) >> 14;
re[kk + jj] = (uu_re + vv_re) as i16;
im[kk + jj] = (uu_im + vv_im) as i16;
re[kk + jj + half] = (uu_re - vv_re) as i16;
im[kk + jj + half] = (uu_im - vv_im) as i16;
}
}
half = full;
twiddle_step /= 2;
}
}
Once the FFT is complete, we calculate the amplitude of the frequency bins by computing the magnitude of the complex result values:
P(k) = re[k]2 + im[k]2
These raw power values are grouped into logical frequency bands (Bass, Mids, and Treble) and smoothed using an exponential decay filter. The resulting smoothed bands determine visual changes in real time: bass frequencies control general zoom scale and flame intensity, while treble frequencies trigger particle bursts.