lib/PDL/FFT/fftn.c

filter: Statementstmt 63.5% 1207 / 1898 Branchbran 34.3% 240 / 698 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 55.7% 1447 / 2596 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« lib/PDL/IO/Pnm/get.c ↑ Summary lib/PDL/FFT.xs »
1 /*--------------------------------*-C-*---------------------------------*
2 * File:
3 * fftn.c
4 *
5 * multivariate complex Fourier transform, computed in place
6 * using mixed-radix Fast Fourier Transform algorithm.
7 *
8 * Fortran code by:
9 * RC Singleton, Stanford Research Institute, Sept. 1968
10 * NIST Guide to Available Math Software.
11 * Source for module FFT from package GO.
12 * Retrieved from NETLIB on Wed Jul 5 11:50:07 1995.
13 * translated by f2c (version 19950721) and with lots of cleanup
14 * to make it resemble C by:
15 * MJ Olesen, Queen's University at Kingston, 1995-97
16 */
17 /*{{{ Copyright: */
18 /*
19 * Copyright(c)1995,97 Mark Olesen <olesen@me.QueensU.CA>
20 * Queen's Univ at Kingston (Canada)
21 *
22 * Permission to use, copy, modify, and distribute this software for
23 * any purpose without fee is hereby granted, provided that this
24 * entire notice is included in all copies of any software which is
25 * or includes a copy or modification of this software and in all
26 * copies of the supporting documentation for such software.
27 *
28 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR
29 * IMPLIED WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR QUEEN'S
30 * UNIVERSITY AT KINGSTON MAKES ANY REPRESENTATION OR WARRANTY OF ANY
31 * KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS
32 * FITNESS FOR ANY PARTICULAR PURPOSE.
33 *
34 * All of which is to say that you can do what you like with this
35 * source code provided you don't try to sell it as your own and you
36 * include an unaltered copy of this message (including the
37 * copyright).
38 *
39 * It is also implicitly understood that bug fixes and improvements
40 * should make their way back to the general Internet community so
41 * that everyone benefits.
42 *----------------------------------------------------------------------*/
43 /*}}}*/
44 /*{{{ notes: */
45 /*
46 * Public:
47 * fftn / fftnf / fftnl
48 * (these are documented in the header file)
49 *
50 * Private:
51 * fftradix / fftradixf
52 *
53 * ----------------------------------------------------------------------*
54 * int fftradix (REAL Re[], REAL Im[], size_t nTotal, size_t nPass,
55 * size_t nSpan, int iSign, size_t maxFactors,
56 * size_t maxPerm);
57 *
58 * RE and IM hold the real and imaginary components of the data, and
59 * return the resulting real and imaginary Fourier coefficients.
60 * Multidimensional data *must* be allocated contiguously. There is
61 * no limit on the number of dimensions.
62 *
63 *
64 * Although there is no limit on the number of dimensions, fftradix()
65 * must be called once for each dimension, but the calls may be in
66 * any order.
67 *
68 * NTOTAL = the total number of complex data values
69 * NPASS = the dimension of the current variable
70 * NSPAN/NPASS = the spacing of consecutive data values while indexing
71 * the current variable
72 * ISIGN - see above documentation
73 *
74 * example:
75 * tri-variate transform with Re[n1][n2][n3], Im[n1][n2][n3]
76 *
77 * fftradix (Re, Im, n1*n2*n3, n1, n1, 1, maxf, maxp);
78 * fftradix (Re, Im, n1*n2*n3, n2, n1*n2, 1, maxf, maxp);
79 * fftradix (Re, Im, n1*n2*n3, n3, n1*n2*n3, 1, maxf, maxp);
80 *
81 * single-variate transform,
82 * NTOTAL = N = NSPAN = (number of complex data values),
83 *
84 * fftradix (Re, Im, n, n, n, 1, maxf, maxp);
85 *
86 * The data can also be stored in a single array with alternating
87 * real and imaginary parts, the magnitude of ISIGN is changed to 2
88 * to give correct indexing increment, and data [0] and data [1] used
89 * to pass the initial addresses for the sequences of real and
90 * imaginary values,
91 *
92 * example:
93 * REAL data [2*NTOTAL];
94 * fftradix (&data[0], &data[1], NTOTAL, nPass, nSpan, 2, maxf, maxp);
95 *
96 * for temporary allocation:
97 *
98 * MAXFACTORS >= the maximum prime factor of NPASS
99 * MAXPERM >= the number of prime factors of NPASS. In addition,
100 * if the square-free portion K of NPASS has two or more prime
101 * factors, then MAXPERM >= (K-1)
102 *
103 * storage in FACTOR for a maximum of 15 prime factors of NPASS. if
104 * NPASS has more than one square-free factor, the product of the
105 * square-free factors must be <= 210 array storage for maximum prime
106 * factor of 23 the following two constants should agree with the
107 * array dimensions.
108 * ----------------------------------------------------------------------*/
109 /*}}}*/
110 /*{{{ Revisions: */
111 /*
112 * 26 July 95 John Beale
113 * - added maxf and maxp as parameters to fftradix()
114 *
115 * 28 July 95 Mark Olesen <olesen@me.QueensU.CA>
116 * - cleaned-up the Fortran 66 goto spaghetti, only 3 labels remain.
117 *
118 * - added fft_free() to provide some measure of control over
119 * allocation/deallocation.
120 *
121 * - added fftn() wrapper for multidimensional FFTs
122 *
123 * - use -DFFT_NOFLOAT or -DFFT_NODOUBLE to avoid compiling that
124 * precision. Note suffix `f' on the function names indicates
125 * float precision.
126 *
127 * - revised documentation
128 *
129 * 31 July 95 Mark Olesen <olesen@me.QueensU.CA>
130 * - added GNU Public License
131 * - more cleanup
132 * - define SUN_BROKEN_REALLOC to use malloc() instead of realloc()
133 * on the first pass through, apparently needed for old libc
134 * - removed #error directive in favour of some code that simply
135 * won't compile (generate an error that way)
136 *
137 * 1 Aug 95 Mark Olesen <olesen@me.QueensU.CA>
138 * - define FFT_RADIX4 to only have radix 2, radix 4 transforms
139 * - made fftradix /fftradixf () static scope, just use fftn()
140 * instead. If you have good ideas about fixing the factors
141 * in fftn() please do so.
142 *
143 * 8 Jan 95 mj olesen <olesen@me.QueensU.CA>
144 * - fixed typo's, including one that broke scaling for scaling by
145 * total number of matrix elements or the square root of same
146 * - removed unnecessary casts from allocations
147 *
148 * 10 Dec 96 mj olesen <olesen@me.QueensU.CA>
149 * - changes defines to compile *without* float support by default,
150 * use -DFFT_FLOAT to enable.
151 * - shifted some variables to local scope (better hints for optimizer)
152 * - added Michael Steffens <Michael.Steffens@mbox.muk.uni-hannover.de>
153 * Fortran 90 module
154 * - made it simpler to pass dimensions for 1D FFT.
155 *
156 * 23 Feb 97 Mark Olesen <olesen@me.QueensU.CA>
157 * - removed the GNU Public License (see 21 July 1995 entry),
158 * which should make it clear why I have the right to do so.
159 * - Added copyright notice and submitted to netlib
160 * - Moved documentation for the public functions to the header
161 * files where is will always be available.
162 *
163 * 11 Nov 97 Robin Williams <rjrw@ast.leeds.ac.uk>
164 * - fixed all temporaries to double precision using REALFIX,
165 * following suggestion from Scott Wurcer
166 * ----------------------------------------------------------------------*/
167 /*}}}*/
168 #ifndef _FFTN_C
169 #define _FFTN_C
170 /* we use CPP to re-include this same file for double/float cases */
171  
172 #include <stdio.h>
173 #include <stdlib.h>
174 #include <math.h>
175 #include "fftn.h"
176  
177 /*{{{ defines/constants */
178 #ifndef M_PI
179 # define M_PI 3.14159265358979323846264338327950288
180 #endif
181  
182 #define FFT_STR(x) #x
183 #define FFT_CONCAT(x, y) FFT_CONCAT_(x, y)
184 #define FFT_CONCAT_(x, y) x ## y /* second call forces arg expansion */
185  
186 #ifndef SIN60
187 # define SIN60 0.86602540378443865 /* sin(60 deg) */
188 # define COS72 0.30901699437494742 /* cos(72 deg) */
189 # define SIN72 0.95105651629515357 /* sin(72 deg) */
190 #endif
191 /*}}}*/
192  
193 #define NFACTOR 11
194 #define REALFIX long double
195  
196 /*
197 * use macros to access the Real/Imaginary parts so that it's possible
198 * to substitute different macros if a complex struct is used
199 */
200 #define Re_Data(i) Re[i]
201 #define Im_Data(i) Im[i]
202  
203 /* return the number of factors */
204 static int
205 10964 factorize (int nPass, int * kt, int *factor)
206 {
207 10964 int nFactor = 0;
208 int j, jj;
209  
210 10964 *kt = 0;
211 /* determine the factors of n */
212 20948 ▶ while ((nPass % 16) == 0) /* factors of 4 */
Branch: 1 branch
BranchTrueFalseTotal
while ((nPass % 16) == 0) /* factors of 4 */ 9984 10964 20948
213 {
214 9984 factor [nFactor++] = 4;
215 9984 nPass /= 16;
216 }
217 10964 j = 3; jj = 9; /* factors of 3, 5, 7, ... */
218 do {
219 11242 ▶ while ((nPass % jj) == 0)
Branch: 1 branch
BranchTrueFalseTotal
while ((nPass % jj) == 0) 0 11242 11242
220 {
221 0 factor [nFactor++] = j;
222 0 nPass /= jj;
223 }
224 11242 j += 2;
225 11242 jj = j * j;
226 11242 ▶ } while (jj <= nPass);
Branch: 1 branch
BranchTrueFalseTotal
} while (jj <= nPass); 278 10964 11242
227 10964 ▶ if (nPass <= 4)
Branch: 1 branch
BranchTrueFalseTotal
if (nPass <= 4) 8 10956 10964
228 {
229 8 *kt = nFactor;
230 8 factor [nFactor] = nPass;
231 8 ▶ if (nPass != 1)
Branch: 1 branch
BranchTrueFalseTotal
if (nPass != 1) 8 0 8
232 8 nFactor++;
233 }
234 else
235 {
236 10956 ▶ if (nPass - (nPass / 4 << 2) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (nPass - (nPass / 4 << 2) == 0) 10128 828 10956
237 {
238 10128 factor [nFactor++] = 2;
239 10128 nPass /= 4;
240 }
241 10956 *kt = nFactor;
242 10956 j = 2;
243 do {
244 23364 ▶ if ((nPass % j) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if ((nPass % j) == 0) 21768 1596 23364
245 {
246 21768 factor [nFactor++] = j;
247 21768 nPass /= j;
248 }
249 23364 j = ((j + 1) / 2 << 1) + 1;
250 23364 ▶ } while (j <= nPass);
Branch: 1 branch
BranchTrueFalseTotal
} while (j <= nPass); 12408 10956 23364
251 }
252 10964 ▶ if (*kt)
Branch: 1 branch
BranchTrueFalseTotal
if (*kt) 10128 836 10964
253 {
254 10128 j = *kt;
255 do
256 20112 factor [nFactor++] = factor [--j];
257 20112 ▶ while (j);
Branch: 1 branch
BranchTrueFalseTotal
while (j); 9984 10128 20112
258 }
259  
260 10964 return nFactor;
261 }
262  
263 /*{{{ defines for re-including long double precision */
264 #ifdef FFT_LDOUBLE
265 # undef REAL
266 # undef FFT_SUFFIX
267 # define FFT_SUFFIX l
268 # define REAL long double
269 # include "fftn.c" /* include this file again */
270 #endif
271 /*}}}*/
272  
273 /*{{{ defines for re-including double precision */
274 #ifdef FFT_DOUBLE
275 # undef REAL
276 # undef FFT_SUFFIX
277 # define FFT_SUFFIX
278 # define REAL double
279 # include "fftn.c" /* include this file again */
280 #endif
281 /*}}}*/
282  
283 /*{{{ defines for re-including float precision */
284 #ifdef FFT_FLOAT
285 # undef REAL
286 # undef FFT_SUFFIX
287 # define FFT_SUFFIX f
288 # define REAL float
289 # include "fftn.c" /* include this file again */
290 #endif
291 /*}}}*/
292 #else /* _FFTN_C */
293  
294 # undef FFTN
295 # undef FFTNS
296 # undef FFTRADIX
297 # undef FFTRADIXS
298 # define FFTN FFT_CONCAT(fftn, FFT_SUFFIX) /* maybe trailing [fl] */
299 # define FFTNS FFT_STR(FFTN) /* name for error message */
300 # define FFTRADIX FFT_CONCAT(fftradix, FFT_SUFFIX) /* maybe trailing [fl] */
301 # define FFTRADIXS FFT_STR(FFTRADIX) /* name for error message */
302  
303 /*----------------------------------------------------------------------*/
304 /*
305 * singleton's mixed radix routine
306 */
307 static int
308 0 FFTRADIX (REAL Re [],
309 REAL Im [],
310 size_t nTotal,
311 size_t nPass,
312 size_t nSpan,
313 int iSign,
314 int maxFactors,
315 int maxPerm)
316 {
317 #ifndef FFTRADIX_RETURN
318 #define FFTRADIX_RETURN(v) \
319 do { \
320 if (Rtmp) free(Rtmp); \
321 if (Itmp) free(Itmp); \
322 if (Cos) free(Cos); \
323 if (Sin) free(Sin); \
324 if (Perm) free(Perm); \
325 return v; \
326 } while (0)
327 #endif
328 #ifndef FFTRADIX_MALLOC
329 #define FFTRADIX_MALLOC(t, p, n) \
330 do { p = malloc(sizeof(t) * n); if (!p) FFTRADIX_RETURN(-1); } while (0)
331 #endif
332 0 ▶ if (nPass < 2)
Branch: 3 branches
BranchTrueFalseTotal
if (nPass < 2) 0 2308 2308
if (nPass < 2) 0 8656 8656
if (nPass < 2) 0 0 0
333 0 return 0;
334  
335 int ii, nFactor, factor[NFACTOR], kspan, ispan, inc;
336 int j, jc, jf, jj, k, k1, k3, kk, kt, nn, ns, nt;
337  
338 REALFIX radf;
339 REALFIX c1, c2, c3, cd;
340 REALFIX s1, s2, s3, sd;
341  
342 0 REALFIX *Rtmp=NULL, *Itmp=NULL, *Cos=NULL, *Sin=NULL;
343 0 int *Perm=NULL;
344 0 ▶ FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */
Branch: 18 branches
BranchTrueFalseTotal
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 2308 2308
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 8656 8656
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Rtmp, maxFactors); /* temp space for real part */ 0 0 0
345 0 ▶ FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */
Branch: 18 branches
BranchTrueFalseTotal
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 2308 2308
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 8656 8656
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Itmp, maxFactors); /* temp space for imag part */ 0 0 0
346 0 ▶ FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */
Branch: 18 branches
BranchTrueFalseTotal
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 2308 2308
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 8656 8656
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Cos, maxFactors); /* Cosine values */ 0 0 0
347 0 ▶ FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */
Branch: 18 branches
BranchTrueFalseTotal
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 2308 2308
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 8656 8656
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
FFTRADIX_MALLOC(REALFIX, Sin, maxFactors); /* Sine values */ 0 0 0
348 0 ▶ FFTRADIX_MALLOC(int, Perm, maxPerm);
Branch: 18 branches
BranchTrueFalseTotal
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 2308 2308
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 8656 8656
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
FFTRADIX_MALLOC(int, Perm, maxPerm); 0 0 0
349  
350 #ifndef FFT_RADIX4
351 0 REALFIX s60 = SIN60; /* sin(60 deg) */
352 0 REALFIX s72 = SIN72; /* sin(72 deg) */
353 0 REALFIX c72 = COS72; /* cos(72 deg) */
354 #endif
355 0 REALFIX pi2 = M_PI; /* use PI first, 2 PI later */
356  
357 /* gcc complains about k3 being uninitialized, but I can't find out where
358 * or why ... it looks okay to me.
359 *
360 * initialize to make gcc happy
361 */
362 0 k3 = 0;
363  
364 /* gcc complains about c2, c3, s2,s3 being uninitialized, but they're
365 * only used for the radix 4 case and only AFTER the (s1 == 0.0) pass
366 * through the loop at which point they will have been calculated.
367 *
368 * initialize to make gcc happy
369 */
370 0 c2 = c3 = s2 = s3 = 0.0;
371  
372 /* Parameter adjustments, was fortran so fix zero-offset */
373 0 Re--;
374 0 Im--;
375  
376 /*
377 * Function Body
378 */
379 0 inc = iSign;
380 0 ▶ if (iSign < 0)
Branch: 3 branches
BranchTrueFalseTotal
if (iSign < 0) 1154 1154 2308
if (iSign < 0) 5430 3226 8656
if (iSign < 0) 0 0 0
381 {
382 #ifndef FFT_RADIX4
383 0 s60 = -s60;
384 0 s72 = -s72;
385 #endif
386 0 pi2 = -pi2;
387 0 inc = -inc; /* absolute value */
388 }
389  
390 /* adjust for strange increments */
391 0 nt = inc * nTotal;
392 0 ns = inc * nSpan;
393 0 kspan = ns;
394  
395 0 nn = nt - inc;
396 0 jc = ns / nPass;
397 0 radf = pi2 * (double) jc;
398 0 pi2 *= 2.0; /* use 2 PI from here on */
399  
400 0 ii = 0;
401 0 jf = 0;
402 /* determine the factors of n */
403  
404 0 nFactor = factorize (nPass, &kt, factor);
405 /* test that nFactors is in range */
406 0 ▶ if (nFactor > NFACTOR)
Branch: 3 branches
BranchTrueFalseTotal
if (nFactor > NFACTOR) 0 2308 2308
if (nFactor > NFACTOR) 0 8656 8656
if (nFactor > NFACTOR) 0 0 0
407 {
408 0 fprintf (stderr, "Error: " FFTRADIXS "() - exceeded number of factors\n");
409 0 goto Memory_Error;
410 }
411  
412 /* compute fourier transform */
413 for (;;) {
414 0 sd = radf / (double) kspan;
415 0 cd = sin (sd);
416 0 cd = 2.0 * cd * cd;
417 0 sd = sin (sd + sd);
418 0 kk = 1;
419 0 ii++;
420  
421 0 switch (factor [ii - 1]) {
422 0 case 2:
423 /* transform for factor of 2 (including rotation factor) */
424 0 kspan /= 2;
425 0 k1 = kspan + 2;
426 do {
427 do {
428 REALFIX tmpr;
429 REALFIX tmpi;
430 int k2;
431  
432 0 k2 = kk + kspan;
433 0 tmpr = Re_Data (k2);
434 0 tmpi = Im_Data (k2);
435 0 Re_Data (k2) = Re_Data (kk) - tmpr;
436 0 Im_Data (k2) = Im_Data (kk) - tmpi;
437 0 Re_Data (kk) += tmpr;
438 0 Im_Data (kk) += tmpi;
439 0 kk = k2 + kspan;
440 0 ▶ } while (kk <= nn);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= nn); 131328 6912 138240
} while (kk <= nn); 438336 24092 462428
} while (kk <= nn); 0 0 0
441 0 kk -= nn;
442 0 ▶ } while (kk <= jc);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= jc); 0 6912 6912
} while (kk <= jc); 0 24092 24092
} while (kk <= jc); 0 0 0
443 0 ▶ if (kk > kspan)
Branch: 3 branches
BranchTrueFalseTotal
if (kk > kspan) 0 6912 6912
if (kk > kspan) 144 23948 24092
if (kk > kspan) 0 0 0
444 0 goto Permute_Results; /* exit infinite loop */
445 do {
446 int k2;
447  
448 0 c1 = 1.0 - cd;
449 0 s1 = sd;
450 do {
451 REALFIX tmp;
452 do {
453 do {
454 REALFIX tmpr;
455 REALFIX tmpi;
456  
457 0 k2 = kk + kspan;
458 0 tmpr = Re_Data (kk) - Re_Data (k2);
459 0 tmpi = Im_Data (kk) - Im_Data (k2);
460 0 Re_Data (kk) += Re_Data (k2);
461 0 Im_Data (kk) += Im_Data (k2);
462 0 Re_Data (k2) = c1 * tmpr - s1 * tmpi;
463 0 Im_Data (k2) = s1 * tmpr + c1 * tmpi;
464 0 kk = k2 + kspan;
465 0 ▶ } while (kk < nt);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < nt); 1020672 168192 1188864
} while (kk < nt); 3402384 563696 3966080
} while (kk < nt); 0 0 0
466 0 k2 = kk - nt;
467 0 c1 = -c1;
468 0 kk = k1 - k2;
469 0 ▶ } while (kk > k2);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk > k2); 80640 87552 168192
} while (kk > k2); 270184 293512 563696
} while (kk > k2); 0 0 0
470 0 tmp = c1 - (cd * c1 + sd * s1);
471 0 s1 = sd * c1 - cd * s1 + s1;
472 0 c1 = 2.0 - (tmp * tmp + s1 * s1);
473 0 s1 *= c1;
474 0 c1 *= tmp;
475 0 kk += jc;
476 0 ▶ } while (kk < k2);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < k2); 80640 6912 87552
} while (kk < k2); 269564 23948 293512
} while (kk < k2); 0 0 0
477 0 k1 += (inc + inc);
478 0 kk = (k1 - kspan) / 2 + jc;
479 0 ▶ } while (kk <= jc + jc);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= jc + jc); 0 6912 6912
} while (kk <= jc + jc); 0 23948 23948
} while (kk <= jc + jc); 0 0 0
480 0 break;
481  
482 0 case 4: /* transform for factor of 4 */
483 0 ispan = kspan;
484 0 kspan /= 4;
485  
486 do {
487 0 c1 = 1.0;
488 0 s1 = 0.0;
489 do {
490 do {
491 REALFIX ajm, ajp, akm, akp;
492 REALFIX bjm, bjp, bkm, bkp;
493 int k2;
494  
495 0 k1 = kk + kspan;
496 0 k2 = k1 + kspan;
497 0 k3 = k2 + kspan;
498 0 akp = Re_Data (kk) + Re_Data (k2);
499 0 akm = Re_Data (kk) - Re_Data (k2);
500  
501 0 ajp = Re_Data (k1) + Re_Data (k3);
502 0 ajm = Re_Data (k1) - Re_Data (k3);
503  
504 0 bkp = Im_Data (kk) + Im_Data (k2);
505 0 bkm = Im_Data (kk) - Im_Data (k2);
506  
507 0 bjp = Im_Data (k1) + Im_Data (k3);
508 0 bjm = Im_Data (k1) - Im_Data (k3);
509  
510 0 Re_Data (kk) = akp + ajp;
511 0 Im_Data (kk) = bkp + bjp;
512 0 ajp = akp - ajp;
513 0 bjp = bkp - bjp;
514 0 ▶ if (iSign < 0)
Branch: 3 branches
BranchTrueFalseTotal
if (iSign < 0) 221186 221186 442372
if (iSign < 0) 884738 589826 1474564
if (iSign < 0) 0 0 0
515 {
516 0 akp = akm + bjm;
517 0 bkp = bkm - ajm;
518 0 akm -= bjm;
519 0 bkm += ajm;
520 }
521 else
522 {
523 0 akp = akm - bjm;
524 0 bkp = bkm + ajm;
525 0 akm += bjm;
526 0 bkm -= ajm;
527 }
528 /* avoid useless multiplies */
529 0 ▶ if (s1 == 0.0)
Branch: 3 branches
BranchTrueFalseTotal
if (s1 == 0.0) 223492 218880 442372
if (s1 == 0.0) 744964 729600 1474564
if (s1 == 0.0) 0 0 0
530 {
531 0 Re_Data (k1) = akp;
532 0 Re_Data (k2) = ajp;
533 0 Re_Data (k3) = akm;
534 0 Im_Data (k1) = bkp;
535 0 Im_Data (k2) = bjp;
536 0 Im_Data (k3) = bkm;
537 }
538 else
539 {
540 0 Re_Data (k1) = akp * c1 - bkp * s1;
541 0 Re_Data (k2) = ajp * c2 - bjp * s2;
542 0 Re_Data (k3) = akm * c3 - bkm * s3;
543 0 Im_Data (k1) = akp * s1 + bkp * c1;
544 0 Im_Data (k2) = ajp * s2 + bjp * c2;
545 0 Im_Data (k3) = akm * s3 + bkm * c3;
546 }
547 0 kk = k3 + kspan;
548 0 ▶ } while (kk <= nt);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= nt); 218880 223492 442372
} while (kk <= nt); 729600 744964 1474564
} while (kk <= nt); 0 0 0
549  
550 0 c2 = c1 - (cd * c1 + sd * s1);
551 0 s1 = sd * c1 - cd * s1 + s1;
552 0 c1 = 2.0 - (c2 * c2 + s1 * s1);
553 0 s1 *= c1;
554 0 c1 *= c2;
555 /* values of c2, c3, s2, s3 that will get used next time */
556 0 c2 = c1 * c1 - s1 * s1;
557 0 s2 = 2.0 * c1 * s1;
558 0 c3 = c2 * c1 - s2 * s1;
559 0 s3 = c2 * s1 + s2 * c1;
560 0 kk = kk - nt + jc;
561 0 ▶ } while (kk <= kspan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= kspan); 218880 4612 223492
} while (kk <= kspan); 729600 15364 744964
} while (kk <= kspan); 0 0 0
562 0 kk = kk - kspan + inc;
563 0 ▶ } while (kk <= jc);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= jc); 0 4612 4612
} while (kk <= jc); 0 15364 15364
} while (kk <= jc); 0 0 0
564 0 ▶ if (kspan == jc)
Branch: 3 branches
BranchTrueFalseTotal
if (kspan == jc) 2308 2304 4612
if (kspan == jc) 7684 7680 15364
if (kspan == jc) 0 0 0
565 0 goto Permute_Results; /* exit infinite loop */
566 0 break;
567  
568 0 default:
569 /* transform for odd factors */
570 #ifdef FFT_RADIX4
571 fprintf (stderr, "Error: " FFTRADIXS "(): compiled for radix 2/4 only\n");
572 FFTRADIX_RETURN(-1);
573 break;
574 #else /* FFT_RADIX4 */
575 0 ispan = kspan;
576 0 k = factor [ii - 1];
577 0 kspan /= factor [ii - 1];
578  
579 0 switch (factor [ii - 1]) {
580 0 case 3: /* transform for factor of 3 (optional code) */
581 do {
582 do {
583 REALFIX aj, tmpr;
584 REALFIX bj, tmpi;
585 int k2;
586  
587 0 k1 = kk + kspan;
588 0 k2 = k1 + kspan;
589 0 tmpr = Re_Data (kk);
590 0 tmpi = Im_Data (kk);
591 0 aj = Re_Data (k1) + Re_Data (k2);
592 0 bj = Im_Data (k1) + Im_Data (k2);
593 0 Re_Data (kk) = tmpr + aj;
594 0 Im_Data (kk) = tmpi + bj;
595 0 tmpr -= 0.5 * aj;
596 0 tmpi -= 0.5 * bj;
597 0 aj = (Re_Data (k1) - Re_Data (k2)) * s60;
598 0 bj = (Im_Data (k1) - Im_Data (k2)) * s60;
599 0 Re_Data (k1) = tmpr - bj;
600 0 Re_Data (k2) = tmpr + bj;
601 0 Im_Data (k1) = tmpi + aj;
602 0 Im_Data (k2) = tmpi - aj;
603 0 kk = k2 + kspan;
604 0 ▶ } while (kk < nn);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < nn); 276480 18432 294912
} while (kk < nn); 921600 63050 984650
} while (kk < nn); 0 0 0
605 0 kk -= nn;
606 0 ▶ } while (kk <= kspan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= kspan); 16128 2304 18432
} while (kk <= kspan); 55300 7750 63050
} while (kk <= kspan); 0 0 0
607 0 break;
608  
609 0 case 5: /* transform for factor of 5 (optional code) */
610 0 c2 = c72 * c72 - s72 * s72;
611 0 s2 = 2.0 * c72 * s72;
612 do {
613 do {
614 REALFIX aa, aj, ak, ajm, ajp, akm, akp;
615 REALFIX bb, bj, bk, bjm, bjp, bkm, bkp;
616 int k2, k4;
617  
618 0 k1 = kk + kspan;
619 0 k2 = k1 + kspan;
620 0 k3 = k2 + kspan;
621 0 k4 = k3 + kspan;
622 0 akp = Re_Data (k1) + Re_Data (k4);
623 0 akm = Re_Data (k1) - Re_Data (k4);
624 0 bkp = Im_Data (k1) + Im_Data (k4);
625 0 bkm = Im_Data (k1) - Im_Data (k4);
626 0 ajp = Re_Data (k2) + Re_Data (k3);
627 0 ajm = Re_Data (k2) - Re_Data (k3);
628 0 bjp = Im_Data (k2) + Im_Data (k3);
629 0 bjm = Im_Data (k2) - Im_Data (k3);
630 0 aa = Re_Data (kk);
631 0 bb = Im_Data (kk);
632 0 Re_Data (kk) = aa + akp + ajp;
633 0 Im_Data (kk) = bb + bkp + bjp;
634 0 ak = akp * c72 + ajp * c2 + aa;
635 0 bk = bkp * c72 + bjp * c2 + bb;
636 0 aj = akm * s72 + ajm * s2;
637 0 bj = bkm * s72 + bjm * s2;
638 0 Re_Data (k1) = ak - bj;
639 0 Re_Data (k4) = ak + bj;
640 0 Im_Data (k1) = bk + aj;
641 0 Im_Data (k4) = bk - aj;
642 0 ak = akp * c2 + ajp * c72 + aa;
643 0 bk = bkp * c2 + bjp * c72 + bb;
644 0 aj = akm * s2 - ajm * s72;
645 0 bj = bkm * s2 - bjm * s72;
646 0 Re_Data (k2) = ak - bj;
647 0 Re_Data (k3) = ak + bj;
648 0 Im_Data (k2) = bk + aj;
649 0 Im_Data (k3) = bk - aj;
650 0 kk = k4 + kspan;
651 0 ▶ } while (kk < nn);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < nn); 0 0 0
} while (kk < nn); 620 1586 2206
} while (kk < nn); 0 0 0
652 0 kk -= nn;
653 0 ▶ } while (kk <= kspan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= kspan); 0 0 0
} while (kk <= kspan); 828 758 1586
} while (kk <= kspan); 0 0 0
654 0 break;
655  
656 0 default:
657 0 k = factor [ii - 1];
658 0 ▶ if (jf != k)
Branch: 3 branches
BranchTrueFalseTotal
if (jf != k) 0 0 0
if (jf != k) 208 0 208
if (jf != k) 0 0 0
659 {
660 0 jf = k;
661 0 s1 = pi2 / (double) jf;
662 0 c1 = cos (s1);
663 0 s1 = sin (s1);
664 0 ▶ if (jf > maxFactors)
Branch: 3 branches
BranchTrueFalseTotal
if (jf > maxFactors) 0 0 0
if (jf > maxFactors) 0 208 208
if (jf > maxFactors) 0 0 0
665 0 goto Memory_Error;
666 0 Cos [jf - 1] = 1.0;
667 0 Sin [jf - 1] = 0.0;
668 0 j = 1;
669 do {
670 0 Cos [j - 1] = Cos [k - 1] * c1 + Sin [k - 1] * s1;
671 0 Sin [j - 1] = Cos [k - 1] * s1 - Sin [k - 1] * c1;
672 0 k--;
673 0 Cos [k - 1] = Cos [j - 1];
674 0 Sin [k - 1] = -Sin [j - 1];
675 0 j++;
676 0 ▶ } while (j < k);
Branch: 3 branches
BranchTrueFalseTotal
} while (j < k); 0 0 0
} while (j < k); 976 208 1184
} while (j < k); 0 0 0
677 }
678 do {
679 do {
680 REALFIX aa, ak;
681 REALFIX bb, bk;
682 int k2;
683  
684 0 aa = ak = Re_Data (kk);
685 0 bb = bk = Im_Data (kk);
686  
687 0 k1 = kk;
688 0 k2 = kk + ispan;
689 0 j = 1;
690 0 k1 += kspan;
691 do {
692 0 k2 -= kspan;
693 0 Rtmp [j] = Re_Data (k1) + Re_Data (k2);
694 0 ak += Rtmp [j];
695 0 Itmp [j] = Im_Data (k1) + Im_Data (k2);
696 0 bk += Itmp [j];
697 0 j++;
698 0 Rtmp [j] = Re_Data (k1) - Re_Data (k2);
699 0 Itmp [j] = Im_Data (k1) - Im_Data (k2);
700 0 j++;
701 0 k1 += kspan;
702 0 ▶ } while (k1 < k2);
Branch: 3 branches
BranchTrueFalseTotal
} while (k1 < k2); 0 0 0
} while (k1 < k2); 3480 900 4380
} while (k1 < k2); 0 0 0
703 0 Re_Data (kk) = ak;
704 0 Im_Data (kk) = bk;
705  
706 0 k1 = kk;
707 0 k2 = kk + ispan;
708 0 j = 1;
709 do {
710 0 REALFIX aj = 0.0;
711 0 REALFIX bj = 0.0;
712  
713 0 k1 += kspan;
714 0 k2 -= kspan;
715 0 jj = j;
716 0 ak = aa;
717 0 bk = bb;
718 0 k = 1;
719 do {
720 0 ak += Rtmp [k] * Cos [jj - 1];
721 0 bk += Itmp [k] * Cos [jj - 1];
722 0 k++;
723 0 aj += Rtmp [k] * Sin [jj - 1];
724 0 bj += Itmp [k] * Sin [jj - 1];
725 0 k++;
726 0 jj += j;
727 0 ▶ if (jj > jf)
Branch: 3 branches
BranchTrueFalseTotal
if (jj > jf) 0 0 0
if (jj > jf) 7680 23940 31620
if (jj > jf) 0 0 0
728 0 jj -= jf;
729 0 ▶ } while (k < jf);
Branch: 3 branches
BranchTrueFalseTotal
} while (k < jf); 0 0 0
} while (k < jf); 27240 4380 31620
} while (k < jf); 0 0 0
730 0 k = jf - j;
731 0 Re_Data (k1) = ak - bj;
732 0 Im_Data (k1) = bk + aj;
733 0 Re_Data (k2) = ak + bj;
734 0 Im_Data (k2) = bk - aj;
735 0 j++;
736 0 ▶ } while (j < k);
Branch: 3 branches
BranchTrueFalseTotal
} while (j < k); 0 0 0
} while (j < k); 3480 900 4380
} while (j < k); 0 0 0
737 0 kk += ispan;
738 0 ▶ } while (kk <= nn);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= nn); 0 0 0
} while (kk <= nn); 692 208 900
} while (kk <= nn); 0 0 0
739 0 kk -= nn;
740 0 ▶ } while (kk <= kspan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= kspan); 0 0 0
} while (kk <= kspan); 0 208 208
} while (kk <= kspan); 0 0 0
741 0 break;
742 }
743 /* multiply by rotation factor (except for factors of 2 and 4) */
744 0 ▶ if (ii == nFactor)
Branch: 3 branches
BranchTrueFalseTotal
if (ii == nFactor) 0 2304 2304
if (ii == nFactor) 828 7888 8716
if (ii == nFactor) 0 0 0
745 0 goto Permute_Results; /* exit infinite loop */
746 0 kk = jc + 1;
747 do {
748 0 c2 = 1.0 - cd;
749 0 s1 = sd;
750 do {
751 0 c1 = c2;
752 0 s2 = s1;
753 0 kk += kspan;
754 do {
755 REALFIX tmp;
756 do {
757 REALFIX ak;
758 0 ak = Re_Data (kk);
759 0 Re_Data (kk) = c2 * ak - s2 * Im_Data (kk);
760 0 Im_Data (kk) = s2 * ak + c2 * Im_Data (kk);
761 0 kk += ispan;
762 0 ▶ } while (kk <= nt);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= nt); 483840 32256 516096
} while (kk <= nt); 1612800 113912 1726712
} while (kk <= nt); 0 0 0
763 0 tmp = s1 * s2;
764 0 s2 = s1 * c2 + c1 * s2;
765 0 c2 = c1 * c2 - tmp;
766 0 kk = kk - nt + kspan;
767 0 ▶ } while (kk <= ispan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= ispan); 16128 16128 32256
} while (kk <= ispan); 57784 56128 113912
} while (kk <= ispan); 0 0 0
768 0 c2 = c1 - (cd * c1 + sd * s1);
769 0 s1 += sd * c1 - cd * s1;
770 0 c1 = 2.0 - (c2 * c2 + s1 * s1);
771 0 s1 *= c1;
772 0 c2 *= c1;
773 0 kk = kk - ispan + jc;
774 0 ▶ } while (kk <= kspan);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= kspan); 13824 2304 16128
} while (kk <= kspan); 48240 7888 56128
} while (kk <= kspan); 0 0 0
775 0 kk = kk - kspan + jc + inc;
776 0 ▶ } while (kk <= jc + jc);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk <= jc + jc); 0 2304 2304
} while (kk <= jc + jc); 0 7888 7888
} while (kk <= jc + jc); 0 0 0
777 0 break;
778 #endif /* FFT_RADIX4 */
779 }
780 }
781  
782 /* permute the results to normal order -- done in two stages */
783 /* permutation for square factors of n */
784 0 Permute_Results:
785 0 Perm [0] = ns;
786 0 ▶ if (kt)
Branch: 3 branches
BranchTrueFalseTotal
if (kt) 2304 4 2308
if (kt) 7824 832 8656
if (kt) 0 0 0
787 {
788 int k2;
789  
790 0 k = kt + kt + 1;
791 0 ▶ if (k > nFactor)
Branch: 3 branches
BranchTrueFalseTotal
if (k > nFactor) 0 2304 2304
if (k > nFactor) 0 7824 7824
if (k > nFactor) 0 0 0
792 0 k--;
793 0 Perm [k] = jc;
794 0 j = 1;
795 do {
796 0 Perm [j] = Perm [j - 1] / factor [j - 1];
797 0 Perm [k - 1] = Perm [k] * factor [j - 1];
798 0 j++;
799 0 k--;
800 0 ▶ } while (j < k);
Branch: 3 branches
BranchTrueFalseTotal
} while (j < k); 2304 2304 4608
} while (j < k); 7680 7824 15504
} while (j < k); 0 0 0
801 0 k3 = Perm [k];
802 0 kspan = Perm [1];
803 0 kk = jc + 1;
804 0 k2 = kspan + 1;
805 0 j = 1;
806 0 ▶ if (nPass != nTotal)
Branch: 3 branches
BranchTrueFalseTotal
if (nPass != nTotal) 2304 0 2304
if (nPass != nTotal) 7824 0 7824
if (nPass != nTotal) 0 0 0
807 {
808 /* permutation for multivariate transform */
809 0 Permute_Multi:
810 do {
811 do {
812 0 k = kk + jc;
813 do {
814 /* swap
815 * Re_Data (kk) <> Re_Data (k2)
816 * Im_Data (kk) <> Im_Data (k2)
817 */
818 REALFIX tmp;
819 0 tmp = Re_Data (kk); Re_Data (kk) = Re_Data (k2); Re_Data (k2) = tmp;
820 0 tmp = Im_Data (kk); Im_Data (kk) = Im_Data (k2); Im_Data (k2) = tmp;
821 0 kk += inc;
822 0 k2 += inc;
823 0 ▶ } while (kk < k);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < k); 0 0 0
} while (kk < k); 0 0 0
} while (kk < k); 0 0 0
824 0 kk += (ns - jc);
825 0 k2 += (ns - jc);
826 0 ▶ } while (kk < nt);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < nt); 0 0 0
} while (kk < nt); 0 0 0
} while (kk < nt); 0 0 0
827 0 k2 = k2 - nt + kspan;
828 0 kk = kk - nt + jc;
829 0 ▶ } while (k2 < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 < ns); 0 0 0
} while (k2 < ns); 0 0 0
} while (k2 < ns); 0 0 0
830 do {
831 do {
832 0 k2 -= Perm [j - 1];
833 0 j++;
834 0 k2 = Perm [j] + k2;
835 0 ▶ } while (k2 > Perm [j - 1]);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 > Perm [j - 1]); 0 0 0
} while (k2 > Perm [j - 1]); 0 0 0
} while (k2 > Perm [j - 1]); 0 0 0
836 0 j = 1;
837 do {
838 0 ▶ if (kk < k2)
Branch: 3 branches
BranchTrueFalseTotal
if (kk < k2) 0 0 0
if (kk < k2) 0 0 0
if (kk < k2) 0 0 0
839 0 goto Permute_Multi;
840 0 kk += jc;
841 0 k2 += kspan;
842 0 ▶ } while (k2 < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 < ns); 0 0 0
} while (k2 < ns); 0 0 0
} while (k2 < ns); 0 0 0
843 0 ▶ } while (kk < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < ns); 0 0 0
} while (kk < ns); 0 0 0
} while (kk < ns); 0 0 0
844 }
845 else
846 {
847 /* permutation for single-variate transform (optional code) */
848 0 Permute_Single:
849 do {
850 /* swap
851 * Re_Data (kk) <> Re_Data (k2)
852 * Im_Data (kk) <> Im_Data (k2)
853 */
854 REALFIX t;
855 0 t = Re_Data (kk); Re_Data (kk) = Re_Data (k2); Re_Data (k2) = t;
856 0 t = Im_Data (kk); Im_Data (kk) = Im_Data (k2); Im_Data (k2) = t;
857 0 kk += inc;
858 0 k2 += kspan;
859 0 ▶ } while (k2 < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 < ns); 207360 179712 387072
} while (k2 < ns); 691200 599328 1290528
} while (k2 < ns); 0 0 0
860 do {
861 do {
862 0 k2 -= Perm [j - 1];
863 0 j++;
864 0 k2 = Perm [j] + k2;
865 0 ▶ } while (k2 > Perm [j - 1]);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 > Perm [j - 1]); 131328 218880 350208
} while (k2 > Perm [j - 1]); 437904 730032 1167936
} while (k2 > Perm [j - 1]); 0 0 0
866 0 j = 1;
867 do {
868 0 ▶ if (kk < k2)
Branch: 3 branches
BranchTrueFalseTotal
if (kk < k2) 177408 493056 670464
if (kk < k2) 591504 1644096 2235600
if (kk < k2) 0 0 0
869 0 goto Permute_Single;
870 0 kk += inc;
871 0 k2 += kspan;
872 0 ▶ } while (k2 < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (k2 < ns); 451584 41472 493056
} while (k2 < ns); 1505568 138528 1644096
} while (k2 < ns); 0 0 0
873 0 ▶ } while (kk < ns);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < ns); 39168 2304 41472
} while (kk < ns); 130704 7824 138528
} while (kk < ns); 0 0 0
874 }
875 0 jc = k3;
876 }
877  
878 0 ▶ if ((kt << 1) + 1 >= nFactor)
Branch: 3 branches
BranchTrueFalseTotal
if ((kt << 1) + 1 >= nFactor) 4 2304 2308
if ((kt << 1) + 1 >= nFactor) 148 8508 8656
if ((kt << 1) + 1 >= nFactor) 0 0 0
879 0 ▶ FFTRADIX_RETURN(0);
Branch: 15 branches
BranchTrueFalseTotal
FFTRADIX_RETURN(0); 4 0 4
FFTRADIX_RETURN(0); 4 0 4
FFTRADIX_RETURN(0); 4 0 4
FFTRADIX_RETURN(0); 4 0 4
FFTRADIX_RETURN(0); 4 0 4
FFTRADIX_RETURN(0); 148 0 148
FFTRADIX_RETURN(0); 148 0 148
FFTRADIX_RETURN(0); 148 0 148
FFTRADIX_RETURN(0); 148 0 148
FFTRADIX_RETURN(0); 148 0 148
FFTRADIX_RETURN(0); 0 0 0
FFTRADIX_RETURN(0); 0 0 0
FFTRADIX_RETURN(0); 0 0 0
FFTRADIX_RETURN(0); 0 0 0
FFTRADIX_RETURN(0); 0 0 0
880 0 ispan = Perm [kt];
881  
882 /* permutation for square-free factors of n */
883 0 j = nFactor - kt;
884 0 factor [j] = 1;
885 do {
886 0 factor [j - 1] *= factor [j];
887 0 j--;
888 0 ▶ } while (j != kt);
Branch: 3 branches
BranchTrueFalseTotal
} while (j != kt); 2304 2304 4608
} while (j != kt); 8508 8508 17016
} while (j != kt); 0 0 0
889 0 nn = factor [kt] - 1;
890 0 kt++;
891 0 ▶ if (nn > maxPerm)
Branch: 3 branches
BranchTrueFalseTotal
if (nn > maxPerm) 0 2304 2304
if (nn > maxPerm) 0 8508 8508
if (nn > maxPerm) 0 0 0
892 0 goto Memory_Error;
893  
894 0 j = jj = 0;
895 0 for (;;) {
896 int k2;
897  
898 0 k = kt + 1;
899 0 k2 = factor [kt - 1];
900 0 kk = factor [k - 1];
901 0 j++;
902 0 ▶ if (j > nn)
Branch: 3 branches
BranchTrueFalseTotal
if (j > nn) 2304 11520 13824
if (j > nn) 8508 53432 61940
if (j > nn) 0 0 0
903 0 break; /* exit infinite loop */
904 0 jj += kk;
905 0 ▶ while (jj >= k2)
Branch: 3 branches
BranchTrueFalseTotal
while (jj >= k2) 4608 11520 16128
while (jj >= k2) 20208 53432 73640
while (jj >= k2) 0 0 0
906 {
907 0 jj -= k2;
908 0 k2 = kk;
909 0 kk = factor [k++];
910 0 jj += kk;
911 }
912 0 Perm [j - 1] = jj;
913 }
914 /* determine the permutation cycles of length greater than 1 */
915 0 j = 0;
916 0 for (;;) {
917 do {
918 0 kk = Perm [j++];
919 0 ▶ } while (kk < 0);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk < 0); 6912 4608 11520
} while (kk < 0); 35170 18262 53432
} while (kk < 0); 0 0 0
920 0 ▶ if (kk != j)
Branch: 3 branches
BranchTrueFalseTotal
if (kk != j) 2304 2304 4608
if (kk != j) 9546 8716 18262
if (kk != j) 0 0 0
921 {
922 do {
923 0 k = kk;
924 0 kk = Perm [k - 1];
925 0 Perm [k - 1] = -kk;
926 0 ▶ } while (kk != j);
Branch: 3 branches
BranchTrueFalseTotal
} while (kk != j); 4608 2304 6912
} while (kk != j); 25624 9546 35170
} while (kk != j); 0 0 0
927 0 k3 = kk;
928 }
929 else
930 {
931 0 Perm [j - 1] = -j;
932 0 ▶ if (j == nn)
Branch: 3 branches
BranchTrueFalseTotal
if (j == nn) 2304 0 2304
if (j == nn) 8508 208 8716
if (j == nn) 0 0 0
933 0 break; /* exit infinite loop */
934 }
935 }
936  
937 0 maxFactors *= inc;
938  
939 /* reorder a and b, following the permutation cycles */
940 for (;;) {
941 0 j = k3 + 1;
942 0 nt -= ispan;
943 0 ii = nt - inc + 1;
944 0 ▶ if (nt < 0)
Branch: 3 branches
BranchTrueFalseTotal
if (nt < 0) 2304 18432 20736
if (nt < 0) 8508 62268 70776
if (nt < 0) 0 0 0
945 0 break; /* exit infinite loop */
946 do {
947 do {
948 0 j--;
949 0 ▶ } while (Perm [j - 1] < 0);
Branch: 3 branches
BranchTrueFalseTotal
} while (Perm [j - 1] < 0); 0 18432 18432
} while (Perm [j - 1] < 0); 1460 63306 64766
} while (Perm [j - 1] < 0); 0 0 0
950 0 jj = jc;
951 do {
952 int k2;
953  
954 0 ▶ if (jj < maxFactors) kspan = jj; else kspan = maxFactors;
Branch: 3 branches
BranchTrueFalseTotal
if (jj < maxFactors) kspan = jj; else kspan = maxFactors; 18432 0 18432
if (jj < maxFactors) kspan = jj; else kspan = maxFactors; 63306 0 63306
if (jj < maxFactors) kspan = jj; else kspan = maxFactors; 0 0 0
955  
956 0 jj -= kspan;
957 0 k = Perm [j - 1];
958 0 kk = jc * k + ii + jj;
959  
960 0 k1 = kk + kspan;
961 0 k2 = 0;
962 do {
963 0 Rtmp [k2] = Re_Data (k1);
964 0 Itmp [k2] = Im_Data (k1);
965 0 k2++;
966 0 k1 -= inc;
967 0 ▶ } while (k1 != kk);
Branch: 3 branches
BranchTrueFalseTotal
} while (k1 != kk); 129024 18432 147456
} while (k1 != kk); 430080 63306 493386
} while (k1 != kk); 0 0 0
968  
969 do {
970 0 k1 = kk + kspan;
971 0 k2 = k1 - jc * (k + Perm [k - 1]);
972 0 k = -Perm [k - 1];
973 do {
974 0 Re_Data (k1) = Re_Data (k2);
975 0 Im_Data (k1) = Im_Data (k2);
976 0 k1 -= inc;
977 0 k2 -= inc;
978 0 ▶ } while (k1 != kk);
Branch: 3 branches
BranchTrueFalseTotal
} while (k1 != kk); 387072 55296 442368
} while (k1 != kk); 1290240 196450 1486690
} while (k1 != kk); 0 0 0
979 0 kk = k2;
980 0 ▶ } while (k != j);
Branch: 3 branches
BranchTrueFalseTotal
} while (k != j); 36864 18432 55296
} while (k != j); 133144 63306 196450
} while (k != j); 0 0 0
981  
982 0 k1 = kk + kspan;
983 0 k2 = 0;
984 do {
985 0 Re_Data (k1) = Rtmp [k2];
986 0 Im_Data (k1) = Itmp [k2];
987 0 k2++;
988 0 k1 -= inc;
989 0 ▶ } while (k1 != kk);
Branch: 3 branches
BranchTrueFalseTotal
} while (k1 != kk); 129024 18432 147456
} while (k1 != kk); 430080 63306 493386
} while (k1 != kk); 0 0 0
990 0 ▶ } while (jj);
Branch: 3 branches
BranchTrueFalseTotal
} while (jj); 0 18432 18432
} while (jj); 0 63306 63306
} while (jj); 0 0 0
991 0 ▶ } while (j != 1);
Branch: 3 branches
BranchTrueFalseTotal
} while (j != 1); 0 18432 18432
} while (j != 1); 1038 62268 63306
} while (j != 1); 0 0 0
992 }
993 0 ▶ FFTRADIX_RETURN(0); /* exit point here */
Branch: 15 branches
BranchTrueFalseTotal
FFTRADIX_RETURN(0); /* exit point here */ 2304 0 2304
FFTRADIX_RETURN(0); /* exit point here */ 2304 0 2304
FFTRADIX_RETURN(0); /* exit point here */ 2304 0 2304
FFTRADIX_RETURN(0); /* exit point here */ 2304 0 2304
FFTRADIX_RETURN(0); /* exit point here */ 2304 0 2304
FFTRADIX_RETURN(0); /* exit point here */ 8508 0 8508
FFTRADIX_RETURN(0); /* exit point here */ 8508 0 8508
FFTRADIX_RETURN(0); /* exit point here */ 8508 0 8508
FFTRADIX_RETURN(0); /* exit point here */ 8508 0 8508
FFTRADIX_RETURN(0); /* exit point here */ 8508 0 8508
FFTRADIX_RETURN(0); /* exit point here */ 0 0 0
FFTRADIX_RETURN(0); /* exit point here */ 0 0 0
FFTRADIX_RETURN(0); /* exit point here */ 0 0 0
FFTRADIX_RETURN(0); /* exit point here */ 0 0 0
FFTRADIX_RETURN(0); /* exit point here */ 0 0 0
994  
995 /* alloc or other problem, do some clean-up */
996 0 Memory_Error:
997 0 fprintf (stderr, "Error: " FFTRADIXS "() - insufficient memory.\n");
998 0 ▶ FFTRADIX_RETURN(-1);
Branch: 15 branches
BranchTrueFalseTotal
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
FFTRADIX_RETURN(-1); 0 0 0
999 #undef FFTRADIX_RETURN
1000 #undef FFTRADIX_MALLOC
1001 }
1002  
1003 /*
1004 *
1005 */
1006 int
1007 10964 FFTN (size_t ndim,
1008 const size_t dims [],
1009 REAL Re [],
1010 REAL Im [],
1011 int iSign,
1012 REAL scaling)
1013 {
1014 size_t nTotal;
1015 int maxFactors, maxPerm;
1016  
1017 /*
1018 * tally the number of elements in the data array
1019 * and determine the number of dimensions
1020 */
1021 10964 nTotal = 1;
1022 10964 if (ndim)
1023 {
1024 10964 if (dims != NULL)
1025 {
1026 int i;
1027 /* number of dimensions was specified */
1028 0 for (i = 0; i < ndim; i++)
1029 {
1030 0 if (dims [i] <= 0) goto Dimension_Error;
1031 0 nTotal *= dims [i];
1032 }
1033 }
1034 else
1035 10964 nTotal *= ndim;
1036 }
1037 else
1038 {
1039 int i;
1040 /* determine # of dimensions from zero-terminated list */
1041 0 if (dims == NULL) goto Dimension_Error;
1042 0 for (ndim = i = 0; dims [i]; i++)
1043 {
1044 0 if (dims [i] <= 0)
1045 0 goto Dimension_Error;
1046 0 nTotal *= dims [i];
1047 0 ndim++;
1048 }
1049 }
1050  
1051 /* determine maximum number of factors and permuations */
1052 #if 1
1053 /*
1054 * follow John Beale's example, just use the largest dimension and don't
1055 * worry about excess allocation. May be someone else will do it?
1056 */
1057 10964 if (dims != NULL)
1058 {
1059 int i;
1060 0 for (maxFactors = maxPerm = 1, i = 0; i < ndim; i++)
1061 {
1062 0 if (dims [i] > maxFactors) maxFactors = dims [i];
1063 0 if (dims [i] > maxPerm) maxPerm = dims [i];
1064 }
1065 }
1066 else
1067 {
1068 10964 maxFactors = maxPerm = nTotal;
1069 }
1070 #else
1071 /* use the constants used in the original Fortran code */
1072 maxFactors = 23;
1073 maxPerm = 209;
1074 #endif
1075 /* loop over the dimensions: */
1076 10964 if (dims != NULL)
1077 {
1078 0 size_t nSpan = 1;
1079 int i;
1080  
1081 0 for (i = 0; i < ndim; i++)
1082 {
1083 int ret;
1084 0 nSpan *= dims [i];
1085 0 ret = FFTRADIX (Re, Im, nTotal, dims [i], nSpan, iSign,
1086 maxFactors, maxPerm);
1087 /* exit, clean-up already done */
1088 0 if (ret)
1089 0 return ret;
1090 }
1091 }
1092 else
1093 {
1094 int ret;
1095 10964 ret = FFTRADIX (Re, Im, nTotal, nTotal, nTotal, iSign,
1096 maxFactors, maxPerm);
1097 /* exit, clean-up already done */
1098 10964 if (ret)
1099 0 return ret;
1100 }
1101  
1102 /* Divide through by the normalizing constant: */
1103 10964 if (scaling && scaling != 1.0)
1104 {
1105 int i;
1106  
1107 4380 if (iSign < 0) iSign = -iSign;
1108 4380 if (scaling < 0.0)
1109 4380 scaling = (scaling < -1.0) ? sqrt (nTotal) : nTotal;
1110  
1111 4380 scaling = 1.0 / scaling; /* multiply is often faster */
1112 1631626 for (i = 0; i < nTotal; i += iSign)
1113 {
1114 1627246 Re_Data (i) *= scaling;
1115 1627246 Im_Data (i) *= scaling;
1116 }
1117 }
1118 10964 return 0;
1119  
1120 0 Dimension_Error:
1121 0 fprintf (stderr, "Error: " FFTNS "() - dimension error\n");
1122 0 return -1;
1123 }
1124 #endif /* _FFTN_C */
1125 /*----------------------- end-of-file (C source) -----------------------*/
« lib/PDL/IO/Pnm/get.c ↑ Summary lib/PDL/FFT.xs »