celt/kiss_fft.c

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