fft function

void fft(int n, Int32List v)

Implementation

void fft(int n, Int32List v) {
  int scale = kLogFftSize;

  // Bit reversal
  for (int r = 0, i = 1; i < n; ++i) {
    for (int p = n; (p & r) == 0;) {
      p >>= 1;
      r ^= p;
    }
    if (i < r) {
      // Swap values
      int t = v[i];
      v[i] = v[r];
      v[r] = t;
    }
  }

  // FFT computation
  for (int p = 1; p < n; p <<= 1) {
    --scale;
    for (int i = 0; i < n; i += p << 1) {
      int x = _half(v[i]);
      int y = _half(v[i + p]);
      v[i] = (x + y);
      v[i + p] = (x - y);
    }

    for (int r = 1; r < p; ++r) {
      int w = (kMaxFftSize ~/ 4) - (r << scale);
      int i = w >> 31;
      w = int32((twiddle[(w ^ i) - i] ^ (i << 16)));

      for (i = r; i < n; i += p << 1) {
        int x = _half(v[i]);
        int y = _mult(w, v[i + p]);
        v[i] = (x - y);
        v[i + p] = (x + y);
      }
    }
  }
}