Merge branch 'cwrs_speedup'
authorJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Mon, 22 Sep 2008 02:33:14 +0000 (22:33 -0400)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Mon, 22 Sep 2008 02:38:43 +0000 (22:38 -0400)
Conflicts:
libcelt/cwrs.c
tests/cwrs32-test.c

1  2 
libcelt/cwrs.c
tests/cwrs32-test.c

diff --cc libcelt/cwrs.c
@@@ -240,22 -286,36 +215,19 @@@ celt_uint32_t ncwrs_u32(int _n,int _m,c
    else{
      celt_uint32_t um1;
      celt_uint32_t n2m1;
-     _u[1]=n2m1=um1=(_m<<1)-1;
-     for(k=2;k<_n;k++){
+     _u[2]=n2m1=um1=(_n<<1)-1;
+     for(k=3;k<len;k++){
        /*U(n,m) = ((2*n-1)*U(n,m-1)-U(n,m-2))/(m-1) + U(n,m-2)*/
-       _u[k]=um2=imusdiv32even(n2m1,um1,um2,k)+um2;
-       if(++k>=_n)break;
-       _u[k]=um1=imusdiv32odd(n2m1,um2,um1,k>>1)+um1;
+       _u[k]=um2=imusdiv32even(n2m1,um1,um2,k-1)+um2;
+       if(++k>=len)break;
+       _u[k]=um1=imusdiv32odd(n2m1,um2,um1,k-1>>1)+um1;
      }
    }
-   ret=1;
-   k=1;
-   do ret+=_u[k];
-   while(++k<_n);
-   return ret<<1;
+   return _u[_m]+_u[_m+1];
  }
  
 -celt_uint64_t ncwrs_u64(int _n,int _m,celt_uint64_t *_u){
 -  int k;
 -  int len;
 -  len=_m+2;
 -  _u[0]=0;
 -  /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
 -  /*If _n==1, _u[i] should be 1 for i>1.*/
 -  celt_assert(_n>=2);
 -  k=1;
 -  do _u[k]=(k<<1)-1;
 -  while(++k<len);
 -  for(k=2;k<_n;k++)unext64(_u+2,_m,(k<<1)+1);
 -  /*TODO: For large _n, an imusdiv64 could make this O(_m) instead of
 -     O(_n*_m), but would require an INV_TABLE twice as large, as well as lots
 -     of 64x64->64 bit multiplies.*/
 -  return _u[_m]+_u[_m+1];
 -}
  
  /*Returns the _i'th combination of _m elements chosen from a set of size _n
     with associated sign bits.
    _y: Returns the vector of pulses.
@@@ -293,6 -345,35 +257,7 @@@ void cwrsi32(int _n,int _m,celt_uint32_
    while(++j<_n);
  }
  
 -/*Returns the _i'th combination of _m elements chosen from a set of size _n
 -   with associated sign bits.
 -  _y: Returns the vector of pulses.
 -  _u: Must contain entries [0..._m+1] of row _n of U() on input.
 -      Its contents will be destructively modified.*/
 -void cwrsi64(int _n,int _m,celt_uint64_t _i,int *_y,celt_uint64_t *_u){
 -  int j;
 -  int k;
 -  celt_assert(_n>0);
 -  j=0;
 -  k=_m;
 -  do{
 -    celt_uint64_t p;
 -    int           s;
 -    int           yj;
 -    p=_u[k+1];
 -    s=_i>=p;
 -    if(s)_i-=p;
 -    yj=k;
 -    p=_u[k];
 -    while(p>_i)p=_u[--k];
 -    _i-=p;
 -    yj-=k;
 -    _y[j]=yj-(yj<<1&-s);
 -    uprev64(_u,k+2,0);
 -  }
 -  while(++j<_n);
 -}
  /*Returns the index of the given combination of _m elements chosen from a set
     of size _n with associated sign bits.
    _y:  The vector of pulses, whose sum of absolute values must be _m.
@@@ -342,15 -446,26 +301,15 @@@ static inline void encode_pulse32(int _
  int get_required_bits(int N, int K, int frac)
  {
     int nbits = 0;
 -   if(fits_in64(N,K))
 +   if(fits_in32(N,K))
     {
 -      VARDECL(celt_uint64_t,u);
 +      VARDECL(celt_uint32_t,u);
        SAVE_STACK;
-       ALLOC(u,N,celt_uint32_t);
 -      ALLOC(u,K+2,celt_uint64_t);
 -      nbits = log2_frac64(ncwrs_u64(N,K,u), frac);
++      ALLOC(u,K+2,celt_uint32_t);
 +      nbits = log2_frac(ncwrs_u32(N,K,u), frac);
        RESTORE_STACK;
     } else {
 -      nbits = log2_frac64(N, frac);
 +      nbits = log2_frac(N, frac);
        nbits += get_required_bits(N/2+1, (K+1)/2, frac);
        nbits += get_required_bits(N/2+1, K/2, frac);
     }
@@@ -21,11 -21,12 +21,11 @@@ int main(int _argc,char **_argv)
        inc=nc/10000;
        if(inc<1)inc=1;
        for(i=0;i<nc;i+=inc){
-         celt_uint32_t u[NMAX>MMAX+2?NMAX:MMAX+2];
+         celt_uint32_t u[MMAX+2];
          int           y[NMAX];
          celt_uint32_t v;
-         memcpy(u,uu,n*sizeof(*u));
-         cwrsi32(n,m,i,nc,y,u);
 -        int           k;
+         memcpy(u,uu,(m+2)*sizeof(*u));
+         cwrsi32(n,m,i,y,u);
          /*printf("%6u of %u:",i,nc);
          for(k=0;k<n;k++)printf(" %+3i",y[k]);
          printf(" ->");*/