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 #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 = SHR(Fout->r, 1);Fout->i = SHR(Fout->i, 1);
  71          Fout2->r = SHR(Fout2->r, 1);Fout2->i = SHR(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 = PSHR(Fout->r, 2);
 140          Fout->i = PSHR(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 = PSHR(Fout[m2].r, 2);
 146          Fout[m2].i = PSHR(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./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