[vorbis-dev] LSP optimisations

[Lionel Bonnet]

Here are two optimisations for LSP :
in vorbis_lsp_to_lpc, Ae and Ao are filled with zero when i increase so you
can reduce the j loop, and I replaced qsort in cacm (maybe there are better
algorithms, but it's already much faster than qsort on my mac)

void vorbis_lsp_to_lpc(double *lsp,double *lpc,int m){
  int i,j,m2=m/2;
  double *O=alloca(sizeof(double)*m2);
  double *E=alloca(sizeof(double)*m2);
  double A;
  double *Ae=alloca(sizeof(double)*(m2+1));
  double *Ao=alloca(sizeof(double)*(m2+1));
  double B;
  double *Be=alloca(sizeof(double)*(m2));
  double *Bo=alloca(sizeof(double)*(m2));
  double temp;

  for(i=0;i<m2;i++){
    O[i]=-2.*cos(*lsp++);    /* even/odd roots setup */
    E[i]=-2.*cos(*lsp++);
    Ae[i]=0.;                /* set up impulse response */
    Ao[i]=1.;
    Be[i]=0.;
    Bo[i]=1.;
  }

  Ao[i]=1.;
  Ae[i]=1.;

  /* run impulse response */
  for(i=0;i<m;i++){
    A=B=0.;
    for(j=(i>>1);j<m2;j++){     /*Ao and Ae are progressively */
      temp=O[j]*Ao[j]+Ae[j];    /*filled with zeros*/
      Ae[j]=Ao[j];
      Ao[j]=A;
      A+=temp;

      temp=E[j]*Bo[j]+Be[j];
      Be[j]=Bo[j];
      Bo[j]=B;
      B+=temp;
    }
    *lpc++=(A+Ao[j]+B-Ae[j])/2;
    Ao[j]=A;
    Ae[j]=B;
  }
}

tatic void cacm283(double *a,int ord,double *r){
  int i, k;
  double val, p, delta, error;
  double rooti;

  for(i=0; i<ord;i++) r[i] = 2.0 * (i+0.5) / ord - 1.0;

  for(error=1 ; error > 1.e-12; ) {
    error = 0;
    for( i=0; i<ord; i++) {  /* Update each point. */
      rooti = r[i];
      val = a[ord];
      p = a[ord];
      for(k=ord-1; k>= 0; k--) {
 val = val * rooti + a[k];
 if (k != i) p *= rooti - r[k];
      }
      delta = val/p;
      r[i] -= delta;

      error += delta*delta;
    }
  }

 {
  int permutation = 1, limit = ord - 1;
  while (permutation > 0)
  {
   permutation = 0;
   for (i = 0; i < limit; i++)
   {
    if (r[i+1] > r[i])
    {
     val = r[i];
     r[i] = r[i+1];
     r[i+1] = val;
     permutation++;
    }
   }
   limit--;
  }
 }

}

 -- Lionel

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/