summaryrefslogtreecommitdiff
path: root/lib/rbcodec/codecs/libopus/celt/cwrs.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/rbcodec/codecs/libopus/celt/cwrs.c')
-rw-r--r--lib/rbcodec/codecs/libopus/celt/cwrs.c658
1 files changed, 354 insertions, 304 deletions
diff --git a/lib/rbcodec/codecs/libopus/celt/cwrs.c b/lib/rbcodec/codecs/libopus/celt/cwrs.c
index b8ade96fce..eb8fa1c807 100644
--- a/lib/rbcodec/codecs/libopus/celt/cwrs.c
+++ b/lib/rbcodec/codecs/libopus/celt/cwrs.c
@@ -28,14 +28,13 @@
28*/ 28*/
29 29
30#ifdef HAVE_CONFIG_H 30#ifdef HAVE_CONFIG_H
31#include "opus_config.h" 31#include "config.h"
32#endif 32#endif
33 33
34#include "os_support.h" 34#include "os_support.h"
35#include "cwrs.h" 35#include "cwrs.h"
36#include "mathops.h" 36#include "mathops.h"
37#include "arch.h" 37#include "arch.h"
38#include "rate.h"
39 38
40#ifdef CUSTOM_MODES 39#ifdef CUSTOM_MODES
41 40
@@ -72,64 +71,6 @@ int log2_frac(opus_uint32 val, int frac)
72} 71}
73#endif 72#endif
74 73
75#ifndef SMALL_FOOTPRINT
76
77#define MASK32 (0xFFFFFFFF)
78
79/*INV_TABLE[i] holds the multiplicative inverse of (2*i+1) mod 2**32.*/
80static const opus_uint32 INV_TABLE[53]={
81 0x00000001,0xAAAAAAAB,0xCCCCCCCD,0xB6DB6DB7,
82 0x38E38E39,0xBA2E8BA3,0xC4EC4EC5,0xEEEEEEEF,
83 0xF0F0F0F1,0x286BCA1B,0x3CF3CF3D,0xE9BD37A7,
84 0xC28F5C29,0x684BDA13,0x4F72C235,0xBDEF7BDF,
85 0x3E0F83E1,0x8AF8AF8B,0x914C1BAD,0x96F96F97,
86 0xC18F9C19,0x2FA0BE83,0xA4FA4FA5,0x677D46CF,
87 0x1A1F58D1,0xFAFAFAFB,0x8C13521D,0x586FB587,
88 0xB823EE09,0xA08AD8F3,0xC10C9715,0xBEFBEFBF,
89 0xC0FC0FC1,0x07A44C6B,0xA33F128D,0xE327A977,
90 0xC7E3F1F9,0x962FC963,0x3F2B3885,0x613716AF,
91 0x781948B1,0x2B2E43DB,0xFCFCFCFD,0x6FD0EB67,
92 0xFA3F47E9,0xD2FD2FD3,0x3F4FD3F5,0xD4E25B9F,
93 0x5F02A3A1,0xBF5A814B,0x7C32B16D,0xD3431B57,
94 0xD8FD8FD9,
95};
96
97/*Computes (_a*_b-_c)/(2*_d+1) when the quotient is known to be exact.
98 _a, _b, _c, and _d may be arbitrary so long as the arbitrary precision result
99 fits in 32 bits, but currently the table for multiplicative inverses is only
100 valid for _d<=52.*/
101static inline opus_uint32 imusdiv32odd(opus_uint32 _a,opus_uint32 _b,
102 opus_uint32 _c,int _d){
103 celt_assert(_d<=52);
104 return (_a*_b-_c)*INV_TABLE[_d]&MASK32;
105}
106
107/*Computes (_a*_b-_c)/_d when the quotient is known to be exact.
108 _d does not actually have to be even, but imusdiv32odd will be faster when
109 it's odd, so you should use that instead.
110 _a and _d are assumed to be small (e.g., _a*_d fits in 32 bits; currently the
111 table for multiplicative inverses is only valid for _d<=54).
112 _b and _c may be arbitrary so long as the arbitrary precision reuslt fits in
113 32 bits.*/
114static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
115 opus_uint32 _c,int _d){
116 opus_uint32 inv;
117 int mask;
118 int shift;
119 int one;
120 celt_assert(_d>0);
121 celt_assert(_d<=54);
122 shift=EC_ILOG(_d^(_d-1));
123 inv=INV_TABLE[(_d-1)>>shift];
124 shift--;
125 one=1<<shift;
126 mask=one-1;
127 return (_a*(_b>>shift)-(_c>>shift)+
128 ((_a*(_b&mask)+one-(_c&mask))>>shift)-1)*inv&MASK32;
129}
130
131#endif /* SMALL_FOOTPRINT */
132
133/*Although derived separately, the pulse vector coding scheme is equivalent to 74/*Although derived separately, the pulse vector coding scheme is equivalent to
134 a Pyramid Vector Quantizer \cite{Fis86}. 75 a Pyramid Vector Quantizer \cite{Fis86}.
135 Some additional notes about an early version appear at 76 Some additional notes about an early version appear at
@@ -249,46 +190,346 @@ static inline opus_uint32 imusdiv32even(opus_uint32 _a,opus_uint32 _b,
249 year=1986 190 year=1986
250 }*/ 191 }*/
251 192
252#ifndef SMALL_FOOTPRINT 193#if !defined(SMALL_FOOTPRINT)
253/*Compute U(2,_k). 194
254 Note that this may be called with _k=32768 (maxK[2]+1).*/ 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*/
255static inline unsigned ucwrs2(unsigned _k){ 196# define CELT_PVQ_U(_n,_k) (CELT_PVQ_U_ROW[IMIN(_n,_k)][IMAX(_n,_k)])
256 celt_assert(_k>0); 197/*V(N,K) := U(N,K)+U(N,K+1) = the number of PVQ codewords for a band of size N
257 return _k+(_k-1); 198 with K pulses allocated to it.*/
258} 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)
211static const opus_uint32 CELT_PVQ_U_DATA[1488]={
212#else
213static const opus_uint32 CELT_PVQ_U_DATA[1272] ICONST_ATTR ={
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};
259 411
260/*Compute V(2,_k).*/ 412#if defined(CUSTOM_MODES)
261static inline opus_uint32 ncwrs2(int _k){ 413const opus_uint32 *const CELT_PVQ_U_ROW[15]={
262 celt_assert(_k>0); 414 CELT_PVQ_U_DATA+ 0,CELT_PVQ_U_DATA+ 208,CELT_PVQ_U_DATA+ 415,
263 return 4*(opus_uint32)_k; 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
421const 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)
431void 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);
264} 437}
438#endif
265 439
266/*Compute U(3,_k). 440static opus_uint32 icwrs(int _n,const int *_y){
267 Note that this may be called with _k=32768 (maxK[3]+1).*/ 441 opus_uint32 i;
268static inline opus_uint32 ucwrs3(unsigned _k){ 442 int j;
269 celt_assert(_k>0); 443 int k;
270 return (2*(opus_uint32)_k-2)*_k+1; 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;
271} 456}
272 457
273/*Compute V(3,_k).*/ 458void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
274static inline opus_uint32 ncwrs3(int _k){
275 celt_assert(_k>0); 459 celt_assert(_k>0);
276 return 2*(2*(unsigned)_k*(opus_uint32)_k+1); 460 ec_enc_uint(_enc,icwrs(_n,_y),CELT_PVQ_V(_n,_k));
277} 461}
278 462
279/*Compute U(4,_k).*/ 463static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y){
280static inline opus_uint32 ucwrs4(int _k){ 464 opus_uint32 p;
465 int s;
466 int k0;
281 celt_assert(_k>0); 467 celt_assert(_k>0);
282 return imusdiv32odd(2*_k,(2*_k-3)*(opus_uint32)_k+4,3,1); 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;
283} 526}
284 527
285/*Compute V(4,_k).*/ 528void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
286static inline opus_uint32 ncwrs4(int _k){ 529 cwrsi(_n,_k,ec_dec_uint(_dec,CELT_PVQ_V(_n,_k)),_y);
287 celt_assert(_k>0);
288 return ((_k*(opus_uint32)_k+2)*_k)/3<<3;
289} 530}
290 531
291#endif /* SMALL_FOOTPRINT */ 532#else /* SMALL_FOOTPRINT */
292 533
293/*Computes the next row/column of any recurrence that obeys the relation 534/*Computes the next row/column of any recurrence that obeys the relation
294 u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1]. 535 u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
@@ -333,125 +574,18 @@ static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
333 celt_assert(len>=3); 574 celt_assert(len>=3);
334 _u[0]=0; 575 _u[0]=0;
335 _u[1]=um2=1; 576 _u[1]=um2=1;
336#ifndef SMALL_FOOTPRINT 577 /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
337 /*_k>52 doesn't work in the false branch due to the limits of INV_TABLE, 578 /*If _n==1, _u[i] should be 1 for i>1.*/
338 but _k isn't tested here because k<=52 for n=7*/ 579 celt_assert(_n>=2);
339 if(_n<=6) 580 /*If _k==0, the following do-while loop will overflow the buffer.*/
340#endif 581 celt_assert(_k>0);
341 { 582 k=2;
342 /*If _n==0, _u[0] should be 1 and the rest should be 0.*/ 583 do _u[k]=(k<<1)-1;
343 /*If _n==1, _u[i] should be 1 for i>1.*/ 584 while(++k<len);
344 celt_assert(_n>=2); 585 for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
345 /*If _k==0, the following do-while loop will overflow the buffer.*/
346 celt_assert(_k>0);
347 k=2;
348 do _u[k]=(k<<1)-1;
349 while(++k<len);
350 for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
351 }
352#ifndef SMALL_FOOTPRINT
353 else{
354 opus_uint32 um1;
355 opus_uint32 n2m1;
356 _u[2]=n2m1=um1=(_n<<1)-1;
357 for(k=3;k<len;k++){
358 /*U(N,K) = ((2*N-1)*U(N,K-1)-U(N,K-2))/(K-1) + U(N,K-2)*/
359 _u[k]=um2=imusdiv32even(n2m1,um1,um2,k-1)+um2;
360 if(++k>=len)break;
361 _u[k]=um1=imusdiv32odd(n2m1,um2,um1,(k-1)>>1)+um1;
362 }
363 }
364#endif /* SMALL_FOOTPRINT */
365 return _u[_k]+_u[_k+1]; 586 return _u[_k]+_u[_k+1];
366} 587}
367 588
368#ifndef SMALL_FOOTPRINT
369
370/*Returns the _i'th combination of _k elements (at most 32767) chosen from a
371 set of size 1 with associated sign bits.
372 _y: Returns the vector of pulses.*/
373static inline void cwrsi1(int _k,opus_uint32 _i,int *_y){
374 int s;
375 s=-(int)_i;
376 _y[0]=(_k+s)^s;
377}
378
379/*Returns the _i'th combination of _k elements (at most 32767) chosen from a
380 set of size 2 with associated sign bits.
381 _y: Returns the vector of pulses.*/
382static inline void cwrsi2(int _k,opus_uint32 _i,int *_y){
383 opus_uint32 p;
384 int s;
385 int yj;
386 p=ucwrs2(_k+1U);
387 s=-(_i>=p);
388 _i-=p&s;
389 yj=_k;
390 _k=(_i+1)>>1;
391 p=_k?ucwrs2(_k):0;
392 _i-=p;
393 yj-=_k;
394 _y[0]=(yj+s)^s;
395 cwrsi1(_k,_i,_y+1);
396}
397
398/*Returns the _i'th combination of _k elements (at most 32767) chosen from a
399 set of size 3 with associated sign bits.
400 _y: Returns the vector of pulses.*/
401static void cwrsi3(int _k,opus_uint32 _i,int *_y){
402 opus_uint32 p;
403 int s;
404 int yj;
405 p=ucwrs3(_k+1U);
406 s=-(_i>=p);
407 _i-=p&s;
408 yj=_k;
409 /*Finds the maximum _k such that ucwrs3(_k)<=_i (tested for all
410 _i<2147418113=U(3,32768)).*/
411 _k=_i>0?(isqrt32(2*_i-1)+1)>>1:0;
412 p=_k?ucwrs3(_k):0;
413 _i-=p;
414 yj-=_k;
415 _y[0]=(yj+s)^s;
416 cwrsi2(_k,_i,_y+1);
417}
418
419/*Returns the _i'th combination of _k elements (at most 1172) chosen from a set
420 of size 4 with associated sign bits.
421 _y: Returns the vector of pulses.*/
422static void cwrsi4(int _k,opus_uint32 _i,int *_y){
423 opus_uint32 p;
424 int s;
425 int yj;
426 int kl;
427 int kr;
428 p=ucwrs4(_k+1);
429 s=-(_i>=p);
430 _i-=p&s;
431 yj=_k;
432 /*We could solve a cubic for k here, but the form of the direct solution does
433 not lend itself well to exact integer arithmetic.
434 Instead we do a binary search on U(4,K).*/
435 kl=0;
436 kr=_k;
437 for(;;){
438 _k=(kl+kr)>>1;
439 p=_k?ucwrs4(_k):0;
440 if(p<_i){
441 if(_k>=kr)break;
442 kl=_k+1;
443 }
444 else if(p>_i)kr=_k-1;
445 else break;
446 }
447 _i-=p;
448 yj-=_k;
449 _y[0]=(yj+s)^s;
450 cwrsi3(_k,_i,_y+1);
451}
452
453#endif /* SMALL_FOOTPRINT */
454
455/*Returns the _i'th combination of _k elements chosen from a set of size _n 589/*Returns the _i'th combination of _k elements chosen from a set of size _n
456 with associated sign bits. 590 with associated sign bits.
457 _y: Returns the vector of pulses. 591 _y: Returns the vector of pulses.
@@ -488,55 +622,6 @@ static inline opus_uint32 icwrs1(const int *_y,int *_k){
488 return _y[0]<0; 622 return _y[0]<0;
489} 623}
490 624
491#ifndef SMALL_FOOTPRINT
492
493/*Returns the index of the given combination of K elements chosen from a set
494 of size 2 with associated sign bits.
495 _y: The vector of pulses, whose sum of absolute values is K.
496 _k: Returns K.*/
497static inline opus_uint32 icwrs2(const int *_y,int *_k){
498 opus_uint32 i;
499 int k;
500 i=icwrs1(_y+1,&k);
501 i+=k?ucwrs2(k):0;
502 k+=abs(_y[0]);
503 if(_y[0]<0)i+=ucwrs2(k+1U);
504 *_k=k;
505 return i;
506}
507
508/*Returns the index of the given combination of K elements chosen from a set
509 of size 3 with associated sign bits.
510 _y: The vector of pulses, whose sum of absolute values is K.
511 _k: Returns K.*/
512static inline opus_uint32 icwrs3(const int *_y,int *_k){
513 opus_uint32 i;
514 int k;
515 i=icwrs2(_y+1,&k);
516 i+=k?ucwrs3(k):0;
517 k+=abs(_y[0]);
518 if(_y[0]<0)i+=ucwrs3(k+1U);
519 *_k=k;
520 return i;
521}
522
523/*Returns the index of the given combination of K elements chosen from a set
524 of size 4 with associated sign bits.
525 _y: The vector of pulses, whose sum of absolute values is K.
526 _k: Returns K.*/
527static inline opus_uint32 icwrs4(const int *_y,int *_k){
528 opus_uint32 i;
529 int k;
530 i=icwrs3(_y+1,&k);
531 i+=k?ucwrs4(k):0;
532 k+=abs(_y[0]);
533 if(_y[0]<0)i+=ucwrs4(k+1);
534 *_k=k;
535 return i;
536}
537
538#endif /* SMALL_FOOTPRINT */
539
540/*Returns the index of the given combination of K elements chosen from a set 625/*Returns the index of the given combination of K elements chosen from a set
541 of size _n with associated sign bits. 626 of size _n with associated sign bits.
542 _y: The vector of pulses, whose sum of absolute values must be _k. 627 _y: The vector of pulses, whose sum of absolute values must be _k.
@@ -544,8 +629,8 @@ static inline opus_uint32 icwrs4(const int *_y,int *_k){
544static inline opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y, 629static inline opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y,
545 opus_uint32 *_u){ 630 opus_uint32 *_u){
546 opus_uint32 i; 631 opus_uint32 i;
547 int j; 632 int j;
548 int k; 633 int k;
549 /*We can't unroll the first two iterations of the loop unless _n>=2.*/ 634 /*We can't unroll the first two iterations of the loop unless _n>=2.*/
550 celt_assert(_n>=2); 635 celt_assert(_n>=2);
551 _u[0]=0; 636 _u[0]=0;
@@ -590,58 +675,23 @@ void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
590 675
591void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){ 676void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
592 opus_uint32 i; 677 opus_uint32 i;
678 VARDECL(opus_uint32,u);
679 opus_uint32 nc;
680 SAVE_STACK;
593 celt_assert(_k>0); 681 celt_assert(_k>0);
594#ifndef SMALL_FOOTPRINT 682 ALLOC(u,_k+2U,opus_uint32);
595 switch(_n){ 683 i=icwrs(_n,_k,&nc,_y,u);
596 case 2:{ 684 ec_enc_uint(_enc,i,nc);
597 i=icwrs2(_y,&_k); 685 RESTORE_STACK;
598 ec_enc_uint(_enc,i,ncwrs2(_k));
599 }break;
600 case 3:{
601 i=icwrs3(_y,&_k);
602 ec_enc_uint(_enc,i,ncwrs3(_k));
603 }break;
604 case 4:{
605 i=icwrs4(_y,&_k);
606 ec_enc_uint(_enc,i,ncwrs4(_k));
607 }break;
608 default:
609 {
610#endif
611 VARDECL(opus_uint32,u);
612 opus_uint32 nc;
613 SAVE_STACK;
614 ALLOC(u,_k+2U,opus_uint32);
615 i=icwrs(_n,_k,&nc,_y,u);
616 ec_enc_uint(_enc,i,nc);
617 RESTORE_STACK;
618#ifndef SMALL_FOOTPRINT
619 }
620 break;
621 }
622#endif
623} 686}
624 687
625void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec) 688void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
626{ 689 VARDECL(opus_uint32,u);
690 SAVE_STACK;
627 celt_assert(_k>0); 691 celt_assert(_k>0);
628#ifndef SMALL_FOOTPRINT 692 ALLOC(u,_k+2U,opus_uint32);
629 switch(_n){ 693 cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
630 case 2:cwrsi2(_k,ec_dec_uint(_dec,ncwrs2(_k)),_y);break; 694 RESTORE_STACK;
631 case 3:cwrsi3(_k,ec_dec_uint(_dec,ncwrs3(_k)),_y);break;
632 case 4:cwrsi4(_k,ec_dec_uint(_dec,ncwrs4(_k)),_y);break;
633 default:
634 {
635#endif
636/* VARDECL(opus_uint32,u);
637 SAVE_STACK;
638 ALLOC(u,_k+2U,opus_uint32); */
639 opus_uint32 u[MAX_PULSES+2];
640 cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
641/* RESTORE_STACK; */
642#ifndef SMALL_FOOTPRINT
643 }
644 break;
645 }
646#endif
647} 695}
696
697#endif /* SMALL_FOOTPRINT */
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 19:55:00 +0000