author Timothy B. Terriberry Tue, 27 Jul 2010 22:09:51 +0000 (15:09 -0700) committer Jean-Marc Valin Tue, 27 Jul 2010 22:20:16 +0000 (00:20 +0200)
Use a closed-form formula for the search instead.
This requires an integer sqrt, so it is not actually closed-form,
but the number of iterations is O(qb) instead of O(2**qb).

 libcelt/bands.c patch | blob | history libcelt/cwrs.c patch | blob | history libcelt/mathops.c patch | blob | history libcelt/mathops.h patch | blob | history

index 11e7190..51652cc 100644 (file)
@@ -664,21 +664,23 @@ static void quant_band(int encode, const CELTMode *m, int i, celt_norm *X, celt_
ec_encode((ec_enc*)ec, fl, fl+fs, ft);
} else {
int fl=0;
-               int j, fm;
+               int fm;
fm = ec_decode((ec_dec*)ec, ft);
-               j=0;
-               while (1)
+
+               if (fm < ((1<<qb>>1)*((1<<qb>>1) + 1)>>1))
+               {
+                  itheta = (isqrt32(8*(celt_uint32)fm + 1) - 1)>>1;
+                  fs = itheta + 1;
+                  fl = itheta*(itheta + 1)>>1;
+               }
+               else
{
-                  if (fm < fl+fs)
-                     break;
-                  fl+=fs;
-                  if (j<(1<<qb>>1))
-                     fs++;
-                  else
-                     fs--;
-                  j++;
+                  itheta = (2*((1<<qb) + 1)
+                   - isqrt32(8*(celt_uint32)(ft - fm - 1) + 1))>>1;
+                  fs = (1<<qb) + 1 - itheta;
+                  fl = ft - (((1<<qb) + 1 - itheta)*((1<<qb) + 2 - itheta)>>1);
}
-               itheta = j;
+
ec_dec_update((ec_dec*)ec, fl, fl+fs, ft);
}
qalloc = log2_frac(ft,BITRES) - log2_frac(fs,BITRES) + 1;
index 0c07709..2d9975c 100644 (file)
@@ -148,33 +148,6 @@ static inline celt_uint32 imusdiv32even(celt_uint32 _a,celt_uint32 _b,
}

-/*Compute floor(sqrt(_val)) with exact arithmetic.
-  This has been tested on all possible 32-bit inputs.*/
-static unsigned isqrt32(celt_uint32 _val){
-  unsigned b;
-  unsigned g;
-  int      bshift;
-  /*Uses the second method from
-     http://www.azillionmonkeys.com/qed/sqroot.html
-    The main idea is to search for the largest binary digit b such that
-     (g+b)*(g+b) <= _val, and add it to the solution g.*/
-  g=0;
-  bshift=EC_ILOG(_val)-1>>1;
-  b=1U<<bshift;
-  do{
-    celt_uint32 t;
-    t=((celt_uint32)g<<1)+b<<bshift;
-    if(t<=_val){
-      g+=b;
-      _val-=t;
-    }
-    b>>=1;
-    bshift--;
-  }
-  while(bshift>=0);
-  return g;
-}
-
#endif /* SMALL_FOOTPRINT */

/*Although derived separately, the pulse vector coding scheme is equivalent to
index 2a9ab5e..3857a9b 100644 (file)

#include "mathops.h"

+/*Compute floor(sqrt(_val)) with exact arithmetic.
+  This has been tested on all possible 32-bit inputs.*/
+unsigned isqrt32(celt_uint32 _val){
+  unsigned b;
+  unsigned g;
+  int      bshift;
+  /*Uses the second method from
+     http://www.azillionmonkeys.com/qed/sqroot.html
+    The main idea is to search for the largest binary digit b such that
+     (g+b)*(g+b) <= _val, and add it to the solution g.*/
+  g=0;
+  bshift=EC_ILOG(_val)-1>>1;
+  b=1U<<bshift;
+  do{
+    celt_uint32 t;
+    t=((celt_uint32)g<<1)+b<<bshift;
+    if(t<=_val){
+      g+=b;
+      _val-=t;
+    }
+    b>>=1;
+    bshift--;
+  }
+  while(bshift>=0);
+  return g;
+}
+
#ifdef FIXED_POINT

celt_word32 frac_div32(celt_word32 a, celt_word32 b)
index 224857d..8717ca9 100644 (file)
@@ -45,6 +45,7 @@
/* Multiplies two 16-bit fractional values. Bit-exactness of this macro is important */
#define FRAC_MUL16(a,b) ((16384+((celt_int32)(celt_int16)(a)*(celt_int16)(b)))>>15)

+unsigned isqrt32(celt_uint32 _val);

#ifndef FIXED_POINT