Generative Fast Fourier Transforms (GFFT)  0.3
gfftstdalg.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2006-2014 by Vladimir Mirnyy *
3  * *
4  * This program is free software; you can redistribute it and/or modify *
5  * it under the terms of the GNU General Public License as published by *
6  * the Free Software Foundation; either version 2 of the License, or *
7  * (at your option) any later version. *
8  * *
9  * This program is distributed in the hope that it will be useful, *
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12  * GNU General Public License for more details. *
13  ***************************************************************************/
14 
15 #ifndef __gfftstdalg_h
16 #define __gfftstdalg_h
17 
23 #include "gfftstdspec.h"
24 #include "gfftfactor.h"
25 #include "gfftswap.h"
26 
27 #include "metacomplex.h"
28 #include "metaroot.h"
29 
30 namespace GFFT {
31 
32 using namespace MF;
33 
34 
36 
49 template<int_t K, int_t M, typename T, int S, class W, bool doStaticLoop>
50 class DFTk_x_Im_T;
51 
52 template<int_t K, int_t M, typename T, int S, class W,
53 template<typename> class Complex>
54 class DFTk_x_Im_T<K,M,Complex<T>,S,W,false>
55 {
56  //typedef typename TempTypeTrait<T>::Result LocalVType;
57  typedef Compute<typename W::Re,2> WR;
58  typedef Compute<typename W::Im,2> WI;
59  static const int_t N = K*M;
60  DFTk_inp<K,M,Complex<T>,S> spec_inp;
61 public:
62  void apply(Complex<T>* data)
63  {
64  spec_inp.apply(data);
65 
66  Complex<T> w[K-1], wp[K-1];
67 
68  // W = (wpr[0], wpi[0])
69  wp[0] = Complex<T>(WR::value(), WI::value());
70  //LocalVType t = Sin<N,1,LocalVType>::value();
71 // wp[0] = Complex<LocalVType>(1 - 2.0*t*t, -S*Sin<N,2,LocalVType>::value());
72 
73  // W^i = (wpr2, wpi2)
74  for (int_t i=0; i<K-2; ++i)
75  wp[i+1] = wp[i]*wp[0];
76 
77  for (int_t i=0; i<K-1; ++i)
78  w[i] = wp[i];
79 
80  for (int_t i=1; i<M; i++) {
81  spec_inp.apply(data+i, w);
82 
83  for (int_t i=0; i<K-1; ++i)
84  w[i] = w[i]*wp[i];
85  }
86  }
87 
88 };
89 
90 template<int_t M, typename T, int S, class W,
91 template<typename> class Complex>
92 class DFTk_x_Im_T<3,M,Complex<T>,S,W,false> {
93  //typedef typename TempTypeTrait<T>::Result LocalVType;
94  typedef Compute<typename W::Re,2> WR;
95  typedef Compute<typename W::Im,2> WI;
96  static const int_t N = 3*M;
97  //static const int_t M2 = M*2;
98  DFTk_inp<3,M,Complex<T>,S> spec_inp;
99 public:
100  void apply(Complex<T>* data)
101  {
102  spec_inp.apply(data);
103 
104  Complex<T> w[2];
105 
106  // W = (wpr1, wpi1)
107 // LocalVType t = Sin<N,1,LocalVType>::value();
108 // const LocalVType wpr1 = 1 - 2.0*t*t;
109 // const LocalVType wpi1 = -S*Sin<N,2,LocalVType>::value();
110  Complex<T> wp1(WR::value(), WI::value());
111 
112  // W^2 = (wpr2, wpi2)
113  Complex<T> wp2(wp1*wp1);
114 
115  w[0] = wp1;
116  w[1] = wp2;
117  for (int_t i=1; i<M; i++) {
118  spec_inp.apply(data+i, w);
119 
120  w[0] = w[0]*wp1;
121  w[1] = w[1]*wp2;
122  }
123  }
124 };
125 
126 template<int_t M, typename T, int S, class W,
127 template<typename> class Complex>
128 class DFTk_x_Im_T<2,M,Complex<T>,S,W,false> {
129  typedef typename TempTypeTrait<T>::Result LocalVType;
130  typedef Compute<typename W::Re,2> WR;
131  typedef Compute<typename W::Im,2> WI;
132  DFTk_inp<2,M,Complex<T>,S> spec_inp;
133 public:
134  void apply(Complex<T>* data)
135  {
136  spec_inp.apply(data);
137 
138 // LocalVType t = Sin<N,1,LocalVType>::value();
139 // const LocalVType wpr = 1-2.0*t*t;
140 // const LocalVType wpi = -S*Sin<N,2,LocalVType>::value();
141  Complex<T> wp(WR::value(), WI::value());
142 
143  Complex<T> w(wp);
144  for (int_t i=1; i<M; i++) {
145  spec_inp.apply(data+i, &w);
146 
147  w = w*wp;
148  }
149  }
150 };
151 
152 
153 // General implementation in-place for Complex<T>
154 template<int_t N, typename Head, typename T, int S, class W1, int_t LastK,
155 template<typename> class Complex>
156 class InTime<N, Loki::Typelist<Head,Loki::NullType>, Complex<T>, S, W1, LastK>
157 {
158  typedef typename TempTypeTrait<T>::Result LocalVType;
159  static const int_t K = Head::first::value;
160  static const int_t M = N/K;
161 
162  typedef typename IPowBig<W1,K>::Result WK;
163  typedef Loki::Typelist<Pair<typename Head::first, SInt<Head::second::value-1> >, Loki::NullType> NFactNext;
164  InTime<M,NFactNext,Complex<T>,S,WK,K*LastK> dft_str;
165 // DFTk_x_Im_T<K,M,Complex<T>,S,W1,(N<=StaticLoopLimit)> dft_scaled;
166  DFTk_x_Im_T<K,M,Complex<T>,S,W1,false> dft_scaled;
167 public:
168  void apply(Complex<T>* data)
169  {
170  for (int_t m=0; m < N; m+=M)
171  dft_str.apply(data + m);
172 
173  dft_scaled.apply(data);
174  }
175 };
176 
177 // Take the next factor from the list
178 template<int_t N, int_t K, typename Tail, typename T, int S, class W1, int_t LastK,
179 template<typename> class Complex>
180 class InTime<N, Loki::Typelist<Pair<SInt<K>, SInt<0> >,Tail>, Complex<T>, S, W1, LastK>
181 : public InTime<N, Tail, Complex<T>, S, W1, LastK> {};
182 
183 
184 // Specialization for prime N
185 template<int_t N, typename T, int S, class W1, int_t LastK,
186 template<typename> class Complex>
187 class InTime<N,Loki::Typelist<Pair<SInt<N>, SInt<1> >, Loki::NullType>,Complex<T>,S,W1,LastK> {
188  DFTk_inp<N, 1, Complex<T>, S> spec_inp;
189 public:
190  void apply(Complex<T>* data)
191  {
192  spec_inp.apply(data);
193  }
194 };
195 
196 
197 
198 // General implementation out-of-place for Complex<T>
199 template<int_t N, typename Head, typename Tail, typename T, int S, class W1, int_t LastK,
200 template<typename> class Complex>
201 class InTimeOOP<N, Loki::Typelist<Head,Tail>, Complex<T>, S, W1, LastK>
202 {
203  typedef typename TempTypeTrait<T>::Result LocalVType;
204  static const int_t K = Head::first::value;
205  static const int_t M = N/K;
206 
207  typedef typename IPowBig<W1,K>::Result WK;
208  typedef Loki::Typelist<Pair<typename Head::first, SInt<Head::second::value-1> >, Tail> NFactNext;
209  InTimeOOP<M,NFactNext,Complex<T>,S,WK,K*LastK> dft_str;
210 // DFTk_x_Im_T<K,M,Complex<T>,S,W1,(N<=StaticLoopLimit)> dft_scaled;
211  DFTk_x_Im_T<K,M,Complex<T>,S,W1,false> dft_scaled;
212 public:
213 
214  void apply(const Complex<T>* src, Complex<T>* dst)
215  {
216  int_t lk = 0;
217  for (int_t m = 0; m < N; m+=M, lk+=LastK)
218  dft_str.apply(src + lk, dst + m);
219 
220  dft_scaled.apply(dst);
221  }
222 };
223 
224 // Take the next factor from the list
225 template<int_t N, int_t K, typename Tail, typename T, int S, class W1, int_t LastK,
226 template<typename> class Complex>
227 class InTimeOOP<N, Loki::Typelist<Pair<SInt<K>, SInt<0> >,Tail>, Complex<T>, S, W1, LastK>
228 : public InTimeOOP<N, Tail, Complex<T>, S, W1, LastK> {};
229 
230 
231 // Specialization for prime N
232 template<int_t N, typename T, int S, class W1, int_t LastK,
233 template<typename> class Complex>
234 class InTimeOOP<N,Loki::Typelist<Pair<SInt<N>, SInt<1> >, Loki::NullType>,Complex<T>,S,W1,LastK>
235 : public DFTk<N, LastK, 1, Complex<T>, S> {};
236 
237 
238 } //namespace DFT
239 
240 #endif /*__gfftstdalg_h*/
Generated on Mon Feb 10 2014 for Generative Fast Fourier Transforms (GFFT) by DoxyGen 1.8.3.1