Thanks for the review!
On 2015-02-01 15:37, Alexander E. Patrakov wrote:
> 29.01.2015 03:14, David Henningsson wrote:
>> The chrome OS audio server has some already existing code, which
>> has been made available under a BSD-style license, which should be
>> safe to import by us.
>>
>> Signed-off-by: David Henningsson <david.henningsson at canonical.com>
>> ---
>> LICENSE | 3 +
>> src/pulsecore/filter/LICENSE.WEBKIT | 27 +++
>> src/pulsecore/filter/biquad.c | 368
>> ++++++++++++++++++++++++++++++++++++
>> src/pulsecore/filter/biquad.h | 57 ++++++
>> src/pulsecore/filter/crossover.c | 188 ++++++++++++++++++
>> src/pulsecore/filter/crossover.h | 70 +++++++
>> 6 files changed, 713 insertions(+)
>> create mode 100644 src/pulsecore/filter/LICENSE.WEBKIT
>> create mode 100644 src/pulsecore/filter/biquad.c
>> create mode 100644 src/pulsecore/filter/biquad.h
>> create mode 100644 src/pulsecore/filter/crossover.c
>> create mode 100644 src/pulsecore/filter/crossover.h
>>
>> diff --git a/LICENSE b/LICENSE
>> index 226c4ce..6932317 100644
>> --- a/LICENSE
>> +++ b/LICENSE
>> @@ -29,6 +29,9 @@ considered too small and stable to be considered as
>> an external library) use the
>> more permissive MIT license. This include the device reservation
>> DBus protocol
>> and realtime kit implementations.
>>
>> +A more permissive BSD-style license is used for LFE filters, see
>> +src/pulsecore/filter/LICENSE.WEBKIT for details.
>> +
>> Additionally, a more permissive Sun license is used for code that
>> performs
>> u-law, A-law and linear PCM conversions.
>>
>> diff --git a/src/pulsecore/filter/LICENSE.WEBKIT
>> b/src/pulsecore/filter/LICENSE.WEBKIT
>> new file mode 100644
>> index 0000000..2f69d9f
>> --- /dev/null
>> +++ b/src/pulsecore/filter/LICENSE.WEBKIT
>> @@ -0,0 +1,27 @@
>> +/*
>> + * Copyright (C) 2010 Google 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.
>> + * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the
>> names of
>> + * its contributors may be used to endorse or promote products
>> derived
>> + * from this software without specific prior written permission.
>> + *
>> + * THIS SOFTWARE IS PROVIDED BY APPLE 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 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.
>> + */
>> diff --git a/src/pulsecore/filter/biquad.c
>> b/src/pulsecore/filter/biquad.c
>> new file mode 100644
>> index 0000000..b28256d
>> --- /dev/null
>> +++ b/src/pulsecore/filter/biquad.c
>> @@ -0,0 +1,368 @@
>> +/* Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
>> + * Use of this source code is governed by a BSD-style license that
>> can be
>> + * found in the LICENSE file.
>> + */
>> +
>> +/* Copyright (C) 2010 Google Inc. All rights reserved.
>> + * Use of this source code is governed by a BSD-style license that
>> can be
>> + * found in the LICENSE.WEBKIT file.
>> + */
>> +
>> +#include <math.h>
>> +#include "biquad.h"
>> +
>> +#ifndef max
>> +#define max(a, b) ({ __typeof__(a) _a = (a); \
>> + __typeof__(b) _b = (b); \
>> + _a > _b ? _a : _b; })
>> +#endif
>> +
>> +#ifndef min
>> +#define min(a, b) ({ __typeof__(a) _a = (a); \
>> + __typeof__(b) _b = (b); \
>> + _a < _b ? _a : _b; })
>> +#endif
>> +
>> +#ifndef M_PI
>> +#define M_PI 3.14159265358979323846
>> +#endif
>> +
>> +static void set_coefficient(struct biquad *bq, double b0, double b1,
>> double b2,
>> + double a0, double a1, double a2)
>> +{
>> + double a0_inv = 1 / a0;
>> + bq->b0 = b0 * a0_inv;
>> + bq->b1 = b1 * a0_inv;
>> + bq->b2 = b2 * a0_inv;
>> + bq->a1 = a1 * a0_inv;
>> + bq->a2 = a2 * a0_inv;
>> +}
>> +
>> +static void biquad_lowpass(struct biquad *bq, double cutoff, double
>> resonance)
>> +{
>> + /* Limit cutoff to 0 to 1. */
>> + cutoff = max(0.0, min(cutoff, 1.0));
>> +
>> + if (cutoff == 1) {
>> + /* When cutoff is 1, the z-transform is 1. */
>> + set_coefficient(bq, 1, 0, 0, 1, 0, 0);
>> + } else if (cutoff > 0) {
>> + /* Compute biquad coefficients for lowpass filter */
>> + resonance = max(0.0, resonance); /* can't go negative */
>> + double g = pow(10.0, 0.05 * resonance);
>> + double d = sqrt((4 - sqrt(16 - 16 / (g * g))) / 2);
>> +
>> + double theta = M_PI * cutoff;
>> + double sn = 0.5 * d * sin(theta);
>> + double beta = 0.5 * (1 - sn) / (1 + sn);
>> + double gamma = (0.5 + beta) * cos(theta);
>> + double alpha = 0.25 * (0.5 + beta - gamma);
>> +
>> + double b0 = 2 * alpha;
>> + double b1 = 2 * 2 * alpha;
>> + double b2 = 2 * alpha;
>> + double a1 = 2 * -gamma;
>> + double a2 = 2 * beta;
>> +
>> + set_coefficient(bq, b0, b1, b2, 1, a1, a2);
>> + } else {
>> + /* When cutoff is zero, nothing gets through the filter, so set
>> + * coefficients up correctly.
>> + */
>> + set_coefficient(bq, 0, 0, 0, 1, 0, 0);
>> + }
>> +}
>
> This definitely comes from some book, so a reference would be nice.
>
> Also, even though the function is static, it would be nice to describe
> the meaning (including units) of each parameter. And why do we have
> "double resonance" with some decibel-conversion applied to it, instead
> of the more-common Q-factor? Does this function come from the "matched
> Z-transform", "bilinear transform" or "impulse invariance" method of
> digital filter design? [just to check the understanding]
>
> (well, by comparing with a known set of filter coefficients for certain
> parameters, I can tell that a bilinear transform and frequency-warping
> is apparently used here, and that "resonance == 0", as passed from
> crossover.c, indeed results in a Butterworth filter)
>
> IOW, too much "scientific code" without proper comments, references, or
> simple testcases.
>
>> +
>> +static void biquad_highpass(struct biquad *bq, double cutoff, double
>> resonance)
>
> (trimming the quotation, because the above is enough to illustrate the
> point)
>
>> +static void biquad_bandpass(struct biquad *bq, double frequency,
>> double Q)
> ...
>
>> +static void biquad_peaking(struct biquad *bq, double frequency,
>> double Q,
>> + double db_gain)
>> +void biquad_set(struct biquad *bq, enum biquad_type type, double
>> freq, double Q,
>> + double gain)
>
> Of the above, you use only lowpass and highpass biquad filters. I.e. too
> much dead code. Please delete, because we are not implementing Web Audio
> API, and because the math cannot change and thus does not have to be
> maintained.
>
> Besides, the function uses a very non-standard definition of Q. In this
> function, to get a Butterworth filter, Q == 0 is passed, while,
> according to the traditional definition, Q == 0.707 should result in a
> Butterworth filter.
>
> Currently, we only need to be able to design 2nd order highpass and
> lowpass Butterworth filters with a given cutoff frequency, which is
> supposed to be very low as compared to the sample rate, so that the
> "bilinear transform vs other alternatives" distinction does not matter.
> Later, for the "virtual headphone" effect that is also based on IIR
> filters, I would need to set the biquad coefficients directly (e.g.,
> load from a file).
>
> If adding proper comments to all the math is a too-hard requirement,
> then, in v2, I'd suggest to (temporarily?) squash patches 1 and 2 for
> easier review, and to remove all unused functions and parameters.
So to answer to these more general thoughts:
- Yes, I think removing dead code makes sense. I was thinking that
maybe it makes sense to have it in case we wanted to implement more
filters later, but perhaps we should take that problem when it happens.
- Adding comments and references is going to be difficult as I'm not
an DSP expert.
- As for squashing patches, I think it's important that patch 1/6
remains the way it is for tracking/Copyright purposes (i e who wrote
what code). I can commit to that in v2, I'll make three patches - the
two first ones and a third to remove dead code - and also post the
combined diff of these three for easier reviewing.
>> diff --git a/src/pulsecore/filter/biquad.h
>> b/src/pulsecore/filter/biquad.h
>
> Not reviewing, as all criticisms are already expressed above.
>
>> +/* The biquad filter parameters. The transfer function H(z) is (b0 +
>> b1 * z^(-1)
>> + * + b2 * z^(-2)) / (1 + a1 * z^(-1) + a2 * z^(-2)). The previous
>> two inputs
>> + * are stored in x1 and x2, and the previous two outputs are stored
>> in y1 and
>> + * y2.
>> + *
>> + * We use double during the coefficients calculation for better
>> accurary, but
>> + * float is used during the actual filtering for faster computation.
>> + */
>
> Yes, this is the kind of comments that I am looking for.
>
>> +struct biquad {
>> + float b0, b1, b2;
>> + float a1, a2;
>> + float x1, x2;
>> + float y1, y2;
>> +};
>
> You don't seem to use this directly, but copy the coefficients and the
> history into struct lr4. Maybe it makes sense to remove x1, x2, y1, y2
> from this structure, and use a "struct biquad coeffs;" inside struct lr4?
>
>> +static void lr4_set(struct lr4 *lr4, enum biquad_type type, float freq)
>> +{
>> + struct biquad q;
>> + biquad_set(&q, type, freq, 0, 0);
>
> I have verified that passing 0, 0 as the last two parameters indeed
> yields a Butterworth filter of 2nd order.
If the definition of Q is non-standard (0 instead of 2^-0.5), and Q is
never anything else than 0, maybe we should just remove Q as a function
argument here.
>> +/* Split input data using two LR4 filters, put the result into the
>> input array
>> + * and another array.
>> + *
>> + * data0 --+-- lp --> data0
>> + * |
>> + * \-- hp --> data1
>
> Why? Later you seem to fight with the in-place processing in PATCH 5/6,
> "Make sure we get a copy - we want to keep our original unchanged".
Good point.
>> + */
>> +static void lr4_split(struct lr4 *lp, struct lr4 *hp, int count,
>> float *data0,
>> + float *data1)
>> +{
>
> The implementation of this strange function is correct.
>
>> +/* Split input data using two LR4 filters and sum them back to the
>> original
>> + * data array.
>> + *
>> + * data --+-- lp --+--> data
>> + * | |
>> + * \-- hp --/
>> + */
>> +static void lr4_merge(struct lr4 *lp, struct lr4 *hp, int count,
>> float *data)
>> +{
>
> Also correct.
>
> But later (in PATCH 2/6) you write your own functions that contain the
> same math. Again, this is an argument for squashing the first two
> patches (at least for review purposes).
>
>> diff --git a/src/pulsecore/filter/crossover.h
>> b/src/pulsecore/filter/crossover.h
>> new file mode 100644
>> index 0000000..99a601c
>> --- /dev/null
>> +++ b/src/pulsecore/filter/crossover.h
>> @@ -0,0 +1,70 @@
>> +/* Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
>> + * Use of this source code is governed by a BSD-style license that
>> can be
>> + * found in the LICENSE file.
>> + */
>> +
>> +#ifndef CROSSOVER_H_
>> +#define CROSSOVER_H_
>> +
>> +#ifdef __cplusplus
>> +extern "C" {
>> +#endif
>> +
>> +/* An LR4 filter is two biquads with the same parameters connected in
>> series:
>> + *
>> + * x -- [BIQUAD] -- y -- [BIQUAD] -- z
>> + *
>> + * Both biquad filter has the same parameter b[012] and a[12],
>> + * The variable [xyz][12] keep the history values.
>> + */
>> +struct lr4 {
>> + float b0, b1, b2;
>> + float a1, a2;
>> + float x1, x2;
>> + float y1, y2;
>> + float z1, z2;
>> +};
>> +
>> +/* Three bands crossover filter:
>> + *
>> + * INPUT --+-- lp0 --+-- lp1 --+---> LOW (0)
>> + * | | |
>> + * | \-- hp1 --/
>> + * |
>> + * \-- hp0 --+-- lp2 ------> MID (1)
>> + * |
>> + * \-- hp2 ------> HIGH (2)
>> + *
>> + * [f0] [f1]
>> + *
>> + * Each lp or hp is an LR4 filter, which consists of two second-order
>> + * lowpass or highpass butterworth filters.
>> + */
>
> Do we actually need this three-band filter on any known hardware?
This is also dead code. ChromeOS uses this for a multiband compressor [1].
--
David Henningsson, Canonical Ltd.
https://launchpad.net/~diwic
[1] https://github.com/drinkcat/adhd/blob/master/cras/src/dsp/drc.h
