Sharing of the twiddles across multiple FFTs
authorJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Fri, 9 Jul 2010 00:54:32 +0000 (20:54 -0400)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Fri, 9 Jul 2010 00:54:32 +0000 (20:54 -0400)
libcelt/_kiss_fft_guts.h
libcelt/kfft_double.h
libcelt/kiss_fft.c
libcelt/kiss_fft.h
libcelt/mdct.c

index 736fa19..dc99ee3 100644 (file)
@@ -35,9 +35,10 @@ struct kiss_fft_state{
 #ifndef FIXED_POINT
     kiss_fft_scalar scale;
 #endif
+    int shift;
     int factors[2*MAXFACTORS];
     int *bitrev;
-    kiss_twiddle_cpx twiddles[1];
+    kiss_twiddle_cpx *twiddles;
 };
 
 /*
index 43b38b0..251536b 100644 (file)
@@ -69,7 +69,8 @@
 #include "kiss_fft.h"
 #include "_kiss_fft_guts.h"
 
-#define cpx32_fft_alloc(length) kiss_fft_alloc(length, 0, 0);
+#define cpx32_fft_alloc_twiddles(length,from) kiss_fft_alloc_twiddles(length, 0, 0, from)
+#define cpx32_fft_alloc(length) kiss_fft_alloc(length, 0, 0)
 #define cpx32_fft_free(state) kiss_fft_free(state)
 #define cpx32_fft(state, X, Y, nx) kiss_fft(state,(const kiss_fft_cpx *)(X), (kiss_fft_cpx *)(Y))
 #define cpx32_ifft(state, X, Y, nx) kiss_ifft(state,(const kiss_fft_cpx *)(X), (kiss_fft_cpx *)(Y))
index 2968a8d..d8c86a7 100644 (file)
@@ -470,7 +470,7 @@ void compute_bitrev_table(
 void kf_work(
         kiss_fft_cpx * Fout,
         const kiss_fft_cpx * f,
-        const size_t fstride,
+        size_t fstride,
         int in_stride,
         int * factors,
         const kiss_fft_cfg st,
@@ -485,6 +485,9 @@ void kf_work(
     if (m!=1) 
         kf_work( Fout , f, fstride*p, in_stride, factors,st, N*p, fstride*in_stride, m);
 
+    /* Compensate for longer twiddles table (when sharing) */
+    if (st->shift>0)
+       fstride <<= st->shift;
     switch (p) {
         case 2: kf_bfly2(Fout,fstride,st,m, N, m2); break;
         case 4: kf_bfly4(Fout,fstride,st,m, N, m2); break;
@@ -501,7 +504,7 @@ void kf_work(
 void ki_work(
              kiss_fft_cpx * Fout,
              const kiss_fft_cpx * f,
-             const size_t fstride,
+             size_t fstride,
              int in_stride,
              int * factors,
              const kiss_fft_cfg st,
@@ -516,6 +519,9 @@ void ki_work(
    if (m!=1) 
       ki_work( Fout , f, fstride*p, in_stride, factors,st, N*p, fstride*in_stride, m);
 
+   /* Compensate for longer twiddles table (when sharing) */
+   if (st->shift>0)
+      fstride <<= st->shift;
    switch (p) {
       case 2: ki_bfly2(Fout,fstride,st,m, N, m2); break;
       case 4: ki_bfly4(Fout,fstride,st,m, N, m2); break;
@@ -559,6 +565,25 @@ int kf_factor(int n,int * facbuf)
     } while (n > 1);
     return 1;
 }
+
+static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
+{
+   int i;
+#if defined(FIXED_POINT) && (!defined(DOUBLE_PRECISION) || defined(MIXED_PRECISION))
+   for (i=0;i<nfft;++i) {
+      celt_word32 phase = -i;
+      kf_cexp2(twiddles+i, DIV32(SHL32(phase,17),nfft));
+   }
+#else
+   for (i=0;i<nfft;++i) {
+      const double pi=3.14159265358979323846264338327;
+      double phase = ( -2*pi /nfft ) * i;
+      kf_cexp(twiddles+i, phase );
+   }
+#endif
+}
+
+
 /*
  *
  * User-callable function to allocate all necessary storage space for the fft.
@@ -566,11 +591,10 @@ int kf_factor(int n,int * facbuf)
  * The return value is a contiguous block of memory, allocated with malloc.  As such,
  * It can be freed with free(), rather than a kiss_fft-specific function.
  * */
-kiss_fft_cfg kiss_fft_alloc(int nfft,void * mem,size_t * lenmem )
+kiss_fft_cfg kiss_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  kiss_fft_cfg base)
 {
     kiss_fft_cfg st=NULL;
-    size_t memneeded = sizeof(struct kiss_fft_state)
-          + sizeof(kiss_twiddle_cpx)*(nfft-1) + sizeof(int)*nfft; /* twiddle factors*/
+    size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
 
     if ( lenmem==NULL ) {
         st = ( kiss_fft_cfg)KISS_FFT_MALLOC( memneeded );
@@ -580,23 +604,24 @@ kiss_fft_cfg kiss_fft_alloc(int nfft,void * mem,size_t * lenmem )
         *lenmem = memneeded;
     }
     if (st) {
-        int i;
         st->nfft=nfft;
 #ifndef FIXED_POINT
         st->scale = 1./nfft;
 #endif
-#if defined(FIXED_POINT) && (!defined(DOUBLE_PRECISION) || defined(MIXED_PRECISION))
-        for (i=0;i<nfft;++i) {
-            celt_word32 phase = -i;
-            kf_cexp2(st->twiddles+i, DIV32(SHL32(phase,17),nfft));
-        }
-#else
-        for (i=0;i<nfft;++i) {
-           const double pi=3.14159265358979323846264338327;
-           double phase = ( -2*pi /nfft ) * i;
-           kf_cexp(st->twiddles+i, phase );
+        if (base != NULL)
+        {
+           st->twiddles = base->twiddles;
+           st->shift = 0;
+           while (nfft<<st->shift != base->nfft && st->shift < 32)
+              st->shift++;
+           /* FIXME: Report error and do proper cleanup */
+           if (st->shift>=32)
+              return NULL;
+        } else {
+           st->twiddles = (kiss_twiddle_cpx*)KISS_FFT_MALLOC(sizeof(kiss_twiddle_cpx)*nfft);
+           compute_twiddles(st->twiddles, nfft);
+           st->shift = -1;
         }
-#endif
         if (!kf_factor(nfft,st->factors))
         {
            kiss_fft_free(st);
@@ -604,13 +629,16 @@ kiss_fft_cfg kiss_fft_alloc(int nfft,void * mem,size_t * lenmem )
         }
         
         /* bitrev */
-        st->bitrev = (int*)((char*)st + memneeded - sizeof(int)*nfft);
+        st->bitrev = (int*)KISS_FFT_MALLOC(sizeof(int)*nfft);
         compute_bitrev_table(0, st->bitrev, 1,1, st->factors,st);
     }
     return st;
 }
 
-
+kiss_fft_cfg kiss_fft_alloc(int nfft,void * mem,size_t * lenmem )
+{
+   return kiss_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
+}
 
     
 void kiss_fft_stride(kiss_fft_cfg st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout,int in_stride)
@@ -657,3 +685,10 @@ void kiss_ifft(kiss_fft_cfg cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
    kiss_ifft_stride(cfg,fin,fout,1);
 }
 
+void kiss_fft_free(kiss_fft_cfg cfg)
+{
+   celt_free(cfg->bitrev);
+   if (cfg->shift < 0)
+      celt_free(cfg->twiddles);
+   celt_free(cfg);
+}
index 1c46206..8acb397 100644 (file)
@@ -75,6 +75,7 @@ extern "C" {
 #define CAT_SUFFIX(a,b) a ## b
 #define SUF(a,b) CAT_SUFFIX(a, b)
 
+#define kiss_fft_alloc_twiddles SUF(kiss_fft_alloc_twiddles,KF_SUFFIX)
 #define kiss_fft_alloc SUF(kiss_fft_alloc,KF_SUFFIX)
 #define kf_work SUF(kf_work,KF_SUFFIX)
 #define ki_work SUF(ki_work,KF_SUFFIX)
@@ -82,6 +83,7 @@ extern "C" {
 #define kiss_ifft SUF(kiss_ifft,KF_SUFFIX)
 #define kiss_fft_stride SUF(kiss_fft_stride,KF_SUFFIX)
 #define kiss_ifft_stride SUF(kiss_ifft_stride,KF_SUFFIX)
+#define kiss_fft_free SUF(kiss_fft_free,KF_SUFFIX)
 
 
 typedef struct {
@@ -119,13 +121,15 @@ typedef struct kiss_fft_state* kiss_fft_cfg;
  *      buffer size in *lenmem.
  * */
 
+kiss_fft_cfg kiss_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  kiss_fft_cfg base);
+
 kiss_fft_cfg kiss_fft_alloc(int nfft,void * mem,size_t * lenmem); 
 
-void kf_work(kiss_fft_cpx * Fout,const kiss_fft_cpx * f,const size_t fstride,
+void kf_work(kiss_fft_cpx * Fout,const kiss_fft_cpx * f,size_t fstride,
              int in_stride,int * factors,const kiss_fft_cfg st,int N,int s2,int m2);
 
 /** Internal function. Can be useful when you want to do the bit-reversing yourself */
-void ki_work(kiss_fft_cpx * Fout, const kiss_fft_cpx * f, const size_t fstride,
+void ki_work(kiss_fft_cpx * Fout, const kiss_fft_cpx * f, size_t fstride,
              int in_stride,int * factors,const kiss_fft_cfg st,int N,int s2,int m2);
 
 /**
@@ -147,9 +151,7 @@ void kiss_ifft(kiss_fft_cfg cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout);
 void kiss_fft_stride(kiss_fft_cfg cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout,int fin_stride);
 void kiss_ifft_stride(kiss_fft_cfg cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout,int fin_stride);
 
-/** If kiss_fft_alloc allocated a buffer, it is one contiguous 
-   buffer and can be simply free()d when no longer needed*/
-#define kiss_fft_free celt_free
+void kiss_fft_free(kiss_fft_cfg cfg);
 
 
 #ifdef __cplusplus
index 653aff0..7a48eac 100644 (file)
@@ -69,7 +69,10 @@ void clt_mdct_init(mdct_lookup *l,int N, int maxshift)
    l->maxshift = maxshift;
    for (i=0;i<=maxshift;i++)
    {
-      l->kfft[i] = cpx32_fft_alloc(N>>2>>i);
+      if (i==0)
+         l->kfft[i] = cpx32_fft_alloc(N>>2>>i);
+      else
+         l->kfft[i] = cpx32_fft_alloc_twiddles(N>>2>>i, l->kfft[0]);
 #ifndef ENABLE_TI_DSPLIB55
       if (l->kfft[i]==NULL)
          return;