1 /*
2 * Copyright (c) 2003, 2007-14 Matteo Frigo
3 * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 */
20
21 /* express a twiddle problem in terms of dft + multiplication by
22 twiddle factors */
23
24 #include "dft/ct.h"
25
26 typedef ct_solver S;
27
28 typedef struct {
29 plan_dftw super;
30
31 INT r, rs, m, mb, me, ms, v, vs;
32
33 plan *cld;
34
35 twid *td;
36
37 const S *slv;
38 int dec;
39 } P;
40
mktwiddle(P * ego,enum wakefulness wakefulness)41 static void mktwiddle(P *ego, enum wakefulness wakefulness)
42 {
43 static const tw_instr tw[] = { { TW_FULL, 0, 0 }, { TW_NEXT, 1, 0 } };
44
45 /* note that R and M are swapped, to allow for sequential
46 access both to data and twiddles */
47 X(twiddle_awake)(wakefulness, &ego->td, tw,
48 ego->r * ego->m, ego->m, ego->r);
49 }
50
bytwiddle(const P * ego,R * rio,R * iio)51 static void bytwiddle(const P *ego, R *rio, R *iio)
52 {
53 INT iv, ir, im;
54 INT r = ego->r, rs = ego->rs;
55 INT m = ego->m, mb = ego->mb, me = ego->me, ms = ego->ms;
56 INT v = ego->v, vs = ego->vs;
57 const R *W = ego->td->W;
58
59 mb += (mb == 0); /* skip m=0 iteration */
60 for (iv = 0; iv < v; ++iv) {
61 for (ir = 1; ir < r; ++ir) {
62 for (im = mb; im < me; ++im) {
63 R *pr = rio + ms * im + rs * ir;
64 R *pi = iio + ms * im + rs * ir;
65 E xr = *pr;
66 E xi = *pi;
67 E wr = W[2 * im + (2 * (m-1)) * ir - 2];
68 E wi = W[2 * im + (2 * (m-1)) * ir - 1];
69 *pr = xr * wr + xi * wi;
70 *pi = xi * wr - xr * wi;
71 }
72 }
73 rio += vs;
74 iio += vs;
75 }
76 }
77
applicable(INT irs,INT ors,INT ivs,INT ovs,const planner * plnr)78 static int applicable(INT irs, INT ors, INT ivs, INT ovs,
79 const planner *plnr)
80 {
81 return (1
82 && irs == ors
83 && ivs == ovs
84 && !NO_SLOWP(plnr)
85 );
86 }
87
apply_dit(const plan * ego_,R * rio,R * iio)88 static void apply_dit(const plan *ego_, R *rio, R *iio)
89 {
90 const P *ego = (const P *) ego_;
91 plan_dft *cld;
92 INT dm = ego->ms * ego->mb;
93
94 bytwiddle(ego, rio, iio);
95
96 cld = (plan_dft *) ego->cld;
97 cld->apply(ego->cld, rio + dm, iio + dm, rio + dm, iio + dm);
98 }
99
apply_dif(const plan * ego_,R * rio,R * iio)100 static void apply_dif(const plan *ego_, R *rio, R *iio)
101 {
102 const P *ego = (const P *) ego_;
103 plan_dft *cld;
104 INT dm = ego->ms * ego->mb;
105
106 cld = (plan_dft *) ego->cld;
107 cld->apply(ego->cld, rio + dm, iio + dm, rio + dm, iio + dm);
108
109 bytwiddle(ego, rio, iio);
110 }
111
awake(plan * ego_,enum wakefulness wakefulness)112 static void awake(plan *ego_, enum wakefulness wakefulness)
113 {
114 P *ego = (P *) ego_;
115 X(plan_awake)(ego->cld, wakefulness);
116 mktwiddle(ego, wakefulness);
117 }
118
destroy(plan * ego_)119 static void destroy(plan *ego_)
120 {
121 P *ego = (P *) ego_;
122 X(plan_destroy_internal)(ego->cld);
123 }
124
print(const plan * ego_,printer * p)125 static void print(const plan *ego_, printer *p)
126 {
127 const P *ego = (const P *) ego_;
128 p->print(p, "(dftw-generic-%s-%D-%D%v%(%p%))",
129 ego->dec == DECDIT ? "dit" : "dif",
130 ego->r, ego->m, ego->v, ego->cld);
131 }
132
mkcldw(const ct_solver * ego_,INT r,INT irs,INT ors,INT m,INT ms,INT v,INT ivs,INT ovs,INT mstart,INT mcount,R * rio,R * iio,planner * plnr)133 static plan *mkcldw(const ct_solver *ego_,
134 INT r, INT irs, INT ors,
135 INT m, INT ms,
136 INT v, INT ivs, INT ovs,
137 INT mstart, INT mcount,
138 R *rio, R *iio,
139 planner *plnr)
140 {
141 const S *ego = (const S *)ego_;
142 P *pln;
143 plan *cld = 0;
144 INT dm = ms * mstart;
145
146 static const plan_adt padt = {
147 0, awake, print, destroy
148 };
149
150 A(mstart >= 0 && mstart + mcount <= m);
151 if (!applicable(irs, ors, ivs, ovs, plnr))
152 return (plan *)0;
153
154 cld = X(mkplan_d)(plnr,
155 X(mkproblem_dft_d)(
156 X(mktensor_1d)(r, irs, irs),
157 X(mktensor_2d)(mcount, ms, ms, v, ivs, ivs),
158 rio + dm, iio + dm, rio + dm, iio + dm)
159 );
160 if (!cld) goto nada;
161
162 pln = MKPLAN_DFTW(P, &padt, ego->dec == DECDIT ? apply_dit : apply_dif);
163 pln->slv = ego;
164 pln->cld = cld;
165 pln->r = r;
166 pln->rs = irs;
167 pln->m = m;
168 pln->ms = ms;
169 pln->v = v;
170 pln->vs = ivs;
171 pln->mb = mstart;
172 pln->me = mstart + mcount;
173 pln->dec = ego->dec;
174 pln->td = 0;
175
176 {
177 double n0 = (r - 1) * (mcount - 1) * v;
178 pln->super.super.ops = cld->ops;
179 pln->super.super.ops.mul += 8 * n0;
180 pln->super.super.ops.add += 4 * n0;
181 pln->super.super.ops.other += 8 * n0;
182 }
183 return &(pln->super.super);
184
185 nada:
186 X(plan_destroy_internal)(cld);
187 return (plan *) 0;
188 }
189
regsolver(planner * plnr,INT r,int dec)190 static void regsolver(planner *plnr, INT r, int dec)
191 {
192 S *slv = (S *)X(mksolver_ct)(sizeof(S), r, dec, mkcldw, 0);
193 REGISTER_SOLVER(plnr, &(slv->super));
194 if (X(mksolver_ct_hook)) {
195 slv = (S *)X(mksolver_ct_hook)(sizeof(S), r, dec, mkcldw, 0);
196 REGISTER_SOLVER(plnr, &(slv->super));
197 }
198 }
199
X(ct_generic_register)200 void X(ct_generic_register)(planner *p)
201 {
202 regsolver(p, 0, DECDIT);
203 regsolver(p, 0, DECDIF);
204 }
205