Adding ENABLE_HARDENING
[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    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
21    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
25    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #ifdef HAVE_CONFIG_H
31 #include "config.h"
32 #endif
33
34 #include "os_support.h"
35 #include "cwrs.h"
36 #include "mathops.h"
37 #include "arch.h"
38
39 #ifdef CUSTOM_MODES
40
41 /*Guaranteed to return a conservatively large estimate of the binary logarithm
42    with frac bits of fractional precision.
43   Tested for all possible 32-bit inputs with frac=4, where the maximum
44    overestimation is 0.06254243 bits.*/
45 int log2_frac(opus_uint32 val, int frac)
46 {
47   int l;
48   l=EC_ILOG(val);
49   if(val&(val-1)){
50     /*This is (val>>l-16), but guaranteed to round up, even if adding a bias
51        before the shift would cause overflow (e.g., for 0xFFFFxxxx).
52        Doesn't work for val=0, but that case fails the test above.*/
53     if(l>16)val=((val-1)>>(l-16))+1;
54     else val<<=16-l;
55     l=(l-1)<<frac;
56     /*Note that we always need one iteration, since the rounding up above means
57        that we might need to adjust the integer part of the logarithm.*/
58     do{
59       int b;
60       b=(int)(val>>16);
61       l+=b<<frac;
62       val=(val+b)>>b;
63       val=(val*val+0x7FFF)>>15;
64     }
65     while(frac-->0);
66     /*If val is not exactly 0x8000, then we have to round up the remainder.*/
67     return l+(val>0x8000);
68   }
69   /*Exact powers of two require no rounding.*/
70   else return (l-1)<<frac;
71 }
72 #endif
73
74 /*Although derived separately, the pulse vector coding scheme is equivalent to
75    a Pyramid Vector Quantizer \cite{Fis86}.
76   Some additional notes about an early version appear at
77    https://people.xiph.org/~tterribe/notes/cwrs.html, but the codebook ordering
78    and the definitions of some terms have evolved since that was written.
79
80   The conversion from a pulse vector to an integer index (encoding) and back
81    (decoding) is governed by two related functions, V(N,K) and U(N,K).
82
83   V(N,K) = the number of combinations, with replacement, of N items, taken K
84    at a time, when a sign bit is added to each item taken at least once (i.e.,
85    the number of N-dimensional unit pulse vectors with K pulses).
86   One way to compute this is via
87     V(N,K) = K>0 ? sum(k=1...K,2**k*choose(N,k)*choose(K-1,k-1)) : 1,
88    where choose() is the binomial function.
89   A table of values for N<10 and K<10 looks like:
90   V[10][10] = {
91     {1,  0,   0,    0,    0,     0,     0,      0,      0,       0},
92     {1,  2,   2,    2,    2,     2,     2,      2,      2,       2},
93     {1,  4,   8,   12,   16,    20,    24,     28,     32,      36},
94     {1,  6,  18,   38,   66,   102,   146,    198,    258,     326},
95     {1,  8,  32,   88,  192,   360,   608,    952,   1408,    1992},
96     {1, 10,  50,  170,  450,  1002,  1970,   3530,   5890,    9290},
97     {1, 12,  72,  292,  912,  2364,  5336,  10836,  20256,   35436},
98     {1, 14,  98,  462, 1666,  4942, 12642,  28814,  59906,  115598},
99     {1, 16, 128,  688, 2816,  9424, 27008,  68464, 157184,  332688},
100     {1, 18, 162,  978, 4482, 16722, 53154, 148626, 374274,  864146}
101   };
102
103   U(N,K) = the number of such combinations wherein N-1 objects are taken at
104    most K-1 at a time.
105   This is given by
106     U(N,K) = sum(k=0...K-1,V(N-1,k))
107            = K>0 ? (V(N-1,K-1) + V(N,K-1))/2 : 0.
108   The latter expression also makes clear that U(N,K) is half the number of such
109    combinations wherein the first object is taken at least once.
110   Although it may not be clear from either of these definitions, U(N,K) is the
111    natural function to work with when enumerating the pulse vector codebooks,
112    not V(N,K).
113   U(N,K) is not well-defined for N=0, but with the extension
114     U(0,K) = K>0 ? 0 : 1,
115    the function becomes symmetric: U(N,K) = U(K,N), with a similar table:
116   U[10][10] = {
117     {1, 0,  0,   0,    0,    0,     0,     0,      0,      0},
118     {0, 1,  1,   1,    1,    1,     1,     1,      1,      1},
119     {0, 1,  3,   5,    7,    9,    11,    13,     15,     17},
120     {0, 1,  5,  13,   25,   41,    61,    85,    113,    145},
121     {0, 1,  7,  25,   63,  129,   231,   377,    575,    833},
122     {0, 1,  9,  41,  129,  321,   681,  1289,   2241,   3649},
123     {0, 1, 11,  61,  231,  681,  1683,  3653,   7183,  13073},
124     {0, 1, 13,  85,  377, 1289,  3653,  8989,  19825,  40081},
125     {0, 1, 15, 113,  575, 2241,  7183, 19825,  48639, 108545},
126     {0, 1, 17, 145,  833, 3649, 13073, 40081, 108545, 265729}
127   };
128
129   With this extension, V(N,K) may be written in terms of U(N,K):
130     V(N,K) = U(N,K) + U(N,K+1)
131    for all N>=0, K>=0.
132   Thus U(N,K+1) represents the number of combinations where the first element
133    is positive or zero, and U(N,K) represents the number of combinations where
134    it is negative.
135   With a large enough table of U(N,K) values, we could write O(N) encoding
136    and O(min(N*log(K),N+K)) decoding routines, but such a table would be
137    prohibitively large for small embedded devices (K may be as large as 32767
138    for small N, and N may be as large as 200).
139
140   Both functions obey the same recurrence relation:
141     V(N,K) = V(N-1,K) + V(N,K-1) + V(N-1,K-1),
142     U(N,K) = U(N-1,K) + U(N,K-1) + U(N-1,K-1),
143    for all N>0, K>0, with different initial conditions at N=0 or K=0.
144   This allows us to construct a row of one of the tables above given the
145    previous row or the next row.
146   Thus we can derive O(NK) encoding and decoding routines with O(K) memory
147    using only addition and subtraction.
148
149   When encoding, we build up from the U(2,K) row and work our way forwards.
150   When decoding, we need to start at the U(N,K) row and work our way backwards,
151    which requires a means of computing U(N,K).
152   U(N,K) may be computed from two previous values with the same N:
153     U(N,K) = ((2*N-1)*U(N,K-1) - U(N,K-2))/(K-1) + U(N,K-2)
154    for all N>1, and since U(N,K) is symmetric, a similar relation holds for two
155    previous values with the same K:
156     U(N,K>1) = ((2*K-1)*U(N-1,K) - U(N-2,K))/(N-1) + U(N-2,K)
157    for all K>1.
158   This allows us to construct an arbitrary row of the U(N,K) table by starting
159    with the first two values, which are constants.
160   This saves roughly 2/3 the work in our O(NK) decoding routine, but costs O(K)
161    multiplications.
162   Similar relations can be derived for V(N,K), but are not used here.
163
164   For N>0 and K>0, U(N,K) and V(N,K) take on the form of an (N-1)-degree
165    polynomial for fixed N.
166   The first few are
167     U(1,K) = 1,
168     U(2,K) = 2*K-1,
169     U(3,K) = (2*K-2)*K+1,
170     U(4,K) = (((4*K-6)*K+8)*K-3)/3,
171     U(5,K) = ((((2*K-4)*K+10)*K-8)*K+3)/3,
172    and
173     V(1,K) = 2,
174     V(2,K) = 4*K,
175     V(3,K) = 4*K*K+2,
176     V(4,K) = 8*(K*K+2)*K/3,
177     V(5,K) = ((4*K*K+20)*K*K+6)/3,
178    for all K>0.
179   This allows us to derive O(N) encoding and O(N*log(K)) decoding routines for
180    small N (and indeed decoding is also O(N) for N<3).
181
182   @ARTICLE{Fis86,
183     author="Thomas R. Fischer",
184     title="A Pyramid Vector Quantizer",
185     journal="IEEE Transactions on Information Theory",
186     volume="IT-32",
187     number=4,
188     pages="568--583",
189     month=Jul,
190     year=1986
191   }*/
192
193 #if !defined(SMALL_FOOTPRINT)
194
195 /*U(N,K) = U(K,N) := N>0?K>0?U(N-1,K)+U(N,K-1)+U(N-1,K-1):0:K>0?1:0*/
196 # define CELT_PVQ_U(_n,_k) (CELT_PVQ_U_ROW[IMIN(_n,_k)][IMAX(_n,_k)])
197 /*V(N,K) := U(N,K)+U(N,K+1) = the number of PVQ codewords for a band of size N
198    with K pulses allocated to it.*/
199 # define CELT_PVQ_V(_n,_k) (CELT_PVQ_U(_n,_k)+CELT_PVQ_U(_n,(_k)+1))
200
201 /*For each V(N,K) supported, we will access element U(min(N,K+1),max(N,K+1)).
202   Thus, the number of entries in row I is the larger of the maximum number of
203    pulses we will ever allocate for a given N=I (K=128, or however many fit in
204    32 bits, whichever is smaller), plus one, and the maximum N for which
205    K=I-1 pulses fit in 32 bits.
206   The largest band size in an Opus Custom mode is 208.
207   Otherwise, we can limit things to the set of N which can be achieved by
208    splitting a band from a standard Opus mode: 176, 144, 96, 88, 72, 64, 48,
209    44, 36, 32, 24, 22, 18, 16, 8, 4, 2).*/
210 #if defined(CUSTOM_MODES)
211 static const opus_uint32 CELT_PVQ_U_DATA[1488]={
212 #else
213 static const opus_uint32 CELT_PVQ_U_DATA[1272]={
214 #endif
215   /*N=0, K=0...176:*/
216   1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
217   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
218   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
219   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
220   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
221   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
222   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
223 #if defined(CUSTOM_MODES)
224   /*...208:*/
225   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
226   0, 0, 0, 0, 0, 0,
227 #endif
228   /*N=1, K=1...176:*/
229   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
230   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
231   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
232   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
233   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
234   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
235   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
236 #if defined(CUSTOM_MODES)
237   /*...208:*/
238   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
239   1, 1, 1, 1, 1, 1,
240 #endif
241   /*N=2, K=2...176:*/
242   3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
243   43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79,
244   81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113,
245   115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143,
246   145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173,
247   175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203,
248   205, 207, 209, 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233,
249   235, 237, 239, 241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261, 263,
250   265, 267, 269, 271, 273, 275, 277, 279, 281, 283, 285, 287, 289, 291, 293,
251   295, 297, 299, 301, 303, 305, 307, 309, 311, 313, 315, 317, 319, 321, 323,
252   325, 327, 329, 331, 333, 335, 337, 339, 341, 343, 345, 347, 349, 351,
253 #if defined(CUSTOM_MODES)
254   /*...208:*/
255   353, 355, 357, 359, 361, 363, 365, 367, 369, 371, 373, 375, 377, 379, 381,
256   383, 385, 387, 389, 391, 393, 395, 397, 399, 401, 403, 405, 407, 409, 411,
257   413, 415,
258 #endif
259   /*N=3, K=3...176:*/
260   13, 25, 41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613,
261   685, 761, 841, 925, 1013, 1105, 1201, 1301, 1405, 1513, 1625, 1741, 1861,
262   1985, 2113, 2245, 2381, 2521, 2665, 2813, 2965, 3121, 3281, 3445, 3613, 3785,
263   3961, 4141, 4325, 4513, 4705, 4901, 5101, 5305, 5513, 5725, 5941, 6161, 6385,
264   6613, 6845, 7081, 7321, 7565, 7813, 8065, 8321, 8581, 8845, 9113, 9385, 9661,
265   9941, 10225, 10513, 10805, 11101, 11401, 11705, 12013, 12325, 12641, 12961,
266   13285, 13613, 13945, 14281, 14621, 14965, 15313, 15665, 16021, 16381, 16745,
267   17113, 17485, 17861, 18241, 18625, 19013, 19405, 19801, 20201, 20605, 21013,
268   21425, 21841, 22261, 22685, 23113, 23545, 23981, 24421, 24865, 25313, 25765,
269   26221, 26681, 27145, 27613, 28085, 28561, 29041, 29525, 30013, 30505, 31001,
270   31501, 32005, 32513, 33025, 33541, 34061, 34585, 35113, 35645, 36181, 36721,
271   37265, 37813, 38365, 38921, 39481, 40045, 40613, 41185, 41761, 42341, 42925,
272   43513, 44105, 44701, 45301, 45905, 46513, 47125, 47741, 48361, 48985, 49613,
273   50245, 50881, 51521, 52165, 52813, 53465, 54121, 54781, 55445, 56113, 56785,
274   57461, 58141, 58825, 59513, 60205, 60901, 61601,
275 #if defined(CUSTOM_MODES)
276   /*...208:*/
277   62305, 63013, 63725, 64441, 65161, 65885, 66613, 67345, 68081, 68821, 69565,
278   70313, 71065, 71821, 72581, 73345, 74113, 74885, 75661, 76441, 77225, 78013,
279   78805, 79601, 80401, 81205, 82013, 82825, 83641, 84461, 85285, 86113,
280 #endif
281   /*N=4, K=4...176:*/
282   63, 129, 231, 377, 575, 833, 1159, 1561, 2047, 2625, 3303, 4089, 4991, 6017,
283   7175, 8473, 9919, 11521, 13287, 15225, 17343, 19649, 22151, 24857, 27775,
284   30913, 34279, 37881, 41727, 45825, 50183, 54809, 59711, 64897, 70375, 76153,
285   82239, 88641, 95367, 102425, 109823, 117569, 125671, 134137, 142975, 152193,
286   161799, 171801, 182207, 193025, 204263, 215929, 228031, 240577, 253575,
287   267033, 280959, 295361, 310247, 325625, 341503, 357889, 374791, 392217,
288   410175, 428673, 447719, 467321, 487487, 508225, 529543, 551449, 573951,
289   597057, 620775, 645113, 670079, 695681, 721927, 748825, 776383, 804609,
290   833511, 863097, 893375, 924353, 956039, 988441, 1021567, 1055425, 1090023,
291   1125369, 1161471, 1198337, 1235975, 1274393, 1313599, 1353601, 1394407,
292   1436025, 1478463, 1521729, 1565831, 1610777, 1656575, 1703233, 1750759,
293   1799161, 1848447, 1898625, 1949703, 2001689, 2054591, 2108417, 2163175,
294   2218873, 2275519, 2333121, 2391687, 2451225, 2511743, 2573249, 2635751,
295   2699257, 2763775, 2829313, 2895879, 2963481, 3032127, 3101825, 3172583,
296   3244409, 3317311, 3391297, 3466375, 3542553, 3619839, 3698241, 3777767,
297   3858425, 3940223, 4023169, 4107271, 4192537, 4278975, 4366593, 4455399,
298   4545401, 4636607, 4729025, 4822663, 4917529, 5013631, 5110977, 5209575,
299   5309433, 5410559, 5512961, 5616647, 5721625, 5827903, 5935489, 6044391,
300   6154617, 6266175, 6379073, 6493319, 6608921, 6725887, 6844225, 6963943,
301   7085049, 7207551,
302 #if defined(CUSTOM_MODES)
303   /*...208:*/
304   7331457, 7456775, 7583513, 7711679, 7841281, 7972327, 8104825, 8238783,
305   8374209, 8511111, 8649497, 8789375, 8930753, 9073639, 9218041, 9363967,
306   9511425, 9660423, 9810969, 9963071, 10116737, 10271975, 10428793, 10587199,
307   10747201, 10908807, 11072025, 11236863, 11403329, 11571431, 11741177,
308   11912575,
309 #endif
310   /*N=5, K=5...176:*/
311   321, 681, 1289, 2241, 3649, 5641, 8361, 11969, 16641, 22569, 29961, 39041,
312   50049, 63241, 78889, 97281, 118721, 143529, 172041, 204609, 241601, 283401,
313   330409, 383041, 441729, 506921, 579081, 658689, 746241, 842249, 947241,
314   1061761, 1186369, 1321641, 1468169, 1626561, 1797441, 1981449, 2179241,
315   2391489, 2618881, 2862121, 3121929, 3399041, 3694209, 4008201, 4341801,
316   4695809, 5071041, 5468329, 5888521, 6332481, 6801089, 7295241, 7815849,
317   8363841, 8940161, 9545769, 10181641, 10848769, 11548161, 12280841, 13047849,
318   13850241, 14689089, 15565481, 16480521, 17435329, 18431041, 19468809,
319   20549801, 21675201, 22846209, 24064041, 25329929, 26645121, 28010881,
320   29428489, 30899241, 32424449, 34005441, 35643561, 37340169, 39096641,
321   40914369, 42794761, 44739241, 46749249, 48826241, 50971689, 53187081,
322   55473921, 57833729, 60268041, 62778409, 65366401, 68033601, 70781609,
323   73612041, 76526529, 79526721, 82614281, 85790889, 89058241, 92418049,
324   95872041, 99421961, 103069569, 106816641, 110664969, 114616361, 118672641,
325   122835649, 127107241, 131489289, 135983681, 140592321, 145317129, 150160041,
326   155123009, 160208001, 165417001, 170752009, 176215041, 181808129, 187533321,
327   193392681, 199388289, 205522241, 211796649, 218213641, 224775361, 231483969,
328   238341641, 245350569, 252512961, 259831041, 267307049, 274943241, 282741889,
329   290705281, 298835721, 307135529, 315607041, 324252609, 333074601, 342075401,
330   351257409, 360623041, 370174729, 379914921, 389846081, 399970689, 410291241,
331   420810249, 431530241, 442453761, 453583369, 464921641, 476471169, 488234561,
332   500214441, 512413449, 524834241, 537479489, 550351881, 563454121, 576788929,
333   590359041, 604167209, 618216201, 632508801,
334 #if defined(CUSTOM_MODES)
335   /*...208:*/
336   647047809, 661836041, 676876329, 692171521, 707724481, 723538089, 739615241,
337   755958849, 772571841, 789457161, 806617769, 824056641, 841776769, 859781161,
338   878072841, 896654849, 915530241, 934702089, 954173481, 973947521, 994027329,
339   1014416041, 1035116809, 1056132801, 1077467201, 1099123209, 1121104041,
340   1143412929, 1166053121, 1189027881, 1212340489, 1235994241,
341 #endif
342   /*N=6, K=6...96:*/
343   1683, 3653, 7183, 13073, 22363, 36365, 56695, 85305, 124515, 177045, 246047,
344   335137, 448427, 590557, 766727, 982729, 1244979, 1560549, 1937199, 2383409,
345   2908411, 3522221, 4235671, 5060441, 6009091, 7095093, 8332863, 9737793,
346   11326283, 13115773, 15124775, 17372905, 19880915, 22670725, 25765455,
347   29189457, 32968347, 37129037, 41699767, 46710137, 52191139, 58175189,
348   64696159, 71789409, 79491819, 87841821, 96879431, 106646281, 117185651,
349   128542501, 140763503, 153897073, 167993403, 183104493, 199284183, 216588185,
350   235074115, 254801525, 275831935, 298228865, 322057867, 347386557, 374284647,
351   402823977, 433078547, 465124549, 499040399, 534906769, 572806619, 612825229,
352   655050231, 699571641, 746481891, 795875861, 847850911, 902506913, 959946283,
353   1020274013, 1083597703, 1150027593, 1219676595, 1292660325, 1369097135,
354   1449108145, 1532817275, 1620351277, 1711839767, 1807415257, 1907213187,
355   2011371957, 2120032959,
356 #if defined(CUSTOM_MODES)
357   /*...109:*/
358   2233340609U, 2351442379U, 2474488829U, 2602633639U, 2736033641U, 2874848851U,
359   3019242501U, 3169381071U, 3325434321U, 3487575323U, 3655980493U, 3830829623U,
360   4012305913U,
361 #endif
362   /*N=7, K=7...54*/
363   8989, 19825, 40081, 75517, 134245, 227305, 369305, 579125, 880685, 1303777,
364   1884961, 2668525, 3707509, 5064793, 6814249, 9041957, 11847485, 15345233,
365   19665841, 24957661, 31388293, 39146185, 48442297, 59511829, 72616013,
366   88043969, 106114625, 127178701, 151620757, 179861305, 212358985, 249612805,
367   292164445, 340600625, 395555537, 457713341, 527810725, 606639529, 695049433,
368   793950709, 904317037, 1027188385, 1163673953, 1314955181, 1482288821,
369   1667010073, 1870535785, 2094367717,
370 #if defined(CUSTOM_MODES)
371   /*...60:*/
372   2340095869U, 2609401873U, 2904062449U, 3225952925U, 3577050821U, 3959439497U,
373 #endif
374   /*N=8, K=8...37*/
375   48639, 108545, 224143, 433905, 795455, 1392065, 2340495, 3800305, 5984767,
376   9173505, 13726991, 20103025, 28875327, 40754369, 56610575, 77500017,
377   104692735, 139703809, 184327311, 240673265, 311207743, 398796225, 506750351,
378   638878193, 799538175, 993696769, 1226990095, 1505789553, 1837271615,
379   2229491905U,
380 #if defined(CUSTOM_MODES)
381   /*...40:*/
382   2691463695U, 3233240945U, 3866006015U,
383 #endif
384   /*N=9, K=9...28:*/
385   265729, 598417, 1256465, 2485825, 4673345, 8405905, 14546705, 24331777,
386   39490049, 62390545, 96220561, 145198913, 214828609, 312193553, 446304145,
387   628496897, 872893441, 1196924561, 1621925137, 2173806145U,
388 #if defined(CUSTOM_MODES)
389   /*...29:*/
390   2883810113U,
391 #endif
392   /*N=10, K=10...24:*/
393   1462563, 3317445, 7059735, 14218905, 27298155, 50250765, 89129247, 152951073,
394   254831667, 413442773, 654862247, 1014889769, 1541911931, 2300409629U,
395   3375210671U,
396   /*N=11, K=11...19:*/
397   8097453, 18474633, 39753273, 81270333, 158819253, 298199265, 540279585,
398   948062325, 1616336765,
399 #if defined(CUSTOM_MODES)
400   /*...20:*/
401   2684641785U,
402 #endif
403   /*N=12, K=12...18:*/
404   45046719, 103274625, 224298231, 464387817, 921406335, 1759885185,
405   3248227095U,
406   /*N=13, K=13...16:*/
407   251595969, 579168825, 1267854873, 2653649025U,
408   /*N=14, K=14:*/
409   1409933619
410 };
411
412 #if defined(CUSTOM_MODES)
413 static const opus_uint32 *const CELT_PVQ_U_ROW[15]={
414   CELT_PVQ_U_DATA+   0,CELT_PVQ_U_DATA+ 208,CELT_PVQ_U_DATA+ 415,
415   CELT_PVQ_U_DATA+ 621,CELT_PVQ_U_DATA+ 826,CELT_PVQ_U_DATA+1030,
416   CELT_PVQ_U_DATA+1233,CELT_PVQ_U_DATA+1336,CELT_PVQ_U_DATA+1389,
417   CELT_PVQ_U_DATA+1421,CELT_PVQ_U_DATA+1441,CELT_PVQ_U_DATA+1455,
418   CELT_PVQ_U_DATA+1464,CELT_PVQ_U_DATA+1470,CELT_PVQ_U_DATA+1473
419 };
420 #else
421 static const opus_uint32 *const CELT_PVQ_U_ROW[15]={
422   CELT_PVQ_U_DATA+   0,CELT_PVQ_U_DATA+ 176,CELT_PVQ_U_DATA+ 351,
423   CELT_PVQ_U_DATA+ 525,CELT_PVQ_U_DATA+ 698,CELT_PVQ_U_DATA+ 870,
424   CELT_PVQ_U_DATA+1041,CELT_PVQ_U_DATA+1131,CELT_PVQ_U_DATA+1178,
425   CELT_PVQ_U_DATA+1207,CELT_PVQ_U_DATA+1226,CELT_PVQ_U_DATA+1240,
426   CELT_PVQ_U_DATA+1248,CELT_PVQ_U_DATA+1254,CELT_PVQ_U_DATA+1257
427 };
428 #endif
429
430 #if defined(CUSTOM_MODES)
431 void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
432   int k;
433   /*_maxk==0 => there's nothing to do.*/
434   celt_assert(_maxk>0);
435   _bits[0]=0;
436   for(k=1;k<=_maxk;k++)_bits[k]=log2_frac(CELT_PVQ_V(_n,k),_frac);
437 }
438 #endif
439
440 static opus_uint32 icwrs(int _n,const int *_y){
441   opus_uint32 i;
442   int         j;
443   int         k;
444   celt_assert(_n>=2);
445   j=_n-1;
446   i=_y[j]<0;
447   k=abs(_y[j]);
448   do{
449     j--;
450     i+=CELT_PVQ_U(_n-j,k);
451     k+=abs(_y[j]);
452     if(_y[j]<0)i+=CELT_PVQ_U(_n-j,k+1);
453   }
454   while(j>0);
455   return i;
456 }
457
458 void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
459   celt_assert(_k>0);
460   ec_enc_uint(_enc,icwrs(_n,_y),CELT_PVQ_V(_n,_k));
461 }
462
463 static opus_val32 cwrsi(int _n,int _k,opus_uint32 _i,int *_y){
464   opus_uint32 p;
465   int         s;
466   int         k0;
467   opus_int16  val;
468   opus_val32  yy=0;
469   celt_assert(_k>0);
470   celt_assert(_n>1);
471   while(_n>2){
472     opus_uint32 q;
473     /*Lots of pulses case:*/
474     if(_k>=_n){
475       const opus_uint32 *row;
476       row=CELT_PVQ_U_ROW[_n];
477       /*Are the pulses in this dimension negative?*/
478       p=row[_k+1];
479       s=-(_i>=p);
480       _i-=p&s;
481       /*Count how many pulses were placed in this dimension.*/
482       k0=_k;
483       q=row[_n];
484       if(q>_i){
485         celt_sig_assert(p>q);
486         _k=_n;
487         do p=CELT_PVQ_U_ROW[--_k][_n];
488         while(p>_i);
489       }
490       else for(p=row[_k];p>_i;p=row[_k])_k--;
491       _i-=p;
492       val=(k0-_k+s)^s;
493       *_y++=val;
494       yy=MAC16_16(yy,val,val);
495     }
496     /*Lots of dimensions case:*/
497     else{
498       /*Are there any pulses in this dimension at all?*/
499       p=CELT_PVQ_U_ROW[_k][_n];
500       q=CELT_PVQ_U_ROW[_k+1][_n];
501       if(p<=_i&&_i<q){
502         _i-=p;
503         *_y++=0;
504       }
505       else{
506         /*Are the pulses in this dimension negative?*/
507         s=-(_i>=q);
508         _i-=q&s;
509         /*Count how many pulses were placed in this dimension.*/
510         k0=_k;
511         do p=CELT_PVQ_U_ROW[--_k][_n];
512         while(p>_i);
513         _i-=p;
514         val=(k0-_k+s)^s;
515         *_y++=val;
516         yy=MAC16_16(yy,val,val);
517       }
518     }
519     _n--;
520   }
521   /*_n==2*/
522   p=2*_k+1;
523   s=-(_i>=p);
524   _i-=p&s;
525   k0=_k;
526   _k=(_i+1)>>1;
527   if(_k)_i-=2*_k-1;
528   val=(k0-_k+s)^s;
529   *_y++=val;
530   yy=MAC16_16(yy,val,val);
531   /*_n==1*/
532   s=-(int)_i;
533   val=(_k+s)^s;
534   *_y=val;
535   yy=MAC16_16(yy,val,val);
536   return yy;
537 }
538
539 opus_val32 decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
540   return cwrsi(_n,_k,ec_dec_uint(_dec,CELT_PVQ_V(_n,_k)),_y);
541 }
542
543 #else /* SMALL_FOOTPRINT */
544
545 /*Computes the next row/column of any recurrence that obeys the relation
546    u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
547   _ui0 is the base case for the new row/column.*/
548 static OPUS_INLINE void unext(opus_uint32 *_ui,unsigned _len,opus_uint32 _ui0){
549   opus_uint32 ui1;
550   unsigned      j;
551   /*This do-while will overrun the array if we don't have storage for at least
552      2 values.*/
553   j=1; do {
554     ui1=UADD32(UADD32(_ui[j],_ui[j-1]),_ui0);
555     _ui[j-1]=_ui0;
556     _ui0=ui1;
557   } while (++j<_len);
558   _ui[j-1]=_ui0;
559 }
560
561 /*Computes the previous row/column of any recurrence that obeys the relation
562    u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
563   _ui0 is the base case for the new row/column.*/
564 static OPUS_INLINE void uprev(opus_uint32 *_ui,unsigned _n,opus_uint32 _ui0){
565   opus_uint32 ui1;
566   unsigned      j;
567   /*This do-while will overrun the array if we don't have storage for at least
568      2 values.*/
569   j=1; do {
570     ui1=USUB32(USUB32(_ui[j],_ui[j-1]),_ui0);
571     _ui[j-1]=_ui0;
572     _ui0=ui1;
573   } while (++j<_n);
574   _ui[j-1]=_ui0;
575 }
576
577 /*Compute V(_n,_k), as well as U(_n,0..._k+1).
578   _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
579 static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
580   opus_uint32 um2;
581   unsigned      len;
582   unsigned      k;
583   len=_k+2;
584   /*We require storage at least 3 values (e.g., _k>0).*/
585   celt_assert(len>=3);
586   _u[0]=0;
587   _u[1]=um2=1;
588   /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
589   /*If _n==1, _u[i] should be 1 for i>1.*/
590   celt_assert(_n>=2);
591   /*If _k==0, the following do-while loop will overflow the buffer.*/
592   celt_assert(_k>0);
593   k=2;
594   do _u[k]=(k<<1)-1;
595   while(++k<len);
596   for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
597   return _u[_k]+_u[_k+1];
598 }
599
600 /*Returns the _i'th combination of _k elements chosen from a set of size _n
601    with associated sign bits.
602   _y: Returns the vector of pulses.
603   _u: Must contain entries [0..._k+1] of row _n of U() on input.
604       Its contents will be destructively modified.*/
605 static opus_val32 cwrsi(int _n,int _k,opus_uint32 _i,int *_y,opus_uint32 *_u){
606   int j;
607   opus_int16 val;
608   opus_val32 yy=0;
609   celt_assert(_n>0);
610   j=0;
611   do{
612     opus_uint32 p;
613     int           s;
614     int           yj;
615     p=_u[_k+1];
616     s=-(_i>=p);
617     _i-=p&s;
618     yj=_k;
619     p=_u[_k];
620     while(p>_i)p=_u[--_k];
621     _i-=p;
622     yj-=_k;
623     val=(yj+s)^s;
624     _y[j]=val;
625     yy=MAC16_16(yy,val,val);
626     uprev(_u,_k+2,0);
627   }
628   while(++j<_n);
629   return yy;
630 }
631
632 /*Returns the index of the given combination of K elements chosen from a set
633    of size 1 with associated sign bits.
634   _y: The vector of pulses, whose sum of absolute values is K.
635   _k: Returns K.*/
636 static OPUS_INLINE opus_uint32 icwrs1(const int *_y,int *_k){
637   *_k=abs(_y[0]);
638   return _y[0]<0;
639 }
640
641 /*Returns the index of the given combination of K elements chosen from a set
642    of size _n with associated sign bits.
643   _y:  The vector of pulses, whose sum of absolute values must be _k.
644   _nc: Returns V(_n,_k).*/
645 static OPUS_INLINE opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y,
646  opus_uint32 *_u){
647   opus_uint32 i;
648   int         j;
649   int         k;
650   /*We can't unroll the first two iterations of the loop unless _n>=2.*/
651   celt_assert(_n>=2);
652   _u[0]=0;
653   for(k=1;k<=_k+1;k++)_u[k]=(k<<1)-1;
654   i=icwrs1(_y+_n-1,&k);
655   j=_n-2;
656   i+=_u[k];
657   k+=abs(_y[j]);
658   if(_y[j]<0)i+=_u[k+1];
659   while(j-->0){
660     unext(_u,_k+2,0);
661     i+=_u[k];
662     k+=abs(_y[j]);
663     if(_y[j]<0)i+=_u[k+1];
664   }
665   *_nc=_u[k]+_u[k+1];
666   return i;
667 }
668
669 #ifdef CUSTOM_MODES
670 void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
671   int k;
672   /*_maxk==0 => there's nothing to do.*/
673   celt_assert(_maxk>0);
674   _bits[0]=0;
675   if (_n==1)
676   {
677     for (k=1;k<=_maxk;k++)
678       _bits[k] = 1<<_frac;
679   }
680   else {
681     VARDECL(opus_uint32,u);
682     SAVE_STACK;
683     ALLOC(u,_maxk+2U,opus_uint32);
684     ncwrs_urow(_n,_maxk,u);
685     for(k=1;k<=_maxk;k++)
686       _bits[k]=log2_frac(u[k]+u[k+1],_frac);
687     RESTORE_STACK;
688   }
689 }
690 #endif /* CUSTOM_MODES */
691
692 void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
693   opus_uint32 i;
694   VARDECL(opus_uint32,u);
695   opus_uint32 nc;
696   SAVE_STACK;
697   celt_assert(_k>0);
698   ALLOC(u,_k+2U,opus_uint32);
699   i=icwrs(_n,_k,&nc,_y,u);
700   ec_enc_uint(_enc,i,nc);
701   RESTORE_STACK;
702 }
703
704 opus_val32 decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
705   VARDECL(opus_uint32,u);
706   int ret;
707   SAVE_STACK;
708   celt_assert(_k>0);
709   ALLOC(u,_k+2U,opus_uint32);
710   ret = cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
711   RESTORE_STACK;
712   return ret;
713 }
714
715 #endif /* SMALL_FOOTPRINT */