[FFmpeg-devel] [PATCH/RFC] Remove triplication of compute_lpc_coefs() function

[Michael Niedermayer]

On Sun, Aug 31, 2008 at 05:08:26AM +0200, Vitor Sessak wrote:
> Michael Niedermayer wrote:
>> On Thu, Aug 28, 2008 at 02:28:50PM +0200, Vitor Sessak wrote:
>>> Hi all.
>>>
>>> I've finally found a more or less clean way of doing $subj. I also want 
>>> to 
>> going back to this patch ...
>> after some tests, ive not been able to find a compute_lpc_coefs() with 
>> floats
>> that results in acceptable compression
>> btw, my tests gave:
>> 27063400
>> vs.
>> 27731934
>> which is a little worse than the 0.4% quoted ... (so much for the, it 
>> doesnt
>> matter)
>> using http://www.gnu.org/fun/jokes/eternal-flame.ogg
>> so lets see if we can improve this patch ...
>> [...]
>>> +    if ((autoc[max_order] == 0 || autoc[0] <= 0) && fail)
>>> +        return -1;
>> fail should be first
>
> done (but I wonder if gcc would be so stupid not to optimize this out in an 
> inline function)
>
>>> +
>>> +    for(i=0; i<max_order; i++) lpc_tmp[i] = 0;
>>> +    err = autoc[0];
>>> +
>>> +    for(i=0; i<max_order; i++) {
>>> +        if (normalize) {
>>> +            r = -autoc[i+1];
>>> +            for(j=0; j<i; j++) {
>>> +                r -= lpc_tmp[j] * autoc[i-j];
>>> +            }
>>> +            r /= err;
>>> +        } else
>>> +            r = -autoc[i];
>>> +
>>> +        if (ref)
>>> +            ref[i] = fabs(r);
>>> +
>>> +        err *= 1.0 - (r * r);
>>> +
>>> +        i2 = (i >> 1);
>>> +        lpc_tmp[i] = r;
>>> +        for(j=0; j<i2; j++) {
>>> +            tmp = lpc_tmp[j];
>>> +            lpc_tmp[j] += r * lpc_tmp[i-1-j];
>>> +            lpc_tmp[i-1-j] += r * tmp;
>>> +        }
>>> +        if(i & 1) {
>>> +            lpc_tmp[j] += lpc_tmp[j] * r;
>>> +        }
>>> +
>>> +        if (lpc)
>>> +            for(j=0; j<=i; j++) {
>>> +                lpc[i][j] = -lpc_tmp[j];
>>> +            }
>> is this really needed?
>> cant a simple
>> lpc+= stride;
>> be used to decide if space gets reused or all intermediates get exported?
>
> It could, but I won't make the code simpler. lpc_tmp (which is not a 
> temporary var, actually) will be modified in the next loop iteration, so 
> one have to do some memcpy'ing anyway. (Yes, I plan to rename lpc_tmp after 
> this patch is commited).

for(i=0; i<max_order; i++) {
    LPC_type r = -autoc[i+1];
    LPC_type *lpc_last= lpc;
    lpc += lpc_stride;

    if (normalize) {
        for(j=0; j<i; j++)
            r -= lpc_last[j] * autoc[i-j];

        r /= err;
        err *= 1.0 - (r * r);
    }
    if (ref)
        ref[i] = fabs(r);

    lpc[i] = r;
    for(j=0; j < (i+1)>>1; j++) {
        LPC_type f = lpc_last[    j];
        LPC_type b = lpc_last[i-1-j];
        lpc[    j] = f + r * b;
        lpc[i-1-j] = b + r * f;
    }

    if (fail && err < 0)
        return -1;
}



[...]
> Index: libavcodec/lpc.h
> ===================================================================
> --- libavcodec/lpc.h	(revision 15050)
> +++ libavcodec/lpc.h	(working copy)
> @@ -45,4 +45,66 @@
>                        int32_t coefs[][MAX_LPC_ORDER], int *shift, int use_lpc,
>                        int omethod, int max_shift, int zero_shift);
>  
> +
> +#ifdef LPC_USE_DOUBLE
> +#define LPC_type double
> +#else
> +#define LPC_type float
> +#endif
> +
> +/**
> + * Levinson-Durbin recursion.
> + * Produces LPC coefficients from autocorrelation data.
> + */
> +static inline int compute_lpc_coefs(const LPC_type *autoc,
> +                                    int max_order,
> +                                    LPC_type lpc[][MAX_LPC_ORDER],
> +                                    LPC_type *ref,
> +                                    LPC_type lpc_tmp[MAX_LPC_ORDER],
> +                                    int fail, int normalize)
> +{
> +    int i, j;
> +    LPC_type err = autoc[0];
> +
> +    if (fail && (autoc[max_order] == 0 || autoc[0] <= 0))
> +        return -1;
> +
> +    for(i=0; i<max_order; i++) {
> +        LPC_type r;

> +        if (normalize) {
> +            r = -autoc[i+1];
> +
> +            for(j=0; j<i; j++)
> +                r -= lpc_tmp[j] * autoc[i-j];
> +
> +            r /= err;
> +        } else

> +            r = -autoc[i];

This can be factored out of the loop when autoc+1 is passed as argument
instead of autoc for !normalize


> +
> +        if (ref)
> +            ref[i] = fabs(r);
> +

> +        err *= 1.0 - (r * r);

This line can be under if(normalize) above


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Asymptotically faster algorithms should always be preferred if you have
asymptotical amounts of data
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080831/956e9a7f/attachment.pgp>