text: /*===========================================================================*\
   * Fast Fourier Transform (Cooley-Tukey Method)
   *
   * (c) Vail Systems. Joshua Jung and Ben Bryan. 2015
   *
   * This code is not designed to be highly optimized but as an educational
   * tool to understand the Fast Fourier Transform.
  \*===========================================================================*/
  
  //------------------------------------------------
  // Note: Some of this code is not optimized and is
  // primarily designed as an educational and testing
  // tool.
  // To get high performace would require transforming
  // the recursive calls into a loop and then loop
  // unrolling. All of this is best accomplished
  // in C or assembly.
  //-------------------------------------------------
  
  //-------------------------------------------------
  // The following code assumes a complex number is
  // an array: [real, imaginary]
  //-------------------------------------------------
  import * as complex from './complex.js'
  import * as fftUtil from './fftutil.js'
  
  let countTrailingZeros = function (v) {
    var c = 32;
    v &= -v;
    if (v) c--;
    if (v & 0x0000FFFF) c -= 16;
    if (v & 0x00FF00FF) c -= 8;
    if (v & 0x0F0F0F0F) c -= 4;
    if (v & 0x33333333) c -= 2;
    if (v & 0x55555555) c -= 1;
    return c;
  }
  
  let reverse = function(v) {
    return  (REVERSE_TABLE[ v         & 0xff] << 24) |
            (REVERSE_TABLE[(v >>> 8)  & 0xff] << 16) |
            (REVERSE_TABLE[(v >>> 16) & 0xff] << 8)  |
             REVERSE_TABLE[(v >>> 24) & 0xff];
  }
  
  let INT_BITS= 32
  
  export let fft = function (vector) {
    var X = [],
        N = vector.length;
  
    // Base case is X = x + 0i since our input is assumed to be real only.
    if (N == 1) {
      if (Array.isArray(vector[0])) //If input vector contains complex numbers
        return [[vector[0][0], vector[0][1]]];
      else
        return [[vector[0], 0]];
    }
  
    // Recurse: all even samples
    var X_evens = fft(vector.filter(even)),
  
        // Recurse: all odd samples
        X_odds  = fft(vector.filter(odd));
  
    // Now, perform N/2 operations!
    for (var k = 0; k < N / 2; k++) {
      // t is a complex number!
      var t = X_evens[k],
          e = complex.multiply(fftUtil.exponent(k, N), X_odds[k]);
  
      X[k] = complex.add(t, e);
      X[k + (N / 2)] = complex.subtract(t, e);
    }
  
    function even(__, ix) {
      return ix % 2 == 0;
    }
  
    function odd(__, ix) {
      return ix % 2 == 1;
    }
  
    return X;
  }
  
  export let fftInPlace = function(vector) {
      var N = vector.length;
  
      var trailingZeros = countTrailingZeros(N); //Once reversed, this will be leading zeros
  
      // Reverse bits
      for (var k = 0; k < N; k++) {
        var p = twiddle.reverse(k) >>> (twiddle.INT_BITS - trailingZeros);
        if (p > k) {
          var complexTemp = [vector[k], 0];
          vector[k] = vector[p];
          vector[p] = complexTemp;
        } else {
          vector[p] = [vector[p], 0];
        }
      }
  
      //Do the DIT now in-place
      for (var len = 2; len <= N; len += len) {
        for (var i = 0; i < len / 2; i++) {
          var w = fftUtil.exponent(i, len);
          for (var j = 0; j < N / len; j++) {
            var t = complex.multiply(w, vector[j * len + i + len / 2]);
            vector[j * len + i + len / 2] = complex.subtract(vector[j * len + i], t);
            vector[j * len + i] = complex.add(vector[j * len + i], t);
          }
        }
      }
    }
  