Adds many syntactically unnecessary casts to silence MSVC C4244; fix an MDCT encoder...
[opus.git] / libcelt / cwrs.c
index 0c090f8..e5cd08d 100644 (file)
@@ -32,8 +32,6 @@
 #endif
 
 #include "os_support.h"
-#include <stdlib.h>
-#include <string.h>
 #include "cwrs.h"
 #include "mathops.h"
 #include "arch.h"
@@ -77,7 +75,7 @@ int log2_frac(opus_uint32 val, int frac)
 #define MASK32 (0xFFFFFFFF)
 
 /*INV_TABLE[i] holds the multiplicative inverse of (2*i+1) mod 2**32.*/
-static const opus_uint32 INV_TABLE[64]={
+static const opus_uint32 INV_TABLE[53]={
   0x00000001,0xAAAAAAAB,0xCCCCCCCD,0xB6DB6DB7,
   0x38E38E39,0xBA2E8BA3,0xC4EC4EC5,0xEEEEEEEF,
   0xF0F0F0F1,0x286BCA1B,0x3CF3CF3D,0xE9BD37A7,
@@ -91,34 +89,16 @@ static const opus_uint32 INV_TABLE[64]={
   0x781948B1,0x2B2E43DB,0xFCFCFCFD,0x6FD0EB67,
   0xFA3F47E9,0xD2FD2FD3,0x3F4FD3F5,0xD4E25B9F,
   0x5F02A3A1,0xBF5A814B,0x7C32B16D,0xD3431B57,
-  0xD8FD8FD9,0x8D28AC43,0xDA6C0965,0xDB195E8F,
-  0x0FDBC091,0x61F2A4BB,0xDCFDCFDD,0x46FDD947,
-  0x56BE69C9,0xEB2FDEB3,0x26E978D5,0xEFDFBF7F,
-  /*
-  0x0FE03F81,0xC9484E2B,0xE133F84D,0xE1A8C537,
-  0x077975B9,0x70586723,0xCD29C245,0xFAA11E6F,
-  0x0FE3C071,0x08B51D9B,0x8CE2CABD,0xBF937F27,
-  0xA8FE53A9,0x592FE593,0x2C0685B5,0x2EB11B5F,
-  0xFCD1E361,0x451AB30B,0x72CFE72D,0xDB35A717,
-  0xFB74A399,0xE80BFA03,0x0D516325,0x1BCB564F,
-  0xE02E4851,0xD962AE7B,0x10F8ED9D,0x95AEDD07,
-  0xE9DC0589,0xA18A4473,0xEA53FA95,0xEE936F3F,
-  0x90948F41,0xEAFEAFEB,0x3D137E0D,0xEF46C0F7,
-  0x028C1979,0x791064E3,0xC04FEC05,0xE115062F,
-  0x32385831,0x6E68575B,0xA10D387D,0x6FECF2E7,
-  0x3FB47F69,0xED4BFB53,0x74FED775,0xDB43BB1F,
-  0x87654321,0x9BA144CB,0x478BBCED,0xBFB912D7,
-  0x1FDCD759,0x14B2A7C3,0xCB125CE5,0x437B2E0F,
-  0x10FEF011,0xD2B3183B,0x386CAB5D,0xEF6AC0C7,
-  0x0E64C149,0x9A020A33,0xE6B41C55,0xFEFEFEFF*/
+  0xD8FD8FD9,
 };
 
 /*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.*/
+   valid for _d<=52.*/
 static inline opus_uint32 imusdiv32odd(opus_uint32 _a,opus_uint32 _b,
  opus_uint32 _c,int _d){
+  celt_assert(_d<=52);
   return (_a*_b-_c)*INV_TABLE[_d]&MASK32;
 }
 
@@ -126,7 +106,7 @@ static inline opus_uint32 imusdiv32odd(opus_uint32 _a,opus_uint32 _b,
   _d does not actually have to be even, but imusdiv32odd will be faster when
    it's odd, so you should use that instead.
   _a and _d are assumed to be small (e.g., _a*_d fits in 32 bits; currently the
-   table for multiplicative inverses is only valid for _d<=256).
+   table for multiplicative inverses is only valid for _d<=54).
   _b and _c may be arbitrary so long as the arbitrary precision reuslt fits in
    32 bits.*/
 static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
@@ -136,14 +116,14 @@ static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
   int           shift;
   int           one;
   celt_assert(_d>0);
+  celt_assert(_d<=54);
   shift=EC_ILOG(_d^_d-1);
-  celt_assert(_d<=256);
-  inv=INV_TABLE[_d-1>>shift];
+  inv=INV_TABLE[(_d-1)>>shift];
   shift--;
   one=1<<shift;
   mask=one-1;
   return (_a*(_b>>shift)-(_c>>shift)+
-   (_a*(_b&mask)+one-(_c&mask)>>shift)-1)*inv&MASK32;
+   ((_a*(_b&mask)+one-(_c&mask))>>shift)-1)*inv&MASK32;
 }
 
 #endif /* SMALL_FOOTPRINT */
@@ -268,52 +248,42 @@ static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
   }*/
 
 #ifndef SMALL_FOOTPRINT
-
-/*Compute V(1,_k).*/
-static inline unsigned ncwrs1(int _k){
-  return _k?2:1;
-}
-
 /*Compute U(2,_k).
   Note that this may be called with _k=32768 (maxK[2]+1).*/
 static inline unsigned ucwrs2(unsigned _k){
-  return _k?_k+(_k-1):0;
+  celt_assert(_k>0);
+  return _k+(_k-1);
 }
 
 /*Compute V(2,_k).*/
 static inline opus_uint32 ncwrs2(int _k){
-  return _k?4*(opus_uint32)_k:1;
+  celt_assert(_k>0);
+  return 4*(opus_uint32)_k;
 }
 
 /*Compute U(3,_k).
   Note that this may be called with _k=32768 (maxK[3]+1).*/
 static inline opus_uint32 ucwrs3(unsigned _k){
-  return _k?(2*(opus_uint32)_k-2)*_k+1:0;
+  celt_assert(_k>0);
+  return (2*(opus_uint32)_k-2)*_k+1;
 }
 
 /*Compute V(3,_k).*/
 static inline opus_uint32 ncwrs3(int _k){
-  return _k?2*(2*(unsigned)_k*(opus_uint32)_k+1):1;
+  celt_assert(_k>0);
+  return 2*(2*(unsigned)_k*(opus_uint32)_k+1);
 }
 
 /*Compute U(4,_k).*/
 static inline opus_uint32 ucwrs4(int _k){
-  return _k?imusdiv32odd(2*_k,(2*_k-3)*(opus_uint32)_k+4,3,1):0;
+  celt_assert(_k>0);
+  return imusdiv32odd(2*_k,(2*_k-3)*(opus_uint32)_k+4,3,1);
 }
 
 /*Compute V(4,_k).*/
 static inline opus_uint32 ncwrs4(int _k){
-  return _k?((_k*(opus_uint32)_k+2)*_k)/3<<3:1;
-}
-
-/*Compute U(5,_k).*/
-static inline opus_uint32 ucwrs5(int _k){
-  return _k?(((((_k-2)*(unsigned)_k+5)*(opus_uint32)_k-4)*_k)/3<<1)+1:0;
-}
-
-/*Compute V(5,_k).*/
-static inline opus_uint32 ncwrs5(int _k){
-  return _k?(((_k*(unsigned)_k+5)*(opus_uint32)_k*_k)/3<<2)+2:1;
+  celt_assert(_k>0);
+  return ((_k*(opus_uint32)_k+2)*_k)/3<<3;
 }
 
 #endif /* SMALL_FOOTPRINT */
@@ -362,7 +332,9 @@ static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
   _u[0]=0;
   _u[1]=um2=1;
 #ifndef SMALL_FOOTPRINT
-  if(_n<=6 || _k>255)
+  /*_k>52 doesn't work in the false branch due to the limits of INV_TABLE,
+    but _k isn't tested here because k<=52 for n=7*/
+  if(_n<=6)
 #endif
  {
     /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
@@ -384,13 +356,15 @@ static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
       /*U(N,K) = ((2*N-1)*U(N,K-1)-U(N,K-2))/(K-1) + U(N,K-2)*/
       _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;
+      _u[k]=um1=imusdiv32odd(n2m1,um2,um1,(k-1)>>1)+um1;
     }
   }
 #endif /* SMALL_FOOTPRINT */
   return _u[_k]+_u[_k+1];
 }
 
+#ifndef SMALL_FOOTPRINT
+
 /*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.*/
@@ -400,8 +374,6 @@ static inline void cwrsi1(int _k,opus_uint32 _i,int *_y){
   _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.*/
@@ -413,8 +385,8 @@ static inline void cwrsi2(int _k,opus_uint32 _i,int *_y){
   s=-(_i>=p);
   _i-=p&s;
   yj=_k;
-  _k=_i+1>>1;
-  p=ucwrs2(_k);
+  _k=(_i+1)>>1;
+  p=_k?ucwrs2(_k):0;
   _i-=p;
   yj-=_k;
   _y[0]=yj+s^s;
@@ -434,8 +406,8 @@ static void cwrsi3(int _k,opus_uint32 _i,int *_y){
   yj=_k;
   /*Finds the maximum _k such that ucwrs3(_k)<=_i (tested for all
      _i<2147418113=U(3,32768)).*/
-  _k=_i>0?isqrt32(2*_i-1)+1>>1:0;
-  p=ucwrs3(_k);
+  _k=_i>0?(isqrt32(2*_i-1)+1)>>1:0;
+  p=_k?ucwrs3(_k):0;
   _i-=p;
   yj-=_k;
   _y[0]=yj+s^s;
@@ -461,8 +433,8 @@ static void cwrsi4(int _k,opus_uint32 _i,int *_y){
   kl=0;
   kr=_k;
   for(;;){
-    _k=kl+kr>>1;
-    p=ucwrs4(_k);
+    _k=(kl+kr)>>1;
+    p=_k?ucwrs4(_k):0;
     if(p<_i){
       if(_k>=kr)break;
       kl=_k+1;
@@ -476,37 +448,6 @@ static void cwrsi4(int _k,opus_uint32 _i,int *_y){
   cwrsi3(_k,_i,_y+1);
 }
 
-/*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,opus_uint32 _i,int *_y){
-  opus_uint32 p;
-  int           s;
-  int           yj;
-  p=ucwrs5(_k+1);
-  s=-(_i>=p);
-  _i-=p&s;
-  yj=_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);
-}
 #endif /* SMALL_FOOTPRINT */
 
 /*Returns the _i'th combination of _k elements chosen from a set of size _n
@@ -555,7 +496,7 @@ static inline opus_uint32 icwrs2(const int *_y,int *_k){
   opus_uint32 i;
   int           k;
   i=icwrs1(_y+1,&k);
-  i+=ucwrs2(k);
+  i+=k?ucwrs2(k):0;
   k+=abs(_y[0]);
   if(_y[0]<0)i+=ucwrs2(k+1U);
   *_k=k;
@@ -570,7 +511,7 @@ static inline opus_uint32 icwrs3(const int *_y,int *_k){
   opus_uint32 i;
   int           k;
   i=icwrs2(_y+1,&k);
-  i+=ucwrs3(k);
+  i+=k?ucwrs3(k):0;
   k+=abs(_y[0]);
   if(_y[0]<0)i+=ucwrs3(k+1U);
   *_k=k;
@@ -585,27 +526,13 @@ static inline opus_uint32 icwrs4(const int *_y,int *_k){
   opus_uint32 i;
   int           k;
   i=icwrs3(_y+1,&k);
-  i+=ucwrs4(k);
+  i+=k?ucwrs4(k):0;
   k+=abs(_y[0]);
   if(_y[0]<0)i+=ucwrs4(k+1);
   *_k=k;
   return i;
 }
 
-/*Returns the index of the given combination of K elements chosen from a set
-   of size 5 with associated sign bits.
-  _y: The vector of pulses, whose sum of absolute values is K.
-  _k: Returns K.*/
-static inline opus_uint32 icwrs5(const int *_y,int *_k){
-  opus_uint32 i;
-  int           k;
-  i=icwrs4(_y+1,&k);
-  i+=ucwrs5(k);
-  k+=abs(_y[0]);
-  if(_y[0]<0)i+=ucwrs5(k+1);
-  *_k=k;
-  return i;
-}
 #endif /* SMALL_FOOTPRINT */
 
 /*Returns the index of the given combination of K elements chosen from a set
@@ -661,15 +588,9 @@ void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
 
 void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
   opus_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;
+  celt_assert(_k>0);
 #ifndef SMALL_FOOTPRINT
+  switch(_n){
     case 2:{
       i=icwrs2(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs2(_k));
@@ -682,13 +603,9 @@ void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
       i=icwrs4(_y,&_k);
       ec_enc_uint(_enc,i,ncwrs4(_k));
     }break;
-    case 5:{
-      i=icwrs5(_y,&_k);
-      ec_enc_uint(_enc,i,ncwrs5(_k));
-    }break;
-#endif
      default:
     {
+#endif
       VARDECL(opus_uint32,u);
       opus_uint32 nc;
       SAVE_STACK;
@@ -696,37 +613,32 @@ void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
       i=icwrs(_n,_k,&nc,_y,u);
       ec_enc_uint(_enc,i,nc);
       RESTORE_STACK;
-    };
+#ifndef SMALL_FOOTPRINT
+    }
+    break;
   }
+#endif
 }
 
 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;
-      return;
-   }
-   switch(_n){
-    case 1:{
-      celt_assert(ncwrs1(_k)==2);
-      cwrsi1(_k,ec_dec_bits(_dec,1),_y);
-    }break;
+  celt_assert(_k>0);
 #ifndef SMALL_FOOTPRINT
+   switch(_n){
     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;
-#endif
-      default:
+    default:
     {
+#endif
       VARDECL(opus_uint32,u);
       SAVE_STACK;
       ALLOC(u,_k+2U,opus_uint32);
       cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
       RESTORE_STACK;
+#ifndef SMALL_FOOTPRINT
     }
+    break;
   }
+#endif
 }
-