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 */
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
10 - Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
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.
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.
34 #include "os_support.h"
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
)
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;
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.*/
63 val
=(val
*val
+0x7FFF)>>15;
66 /*If val is not exactly 0x8000, then we have to round up the remainder.*/
67 return l
+(val
>0x8000);
69 /*Exact powers of two require no rounding.*/
70 else return (l
-1)<<frac
;
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.
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).
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:
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}
103 U(N,K) = the number of such combinations wherein N-1 objects are taken at
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,
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:
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}
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)
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
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).
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.
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)
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)
162 Similar relations can be derived for V(N,K), but are not used here.
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.
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,
176 V(4,K) = 8*(K*K+2)*K/3,
177 V(5,K) = ((4*K*K+20)*K*K+6)/3,
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).
183 author="Thomas R. Fischer",
184 title="A Pyramid Vector Quantizer",
185 journal="IEEE Transactions on Information Theory",
193 #if !defined(SMALL_FOOTPRINT)
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))
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]={
213 static const opus_uint32 CELT_PVQ_U_DATA
[1272]={
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)
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,
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)
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,
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)
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,
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)
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,
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,
302 #if defined(CUSTOM_MODES)
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,
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)
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,
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)
358 2233340609U, 2351442379U, 2474488829U, 2602633639U, 2736033641U, 2874848851U,
359 3019242501U, 3169381071U, 3325434321U, 3487575323U, 3655980493U, 3830829623U,
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)
372 2340095869U, 2609401873U, 2904062449U, 3225952925U, 3577050821U, 3959439497U,
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,
380 #if defined(CUSTOM_MODES)
382 2691463695U, 3233240945U, 3866006015U,
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)
393 1462563, 3317445, 7059735, 14218905, 27298155, 50250765, 89129247, 152951073,
394 254831667, 413442773, 654862247, 1014889769, 1541911931, 2300409629U,
397 8097453, 18474633, 39753273, 81270333, 158819253, 298199265, 540279585,
398 948062325, 1616336765,
399 #if defined(CUSTOM_MODES)
404 45046719, 103274625, 224298231, 464387817, 921406335, 1759885185,
407 251595969, 579168825, 1267854873, 2653649025U,
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
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
430 #if defined(CUSTOM_MODES)
431 void get_required_bits(opus_int16
*_bits
,int _n
,int _maxk
,int _frac
){
433 /*_maxk==0 => there's nothing to do.*/
434 celt_assert(_maxk
>0);
436 for(k
=1;k
<=_maxk
;k
++)_bits
[k
]=log2_frac(CELT_PVQ_V(_n
,k
),_frac
);
440 static opus_uint32
icwrs(int _n
,const int *_y
){
450 i
+=CELT_PVQ_U(_n
-j
,k
);
452 if(_y
[j
]<0)i
+=CELT_PVQ_U(_n
-j
,k
+1);
458 void encode_pulses(const int *_y
,int _n
,int _k
,ec_enc
*_enc
){
460 ec_enc_uint(_enc
,icwrs(_n
,_y
),CELT_PVQ_V(_n
,_k
));
463 static void cwrsi(int _n
,int _k
,opus_uint32 _i
,int *_y
){
471 /*Lots of pulses case:*/
473 const opus_uint32
*row
;
474 row
=CELT_PVQ_U_ROW
[_n
];
475 /*Are the pulses in this dimension negative?*/
479 /*Count how many pulses were placed in this dimension.*/
485 do p
=CELT_PVQ_U_ROW
[--_k
][_n
];
488 else for(p
=row
[_k
];p
>_i
;p
=row
[_k
])_k
--;
492 /*Lots of dimensions case:*/
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
];
502 /*Are the pulses in this dimension negative?*/
505 /*Count how many pulses were placed in this dimension.*/
507 do p
=CELT_PVQ_U_ROW
[--_k
][_n
];
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
);
532 #else /* SMALL_FOOTPRINT */
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.*/
537 static OPUS_INLINE
void unext(opus_uint32
*_ui
,unsigned _len
,opus_uint32 _ui0
){
540 /*This do-while will overrun the array if we don't have storage for at least
543 ui1
=UADD32(UADD32(_ui
[j
],_ui
[j
-1]),_ui0
);
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.*/
553 static OPUS_INLINE
void uprev(opus_uint32
*_ui
,unsigned _n
,opus_uint32 _ui0
){
556 /*This do-while will overrun the array if we don't have storage for at least
559 ui1
=USUB32(USUB32(_ui
[j
],_ui
[j
-1]),_ui0
);
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].*/
568 static opus_uint32
ncwrs_urow(unsigned _n
,unsigned _k
,opus_uint32
*_u
){
573 /*We require storage at least 3 values (e.g., _k>0).*/
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.*/
580 /*If _k==0, the following do-while loop will overflow the buffer.*/
585 for(k
=2;k
<_n
;k
++)unext(_u
+1,_k
+1,1);
586 return _u
[_k
]+_u
[_k
+1];
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.*/
594 static void cwrsi(int _n
,int _k
,opus_uint32 _i
,int *_y
,opus_uint32
*_u
){
607 while(p
>_i
)p
=_u
[--_k
];
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.
620 static OPUS_INLINE opus_uint32
icwrs1(const int *_y
,int *_k
){
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).*/
629 static OPUS_INLINE opus_uint32
icwrs(int _n
,int _k
,opus_uint32
*_nc
,const int *_y
,
634 /*We can't unroll the first two iterations of the loop unless _n>=2.*/
637 for(k
=1;k
<=_k
+1;k
++)_u
[k
]=(k
<<1)-1;
638 i
=icwrs1(_y
+_n
-1,&k
);
642 if(_y
[j
]<0)i
+=_u
[k
+1];
647 if(_y
[j
]<0)i
+=_u
[k
+1];
654 void get_required_bits(opus_int16
*_bits
,int _n
,int _maxk
,int _frac
){
656 /*_maxk==0 => there's nothing to do.*/
657 celt_assert(_maxk
>0);
661 for (k
=1;k
<=_maxk
;k
++)
665 VARDECL(opus_uint32
,u
);
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
);
674 #endif /* CUSTOM_MODES */
676 void encode_pulses(const int *_y
,int _n
,int _k
,ec_enc
*_enc
){
678 VARDECL(opus_uint32
,u
);
682 ALLOC(u
,_k
+2U,opus_uint32
);
683 i
=icwrs(_n
,_k
,&nc
,_y
,u
);
684 ec_enc_uint(_enc
,i
,nc
);
688 void decode_pulses(int *_y
,int _n
,int _k
,ec_dec
*_dec
){
689 VARDECL(opus_uint32
,u
);
692 ALLOC(u
,_k
+2U,opus_uint32
);
693 cwrsi(_n
,_k
,ec_dec_uint(_dec
,ncwrs_urow(_n
,_k
,u
)),_y
,u
);
697 #endif /* SMALL_FOOTPRINT */