#![allow(dead_code)]
use core::f32::consts::FRAC_1_SQRT_2;
use alloc::borrow::Cow;
use alloc::sync::Arc;
use alloc::vec;
use alloc::vec::Vec;
use super::fft_twiddles_48000_960::FFT_TWIDDLES_48000_960;
use super::math::mul_add_f32;
use super::mini_kfft::KissFftCpx;
const MAXFACTORS: usize = 32;
#[allow(clippy::approx_constant)]
const PI_F64: f64 = 3.14159265358979323846264338327;
#[cfg(test)]
mod fft_stage_trace {
extern crate std;
use std::env;
use std::format;
use std::string::String;
use std::sync::OnceLock;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::vec::Vec;
use super::KissFftCpx;
pub(crate) struct TraceConfig {
bins: Vec<usize>,
all_bins: bool,
frame_filter: Option<usize>,
manual: bool,
bfly_stage: Option<usize>,
bfly_index: Option<usize>,
bfly_hex: bool,
twiddle_dump: bool,
bitrev_src: bool,
}
static TRACE_CONFIG: OnceLock<Option<TraceConfig>> = OnceLock::new();
static TRACE_FRAME_INDEX: AtomicUsize = AtomicUsize::new(0);
static CURRENT_FRAME: AtomicUsize = AtomicUsize::new(usize::MAX);
static OVERRIDE_FRAME: AtomicUsize = AtomicUsize::new(usize::MAX);
static OVERRIDE_PENDING: AtomicBool = AtomicBool::new(false);
static BFLY_ENABLED: AtomicBool = AtomicBool::new(false);
static BFLY_INDEX: AtomicUsize = AtomicUsize::new(0);
static BFLY_STAGE: AtomicUsize = AtomicUsize::new(usize::MAX);
static BFLY_HEX: AtomicBool = AtomicBool::new(false);
static BFLY_DETAIL_INDEX: AtomicUsize = AtomicUsize::new(4);
static TWIDDLE_DUMPED: AtomicBool = AtomicBool::new(false);
pub(crate) fn set_frame_override(frame_idx: usize) {
OVERRIDE_FRAME.store(frame_idx, Ordering::Relaxed);
OVERRIDE_PENDING.store(true, Ordering::Relaxed);
}
pub(crate) fn begin_call() {
let Some(cfg) = config() else {
return;
};
if OVERRIDE_PENDING.swap(false, Ordering::Relaxed) {
let frame = OVERRIDE_FRAME.load(Ordering::Relaxed);
CURRENT_FRAME.store(frame, Ordering::Relaxed);
return;
}
if cfg.manual {
CURRENT_FRAME.store(usize::MAX, Ordering::Relaxed);
} else {
let frame = TRACE_FRAME_INDEX.fetch_add(1, Ordering::Relaxed);
CURRENT_FRAME.store(frame, Ordering::Relaxed);
}
}
pub(crate) fn end_call() {
CURRENT_FRAME.store(usize::MAX, Ordering::Relaxed);
}
fn current_frame() -> Option<usize> {
let value = CURRENT_FRAME.load(Ordering::Relaxed);
if value == usize::MAX {
None
} else {
Some(value)
}
}
pub(crate) fn config() -> Option<&'static TraceConfig> {
TRACE_CONFIG
.get_or_init(|| {
let enabled = env::var_os("ANALYSIS_TRACE_STAGE").is_some()
|| env::var_os("KISS_FFT_TRACE_STAGE").is_some()
|| env::var_os("ANALYSIS_TRACE_BFLY_STAGE").is_some()
|| env::var_os("KISS_FFT_TRACE_BFLY_STAGE").is_some()
|| env::var_os("ANALYSIS_TRACE_BITREV_SRC").is_some()
|| env::var_os("KISS_FFT_TRACE_BITREV_SRC").is_some();
let twiddle_dump = env::var_os("ANALYSIS_TRACE_TWIDDLES").is_some()
|| env::var_os("KISS_FFT_TRACE_TWIDDLES").is_some();
if !enabled && !twiddle_dump {
return None;
}
let bins = match env::var("ANALYSIS_TRACE_BINS") {
Ok(value) => parse_bins(&value),
Err(_) => default_bins(),
};
let frame_filter = env::var("ANALYSIS_TRACE_FRAME")
.ok()
.and_then(|value| value.parse::<usize>().ok());
let bfly_stage = env::var("ANALYSIS_TRACE_BFLY_STAGE")
.or_else(|_| env::var("KISS_FFT_TRACE_BFLY_STAGE"))
.ok()
.and_then(|value| value.parse::<usize>().ok());
let bfly_index = env::var("ANALYSIS_TRACE_BFLY_INDEX")
.or_else(|_| env::var("KISS_FFT_TRACE_BFLY_INDEX"))
.ok()
.and_then(|value| value.parse::<usize>().ok());
let bfly_hex = env::var_os("ANALYSIS_TRACE_BFLY_HEX").is_some()
|| env::var_os("KISS_FFT_TRACE_BFLY_HEX").is_some();
let manual = env::var_os("ANALYSIS_TRACE_STAGE_MANUAL").is_some()
|| env::var_os("KISS_FFT_TRACE_MANUAL").is_some();
let bitrev_src = env::var_os("ANALYSIS_TRACE_BITREV_SRC").is_some()
|| env::var_os("KISS_FFT_TRACE_BITREV_SRC").is_some();
Some(TraceConfig {
bins: bins.bins,
all_bins: bins.all_bins,
frame_filter,
manual,
bfly_stage,
bfly_index,
bfly_hex,
twiddle_dump,
bitrev_src,
})
})
.as_ref()
}
pub(crate) fn dump_bitrev_source(fin: &[KissFftCpx], bitrev: &[usize], scale: f32) {
let Some(frame_idx) = current_frame() else {
return;
};
let Some(cfg) = config() else {
return;
};
if !cfg.bitrev_src || !should_trace_frame(cfg, frame_idx) {
return;
}
for (src_idx, &dest) in bitrev.iter().enumerate() {
if !should_trace_bin(cfg, dest) {
continue;
}
let src = fin[src_idx];
let scaled = KissFftCpx::new(src.r * scale, src.i * scale);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].src={src_idx}"
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].input.r={}",
format_value(src.r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].input.i={}",
format_value(src.i as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].input_bits.r=0x{:08x}",
src.r.to_bits()
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].input_bits.i=0x{:08x}",
src.i.to_bits()
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].scaled.r={}",
format_value(scaled.r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].scaled.i={}",
format_value(scaled.i as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].scaled_bits.r=0x{:08x}",
scaled.r.to_bits()
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev_src.bin[{dest}].scaled_bits.i=0x{:08x}",
scaled.i.to_bits()
);
}
}
pub(crate) fn dump_bitrev(buf: &[KissFftCpx]) {
let Some(frame_idx) = current_frame() else {
return;
};
let Some(cfg) = config() else {
return;
};
if !should_trace_frame(cfg, frame_idx) {
return;
}
for bin in 0..buf.len() {
if !should_trace_bin(cfg, bin) {
continue;
}
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev.bin[{bin}].r={}",
format_value(buf[bin].r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].bitrev.bin[{bin}].i={}",
format_value(buf[bin].i as f64)
);
}
}
pub(crate) fn dump_twiddles(nfft: usize, twiddles: &[KissFftCpx]) {
let Some(cfg) = config() else {
return;
};
if !cfg.twiddle_dump {
return;
}
if TWIDDLE_DUMPED.swap(true, Ordering::Relaxed) {
return;
}
let count = nfft.min(twiddles.len());
crate::test_trace::trace_println!("fft_twiddles.nfft={count}");
for (idx, value) in twiddles.iter().take(count).enumerate() {
let r = value.r.to_bits();
let i = value.i.to_bits();
crate::test_trace::trace_println!("fft_twiddles[{idx}].bits.r=0x{r:08x}");
crate::test_trace::trace_println!("fft_twiddles[{idx}].bits.i=0x{i:08x}");
}
}
pub(crate) fn dump_twiddle_phase(index: usize, phase: f64) {
let Some(cfg) = config() else {
return;
};
if !cfg.twiddle_dump || (index != 120 && index != 240) {
return;
}
let bits = phase.to_bits();
crate::test_trace::trace_println!("fft_twiddle_phase[{index}].bits=0x{bits:016x}");
}
pub(crate) fn dump_stage(stage: usize, buf: &[KissFftCpx]) {
let Some(frame_idx) = current_frame() else {
return;
};
let Some(cfg) = config() else {
return;
};
if !should_trace_frame(cfg, frame_idx) {
return;
}
for bin in 0..buf.len() {
if !should_trace_bin(cfg, bin) {
continue;
}
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bin[{bin}].r={}",
format_value(buf[bin].r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bin[{bin}].i={}",
format_value(buf[bin].i as f64)
);
}
}
pub(crate) fn begin_bfly_stage(stage: usize) {
let Some(cfg) = config() else {
return;
};
let Some(target) = cfg.bfly_stage else {
return;
};
let Some(frame_idx) = current_frame() else {
return;
};
if target != stage || !should_trace_frame(cfg, frame_idx) {
return;
}
BFLY_STAGE.store(stage, Ordering::Relaxed);
BFLY_INDEX.store(0, Ordering::Relaxed);
BFLY_ENABLED.store(true, Ordering::Relaxed);
BFLY_HEX.store(cfg.bfly_hex, Ordering::Relaxed);
BFLY_DETAIL_INDEX.store(cfg.bfly_index.unwrap_or(4), Ordering::Relaxed);
}
pub(crate) fn end_bfly_stage(stage: usize) {
if BFLY_ENABLED.load(Ordering::Relaxed) && BFLY_STAGE.load(Ordering::Relaxed) == stage {
BFLY_ENABLED.store(false, Ordering::Relaxed);
BFLY_HEX.store(false, Ordering::Relaxed);
BFLY_DETAIL_INDEX.store(4, Ordering::Relaxed);
}
}
pub(crate) fn bfly_active() -> bool {
BFLY_ENABLED.load(Ordering::Relaxed)
}
pub(crate) fn current_bfly_index() -> Option<usize> {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return None;
}
Some(BFLY_INDEX.load(Ordering::Relaxed))
}
pub(crate) fn bfly_detail_index() -> usize {
BFLY_DETAIL_INDEX.load(Ordering::Relaxed)
}
pub(crate) fn dump_bfly_value(bfly_idx: usize, label: &str, value: KissFftCpx) {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}.r={}",
format_value(value.r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}.i={}",
format_value(value.i as f64)
);
}
pub(crate) fn dump_bfly_bits(bfly_idx: usize, label: &str, value: KissFftCpx) {
if !BFLY_ENABLED.load(Ordering::Relaxed) || !BFLY_HEX.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}.bits.r=0x{bits:08x}",
bits = value.r.to_bits()
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}.bits.i=0x{bits:08x}",
bits = value.i.to_bits()
);
}
pub(crate) fn dump_bfly_scalar(bfly_idx: usize, label: &str, value: f32) {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}={}",
format_value(value as f64)
);
}
pub(crate) fn dump_bfly_scalar_bits(bfly_idx: usize, label: &str, value: f32) {
if !BFLY_ENABLED.load(Ordering::Relaxed) || !BFLY_HEX.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}_bits=0x{bits:08x}",
bits = value.to_bits()
);
}
pub(crate) fn dump_bfly_indices(bfly_idx: usize, indices: [usize; 5]) {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
for (slot, idx) in indices.into_iter().enumerate() {
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].idx[{slot}]={idx}"
);
}
}
pub(crate) fn dump_bfly_twiddle_index(bfly_idx: usize, label: &str, index: usize) {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].{label}={index}"
);
}
pub(crate) fn dump_bfly(before: &[KissFftCpx], after: &[KissFftCpx]) {
if !BFLY_ENABLED.load(Ordering::Relaxed) {
return;
}
let Some(frame_idx) = current_frame() else {
return;
};
let stage = BFLY_STAGE.load(Ordering::Relaxed);
let bfly_idx = BFLY_INDEX.fetch_add(1, Ordering::Relaxed);
for (idx, value) in before.iter().enumerate() {
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].in[{idx}].r={}",
format_value(value.r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].in[{idx}].i={}",
format_value(value.i as f64)
);
let out = after[idx];
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].out[{idx}].r={}",
format_value(out.r as f64)
);
crate::test_trace::trace_println!(
"fft_stage[{frame_idx}].stage[{stage}].bfly[{bfly_idx}].out[{idx}].i={}",
format_value(out.i as f64)
);
}
}
fn format_value(value: f64) -> String {
let raw = format!("{:.9e}", value);
let Some(pos) = raw.find('e') else {
return raw;
};
let (mant, exp) = raw.split_at(pos);
let mut digits = String::from(&exp[1..]);
let mut sign = '+';
if let Some(rest) = digits.strip_prefix('-') {
sign = '-';
digits = String::from(rest);
} else if let Some(rest) = digits.strip_prefix('+') {
sign = '+';
digits = String::from(rest);
}
if digits.len() == 1 {
digits.insert(0, '0');
}
format!("{mant}e{sign}{digits}")
}
fn should_trace_bin(cfg: &TraceConfig, bin: usize) -> bool {
if cfg.all_bins {
return true;
}
cfg.bins.iter().any(|&value| value == bin)
}
fn should_trace_frame(cfg: &TraceConfig, frame_idx: usize) -> bool {
cfg.frame_filter.map_or(true, |value| value == frame_idx)
}
struct BinConfig {
bins: Vec<usize>,
all_bins: bool,
}
fn default_bins() -> BinConfig {
let mut bins = Vec::new();
bins.push(1);
bins.push(61);
BinConfig {
bins,
all_bins: false,
}
}
fn parse_bins(value: &str) -> BinConfig {
let trimmed = value.trim();
if trimmed.is_empty() {
return default_bins();
}
if trimmed.eq_ignore_ascii_case("all") {
return BinConfig {
bins: Vec::new(),
all_bins: true,
};
}
let mut bins = Vec::new();
for token in trimmed.split(|c| c == ',' || c == ' ' || c == '\t') {
if token.is_empty() {
continue;
}
if let Ok(bin) = token.parse::<usize>() {
if bin < 480 {
bins.push(bin);
}
}
}
if bins.is_empty() {
default_bins()
} else {
BinConfig {
bins,
all_bins: false,
}
}
}
}
#[cfg(test)]
pub(crate) fn set_fft_trace_frame(frame_idx: usize) {
fft_stage_trace::set_frame_override(frame_idx);
}
#[inline]
fn c_add(a: KissFftCpx, b: KissFftCpx) -> KissFftCpx {
KissFftCpx::new(a.r + b.r, a.i + b.i)
}
#[inline]
fn c_sub(a: KissFftCpx, b: KissFftCpx) -> KissFftCpx {
KissFftCpx::new(a.r - b.r, a.i - b.i)
}
#[inline]
fn c_mul(a: KissFftCpx, b: KissFftCpx) -> KissFftCpx {
let real = mul_add_f32(a.r, b.r, -(a.i * b.i));
let imag = mul_add_f32(a.r, b.i, a.i * b.r);
KissFftCpx::new(real, imag)
}
#[inline]
fn c_mul_by_scalar(a: KissFftCpx, s: f32) -> KissFftCpx {
KissFftCpx::new(a.r * s, a.i * s)
}
#[inline]
fn half_of(x: f32) -> f32 {
0.5 * x
}
#[inline]
fn fft_scale(nfft: usize) -> f32 {
match nfft {
60 => 0.016_666_667,
120 => 0.008_333_333,
240 => 0.004_166_667,
480 => 0.002_083_333,
_ => 1.0 / nfft as f32,
}
}
#[derive(Clone, Debug)]
enum TwiddleStorage {
Static(&'static [KissFftCpx]),
Shared(Arc<[KissFftCpx]>),
}
impl TwiddleStorage {
#[inline]
fn as_slice(&self) -> &[KissFftCpx] {
match self {
Self::Static(values) => values,
Self::Shared(values) => values.as_ref(),
}
}
#[inline]
const fn from_static(values: &'static [KissFftCpx]) -> Self {
Self::Static(values)
}
}
#[derive(Clone, Debug)]
pub struct KissFftState {
nfft: usize,
scale: f32,
shift: Option<usize>,
factors: Cow<'static, [usize]>,
bitrev: Cow<'static, [usize]>,
twiddles: TwiddleStorage,
}
impl KissFftState {
#[must_use]
pub(crate) const fn from_static(
nfft: usize,
scale: f32,
shift: Option<usize>,
factors: &'static [usize],
bitrev: &'static [usize],
twiddles: &'static [KissFftCpx],
) -> Self {
Self {
nfft,
scale,
shift,
factors: Cow::Borrowed(factors),
bitrev: Cow::Borrowed(bitrev),
twiddles: TwiddleStorage::from_static(twiddles),
}
}
#[must_use]
pub fn new(nfft: usize) -> Self {
Self::with_base(nfft, None)
}
#[must_use]
pub fn with_base(nfft: usize, base: Option<&KissFftState>) -> Self {
assert!(nfft > 0, "FFT size must be non-zero");
let (twiddles, shift) = if let Some(base_state) = base {
let mut shift = 0usize;
while (nfft << shift) < base_state.nfft {
shift += 1;
}
assert_eq!(
nfft << shift,
base_state.nfft,
"base FFT length must be a power-of-two multiple of the requested length"
);
(base_state.twiddles.clone(), Some(shift))
} else {
let twiddles = if nfft == 480 {
TwiddleStorage::Static(&FFT_TWIDDLES_48000_960)
} else {
TwiddleStorage::Shared(Arc::<[KissFftCpx]>::from(compute_twiddles(nfft)))
};
(twiddles, None)
};
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::dump_twiddles(nfft, twiddles.as_slice());
}
let factors = kf_factor(nfft);
assert!(
factors.len() <= 2 * MAXFACTORS,
"factor buffer overflow: {} entries",
factors.len()
);
let mut bitrev = vec![0usize; nfft];
compute_bitrev_table(0, &mut bitrev, 1, 1, &factors);
Self {
nfft,
scale: fft_scale(nfft),
shift,
factors: Cow::Owned(factors),
bitrev: Cow::Owned(bitrev),
twiddles,
}
}
#[inline]
#[must_use]
pub fn nfft(&self) -> usize {
self.nfft
}
#[inline]
#[must_use]
pub fn scale(&self) -> f32 {
self.scale
}
#[inline]
#[must_use]
pub fn bitrev(&self) -> &[usize] {
self.bitrev.as_ref()
}
pub fn fft(&self, fin: &[KissFftCpx], fout: &mut [KissFftCpx]) {
assert_eq!(fin.len(), self.nfft, "input length must match FFT size");
assert_eq!(fout.len(), self.nfft, "output length must match FFT size");
assert!(
!core::ptr::eq(fin.as_ptr(), fout.as_mut_ptr()),
"in-place FFT not supported"
);
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::begin_call();
}
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::dump_bitrev_source(fin, self.bitrev.as_ref(), self.scale);
}
for (src, &rev) in fin.iter().zip(self.bitrev.as_ref().iter()) {
fout[rev] = KissFftCpx::new(src.r * self.scale, src.i * self.scale);
}
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::dump_bitrev(fout);
}
self.fft_impl(fout);
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::end_call();
}
}
pub fn ifft(&self, fin: &[KissFftCpx], fout: &mut [KissFftCpx]) {
assert_eq!(fin.len(), self.nfft, "input length must match FFT size");
assert_eq!(fout.len(), self.nfft, "output length must match FFT size");
assert!(
!core::ptr::eq(fin.as_ptr(), fout.as_mut_ptr()),
"in-place FFT not supported"
);
for (src, &rev) in fin.iter().zip(self.bitrev.as_ref().iter()) {
fout[rev] = KissFftCpx::new(src.r, -src.i);
}
self.fft_impl(fout);
for val in fout.iter_mut() {
val.i = -val.i;
}
}
fn fft_impl(&self, fout: &mut [KissFftCpx]) {
let mut fstride = [0usize; MAXFACTORS + 1];
fstride[0] = 1;
let mut stages = 0usize;
let factors = self.factors.as_ref();
loop {
let p = factors[2 * stages];
let m = factors[2 * stages + 1];
fstride[stages + 1] = fstride[stages] * p;
stages += 1;
if m == 1 {
break;
}
}
let mut m = factors[2 * stages - 1];
let shift = self.shift.unwrap_or(0);
#[cfg(test)]
let total_stages = stages;
for stage in (0..stages).rev() {
let p = factors[2 * stage];
let m2 = if stage != 0 {
factors[2 * stage - 1]
} else {
1
};
#[cfg(test)]
let applied_stage = total_stages - 1 - stage;
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::begin_bfly_stage(applied_stage);
}
match p {
2 => kf_bfly2(fout, m, fstride[stage]),
3 => kf_bfly3(fout, fstride[stage] << shift, self, m, fstride[stage], m2),
4 => kf_bfly4(fout, fstride[stage] << shift, self, m, fstride[stage], m2),
5 => kf_bfly5(fout, fstride[stage] << shift, self, m, fstride[stage], m2),
_ => panic!("unsupported radix {p} in factorisation"),
}
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::end_bfly_stage(applied_stage);
fft_stage_trace::dump_stage(applied_stage, fout);
}
m = m2;
}
}
}
#[must_use]
fn twiddle_phase(index: usize, nfft: usize) -> f64 {
(-2.0 * PI_F64 / nfft as f64) * index as f64
}
fn compute_twiddles(nfft: usize) -> Vec<KissFftCpx> {
(0..nfft)
.map(|i| {
let phase = twiddle_phase(i, nfft);
#[cfg(test)]
if fft_stage_trace::config().is_some() {
fft_stage_trace::dump_twiddle_phase(i, phase);
}
let (re, im) = twiddle_math::cos_sin(phase);
KissFftCpx::new(re as f32, im as f32)
})
.collect()
}
mod twiddle_math {
use libm::{cos, sin};
pub(super) fn cos_sin(phase: f64) -> (f64, f64) {
(cos(phase), sin(phase))
}
}
fn compute_bitrev_table(
fout: usize,
table: &mut [usize],
fstride: usize,
in_stride: usize,
factors: &[usize],
) {
let p = factors[0];
let m = factors[1];
if m == 1 {
for j in 0..p {
table[j * fstride * in_stride] = fout + j;
}
} else {
let mut fout_base = fout;
let mut table_offset = 0usize;
for _ in 0..p {
compute_bitrev_table(
fout_base,
&mut table[table_offset..],
fstride * p,
in_stride,
&factors[2..],
);
table_offset += fstride * in_stride;
fout_base += m;
}
}
}
fn kf_factor(mut n: usize) -> Vec<usize> {
let mut factors = [0usize; 2 * MAXFACTORS];
let mut p = 4usize;
let mut stages = 0usize;
let nbak = n;
loop {
while !n.is_multiple_of(p) {
p = match p {
4 => 2,
2 => 3,
_ => p + 2,
};
if p > 32000 || p.saturating_mul(p) > n {
p = n;
}
}
n /= p;
assert!(p <= 5, "unsupported FFT radix {p}");
factors[2 * stages] = p;
if p == 2 && stages > 1 {
factors[2 * stages] = 4;
factors[2] = 2;
}
stages += 1;
if n == 1 {
break;
}
}
let mut n = nbak;
for i in 0..(stages / 2) {
factors.swap(2 * i, 2 * (stages - i - 1));
}
let mut out = Vec::with_capacity(2 * stages);
for i in 0..stages {
n /= factors[2 * i];
factors[2 * i + 1] = n;
out.push(factors[2 * i]);
out.push(factors[2 * i + 1]);
}
out
}
fn kf_bfly2(fout: &mut [KissFftCpx], m: usize, n: usize) {
#[cfg(test)]
let trace_enabled = fft_stage_trace::bfly_active();
if m == 1 {
for i in 0..n {
let base = 2 * i;
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 2];
#[cfg(test)]
if trace_enabled {
before[0] = fout[base];
before[1] = fout[base + 1];
}
let t = fout[base + 1];
fout[base + 1] = c_sub(fout[base], t);
fout[base] = c_add(fout[base], t);
#[cfg(test)]
if trace_enabled {
let after = [fout[base], fout[base + 1]];
fft_stage_trace::dump_bfly(&before, &after);
}
}
} else {
debug_assert_eq!(m, 4);
let tw = FRAC_1_SQRT_2;
for i in 0..n {
let base = i * 2 * m;
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 8];
#[cfg(test)]
if trace_enabled {
for k in 0..8 {
before[k] = fout[base + k];
}
}
let t0 = fout[base + 4];
fout[base + 4] = c_sub(fout[base], t0);
fout[base] = c_add(fout[base], t0);
let mut t1 = KissFftCpx::new(
(fout[base + 5].r + fout[base + 5].i) * tw,
(fout[base + 5].i - fout[base + 5].r) * tw,
);
fout[base + 5] = c_sub(fout[base + 1], t1);
fout[base + 1] = c_add(fout[base + 1], t1);
let t2 = KissFftCpx::new(fout[base + 6].i, -fout[base + 6].r);
fout[base + 6] = c_sub(fout[base + 2], t2);
fout[base + 2] = c_add(fout[base + 2], t2);
t1 = KissFftCpx::new(
(fout[base + 7].i - fout[base + 7].r) * tw,
-(fout[base + 7].i + fout[base + 7].r) * tw,
);
fout[base + 7] = c_sub(fout[base + 3], t1);
fout[base + 3] = c_add(fout[base + 3], t1);
#[cfg(test)]
if trace_enabled {
let mut after = [KissFftCpx::new(0.0, 0.0); 8];
for k in 0..8 {
after[k] = fout[base + k];
}
fft_stage_trace::dump_bfly(&before, &after);
}
}
}
}
fn kf_bfly3(
fout: &mut [KissFftCpx],
fstride: usize,
st: &KissFftState,
m: usize,
n: usize,
mm: usize,
) {
#[cfg(test)]
let trace_enabled = fft_stage_trace::bfly_active();
let m2 = 2 * m;
let twiddles = st.twiddles.as_slice();
let epi3 = twiddles[fstride * m];
for i in 0..n {
let base = i * mm;
let mut tw1 = 0usize;
let mut tw2 = 0usize;
for k in 0..m {
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 3];
#[cfg(test)]
if trace_enabled {
before[0] = fout[base + k];
before[1] = fout[base + m + k];
before[2] = fout[base + m2 + k];
}
let scratch1 = c_mul(fout[base + m + k], twiddles[tw1]);
let scratch2 = c_mul(fout[base + m2 + k], twiddles[tw2]);
let scratch3 = c_add(scratch1, scratch2);
let scratch0 = c_sub(scratch1, scratch2);
tw1 += fstride;
tw2 += fstride * 2;
let mut fout_m = KissFftCpx::new(
fout[base + k].r - half_of(scratch3.r),
fout[base + k].i - half_of(scratch3.i),
);
let scratch0 = c_mul_by_scalar(scratch0, epi3.i);
let fout0 = c_add(fout[base + k], scratch3);
fout[base + m2 + k] = KissFftCpx::new(fout_m.r + scratch0.i, fout_m.i - scratch0.r);
fout_m = KissFftCpx::new(fout_m.r - scratch0.i, fout_m.i + scratch0.r);
fout[base + k] = fout0;
fout[base + m + k] = fout_m;
#[cfg(test)]
if trace_enabled {
let after = [fout[base + k], fout[base + m + k], fout[base + m2 + k]];
fft_stage_trace::dump_bfly(&before, &after);
}
}
}
}
fn kf_bfly4(
fout: &mut [KissFftCpx],
fstride: usize,
st: &KissFftState,
m: usize,
n: usize,
mm: usize,
) {
#[cfg(test)]
let trace_enabled = fft_stage_trace::bfly_active();
let twiddles = st.twiddles.as_slice();
if m == 1 {
for i in 0..n {
let base = i * mm;
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 4];
#[cfg(test)]
if trace_enabled {
for k in 0..4 {
before[k] = fout[base + k];
}
}
#[cfg(test)]
let bfly_idx = if trace_enabled {
fft_stage_trace::current_bfly_index()
} else {
None
};
let scratch0 = c_sub(fout[base], fout[base + 2]);
let scratch1 = c_add(fout[base + 1], fout[base + 3]);
let scratch1b = c_sub(fout[base + 1], fout[base + 3]);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch0", scratch0);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch1", scratch1);
}
let mut fout0 = c_add(fout[base], fout[base + 2]);
fout[base + 2] = c_sub(fout0, scratch1);
fout0 = c_add(fout0, scratch1);
fout[base + 1] = KissFftCpx::new(scratch0.r + scratch1b.i, scratch0.i - scratch1b.r);
fout[base + 3] = KissFftCpx::new(scratch0.r - scratch1b.i, scratch0.i + scratch1b.r);
fout[base] = fout0;
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch1b", scratch1b);
}
#[cfg(test)]
if trace_enabled {
let mut after = [KissFftCpx::new(0.0, 0.0); 4];
for k in 0..4 {
after[k] = fout[base + k];
}
fft_stage_trace::dump_bfly(&before, &after);
}
}
} else {
let m2 = 2 * m;
let m3 = 3 * m;
for i in 0..n {
let base = i * mm;
let mut tw1 = 0usize;
let mut tw2 = 0usize;
let mut tw3 = 0usize;
for j in 0..m {
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 4];
#[cfg(test)]
if trace_enabled {
before[0] = fout[base + j];
before[1] = fout[base + j + m];
before[2] = fout[base + j + m2];
before[3] = fout[base + j + m3];
}
#[cfg(test)]
let bfly_idx = if trace_enabled {
fft_stage_trace::current_bfly_index()
} else {
None
};
let scratch0 = c_mul(fout[base + j + m], twiddles[tw1]);
let scratch1 = c_mul(fout[base + j + m2], twiddles[tw2]);
let scratch2 = c_mul(fout[base + j + m3], twiddles[tw3]);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "mul_in0", before[1]);
fft_stage_trace::dump_bfly_value(bfly_idx, "mul_in1", before[2]);
fft_stage_trace::dump_bfly_value(bfly_idx, "mul_in2", before[3]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul_in0", before[1]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul_in1", before[2]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul_in2", before[3]);
fft_stage_trace::dump_bfly_value(bfly_idx, "tw1", twiddles[tw1]);
fft_stage_trace::dump_bfly_value(bfly_idx, "tw2", twiddles[tw2]);
fft_stage_trace::dump_bfly_value(bfly_idx, "tw3", twiddles[tw3]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "tw1", twiddles[tw1]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "tw2", twiddles[tw2]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "tw3", twiddles[tw3]);
fft_stage_trace::dump_bfly_value(bfly_idx, "mul0", scratch0);
fft_stage_trace::dump_bfly_value(bfly_idx, "mul1", scratch1);
fft_stage_trace::dump_bfly_value(bfly_idx, "mul2", scratch2);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul0", scratch0);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul1", scratch1);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul2", scratch2);
}
tw1 += fstride;
tw2 += fstride * 2;
tw3 += fstride * 3;
let scratch5 = c_sub(fout[base + j], scratch1);
let mut fout0 = c_add(fout[base + j], scratch1);
let scratch3 = c_add(scratch0, scratch2);
let scratch4 = c_sub(scratch0, scratch2);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch5", scratch5);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch3", scratch3);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch4", scratch4);
}
fout[base + j + m2] = c_sub(fout0, scratch3);
fout0 = c_add(fout0, scratch3);
let fout_m = KissFftCpx::new(scratch5.r + scratch4.i, scratch5.i - scratch4.r);
let fout_m3 = KissFftCpx::new(scratch5.r - scratch4.i, scratch5.i + scratch4.r);
fout[base + j] = fout0;
fout[base + j + m] = fout_m;
fout[base + j + m3] = fout_m3;
#[cfg(test)]
if trace_enabled {
let after = [
fout[base + j],
fout[base + j + m],
fout[base + j + m2],
fout[base + j + m3],
];
fft_stage_trace::dump_bfly(&before, &after);
}
}
}
}
}
fn kf_bfly5(
fout: &mut [KissFftCpx],
fstride: usize,
st: &KissFftState,
m: usize,
n: usize,
mm: usize,
) {
#[cfg(test)]
let trace_enabled = fft_stage_trace::bfly_active();
let twiddles = st.twiddles.as_slice();
let ya = twiddles[fstride * m];
let yb = twiddles[fstride * 2 * m];
for i in 0..n {
let base = i * mm;
for u in 0..m {
#[cfg(test)]
let mut before = [KissFftCpx::new(0.0, 0.0); 5];
#[cfg(test)]
if trace_enabled {
before[0] = fout[base + u];
before[1] = fout[base + m + u];
before[2] = fout[base + 2 * m + u];
before[3] = fout[base + 3 * m + u];
before[4] = fout[base + 4 * m + u];
}
#[cfg(test)]
let bfly_idx = if trace_enabled {
fft_stage_trace::current_bfly_index()
} else {
None
};
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_indices(
bfly_idx,
[
base + u,
base + m + u,
base + 2 * m + u,
base + 3 * m + u,
base + 4 * m + u,
],
);
if bfly_idx == 0 {
fft_stage_trace::dump_bfly_bits(bfly_idx, "ya", ya);
fft_stage_trace::dump_bfly_bits(bfly_idx, "yb", yb);
}
}
let scratch0 = fout[base + u];
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch0", scratch0);
}
let scratch1 = c_mul(fout[base + m + u], twiddles[u * fstride]);
let scratch2 = c_mul(fout[base + 2 * m + u], twiddles[2 * u * fstride]);
let scratch3 = c_mul(fout[base + 3 * m + u], twiddles[3 * u * fstride]);
let scratch4 = c_mul(fout[base + 4 * m + u], twiddles[4 * u * fstride]);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
let tw4_idx = 4 * u * fstride;
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch1", scratch1);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch2", scratch2);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch3", scratch3);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch4", scratch4);
fft_stage_trace::dump_bfly_bits(bfly_idx, "mul_in4", before[4]);
fft_stage_trace::dump_bfly_twiddle_index(bfly_idx, "tw4.idx", tw4_idx);
fft_stage_trace::dump_bfly_bits(bfly_idx, "tw4", twiddles[tw4_idx]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "scratch4", scratch4);
}
let scratch7 = c_add(scratch1, scratch4);
let scratch10 = c_sub(scratch1, scratch4);
let scratch8 = c_add(scratch2, scratch3);
let scratch9 = c_sub(scratch2, scratch3);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch7", scratch7);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch10", scratch10);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch8", scratch8);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch9", scratch9);
if bfly_idx == fft_stage_trace::bfly_detail_index() {
let s6a = scratch10.i * ya.i;
let s6b = scratch9.i * yb.i;
let s6sum = s6a + s6b;
let s11ar = scratch7.r * yb.r;
let s11br = scratch8.r * ya.r;
let s11sum_r = s11ar + s11br;
let s11ai = scratch7.i * yb.r;
let s11bi = scratch8.i * ya.r;
let s11sum_i = s11ai + s11bi;
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch6_term0", s6a);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch6_term0", s6a);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch6_term1", s6b);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch6_term1", s6b);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch6_sum", s6sum);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch6_sum", s6sum);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_term0_r", s11ar);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_term0_r", s11ar);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_term1_r", s11br);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_term1_r", s11br);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_sum_r", s11sum_r);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_sum_r", s11sum_r);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_term0_i", s11ai);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_term0_i", s11ai);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_term1_i", s11bi);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_term1_i", s11bi);
fft_stage_trace::dump_bfly_scalar(bfly_idx, "scratch11_sum_i", s11sum_i);
fft_stage_trace::dump_bfly_scalar_bits(bfly_idx, "scratch11_sum_i", s11sum_i);
}
}
let fout0 = c_add(scratch0, c_add(scratch7, scratch8));
let scratch5_r = mul_add_f32(scratch7.r, ya.r, scratch8.r * yb.r);
let scratch5_i = mul_add_f32(scratch7.i, ya.r, scratch8.i * yb.r);
let scratch5 = KissFftCpx::new(scratch0.r + scratch5_r, scratch0.i + scratch5_i);
let scratch6 = KissFftCpx::new(
mul_add_f32(scratch10.i, ya.i, scratch9.i * yb.i),
-mul_add_f32(scratch10.r, ya.i, scratch9.r * yb.i),
);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch5", scratch5);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch6", scratch6);
fft_stage_trace::dump_bfly_bits(bfly_idx, "scratch6", scratch6);
}
fout[base + m + u] = c_sub(scratch5, scratch6);
fout[base + 4 * m + u] = c_add(scratch5, scratch6);
let scratch11_r = mul_add_f32(scratch7.r, yb.r, scratch8.r * ya.r);
let scratch11_i = mul_add_f32(scratch7.i, yb.r, scratch8.i * ya.r);
let scratch11 = KissFftCpx::new(scratch0.r + scratch11_r, scratch0.i + scratch11_i);
let scratch12 = KissFftCpx::new(
mul_add_f32(scratch9.i, ya.i, -scratch10.i * yb.i),
mul_add_f32(scratch10.r, yb.i, -scratch9.r * ya.i),
);
#[cfg(test)]
if let Some(bfly_idx) = bfly_idx {
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch11", scratch11);
fft_stage_trace::dump_bfly_value(bfly_idx, "scratch12", scratch12);
fft_stage_trace::dump_bfly_bits(bfly_idx, "scratch11", scratch11);
fft_stage_trace::dump_bfly_bits(bfly_idx, "scratch12", scratch12);
}
fout[base + 2 * m + u] = c_add(scratch11, scratch12);
fout[base + 3 * m + u] = c_sub(scratch11, scratch12);
fout[base + u] = fout0;
#[cfg(test)]
if trace_enabled {
let after = [
fout[base + u],
fout[base + m + u],
fout[base + 2 * m + u],
fout[base + 3 * m + u],
fout[base + 4 * m + u],
];
if let Some(bfly_idx) = bfly_idx {
if bfly_idx == fft_stage_trace::bfly_detail_index() {
fft_stage_trace::dump_bfly_bits(bfly_idx, "out0", after[0]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "out1", after[1]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "out2", after[2]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "out3", after[3]);
fft_stage_trace::dump_bfly_bits(bfly_idx, "out4", after[4]);
}
}
fft_stage_trace::dump_bfly(&before, &after);
}
}
}
}
#[must_use]
pub fn opus_fft_alloc(nfft: usize) -> KissFftState {
KissFftState::new(nfft)
}
#[must_use]
pub fn opus_fft_alloc_twiddles(nfft: usize, base: Option<&KissFftState>) -> KissFftState {
KissFftState::with_base(nfft, base)
}
pub fn opus_fft(state: &KissFftState, fin: &[KissFftCpx], fout: &mut [KissFftCpx]) {
state.fft(fin, fout);
}
pub fn opus_ifft(state: &KissFftState, fin: &[KissFftCpx], fout: &mut [KissFftCpx]) {
state.ifft(fin, fout);
}
#[cfg(test)]
mod tests {
use alloc::vec::Vec;
use libm::{cos, sin};
use super::*;
fn check(fin: &[KissFftCpx], fout: &[KissFftCpx], inverse: bool) -> f64 {
let nfft = fin.len();
let mut errpow = 0.0f64;
let mut sigpow = 0.0f64;
for bin in 0..nfft {
let mut ansr = 0.0f64;
let mut ansi = 0.0f64;
for (k, sample) in fin.iter().enumerate() {
let phase = -2.0 * PI_F64 * bin as f64 * k as f64 / nfft as f64;
let mut re = cos(phase);
let mut im = sin(phase);
if inverse {
im = -im;
} else {
re /= nfft as f64;
im /= nfft as f64;
}
ansr += sample.r as f64 * re - sample.i as f64 * im;
ansi += sample.r as f64 * im + sample.i as f64 * re;
}
let difr = ansr - fout[bin].r as f64;
let difi = ansi - fout[bin].i as f64;
errpow += difr * difr + difi * difi;
sigpow += ansr * ansr + ansi * ansi;
}
10.0 * (sigpow / errpow).log10()
}
fn lcg(seed: &mut u32) -> u32 {
*seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
*seed
}
fn generate_input(nfft: usize, inverse: bool, seed: &mut u32) -> Vec<KissFftCpx> {
let mut buf = Vec::with_capacity(nfft);
for _ in 0..nfft {
let r = (lcg(seed) & 0x7fff) as f32 - 16384.0;
let i = (lcg(seed) & 0x7fff) as f32 - 16384.0;
buf.push(KissFftCpx::new(r * 32768.0, i * 32768.0));
}
if inverse {
let scale = 1.0 / nfft as f32;
for v in &mut buf {
v.r *= scale;
v.i *= scale;
}
}
buf
}
fn run_case(nfft: usize, inverse: bool) {
let mut seed = 1u32;
let state = KissFftState::new(nfft);
let input = generate_input(nfft, inverse, &mut seed);
let mut output = vec![KissFftCpx::default(); nfft];
if inverse {
state.ifft(&input, &mut output);
} else {
state.fft(&input, &mut output);
}
let snr = check(&input, &output, inverse);
assert!(
snr >= 60.0,
"poor SNR {snr:.2} dB for nfft={nfft} inverse={inverse}"
);
}
#[test]
fn fft_matches_reference_across_sizes() {
let sizes = [32usize, 128, 256, 36, 50, 60, 120, 240, 480];
for &nfft in &sizes {
run_case(nfft, false);
run_case(nfft, true);
}
}
#[test]
fn twiddle_phase_matches_opus_c_order() {
let nfft = 480usize;
let cases = [
(120usize, 0xbff921fb54442d18u64),
(240usize, 0xc00921fb54442d18u64),
];
for (index, expected) in cases {
let phase = twiddle_phase(index, nfft);
assert_eq!(
phase.to_bits(),
expected,
"phase bits mismatch for index={index}"
);
}
}
}