diff options
Diffstat (limited to 'lib/rbcodec/codecs/libopus/celt/kiss_fft.c')
-rw-r--r-- | lib/rbcodec/codecs/libopus/celt/kiss_fft.c | 722 |
1 files changed, 722 insertions, 0 deletions
diff --git a/lib/rbcodec/codecs/libopus/celt/kiss_fft.c b/lib/rbcodec/codecs/libopus/celt/kiss_fft.c new file mode 100644 index 0000000000..3ba075ab0c --- /dev/null +++ b/lib/rbcodec/codecs/libopus/celt/kiss_fft.c | |||
@@ -0,0 +1,722 @@ | |||
1 | /*Copyright (c) 2003-2004, Mark Borgerding | ||
2 | Lots of modifications by Jean-Marc Valin | ||
3 | Copyright (c) 2005-2007, Xiph.Org Foundation | ||
4 | Copyright (c) 2008, Xiph.Org Foundation, CSIRO | ||
5 | |||
6 | All rights reserved. | ||
7 | |||
8 | Redistribution and use in source and binary forms, with or without | ||
9 | modification, are permitted provided that the following conditions are met: | ||
10 | |||
11 | * Redistributions of source code must retain the above copyright notice, | ||
12 | this list of conditions and the following disclaimer. | ||
13 | * Redistributions in binary form must reproduce the above copyright notice, | ||
14 | 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 "AS IS" | ||
18 | AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
19 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
20 | ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE | ||
21 | LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
22 | CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
23 | SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
24 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
25 | CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
26 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
27 | POSSIBILITY OF SUCH DAMAGE.*/ | ||
28 | |||
29 | /* This code is originally from Mark Borgerding's KISS-FFT but has been | ||
30 | heavily modified to better suit Opus */ | ||
31 | |||
32 | #ifndef SKIP_CONFIG_H | ||
33 | # ifdef HAVE_CONFIG_H | ||
34 | # include "opus_config.h" | ||
35 | # endif | ||
36 | #endif | ||
37 | |||
38 | #include "_kiss_fft_guts.h" | ||
39 | #include "arch.h" | ||
40 | #include "os_support.h" | ||
41 | #include "mathops.h" | ||
42 | #include "stack_alloc.h" | ||
43 | #include "os_support.h" | ||
44 | |||
45 | /* The guts header contains all the multiplication and addition macros that are defined for | ||
46 | complex numbers. It also delares the kf_ internal functions. | ||
47 | */ | ||
48 | |||
49 | static void kf_bfly2( | ||
50 | kiss_fft_cpx * Fout, | ||
51 | const size_t fstride, | ||
52 | const kiss_fft_state *st, | ||
53 | int m, | ||
54 | int N, | ||
55 | int mm | ||
56 | ) | ||
57 | { | ||
58 | kiss_fft_cpx * Fout2; | ||
59 | const kiss_twiddle_cpx * tw1; | ||
60 | int i,j; | ||
61 | kiss_fft_cpx * Fout_beg = Fout; | ||
62 | for (i=0;i<N;i++) | ||
63 | { | ||
64 | Fout = Fout_beg + i*mm; | ||
65 | Fout2 = Fout + m; | ||
66 | tw1 = st->twiddles; | ||
67 | for(j=0;j<m;j++) | ||
68 | { | ||
69 | kiss_fft_cpx t; | ||
70 | Fout->r = SHR32(Fout->r, 1);Fout->i = SHR32(Fout->i, 1); | ||
71 | Fout2->r = SHR32(Fout2->r, 1);Fout2->i = SHR32(Fout2->i, 1); | ||
72 | C_MUL (t, *Fout2 , *tw1); | ||
73 | tw1 += fstride; | ||
74 | C_SUB( *Fout2 , *Fout , t ); | ||
75 | C_ADDTO( *Fout , t ); | ||
76 | ++Fout2; | ||
77 | ++Fout; | ||
78 | } | ||
79 | } | ||
80 | } | ||
81 | |||
82 | static void ki_bfly2( | ||
83 | kiss_fft_cpx * Fout, | ||
84 | const size_t fstride, | ||
85 | const kiss_fft_state *st, | ||
86 | int m, | ||
87 | int N, | ||
88 | int mm | ||
89 | ) | ||
90 | { | ||
91 | kiss_fft_cpx * Fout2; | ||
92 | const kiss_twiddle_cpx * tw1; | ||
93 | kiss_fft_cpx t; | ||
94 | int i,j; | ||
95 | kiss_fft_cpx * Fout_beg = Fout; | ||
96 | for (i=0;i<N;i++) | ||
97 | { | ||
98 | Fout = Fout_beg + i*mm; | ||
99 | Fout2 = Fout + m; | ||
100 | tw1 = st->twiddles; | ||
101 | for(j=0;j<m;j++) | ||
102 | { | ||
103 | C_MULC (t, *Fout2 , *tw1); | ||
104 | tw1 += fstride; | ||
105 | C_SUB( *Fout2 , *Fout , t ); | ||
106 | C_ADDTO( *Fout , t ); | ||
107 | ++Fout2; | ||
108 | ++Fout; | ||
109 | } | ||
110 | } | ||
111 | } | ||
112 | |||
113 | static void kf_bfly4( | ||
114 | kiss_fft_cpx * Fout, | ||
115 | const size_t fstride, | ||
116 | const kiss_fft_state *st, | ||
117 | int m, | ||
118 | int N, | ||
119 | int mm | ||
120 | ) | ||
121 | { | ||
122 | const kiss_twiddle_cpx *tw1,*tw2,*tw3; | ||
123 | kiss_fft_cpx scratch[6]; | ||
124 | const size_t m2=2*m; | ||
125 | const size_t m3=3*m; | ||
126 | int i, j; | ||
127 | |||
128 | kiss_fft_cpx * Fout_beg = Fout; | ||
129 | for (i=0;i<N;i++) | ||
130 | { | ||
131 | Fout = Fout_beg + i*mm; | ||
132 | tw3 = tw2 = tw1 = st->twiddles; | ||
133 | for (j=0;j<m;j++) | ||
134 | { | ||
135 | C_MUL4(scratch[0],Fout[m] , *tw1 ); | ||
136 | C_MUL4(scratch[1],Fout[m2] , *tw2 ); | ||
137 | C_MUL4(scratch[2],Fout[m3] , *tw3 ); | ||
138 | |||
139 | Fout->r = PSHR32(Fout->r, 2); | ||
140 | Fout->i = PSHR32(Fout->i, 2); | ||
141 | C_SUB( scratch[5] , *Fout, scratch[1] ); | ||
142 | C_ADDTO(*Fout, scratch[1]); | ||
143 | C_ADD( scratch[3] , scratch[0] , scratch[2] ); | ||
144 | C_SUB( scratch[4] , scratch[0] , scratch[2] ); | ||
145 | Fout[m2].r = PSHR32(Fout[m2].r, 2); | ||
146 | Fout[m2].i = PSHR32(Fout[m2].i, 2); | ||
147 | C_SUB( Fout[m2], *Fout, scratch[3] ); | ||
148 | tw1 += fstride; | ||
149 | tw2 += fstride*2; | ||
150 | tw3 += fstride*3; | ||
151 | C_ADDTO( *Fout , scratch[3] ); | ||
152 | |||
153 | Fout[m].r = scratch[5].r + scratch[4].i; | ||
154 | Fout[m].i = scratch[5].i - scratch[4].r; | ||
155 | Fout[m3].r = scratch[5].r - scratch[4].i; | ||
156 | Fout[m3].i = scratch[5].i + scratch[4].r; | ||
157 | ++Fout; | ||
158 | } | ||
159 | } | ||
160 | } | ||
161 | |||
162 | static void ki_bfly4( | ||
163 | kiss_fft_cpx * Fout, | ||
164 | const size_t fstride, | ||
165 | const kiss_fft_state *st, | ||
166 | int m, | ||
167 | int N, | ||
168 | int mm | ||
169 | ) | ||
170 | { | ||
171 | const kiss_twiddle_cpx *tw1,*tw2,*tw3; | ||
172 | kiss_fft_cpx scratch[6]; | ||
173 | const size_t m2=2*m; | ||
174 | const size_t m3=3*m; | ||
175 | int i, j; | ||
176 | |||
177 | kiss_fft_cpx * Fout_beg = Fout; | ||
178 | for (i=0;i<N;i++) | ||
179 | { | ||
180 | Fout = Fout_beg + i*mm; | ||
181 | tw3 = tw2 = tw1 = st->twiddles; | ||
182 | for (j=0;j<m;j++) | ||
183 | { | ||
184 | C_MULC(scratch[0],Fout[m] , *tw1 ); | ||
185 | C_MULC(scratch[1],Fout[m2] , *tw2 ); | ||
186 | C_MULC(scratch[2],Fout[m3] , *tw3 ); | ||
187 | |||
188 | C_SUB( scratch[5] , *Fout, scratch[1] ); | ||
189 | C_ADDTO(*Fout, scratch[1]); | ||
190 | C_ADD( scratch[3] , scratch[0] , scratch[2] ); | ||
191 | C_SUB( scratch[4] , scratch[0] , scratch[2] ); | ||
192 | C_SUB( Fout[m2], *Fout, scratch[3] ); | ||
193 | tw1 += fstride; | ||
194 | tw2 += fstride*2; | ||
195 | tw3 += fstride*3; | ||
196 | C_ADDTO( *Fout , scratch[3] ); | ||
197 | |||
198 | Fout[m].r = scratch[5].r - scratch[4].i; | ||
199 | Fout[m].i = scratch[5].i + scratch[4].r; | ||
200 | Fout[m3].r = scratch[5].r + scratch[4].i; | ||
201 | Fout[m3].i = scratch[5].i - scratch[4].r; | ||
202 | ++Fout; | ||
203 | } | ||
204 | } | ||
205 | } | ||
206 | |||
207 | #ifndef RADIX_TWO_ONLY | ||
208 | |||
209 | static void kf_bfly3( | ||
210 | kiss_fft_cpx * Fout, | ||
211 | const size_t fstride, | ||
212 | const kiss_fft_state *st, | ||
213 | int m, | ||
214 | int N, | ||
215 | int mm | ||
216 | ) | ||
217 | { | ||
218 | int i; | ||
219 | size_t k; | ||
220 | const size_t m2 = 2*m; | ||
221 | const kiss_twiddle_cpx *tw1,*tw2; | ||
222 | kiss_fft_cpx scratch[5]; | ||
223 | kiss_twiddle_cpx epi3; | ||
224 | |||
225 | kiss_fft_cpx * Fout_beg = Fout; | ||
226 | epi3 = st->twiddles[fstride*m]; | ||
227 | for (i=0;i<N;i++) | ||
228 | { | ||
229 | Fout = Fout_beg + i*mm; | ||
230 | tw1=tw2=st->twiddles; | ||
231 | k=m; | ||
232 | do { | ||
233 | C_FIXDIV(*Fout,3); C_FIXDIV(Fout[m],3); C_FIXDIV(Fout[m2],3); | ||
234 | |||
235 | C_MUL(scratch[1],Fout[m] , *tw1); | ||
236 | C_MUL(scratch[2],Fout[m2] , *tw2); | ||
237 | |||
238 | C_ADD(scratch[3],scratch[1],scratch[2]); | ||
239 | C_SUB(scratch[0],scratch[1],scratch[2]); | ||
240 | tw1 += fstride; | ||
241 | tw2 += fstride*2; | ||
242 | |||
243 | Fout[m].r = Fout->r - HALF_OF(scratch[3].r); | ||
244 | Fout[m].i = Fout->i - HALF_OF(scratch[3].i); | ||
245 | |||
246 | C_MULBYSCALAR( scratch[0] , epi3.i ); | ||
247 | |||
248 | C_ADDTO(*Fout,scratch[3]); | ||
249 | |||
250 | Fout[m2].r = Fout[m].r + scratch[0].i; | ||
251 | Fout[m2].i = Fout[m].i - scratch[0].r; | ||
252 | |||
253 | Fout[m].r -= scratch[0].i; | ||
254 | Fout[m].i += scratch[0].r; | ||
255 | |||
256 | ++Fout; | ||
257 | } while(--k); | ||
258 | } | ||
259 | } | ||
260 | |||
261 | static void ki_bfly3( | ||
262 | kiss_fft_cpx * Fout, | ||
263 | const size_t fstride, | ||
264 | const kiss_fft_state *st, | ||
265 | int m, | ||
266 | int N, | ||
267 | int mm | ||
268 | ) | ||
269 | { | ||
270 | int i, k; | ||
271 | const size_t m2 = 2*m; | ||
272 | const kiss_twiddle_cpx *tw1,*tw2; | ||
273 | kiss_fft_cpx scratch[5]; | ||
274 | kiss_twiddle_cpx epi3; | ||
275 | |||
276 | kiss_fft_cpx * Fout_beg = Fout; | ||
277 | epi3 = st->twiddles[fstride*m]; | ||
278 | for (i=0;i<N;i++) | ||
279 | { | ||
280 | Fout = Fout_beg + i*mm; | ||
281 | tw1=tw2=st->twiddles; | ||
282 | k=m; | ||
283 | do{ | ||
284 | |||
285 | C_MULC(scratch[1],Fout[m] , *tw1); | ||
286 | C_MULC(scratch[2],Fout[m2] , *tw2); | ||
287 | |||
288 | C_ADD(scratch[3],scratch[1],scratch[2]); | ||
289 | C_SUB(scratch[0],scratch[1],scratch[2]); | ||
290 | tw1 += fstride; | ||
291 | tw2 += fstride*2; | ||
292 | |||
293 | Fout[m].r = Fout->r - HALF_OF(scratch[3].r); | ||
294 | Fout[m].i = Fout->i - HALF_OF(scratch[3].i); | ||
295 | |||
296 | C_MULBYSCALAR( scratch[0] , -epi3.i ); | ||
297 | |||
298 | C_ADDTO(*Fout,scratch[3]); | ||
299 | |||
300 | Fout[m2].r = Fout[m].r + scratch[0].i; | ||
301 | Fout[m2].i = Fout[m].i - scratch[0].r; | ||
302 | |||
303 | Fout[m].r -= scratch[0].i; | ||
304 | Fout[m].i += scratch[0].r; | ||
305 | |||
306 | ++Fout; | ||
307 | }while(--k); | ||
308 | } | ||
309 | } | ||
310 | |||
311 | static void kf_bfly5( | ||
312 | kiss_fft_cpx * Fout, | ||
313 | const size_t fstride, | ||
314 | const kiss_fft_state *st, | ||
315 | int m, | ||
316 | int N, | ||
317 | int mm | ||
318 | ) | ||
319 | { | ||
320 | kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4; | ||
321 | int i, u; | ||
322 | kiss_fft_cpx scratch[13]; | ||
323 | const kiss_twiddle_cpx * twiddles = st->twiddles; | ||
324 | const kiss_twiddle_cpx *tw; | ||
325 | kiss_twiddle_cpx ya,yb; | ||
326 | kiss_fft_cpx * Fout_beg = Fout; | ||
327 | |||
328 | ya = twiddles[fstride*m]; | ||
329 | yb = twiddles[fstride*2*m]; | ||
330 | tw=st->twiddles; | ||
331 | |||
332 | for (i=0;i<N;i++) | ||
333 | { | ||
334 | Fout = Fout_beg + i*mm; | ||
335 | Fout0=Fout; | ||
336 | Fout1=Fout0+m; | ||
337 | Fout2=Fout0+2*m; | ||
338 | Fout3=Fout0+3*m; | ||
339 | Fout4=Fout0+4*m; | ||
340 | |||
341 | for ( u=0; u<m; ++u ) { | ||
342 | C_FIXDIV( *Fout0,5); C_FIXDIV( *Fout1,5); C_FIXDIV( *Fout2,5); C_FIXDIV( *Fout3,5); C_FIXDIV( *Fout4,5); | ||
343 | scratch[0] = *Fout0; | ||
344 | |||
345 | C_MUL(scratch[1] ,*Fout1, tw[u*fstride]); | ||
346 | C_MUL(scratch[2] ,*Fout2, tw[2*u*fstride]); | ||
347 | C_MUL(scratch[3] ,*Fout3, tw[3*u*fstride]); | ||
348 | C_MUL(scratch[4] ,*Fout4, tw[4*u*fstride]); | ||
349 | |||
350 | C_ADD( scratch[7],scratch[1],scratch[4]); | ||
351 | C_SUB( scratch[10],scratch[1],scratch[4]); | ||
352 | C_ADD( scratch[8],scratch[2],scratch[3]); | ||
353 | C_SUB( scratch[9],scratch[2],scratch[3]); | ||
354 | |||
355 | Fout0->r += scratch[7].r + scratch[8].r; | ||
356 | Fout0->i += scratch[7].i + scratch[8].i; | ||
357 | |||
358 | scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r); | ||
359 | scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r); | ||
360 | |||
361 | scratch[6].r = S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i); | ||
362 | scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i); | ||
363 | |||
364 | C_SUB(*Fout1,scratch[5],scratch[6]); | ||
365 | C_ADD(*Fout4,scratch[5],scratch[6]); | ||
366 | |||
367 | scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r); | ||
368 | scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r); | ||
369 | scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i); | ||
370 | scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i); | ||
371 | |||
372 | C_ADD(*Fout2,scratch[11],scratch[12]); | ||
373 | C_SUB(*Fout3,scratch[11],scratch[12]); | ||
374 | |||
375 | ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4; | ||
376 | } | ||
377 | } | ||
378 | } | ||
379 | |||
380 | static void ki_bfly5( | ||
381 | kiss_fft_cpx * Fout, | ||
382 | const size_t fstride, | ||
383 | const kiss_fft_state *st, | ||
384 | int m, | ||
385 | int N, | ||
386 | int mm | ||
387 | ) | ||
388 | { | ||
389 | kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4; | ||
390 | int i, u; | ||
391 | kiss_fft_cpx scratch[13]; | ||
392 | const kiss_twiddle_cpx * twiddles = st->twiddles; | ||
393 | const kiss_twiddle_cpx *tw; | ||
394 | kiss_twiddle_cpx ya,yb; | ||
395 | kiss_fft_cpx * Fout_beg = Fout; | ||
396 | |||
397 | ya = twiddles[fstride*m]; | ||
398 | yb = twiddles[fstride*2*m]; | ||
399 | tw=st->twiddles; | ||
400 | |||
401 | for (i=0;i<N;i++) | ||
402 | { | ||
403 | Fout = Fout_beg + i*mm; | ||
404 | Fout0=Fout; | ||
405 | Fout1=Fout0+m; | ||
406 | Fout2=Fout0+2*m; | ||
407 | Fout3=Fout0+3*m; | ||
408 | Fout4=Fout0+4*m; | ||
409 | |||
410 | for ( u=0; u<m; ++u ) { | ||
411 | scratch[0] = *Fout0; | ||
412 | |||
413 | C_MULC(scratch[1] ,*Fout1, tw[u*fstride]); | ||
414 | C_MULC(scratch[2] ,*Fout2, tw[2*u*fstride]); | ||
415 | C_MULC(scratch[3] ,*Fout3, tw[3*u*fstride]); | ||
416 | C_MULC(scratch[4] ,*Fout4, tw[4*u*fstride]); | ||
417 | |||
418 | C_ADD( scratch[7],scratch[1],scratch[4]); | ||
419 | C_SUB( scratch[10],scratch[1],scratch[4]); | ||
420 | C_ADD( scratch[8],scratch[2],scratch[3]); | ||
421 | C_SUB( scratch[9],scratch[2],scratch[3]); | ||
422 | |||
423 | Fout0->r += scratch[7].r + scratch[8].r; | ||
424 | Fout0->i += scratch[7].i + scratch[8].i; | ||
425 | |||
426 | scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r); | ||
427 | scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r); | ||
428 | |||
429 | scratch[6].r = -S_MUL(scratch[10].i,ya.i) - S_MUL(scratch[9].i,yb.i); | ||
430 | scratch[6].i = S_MUL(scratch[10].r,ya.i) + S_MUL(scratch[9].r,yb.i); | ||
431 | |||
432 | C_SUB(*Fout1,scratch[5],scratch[6]); | ||
433 | C_ADD(*Fout4,scratch[5],scratch[6]); | ||
434 | |||
435 | scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r); | ||
436 | scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r); | ||
437 | scratch[12].r = S_MUL(scratch[10].i,yb.i) - S_MUL(scratch[9].i,ya.i); | ||
438 | scratch[12].i = -S_MUL(scratch[10].r,yb.i) + S_MUL(scratch[9].r,ya.i); | ||
439 | |||
440 | C_ADD(*Fout2,scratch[11],scratch[12]); | ||
441 | C_SUB(*Fout3,scratch[11],scratch[12]); | ||
442 | |||
443 | ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4; | ||
444 | } | ||
445 | } | ||
446 | } | ||
447 | |||
448 | #endif | ||
449 | |||
450 | |||
451 | #ifdef CUSTOM_MODES | ||
452 | |||
453 | static | ||
454 | void compute_bitrev_table( | ||
455 | int Fout, | ||
456 | opus_int16 *f, | ||
457 | const size_t fstride, | ||
458 | int in_stride, | ||
459 | opus_int16 * factors, | ||
460 | const kiss_fft_state *st | ||
461 | ) | ||
462 | { | ||
463 | const int p=*factors++; /* the radix */ | ||
464 | const int m=*factors++; /* stage's fft length/p */ | ||
465 | |||
466 | /*printf ("fft %d %d %d %d %d %d\n", p*m, m, p, s2, fstride*in_stride, N);*/ | ||
467 | if (m==1) | ||
468 | { | ||
469 | int j; | ||
470 | for (j=0;j<p;j++) | ||
471 | { | ||
472 | *f = Fout+j; | ||
473 | f += fstride*in_stride; | ||
474 | } | ||
475 | } else { | ||
476 | int j; | ||
477 | for (j=0;j<p;j++) | ||
478 | { | ||
479 | compute_bitrev_table( Fout , f, fstride*p, in_stride, factors,st); | ||
480 | f += fstride*in_stride; | ||
481 | Fout += m; | ||
482 | } | ||
483 | } | ||
484 | } | ||
485 | |||
486 | /* facbuf is populated by p1,m1,p2,m2, ... | ||
487 | where | ||
488 | p[i] * m[i] = m[i-1] | ||
489 | m0 = n */ | ||
490 | static | ||
491 | int kf_factor(int n,opus_int16 * facbuf) | ||
492 | { | ||
493 | int p=4; | ||
494 | |||
495 | /*factor out powers of 4, powers of 2, then any remaining primes */ | ||
496 | do { | ||
497 | while (n % p) { | ||
498 | switch (p) { | ||
499 | case 4: p = 2; break; | ||
500 | case 2: p = 3; break; | ||
501 | default: p += 2; break; | ||
502 | } | ||
503 | if (p>32000 || (opus_int32)p*(opus_int32)p > n) | ||
504 | p = n; /* no more factors, skip to end */ | ||
505 | } | ||
506 | n /= p; | ||
507 | #ifdef RADIX_TWO_ONLY | ||
508 | if (p!=2 && p != 4) | ||
509 | #else | ||
510 | if (p>5) | ||
511 | #endif | ||
512 | { | ||
513 | return 0; | ||
514 | } | ||
515 | *facbuf++ = p; | ||
516 | *facbuf++ = n; | ||
517 | } while (n > 1); | ||
518 | return 1; | ||
519 | } | ||
520 | |||
521 | static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft) | ||
522 | { | ||
523 | int i; | ||
524 | #ifdef FIXED_POINT | ||
525 | for (i=0;i<nfft;++i) { | ||
526 | opus_val32 phase = -i; | ||
527 | kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft)); | ||
528 | } | ||
529 | #else | ||
530 | for (i=0;i<nfft;++i) { | ||
531 | const double pi=3.14159265358979323846264338327; | ||
532 | double phase = ( -2*pi /nfft ) * i; | ||
533 | kf_cexp(twiddles+i, phase ); | ||
534 | } | ||
535 | #endif | ||
536 | } | ||
537 | |||
538 | /* | ||
539 | * | ||
540 | * Allocates all necessary storage space for the fft and ifft. | ||
541 | * The return value is a contiguous block of memory. As such, | ||
542 | * It can be freed with free(). | ||
543 | * */ | ||
544 | kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem, const kiss_fft_state *base) | ||
545 | { | ||
546 | kiss_fft_state *st=NULL; | ||
547 | size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/ | ||
548 | |||
549 | if ( lenmem==NULL ) { | ||
550 | st = ( kiss_fft_state*)KISS_FFT_MALLOC( memneeded ); | ||
551 | }else{ | ||
552 | if (mem != NULL && *lenmem >= memneeded) | ||
553 | st = (kiss_fft_state*)mem; | ||
554 | *lenmem = memneeded; | ||
555 | } | ||
556 | if (st) { | ||
557 | opus_int16 *bitrev; | ||
558 | kiss_twiddle_cpx *twiddles; | ||
559 | |||
560 | st->nfft=nfft; | ||
561 | #ifndef FIXED_POINT | ||
562 | st->scale = 1.f/nfft; | ||
563 | #endif | ||
564 | if (base != NULL) | ||
565 | { | ||
566 | st->twiddles = base->twiddles; | ||
567 | st->shift = 0; | ||
568 | while (nfft<<st->shift != base->nfft && st->shift < 32) | ||
569 | st->shift++; | ||
570 | if (st->shift>=32) | ||
571 | goto fail; | ||
572 | } else { | ||
573 | st->twiddles = twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft); | ||
574 | compute_twiddles(twiddles, nfft); | ||
575 | st->shift = -1; | ||
576 | } | ||
577 | if (!kf_factor(nfft,st->factors)) | ||
578 | { | ||
579 | goto fail; | ||
580 | } | ||
581 | |||
582 | /* bitrev */ | ||
583 | st->bitrev = bitrev = (opus_int16*)KISS_FFT_MALLOC(sizeof(opus_int16)*nfft); | ||
584 | if (st->bitrev==NULL) | ||
585 | goto fail; | ||
586 | compute_bitrev_table(0, bitrev, 1,1, st->factors,st); | ||
587 | } | ||
588 | return st; | ||
589 | fail: | ||
590 | opus_fft_free(st); | ||
591 | return NULL; | ||
592 | } | ||
593 | |||
594 | kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem ) | ||
595 | { | ||
596 | return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL); | ||
597 | } | ||
598 | |||
599 | void opus_fft_free(const kiss_fft_state *cfg) | ||
600 | { | ||
601 | if (cfg) | ||
602 | { | ||
603 | opus_free((opus_int16*)cfg->bitrev); | ||
604 | if (cfg->shift < 0) | ||
605 | opus_free((kiss_twiddle_cpx*)cfg->twiddles); | ||
606 | opus_free((kiss_fft_state*)cfg); | ||
607 | } | ||
608 | } | ||
609 | |||
610 | #endif /* CUSTOM_MODES */ | ||
611 | |||
612 | void opus_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout) | ||
613 | { | ||
614 | int m2, m; | ||
615 | int p; | ||
616 | int L; | ||
617 | int fstride[MAXFACTORS]; | ||
618 | int i; | ||
619 | int shift; | ||
620 | |||
621 | /* st->shift can be -1 */ | ||
622 | shift = st->shift>0 ? st->shift : 0; | ||
623 | |||
624 | celt_assert2 (fin != fout, "In-place FFT not supported"); | ||
625 | /* Bit-reverse the input */ | ||
626 | for (i=0;i<st->nfft;i++) | ||
627 | { | ||
628 | fout[st->bitrev[i]] = fin[i]; | ||
629 | #ifndef FIXED_POINT | ||
630 | fout[st->bitrev[i]].r *= st->scale; | ||
631 | fout[st->bitrev[i]].i *= st->scale; | ||
632 | #endif | ||
633 | } | ||
634 | |||
635 | fstride[0] = 1; | ||
636 | L=0; | ||
637 | do { | ||
638 | p = st->factors[2*L]; | ||
639 | m = st->factors[2*L+1]; | ||
640 | fstride[L+1] = fstride[L]*p; | ||
641 | L++; | ||
642 | } while(m!=1); | ||
643 | m = st->factors[2*L-1]; | ||
644 | for (i=L-1;i>=0;i--) | ||
645 | { | ||
646 | if (i!=0) | ||
647 | m2 = st->factors[2*i-1]; | ||
648 | else | ||
649 | m2 = 1; | ||
650 | switch (st->factors[2*i]) | ||
651 | { | ||
652 | case 2: | ||
653 | kf_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
654 | break; | ||
655 | case 4: | ||
656 | kf_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
657 | break; | ||
658 | #ifndef RADIX_TWO_ONLY | ||
659 | case 3: | ||
660 | kf_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
661 | break; | ||
662 | case 5: | ||
663 | kf_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
664 | break; | ||
665 | #endif | ||
666 | } | ||
667 | m = m2; | ||
668 | } | ||
669 | } | ||
670 | |||
671 | void opus_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout) | ||
672 | { | ||
673 | int m2, m; | ||
674 | int p; | ||
675 | int L; | ||
676 | int fstride[MAXFACTORS]; | ||
677 | int i; | ||
678 | int shift; | ||
679 | |||
680 | /* st->shift can be -1 */ | ||
681 | shift = st->shift>0 ? st->shift : 0; | ||
682 | celt_assert2 (fin != fout, "In-place FFT not supported"); | ||
683 | /* Bit-reverse the input */ | ||
684 | for (i=0;i<st->nfft;i++) | ||
685 | fout[st->bitrev[i]] = fin[i]; | ||
686 | |||
687 | fstride[0] = 1; | ||
688 | L=0; | ||
689 | do { | ||
690 | p = st->factors[2*L]; | ||
691 | m = st->factors[2*L+1]; | ||
692 | fstride[L+1] = fstride[L]*p; | ||
693 | L++; | ||
694 | } while(m!=1); | ||
695 | m = st->factors[2*L-1]; | ||
696 | for (i=L-1;i>=0;i--) | ||
697 | { | ||
698 | if (i!=0) | ||
699 | m2 = st->factors[2*i-1]; | ||
700 | else | ||
701 | m2 = 1; | ||
702 | switch (st->factors[2*i]) | ||
703 | { | ||
704 | case 2: | ||
705 | ki_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
706 | break; | ||
707 | case 4: | ||
708 | ki_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
709 | break; | ||
710 | #ifndef RADIX_TWO_ONLY | ||
711 | case 3: | ||
712 | ki_bfly3(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
713 | break; | ||
714 | case 5: | ||
715 | ki_bfly5(fout,fstride[i]<<shift,st,m, fstride[i], m2); | ||
716 | break; | ||
717 | #endif | ||
718 | } | ||
719 | m = m2; | ||
720 | } | ||
721 | } | ||
722 | |||