← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/fftw/dft/dftw-generic.c

  • Committer: Bazaar Package Importer
  • Author(s): Kevin Roy
  • Date: 2011-02-08 22:20:54 UTC
  • mfrom: (1.4.2 upstream)
  • mto: (14.2.6 sid) (1.5.1)
  • mto: This revision was merged to the branch mainline in revision 27.
  • Revision ID: james.westby@ubuntu.com-20110208222054-kk0gwa4bu8h5lyq4
Tags: upstream-2.56.1-beta-svn34076
Import upstream version 2.56.1-beta-svn34076

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/fftw/dft/dftw-generic.c
1
 
/*
2
 
 * Copyright (c) 2003, 2006 Matteo Frigo
3
 
 * Copyright (c) 2003, 2006 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
 
 *
19
 
 */
20
 
 
21
 
/* express a twiddle problem in terms of dft + multiplication by
22
 
   twiddle factors */
23
 
 
24
 
#include "ct.h"
25
 
 
26
 
typedef ct_solver S;
27
 
 
28
 
typedef struct {
29
 
     plan_dftw super;
30
 
 
31
 
     INT r, m, s, vl, vs, mstart, mcount;
32
 
     plan *cld;
33
 
 
34
 
     /* defined only for solver1: */
35
 
     twid *td;
36
 
 
37
 
     const S *slv;
38
 
     int dec;
39
 
} P;
40
 
 
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
 
 
51
 
static void bytwiddle(const P *ego, R *rio, R *iio)
52
 
{
53
 
     INT i, j, k;
54
 
     INT r = ego->r, m = ego->m, s = ego->s, vl = ego->vl, vs = ego->vs;
55
 
     INT mcount = ego->mcount, mstart = ego->mstart;
56
 
     INT jstart = mstart == 0;
57
 
     INT jrem_W = 2 * ((m - 1) - (mcount - jstart));
58
 
     INT jrem_p = s * (m - mcount);
59
 
     INT ip = iio - rio;
60
 
     R *p;
61
 
 
62
 
     for (i = 0; i < vl; ++i) {
63
 
          const R *W = ego->td->W + 2 * (mstart - 1 + jstart);
64
 
 
65
 
          /* loop invariant: p = rio + s * (k * m + j) + i * vs. */
66
 
          p = rio + i * vs;
67
 
 
68
 
          for (k = 1, p += s * m, W += 2 * (m - 1); k < r; ++k) {
69
 
               for (j = jstart, p += jstart*s; j < mcount; ++j, p += s) {
70
 
                    E xr = p[0];
71
 
                    E xi = p[ip];
72
 
                    E wr = W[0];
73
 
                    E wi = W[1];
74
 
                    p[0] = xr * wr + xi * wi;
75
 
                    p[ip] = xi * wr - xr * wi;
76
 
                    W += 2;
77
 
               }
78
 
               W += jrem_W;
79
 
               p += jrem_p;
80
 
          }
81
 
     }
82
 
}
83
 
 
84
 
static int applicable(INT r, INT m, const planner *plnr)
85
 
{
86
 
     UNUSED(r); UNUSED(m);
87
 
     return (1 
88
 
             && !NO_SLOWP(plnr)
89
 
          );
90
 
}
91
 
 
92
 
static void apply_dit(const plan *ego_, R *rio, R *iio)
93
 
{
94
 
     const P *ego = (const P *) ego_;
95
 
     plan_dft *cld;
96
 
 
97
 
     bytwiddle(ego, rio, iio);
98
 
 
99
 
     cld = (plan_dft *) ego->cld;
100
 
     cld->apply(ego->cld, rio, iio, rio, iio);
101
 
}
102
 
 
103
 
static void apply_dif(const plan *ego_, R *rio, R *iio)
104
 
{
105
 
     const P *ego = (const P *) ego_;
106
 
     plan_dft *cld;
107
 
 
108
 
     cld = (plan_dft *) ego->cld;
109
 
     cld->apply(ego->cld, rio, iio, rio, iio);
110
 
 
111
 
     bytwiddle(ego, rio, iio);
112
 
}
113
 
 
114
 
static void awake(plan *ego_, enum wakefulness wakefulness)
115
 
{
116
 
     P *ego = (P *) ego_;
117
 
     X(plan_awake)(ego->cld, wakefulness);
118
 
     mktwiddle(ego, wakefulness);
119
 
}
120
 
 
121
 
static void destroy(plan *ego_)
122
 
{
123
 
     P *ego = (P *) ego_;
124
 
     X(plan_destroy_internal)(ego->cld);
125
 
}
126
 
 
127
 
static void print(const plan *ego_, printer *p)
128
 
{
129
 
     const P *ego = (const P *) ego_;
130
 
     p->print(p, "(dftw-generic-%s-%D-%D%v%(%p%))", 
131
 
              ego->dec == DECDIT ? "dit" : "dif",
132
 
              ego->r, ego->m, ego->vl, ego->cld);
133
 
}
134
 
 
135
 
static plan *mkcldw(const ct_solver *ego_, 
136
 
                    int dec, INT r, INT m, INT s, INT vl, INT vs, 
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
 
 
145
 
     static const plan_adt padt = {
146
 
          0, awake, print, destroy
147
 
     };
148
 
 
149
 
     A(mstart >= 0 && mstart + mcount <= m);
150
 
     if (!applicable(r, m, plnr))
151
 
          return (plan *)0;
152
 
 
153
 
     cld = X(mkplan_d)(plnr, 
154
 
                        X(mkproblem_dft_d)(
155
 
                             X(mktensor_1d)(r, m * s, m * s),
156
 
                             X(mktensor_2d)(mcount, s, s, vl, vs, vs),
157
 
                             rio, iio, rio, iio)
158
 
                        );
159
 
     if (!cld) goto nada;
160
 
 
161
 
     pln = MKPLAN_DFTW(P, &padt, dec == DECDIT ? apply_dit : apply_dif);
162
 
     pln->slv = ego;
163
 
     pln->cld = cld;
164
 
     pln->r = r;
165
 
     pln->m = m;
166
 
     pln->s = s;
167
 
     pln->vl = vl;
168
 
     pln->vs = vs;
169
 
     pln->mstart = mstart;
170
 
     pln->mcount = mcount;
171
 
     pln->dec = dec;
172
 
     pln->td = 0;
173
 
 
174
 
     {
175
 
          double n0 = (r - 1) * (mcount - 1) * vl;
176
 
          pln->super.super.ops = cld->ops;
177
 
          pln->super.super.ops.mul += 8 * n0;
178
 
          pln->super.super.ops.add += 4 * n0;
179
 
          pln->super.super.ops.other += 8 * n0;
180
 
     }
181
 
     return &(pln->super.super);
182
 
 
183
 
 nada:
184
 
     X(plan_destroy_internal)(cld);
185
 
     return (plan *) 0;
186
 
}
187
 
 
188
 
static void regsolver(planner *plnr, INT r, int dec)
189
 
{
190
 
     S *slv = (S *)X(mksolver_ct)(sizeof(S), r, dec, mkcldw);
191
 
     REGISTER_SOLVER(plnr, &(slv->super));
192
 
     if (X(mksolver_ct_hook)) {
193
 
          slv = (S *)X(mksolver_ct_hook)(sizeof(S), r, dec, mkcldw);
194
 
          REGISTER_SOLVER(plnr, &(slv->super));
195
 
     }
196
 
}
197
 
 
198
 
void X(ct_generic_register)(planner *p)
199
 
{
200
 
     regsolver(p, 0, DECDIT);
201
 
     regsolver(p, 0, DECDIF);
202
 
}