/*

* Copyright 2016 The Chromium Authors. All rights reserved.

* Copyright (C) 2020, Apple Inc. All rights reserved.

*

* Redistribution and use in source and binary forms, with or without

* modification, are permitted provided that the following conditions

* are met:

* 1. Redistributions of source code must retain the above copyright

* notice, this list of conditions and the following disclaimer.

* 2. Redistributions in binary form must reproduce the above copyright

* notice, this list of conditions and the following disclaimer in the

* documentation and/or other materials provided with the distribution.

*

* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY

* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

* DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY

* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

#include "config.h"

#if ENABLE(WEB_AUDIO)

#include "IIRFilter.h"

#include "AudioArray.h"

#include "AudioUtilities.h"

#include "VectorMath.h"

#include <algorithm>

#include <complex>

#include <wtf/MathExtras.h>

namespace WebCore {

// The length of the memory buffers for the IIR filter. This MUST be a power of

// two and must be greater than the possible length of the filter coefficients.

constexpr int bufferLength = 32;

static_assert(bufferLength >= IIRFilter::maxOrder + 1, "Internal IIR buffer length must be greater than maximum IIR Filter order.");

static std::complex<double> evaluatePolynomial(const double* coefficients, std::complex<double> z, int order)

{

// Use Horner's method to evaluate the polynomial P(z) = sum(coef[k]*z^k, k, 0, order);

std::complex<double> result = 0;

for (int k = order; k >= 0; --k)

result = result * z + std::complex<double>(coefficients[k]);

return result;

}

IIRFilter::IIRFilter(const Vector<double>& feedforward, const Vector<double>& feedback)

: m_feedforward(feedforward)

, m_feedback(feedback)

{

m_xBuffer.fill(0, bufferLength);

m_yBuffer.fill(0, bufferLength);

}

void IIRFilter::reset()

{

m_xBuffer.fill(0);

m_yBuffer.fill(0);

m_bufferIndex = 0;

}

void IIRFilter::process(const float* source, float* destination, size_t framesToProcess)

{

// Compute

//

// y[n] = sum(b[k] * x[n - k], k = 0, M) - sum(a[k] * y[n - k], k = 1, N)

//

// where b[k] are the feedforward coefficients and a[k] are the feedback

// coefficients of the filter.

// This is a Direct Form I implementation of an IIR Filter. Should we

// consider doing a different implementation such as Transposed Direct Form

// II?

const double* feedback = m_feedback.data();

const double* feedforward = m_feedforward.data();

ASSERT(feedback);

ASSERT(feedforward);

// Sanity check to see if the feedback coefficients have been scaled appropriately. It must be EXACTLY 1!

ASSERT(feedback[0] == 1);

int feedbackLength = m_feedback.size();

int feedforwardLength = m_feedforward.size();

int minLength = std::min(feedbackLength, feedforwardLength);

double* xBuffer = m_xBuffer.data();

double* yBuffer = m_yBuffer.data();

for (size_t n = 0; n < framesToProcess; ++n) {

// To help minimize roundoff, we compute using double's, even though the

// filter coefficients only have single precision values.

double yn = feedforward[0] * source[n];

// Run both the feedforward and feedback terms together, when possible.

for (int k = 1; k < minLength; ++k) {

int m = (m_bufferIndex - k) & (bufferLength - 1);

yn += feedforward[k] * xBuffer[m];

yn -= feedback[k] * yBuffer[m];

}

// Handle any remaining feedforward or feedback terms.

for (int k = minLength; k < feedforwardLength; ++k)

yn += feedforward[k] * xBuffer[(m_bufferIndex - k) & (bufferLength - 1)];

for (int k = minLength; k < feedbackLength; ++k)

yn -= feedback[k] * yBuffer[(m_bufferIndex - k) & (bufferLength - 1)];

// Save the current input and output values in the memory buffers for the

// next output.

m_xBuffer[m_bufferIndex] = source[n];

m_yBuffer[m_bufferIndex] = yn;

m_bufferIndex = (m_bufferIndex + 1) & (bufferLength - 1);

destination[n] = yn;

}

}

void IIRFilter::getFrequencyResponse(unsigned length, const float* frequency, float* magResponse, float* phaseResponse)

{

// Evaluate the z-transform of the filter at the given normalized frequencies

// from 0 to 1. (One corresponds to the Nyquist frequency.)

//

// The z-tranform of the filter is

//

// H(z) = sum(b[k]*z^(-k), k, 0, M) / sum(a[k]*z^(-k), k, 0, N);

//

// The desired frequency response is H(exp(j*omega)), where omega is in [0,

// 1).

//

// Let P(x) = sum(c[k]*x^k, k, 0, P) be a polynomial of order P. Then each of

// the sums in H(z) is equivalent to evaluating a polynomial at the point

// 1/z.

for (unsigned k = 0; k < length; ++k) {

if (frequency[k] < 0 || frequency[k] > 1) {

// Out-of-bounds frequencies should return NaN.

magResponse[k] = std::nanf("");

phaseResponse[k] = std::nanf("");

} else {

// zRecip = 1/z = exp(-j*frequency)

double omega = -piDouble * frequency[k];

auto zRecip = std::complex<double>(cos(omega), sin(omega));

auto numerator = evaluatePolynomial(m_feedforward.data(), zRecip, m_feedforward.size() - 1);

auto denominator = evaluatePolynomial(m_feedback.data(), zRecip, m_feedback.size() - 1);

auto response = numerator / denominator;

magResponse[k] = static_cast<float>(abs(response));

phaseResponse[k] = static_cast<float>(atan2(imag(response), real(response)));

}

}

}

double IIRFilter::tailTime(double sampleRate, bool isFilterStable)

{

// The maximum tail time. This is somewhat arbitrary, but we're assuming that

// no one is going to expect the IIRFilter to produce an output after this

// much time after the inputs have stopped.

constexpr double maxTailTime = 10;

// If the maximum amplitude of the impulse response is less than this, we

// assume that we've reached the tail of the response. Currently, this means

// that the impulse is less than 1 bit of a 16-bit PCM value.

constexpr float maxTailAmplitude = 1 / 32768.0;

// If filter is not stable, just return max tail. Since the filter is not

// stable, the impulse response won't converge to zero, so we don't need to

// find the impulse response to find the actual tail time.

if (!isFilterStable || !sampleRate)

return maxTailTime;

// How to compute the tail time? We're going to filter an impulse

// for |maxTailTime| seconds, in blocks of kRenderQuantumFrames at

// a time. The maximum magnitude of this block is saved. After all

// of the samples have been computed, find the last block with a

// maximum magnitude greater than |kMaxTaileAmplitude|. That block

// index + 1 will be the tail time. We don't need to be

// super-accurate in computing the tail time since we process on

// blocks, block accuracy is good enough, and the value just needs

// to be larger than the "real" tail time, so we don't prematurely

// zero out the output of the node.

// Number of render quanta needed to reach the max tail time.

int numberOfBlocks = std::ceil(sampleRate * maxTailTime / AudioUtilities::renderQuantumSize);

RELEASE_ASSERT(numberOfBlocks);

// Input and output buffers for filtering.

AudioFloatArray input(AudioUtilities::renderQuantumSize);

AudioFloatArray output(AudioUtilities::renderQuantumSize);

// Array to hold the max magnitudes

AudioFloatArray magnitudes(numberOfBlocks);

// Create the impulse input signal.

input[0] = 1;

// Process the first block and get the max magnitude of the output.

process(input.data(), output.data(), AudioUtilities::renderQuantumSize);

magnitudes[0] = VectorMath::maximumMagnitude(output.data(), AudioUtilities::renderQuantumSize);

// Process the rest of the signal, getting the max magnitude of the

// output for each block.

input[0] = 0;

for (int k = 1; k < numberOfBlocks; ++k) {

process(input.data(), output.data(), AudioUtilities::renderQuantumSize);

magnitudes[k] = VectorMath::maximumMagnitude(output.data(), AudioUtilities::renderQuantumSize);

}

// Done computing the impulse response; reset the state so the actual node

// starts in the expected initial state.

reset();

// Find the last block with amplitude greater than the threshold.

int index = numberOfBlocks - 1;

for (int k = index; k >= 0; --k) {

if (magnitudes[k] > maxTailAmplitude) {

index = k;

break;

}

}

// The magnitude first become lower than the threshold at the next block.

// Compute the corresponding time value value; that's the tail time.

return (index + 1) * AudioUtilities::renderQuantumSize / sampleRate;

}

} // namespace WebCore

#endif // ENABLE(WEB_AUDIO)