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.*/
log2_frac(opus_uint32 val,int frac)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    http://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)
get_required_bits(opus_int16 * _bits,int _n,int _maxk,int _frac)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 
icwrs(int _n,const int * _y)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 
encode_pulses(const int * _y,int _n,int _k,ec_enc * _enc)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 
cwrsi(int _n,int _k,opus_uint32 _i,int * _y)463 static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y){
464   opus_uint32 p;
465   int         s;
466   int         k0;
467   celt_assert(_k>0);
468   celt_assert(_n>1);
469   while(_n>2){
470     opus_uint32 q;
471     /*Lots of pulses case:*/
472     if(_k>=_n){
473       const opus_uint32 *row;
474       row=CELT_PVQ_U_ROW[_n];
475       /*Are the pulses in this dimension negative?*/
476       p=row[_k+1];
477       s=-(_i>=p);
478       _i-=p&s;
479       /*Count how many pulses were placed in this dimension.*/
480       k0=_k;
481       q=row[_n];
482       if(q>_i){
483         celt_assert(p>q);
484         _k=_n;
485         do p=CELT_PVQ_U_ROW[--_k][_n];
486         while(p>_i);
487       }
488       else for(p=row[_k];p>_i;p=row[_k])_k--;
489       _i-=p;
490       *_y++=(k0-_k+s)^s;
491     }
492     /*Lots of dimensions case:*/
493     else{
494       /*Are there any pulses in this dimension at all?*/
495       p=CELT_PVQ_U_ROW[_k][_n];
496       q=CELT_PVQ_U_ROW[_k+1][_n];
497       if(p<=_i&&_i<q){
498         _i-=p;
499         *_y++=0;
500       }
501       else{
502         /*Are the pulses in this dimension negative?*/
503         s=-(_i>=q);
504         _i-=q&s;
505         /*Count how many pulses were placed in this dimension.*/
506         k0=_k;
507         do p=CELT_PVQ_U_ROW[--_k][_n];
508         while(p>_i);
509         _i-=p;
510         *_y++=(k0-_k+s)^s;
511       }
512     }
513     _n--;
514   }
515   /*_n==2*/
516   p=2*_k+1;
517   s=-(_i>=p);
518   _i-=p&s;
519   k0=_k;
520   _k=(_i+1)>>1;
521   if(_k)_i-=2*_k-1;
522   *_y++=(k0-_k+s)^s;
523   /*_n==1*/
524   s=-(int)_i;
525   *_y=(_k+s)^s;
526 }
527 
decode_pulses(int * _y,int _n,int _k,ec_dec * _dec)528 void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
529   cwrsi(_n,_k,ec_dec_uint(_dec,CELT_PVQ_V(_n,_k)),_y);
530 }
531 
532 #else /* SMALL_FOOTPRINT */
533 
534 /*Computes the next row/column of any recurrence that obeys the relation
535    u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
536   _ui0 is the base case for the new row/column.*/
unext(opus_uint32 * _ui,unsigned _len,opus_uint32 _ui0)537 static OPUS_INLINE void unext(opus_uint32 *_ui,unsigned _len,opus_uint32 _ui0){
538   opus_uint32 ui1;
539   unsigned      j;
540   /*This do-while will overrun the array if we don't have storage for at least
541      2 values.*/
542   j=1; do {
543     ui1=UADD32(UADD32(_ui[j],_ui[j-1]),_ui0);
544     _ui[j-1]=_ui0;
545     _ui0=ui1;
546   } while (++j<_len);
547   _ui[j-1]=_ui0;
548 }
549 
550 /*Computes the previous row/column of any recurrence that obeys the relation
551    u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
552   _ui0 is the base case for the new row/column.*/
uprev(opus_uint32 * _ui,unsigned _n,opus_uint32 _ui0)553 static OPUS_INLINE void uprev(opus_uint32 *_ui,unsigned _n,opus_uint32 _ui0){
554   opus_uint32 ui1;
555   unsigned      j;
556   /*This do-while will overrun the array if we don't have storage for at least
557      2 values.*/
558   j=1; do {
559     ui1=USUB32(USUB32(_ui[j],_ui[j-1]),_ui0);
560     _ui[j-1]=_ui0;
561     _ui0=ui1;
562   } while (++j<_n);
563   _ui[j-1]=_ui0;
564 }
565 
566 /*Compute V(_n,_k), as well as U(_n,0..._k+1).
567   _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 * _u)568 static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
569   opus_uint32 um2;
570   unsigned      len;
571   unsigned      k;
572   len=_k+2;
573   /*We require storage at least 3 values (e.g., _k>0).*/
574   celt_assert(len>=3);
575   _u[0]=0;
576   _u[1]=um2=1;
577   /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
578   /*If _n==1, _u[i] should be 1 for i>1.*/
579   celt_assert(_n>=2);
580   /*If _k==0, the following do-while loop will overflow the buffer.*/
581   celt_assert(_k>0);
582   k=2;
583   do _u[k]=(k<<1)-1;
584   while(++k<len);
585   for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
586   return _u[_k]+_u[_k+1];
587 }
588 
589 /*Returns the _i'th combination of _k elements chosen from a set of size _n
590    with associated sign bits.
591   _y: Returns the vector of pulses.
592   _u: Must contain entries [0..._k+1] of row _n of U() on input.
593       Its contents will be destructively modified.*/
cwrsi(int _n,int _k,opus_uint32 _i,int * _y,opus_uint32 * _u)594 static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y,opus_uint32 *_u){
595   int j;
596   celt_assert(_n>0);
597   j=0;
598   do{
599     opus_uint32 p;
600     int           s;
601     int           yj;
602     p=_u[_k+1];
603     s=-(_i>=p);
604     _i-=p&s;
605     yj=_k;
606     p=_u[_k];
607     while(p>_i)p=_u[--_k];
608     _i-=p;
609     yj-=_k;
610     _y[j]=(yj+s)^s;
611     uprev(_u,_k+2,0);
612   }
613   while(++j<_n);
614 }
615 
616 /*Returns the index of the given combination of K elements chosen from a set
617    of size 1 with associated sign bits.
618   _y: The vector of pulses, whose sum of absolute values is K.
619   _k: Returns K.*/
icwrs1(const int * _y,int * _k)620 static OPUS_INLINE opus_uint32 icwrs1(const int *_y,int *_k){
621   *_k=abs(_y[0]);
622   return _y[0]<0;
623 }
624 
625 /*Returns the index of the given combination of K elements chosen from a set
626    of size _n with associated sign bits.
627   _y:  The vector of pulses, whose sum of absolute values must be _k.
628   _nc: Returns V(_n,_k).*/
icwrs(int _n,int _k,opus_uint32 * _nc,const int * _y,opus_uint32 * _u)629 static OPUS_INLINE opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y,
630  opus_uint32 *_u){
631   opus_uint32 i;
632   int         j;
633   int         k;
634   /*We can't unroll the first two iterations of the loop unless _n>=2.*/
635   celt_assert(_n>=2);
636   _u[0]=0;
637   for(k=1;k<=_k+1;k++)_u[k]=(k<<1)-1;
638   i=icwrs1(_y+_n-1,&k);
639   j=_n-2;
640   i+=_u[k];
641   k+=abs(_y[j]);
642   if(_y[j]<0)i+=_u[k+1];
643   while(j-->0){
644     unext(_u,_k+2,0);
645     i+=_u[k];
646     k+=abs(_y[j]);
647     if(_y[j]<0)i+=_u[k+1];
648   }
649   *_nc=_u[k]+_u[k+1];
650   return i;
651 }
652 
653 #ifdef CUSTOM_MODES
get_required_bits(opus_int16 * _bits,int _n,int _maxk,int _frac)654 void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
655   int k;
656   /*_maxk==0 => there's nothing to do.*/
657   celt_assert(_maxk>0);
658   _bits[0]=0;
659   if (_n==1)
660   {
661     for (k=1;k<=_maxk;k++)
662       _bits[k] = 1<<_frac;
663   }
664   else {
665     VARDECL(opus_uint32,u);
666     SAVE_STACK;
667     ALLOC(u,_maxk+2U,opus_uint32);
668     ncwrs_urow(_n,_maxk,u);
669     for(k=1;k<=_maxk;k++)
670       _bits[k]=log2_frac(u[k]+u[k+1],_frac);
671     RESTORE_STACK;
672   }
673 }
674 #endif /* CUSTOM_MODES */
675 
encode_pulses(const int * _y,int _n,int _k,ec_enc * _enc)676 void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
677   opus_uint32 i;
678   VARDECL(opus_uint32,u);
679   opus_uint32 nc;
680   SAVE_STACK;
681   celt_assert(_k>0);
682   ALLOC(u,_k+2U,opus_uint32);
683   i=icwrs(_n,_k,&nc,_y,u);
684   ec_enc_uint(_enc,i,nc);
685   RESTORE_STACK;
686 }
687 
decode_pulses(int * _y,int _n,int _k,ec_dec * _dec)688 void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
689   VARDECL(opus_uint32,u);
690   SAVE_STACK;
691   celt_assert(_k>0);
692   ALLOC(u,_k+2U,opus_uint32);
693   cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
694   RESTORE_STACK;
695 }
696 
697 #endif /* SMALL_FOOTPRINT */
698