Index: third_party/WebKit/LayoutTests/webaudio/resources/fft.js |
diff --git a/third_party/WebKit/LayoutTests/webaudio/resources/fft.js b/third_party/WebKit/LayoutTests/webaudio/resources/fft.js |
index 87e7235f8a211c5ae05c02972e61a676cb2b2e3c..8c9e8096b0afd915a07a01b71e78d002996c75c1 100644 |
--- a/third_party/WebKit/LayoutTests/webaudio/resources/fft.js |
+++ b/third_party/WebKit/LayoutTests/webaudio/resources/fft.js |
@@ -1,263 +1,272 @@ |
-// FFT routines. Obtained from https://github.com/rtoy/js-hacks/blob/master/fft/fft-r2-nn.js. |
+// FFT routines. Obtained from |
+// https://github.com/rtoy/js-hacks/blob/master/fft/fft-r2-nn.js. |
// |
// Create an FFT object of order |order|. This will |
// compute forward and inverse FFTs of length 2^|order|. |
function FFT(order) { |
- if (order <= 1) { |
- throw new this.FFTException(order); |
- } |
- |
- this.order = order; |
- this.N = 1 << order; |
- this.halfN = 1 << (order - 1); |
- |
- // Internal variables needed for computing each stage of the FFT. |
- this.pairsInGroup = 0; |
- this.numberOfGroups = 0; |
- this.distance = 0; |
- this.notSwitchInput = 0; |
- |
- // Work arrays |
- this.aReal = new Float32Array(this.N); |
- this.aImag = new Float32Array(this.N); |
- this.debug = 0; |
- |
- // Twiddle tables for the FFT. |
- this.twiddleCos = new Float32Array(this.N); |
- this.twiddleSin = new Float32Array(this.N); |
- |
- var omega = -2 * Math.PI / this.N; |
- for (var k = 0; k < this.N; ++k) { |
- this.twiddleCos[k] = Math.fround(Math.cos(omega * k)); |
- this.twiddleSin[k] = Math.fround(Math.sin(omega * k)); |
- } |
+ if (order <= 1) { |
+ throw new this.FFTException(order); |
+ } |
+ |
+ this.order = order; |
+ this.N = 1 << order; |
+ this.halfN = 1 << (order - 1); |
+ |
+ // Internal variables needed for computing each stage of the FFT. |
+ this.pairsInGroup = 0; |
+ this.numberOfGroups = 0; |
+ this.distance = 0; |
+ this.notSwitchInput = 0; |
+ |
+ // Work arrays |
+ this.aReal = new Float32Array(this.N); |
+ this.aImag = new Float32Array(this.N); |
+ this.debug = 0; |
+ |
+ // Twiddle tables for the FFT. |
+ this.twiddleCos = new Float32Array(this.N); |
+ this.twiddleSin = new Float32Array(this.N); |
+ |
+ let omega = -2 * Math.PI / this.N; |
+ for (let k = 0; k < this.N; ++k) { |
+ this.twiddleCos[k] = Math.fround(Math.cos(omega * k)); |
+ this.twiddleSin[k] = Math.fround(Math.sin(omega * k)); |
+ } |
} |
-FFT.prototype.FFTException = function (order) { |
- this.value = order; |
- this.message = "Order must be greater than 1: "; |
- this.toString = function () { |
- return this.message + this.value; |
- }; |
+FFT.prototype.FFTException = |
+ function(order) { |
+ this.value = order; |
+ this.message = 'Order must be greater than 1: '; |
+ this.toString = function() { |
+ return this.message + this.value; |
+ }; |
} |
-// Core routine that does one stage of the FFT, implementing all of |
-// the butterflies for that stage. |
-FFT.prototype.FFTRadix2Core = function (aReal, aImag, bReal, bImag) { |
- var index = 0; |
- for (var k = 0; k < this.numberOfGroups; ++k) { |
- var jfirst = 2 * k * this.pairsInGroup; |
- var jlast = jfirst + this.pairsInGroup - 1; |
- var jtwiddle = k * this.pairsInGroup; |
- var wr = this.twiddleCos[jtwiddle]; |
- var wi = this.twiddleSin[jtwiddle]; |
- |
- for (var j = jfirst; j <= jlast; ++j) { |
- // temp = w * a[j + distance] |
- var idx = j + this.distance; |
- var tr = wr * aReal[idx] - wi * aImag[idx]; |
- var ti = wr * aImag[idx] + wi * aReal[idx]; |
- |
- bReal[index] = aReal[j] + tr; |
- bImag[index] = aImag[j] + ti; |
- bReal[index + this.halfN] = aReal[j] - tr; |
- bImag[index + this.halfN] = aImag[j] - ti; |
- ++index; |
- } |
+ // Core routine that does one stage of the FFT, implementing all of |
+ // the butterflies for that stage. |
+ FFT.prototype.FFTRadix2Core = |
+ function(aReal, aImag, bReal, bImag) { |
+ let index = 0; |
+ for (let k = 0; k < this.numberOfGroups; ++k) { |
+ let jfirst = 2 * k * this.pairsInGroup; |
+ let jlast = jfirst + this.pairsInGroup - 1; |
+ let jtwiddle = k * this.pairsInGroup; |
+ let wr = this.twiddleCos[jtwiddle]; |
+ let wi = this.twiddleSin[jtwiddle]; |
+ |
+ for (let j = jfirst; j <= jlast; ++j) { |
+ // temp = w * a[j + distance] |
+ let idx = j + this.distance; |
+ let tr = wr * aReal[idx] - wi * aImag[idx]; |
+ let ti = wr * aImag[idx] + wi * aReal[idx]; |
+ |
+ bReal[index] = aReal[j] + tr; |
+ bImag[index] = aImag[j] + ti; |
+ bReal[index + this.halfN] = aReal[j] - tr; |
+ bImag[index + this.halfN] = aImag[j] - ti; |
+ ++index; |
} |
+ } |
} |
-// Forward out-of-place complex FFT. |
-// |
-// Computes the forward FFT, b, of a complex vector x: |
-// |
-// b[k] = sum(x[n] * W^(k*n), n, 0, N - 1), k = 0, 1,..., N-1 |
-// |
-// where |
-// N = length of x, which must be a power of 2 and |
-// W = exp(-2*i*pi/N) |
-// |
-// x = |xr| + i*|xi| |
-// b = |bReal| + i*|bImag| |
-FFT.prototype.fft = function (xr, xi, bReal, bImag) { |
- this.pairsInGroup = this.halfN; |
- this.numberOfGroups = 1; |
- this.distance = this.halfN; |
- this.notSwitchInput = true; |
- |
- // Arrange it so that the last iteration puts the desired output |
- // in bReal/bImag. |
- if (this.order & 1 == 1) { |
- this.FFTRadix2Core(xr, xi, bReal, bImag); |
- this.notSwitchInput = !this.notSwitchInput; |
+ // Forward out-of-place complex FFT. |
+ // |
+ // Computes the forward FFT, b, of a complex vector x: |
+ // |
+ // b[k] = sum(x[n] * W^(k*n), n, 0, N - 1), k = 0, 1,..., N-1 |
+ // |
+ // where |
+ // N = length of x, which must be a power of 2 and |
+ // W = exp(-2*i*pi/N) |
+ // |
+ // x = |xr| + i*|xi| |
+ // b = |bReal| + i*|bImag| |
+ FFT.prototype.fft = |
+ function(xr, xi, bReal, bImag) { |
+ this.pairsInGroup = this.halfN; |
+ this.numberOfGroups = 1; |
+ this.distance = this.halfN; |
+ this.notSwitchInput = true; |
+ |
+ // Arrange it so that the last iteration puts the desired output |
+ // in bReal/bImag. |
+ if (this.order & 1 == 1) { |
+ this.FFTRadix2Core(xr, xi, bReal, bImag); |
+ this.notSwitchInput = !this.notSwitchInput; |
+ } else { |
+ this.FFTRadix2Core(xr, xi, this.aReal, this.aImag); |
+ } |
+ |
+ this.pairsInGroup >>= 1; |
+ this.numberOfGroups <<= 1; |
+ this.distance >>= 1; |
+ |
+ while (this.numberOfGroups < this.N) { |
+ if (this.notSwitchInput) { |
+ this.FFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
} else { |
- this.FFTRadix2Core(xr, xi, this.aReal, this.aImag); |
+ this.FFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
} |
+ this.notSwitchInput = !this.notSwitchInput; |
this.pairsInGroup >>= 1; |
this.numberOfGroups <<= 1; |
this.distance >>= 1; |
- |
- while (this.numberOfGroups < this.N) { |
- if (this.notSwitchInput) { |
- this.FFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
- } else { |
- this.FFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
- } |
- |
- this.notSwitchInput = !this.notSwitchInput; |
- this.pairsInGroup >>= 1; |
- this.numberOfGroups <<= 1; |
- this.distance >>= 1; |
- } |
+ } |
} |
-// Core routine that does one stage of the FFT, implementing all of |
-// the butterflies for that stage. This is identical to |
-// FFTRadix2Core, except the twiddle factor, w, is the conjugate. |
-FFT.prototype.iFFTRadix2Core = function (aReal, aImag, bReal, bImag) { |
- var index = 0; |
- for (var k = 0; k < this.numberOfGroups; ++k) { |
- var jfirst = 2 * k * this.pairsInGroup; |
- var jlast = jfirst + this.pairsInGroup - 1; |
- var jtwiddle = k * this.pairsInGroup; |
- var wr = this.twiddleCos[jtwiddle]; |
- var wi = -this.twiddleSin[jtwiddle]; |
- |
- for (var j = jfirst; j <= jlast; ++j) { |
- // temp = w * a[j + distance] |
- var idx = j + this.distance; |
- var tr = wr * aReal[idx] - wi * aImag[idx]; |
- var ti = wr * aImag[idx] + wi * aReal[idx]; |
- |
- bReal[index] = aReal[j] + tr; |
- bImag[index] = aImag[j] + ti; |
- bReal[index + this.halfN] = aReal[j] - tr; |
- bImag[index + this.halfN] = aImag[j] - ti; |
- ++index; |
- } |
+ // Core routine that does one stage of the FFT, implementing all of |
+ // the butterflies for that stage. This is identical to |
+ // FFTRadix2Core, except the twiddle factor, w, is the conjugate. |
+ FFT.prototype.iFFTRadix2Core = |
+ function(aReal, aImag, bReal, bImag) { |
+ let index = 0; |
+ for (let k = 0; k < this.numberOfGroups; ++k) { |
+ let jfirst = 2 * k * this.pairsInGroup; |
+ let jlast = jfirst + this.pairsInGroup - 1; |
+ let jtwiddle = k * this.pairsInGroup; |
+ let wr = this.twiddleCos[jtwiddle]; |
+ let wi = -this.twiddleSin[jtwiddle]; |
+ |
+ for (let j = jfirst; j <= jlast; ++j) { |
+ // temp = w * a[j + distance] |
+ let idx = j + this.distance; |
+ let tr = wr * aReal[idx] - wi * aImag[idx]; |
+ let ti = wr * aImag[idx] + wi * aReal[idx]; |
+ |
+ bReal[index] = aReal[j] + tr; |
+ bImag[index] = aImag[j] + ti; |
+ bReal[index + this.halfN] = aReal[j] - tr; |
+ bImag[index + this.halfN] = aImag[j] - ti; |
+ ++index; |
} |
+ } |
} |
-// Inverse out-of-place complex FFT. |
-// |
-// Computes the inverse FFT, b, of a complex vector x: |
-// |
-// b[k] = sum(x[n] * W^(-k*n), n, 0, N - 1), k = 0, 1,..., N-1 |
-// |
-// where |
-// N = length of x, which must be a power of 2 and |
-// W = exp(-2*i*pi/N) |
-// |
-// x = |xr| + i*|xi| |
-// b = |bReal| + i*|bImag| |
-// |
-// Note that ifft(fft(x)) = N * x. To get x, call ifftScale to scale |
-// the output of the ifft appropriately. |
-FFT.prototype.ifft = function (xr, xi, bReal, bImag) { |
- this.pairsInGroup = this.halfN; |
- this.numberOfGroups = 1; |
- this.distance = this.halfN; |
- this.notSwitchInput = true; |
- |
- // Arrange it so that the last iteration puts the desired output |
- // in bReal/bImag. |
- if (this.order & 1 == 1) { |
- this.iFFTRadix2Core(xr, xi, bReal, bImag); |
- this.notSwitchInput = !this.notSwitchInput; |
+ // Inverse out-of-place complex FFT. |
+ // |
+ // Computes the inverse FFT, b, of a complex vector x: |
+ // |
+ // b[k] = sum(x[n] * W^(-k*n), n, 0, N - 1), k = 0, 1,..., N-1 |
+ // |
+ // where |
+ // N = length of x, which must be a power of 2 and |
+ // W = exp(-2*i*pi/N) |
+ // |
+ // x = |xr| + i*|xi| |
+ // b = |bReal| + i*|bImag| |
+ // |
+ // Note that ifft(fft(x)) = N * x. To get x, call ifftScale to |
+ // scale the output of the ifft appropriately. |
+ FFT.prototype.ifft = |
+ function(xr, xi, bReal, bImag) { |
+ this.pairsInGroup = this.halfN; |
+ this.numberOfGroups = 1; |
+ this.distance = this.halfN; |
+ this.notSwitchInput = true; |
+ |
+ // Arrange it so that the last iteration puts the desired output |
+ // in bReal/bImag. |
+ if (this.order & 1 == 1) { |
+ this.iFFTRadix2Core(xr, xi, bReal, bImag); |
+ this.notSwitchInput = !this.notSwitchInput; |
+ } else { |
+ this.iFFTRadix2Core(xr, xi, this.aReal, this.aImag); |
+ } |
+ |
+ this.pairsInGroup >>= 1; |
+ this.numberOfGroups <<= 1; |
+ this.distance >>= 1; |
+ |
+ while (this.numberOfGroups < this.N) { |
+ if (this.notSwitchInput) { |
+ this.iFFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
} else { |
- this.iFFTRadix2Core(xr, xi, this.aReal, this.aImag); |
+ this.iFFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
} |
+ this.notSwitchInput = !this.notSwitchInput; |
this.pairsInGroup >>= 1; |
this.numberOfGroups <<= 1; |
this.distance >>= 1; |
- |
- while (this.numberOfGroups < this.N) { |
- |
- if (this.notSwitchInput) { |
- this.iFFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
- } else { |
- this.iFFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
- } |
- |
- this.notSwitchInput = !this.notSwitchInput; |
- this.pairsInGroup >>= 1; |
- this.numberOfGroups <<= 1; |
- this.distance >>= 1; |
- } |
+ } |
} |
-// |
-// Scales the IFFT by 1/N, done in place. |
-FFT.prototype.ifftScale = function (xr, xi) { |
- var factor = 1 / this.N; |
- for (var k = 0; k < this.N; ++k) { |
- xr[k] *= factor; |
- xi[k] *= factor; |
- } |
+ // |
+ // Scales the IFFT by 1/N, done in place. |
+ FFT.prototype.ifftScale = |
+ function(xr, xi) { |
+ let factor = 1 / this.N; |
+ for (let k = 0; k < this.N; ++k) { |
+ xr[k] *= factor; |
+ xi[k] *= factor; |
+ } |
} |
-// First stage for the RFFT. Basically the same as FFTRadix2Core, but |
-// we assume aImag is 0, and adjust the code accordingly. |
-FFT.prototype.RFFTRadix2CoreStage1 = function (aReal, bReal, bImag) { |
- var index = 0; |
- for (var k = 0; k < this.numberOfGroups; ++k) { |
- var jfirst = 2 * k * this.pairsInGroup; |
- var jlast = jfirst + this.pairsInGroup - 1; |
- var jtwiddle = k * this.pairsInGroup; |
- var wr = this.twiddleCos[jtwiddle]; |
- var wi = this.twiddleSin[jtwiddle]; |
- |
- for (var j = jfirst; j <= jlast; ++j) { |
- // temp = w * a[j + distance] |
- var idx = j + this.distance; |
- var tr = wr * aReal[idx]; |
- var ti = wi * aReal[idx]; |
- |
- bReal[index] = aReal[j] + tr; |
- bImag[index] = ti; |
- bReal[index + this.halfN] = aReal[j] - tr; |
- bImag[index + this.halfN] = -ti; |
- ++index; |
- } |
+ // First stage for the RFFT. Basically the same as |
+ // FFTRadix2Core, but we assume aImag is 0, and adjust |
+ // the code accordingly. |
+ FFT.prototype.RFFTRadix2CoreStage1 = |
+ function(aReal, bReal, bImag) { |
+ let index = 0; |
+ for (let k = 0; k < this.numberOfGroups; ++k) { |
+ let jfirst = 2 * k * this.pairsInGroup; |
+ let jlast = jfirst + this.pairsInGroup - 1; |
+ let jtwiddle = k * this.pairsInGroup; |
+ let wr = this.twiddleCos[jtwiddle]; |
+ let wi = this.twiddleSin[jtwiddle]; |
+ |
+ for (let j = jfirst; j <= jlast; ++j) { |
+ // temp = w * a[j + distance] |
+ let idx = j + this.distance; |
+ let tr = wr * aReal[idx]; |
+ let ti = wi * aReal[idx]; |
+ |
+ bReal[index] = aReal[j] + tr; |
+ bImag[index] = ti; |
+ bReal[index + this.halfN] = aReal[j] - tr; |
+ bImag[index + this.halfN] = -ti; |
+ ++index; |
} |
+ } |
} |
-// Forward Real FFT. Like fft, but the signal is assumed to be real, |
-// so the imaginary part is not supplied. The output, however, is |
-// still the same and is returned in two arrays. (This could be |
-// optimized to use less storage, both internally and for the output, |
-// but we don't do that.) |
-FFT.prototype.rfft = function (xr, bReal, bImag) { |
- this.pairsInGroup = this.halfN; |
- this.numberOfGroups = 1; |
- this.distance = this.halfN; |
- this.notSwitchInput = true; |
- |
- // Arrange it so that the last iteration puts the desired output |
- // in bReal/bImag. |
- if (this.order & 1 == 1) { |
- this.RFFTRadix2CoreStage1(xr, bReal, bImag); |
- this.notSwitchInput = !this.notSwitchInput; |
+ // Forward Real FFT. Like fft, but the signal is |
+ // assumed to be real, so the imaginary part is not |
+ // supplied. The output, however, is still the same |
+ // and is returned in two arrays. (This could be |
+ // optimized to use less storage, both internally |
+ // and for the output, but we don't do that.) |
+ FFT.prototype.rfft = function(xr, bReal, bImag) { |
+ this.pairsInGroup = this.halfN; |
+ this.numberOfGroups = 1; |
+ this.distance = this.halfN; |
+ this.notSwitchInput = true; |
+ |
+ // Arrange it so that the last iteration puts the desired output |
+ // in bReal/bImag. |
+ if (this.order & 1 == 1) { |
+ this.RFFTRadix2CoreStage1(xr, bReal, bImag); |
+ this.notSwitchInput = !this.notSwitchInput; |
+ } else { |
+ this.RFFTRadix2CoreStage1(xr, this.aReal, this.aImag); |
+ } |
+ |
+ this.pairsInGroup >>= 1; |
+ this.numberOfGroups <<= 1; |
+ this.distance >>= 1; |
+ |
+ while (this.numberOfGroups < this.N) { |
+ if (this.notSwitchInput) { |
+ this.FFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
} else { |
- this.RFFTRadix2CoreStage1(xr, this.aReal, this.aImag); |
+ this.FFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
} |
+ this.notSwitchInput = !this.notSwitchInput; |
this.pairsInGroup >>= 1; |
this.numberOfGroups <<= 1; |
this.distance >>= 1; |
- |
- while (this.numberOfGroups < this.N) { |
- if (this.notSwitchInput) { |
- this.FFTRadix2Core(this.aReal, this.aImag, bReal, bImag); |
- } else { |
- this.FFTRadix2Core(bReal, bImag, this.aReal, this.aImag); |
- } |
- |
- this.notSwitchInput = !this.notSwitchInput; |
- this.pairsInGroup >>= 1; |
- this.numberOfGroups <<= 1; |
- this.distance >>= 1; |
- } |
+ } |
} |