CWRS clean-ups and optimizations.

Adds specialized O(N*log(K)) versions of cwrsi() and O(N) versions of icwrs()
 for N={3,4,5}, which allows them to operate all the way up to the theoretical
 pulse limit without serious performance degredation.
Also substantially reduces the computation time and stack usage of
 get_required_bits().
On x86-64, this gives a 2% speed-up for 256 sample frames, and almost a 16%
 speed-up for 64 sample frames.

2 files changed, 132 insertions, 65 deletions

diff --git a/tests/cwrs32-test.c b/tests/cwrs32-test.c
index 22f40ea..7332ca5 100644
--- a/tests/cwrs32-test.c
+++ b/tests/cwrs32-test.c
@@ -3,52 +3,169 @@
 #endif
 
 #include <stdio.h>
-#include "cwrs.h"
 #include <string.h>
 
-#include "../libcelt/cwrs.c"
 #include "../libcelt/rangeenc.c"
 #include "../libcelt/rangedec.c"
 #include "../libcelt/entenc.c"
 #include "../libcelt/entdec.c"
 #include "../libcelt/entcode.c"
+#include "../libcelt/cwrs.c"
+
+#define NMAX (14)
+#define KMAX (32767)
+
+static const int kmax[15]={
+  32767,32767,32767,32767, 1172,
+    238,   95,   53,   36,   27,
+     22,   18,   16,   15,   13
+};
 
-#define NMAX (10)
-#define MMAX (9)
 
 int main(int _argc,char **_argv){
   int n;
   for(n=2;n<=NMAX;n++){
-    int m;
-    for(m=1;m<=MMAX;m++){
-      celt_uint32_t uu[MMAX+2];
+    int dk;
+    int k;
+    dk=kmax[n]>7?kmax[n]/7:1;
+    k=1-dk;
+    do{
+      celt_uint32_t uu[KMAX+2U];
       celt_uint32_t inc;
       celt_uint32_t nc;
       celt_uint32_t i;
-      nc=ncwrs_u32(n,m,uu);
+      k=kmax[n]-dk<k?kmax[n]:k+dk;
+      printf("Testing CWRS with N=%i, K=%i...\n",n,k);
+      nc=ncwrs_urow(n,k,uu);
       inc=nc/10000;
       if(inc<1)inc=1;
       for(i=0;i<nc;i+=inc){
-        celt_uint32_t u[MMAX+2];
+        celt_uint32_t u[KMAX+2U];
         int           y[NMAX];
+        int           yy[5];
         celt_uint32_t v;
-        memcpy(u,uu,(m+2)*sizeof(*u));
-        cwrsi32(n,m,i,y,u);
+        celt_uint32_t ii;
+        int           kk;
+        int           j;
+        memcpy(u,uu,(k+2U)*sizeof(*u));
+        cwrsi(n,k,i,y,u);
         /*printf("%6u of %u:",i,nc);
-        for(k=0;k<n;k++)printf(" %+3i",y[k]);
+        for(j=0;j<n;j++)printf(" %+3i",y[j]);
         printf(" ->");*/
-        if(icwrs32(n,m,&v,y,u)!=i){
-          fprintf(stderr,"Combination-index mismatch.\n");
+        ii=icwrs(n,k,&v,y,u);
+        if(ii!=i){
+          fprintf(stderr,"Combination-index mismatch (%lu!=%lu).\n",
+           (long)ii,(long)i);
           return 1;
         }
         if(v!=nc){
-          fprintf(stderr,"Combination count mismatch.\n");
+          fprintf(stderr,"Combination count mismatch (%lu!=%lu).\n",
+           (long)v,(long)nc);
           return 2;
         }
+        if(n==2){
+          cwrsi2(k,i,yy);
+          for(j=0;j<2;j++)if(yy[j]!=y[j]){
+            fprintf(stderr,"N=2 pulse vector mismatch ({%i,%i}!={%i,%i}).\n",
+             yy[0],yy[1],y[0],y[1]);
+            return 3;
+          }
+          ii=icwrs2(yy,&kk);
+          if(ii!=i){
+            fprintf(stderr,"N=2 combination-index mismatch (%lu!=%lu).\n",
+             (long)ii,(long)i);
+            return 4;
+          }
+          if(kk!=k){
+            fprintf(stderr,"N=2 pulse count mismatch (%i,%i).\n",kk,k);
+            return 5;
+          }
+          v=ncwrs2(k);
+          if(v!=nc){
+            fprintf(stderr,"N=2 combination count mismatch (%lu,%lu).\n",
+             (long)v,(long)nc);
+            return 6;
+          }
+        }
+        else if(n==3){
+          cwrsi3(k,i,yy);
+          for(j=0;j<3;j++)if(yy[j]!=y[j]){
+            fprintf(stderr,"N=3 pulse vector mismatch "
+             "({%i,%i,%i}!={%i,%i,%i}).\n",yy[0],yy[1],yy[2],y[0],y[1],y[2]);
+            return 7;
+          }
+          ii=icwrs3(yy,&kk);
+          if(ii!=i){
+            fprintf(stderr,"N=3 combination-index mismatch (%lu!=%lu).\n",
+             (long)ii,(long)i);
+            return 8;
+          }
+          if(kk!=k){
+            fprintf(stderr,"N=3 pulse count mismatch (%i!=%i).\n",kk,k);
+            return 9;
+          }
+          v=ncwrs3(k);
+          if(v!=nc){
+            fprintf(stderr,"N=3 combination count mismatch (%lu!=%lu).\n",
+             (long)v,(long)nc);
+            return 10;
+          }
+        }
+        else if(n==4){
+          cwrsi4(k,i,yy);
+          for(j=0;j<4;j++)if(yy[j]!=y[j]){
+            fprintf(stderr,"N=4 pulse vector mismatch "
+             "({%i,%i,%i,%i}!={%i,%i,%i,%i}.\n",
+             yy[0],yy[1],yy[2],yy[3],y[0],y[1],y[2],y[3]);
+            return 11;
+          }
+          ii=icwrs4(yy,&kk);
+          if(ii!=i){
+            fprintf(stderr,"N=4 combination-index mismatch (%lu!=%lu).\n",
+             (long)ii,(long)i);
+            return 12;
+          }
+          if(kk!=k){
+            fprintf(stderr,"N=4 pulse count mismatch (%i!=%i).\n",kk,k);
+            return 13;
+          }
+          v=ncwrs4(k);
+          if(v!=nc){
+            fprintf(stderr,"N=4 combination count mismatch (%lu!=%lu).\n",
+             (long)v,(long)nc);
+            return 14;
+          }
+        }
+        else if(n==5){
+          cwrsi5(k,i,yy);
+          for(j=0;j<5;j++)if(yy[j]!=y[j]){
+            fprintf(stderr,"N=5 pulse vector mismatch "
+             "({%i,%i,%i,%i,%i}!={%i,%i,%i,%i,%i}).\n",
+             yy[0],yy[1],yy[2],yy[3],yy[4],y[0],y[1],y[2],y[3],y[4]);
+            return 15;
+          }
+          ii=icwrs5(yy,&kk);
+          if(ii!=i){
+            fprintf(stderr,"N=5 combination-index mismatch (%lu!=%lu).\n",
+             (long)ii,(long)i);
+            return 16;
+          }
+          if(kk!=k){
+            fprintf(stderr,"N=5 pulse count mismatch (%i!=%i).\n",kk,k);
+            return 17;
+          }
+          v=ncwrs5(k);
+          if(v!=nc){
+            fprintf(stderr,"N=5 combination count mismatch (%lu!=%lu).\n",
+             (long)v,(long)nc);
+            return 18;
+          }
+        }
         /*printf(" %6u\n",i);*/
       }
       /*printf("\n");*/
     }
+    while(k<kmax[n]);
   }
   return 0;
 }
diff --git a/tests/cwrs64-test.c b/tests/cwrs64-test.c
deleted file mode 100644
index 548fa22..0000000
--- a/tests/cwrs64-test.c
+++ /dev/null
@@ -1,50 +0,0 @@
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include <stdio.h>
-#include "cwrs.h"
-#include <string.h>
-
-#define NMAX (32)
-#define MMAX (16)
-
-int main(int _argc,char **_argv){
-  int n;
-  for(n=2;n<=NMAX;n+=3){
-    int m;
-    for(m=1;m<=MMAX;m++){
-      celt_uint64_t uu[MMAX+2];
-      celt_uint64_t inc;
-      celt_uint64_t nc;
-      celt_uint64_t i;
-      nc=ncwrs_u64(n,m,uu);
-      /*Testing all cases just wouldn't work!*/
-      inc=nc/1000;
-      if(inc<1)inc=1;
-      /*printf("%d/%d: %llu",n,m, nc);*/
-      for(i=0;i<nc;i+=inc){
-        celt_uint64_t u[MMAX+2];
-        int           y[NMAX];
-        celt_uint64_t v;
-        int           k;
-        memcpy(u,uu,(m+2)*sizeof(*u));
-        cwrsi64(n,m,i,y,u);
-        /*printf("%llu of %llu:",i,nc);
-        for(k=0;k<n;k++)printf(" %+3i",y[k]);
-        printf(" ->");*/
-        if(icwrs64(n,m,&v,y,u)!=i){
-          fprintf(stderr,"Combination-index mismatch.\n");
-          return 1;
-        }
-        if(v!=nc){
-          fprintf(stderr,"Combination count mismatch.\n");
-          return 2;
-        }
-        /*printf(" %6llu\n",i);*/
-      }
-      /*printf("\n");*/
-    }
-  }
-  return 0;
-}