nuclear@0: /********************************************************************
nuclear@0:  *                                                                  *
nuclear@0:  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
nuclear@0:  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
nuclear@0:  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
nuclear@0:  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
nuclear@0:  *                                                                  *
nuclear@0:  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009             *
nuclear@0:  * by the Xiph.Org Foundation http://www.xiph.org/                  *
nuclear@0:  *                                                                  *
nuclear@0:  ********************************************************************
nuclear@0: 
nuclear@0:   function: LPC low level routines
nuclear@0:   last mod: $Id: lpc.c 16227 2009-07-08 06:58:46Z xiphmont $
nuclear@0: 
nuclear@0:  ********************************************************************/
nuclear@0: 
nuclear@0: /* Some of these routines (autocorrelator, LPC coefficient estimator)
nuclear@0:    are derived from code written by Jutta Degener and Carsten Bormann;
nuclear@0:    thus we include their copyright below.  The entirety of this file
nuclear@0:    is freely redistributable on the condition that both of these
nuclear@0:    copyright notices are preserved without modification.  */
nuclear@0: 
nuclear@0: /* Preserved Copyright: *********************************************/
nuclear@0: 
nuclear@0: /* Copyright 1992, 1993, 1994 by Jutta Degener and Carsten Bormann,
nuclear@0: Technische Universita"t Berlin
nuclear@0: 
nuclear@0: Any use of this software is permitted provided that this notice is not
nuclear@0: removed and that neither the authors nor the Technische Universita"t
nuclear@0: Berlin are deemed to have made any representations as to the
nuclear@0: suitability of this software for any purpose nor are held responsible
nuclear@0: for any defects of this software. THERE IS ABSOLUTELY NO WARRANTY FOR
nuclear@0: THIS SOFTWARE.
nuclear@0: 
nuclear@0: As a matter of courtesy, the authors request to be informed about uses
nuclear@0: this software has found, about bugs in this software, and about any
nuclear@0: improvements that may be of general interest.
nuclear@0: 
nuclear@0: Berlin, 28.11.1994
nuclear@0: Jutta Degener
nuclear@0: Carsten Bormann
nuclear@0: 
nuclear@0: *********************************************************************/
nuclear@0: 
nuclear@0: #include <stdlib.h>
nuclear@0: #include <string.h>
nuclear@0: #include <math.h>
nuclear@0: #include "os.h"
nuclear@0: #include "smallft.h"
nuclear@0: #include "lpc.h"
nuclear@0: #include "scales.h"
nuclear@0: #include "misc.h"
nuclear@0: 
nuclear@0: /* Autocorrelation LPC coeff generation algorithm invented by
nuclear@0:    N. Levinson in 1947, modified by J. Durbin in 1959. */
nuclear@0: 
nuclear@0: /* Input : n elements of time doamin data
nuclear@0:    Output: m lpc coefficients, excitation energy */
nuclear@0: 
nuclear@0: float vorbis_lpc_from_data(float *data,float *lpci,int n,int m){
nuclear@0:   double *aut=alloca(sizeof(*aut)*(m+1));
nuclear@0:   double *lpc=alloca(sizeof(*lpc)*(m));
nuclear@0:   double error;
nuclear@0:   double epsilon;
nuclear@0:   int i,j;
nuclear@0: 
nuclear@0:   /* autocorrelation, p+1 lag coefficients */
nuclear@0:   j=m+1;
nuclear@0:   while(j--){
nuclear@0:     double d=0; /* double needed for accumulator depth */
nuclear@0:     for(i=j;i<n;i++)d+=(double)data[i]*data[i-j];
nuclear@0:     aut[j]=d;
nuclear@0:   }
nuclear@0: 
nuclear@0:   /* Generate lpc coefficients from autocorr values */
nuclear@0: 
nuclear@0:   /* set our noise floor to about -100dB */
nuclear@0:   error=aut[0] * (1. + 1e-10);
nuclear@0:   epsilon=1e-9*aut[0]+1e-10;
nuclear@0: 
nuclear@0:   for(i=0;i<m;i++){
nuclear@0:     double r= -aut[i+1];
nuclear@0: 
nuclear@0:     if(error<epsilon){
nuclear@0:       memset(lpc+i,0,(m-i)*sizeof(*lpc));
nuclear@0:       goto done;
nuclear@0:     }
nuclear@0: 
nuclear@0:     /* Sum up this iteration's reflection coefficient; note that in
nuclear@0:        Vorbis we don't save it.  If anyone wants to recycle this code
nuclear@0:        and needs reflection coefficients, save the results of 'r' from
nuclear@0:        each iteration. */
nuclear@0: 
nuclear@0:     for(j=0;j<i;j++)r-=lpc[j]*aut[i-j];
nuclear@0:     r/=error;
nuclear@0: 
nuclear@0:     /* Update LPC coefficients and total error */
nuclear@0: 
nuclear@0:     lpc[i]=r;
nuclear@0:     for(j=0;j<i/2;j++){
nuclear@0:       double tmp=lpc[j];
nuclear@0: 
nuclear@0:       lpc[j]+=r*lpc[i-1-j];
nuclear@0:       lpc[i-1-j]+=r*tmp;
nuclear@0:     }
nuclear@0:     if(i&1)lpc[j]+=lpc[j]*r;
nuclear@0: 
nuclear@0:     error*=1.-r*r;
nuclear@0: 
nuclear@0:   }
nuclear@0: 
nuclear@0:  done:
nuclear@0: 
nuclear@0:   /* slightly damp the filter */
nuclear@0:   {
nuclear@0:     double g = .99;
nuclear@0:     double damp = g;
nuclear@0:     for(j=0;j<m;j++){
nuclear@0:       lpc[j]*=damp;
nuclear@0:       damp*=g;
nuclear@0:     }
nuclear@0:   }
nuclear@0: 
nuclear@0:   for(j=0;j<m;j++)lpci[j]=(float)lpc[j];
nuclear@0: 
nuclear@0:   /* we need the error value to know how big an impulse to hit the
nuclear@0:      filter with later */
nuclear@0: 
nuclear@0:   return error;
nuclear@0: }
nuclear@0: 
nuclear@0: void vorbis_lpc_predict(float *coeff,float *prime,int m,
nuclear@0:                      float *data,long n){
nuclear@0: 
nuclear@0:   /* in: coeff[0...m-1] LPC coefficients
nuclear@0:          prime[0...m-1] initial values (allocated size of n+m-1)
nuclear@0:     out: data[0...n-1] data samples */
nuclear@0: 
nuclear@0:   long i,j,o,p;
nuclear@0:   float y;
nuclear@0:   float *work=alloca(sizeof(*work)*(m+n));
nuclear@0: 
nuclear@0:   if(!prime)
nuclear@0:     for(i=0;i<m;i++)
nuclear@0:       work[i]=0.f;
nuclear@0:   else
nuclear@0:     for(i=0;i<m;i++)
nuclear@0:       work[i]=prime[i];
nuclear@0: 
nuclear@0:   for(i=0;i<n;i++){
nuclear@0:     y=0;
nuclear@0:     o=i;
nuclear@0:     p=m;
nuclear@0:     for(j=0;j<m;j++)
nuclear@0:       y-=work[o++]*coeff[--p];
nuclear@0: 
nuclear@0:     data[i]=work[o]=y;
nuclear@0:   }
nuclear@0: }