From 210092d16c57ec2fd2f8f515151de284e8a737e3 Mon Sep 17 00:00:00 2001 From: Mark Borgerding Date: Mon, 25 May 2009 20:35:24 -0400 Subject: changed name from simple_fft_traits to ei_kissfft_impl --- bench/benchFFT.cpp | 2 +- unsupported/Eigen/FFT | 95 ++++++ unsupported/Eigen/FFT.h | 95 ------ unsupported/Eigen/src/FFT/ei_kissfft_impl.h | 397 ++++++++++++++++++++++++++ unsupported/Eigen/src/FFT/simple_fft_traits.h | 374 ------------------------ unsupported/test/FFT.cpp | 3 +- 6 files changed, 494 insertions(+), 472 deletions(-) create mode 100644 unsupported/Eigen/FFT delete mode 100644 unsupported/Eigen/FFT.h create mode 100644 unsupported/Eigen/src/FFT/ei_kissfft_impl.h delete mode 100644 unsupported/Eigen/src/FFT/simple_fft_traits.h diff --git a/bench/benchFFT.cpp b/bench/benchFFT.cpp index 84cc49fe3..ffa4ffffc 100644 --- a/bench/benchFFT.cpp +++ b/bench/benchFFT.cpp @@ -26,7 +26,7 @@ #include #include #include -#include +#include using namespace Eigen; using namespace std; diff --git a/unsupported/Eigen/FFT b/unsupported/Eigen/FFT new file mode 100644 index 000000000..3d852f5a2 --- /dev/null +++ b/unsupported/Eigen/FFT @@ -0,0 +1,95 @@ +// This file is part of Eigen, a lightweight C++ template library +// for linear algebra. Eigen itself is part of the KDE project. +// +// Copyright (C) 2009 Mark Borgerding mark a borgerding net +// +// Eigen is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 3 of the License, or (at your option) any later version. +// +// Alternatively, you can redistribute it and/or +// modify it under the terms of the GNU General Public License as +// published by the Free Software Foundation; either version 2 of +// the License, or (at your option) any later version. +// +// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY +// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License and a copy of the GNU General Public License along with +// Eigen. If not, see . + +#ifndef EIGEN_FFT_H +#define EIGEN_FFT_H + +// ei_kissfft_impl: small, free, reasonably efficient default, derived from kissfft +#include "src/FFT/ei_kissfft_impl.h" +#define DEFAULT_FFT_IMPL ei_kissfft_impl + +// FFTW: faster, GPL-not LGPL, bigger code size +#ifdef FFTW_PATIENT // definition of FFTW_PATIENT indicates the caller has included fftw3.h, we can use FFTW routines +// TODO +// #include "src/FFT/ei_fftw_impl.h" +// #define DEFAULT_FFT_IMPL ei_fftw_impl +#endif + +// intel Math Kernel Library: fastest, commerical +#ifdef _MKL_DFTI_H_ // mkl_dfti.h has been included, we can use MKL FFT routines +// TODO +// #include "src/FFT/ei_imkl_impl.h" +// #define DEFAULT_FFT_IMPL ei_imkl_impl +#endif + +namespace Eigen { + +template + > +class FFT +{ + public: + typedef _Traits traits_type; + typedef typename traits_type::Scalar Scalar; + typedef typename traits_type::Complex Complex; + + FFT(const traits_type & traits=traits_type() ) :m_traits(traits) { } + + template + void fwd( Complex * dst, const _Input * src, int nfft) + { + m_traits.fwd(dst,src,nfft); + } + + template + void fwd( std::vector & dst, const std::vector<_Input> & src) + { + dst.resize( src.size() ); + fwd( &dst[0],&src[0],src.size() ); + } + + template + void inv( _Output * dst, const Complex * src, int nfft) + { + m_traits.inv( dst,src,nfft ); + } + + template + void inv( std::vector<_Output> & dst, const std::vector & src) + { + dst.resize( src.size() ); + inv( &dst[0],&src[0],src.size() ); + } + + // TODO: multi-dimensional FFTs + // TODO: handle Eigen MatrixBase + + traits_type & traits() {return m_traits;} + private: + traits_type m_traits; +}; +#undef DEFAULT_FFT_IMPL +} +#endif diff --git a/unsupported/Eigen/FFT.h b/unsupported/Eigen/FFT.h deleted file mode 100644 index c466423b7..000000000 --- a/unsupported/Eigen/FFT.h +++ /dev/null @@ -1,95 +0,0 @@ -// This file is part of Eigen, a lightweight C++ template library -// for linear algebra. Eigen itself is part of the KDE project. -// -// Copyright (C) 2009 Mark Borgerding mark a borgerding net -// -// Eigen is free software; you can redistribute it and/or -// modify it under the terms of the GNU Lesser General Public -// License as published by the Free Software Foundation; either -// version 3 of the License, or (at your option) any later version. -// -// Alternatively, you can redistribute it and/or -// modify it under the terms of the GNU General Public License as -// published by the Free Software Foundation; either version 2 of -// the License, or (at your option) any later version. -// -// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY -// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS -// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the -// GNU General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public -// License and a copy of the GNU General Public License along with -// Eigen. If not, see . - -#ifndef EIGEN_FFT_H -#define EIGEN_FFT_H - -// simple_fft_traits: small, free, reasonably efficient default, derived from kissfft -#include "src/FFT/simple_fft_traits.h" -#define DEFAULT_FFT_TRAITS simple_fft_traits - -// FFTW: faster, GPL-not LGPL, bigger code size -#ifdef FFTW_PATIENT // definition of FFTW_PATIENT indicates the caller has included fftw3.h, we can use FFTW routines -// TODO -// #include "src/FFT/fftw_traits.h" -// #define DEFAULT_FFT_TRAITS fftw_traits -#endif - -// intel Math Kernel Library: fastest, commerical -#ifdef _MKL_DFTI_H_ // mkl_dfti.h has been included, we can use MKL FFT routines -// TODO -// #include "src/FFT/imkl_traits.h" -// #define DEFAULT_FFT_TRAITS imkl_traits -#endif - -namespace Eigen { - -template - > -class FFT -{ - public: - typedef _Traits traits_type; - typedef typename traits_type::Scalar Scalar; - typedef typename traits_type::Complex Complex; - - FFT(const traits_type & traits=traits_type() ) :m_traits(traits) { } - - template - void fwd( Complex * dst, const _Input * src, int nfft) - { - m_traits.fwd(dst,src,nfft); - } - - template - void fwd( std::vector & dst, const std::vector<_Input> & src) - { - dst.resize( src.size() ); - fwd( &dst[0],&src[0],src.size() ); - } - - template - void inv( _Output * dst, const Complex * src, int nfft) - { - m_traits.inv( dst,src,nfft ); - } - - template - void inv( std::vector<_Output> & dst, const std::vector & src) - { - dst.resize( src.size() ); - inv( &dst[0],&src[0],src.size() ); - } - - // TODO: multi-dimensional FFTs - // TODO: handle Eigen MatrixBase - - traits_type & traits() {return m_traits;} - private: - traits_type m_traits; -}; -#undef DEFAULT_FFT_TRAITS -} -#endif diff --git a/unsupported/Eigen/src/FFT/ei_kissfft_impl.h b/unsupported/Eigen/src/FFT/ei_kissfft_impl.h new file mode 100644 index 000000000..ce2c9f16e --- /dev/null +++ b/unsupported/Eigen/src/FFT/ei_kissfft_impl.h @@ -0,0 +1,397 @@ +// This file is part of Eigen, a lightweight C++ template library +// for linear algebra. Eigen itself is part of the KDE project. +// +// Copyright (C) 2009 Mark Borgerding mark a borgerding net +// +// Eigen is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 3 of the License, or (at your option) any later version. +// +// Alternatively, you can redistribute it and/or +// modify it under the terms of the GNU General Public License as +// published by the Free Software Foundation; either version 2 of +// the License, or (at your option) any later version. +// +// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY +// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License and a copy of the GNU General Public License along with +// Eigen. If not, see . + +#include +#include + +namespace Eigen { + + template + struct ei_kissfft_impl + { + typedef _Scalar Scalar; + typedef std::complex Complex; + ei_kissfft_impl() : m_nfft(0) {} + + template + void fwd( Complex * dst,const _Src *src,int nfft) + { + prepare(nfft,false); + work(0, dst, src, 1,1); + } + + // real-to-complex forward FFT + // perform two FFTs of src even and src odd + // then twiddle to recombine them into the half-spectrum format + // then fill in the conjugate symmetric half + void fwd( Complex * dst,const Scalar * src,int nfft) + { + if ( nfft&1 ) { + // use generic mode for odd + prepare(nfft,false); + work(0, dst, src, 1,1); + }else{ + int ncfft = nfft>>1; + int ncfft2 = nfft>>2; + // use optimized mode for even real + fwd( dst, reinterpret_cast (src),ncfft); + make_real_twiddles(nfft); + Complex dc = dst[0].real() + dst[0].imag(); + Complex nyquist = dst[0].real() - dst[0].imag(); + int k; + for ( k=1;k <= ncfft2 ; ++k ) { + Complex fpk = dst[k]; + Complex fpnk = conj(dst[ncfft-k]); + Complex f1k = fpk + fpnk; + Complex f2k = fpk - fpnk; + //Complex tw = f2k * exp( Complex(0,-3.14159265358979323846264338327 * ((double) (k) / ncfft + .5) ) ); + Complex tw= f2k * m_realTwiddles[k-1]; + + dst[k] = (f1k + tw) * Scalar(.5); + dst[ncfft-k] = conj(f1k -tw)*Scalar(.5); + } + + // place conjugate-symmetric half at the end for completeness + // TODO: make this configurable ( opt-out ) + for ( k=1;k < ncfft ; ++k ) + dst[nfft-k] = conj(dst[k]); + + dst[0] = dc; + dst[ncfft] = nyquist; + } + } + + // half-complex to scalar + void inv( Scalar * dst,const Complex * src,int nfft) + { + // TODO add optimized version for even numbers + std::vector tmp(nfft); + inv(&tmp[0],src,nfft); + for (int k=0;k>2; + if ( m_realTwiddles.size() != ncfft2) { + m_realTwiddles.resize(ncfft2); + int ncfft= nfft>>1; + for (int k=1;k<=ncfft2;++k) + m_realTwiddles[k-1] = exp( Complex(0,-3.14159265358979323846264338327 * ((double) (k) / ncfft + .5) ) ); + } + } + + void make_twiddles(int nfft,bool inverse) + { + if ( m_twiddles.size() == nfft) { + // reuse the twiddles, conjugate if necessary + if (inverse != m_inverse) + for (int i=0;in) + p=n;// impossible to have a factor > sqrt(n) + } + n /= p; + m_stageRadix.push_back(p); + m_stageRemainder.push_back(n); + }while(n>1); + } + m_nfft = nfft; + } + + void scale(Complex *dst,Scalar s) + { + for (int k=0;k + void work( int stage,Complex * xout, const _Src * xin, size_t fstride,size_t in_stride) + { + int p = m_stageRadix[stage]; + int m = m_stageRemainder[stage]; + Complex * Fout_beg = xout; + Complex * Fout_end = xout + p*m; + + if (m>1) { + do{ + // recursive call: + // DFT of size m*p performed by doing + // p instances of smaller DFTs of size m, + // each one takes a decimated version of the input + work(stage+1, xout , xin, fstride*p,in_stride); + xin += fstride*in_stride; + }while( (xout += m) != Fout_end ); + }else{ + do{ + *xout = *xin; + xin += fstride*in_stride; + }while(++xout != Fout_end ); + } + xout=Fout_beg; + + // recombine the p smaller DFTs + switch (p) { + case 2: bfly2(xout,fstride,m); break; + case 3: bfly3(xout,fstride,m); break; + case 4: bfly4(xout,fstride,m); break; + case 5: bfly5(xout,fstride,m); break; + default: bfly_generic(xout,fstride,m,p); break; + } + } + + void bfly2( Complex * Fout, const size_t fstride, int m) + { + for (int k=0;kreal() - .5*scratch[3].real() , Fout->imag() - .5*scratch[3].imag() ); + scratch[0] *= epi3.imag(); + *Fout += scratch[3]; + Fout[m2] = Complex( Fout[m].real() + scratch[0].imag() , Fout[m].imag() - scratch[0].real() ); + Fout[m] += Complex( -scratch[0].imag(),scratch[0].real() ); + ++Fout; + }while(--k); + } + + void bfly5( Complex * Fout, const size_t fstride, const size_t m) + { + Complex *Fout0,*Fout1,*Fout2,*Fout3,*Fout4; + size_t u; + Complex scratch[13]; + Complex * twiddles = &m_twiddles[0]; + Complex *tw; + Complex ya,yb; + ya = twiddles[fstride*m]; + yb = twiddles[fstride*2*m]; + + Fout0=Fout; + Fout1=Fout0+m; + Fout2=Fout0+2*m; + Fout3=Fout0+3*m; + Fout4=Fout0+4*m; + + tw=twiddles; + for ( u=0; u=Norig) twidx-=Norig; + t=scratchbuf[q] * twiddles[twidx]; + Fout[ k ] += t; + } + k += m; + } + } + } + + int m_nfft; + bool m_inverse; + std::vector m_twiddles; + std::vector m_realTwiddles; + std::vector m_stageRadix; + std::vector m_stageRemainder; +/* + enum {FORWARD,INVERSE,REAL,COMPLEX}; + + struct PlanKey + { + PlanKey(int nfft,bool isinverse,bool iscomplex) + { + _key = (nfft<<2) | (isinverse<<1) | iscomplex; + } + + bool operator<(const PlanKey & other) const + { + return this->_key < other._key; + } + int _key; + }; + + struct PlanData + { + std::vector m_twiddles; + }; + + std::map. - -#include -#include -#include - -namespace Eigen { - - template - struct simple_fft_traits - { - typedef _Scalar Scalar; - typedef std::complex Complex; - simple_fft_traits() : m_nfft(0) {} - - template - void fwd( Complex * dst,const _Src *src,int nfft) - { - prepare(nfft,false); - work(0, dst, src, 1,1); - } - - // real-to-complex forward FFT - // perform two FFTs of src even and src odd - // then twiddle to recombine them into the half-spectrum format - // then fill in the conjugate symmetric half - void fwd( Complex * dst,const Scalar * src,int nfft) - { - if ( nfft&1 ) { - // use generic mode for odd - prepare(nfft,false); - work(0, dst, src, 1,1); - }else{ - int ncfft = nfft>>1; - int ncfft2 = nfft>>2; - // use optimized mode for even real - fwd( dst, reinterpret_cast (src),ncfft); - make_real_twiddles(nfft); - Complex dc = dst[0].real() + dst[0].imag(); - Complex nyquist = dst[0].real() - dst[0].imag(); - int k; - for ( k=1;k <= ncfft2 ; ++k ) { - Complex fpk = dst[k]; - Complex fpnk = conj(dst[ncfft-k]); - Complex f1k = fpk + fpnk; - Complex f2k = fpk - fpnk; - //Complex tw = f2k * exp( Complex(0,-3.14159265358979323846264338327 * ((double) (k) / ncfft + .5) ) ); - Complex tw= f2k * m_realTwiddles[k-1]; - - dst[k] = (f1k + tw) * Scalar(.5); - dst[ncfft-k] = conj(f1k -tw)*Scalar(.5); - } - - // place conjugate-symmetric half at the end for completeness - // TODO: make this configurable ( opt-out ) - for ( k=1;k < ncfft ; ++k ) - dst[nfft-k] = conj(dst[k]); - - dst[0] = dc; - dst[ncfft] = nyquist; - } - } - - // half-complex to scalar - void inv( Scalar * dst,const Complex * src,int nfft) - { - // TODO add optimized version for even numbers - std::vector tmp(nfft); - inv(&tmp[0],src,nfft); - for (int k=0;k>2; - if ( m_realTwiddles.size() != ncfft2) { - m_realTwiddles.resize(ncfft2); - int ncfft= nfft>>1; - for (int k=1;k<=ncfft2;++k) - m_realTwiddles[k-1] = exp( Complex(0,-3.14159265358979323846264338327 * ((double) (k) / ncfft + .5) ) ); - } - } - - void make_twiddles(int nfft,bool inverse) - { - if ( m_twiddles.size() == nfft) { - // reuse the twiddles, conjugate if necessary - if (inverse != m_inverse) - for (int i=0;in) - p=n;// impossible to have a factor > sqrt(n) - } - n /= p; - m_stageRadix.push_back(p); - m_stageRemainder.push_back(n); - }while(n>1); - } - m_nfft = nfft; - } - - void scale(Complex *dst,Scalar s) - { - for (int k=0;k - void work( int stage,Complex * xout, const _Src * xin, size_t fstride,size_t in_stride) - { - int p = m_stageRadix[stage]; - int m = m_stageRemainder[stage]; - Complex * Fout_beg = xout; - Complex * Fout_end = xout + p*m; - - if (m>1) { - do{ - // recursive call: - // DFT of size m*p performed by doing - // p instances of smaller DFTs of size m, - // each one takes a decimated version of the input - work(stage+1, xout , xin, fstride*p,in_stride); - xin += fstride*in_stride; - }while( (xout += m) != Fout_end ); - }else{ - do{ - *xout = *xin; - xin += fstride*in_stride; - }while(++xout != Fout_end ); - } - xout=Fout_beg; - - // recombine the p smaller DFTs - switch (p) { - case 2: bfly2(xout,fstride,m); break; - case 3: bfly3(xout,fstride,m); break; - case 4: bfly4(xout,fstride,m); break; - case 5: bfly5(xout,fstride,m); break; - default: bfly_generic(xout,fstride,m,p); break; - } - } - - void bfly2( Complex * Fout, const size_t fstride, int m) - { - for (int k=0;kreal() - .5*scratch[3].real() , Fout->imag() - .5*scratch[3].imag() ); - scratch[0] *= epi3.imag(); - *Fout += scratch[3]; - Fout[m2] = Complex( Fout[m].real() + scratch[0].imag() , Fout[m].imag() - scratch[0].real() ); - Fout[m] += Complex( -scratch[0].imag(),scratch[0].real() ); - ++Fout; - }while(--k); - } - - void bfly5( Complex * Fout, const size_t fstride, const size_t m) - { - Complex *Fout0,*Fout1,*Fout2,*Fout3,*Fout4; - size_t u; - Complex scratch[13]; - Complex * twiddles = &m_twiddles[0]; - Complex *tw; - Complex ya,yb; - ya = twiddles[fstride*m]; - yb = twiddles[fstride*2*m]; - - Fout0=Fout; - Fout1=Fout0+m; - Fout2=Fout0+2*m; - Fout3=Fout0+3*m; - Fout4=Fout0+4*m; - - tw=twiddles; - for ( u=0; u=Norig) twidx-=Norig; - t=scratchbuf[q] * twiddles[twidx]; - Fout[ k ] += t; - } - k += m; - } - } - } - - int m_nfft; - bool m_inverse; - std::vector m_twiddles; - std::vector m_realTwiddles; - std::vector m_stageRadix; - std::vector m_stageRemainder; - }; -} diff --git a/unsupported/test/FFT.cpp b/unsupported/test/FFT.cpp index 75c33277d..daf397790 100644 --- a/unsupported/test/FFT.cpp +++ b/unsupported/test/FFT.cpp @@ -23,8 +23,7 @@ // Eigen. If not, see . #include "main.h" -#include - +#include using namespace std; -- cgit v1.2.3