Eliminate the loop when decoding the split angle.
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).
diff --git a/libcelt/mathops.c b/libcelt/mathops.c
index 2a9ab5e..3857a9b 100644
--- a/libcelt/mathops.c
+++ b/libcelt/mathops.c
@@ -41,6 +41,33 @@
#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)