|
algebramix_doc 0.3
|
|
algebramix_doc 0.3
|
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
1.7.4 
