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 "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 723
