Adds 3rd clause to CELT license
[opus.git] / celt / cwrs.c
1 /* Copyright (c) 2007-2008 CSIRO
2    Copyright (c) 2007-2009 Xiph.Org Foundation
3    Copyright (c) 2007-2009 Timothy B. Terriberry
4    Written by Timothy B. Terriberry and Jean-Marc Valin */
5 /*
6    Redistribution and use in source and binary forms, with or without
7    modification, are permitted provided that the following conditions
8    are met:
9
10    - Redistributions of source code must retain the above copyright
11    notice, this list of conditions and the following disclaimer.
12
13    - Redistributions in binary form must reproduce the above copyright
14    notice, this list of conditions and the following disclaimer in the
15    documentation and/or other materials provided with the distribution.
16
17    - Neither the name of Internet Society, IETF or IETF Trust, nor the
18    names of specific contributors, may be used to endorse or promote
19    products derived from this software without specific prior written
20    permission.
21
22    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
26    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
28    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
31    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 */
34
35 #ifdef HAVE_CONFIG_H
36 #include "config.h"
37 #endif
38
39 #include "os_support.h"
40 #include "cwrs.h"
41 #include "mathops.h"
42 #include "arch.h"
43
44 #ifdef CUSTOM_MODES
45
46 /*Guaranteed to return a conservatively large estimate of the binary logarithm
47    with frac bits of fractional precision.
48   Tested for all possible 32-bit inputs with frac=4, where the maximum
49    overestimation is 0.06254243 bits.*/
50 int log2_frac(opus_uint32 val, int frac)
51 {
52   int l;
53   l=EC_ILOG(val);
54   if(val&(val-1)){
55     /*This is (val>>l-16), but guaranteed to round up, even if adding a bias
56        before the shift would cause overflow (e.g., for 0xFFFFxxxx).*/
57     if(l>16)val=(val>>(l-16))+(((val&((1<<(l-16))-1))+(1<<(l-16))-1)>>(l-16));
58     else val<<=16-l;
59     l=(l-1)<<frac;
60     /*Note that we always need one iteration, since the rounding up above means
61        that we might need to adjust the integer part of the logarithm.*/
62     do{
63       int b;
64       b=(int)(val>>16);
65       l+=b<<frac;
66       val=(val+b)>>b;
67       val=(val*val+0x7FFF)>>15;
68     }
69     while(frac-->0);
70     /*If val is not exactly 0x8000, then we have to round up the remainder.*/
71     return l+(val>0x8000);
72   }
73   /*Exact powers of two require no rounding.*/
74   else return (l-1)<<frac;
75 }
76 #endif
77
78 #ifndef SMALL_FOOTPRINT
79
80 #define MASK32 (0xFFFFFFFF)
81
82 /*INV_TABLE[i] holds the multiplicative inverse of (2*i+1) mod 2**32.*/
83 static const opus_uint32 INV_TABLE[53]={
84   0x00000001,0xAAAAAAAB,0xCCCCCCCD,0xB6DB6DB7,
85   0x38E38E39,0xBA2E8BA3,0xC4EC4EC5,0xEEEEEEEF,
86   0xF0F0F0F1,0x286BCA1B,0x3CF3CF3D,0xE9BD37A7,
87   0xC28F5C29,0x684BDA13,0x4F72C235,0xBDEF7BDF,
88   0x3E0F83E1,0x8AF8AF8B,0x914C1BAD,0x96F96F97,
89   0xC18F9C19,0x2FA0BE83,0xA4FA4FA5,0x677D46CF,
90   0x1A1F58D1,0xFAFAFAFB,0x8C13521D,0x586FB587,
91   0xB823EE09,0xA08AD8F3,0xC10C9715,0xBEFBEFBF,
92   0xC0FC0FC1,0x07A44C6B,0xA33F128D,0xE327A977,
93   0xC7E3F1F9,0x962FC963,0x3F2B3885,0x613716AF,
94   0x781948B1,0x2B2E43DB,0xFCFCFCFD,0x6FD0EB67,
95   0xFA3F47E9,0xD2FD2FD3,0x3F4FD3F5,0xD4E25B9F,
96   0x5F02A3A1,0xBF5A814B,0x7C32B16D,0xD3431B57,
97   0xD8FD8FD9,
98 };
99
100 /*Computes (_a*_b-_c)/(2*_d+1) when the quotient is known to be exact.
101   _a, _b, _c, and _d may be arbitrary so long as the arbitrary precision result
102    fits in 32 bits, but currently the table for multiplicative inverses is only
103    valid for _d<=52.*/
104 static inline opus_uint32 imusdiv32odd(opus_uint32 _a,opus_uint32 _b,
105  opus_uint32 _c,int _d){
106   celt_assert(_d<=52);
107   return (_a*_b-_c)*INV_TABLE[_d]&MASK32;
108 }
109
110 /*Computes (_a*_b-_c)/_d when the quotient is known to be exact.
111   _d does not actually have to be even, but imusdiv32odd will be faster when
112    it's odd, so you should use that instead.
113   _a and _d are assumed to be small (e.g., _a*_d fits in 32 bits; currently the
114    table for multiplicative inverses is only valid for _d<=54).
115   _b and _c may be arbitrary so long as the arbitrary precision reuslt fits in
116    32 bits.*/
117 static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
118  opus_uint32 _c,int _d){
119   opus_uint32 inv;
120   int           mask;
121   int           shift;
122   int           one;
123   celt_assert(_d>0);
124   celt_assert(_d<=54);
125   shift=EC_ILOG(_d^(_d-1));
126   inv=INV_TABLE[(_d-1)>>shift];
127   shift--;
128   one=1<<shift;
129   mask=one-1;
130   return (_a*(_b>>shift)-(_c>>shift)+
131    ((_a*(_b&mask)+one-(_c&mask))>>shift)-1)*inv&MASK32;
132 }
133
134 #endif /* SMALL_FOOTPRINT */
135
136 /*Although derived separately, the pulse vector coding scheme is equivalent to
137    a Pyramid Vector Quantizer \cite{Fis86}.
138   Some additional notes about an early version appear at
139    http://people.xiph.org/~tterribe/notes/cwrs.html, but the codebook ordering
140    and the definitions of some terms have evolved since that was written.
141
142   The conversion from a pulse vector to an integer index (encoding) and back
143    (decoding) is governed by two related functions, V(N,K) and U(N,K).
144
145   V(N,K) = the number of combinations, with replacement, of N items, taken K
146    at a time, when a sign bit is added to each item taken at least once (i.e.,
147    the number of N-dimensional unit pulse vectors with K pulses).
148   One way to compute this is via
149     V(N,K) = K>0 ? sum(k=1...K,2**k*choose(N,k)*choose(K-1,k-1)) : 1,
150    where choose() is the binomial function.
151   A table of values for N<10 and K<10 looks like:
152   V[10][10] = {
153     {1,  0,   0,    0,    0,     0,     0,      0,      0,       0},
154     {1,  2,   2,    2,    2,     2,     2,      2,      2,       2},
155     {1,  4,   8,   12,   16,    20,    24,     28,     32,      36},
156     {1,  6,  18,   38,   66,   102,   146,    198,    258,     326},
157     {1,  8,  32,   88,  192,   360,   608,    952,   1408,    1992},
158     {1, 10,  50,  170,  450,  1002,  1970,   3530,   5890,    9290},
159     {1, 12,  72,  292,  912,  2364,  5336,  10836,  20256,   35436},
160     {1, 14,  98,  462, 1666,  4942, 12642,  28814,  59906,  115598},
161     {1, 16, 128,  688, 2816,  9424, 27008,  68464, 157184,  332688},
162     {1, 18, 162,  978, 4482, 16722, 53154, 148626, 374274,  864146}
163   };
164
165   U(N,K) = the number of such combinations wherein N-1 objects are taken at
166    most K-1 at a time.
167   This is given by
168     U(N,K) = sum(k=0...K-1,V(N-1,k))
169            = K>0 ? (V(N-1,K-1) + V(N,K-1))/2 : 0.
170   The latter expression also makes clear that U(N,K) is half the number of such
171    combinations wherein the first object is taken at least once.
172   Although it may not be clear from either of these definitions, U(N,K) is the
173    natural function to work with when enumerating the pulse vector codebooks,
174    not V(N,K).
175   U(N,K) is not well-defined for N=0, but with the extension
176     U(0,K) = K>0 ? 0 : 1,
177    the function becomes symmetric: U(N,K) = U(K,N), with a similar table:
178   U[10][10] = {
179     {1, 0,  0,   0,    0,    0,     0,     0,      0,      0},
180     {0, 1,  1,   1,    1,    1,     1,     1,      1,      1},
181     {0, 1,  3,   5,    7,    9,    11,    13,     15,     17},
182     {0, 1,  5,  13,   25,   41,    61,    85,    113,    145},
183     {0, 1,  7,  25,   63,  129,   231,   377,    575,    833},
184     {0, 1,  9,  41,  129,  321,   681,  1289,   2241,   3649},
185     {0, 1, 11,  61,  231,  681,  1683,  3653,   7183,  13073},
186     {0, 1, 13,  85,  377, 1289,  3653,  8989,  19825,  40081},
187     {0, 1, 15, 113,  575, 2241,  7183, 19825,  48639, 108545},
188     {0, 1, 17, 145,  833, 3649, 13073, 40081, 108545, 265729}
189   };
190
191   With this extension, V(N,K) may be written in terms of U(N,K):
192     V(N,K) = U(N,K) + U(N,K+1)
193    for all N>=0, K>=0.
194   Thus U(N,K+1) represents the number of combinations where the first element
195    is positive or zero, and U(N,K) represents the number of combinations where
196    it is negative.
197   With a large enough table of U(N,K) values, we could write O(N) encoding
198    and O(min(N*log(K),N+K)) decoding routines, but such a table would be
199    prohibitively large for small embedded devices (K may be as large as 32767
200    for small N, and N may be as large as 200).
201
202   Both functions obey the same recurrence relation:
203     V(N,K) = V(N-1,K) + V(N,K-1) + V(N-1,K-1),
204     U(N,K) = U(N-1,K) + U(N,K-1) + U(N-1,K-1),
205    for all N>0, K>0, with different initial conditions at N=0 or K=0.
206   This allows us to construct a row of one of the tables above given the
207    previous row or the next row.
208   Thus we can derive O(NK) encoding and decoding routines with O(K) memory
209    using only addition and subtraction.
210
211   When encoding, we build up from the U(2,K) row and work our way forwards.
212   When decoding, we need to start at the U(N,K) row and work our way backwards,
213    which requires a means of computing U(N,K).
214   U(N,K) may be computed from two previous values with the same N:
215     U(N,K) = ((2*N-1)*U(N,K-1) - U(N,K-2))/(K-1) + U(N,K-2)
216    for all N>1, and since U(N,K) is symmetric, a similar relation holds for two
217    previous values with the same K:
218     U(N,K>1) = ((2*K-1)*U(N-1,K) - U(N-2,K))/(N-1) + U(N-2,K)
219    for all K>1.
220   This allows us to construct an arbitrary row of the U(N,K) table by starting
221    with the first two values, which are constants.
222   This saves roughly 2/3 the work in our O(NK) decoding routine, but costs O(K)
223    multiplications.
224   Similar relations can be derived for V(N,K), but are not used here.
225
226   For N>0 and K>0, U(N,K) and V(N,K) take on the form of an (N-1)-degree
227    polynomial for fixed N.
228   The first few are
229     U(1,K) = 1,
230     U(2,K) = 2*K-1,
231     U(3,K) = (2*K-2)*K+1,
232     U(4,K) = (((4*K-6)*K+8)*K-3)/3,
233     U(5,K) = ((((2*K-4)*K+10)*K-8)*K+3)/3,
234    and
235     V(1,K) = 2,
236     V(2,K) = 4*K,
237     V(3,K) = 4*K*K+2,
238     V(4,K) = 8*(K*K+2)*K/3,
239     V(5,K) = ((4*K*K+20)*K*K+6)/3,
240    for all K>0.
241   This allows us to derive O(N) encoding and O(N*log(K)) decoding routines for
242    small N (and indeed decoding is also O(N) for N<3).
243
244   @ARTICLE{Fis86,
245     author="Thomas R. Fischer",
246     title="A Pyramid Vector Quantizer",
247     journal="IEEE Transactions on Information Theory",
248     volume="IT-32",
249     number=4,
250     pages="568--583",
251     month=Jul,
252     year=1986
253   }*/
254
255 #ifndef SMALL_FOOTPRINT
256 /*Compute U(2,_k).
257   Note that this may be called with _k=32768 (maxK[2]+1).*/
258 static inline unsigned ucwrs2(unsigned _k){
259   celt_assert(_k>0);
260   return _k+(_k-1);
261 }
262
263 /*Compute V(2,_k).*/
264 static inline opus_uint32 ncwrs2(int _k){
265   celt_assert(_k>0);
266   return 4*(opus_uint32)_k;
267 }
268
269 /*Compute U(3,_k).
270   Note that this may be called with _k=32768 (maxK[3]+1).*/
271 static inline opus_uint32 ucwrs3(unsigned _k){
272   celt_assert(_k>0);
273   return (2*(opus_uint32)_k-2)*_k+1;
274 }
275
276 /*Compute V(3,_k).*/
277 static inline opus_uint32 ncwrs3(int _k){
278   celt_assert(_k>0);
279   return 2*(2*(unsigned)_k*(opus_uint32)_k+1);
280 }
281
282 /*Compute U(4,_k).*/
283 static inline opus_uint32 ucwrs4(int _k){
284   celt_assert(_k>0);
285   return imusdiv32odd(2*_k,(2*_k-3)*(opus_uint32)_k+4,3,1);
286 }
287
288 /*Compute V(4,_k).*/
289 static inline opus_uint32 ncwrs4(int _k){
290   celt_assert(_k>0);
291   return ((_k*(opus_uint32)_k+2)*_k)/3<<3;
292 }
293
294 #endif /* SMALL_FOOTPRINT */
295
296 /*Computes the next row/column of any recurrence that obeys the relation
297    u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
298   _ui0 is the base case for the new row/column.*/
299 static inline void unext(opus_uint32 *_ui,unsigned _len,opus_uint32 _ui0){
300   opus_uint32 ui1;
301   unsigned      j;
302   /*This do-while will overrun the array if we don't have storage for at least
303      2 values.*/
304   j=1; do {
305     ui1=UADD32(UADD32(_ui[j],_ui[j-1]),_ui0);
306     _ui[j-1]=_ui0;
307     _ui0=ui1;
308   } while (++j<_len);
309   _ui[j-1]=_ui0;
310 }
311
312 /*Computes the previous row/column of any recurrence that obeys the relation
313    u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
314   _ui0 is the base case for the new row/column.*/
315 static inline void uprev(opus_uint32 *_ui,unsigned _n,opus_uint32 _ui0){
316   opus_uint32 ui1;
317   unsigned      j;
318   /*This do-while will overrun the array if we don't have storage for at least
319      2 values.*/
320   j=1; do {
321     ui1=USUB32(USUB32(_ui[j],_ui[j-1]),_ui0);
322     _ui[j-1]=_ui0;
323     _ui0=ui1;
324   } while (++j<_n);
325   _ui[j-1]=_ui0;
326 }
327
328 /*Compute V(_n,_k), as well as U(_n,0..._k+1).
329   _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
330 static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
331   opus_uint32 um2;
332   unsigned      len;
333   unsigned      k;
334   len=_k+2;
335   /*We require storage at least 3 values (e.g., _k>0).*/
336   celt_assert(len>=3);
337   _u[0]=0;
338   _u[1]=um2=1;
339 #ifndef SMALL_FOOTPRINT
340   /*_k>52 doesn't work in the false branch due to the limits of INV_TABLE,
341     but _k isn't tested here because k<=52 for n=7*/
342   if(_n<=6)
343 #endif
344  {
345     /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
346     /*If _n==1, _u[i] should be 1 for i>1.*/
347     celt_assert(_n>=2);
348     /*If _k==0, the following do-while loop will overflow the buffer.*/
349     celt_assert(_k>0);
350     k=2;
351     do _u[k]=(k<<1)-1;
352     while(++k<len);
353     for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
354   }
355 #ifndef SMALL_FOOTPRINT
356   else{
357     opus_uint32 um1;
358     opus_uint32 n2m1;
359     _u[2]=n2m1=um1=(_n<<1)-1;
360     for(k=3;k<len;k++){
361       /*U(N,K) = ((2*N-1)*U(N,K-1)-U(N,K-2))/(K-1) + U(N,K-2)*/
362       _u[k]=um2=imusdiv32even(n2m1,um1,um2,k-1)+um2;
363       if(++k>=len)break;
364       _u[k]=um1=imusdiv32odd(n2m1,um2,um1,(k-1)>>1)+um1;
365     }
366   }
367 #endif /* SMALL_FOOTPRINT */
368   return _u[_k]+_u[_k+1];
369 }
370
371 #ifndef SMALL_FOOTPRINT
372
373 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
374    set of size 1 with associated sign bits.
375   _y: Returns the vector of pulses.*/
376 static inline void cwrsi1(int _k,opus_uint32 _i,int *_y){
377   int s;
378   s=-(int)_i;
379   _y[0]=(_k+s)^s;
380 }
381
382 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
383    set of size 2 with associated sign bits.
384   _y: Returns the vector of pulses.*/
385 static inline void cwrsi2(int _k,opus_uint32 _i,int *_y){
386   opus_uint32 p;
387   int           s;
388   int           yj;
389   p=ucwrs2(_k+1U);
390   s=-(_i>=p);
391   _i-=p&s;
392   yj=_k;
393   _k=(_i+1)>>1;
394   p=_k?ucwrs2(_k):0;
395   _i-=p;
396   yj-=_k;
397   _y[0]=(yj+s)^s;
398   cwrsi1(_k,_i,_y+1);
399 }
400
401 /*Returns the _i'th combination of _k elements (at most 32767) chosen from a
402    set of size 3 with associated sign bits.
403   _y: Returns the vector of pulses.*/
404 static void cwrsi3(int _k,opus_uint32 _i,int *_y){
405   opus_uint32 p;
406   int           s;
407   int           yj;
408   p=ucwrs3(_k+1U);
409   s=-(_i>=p);
410   _i-=p&s;
411   yj=_k;
412   /*Finds the maximum _k such that ucwrs3(_k)<=_i (tested for all
413      _i<2147418113=U(3,32768)).*/
414   _k=_i>0?(isqrt32(2*_i-1)+1)>>1:0;
415   p=_k?ucwrs3(_k):0;
416   _i-=p;
417   yj-=_k;
418   _y[0]=(yj+s)^s;
419   cwrsi2(_k,_i,_y+1);
420 }
421
422 /*Returns the _i'th combination of _k elements (at most 1172) chosen from a set
423    of size 4 with associated sign bits.
424   _y: Returns the vector of pulses.*/
425 static void cwrsi4(int _k,opus_uint32 _i,int *_y){
426   opus_uint32 p;
427   int           s;
428   int           yj;
429   int           kl;
430   int           kr;
431   p=ucwrs4(_k+1);
432   s=-(_i>=p);
433   _i-=p&s;
434   yj=_k;
435   /*We could solve a cubic for k here, but the form of the direct solution does
436      not lend itself well to exact integer arithmetic.
437     Instead we do a binary search on U(4,K).*/
438   kl=0;
439   kr=_k;
440   for(;;){
441     _k=(kl+kr)>>1;
442     p=_k?ucwrs4(_k):0;
443     if(p<_i){
444       if(_k>=kr)break;
445       kl=_k+1;
446     }
447     else if(p>_i)kr=_k-1;
448     else break;
449   }
450   _i-=p;
451   yj-=_k;
452   _y[0]=(yj+s)^s;
453   cwrsi3(_k,_i,_y+1);
454 }
455
456 #endif /* SMALL_FOOTPRINT */
457
458 /*Returns the _i'th combination of _k elements chosen from a set of size _n
459    with associated sign bits.
460   _y: Returns the vector of pulses.
461   _u: Must contain entries [0..._k+1] of row _n of U() on input.
462       Its contents will be destructively modified.*/
463 static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y,opus_uint32 *_u){
464   int j;
465   celt_assert(_n>0);
466   j=0;
467   do{
468     opus_uint32 p;
469     int           s;
470     int           yj;
471     p=_u[_k+1];
472     s=-(_i>=p);
473     _i-=p&s;
474     yj=_k;
475     p=_u[_k];
476     while(p>_i)p=_u[--_k];
477     _i-=p;
478     yj-=_k;
479     _y[j]=(yj+s)^s;
480     uprev(_u,_k+2,0);
481   }
482   while(++j<_n);
483 }
484
485 /*Returns the index of the given combination of K elements chosen from a set
486    of size 1 with associated sign bits.
487   _y: The vector of pulses, whose sum of absolute values is K.
488   _k: Returns K.*/
489 static inline opus_uint32 icwrs1(const int *_y,int *_k){
490   *_k=abs(_y[0]);
491   return _y[0]<0;
492 }
493
494 #ifndef SMALL_FOOTPRINT
495
496 /*Returns the index of the given combination of K elements chosen from a set
497    of size 2 with associated sign bits.
498   _y: The vector of pulses, whose sum of absolute values is K.
499   _k: Returns K.*/
500 static inline opus_uint32 icwrs2(const int *_y,int *_k){
501   opus_uint32 i;
502   int           k;
503   i=icwrs1(_y+1,&k);
504   i+=k?ucwrs2(k):0;
505   k+=abs(_y[0]);
506   if(_y[0]<0)i+=ucwrs2(k+1U);
507   *_k=k;
508   return i;
509 }
510
511 /*Returns the index of the given combination of K elements chosen from a set
512    of size 3 with associated sign bits.
513   _y: The vector of pulses, whose sum of absolute values is K.
514   _k: Returns K.*/
515 static inline opus_uint32 icwrs3(const int *_y,int *_k){
516   opus_uint32 i;
517   int           k;
518   i=icwrs2(_y+1,&k);
519   i+=k?ucwrs3(k):0;
520   k+=abs(_y[0]);
521   if(_y[0]<0)i+=ucwrs3(k+1U);
522   *_k=k;
523   return i;
524 }
525
526 /*Returns the index of the given combination of K elements chosen from a set
527    of size 4 with associated sign bits.
528   _y: The vector of pulses, whose sum of absolute values is K.
529   _k: Returns K.*/
530 static inline opus_uint32 icwrs4(const int *_y,int *_k){
531   opus_uint32 i;
532   int           k;
533   i=icwrs3(_y+1,&k);
534   i+=k?ucwrs4(k):0;
535   k+=abs(_y[0]);
536   if(_y[0]<0)i+=ucwrs4(k+1);
537   *_k=k;
538   return i;
539 }
540
541 #endif /* SMALL_FOOTPRINT */
542
543 /*Returns the index of the given combination of K elements chosen from a set
544    of size _n with associated sign bits.
545   _y:  The vector of pulses, whose sum of absolute values must be _k.
546   _nc: Returns V(_n,_k).*/
547 static inline opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y,
548  opus_uint32 *_u){
549   opus_uint32 i;
550   int           j;
551   int           k;
552   /*We can't unroll the first two iterations of the loop unless _n>=2.*/
553   celt_assert(_n>=2);
554   _u[0]=0;
555   for(k=1;k<=_k+1;k++)_u[k]=(k<<1)-1;
556   i=icwrs1(_y+_n-1,&k);
557   j=_n-2;
558   i+=_u[k];
559   k+=abs(_y[j]);
560   if(_y[j]<0)i+=_u[k+1];
561   while(j-->0){
562     unext(_u,_k+2,0);
563     i+=_u[k];
564     k+=abs(_y[j]);
565     if(_y[j]<0)i+=_u[k+1];
566   }
567   *_nc=_u[k]+_u[k+1];
568   return i;
569 }
570
571 #ifdef CUSTOM_MODES
572 void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
573   int k;
574   /*_maxk==0 => there's nothing to do.*/
575   celt_assert(_maxk>0);
576   _bits[0]=0;
577   if (_n==1)
578   {
579     for (k=1;k<=_maxk;k++)
580       _bits[k] = 1<<_frac;
581   }
582   else {
583     VARDECL(opus_uint32,u);
584     SAVE_STACK;
585     ALLOC(u,_maxk+2U,opus_uint32);
586     ncwrs_urow(_n,_maxk,u);
587     for(k=1;k<=_maxk;k++)
588       _bits[k]=log2_frac(u[k]+u[k+1],_frac);
589     RESTORE_STACK;
590   }
591 }
592 #endif /* CUSTOM_MODES */
593
594 void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
595   opus_uint32 i;
596   celt_assert(_k>0);
597 #ifndef SMALL_FOOTPRINT
598   switch(_n){
599     case 2:{
600       i=icwrs2(_y,&_k);
601       ec_enc_uint(_enc,i,ncwrs2(_k));
602     }break;
603     case 3:{
604       i=icwrs3(_y,&_k);
605       ec_enc_uint(_enc,i,ncwrs3(_k));
606     }break;
607     case 4:{
608       i=icwrs4(_y,&_k);
609       ec_enc_uint(_enc,i,ncwrs4(_k));
610     }break;
611      default:
612     {
613 #endif
614       VARDECL(opus_uint32,u);
615       opus_uint32 nc;
616       SAVE_STACK;
617       ALLOC(u,_k+2U,opus_uint32);
618       i=icwrs(_n,_k,&nc,_y,u);
619       ec_enc_uint(_enc,i,nc);
620       RESTORE_STACK;
621 #ifndef SMALL_FOOTPRINT
622     }
623     break;
624   }
625 #endif
626 }
627
628 void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec)
629 {
630   celt_assert(_k>0);
631 #ifndef SMALL_FOOTPRINT
632    switch(_n){
633     case 2:cwrsi2(_k,ec_dec_uint(_dec,ncwrs2(_k)),_y);break;
634     case 3:cwrsi3(_k,ec_dec_uint(_dec,ncwrs3(_k)),_y);break;
635     case 4:cwrsi4(_k,ec_dec_uint(_dec,ncwrs4(_k)),_y);break;
636     default:
637     {
638 #endif
639       VARDECL(opus_uint32,u);
640       SAVE_STACK;
641       ALLOC(u,_k+2U,opus_uint32);
642       cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
643       RESTORE_STACK;
644 #ifndef SMALL_FOOTPRINT
645     }
646     break;
647   }
648 #endif
649 }