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