1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libopus/celt/cwrs.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,697 @@
1.4 +/* Copyright (c) 2007-2008 CSIRO
1.5 + Copyright (c) 2007-2009 Xiph.Org Foundation
1.6 + Copyright (c) 2007-2009 Timothy B. Terriberry
1.7 + Written by Timothy B. Terriberry and Jean-Marc Valin */
1.8 +/*
1.9 + Redistribution and use in source and binary forms, with or without
1.10 + modification, are permitted provided that the following conditions
1.11 + are met:
1.12 +
1.13 + - Redistributions of source code must retain the above copyright
1.14 + notice, this list of conditions and the following disclaimer.
1.15 +
1.16 + - Redistributions in binary form must reproduce the above copyright
1.17 + notice, this list of conditions and the following disclaimer in the
1.18 + documentation and/or other materials provided with the distribution.
1.19 +
1.20 + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.21 + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.22 + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.23 + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
1.24 + OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
1.25 + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
1.26 + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
1.27 + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
1.28 + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1.29 + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1.30 + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.31 +*/
1.32 +
1.33 +#ifdef HAVE_CONFIG_H
1.34 +#include "config.h"
1.35 +#endif
1.36 +
1.37 +#include "os_support.h"
1.38 +#include "cwrs.h"
1.39 +#include "mathops.h"
1.40 +#include "arch.h"
1.41 +
1.42 +#ifdef CUSTOM_MODES
1.43 +
1.44 +/*Guaranteed to return a conservatively large estimate of the binary logarithm
1.45 + with frac bits of fractional precision.
1.46 + Tested for all possible 32-bit inputs with frac=4, where the maximum
1.47 + overestimation is 0.06254243 bits.*/
1.48 +int log2_frac(opus_uint32 val, int frac)
1.49 +{
1.50 + int l;
1.51 + l=EC_ILOG(val);
1.52 + if(val&(val-1)){
1.53 + /*This is (val>>l-16), but guaranteed to round up, even if adding a bias
1.54 + before the shift would cause overflow (e.g., for 0xFFFFxxxx).
1.55 + Doesn't work for val=0, but that case fails the test above.*/
1.56 + if(l>16)val=((val-1)>>(l-16))+1;
1.57 + else val<<=16-l;
1.58 + l=(l-1)<<frac;
1.59 + /*Note that we always need one iteration, since the rounding up above means
1.60 + that we might need to adjust the integer part of the logarithm.*/
1.61 + do{
1.62 + int b;
1.63 + b=(int)(val>>16);
1.64 + l+=b<<frac;
1.65 + val=(val+b)>>b;
1.66 + val=(val*val+0x7FFF)>>15;
1.67 + }
1.68 + while(frac-->0);
1.69 + /*If val is not exactly 0x8000, then we have to round up the remainder.*/
1.70 + return l+(val>0x8000);
1.71 + }
1.72 + /*Exact powers of two require no rounding.*/
1.73 + else return (l-1)<<frac;
1.74 +}
1.75 +#endif
1.76 +
1.77 +/*Although derived separately, the pulse vector coding scheme is equivalent to
1.78 + a Pyramid Vector Quantizer \cite{Fis86}.
1.79 + Some additional notes about an early version appear at
1.80 + http://people.xiph.org/~tterribe/notes/cwrs.html, but the codebook ordering
1.81 + and the definitions of some terms have evolved since that was written.
1.82 +
1.83 + The conversion from a pulse vector to an integer index (encoding) and back
1.84 + (decoding) is governed by two related functions, V(N,K) and U(N,K).
1.85 +
1.86 + V(N,K) = the number of combinations, with replacement, of N items, taken K
1.87 + at a time, when a sign bit is added to each item taken at least once (i.e.,
1.88 + the number of N-dimensional unit pulse vectors with K pulses).
1.89 + One way to compute this is via
1.90 + V(N,K) = K>0 ? sum(k=1...K,2**k*choose(N,k)*choose(K-1,k-1)) : 1,
1.91 + where choose() is the binomial function.
1.92 + A table of values for N<10 and K<10 looks like:
1.93 + V[10][10] = {
1.94 + {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
1.95 + {1, 2, 2, 2, 2, 2, 2, 2, 2, 2},
1.96 + {1, 4, 8, 12, 16, 20, 24, 28, 32, 36},
1.97 + {1, 6, 18, 38, 66, 102, 146, 198, 258, 326},
1.98 + {1, 8, 32, 88, 192, 360, 608, 952, 1408, 1992},
1.99 + {1, 10, 50, 170, 450, 1002, 1970, 3530, 5890, 9290},
1.100 + {1, 12, 72, 292, 912, 2364, 5336, 10836, 20256, 35436},
1.101 + {1, 14, 98, 462, 1666, 4942, 12642, 28814, 59906, 115598},
1.102 + {1, 16, 128, 688, 2816, 9424, 27008, 68464, 157184, 332688},
1.103 + {1, 18, 162, 978, 4482, 16722, 53154, 148626, 374274, 864146}
1.104 + };
1.105 +
1.106 + U(N,K) = the number of such combinations wherein N-1 objects are taken at
1.107 + most K-1 at a time.
1.108 + This is given by
1.109 + U(N,K) = sum(k=0...K-1,V(N-1,k))
1.110 + = K>0 ? (V(N-1,K-1) + V(N,K-1))/2 : 0.
1.111 + The latter expression also makes clear that U(N,K) is half the number of such
1.112 + combinations wherein the first object is taken at least once.
1.113 + Although it may not be clear from either of these definitions, U(N,K) is the
1.114 + natural function to work with when enumerating the pulse vector codebooks,
1.115 + not V(N,K).
1.116 + U(N,K) is not well-defined for N=0, but with the extension
1.117 + U(0,K) = K>0 ? 0 : 1,
1.118 + the function becomes symmetric: U(N,K) = U(K,N), with a similar table:
1.119 + U[10][10] = {
1.120 + {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
1.121 + {0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
1.122 + {0, 1, 3, 5, 7, 9, 11, 13, 15, 17},
1.123 + {0, 1, 5, 13, 25, 41, 61, 85, 113, 145},
1.124 + {0, 1, 7, 25, 63, 129, 231, 377, 575, 833},
1.125 + {0, 1, 9, 41, 129, 321, 681, 1289, 2241, 3649},
1.126 + {0, 1, 11, 61, 231, 681, 1683, 3653, 7183, 13073},
1.127 + {0, 1, 13, 85, 377, 1289, 3653, 8989, 19825, 40081},
1.128 + {0, 1, 15, 113, 575, 2241, 7183, 19825, 48639, 108545},
1.129 + {0, 1, 17, 145, 833, 3649, 13073, 40081, 108545, 265729}
1.130 + };
1.131 +
1.132 + With this extension, V(N,K) may be written in terms of U(N,K):
1.133 + V(N,K) = U(N,K) + U(N,K+1)
1.134 + for all N>=0, K>=0.
1.135 + Thus U(N,K+1) represents the number of combinations where the first element
1.136 + is positive or zero, and U(N,K) represents the number of combinations where
1.137 + it is negative.
1.138 + With a large enough table of U(N,K) values, we could write O(N) encoding
1.139 + and O(min(N*log(K),N+K)) decoding routines, but such a table would be
1.140 + prohibitively large for small embedded devices (K may be as large as 32767
1.141 + for small N, and N may be as large as 200).
1.142 +
1.143 + Both functions obey the same recurrence relation:
1.144 + V(N,K) = V(N-1,K) + V(N,K-1) + V(N-1,K-1),
1.145 + U(N,K) = U(N-1,K) + U(N,K-1) + U(N-1,K-1),
1.146 + for all N>0, K>0, with different initial conditions at N=0 or K=0.
1.147 + This allows us to construct a row of one of the tables above given the
1.148 + previous row or the next row.
1.149 + Thus we can derive O(NK) encoding and decoding routines with O(K) memory
1.150 + using only addition and subtraction.
1.151 +
1.152 + When encoding, we build up from the U(2,K) row and work our way forwards.
1.153 + When decoding, we need to start at the U(N,K) row and work our way backwards,
1.154 + which requires a means of computing U(N,K).
1.155 + U(N,K) may be computed from two previous values with the same N:
1.156 + U(N,K) = ((2*N-1)*U(N,K-1) - U(N,K-2))/(K-1) + U(N,K-2)
1.157 + for all N>1, and since U(N,K) is symmetric, a similar relation holds for two
1.158 + previous values with the same K:
1.159 + U(N,K>1) = ((2*K-1)*U(N-1,K) - U(N-2,K))/(N-1) + U(N-2,K)
1.160 + for all K>1.
1.161 + This allows us to construct an arbitrary row of the U(N,K) table by starting
1.162 + with the first two values, which are constants.
1.163 + This saves roughly 2/3 the work in our O(NK) decoding routine, but costs O(K)
1.164 + multiplications.
1.165 + Similar relations can be derived for V(N,K), but are not used here.
1.166 +
1.167 + For N>0 and K>0, U(N,K) and V(N,K) take on the form of an (N-1)-degree
1.168 + polynomial for fixed N.
1.169 + The first few are
1.170 + U(1,K) = 1,
1.171 + U(2,K) = 2*K-1,
1.172 + U(3,K) = (2*K-2)*K+1,
1.173 + U(4,K) = (((4*K-6)*K+8)*K-3)/3,
1.174 + U(5,K) = ((((2*K-4)*K+10)*K-8)*K+3)/3,
1.175 + and
1.176 + V(1,K) = 2,
1.177 + V(2,K) = 4*K,
1.178 + V(3,K) = 4*K*K+2,
1.179 + V(4,K) = 8*(K*K+2)*K/3,
1.180 + V(5,K) = ((4*K*K+20)*K*K+6)/3,
1.181 + for all K>0.
1.182 + This allows us to derive O(N) encoding and O(N*log(K)) decoding routines for
1.183 + small N (and indeed decoding is also O(N) for N<3).
1.184 +
1.185 + @ARTICLE{Fis86,
1.186 + author="Thomas R. Fischer",
1.187 + title="A Pyramid Vector Quantizer",
1.188 + journal="IEEE Transactions on Information Theory",
1.189 + volume="IT-32",
1.190 + number=4,
1.191 + pages="568--583",
1.192 + month=Jul,
1.193 + year=1986
1.194 + }*/
1.195 +
1.196 +#if !defined(SMALL_FOOTPRINT)
1.197 +
1.198 +/*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*/
1.199 +# define CELT_PVQ_U(_n,_k) (CELT_PVQ_U_ROW[IMIN(_n,_k)][IMAX(_n,_k)])
1.200 +/*V(N,K) := U(N,K)+U(N,K+1) = the number of PVQ codewords for a band of size N
1.201 + with K pulses allocated to it.*/
1.202 +# define CELT_PVQ_V(_n,_k) (CELT_PVQ_U(_n,_k)+CELT_PVQ_U(_n,(_k)+1))
1.203 +
1.204 +/*For each V(N,K) supported, we will access element U(min(N,K+1),max(N,K+1)).
1.205 + Thus, the number of entries in row I is the larger of the maximum number of
1.206 + pulses we will ever allocate for a given N=I (K=128, or however many fit in
1.207 + 32 bits, whichever is smaller), plus one, and the maximum N for which
1.208 + K=I-1 pulses fit in 32 bits.
1.209 + The largest band size in an Opus Custom mode is 208.
1.210 + Otherwise, we can limit things to the set of N which can be achieved by
1.211 + splitting a band from a standard Opus mode: 176, 144, 96, 88, 72, 64, 48,
1.212 + 44, 36, 32, 24, 22, 18, 16, 8, 4, 2).*/
1.213 +#if defined(CUSTOM_MODES)
1.214 +static const opus_uint32 CELT_PVQ_U_DATA[1488]={
1.215 +#else
1.216 +static const opus_uint32 CELT_PVQ_U_DATA[1272]={
1.217 +#endif
1.218 + /*N=0, K=0...176:*/
1.219 + 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,
1.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,
1.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,
1.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,
1.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,
1.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,
1.225 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1.226 +#if defined(CUSTOM_MODES)
1.227 + /*...208:*/
1.228 + 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,
1.229 + 0, 0, 0, 0, 0, 0,
1.230 +#endif
1.231 + /*N=1, K=1...176:*/
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,
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,
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,
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,
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,
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,
1.238 + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1.239 +#if defined(CUSTOM_MODES)
1.240 + /*...208:*/
1.241 + 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,
1.242 + 1, 1, 1, 1, 1, 1,
1.243 +#endif
1.244 + /*N=2, K=2...176:*/
1.245 + 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
1.246 + 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79,
1.247 + 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113,
1.248 + 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143,
1.249 + 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173,
1.250 + 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203,
1.251 + 205, 207, 209, 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233,
1.252 + 235, 237, 239, 241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261, 263,
1.253 + 265, 267, 269, 271, 273, 275, 277, 279, 281, 283, 285, 287, 289, 291, 293,
1.254 + 295, 297, 299, 301, 303, 305, 307, 309, 311, 313, 315, 317, 319, 321, 323,
1.255 + 325, 327, 329, 331, 333, 335, 337, 339, 341, 343, 345, 347, 349, 351,
1.256 +#if defined(CUSTOM_MODES)
1.257 + /*...208:*/
1.258 + 353, 355, 357, 359, 361, 363, 365, 367, 369, 371, 373, 375, 377, 379, 381,
1.259 + 383, 385, 387, 389, 391, 393, 395, 397, 399, 401, 403, 405, 407, 409, 411,
1.260 + 413, 415,
1.261 +#endif
1.262 + /*N=3, K=3...176:*/
1.263 + 13, 25, 41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613,
1.264 + 685, 761, 841, 925, 1013, 1105, 1201, 1301, 1405, 1513, 1625, 1741, 1861,
1.265 + 1985, 2113, 2245, 2381, 2521, 2665, 2813, 2965, 3121, 3281, 3445, 3613, 3785,
1.266 + 3961, 4141, 4325, 4513, 4705, 4901, 5101, 5305, 5513, 5725, 5941, 6161, 6385,
1.267 + 6613, 6845, 7081, 7321, 7565, 7813, 8065, 8321, 8581, 8845, 9113, 9385, 9661,
1.268 + 9941, 10225, 10513, 10805, 11101, 11401, 11705, 12013, 12325, 12641, 12961,
1.269 + 13285, 13613, 13945, 14281, 14621, 14965, 15313, 15665, 16021, 16381, 16745,
1.270 + 17113, 17485, 17861, 18241, 18625, 19013, 19405, 19801, 20201, 20605, 21013,
1.271 + 21425, 21841, 22261, 22685, 23113, 23545, 23981, 24421, 24865, 25313, 25765,
1.272 + 26221, 26681, 27145, 27613, 28085, 28561, 29041, 29525, 30013, 30505, 31001,
1.273 + 31501, 32005, 32513, 33025, 33541, 34061, 34585, 35113, 35645, 36181, 36721,
1.274 + 37265, 37813, 38365, 38921, 39481, 40045, 40613, 41185, 41761, 42341, 42925,
1.275 + 43513, 44105, 44701, 45301, 45905, 46513, 47125, 47741, 48361, 48985, 49613,
1.276 + 50245, 50881, 51521, 52165, 52813, 53465, 54121, 54781, 55445, 56113, 56785,
1.277 + 57461, 58141, 58825, 59513, 60205, 60901, 61601,
1.278 +#if defined(CUSTOM_MODES)
1.279 + /*...208:*/
1.280 + 62305, 63013, 63725, 64441, 65161, 65885, 66613, 67345, 68081, 68821, 69565,
1.281 + 70313, 71065, 71821, 72581, 73345, 74113, 74885, 75661, 76441, 77225, 78013,
1.282 + 78805, 79601, 80401, 81205, 82013, 82825, 83641, 84461, 85285, 86113,
1.283 +#endif
1.284 + /*N=4, K=4...176:*/
1.285 + 63, 129, 231, 377, 575, 833, 1159, 1561, 2047, 2625, 3303, 4089, 4991, 6017,
1.286 + 7175, 8473, 9919, 11521, 13287, 15225, 17343, 19649, 22151, 24857, 27775,
1.287 + 30913, 34279, 37881, 41727, 45825, 50183, 54809, 59711, 64897, 70375, 76153,
1.288 + 82239, 88641, 95367, 102425, 109823, 117569, 125671, 134137, 142975, 152193,
1.289 + 161799, 171801, 182207, 193025, 204263, 215929, 228031, 240577, 253575,
1.290 + 267033, 280959, 295361, 310247, 325625, 341503, 357889, 374791, 392217,
1.291 + 410175, 428673, 447719, 467321, 487487, 508225, 529543, 551449, 573951,
1.292 + 597057, 620775, 645113, 670079, 695681, 721927, 748825, 776383, 804609,
1.293 + 833511, 863097, 893375, 924353, 956039, 988441, 1021567, 1055425, 1090023,
1.294 + 1125369, 1161471, 1198337, 1235975, 1274393, 1313599, 1353601, 1394407,
1.295 + 1436025, 1478463, 1521729, 1565831, 1610777, 1656575, 1703233, 1750759,
1.296 + 1799161, 1848447, 1898625, 1949703, 2001689, 2054591, 2108417, 2163175,
1.297 + 2218873, 2275519, 2333121, 2391687, 2451225, 2511743, 2573249, 2635751,
1.298 + 2699257, 2763775, 2829313, 2895879, 2963481, 3032127, 3101825, 3172583,
1.299 + 3244409, 3317311, 3391297, 3466375, 3542553, 3619839, 3698241, 3777767,
1.300 + 3858425, 3940223, 4023169, 4107271, 4192537, 4278975, 4366593, 4455399,
1.301 + 4545401, 4636607, 4729025, 4822663, 4917529, 5013631, 5110977, 5209575,
1.302 + 5309433, 5410559, 5512961, 5616647, 5721625, 5827903, 5935489, 6044391,
1.303 + 6154617, 6266175, 6379073, 6493319, 6608921, 6725887, 6844225, 6963943,
1.304 + 7085049, 7207551,
1.305 +#if defined(CUSTOM_MODES)
1.306 + /*...208:*/
1.307 + 7331457, 7456775, 7583513, 7711679, 7841281, 7972327, 8104825, 8238783,
1.308 + 8374209, 8511111, 8649497, 8789375, 8930753, 9073639, 9218041, 9363967,
1.309 + 9511425, 9660423, 9810969, 9963071, 10116737, 10271975, 10428793, 10587199,
1.310 + 10747201, 10908807, 11072025, 11236863, 11403329, 11571431, 11741177,
1.311 + 11912575,
1.312 +#endif
1.313 + /*N=5, K=5...176:*/
1.314 + 321, 681, 1289, 2241, 3649, 5641, 8361, 11969, 16641, 22569, 29961, 39041,
1.315 + 50049, 63241, 78889, 97281, 118721, 143529, 172041, 204609, 241601, 283401,
1.316 + 330409, 383041, 441729, 506921, 579081, 658689, 746241, 842249, 947241,
1.317 + 1061761, 1186369, 1321641, 1468169, 1626561, 1797441, 1981449, 2179241,
1.318 + 2391489, 2618881, 2862121, 3121929, 3399041, 3694209, 4008201, 4341801,
1.319 + 4695809, 5071041, 5468329, 5888521, 6332481, 6801089, 7295241, 7815849,
1.320 + 8363841, 8940161, 9545769, 10181641, 10848769, 11548161, 12280841, 13047849,
1.321 + 13850241, 14689089, 15565481, 16480521, 17435329, 18431041, 19468809,
1.322 + 20549801, 21675201, 22846209, 24064041, 25329929, 26645121, 28010881,
1.323 + 29428489, 30899241, 32424449, 34005441, 35643561, 37340169, 39096641,
1.324 + 40914369, 42794761, 44739241, 46749249, 48826241, 50971689, 53187081,
1.325 + 55473921, 57833729, 60268041, 62778409, 65366401, 68033601, 70781609,
1.326 + 73612041, 76526529, 79526721, 82614281, 85790889, 89058241, 92418049,
1.327 + 95872041, 99421961, 103069569, 106816641, 110664969, 114616361, 118672641,
1.328 + 122835649, 127107241, 131489289, 135983681, 140592321, 145317129, 150160041,
1.329 + 155123009, 160208001, 165417001, 170752009, 176215041, 181808129, 187533321,
1.330 + 193392681, 199388289, 205522241, 211796649, 218213641, 224775361, 231483969,
1.331 + 238341641, 245350569, 252512961, 259831041, 267307049, 274943241, 282741889,
1.332 + 290705281, 298835721, 307135529, 315607041, 324252609, 333074601, 342075401,
1.333 + 351257409, 360623041, 370174729, 379914921, 389846081, 399970689, 410291241,
1.334 + 420810249, 431530241, 442453761, 453583369, 464921641, 476471169, 488234561,
1.335 + 500214441, 512413449, 524834241, 537479489, 550351881, 563454121, 576788929,
1.336 + 590359041, 604167209, 618216201, 632508801,
1.337 +#if defined(CUSTOM_MODES)
1.338 + /*...208:*/
1.339 + 647047809, 661836041, 676876329, 692171521, 707724481, 723538089, 739615241,
1.340 + 755958849, 772571841, 789457161, 806617769, 824056641, 841776769, 859781161,
1.341 + 878072841, 896654849, 915530241, 934702089, 954173481, 973947521, 994027329,
1.342 + 1014416041, 1035116809, 1056132801, 1077467201, 1099123209, 1121104041,
1.343 + 1143412929, 1166053121, 1189027881, 1212340489, 1235994241,
1.344 +#endif
1.345 + /*N=6, K=6...96:*/
1.346 + 1683, 3653, 7183, 13073, 22363, 36365, 56695, 85305, 124515, 177045, 246047,
1.347 + 335137, 448427, 590557, 766727, 982729, 1244979, 1560549, 1937199, 2383409,
1.348 + 2908411, 3522221, 4235671, 5060441, 6009091, 7095093, 8332863, 9737793,
1.349 + 11326283, 13115773, 15124775, 17372905, 19880915, 22670725, 25765455,
1.350 + 29189457, 32968347, 37129037, 41699767, 46710137, 52191139, 58175189,
1.351 + 64696159, 71789409, 79491819, 87841821, 96879431, 106646281, 117185651,
1.352 + 128542501, 140763503, 153897073, 167993403, 183104493, 199284183, 216588185,
1.353 + 235074115, 254801525, 275831935, 298228865, 322057867, 347386557, 374284647,
1.354 + 402823977, 433078547, 465124549, 499040399, 534906769, 572806619, 612825229,
1.355 + 655050231, 699571641, 746481891, 795875861, 847850911, 902506913, 959946283,
1.356 + 1020274013, 1083597703, 1150027593, 1219676595, 1292660325, 1369097135,
1.357 + 1449108145, 1532817275, 1620351277, 1711839767, 1807415257, 1907213187,
1.358 + 2011371957, 2120032959,
1.359 +#if defined(CUSTOM_MODES)
1.360 + /*...109:*/
1.361 + 2233340609U, 2351442379U, 2474488829U, 2602633639U, 2736033641U, 2874848851U,
1.362 + 3019242501U, 3169381071U, 3325434321U, 3487575323U, 3655980493U, 3830829623U,
1.363 + 4012305913U,
1.364 +#endif
1.365 + /*N=7, K=7...54*/
1.366 + 8989, 19825, 40081, 75517, 134245, 227305, 369305, 579125, 880685, 1303777,
1.367 + 1884961, 2668525, 3707509, 5064793, 6814249, 9041957, 11847485, 15345233,
1.368 + 19665841, 24957661, 31388293, 39146185, 48442297, 59511829, 72616013,
1.369 + 88043969, 106114625, 127178701, 151620757, 179861305, 212358985, 249612805,
1.370 + 292164445, 340600625, 395555537, 457713341, 527810725, 606639529, 695049433,
1.371 + 793950709, 904317037, 1027188385, 1163673953, 1314955181, 1482288821,
1.372 + 1667010073, 1870535785, 2094367717,
1.373 +#if defined(CUSTOM_MODES)
1.374 + /*...60:*/
1.375 + 2340095869U, 2609401873U, 2904062449U, 3225952925U, 3577050821U, 3959439497U,
1.376 +#endif
1.377 + /*N=8, K=8...37*/
1.378 + 48639, 108545, 224143, 433905, 795455, 1392065, 2340495, 3800305, 5984767,
1.379 + 9173505, 13726991, 20103025, 28875327, 40754369, 56610575, 77500017,
1.380 + 104692735, 139703809, 184327311, 240673265, 311207743, 398796225, 506750351,
1.381 + 638878193, 799538175, 993696769, 1226990095, 1505789553, 1837271615,
1.382 + 2229491905U,
1.383 +#if defined(CUSTOM_MODES)
1.384 + /*...40:*/
1.385 + 2691463695U, 3233240945U, 3866006015U,
1.386 +#endif
1.387 + /*N=9, K=9...28:*/
1.388 + 265729, 598417, 1256465, 2485825, 4673345, 8405905, 14546705, 24331777,
1.389 + 39490049, 62390545, 96220561, 145198913, 214828609, 312193553, 446304145,
1.390 + 628496897, 872893441, 1196924561, 1621925137, 2173806145U,
1.391 +#if defined(CUSTOM_MODES)
1.392 + /*...29:*/
1.393 + 2883810113U,
1.394 +#endif
1.395 + /*N=10, K=10...24:*/
1.396 + 1462563, 3317445, 7059735, 14218905, 27298155, 50250765, 89129247, 152951073,
1.397 + 254831667, 413442773, 654862247, 1014889769, 1541911931, 2300409629U,
1.398 + 3375210671U,
1.399 + /*N=11, K=11...19:*/
1.400 + 8097453, 18474633, 39753273, 81270333, 158819253, 298199265, 540279585,
1.401 + 948062325, 1616336765,
1.402 +#if defined(CUSTOM_MODES)
1.403 + /*...20:*/
1.404 + 2684641785U,
1.405 +#endif
1.406 + /*N=12, K=12...18:*/
1.407 + 45046719, 103274625, 224298231, 464387817, 921406335, 1759885185,
1.408 + 3248227095U,
1.409 + /*N=13, K=13...16:*/
1.410 + 251595969, 579168825, 1267854873, 2653649025U,
1.411 + /*N=14, K=14:*/
1.412 + 1409933619
1.413 +};
1.414 +
1.415 +#if defined(CUSTOM_MODES)
1.416 +static const opus_uint32 *const CELT_PVQ_U_ROW[15]={
1.417 + CELT_PVQ_U_DATA+ 0,CELT_PVQ_U_DATA+ 208,CELT_PVQ_U_DATA+ 415,
1.418 + CELT_PVQ_U_DATA+ 621,CELT_PVQ_U_DATA+ 826,CELT_PVQ_U_DATA+1030,
1.419 + CELT_PVQ_U_DATA+1233,CELT_PVQ_U_DATA+1336,CELT_PVQ_U_DATA+1389,
1.420 + CELT_PVQ_U_DATA+1421,CELT_PVQ_U_DATA+1441,CELT_PVQ_U_DATA+1455,
1.421 + CELT_PVQ_U_DATA+1464,CELT_PVQ_U_DATA+1470,CELT_PVQ_U_DATA+1473
1.422 +};
1.423 +#else
1.424 +static const opus_uint32 *const CELT_PVQ_U_ROW[15]={
1.425 + CELT_PVQ_U_DATA+ 0,CELT_PVQ_U_DATA+ 176,CELT_PVQ_U_DATA+ 351,
1.426 + CELT_PVQ_U_DATA+ 525,CELT_PVQ_U_DATA+ 698,CELT_PVQ_U_DATA+ 870,
1.427 + CELT_PVQ_U_DATA+1041,CELT_PVQ_U_DATA+1131,CELT_PVQ_U_DATA+1178,
1.428 + CELT_PVQ_U_DATA+1207,CELT_PVQ_U_DATA+1226,CELT_PVQ_U_DATA+1240,
1.429 + CELT_PVQ_U_DATA+1248,CELT_PVQ_U_DATA+1254,CELT_PVQ_U_DATA+1257
1.430 +};
1.431 +#endif
1.432 +
1.433 +#if defined(CUSTOM_MODES)
1.434 +void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
1.435 + int k;
1.436 + /*_maxk==0 => there's nothing to do.*/
1.437 + celt_assert(_maxk>0);
1.438 + _bits[0]=0;
1.439 + for(k=1;k<=_maxk;k++)_bits[k]=log2_frac(CELT_PVQ_V(_n,k),_frac);
1.440 +}
1.441 +#endif
1.442 +
1.443 +static opus_uint32 icwrs(int _n,const int *_y){
1.444 + opus_uint32 i;
1.445 + int j;
1.446 + int k;
1.447 + celt_assert(_n>=2);
1.448 + j=_n-1;
1.449 + i=_y[j]<0;
1.450 + k=abs(_y[j]);
1.451 + do{
1.452 + j--;
1.453 + i+=CELT_PVQ_U(_n-j,k);
1.454 + k+=abs(_y[j]);
1.455 + if(_y[j]<0)i+=CELT_PVQ_U(_n-j,k+1);
1.456 + }
1.457 + while(j>0);
1.458 + return i;
1.459 +}
1.460 +
1.461 +void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
1.462 + celt_assert(_k>0);
1.463 + ec_enc_uint(_enc,icwrs(_n,_y),CELT_PVQ_V(_n,_k));
1.464 +}
1.465 +
1.466 +static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y){
1.467 + opus_uint32 p;
1.468 + int s;
1.469 + int k0;
1.470 + celt_assert(_k>0);
1.471 + celt_assert(_n>1);
1.472 + while(_n>2){
1.473 + opus_uint32 q;
1.474 + /*Lots of pulses case:*/
1.475 + if(_k>=_n){
1.476 + const opus_uint32 *row;
1.477 + row=CELT_PVQ_U_ROW[_n];
1.478 + /*Are the pulses in this dimension negative?*/
1.479 + p=row[_k+1];
1.480 + s=-(_i>=p);
1.481 + _i-=p&s;
1.482 + /*Count how many pulses were placed in this dimension.*/
1.483 + k0=_k;
1.484 + q=row[_n];
1.485 + if(q>_i){
1.486 + celt_assert(p>q);
1.487 + _k=_n;
1.488 + do p=CELT_PVQ_U_ROW[--_k][_n];
1.489 + while(p>_i);
1.490 + }
1.491 + else for(p=row[_k];p>_i;p=row[_k])_k--;
1.492 + _i-=p;
1.493 + *_y++=(k0-_k+s)^s;
1.494 + }
1.495 + /*Lots of dimensions case:*/
1.496 + else{
1.497 + /*Are there any pulses in this dimension at all?*/
1.498 + p=CELT_PVQ_U_ROW[_k][_n];
1.499 + q=CELT_PVQ_U_ROW[_k+1][_n];
1.500 + if(p<=_i&&_i<q){
1.501 + _i-=p;
1.502 + *_y++=0;
1.503 + }
1.504 + else{
1.505 + /*Are the pulses in this dimension negative?*/
1.506 + s=-(_i>=q);
1.507 + _i-=q&s;
1.508 + /*Count how many pulses were placed in this dimension.*/
1.509 + k0=_k;
1.510 + do p=CELT_PVQ_U_ROW[--_k][_n];
1.511 + while(p>_i);
1.512 + _i-=p;
1.513 + *_y++=(k0-_k+s)^s;
1.514 + }
1.515 + }
1.516 + _n--;
1.517 + }
1.518 + /*_n==2*/
1.519 + p=2*_k+1;
1.520 + s=-(_i>=p);
1.521 + _i-=p&s;
1.522 + k0=_k;
1.523 + _k=(_i+1)>>1;
1.524 + if(_k)_i-=2*_k-1;
1.525 + *_y++=(k0-_k+s)^s;
1.526 + /*_n==1*/
1.527 + s=-(int)_i;
1.528 + *_y=(_k+s)^s;
1.529 +}
1.530 +
1.531 +void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
1.532 + cwrsi(_n,_k,ec_dec_uint(_dec,CELT_PVQ_V(_n,_k)),_y);
1.533 +}
1.534 +
1.535 +#else /* SMALL_FOOTPRINT */
1.536 +
1.537 +/*Computes the next row/column of any recurrence that obeys the relation
1.538 + u[i][j]=u[i-1][j]+u[i][j-1]+u[i-1][j-1].
1.539 + _ui0 is the base case for the new row/column.*/
1.540 +static OPUS_INLINE void unext(opus_uint32 *_ui,unsigned _len,opus_uint32 _ui0){
1.541 + opus_uint32 ui1;
1.542 + unsigned j;
1.543 + /*This do-while will overrun the array if we don't have storage for at least
1.544 + 2 values.*/
1.545 + j=1; do {
1.546 + ui1=UADD32(UADD32(_ui[j],_ui[j-1]),_ui0);
1.547 + _ui[j-1]=_ui0;
1.548 + _ui0=ui1;
1.549 + } while (++j<_len);
1.550 + _ui[j-1]=_ui0;
1.551 +}
1.552 +
1.553 +/*Computes the previous row/column of any recurrence that obeys the relation
1.554 + u[i-1][j]=u[i][j]-u[i][j-1]-u[i-1][j-1].
1.555 + _ui0 is the base case for the new row/column.*/
1.556 +static OPUS_INLINE void uprev(opus_uint32 *_ui,unsigned _n,opus_uint32 _ui0){
1.557 + opus_uint32 ui1;
1.558 + unsigned j;
1.559 + /*This do-while will overrun the array if we don't have storage for at least
1.560 + 2 values.*/
1.561 + j=1; do {
1.562 + ui1=USUB32(USUB32(_ui[j],_ui[j-1]),_ui0);
1.563 + _ui[j-1]=_ui0;
1.564 + _ui0=ui1;
1.565 + } while (++j<_n);
1.566 + _ui[j-1]=_ui0;
1.567 +}
1.568 +
1.569 +/*Compute V(_n,_k), as well as U(_n,0..._k+1).
1.570 + _u: On exit, _u[i] contains U(_n,i) for i in [0..._k+1].*/
1.571 +static opus_uint32 ncwrs_urow(unsigned _n,unsigned _k,opus_uint32 *_u){
1.572 + opus_uint32 um2;
1.573 + unsigned len;
1.574 + unsigned k;
1.575 + len=_k+2;
1.576 + /*We require storage at least 3 values (e.g., _k>0).*/
1.577 + celt_assert(len>=3);
1.578 + _u[0]=0;
1.579 + _u[1]=um2=1;
1.580 + /*If _n==0, _u[0] should be 1 and the rest should be 0.*/
1.581 + /*If _n==1, _u[i] should be 1 for i>1.*/
1.582 + celt_assert(_n>=2);
1.583 + /*If _k==0, the following do-while loop will overflow the buffer.*/
1.584 + celt_assert(_k>0);
1.585 + k=2;
1.586 + do _u[k]=(k<<1)-1;
1.587 + while(++k<len);
1.588 + for(k=2;k<_n;k++)unext(_u+1,_k+1,1);
1.589 + return _u[_k]+_u[_k+1];
1.590 +}
1.591 +
1.592 +/*Returns the _i'th combination of _k elements chosen from a set of size _n
1.593 + with associated sign bits.
1.594 + _y: Returns the vector of pulses.
1.595 + _u: Must contain entries [0..._k+1] of row _n of U() on input.
1.596 + Its contents will be destructively modified.*/
1.597 +static void cwrsi(int _n,int _k,opus_uint32 _i,int *_y,opus_uint32 *_u){
1.598 + int j;
1.599 + celt_assert(_n>0);
1.600 + j=0;
1.601 + do{
1.602 + opus_uint32 p;
1.603 + int s;
1.604 + int yj;
1.605 + p=_u[_k+1];
1.606 + s=-(_i>=p);
1.607 + _i-=p&s;
1.608 + yj=_k;
1.609 + p=_u[_k];
1.610 + while(p>_i)p=_u[--_k];
1.611 + _i-=p;
1.612 + yj-=_k;
1.613 + _y[j]=(yj+s)^s;
1.614 + uprev(_u,_k+2,0);
1.615 + }
1.616 + while(++j<_n);
1.617 +}
1.618 +
1.619 +/*Returns the index of the given combination of K elements chosen from a set
1.620 + of size 1 with associated sign bits.
1.621 + _y: The vector of pulses, whose sum of absolute values is K.
1.622 + _k: Returns K.*/
1.623 +static OPUS_INLINE opus_uint32 icwrs1(const int *_y,int *_k){
1.624 + *_k=abs(_y[0]);
1.625 + return _y[0]<0;
1.626 +}
1.627 +
1.628 +/*Returns the index of the given combination of K elements chosen from a set
1.629 + of size _n with associated sign bits.
1.630 + _y: The vector of pulses, whose sum of absolute values must be _k.
1.631 + _nc: Returns V(_n,_k).*/
1.632 +static OPUS_INLINE opus_uint32 icwrs(int _n,int _k,opus_uint32 *_nc,const int *_y,
1.633 + opus_uint32 *_u){
1.634 + opus_uint32 i;
1.635 + int j;
1.636 + int k;
1.637 + /*We can't unroll the first two iterations of the loop unless _n>=2.*/
1.638 + celt_assert(_n>=2);
1.639 + _u[0]=0;
1.640 + for(k=1;k<=_k+1;k++)_u[k]=(k<<1)-1;
1.641 + i=icwrs1(_y+_n-1,&k);
1.642 + j=_n-2;
1.643 + i+=_u[k];
1.644 + k+=abs(_y[j]);
1.645 + if(_y[j]<0)i+=_u[k+1];
1.646 + while(j-->0){
1.647 + unext(_u,_k+2,0);
1.648 + i+=_u[k];
1.649 + k+=abs(_y[j]);
1.650 + if(_y[j]<0)i+=_u[k+1];
1.651 + }
1.652 + *_nc=_u[k]+_u[k+1];
1.653 + return i;
1.654 +}
1.655 +
1.656 +#ifdef CUSTOM_MODES
1.657 +void get_required_bits(opus_int16 *_bits,int _n,int _maxk,int _frac){
1.658 + int k;
1.659 + /*_maxk==0 => there's nothing to do.*/
1.660 + celt_assert(_maxk>0);
1.661 + _bits[0]=0;
1.662 + if (_n==1)
1.663 + {
1.664 + for (k=1;k<=_maxk;k++)
1.665 + _bits[k] = 1<<_frac;
1.666 + }
1.667 + else {
1.668 + VARDECL(opus_uint32,u);
1.669 + SAVE_STACK;
1.670 + ALLOC(u,_maxk+2U,opus_uint32);
1.671 + ncwrs_urow(_n,_maxk,u);
1.672 + for(k=1;k<=_maxk;k++)
1.673 + _bits[k]=log2_frac(u[k]+u[k+1],_frac);
1.674 + RESTORE_STACK;
1.675 + }
1.676 +}
1.677 +#endif /* CUSTOM_MODES */
1.678 +
1.679 +void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
1.680 + opus_uint32 i;
1.681 + VARDECL(opus_uint32,u);
1.682 + opus_uint32 nc;
1.683 + SAVE_STACK;
1.684 + celt_assert(_k>0);
1.685 + ALLOC(u,_k+2U,opus_uint32);
1.686 + i=icwrs(_n,_k,&nc,_y,u);
1.687 + ec_enc_uint(_enc,i,nc);
1.688 + RESTORE_STACK;
1.689 +}
1.690 +
1.691 +void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec){
1.692 + VARDECL(opus_uint32,u);
1.693 + SAVE_STACK;
1.694 + celt_assert(_k>0);
1.695 + ALLOC(u,_k+2U,opus_uint32);
1.696 + cwrsi(_n,_k,ec_dec_uint(_dec,ncwrs_urow(_n,_k,u)),_y,u);
1.697 + RESTORE_STACK;
1.698 +}
1.699 +
1.700 +#endif /* SMALL_FOOTPRINT */
