| 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;
|
| - }
|
| + }
|
| }
|
|
|