algebramix: include/algebramix/fft

00001 
00002 /******************************************************************************
00003 * MODULE     : fft_fixed.hpp
00004 * DESCRIPTION: inlined low-level fft "codelets"
00005 * COPYRIGHT  : (C) 2007  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license and comes WITHOUT
00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00009 * If you don't have this file, write to the Free Software Foundation, Inc.,
00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00011 ******************************************************************************/
00012 
00013 #ifndef __MMX__FFT_FIXED__HPP
00014 #define __MMX__FFT_FIXED__HPP
00015 #include <algebramix/fft_naive.hpp>
00016 
00017 namespace mmx {
00018 
00019 /******************************************************************************
00020 * Inlined fft codelet
00021 ******************************************************************************/
00022 
00023 template<typename D, typename R, nat steps, nat todo> struct fft_large_helper;
00024 template<typename D, typename R, nat steps, nat todo> struct fft_small_helper;
00025 
00026 template<typename D, typename R, nat steps>
00027 struct fft_helper {
00028   static const nat half1= steps >> 1;
00029   static const nat half2= steps - half1;
00030   static const nat n1   = 1 << half1;
00031   static const nat n2   = 1 << half2;
00032   typedef typename R::C C;
00033   typedef typename R::U U;
00034 
00035   static inline void
00036   tf (C* c, nat stride, U* u, nat shift) {
00037     fft_large_helper<D,R,half1,n2>::tf (c, stride<<half2, u, shift>>half2);
00038     fft_small_helper<D,R,half2,n1>::tf (c, stride, u, shift);
00039   }
00040 };
00041 
00042 template<typename R, nat steps>
00043 struct fft_helper<fft_inverse,R,steps> {
00044   static const nat half1= steps >> 1;
00045   static const nat half2= steps - half1;
00046   static const nat n1   = 1 << half1;
00047   static const nat n2   = 1 << half2;
00048   typedef fft_inverse D;
00049   typedef typename R::C C;
00050   typedef typename R::U U;
00051 
00052   static inline void
00053   tf (C* c, nat stride, U* u, nat shift) {
00054     fft_small_helper<D,R,half2,n1>::tf (c, stride, u, shift);
00055     fft_large_helper<D,R,half1,n2>::tf (c, stride<<half2, u, shift>>half2);
00056   }
00057 };
00058 
00059 template<typename D, typename R>
00060 struct fft_helper<D,R,1> {
00061   typedef typename R::C C;
00062   typedef typename R::U U;
00063 
00064   static inline void
00065   tf (C* c, nat stride, U* u, nat shift) {
00066     cross<R,D> (c, c + stride, u + shift);
00067   }
00068 };
00069 
00070 /******************************************************************************
00071 * Unroll loop for large strides
00072 ******************************************************************************/
00073 
00074 template<typename D, typename R, nat steps, nat todo>
00075 struct fft_large_helper {
00076   typedef typename R::C C;
00077   typedef typename R::U U;
00078 
00079   static inline void
00080   tf (C* c, nat stride, U* u, nat shift) {
00081     fft_helper<D,R,steps>::tf (c, stride, u, shift);
00082     fft_large_helper<D,R,steps,todo-1>::tf (c, stride, u, shift);
00083   }
00084 };
00085 
00086 template<typename D, typename R, nat steps>
00087 struct fft_large_helper<D,R,steps,1> {
00088   typedef typename R::C C;
00089   typedef typename R::U U;
00090 
00091   static inline void
00092   tf (C* c, nat stride, U* u, nat shift) {
00093     fft_helper<D,R,steps>::tf (c, stride, u, shift);
00094   }
00095 };
00096 
00097 /******************************************************************************
00098 * Unroll loop for small strides
00099 ******************************************************************************/
00100 
00101 template<typename D, typename R, nat steps, nat todo>
00102 struct fft_small_helper {
00103   typedef typename R::C C;
00104   typedef typename R::U U;
00105 
00106   static inline void
00107   tf (C* c, nat stride, U* u, nat shift) {
00108     fft_helper<D,R,steps>::tf (c, stride, u, shift);
00109     fft_small_helper<D,R,steps,todo-1>::tf (c, stride, u, shift + (1<<steps));
00110   }
00111 };
00112 
00113 template<typename D, typename R, nat steps>
00114 struct fft_small_helper<D,R,steps,1> {
00115   typedef typename R::C C;
00116   typedef typename R::U U;
00117 
00118   static inline void
00119   tf (C* c, nat stride, U* u, nat shift) {
00120     fft_helper<D,R,steps>::tf (c, stride, u, shift);
00121   }
00122 };
00123 
00124 /******************************************************************************
00125 * Code for all sizes
00126 ******************************************************************************/
00127 
00128 template<typename R, nat steps>
00129 struct fft_fixed_helper {
00130   typedef typename R::C C;
00131   typedef typename R::U U;
00132 
00133   template<typename D> static inline void
00134   transform (nat s, C* c, nat stride, U* u, nat shift) {
00135     if (s < steps) fft_fixed_helper<R,steps>::
00136                      template transform<D> (s, c, stride, u, shift);
00137     else fft_helper<D,R,steps>::tf (c, stride, u, shift);
00138   }
00139 };
00140 
00141 template<typename R>
00142 struct fft_fixed_helper<R,1> {
00143   typedef typename R::C C;
00144   typedef typename R::U U;
00145 
00146   template<typename D> static inline void
00147   transform (nat s, C* c, nat stride, U* u, nat shift) {
00148     (void) s;
00149     cross<R,D> (c, c + stride, u + shift);
00150   }
00151 };
00152 
00153 template<typename R>
00154 struct fft_fixed_helper<R,2> {
00155   typedef typename R::C C;
00156   typedef typename R::U U;
00157 
00158   template<typename D> static inline void
00159   transform (nat s, C* c, nat stride, U* u, nat shift) {
00160     switch (s) {
00161     case 1: cross<R,D> (c, c + stride, u + shift); break;
00162     case 2: fft_helper<D,R,2>::tf (c, stride, u, shift); break;
00163     }
00164   }
00165 };
00166 
00167 template<typename R>
00168 struct fft_fixed_helper<R,3> {
00169   typedef typename R::C C;
00170   typedef typename R::U U;
00171 
00172   template<typename D> static inline void
00173   transform (nat s, C* c, nat stride, U* u, nat shift) {
00174     switch (s) {
00175     case 1: cross<R,D> (c, c + stride, u + shift); break;
00176     case 2: fft_helper<D,R,2>::tf (c, stride, u, shift); break;
00177     case 3: fft_helper<D,R,3>::tf (c, stride, u, shift); break;
00178     }
00179   }
00180 };
00181 
00182 template<typename R>
00183 struct fft_fixed_helper<R,4> {
00184   typedef typename R::C C;
00185   typedef typename R::U U;
00186 
00187   template<typename D> static inline void
00188   transform (nat s, C* c, nat stride, U* u, nat shift) {
00189     switch (s) {
00190     case 1: cross<R,D> (c, c + stride, u + shift); break;
00191     case 2: fft_helper<D,R,2>::tf (c, stride, u, shift); break;
00192     case 3: fft_helper<D,R,3>::tf (c, stride, u, shift); break;
00193     case 4: fft_helper<D,R,4>::tf (c, stride, u, shift); break;
00194     }
00195   }
00196 };
00197 
00198 template<typename R>
00199 struct fft_fixed_helper<R,5> {
00200   typedef typename R::C C;
00201   typedef typename R::U U;
00202 
00203   template<typename D> static inline void
00204   transform (nat s, C* c, nat stride, U* u, nat shift) {
00205     switch (s) {
00206     case 1: cross<R,D> (c, c + stride, u + shift); break;
00207     case 2: fft_helper<D,R,2>::tf (c, stride, u, shift); break;
00208     case 3: fft_helper<D,R,3>::tf (c, stride, u, shift); break;
00209     case 4: fft_helper<D,R,4>::tf (c, stride, u, shift); break;
00210     case 5: fft_helper<D,R,5>::tf (c, stride, u, shift); break;
00211     }
00212   }
00213 };
00214 
00215 template<typename R>
00216 struct fft_fixed_helper<R,6> {
00217   typedef typename R::C C;
00218   typedef typename R::U U;
00219 
00220   template<typename D> static inline void
00221   transform (nat s, C* c, nat stride, U* u, nat shift) {
00222     switch (s) {
00223     case 1: cross<R,D> (c, c + stride, u + shift); break;
00224     case 2: fft_helper<D,R,2>::tf (c, stride, u, shift); break;
00225     case 3: fft_helper<D,R,3>::tf (c, stride, u, shift); break;
00226     case 4: fft_helper<D,R,4>::tf (c, stride, u, shift); break;
00227     case 5: fft_helper<D,R,5>::tf (c, stride, u, shift); break;
00228     case 6: fft_helper<D,R,6>::tf (c, stride, u, shift); break;
00229     }
00230   }
00231 };
00232 
00233 } // namespace mmx
00234 #endif //__MMX__FFT_FIXED__HPP
include/algebramix/fft_fixed.hpp
