spike(rust/fft): port compute_cross_correlation to Rust

[natashaannn]

User story

As a coding agent implementing the Rust FFT spike (tracked in #93), I want a compute_cross_correlation function in spike/audio-sync/src/lib.rs that exactly replicates the JS implementation, so that the lag computation pipeline has a correct, tested FFT core.

Background

RFC 0001 (#90) proposes rewriting the editing pipeline in Rust. To validate the agent-driven Rust dev loop before committing, the team is running a spike: port the FFT cross-correlation algorithm from scripts/sync/AudioSyncer.js to a standalone Rust binary.

This issue ports one function: computeCrossCorrelation (scripts/sync/AudioSyncer.js L145–186). It is the mathematical core of the sync algorithm — it takes two audio sample buffers and returns a correlation array whose peak encodes the time offset between them. The companion functions find_best_lag (#97) and validate_peak (#98) consume its output.

The Rust implementation must produce the same floating-point correlation values as the JS for identical input samples. It uses the rustfft crate (already in Cargo.toml from #95) — no C FFT bindings.

Acceptance criteria

Happy path

Given two &[f32] sample slices of arbitrary length
When compute_cross_correlation(samples_a, samples_b) is called
Then it returns a Vec<f64> of length next_power_of_two(len_a + len_b - 1) where each value equals IFFT(FFT(a) * conj(FFT(b)))[i] / N — matching the JS formula exactly

Given a known synthesized input (e.g. an impulse in A at sample 0 and an impulse in B at sample K)
When compute_cross_correlation is called
Then the returned correlation array has its peak at index K (or N - K for negative lag), confirming correct circular cross-correlation behaviour

Error path / edge case

Given two input slices where one is length 1 and the other is length 1
When compute_cross_correlation is called
Then it returns a valid (non-panicking) result of length 1

Out of scope

• Peak-finding logic — that is find_best_lag (spike(rust/lag): port find_best_lag to Rust #97)
• SNR validation — that is validate_peak (spike(rust/snr): port validate_peak to Rust #98)
• Reading WAV files — that is the CLI issue (spike(rust/cli): wire CLI binary and fixture round-trip test #99)

Technical context

JS source to replicate (scripts/sync/AudioSyncer.js L145–186):

computeCrossCorrelation(samplesA, samplesB) {
  const lenA = samplesA.length;
  const lenB = samplesB.length;
  const N = nextPowerOfTwo(lenA + lenB - 1);

  const fft = new FFT(N);

  const cA = fft.createComplexArray();   // interleaved [re, im, re, im, ...]
  const cB = fft.createComplexArray();
  for (let i = 0; i < lenA; i++) cA[2 * i] = samplesA[i];
  for (let i = 0; i < lenB; i++) cB[2 * i] = samplesB[i];

  const FA = fft.createComplexArray();
  const FB = fft.createComplexArray();
  fft.transform(FA, cA);
  fft.transform(FB, cB);

  // multiply FA by conjugate of FB
  const product = fft.createComplexArray();
  for (let i = 0; i < N; i++) {
    const re = FA[2*i]   * FB[2*i]   + FA[2*i+1] * FB[2*i+1];
    const im = FA[2*i+1] * FB[2*i]   - FA[2*i]   * FB[2*i+1];
    product[2*i]   = re;
    product[2*i+1] = im;
  }

  const result = fft.createComplexArray();
  fft.inverseTransform(result, product);

  const correlation = new Float64Array(N);
  for (let i = 0; i < N; i++) {
    correlation[i] = result[2*i] / N;  // real part, normalized
  }
  return correlation;
}

rustfft equivalent pattern:

use rustfft::{FftPlanner, num_complex::Complex};

fn compute_cross_correlation(samples_a: &[f32], samples_b: &[f32]) -> Vec<f64> {
    let len_a = samples_a.len();
    let len_b = samples_b.len();
    let n = next_power_of_two(len_a + len_b - 1);

    let mut planner = FftPlanner::<f32>::new();
    let fft = planner.plan_fft_forward(n);
    let ifft = planner.plan_fft_inverse(n);

    let mut ca: Vec<Complex<f32>> = vec![Complex::default(); n];
    let mut cb: Vec<Complex<f32>> = vec![Complex::default(); n];
    for (i, &s) in samples_a.iter().enumerate() { ca[i].re = s; }
    for (i, &s) in samples_b.iter().enumerate() { cb[i].re = s; }

    fft.process(&mut ca);
    fft.process(&mut cb);

    let mut product: Vec<Complex<f32>> = ca.iter().zip(cb.iter())
        .map(|(a, b)| a * b.conj())
        .collect();

    ifft.process(&mut product);

    product.iter().map(|c| c.re as f64 / n as f64).collect()
}

Note: rustfft's inverse transform does not normalize by N — the / n as f64 in the final map is required to match the JS / N.

next_power_of_two (also needs to live in lib.rs, JS source L18–22):

function nextPowerOfTwo(n) {
  let p = 1;
  while (p < n) p <<= 1;
  return p;
}

Implementation details

1. Add next_power_of_two(n: usize) -> usize to spike/audio-sync/src/lib.rs.
2. Add compute_cross_correlation(samples_a: &[f32], samples_b: &[f32]) -> Vec<f64> to spike/audio-sync/src/lib.rs following the pattern above.
3. Add a #[test] for next_power_of_two: assert next_power_of_two(1) == 1, next_power_of_two(2) == 2, next_power_of_two(3) == 4, next_power_of_two(300_000) == 524288.
4. Add a #[test] for compute_cross_correlation using synthesized impulses: place a 1.0 at index 0 in a and a 1.0 at index K in b; assert the correlation peak is at index K.
5. Run cargo test --manifest-path spike/audio-sync/Cargo.toml — all tests must pass.
6. Commit spike/audio-sync/src/lib.rs with both functions and their tests.

Additional test scenarios

• Both inputs all-zeros: correlation should be all-zeros, function should not panic
• Single-sample inputs: result length should be 1
• Identical inputs (a == b): peak should be at index 0 (zero lag)

Hard constraints

• Must use rustfft — no C FFT bindings
• The division by N in the final normalization step is mandatory — omitting it will cause validate_peak's SNR to be wrong by a scale factor
• No changes to files outside spike/audio-sync/src/lib.rs

Dependency issues

Depends on #95 (Cargo scaffold — Cargo.toml must exist with rustfft dependency).
Independent of #94 (fixtures) — fixtures are not needed until the round-trip test in #99.
Can be developed in parallel with #97 and #98.