Move skip coding into interp_bits2pulses().
[opus.git] / libcelt / cwrs.c
index 4b0f36a..843dcd5 100644 (file)
@@ -1,5 +1,7 @@
-/* (C) 2007-2008 Timothy B. Terriberry
-   (C) 2008 Jean-Marc Valin */
+/* Copyright (c) 2007-2008 CSIRO
+   Copyright (c) 2007-2009 Xiph.Org Foundation
+   Copyright (c) 2007-2009 Timothy B. Terriberry
+   Written by Timothy B. Terriberry and Jean-Marc Valin */
 /*
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
 /*
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
@@ -71,10 +73,13 @@ int log2_frac(ec_uint32 val, int frac)
   else return l-1<<frac;
 }
 
   else return l-1<<frac;
 }
 
+#ifndef SMALL_FOOTPRINT
+
+
 #define MASK32 (0xFFFFFFFF)
 
 /*INV_TABLE[i] holds the multiplicative inverse of (2*i+1) mod 2**32.*/
 #define MASK32 (0xFFFFFFFF)
 
 /*INV_TABLE[i] holds the multiplicative inverse of (2*i+1) mod 2**32.*/
-static const celt_uint32_t INV_TABLE[128]={
+static const celt_uint32 INV_TABLE[64]={
   0x00000001,0xAAAAAAAB,0xCCCCCCCD,0xB6DB6DB7,
   0x38E38E39,0xBA2E8BA3,0xC4EC4EC5,0xEEEEEEEF,
   0xF0F0F0F1,0x286BCA1B,0x3CF3CF3D,0xE9BD37A7,
   0x00000001,0xAAAAAAAB,0xCCCCCCCD,0xB6DB6DB7,
   0x38E38E39,0xBA2E8BA3,0xC4EC4EC5,0xEEEEEEEF,
   0xF0F0F0F1,0x286BCA1B,0x3CF3CF3D,0xE9BD37A7,
@@ -91,6 +96,7 @@ static const celt_uint32_t INV_TABLE[128]={
   0xD8FD8FD9,0x8D28AC43,0xDA6C0965,0xDB195E8F,
   0x0FDBC091,0x61F2A4BB,0xDCFDCFDD,0x46FDD947,
   0x56BE69C9,0xEB2FDEB3,0x26E978D5,0xEFDFBF7F,
   0xD8FD8FD9,0x8D28AC43,0xDA6C0965,0xDB195E8F,
   0x0FDBC091,0x61F2A4BB,0xDCFDCFDD,0x46FDD947,
   0x56BE69C9,0xEB2FDEB3,0x26E978D5,0xEFDFBF7F,
+  /*
   0x0FE03F81,0xC9484E2B,0xE133F84D,0xE1A8C537,
   0x077975B9,0x70586723,0xCD29C245,0xFAA11E6F,
   0x0FE3C071,0x08B51D9B,0x8CE2CABD,0xBF937F27,
   0x0FE03F81,0xC9484E2B,0xE133F84D,0xE1A8C537,
   0x077975B9,0x70586723,0xCD29C245,0xFAA11E6F,
   0x0FE3C071,0x08B51D9B,0x8CE2CABD,0xBF937F27,
@@ -106,15 +112,15 @@ static const celt_uint32_t INV_TABLE[128]={
   0x87654321,0x9BA144CB,0x478BBCED,0xBFB912D7,
   0x1FDCD759,0x14B2A7C3,0xCB125CE5,0x437B2E0F,
   0x10FEF011,0xD2B3183B,0x386CAB5D,0xEF6AC0C7,
   0x87654321,0x9BA144CB,0x478BBCED,0xBFB912D7,
   0x1FDCD759,0x14B2A7C3,0xCB125CE5,0x437B2E0F,
   0x10FEF011,0xD2B3183B,0x386CAB5D,0xEF6AC0C7,
-  0x0E64C149,0x9A020A33,0xE6B41C55,0xFEFEFEFF
+  0x0E64C149,0x9A020A33,0xE6B41C55,0xFEFEFEFF*/
 };
 
 /*Computes (_a*_b-_c)/(2*_d+1) when the quotient is known to be exact.
   _a, _b, _c, and _d may be arbitrary so long as the arbitrary precision result
    fits in 32 bits, but currently the table for multiplicative inverses is only
    valid for _d<128.*/
 };
 
 /*Computes (_a*_b-_c)/(2*_d+1) when the quotient is known to be exact.
   _a, _b, _c, and _d may be arbitrary so long as the arbitrary precision result
    fits in 32 bits, but currently the table for multiplicative inverses is only
    valid for _d<128.*/
-static inline celt_uint32_t imusdiv32odd(celt_uint32_t _a,celt_uint32_t _b,
- celt_uint32_t _c,int _d){
+static inline celt_uint32 imusdiv32odd(celt_uint32 _a,celt_uint32 _b,
+ celt_uint32 _c,int _d){
   return (_a*_b-_c)*INV_TABLE[_d]&MASK32;
 }
 
   return (_a*_b-_c)*INV_TABLE[_d]&MASK32;
 }
 
@@ -125,9 +131,9 @@ static inline celt_uint32_t imusdiv32odd(celt_uint32_t _a,celt_uint32_t _b,
    table for multiplicative inverses is only valid for _d<=256).
   _b and _c may be arbitrary so long as the arbitrary precision reuslt fits in
    32 bits.*/
    table for multiplicative inverses is only valid for _d<=256).
   _b and _c may be arbitrary so long as the arbitrary precision reuslt fits in
    32 bits.*/
-static inline celt_uint32_t imusdiv32even(celt_uint32_t _a,celt_uint32_t _b,
- celt_uint32_t _c,int _d){
-  celt_uint32_t inv;
+static inline celt_uint32 imusdiv32even(celt_uint32 _a,celt_uint32 _b,
+ celt_uint32 _c,int _d){
+  celt_uint32 inv;
   int           mask;
   int           shift;
   int           one;
   int           mask;
   int           shift;
   int           one;
@@ -142,61 +148,7 @@ static inline celt_uint32_t imusdiv32even(celt_uint32_t _a,celt_uint32_t _b,
    (_a*(_b&mask)+one-(_c&mask)>>shift)-1)*inv&MASK32;
 }
 
    (_a*(_b&mask)+one-(_c&mask)>>shift)-1)*inv&MASK32;
 }
 
-/*Compute floor(sqrt(_val)) with exact arithmetic.
-  This has been tested on all possible 32-bit inputs.*/
-static unsigned isqrt32(celt_uint32_t _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;
-  for(;bshift>=0;bshift--){
-    celt_uint32_t t;
-    t=((celt_uint32_t)g<<1)+b<<bshift;
-    if(t<=_val){
-      g+=b;
-      _val-=t;
-    }
-    b>>=1;
-  }
-  return g;
-}
-
-/*Compute floor(sqrt(_val)) with exact arithmetic.
-  This has been tested on all possible 36-bit inputs.*/
-static celt_uint32_t isqrt36(celt_uint64_t _val){
-  celt_uint32_t val32;
-  celt_uint32_t b;
-  celt_uint32_t g;
-  int           bshift;
-  g=0;
-  b=0x20000;
-  for(bshift=18;bshift-->13;){
-    celt_uint64_t t;
-    t=((celt_uint64_t)g<<1)+b<<bshift;
-    if(t<=_val){
-      g+=b;
-      _val-=t;
-    }
-    b>>=1;
-  }
-  val32=(celt_uint32_t)_val;
-  for(;bshift>=0;bshift--){
-    celt_uint32_t t;
-    t=(g<<1)+b<<bshift;
-    if(t<=val32){
-      g+=b;
-      val32-=t;
-    }
-    b>>=1;
-  }
-  return g;
-}
+#endif /* SMALL_FOOTPRINT */
 
 /*Although derived separately, the pulse vector coding scheme is equivalent to
    a Pyramid Vector Quantizer \cite{Fis86}.
 
 /*Although derived separately, the pulse vector coding scheme is equivalent to
    a Pyramid Vector Quantizer \cite{Fis86}.
@@ -317,26 +269,7 @@ static celt_uint32_t isqrt36(celt_uint64_t _val){
     year=1986
   }*/
 
     year=1986
   }*/
 
-/*Determines if V(N,K) fits in a 32-bit unsigned integer.
-  N and K are themselves limited to 15 bits.*/
-int fits_in32(int _n, int _k)
-{
-   static const celt_int16_t maxN[15] = {
-      32767, 32767, 32767, 1476, 283, 109,  60,  40,
-       29,  24,  20,  18,  16,  14,  13};
-   static const celt_int16_t maxK[15] = {
-      32767, 32767, 32767, 32767, 1172, 238,  95,  53,
-       36,  27,  22,  18,  16,  15,  13};
-   if (_n>=14)
-   {
-      if (_k>=14)
-         return 0;
-      else
-         return _n <= maxN[_k];
-   } else {
-      return _k <= maxK[_n];
-   }
-}
+#ifndef SMALL_FOOTPRINT
 
 /*Compute U(1,_k).*/
 static inline unsigned ucwrs1(int _k){
 
 /*Compute U(1,_k).*/
 static inline unsigned ucwrs1(int _k){
@@ -355,46 +288,48 @@ static inline unsigned ucwrs2(unsigned _k){
 }
 
 /*Compute V(2,_k).*/
 }
 
 /*Compute V(2,_k).*/
-static inline celt_uint32_t ncwrs2(int _k){
-  return _k?4*(celt_uint32_t)_k:1;
+static inline celt_uint32 ncwrs2(int _k){
+  return _k?4*(celt_uint32)_k:1;
 }
 
 /*Compute U(3,_k).
   Note that this may be called with _k=32768 (maxK[3]+1).*/
 }
 
 /*Compute U(3,_k).
   Note that this may be called with _k=32768 (maxK[3]+1).*/
-static inline celt_uint32_t ucwrs3(unsigned _k){
-  return _k?(2*(celt_uint32_t)_k-2)*_k+1:0;
+static inline celt_uint32 ucwrs3(unsigned _k){
+  return _k?(2*(celt_uint32)_k-2)*_k+1:0;
 }
 
 /*Compute V(3,_k).*/
 }
 
 /*Compute V(3,_k).*/
-static inline celt_uint32_t ncwrs3(int _k){
-  return _k?2*(2*(unsigned)_k*(celt_uint32_t)_k+1):1;
+static inline celt_uint32 ncwrs3(int _k){
+  return _k?2*(2*(unsigned)_k*(celt_uint32)_k+1):1;
 }
 
 /*Compute U(4,_k).*/
 }
 
 /*Compute U(4,_k).*/
-static inline celt_uint32_t ucwrs4(int _k){
-  return _k?imusdiv32odd(2*_k,(2*_k-3)*(celt_uint32_t)_k+4,3,1):0;
+static inline celt_uint32 ucwrs4(int _k){
+  return _k?imusdiv32odd(2*_k,(2*_k-3)*(celt_uint32)_k+4,3,1):0;
 }
 
 /*Compute V(4,_k).*/
 }
 
 /*Compute V(4,_k).*/
-static inline celt_uint32_t ncwrs4(int _k){
-  return _k?((_k*(celt_uint32_t)_k+2)*_k)/3<<3:1;
+static inline celt_uint32 ncwrs4(int _k){
+  return _k?((_k*(celt_uint32)_k+2)*_k)/3<<3:1;
 }
 
 /*Compute U(5,_k).*/
 }
 
 /*Compute U(5,_k).*/
-static inline celt_uint32_t ucwrs5(int _k){
-  return _k?(((((_k-2)*(unsigned)_k+5)*(celt_uint32_t)_k-4)*_k)/3<<1)+1:0;
+static inline celt_uint32 ucwrs5(int _k){
+  return _k?(((((_k-2)*(unsigned)_k+5)*(celt_uint32)_k-4)*_k)/3<<1)+1:0;
 }
 
 /*Compute V(5,_k).*/
 }
 
 /*Compute V(5,_k).*/
-static inline celt_uint32_t ncwrs5(int _k){
-  return _k?(((_k*(unsigned)_k+5)*(celt_uint32_t)_k*_k)/3<<2)+2:1;
+static inline celt_uint32 ncwrs5(int _k){
+  return _k?(((_k*(unsigned)_k+5)*(celt_uint32)_k*_k)/3<<2)+2:1;
 }
 
 }
 
+#endif /* SMALL_FOOTPRINT */
+
 /*Computes the next row/column of any recurrence that obeys the relation
    u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
   _ui0 is the base case for the new row/column.*/
 /*Computes the next row/column of any recurrence that obeys the relation
    u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
   _ui0 is the base case for the new row/column.*/
-static inline void unext(celt_uint32_t *_ui,unsigned _len,celt_uint32_t _ui0){
-  celt_uint32_t ui1;
+static inline void unext(celt_uint32 *_ui,unsigned _len,celt_uint32 _ui0){
+  celt_uint32 ui1;
   unsigned      j;
   /*This do-while will overrun the array if we don't have storage for at least
      2 values.*/
   unsigned      j;
   /*This do-while will overrun the array if we don't have storage for at least
      2 values.*/
@@ -409,8 +344,8 @@ static inline void unext(celt_uint32_t *_ui,unsigned _len,celt_uint32_t _ui0){
 /*Computes the previous row/column of any recurrence that obeys the relation
    u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
   _ui0 is the base case for the new row/column.*/
 /*Computes the previous row/column of any recurrence that obeys the relation
    u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
   _ui0 is the base case for the new row/column.*/
-static inline void uprev(celt_uint32_t *_ui,unsigned _n,celt_uint32_t _ui0){
-  celt_uint32_t ui1;
+static inline void uprev(celt_uint32 *_ui,unsigned _n,celt_uint32 _ui0){
+  celt_uint32 ui1;
   unsigned      j;
   /*This do-while will overrun the array if we don't have storage for at least
      2 values.*/
   unsigned      j;
   /*This do-while will overrun the array if we don't have storage for at least
      2 values.*/
@@ -424,8 +359,8 @@ static inline void uprev(celt_uint32_t *_ui,unsigned _n,celt_uint32_t _ui0){
 
 /*Compute V(_n,_k), as well as U(_n,0..._k+1).
   _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
 
 /*Compute V(_n,_k), as well as U(_n,0..._k+1).
   _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
-static celt_uint32_t ncwrs_urow(unsigned _n,unsigned _k,celt_uint32_t *_u){
-  celt_uint32_t um2;
+static celt_uint32 ncwrs_urow(unsigned _n,unsigned _k,celt_uint32 *_u){
+  celt_uint32 um2;
   unsigned      len;
   unsigned      k;
   len=_k+2;
   unsigned      len;
   unsigned      k;
   len=_k+2;
@@ -433,7 +368,10 @@ static celt_uint32_t ncwrs_urow(unsigned _n,unsigned _k,celt_uint32_t *_u){
   celt_assert(len>=3);
   _u[0]=0;
   _u[1]=um2=1;
   celt_assert(len>=3);
   _u[0]=0;
   _u[1]=um2=1;
-  if(_n<=6 || _k>255){
+#ifndef SMALL_FOOTPRINT
+  if(_n<=6 || _k>255)
+#endif
+ {
     /*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);
     /*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);
@@ -444,9 +382,10 @@ static celt_uint32_t ncwrs_urow(unsigned _n,unsigned _k,celt_uint32_t *_u){
     while(++k<len);
     for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
   }
     while(++k<len);
     for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
   }
+#ifndef SMALL_FOOTPRINT
   else{
   else{
-    celt_uint32_t um1;
-    celt_uint32_t n2m1;
+    celt_uint32 um1;
+    celt_uint32 n2m1;
     _u[2]=n2m1=um1=(_n<<1)-1;
     for(k=3;k<len;k++){
       /*U(N,K) = ((2*N-1)*U(N,K-1)-U(N,K-2))/(K-1) + U(N,K-2)*/
     _u[2]=n2m1=um1=(_n<<1)-1;
     for(k=3;k<len;k++){
       /*U(N,K) = ((2*N-1)*U(N,K-1)-U(N,K-2))/(K-1) + U(N,K-2)*/
@@ -455,24 +394,26 @@ static celt_uint32_t ncwrs_urow(unsigned _n,unsigned _k,celt_uint32_t *_u){
       _u[k]=um1=imusdiv32odd(n2m1,um2,um1,k-1>>1)+um1;
     }
   }
       _u[k]=um1=imusdiv32odd(n2m1,um2,um1,k-1>>1)+um1;
     }
   }
+#endif /* SMALL_FOOTPRINT */
   return _u[_k]+_u[_k+1];
 }
 
   return _u[_k]+_u[_k+1];
 }
 
-
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 1 with associated sign bits.
   _y: Returns the vector of pulses.*/
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 1 with associated sign bits.
   _y: Returns the vector of pulses.*/
-static inline void cwrsi1(int _k,celt_uint32_t _i,int *_y){
+static inline void cwrsi1(int _k,celt_uint32 _i,int *_y){
   int s;
   s=-(int)_i;
   _y[0]=_k+s^s;
 }
 
   int s;
   s=-(int)_i;
   _y[0]=_k+s^s;
 }
 
+#ifndef SMALL_FOOTPRINT
+
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 2 with associated sign bits.
   _y: Returns the vector of pulses.*/
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 2 with associated sign bits.
   _y: Returns the vector of pulses.*/
-static inline void cwrsi2(int _k,celt_uint32_t _i,int *_y){
-  celt_uint32_t p;
+static inline void cwrsi2(int _k,celt_uint32 _i,int *_y){
+  celt_uint32 p;
   int           s;
   int           yj;
   p=ucwrs2(_k+1U);
   int           s;
   int           yj;
   p=ucwrs2(_k+1U);
@@ -490,8 +431,8 @@ static inline void cwrsi2(int _k,celt_uint32_t _i,int *_y){
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 3 with associated sign bits.
   _y: Returns the vector of pulses.*/
 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
    set of size 3 with associated sign bits.
   _y: Returns the vector of pulses.*/
-static void cwrsi3(int _k,celt_uint32_t _i,int *_y){
-  celt_uint32_t p;
+static void cwrsi3(int _k,celt_uint32 _i,int *_y){
+  celt_uint32 p;
   int           s;
   int           yj;
   p=ucwrs3(_k+1U);
   int           s;
   int           yj;
   p=ucwrs3(_k+1U);
@@ -511,8 +452,8 @@ static void cwrsi3(int _k,celt_uint32_t _i,int *_y){
 /*Returns the _i'th combination of _k elements (at most 1172) chosen from a set
    of size 4 with associated sign bits.
   _y: Returns the vector of pulses.*/
 /*Returns the _i'th combination of _k elements (at most 1172) chosen from a set
    of size 4 with associated sign bits.
   _y: Returns the vector of pulses.*/
-static void cwrsi4(int _k,celt_uint32_t _i,int *_y){
-  celt_uint32_t p;
+static void cwrsi4(int _k,celt_uint32 _i,int *_y){
+  celt_uint32 p;
   int           s;
   int           yj;
   int           kl;
   int           s;
   int           yj;
   int           kl;
@@ -545,36 +486,47 @@ static void cwrsi4(int _k,celt_uint32_t _i,int *_y){
 /*Returns the _i'th combination of _k elements (at most 238) chosen from a set
    of size 5 with associated sign bits.
   _y: Returns the vector of pulses.*/
 /*Returns the _i'th combination of _k elements (at most 238) chosen from a set
    of size 5 with associated sign bits.
   _y: Returns the vector of pulses.*/
-static void cwrsi5(int _k,celt_uint32_t _i,int *_y){
-  celt_uint32_t p;
+static void cwrsi5(int _k,celt_uint32 _i,int *_y){
+  celt_uint32 p;
   int           s;
   int           yj;
   p=ucwrs5(_k+1);
   s=-(_i>=p);
   _i-=p&s;
   yj=_k;
   int           s;
   int           yj;
   p=ucwrs5(_k+1);
   s=-(_i>=p);
   _i-=p&s;
   yj=_k;
-  /*Finds the maximum _k such that ucwrs5(_k)<=_i (tested for all
-     _i<2157192969=U(5,239)).*/
-  if(_i>=0x2AAAAAA9UL)_k=isqrt32(2*isqrt36(10+6*(celt_uint64_t)_i)-7)+1>>1;
-  else _k=_i>0?isqrt32(2*(celt_uint32_t)isqrt32(10+6*_i)-7)+1>>1:0;
-  p=ucwrs5(_k);
+  /* A binary search on U(5,K) avoids the need for 64-bit arithmetic */
+  {
+    int kl=0;
+    int kr=_k;
+    for(;;){
+      _k=kl+kr>>1;
+      p=ucwrs5(_k);
+      if(p<_i){
+        if(_k>=kr)break;
+        kl=_k+1;
+      }
+      else if(p>_i)kr=_k-1;
+      else break;
+    }  
+  }
   _i-=p;
   yj-=_k;
   _y[0]=yj+s^s;
   cwrsi4(_k,_i,_y+1);
 }
   _i-=p;
   yj-=_k;
   _y[0]=yj+s^s;
   cwrsi4(_k,_i,_y+1);
 }
+#endif /* SMALL_FOOTPRINT */
 
 /*Returns the _i'th combination of _k elements chosen from a set of size _n
    with associated sign bits.
   _y: Returns the vector of pulses.
   _u: Must contain entries [0..._k+1] of row _n of U() on input.
       Its contents will be destructively modified.*/
 
 /*Returns the _i'th combination of _k elements chosen from a set of size _n
    with associated sign bits.
   _y: Returns the vector of pulses.
   _u: Must contain entries [0..._k+1] of row _n of U() on input.
       Its contents will be destructively modified.*/
-static void cwrsi(int _n,int _k,celt_uint32_t _i,int *_y,celt_uint32_t *_u){
+static void cwrsi(int _n,int _k,celt_uint32 _i,int *_y,celt_uint32 *_u){
   int j;
   celt_assert(_n>0);
   j=0;
   do{
   int j;
   celt_assert(_n>0);
   j=0;
   do{
-    celt_uint32_t p;
+    celt_uint32 p;
     int           s;
     int           yj;
     p=_u[_k+1];
     int           s;
     int           yj;
     p=_u[_k+1];
@@ -596,17 +548,19 @@ static void cwrsi(int _n,int _k,celt_uint32_t _i,int *_y,celt_uint32_t *_u){
    of size 1 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
    of size 1 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
-static inline celt_uint32_t icwrs1(const int *_y,int *_k){
+static inline celt_uint32 icwrs1(const int *_y,int *_k){
   *_k=abs(_y[0]);
   return _y[0]<0;
 }
 
   *_k=abs(_y[0]);
   return _y[0]<0;
 }
 
+#ifndef SMALL_FOOTPRINT
+
 /*Returns the index of the given combination of K elements chosen from a set
    of size 2 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
 /*Returns the index of the given combination of K elements chosen from a set
    of size 2 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
-static inline celt_uint32_t icwrs2(const int *_y,int *_k){
-  celt_uint32_t i;
+static inline celt_uint32 icwrs2(const int *_y,int *_k){
+  celt_uint32 i;
   int           k;
   i=icwrs1(_y+1,&k);
   i+=ucwrs2(k);
   int           k;
   i=icwrs1(_y+1,&k);
   i+=ucwrs2(k);
@@ -620,8 +574,8 @@ static inline celt_uint32_t icwrs2(const int *_y,int *_k){
    of size 3 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
    of size 3 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
-static inline celt_uint32_t icwrs3(const int *_y,int *_k){
-  celt_uint32_t i;
+static inline celt_uint32 icwrs3(const int *_y,int *_k){
+  celt_uint32 i;
   int           k;
   i=icwrs2(_y+1,&k);
   i+=ucwrs3(k);
   int           k;
   i=icwrs2(_y+1,&k);
   i+=ucwrs3(k);
@@ -635,8 +589,8 @@ static inline celt_uint32_t icwrs3(const int *_y,int *_k){
    of size 4 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
    of size 4 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
-static inline celt_uint32_t icwrs4(const int *_y,int *_k){
-  celt_uint32_t i;
+static inline celt_uint32 icwrs4(const int *_y,int *_k){
+  celt_uint32 i;
   int           k;
   i=icwrs3(_y+1,&k);
   i+=ucwrs4(k);
   int           k;
   i=icwrs3(_y+1,&k);
   i+=ucwrs4(k);
@@ -650,8 +604,8 @@ static inline celt_uint32_t icwrs4(const int *_y,int *_k){
    of size 5 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
    of size 5 with associated sign bits.
   _y: The vector of pulses, whose sum of absolute values is K.
   _k: Returns K.*/
-static inline celt_uint32_t icwrs5(const int *_y,int *_k){
-  celt_uint32_t i;
+static inline celt_uint32 icwrs5(const int *_y,int *_k){
+  celt_uint32 i;
   int           k;
   i=icwrs4(_y+1,&k);
   i+=ucwrs5(k);
   int           k;
   i=icwrs4(_y+1,&k);
   i+=ucwrs5(k);
@@ -660,14 +614,15 @@ static inline celt_uint32_t icwrs5(const int *_y,int *_k){
   *_k=k;
   return i;
 }
   *_k=k;
   return i;
 }
+#endif /* SMALL_FOOTPRINT */
 
 /*Returns the index of the given combination of K elements chosen from a set
    of size _n with associated sign bits.
   _y:  The vector of pulses, whose sum of absolute values must be _k.
   _nc: Returns V(_n,_k).*/
 
 /*Returns the index of the given combination of K elements chosen from a set
    of size _n with associated sign bits.
   _y:  The vector of pulses, whose sum of absolute values must be _k.
   _nc: Returns V(_n,_k).*/
-celt_uint32_t icwrs(int _n,int _k,celt_uint32_t *_nc,const int *_y,
- celt_uint32_t *_u){
-  celt_uint32_t i;
+celt_uint32 icwrs(int _n,int _k,celt_uint32 *_nc,const int *_y,
+ celt_uint32 *_u){
+  celt_uint32 i;
   int           j;
   int           k;
   /*We can't unroll the first two iterations of the loop unless _n>=2.*/
   int           j;
   int           k;
   /*We can't unroll the first two iterations of the loop unless _n>=2.*/
@@ -689,129 +644,40 @@ celt_uint32_t icwrs(int _n,int _k,celt_uint32_t *_nc,const int *_y,
   return i;
 }
 
   return i;
 }
 
-
-/*Computes get_required_bits when splitting is required.
-  _left_bits and _right_bits must contain the required bits for the left and
-   right sides of the split, respectively (which themselves may require
-   splitting).*/
-static void get_required_split_bits(celt_int16_t *_bits,
- const celt_int16_t *_left_bits,const celt_int16_t *_right_bits,
- int _n,int _maxk,int _frac){
-  int k;
-  for(k=_maxk;k-->0;){
-    /*If we've reached a k where everything fits in 32 bits, evaluate the
-       remaining required bits directly.*/
-    if(fits_in32(_n,k)){
-      get_required_bits(_bits,_n,k+1,_frac);
-      break;
-    }
-    else{
-      int worst_bits;
-      int i;
-      /*Due to potentially recursive splitting, it's difficult to derive an
-         analytic expression for the location of the worst-case split index.
-        We simply check them all.*/
-      worst_bits=0;
-      for(i=0;i<=k;i++){
-        int split_bits;
-        split_bits=_left_bits[i]+_right_bits[k-i];
-        if(split_bits>worst_bits)worst_bits=split_bits;
-      }
-      _bits[k]=log2_frac(k+1,_frac)+worst_bits;
-    }
-  }
-}
-
-/*Computes get_required_bits for a pair of N values.
-  _n1 and _n2 must either be equal or two consecutive integers.
-  Returns the buffer used to store the required bits for _n2, which is either
-   _bits1 if _n1==_n2 or _bits2 if _n1+1==_n2.*/
-static celt_int16_t *get_required_bits_pair(celt_int16_t *_bits1,
- celt_int16_t *_bits2,celt_int16_t *_tmp,int _n1,int _n2,int _maxk,int _frac){
-  celt_int16_t *tmp2;
-  /*If we only need a single set of required bits...*/
-  if(_n1==_n2){
-    /*Stop recursing if everything fits.*/
-    if(fits_in32(_n1,_maxk-1))get_required_bits(_bits1,_n1,_maxk,_frac);
-    else{
-      _tmp=get_required_bits_pair(_bits2,_tmp,_bits1,
-       _n1>>1,_n1+1>>1,_maxk,_frac);
-      get_required_split_bits(_bits1,_bits2,_tmp,_n1,_maxk,_frac);
-    }
-    return _bits1;
-  }
-  /*Otherwise we need two distinct sets...*/
-  celt_assert(_n1+1==_n2);
-  /*Stop recursing if everything fits.*/
-  if(fits_in32(_n2,_maxk-1)){
-    get_required_bits(_bits1,_n1,_maxk,_frac);
-    get_required_bits(_bits2,_n2,_maxk,_frac);
-  }
-  /*Otherwise choose an evaluation order that doesn't require extra buffers.*/
-  else if(_n1&1){
-    /*This special case isn't really needed, but can save some work.*/
-    if(fits_in32(_n1,_maxk-1)){
-      tmp2=get_required_bits_pair(_tmp,_bits1,_bits2,
-       _n2>>1,_n2>>1,_maxk,_frac);
-      get_required_split_bits(_bits2,_tmp,tmp2,_n2,_maxk,_frac);
-      get_required_bits(_bits1,_n1,_maxk,_frac);
-    }
-    else{
-      _tmp=get_required_bits_pair(_bits2,_tmp,_bits1,
-       _n1>>1,_n1+1>>1,_maxk,_frac);
-      get_required_split_bits(_bits1,_bits2,_tmp,_n1,_maxk,_frac);
-      get_required_split_bits(_bits2,_tmp,_tmp,_n2,_maxk,_frac);
-    }
-  }
-  else{
-    /*There's no need to special case _n1 fitting by itself, since _n2 requires
-       us to recurse for both values anyway.*/
-    tmp2=get_required_bits_pair(_tmp,_bits1,_bits2,
-     _n2>>1,_n2+1>>1,_maxk,_frac);
-    get_required_split_bits(_bits2,_tmp,tmp2,_n2,_maxk,_frac);
-    get_required_split_bits(_bits1,_tmp,_tmp,_n1,_maxk,_frac);
-  }
-  return _bits2;
-}
-
-void get_required_bits(celt_int16_t *_bits,int _n,int _maxk,int _frac){
+#ifndef STATIC_MODES
+void get_required_bits(celt_int16 *_bits,int _n,int _maxk,int _frac){
   int k;
   /*_maxk==0 => there's nothing to do.*/
   celt_assert(_maxk>0);
   int k;
   /*_maxk==0 => there's nothing to do.*/
   celt_assert(_maxk>0);
-  if(fits_in32(_n,_maxk-1)){
-    _bits[0]=0;
-    if(_maxk>1){
-      VARDECL(celt_uint32_t,u);
-      SAVE_STACK;
-      ALLOC(u,_maxk+1U,celt_uint32_t);
-      ncwrs_urow(_n,_maxk-1,u);
-      for(k=1;k<_maxk;k++)_bits[k]=log2_frac(u[k]+u[k+1],_frac);
-      RESTORE_STACK;
-    }
+  _bits[0]=0;
+  if (_n==1)
+  {
+    for (k=1;k<=_maxk;k++)
+      _bits[k] = 1<<_frac;
   }
   }
-  else{
-    VARDECL(celt_int16_t,n1bits);
-    VARDECL(celt_int16_t,n2bits_buf);
-    celt_int16_t *n2bits;
+  else {
+    VARDECL(celt_uint32,u);
     SAVE_STACK;
     SAVE_STACK;
-    ALLOC(n1bits,_maxk,celt_int16_t);
-    ALLOC(n2bits_buf,_maxk,celt_int16_t);
-    n2bits=get_required_bits_pair(n1bits,n2bits_buf,_bits,
-     _n>>1,_n+1>>1,_maxk,_frac);
-    get_required_split_bits(_bits,n1bits,n2bits,_n,_maxk,_frac);
+    ALLOC(u,_maxk+2U,celt_uint32);
+    ncwrs_urow(_n,_maxk,u);
+    for(k=1;k<=_maxk;k++)
+      _bits[k]=log2_frac(u[k]+u[k+1],_frac);
     RESTORE_STACK;
   }
 }
     RESTORE_STACK;
   }
 }
+#endif /* STATIC_MODES */
 
 
-
-static inline void encode_pulses32(int _n,int _k,const int *_y,ec_enc *_enc){
-  celt_uint32_t i;
+void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
+  celt_uint32 i;
+  if (_k==0)
+     return;
   switch(_n){
     case 1:{
       i=icwrs1(_y,&_k);
       celt_assert(ncwrs1(_k)==2);
       ec_enc_bits(_enc,i,1);
     }break;
   switch(_n){
     case 1:{
       i=icwrs1(_y,&_k);
       celt_assert(ncwrs1(_k)==2);
       ec_enc_bits(_enc,i,1);
     }break;
+#ifndef SMALL_FOOTPRINT
     case 2:{
       i=icwrs2(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs2(_k));
     case 2:{
       i=icwrs2(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs2(_k));
@@ -828,71 +694,47 @@ static inline void encode_pulses32(int _n,int _k,const int *_y,ec_enc *_enc){
       i=icwrs5(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs5(_k));
     }break;
       i=icwrs5(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs5(_k));
     }break;
-    default:{
-      VARDECL(celt_uint32_t,u);
-      celt_uint32_t nc;
+#endif
+     default:
+    {
+      VARDECL(celt_uint32,u);
+      celt_uint32 nc;
       SAVE_STACK;
       SAVE_STACK;
-      ALLOC(u,_k+2U,celt_uint32_t);
+      ALLOC(u,_k+2U,celt_uint32);
       i=icwrs(_n,_k,&nc,_y,u);
       ec_enc_uint(_enc,i,nc);
       RESTORE_STACK;
       i=icwrs(_n,_k,&nc,_y,u);
       ec_enc_uint(_enc,i,nc);
       RESTORE_STACK;
-    }break;
+    };
   }
 }
 
   }
 }
 
-void encode_pulses(int *_y, int N, int K, ec_enc *enc)
+void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec)
 {
 {
-   if (K==0) {
-   } else if(fits_in32(N,K))
-   {
-      encode_pulses32(N, K, _y, enc);
-   } else {
-     int i;
-     int count=0;
-     int split;
-     split = (N+1)/2;
-     for (i=0;i<split;i++)
-        count += abs(_y[i]);
-     ec_enc_uint(enc,count,K+1);
-     encode_pulses(_y, split, count, enc);
-     encode_pulses(_y+split, N-split, K-count, enc);
+   if (_k==0) {
+      int i;
+      for (i=0;i<_n;i++)
+         _y[i] = 0;
+      return;
    }
    }
-}
-
-static inline void decode_pulses32(int _n,int _k,int *_y,ec_dec *_dec){
-  switch(_n){
+   switch(_n){
     case 1:{
       celt_assert(ncwrs1(_k)==2);
       cwrsi1(_k,ec_dec_bits(_dec,1),_y);
     }break;
     case 1:{
       celt_assert(ncwrs1(_k)==2);
       cwrsi1(_k,ec_dec_bits(_dec,1),_y);
     }break;
+#ifndef SMALL_FOOTPRINT
     case 2:cwrsi2(_k,ec_dec_uint(_dec,ncwrs2(_k)),_y);break;
     case 3:cwrsi3(_k,ec_dec_uint(_dec,ncwrs3(_k)),_y);break;
     case 4:cwrsi4(_k,ec_dec_uint(_dec,ncwrs4(_k)),_y);break;
     case 5:cwrsi5(_k,ec_dec_uint(_dec,ncwrs5(_k)),_y);break;
     case 2:cwrsi2(_k,ec_dec_uint(_dec,ncwrs2(_k)),_y);break;
     case 3:cwrsi3(_k,ec_dec_uint(_dec,ncwrs3(_k)),_y);break;
     case 4:cwrsi4(_k,ec_dec_uint(_dec,ncwrs4(_k)),_y);break;
     case 5:cwrsi5(_k,ec_dec_uint(_dec,ncwrs5(_k)),_y);break;
-    default:{
-      VARDECL(celt_uint32_t,u);
+#endif
+      default:
+    {
+      VARDECL(celt_uint32,u);
       SAVE_STACK;
       SAVE_STACK;
-      ALLOC(u,_k+2U,celt_uint32_t);
+      ALLOC(u,_k+2U,celt_uint32);
       cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
       RESTORE_STACK;
     }
   }
 }
 
       cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
       RESTORE_STACK;
     }
   }
 }
 
-void decode_pulses(int *_y, int N, int K, ec_dec *dec)
-{
-   if (K==0) {
-      int i;
-      for (i=0;i<N;i++)
-         _y[i] = 0;
-   } else if(fits_in32(N,K))
-   {
-      decode_pulses32(N, K, _y, dec);
-   } else {
-     int split;
-     int count = ec_dec_uint(dec,K+1);
-     split = (N+1)/2;
-     decode_pulses(_y, split, count, dec);
-     decode_pulses(_y+split, N-split, K-count, dec);
-   }
-}