Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 pj 1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
2
<HTML>
3
<HEAD>
4
<!-- This HTML file has been created by texi2html 1.52
5
     from fftw.texi on 18 May 1999 -->
6
 
7
<TITLE>FFTW - FFTW Reference</TITLE>
8
</HEAD>
9
<BODY TEXT="#000000" BGCOLOR="#FFFFFF">
10
Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
11
<P><HR><P>
12
 
13
 
14
<H1><A NAME="SEC16">FFTW Reference</A></H1>
15
 
16
<P>
17
This chapter provides a complete reference for all sequential (i.e.,
18
one-processor) FFTW functions.  We first define the data types upon
19
which FFTW operates, that is, real, complex, and "halfcomplex" numbers
20
(see Section <A HREF="fftw_3.html#SEC17">Data Types</A>).  Then, in four sections, we explain the FFTW
21
program interface for complex one-dimensional transforms
22
(see Section <A HREF="fftw_3.html#SEC18">One-dimensional Transforms Reference</A>), complex
23
multi-dimensional transforms (see Section <A HREF="fftw_3.html#SEC24">Multi-dimensional Transforms Reference</A>), and real one-dimensional transforms (see Section <A HREF="fftw_3.html#SEC29">Real One-dimensional Transforms Reference</A>), real multi-dimensional
24
transforms (see Section <A HREF="fftw_3.html#SEC34">Real Multi-dimensional Transforms Reference</A>).
25
Section <A HREF="fftw_3.html#SEC41">Wisdom Reference</A> describes the <CODE>wisdom</CODE> mechanism for
26
exporting and importing plans.  Finally, Section <A HREF="fftw_3.html#SEC45">Memory Allocator Reference</A> describes how to change FFTW's default memory allocator.
27
For parallel transforms, See Section <A HREF="fftw_4.html#SEC47">Parallel FFTW</A>.
28
 
29
 
30
 
31
 
32
<H2><A NAME="SEC17">Data Types</A></H2>
33
<P>
34
<A NAME="IDX98"></A>
35
<A NAME="IDX99"></A>
36
<A NAME="IDX100"></A>
37
 
38
 
39
<P>
40
The routines in the FFTW package use three main kinds of data types.
41
<EM>Real</EM> and <EM>complex</EM> numbers should be already known to the
42
reader.  We also use the term <EM>halfcomplex</EM> to describe complex
43
arrays in a special packed format used by the one-dimensional real
44
transforms (taking advantage of the <EM>hermitian</EM> symmetry that arises
45
in those cases).
46
 
47
 
48
<P>
49
By including <CODE>&#60;fftw.h&#62;</CODE> or <CODE>&#60;rfftw.h&#62;</CODE>, you will have access
50
to the following definitions:
51
 
52
 
53
 
54
<PRE>
55
typedef double fftw_real;
56
 
57
typedef struct {
58
     fftw_real re, im;
59
} fftw_complex;
60
 
61
#define c_re(c)  ((c).re)
62
#define c_im(c)  ((c).im)
63
</PRE>
64
 
65
<P>
66
<A NAME="IDX101"></A>
67
<A NAME="IDX102"></A>
68
 
69
 
70
<P>
71
All FFTW operations are performed on the <CODE>fftw_real</CODE> and
72
<CODE>fftw_complex</CODE> data types.  For <CODE>fftw_complex</CODE> numbers, the
73
two macros <CODE>c_re</CODE> and <CODE>c_im</CODE> retrieve, respectively, the real
74
and imaginary parts of the number.
75
 
76
 
77
<P>
78
A <EM>real array</EM> is an array of real numbers.  A <EM>complex array</EM>
79
is an array of complex numbers.  A one-dimensional array X of
80
n complex numbers is <EM>hermitian</EM> if the following property
81
holds:
82
for all 0 &lt;= i &lt; n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}.
83
Hermitian arrays are relevant to FFTW because the Fourier transform of a
84
real array is hermitian.
85
 
86
 
87
<P>
88
Because of its symmetry, a hermitian array can be stored in half the
89
space of a complex array of the same size.  FFTW's one-dimensional real
90
transforms store hermitian arrays as <EM>halfcomplex</EM> arrays.  A
91
halfcomplex array of size n is
92
<A NAME="IDX103"></A>
93
a one-dimensional array of n <CODE>fftw_real</CODE> numbers.  A
94
hermitian array X in stored into a halfcomplex array Y as
95
follows.
96
For all integers i such that 0 &lt;= i &lt;= n / 2, we have
97
Y<sub>i</sub> = Re(X<sub>i</sub>).  For all integers i such that 0
98
&lt; i &lt; n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>).
99
 
100
 
101
<P>
102
We now illustrate halfcomplex storage for n = 4 and n = 5,
103
since the scheme depends on the parity of n.  Let n = 4.
104
In this case, we have
105
Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
106
Y<sub>2</sub> = Re(X<sub>2</sub>), and  Y<sub>3</sub> = Im(X<sub>1</sub>).
107
Let now n = 5.  In this case, we have
108
Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
109
Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>),
110
and Y<sub>4</sub> = Im(X<sub>1</sub>).
111
 
112
 
113
<P>
114
<A NAME="IDX104"></A>
115
By default, the type <CODE>fftw_real</CODE> equals the C type <CODE>double</CODE>.
116
To work in single precision rather than double precision, <CODE>#define</CODE>
117
the symbol <CODE>FFTW_ENABLE_FLOAT</CODE> in <CODE>fftw.h</CODE> and then recompile
118
the library.  On Unix systems, you can instead use <CODE>configure
119
--enable-float</CODE> at installation time (see Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>).
120
<A NAME="IDX105"></A>
121
<A NAME="IDX106"></A>
122
 
123
 
124
<P>
125
In version 1 of FFTW, the data types were called <CODE>FFTW_REAL</CODE> and
126
<CODE>FFTW_COMPLEX</CODE>.  We changed the capitalization for consistency with
127
the rest of FFTW's conventions.  The old names are still supported, but
128
their use is deprecated.
129
<A NAME="IDX107"></A>
130
<A NAME="IDX108"></A>
131
 
132
 
133
 
134
 
135
<H2><A NAME="SEC18">One-dimensional Transforms Reference</A></H2>
136
 
137
<P>
138
The one-dimensional complex routines are generally prefixed with
139
<CODE>fftw_</CODE>.  Programs using FFTW should be linked with <CODE>-lfftw
140
-lm</CODE> on Unix systems, or with the FFTW and standard math libraries in
141
general.
142
 
143
 
144
 
145
 
146
<H3><A NAME="SEC19">Plan Creation for One-dimensional Transforms</A></H3>
147
 
148
 
149
<PRE>
150
#include &#60;fftw.h&#62;
151
 
152
fftw_plan fftw_create_plan(int n, fftw_direction dir,
153
                           int flags);
154
 
155
fftw_plan fftw_create_plan_specific(int n, fftw_direction dir,
156
                                    int flags,
157
                                    fftw_complex *in, int istride,
158
                                    fftw_complex *out, int ostride);
159
</PRE>
160
 
161
<P>
162
<A NAME="IDX109"></A>
163
<A NAME="IDX110"></A>
164
<A NAME="IDX111"></A>
165
<A NAME="IDX112"></A>
166
 
167
 
168
<P>
169
The function <CODE>fftw_create_plan</CODE> creates a plan, which is
170
a data structure containing all the information that <CODE>fftw</CODE>
171
needs in order to compute the 1D Fourier transform. You can
172
create as many plans as you need, but only one plan for a given
173
array size is required (a plan can be reused many times).
174
 
175
 
176
<P>
177
<CODE>fftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE>
178
if, for some reason, the plan can't be created.  In the
179
default installation, this cannot happen, but it is possible
180
to configure FFTW in such a way that some input sizes are
181
forbidden, and FFTW cannot create a plan.
182
 
183
 
184
<P>
185
The <CODE>fftw_create_plan_specific</CODE> variant takes as additional
186
arguments specific input/output arrays and their strides.  For the last
187
four arguments, you should pass the arrays and strides that you will
188
eventually be passing to <CODE>fftw</CODE>.  The resulting plans will be
189
optimized for those arrays and strides, although they may be used on
190
other arrays as well.  Note: the contents of the in and out arrays are
191
<EM>destroyed</EM> by the specific planner (the initial contents are
192
ignored, so the arrays need not have been initialized).
193
 
194
 
195
 
196
<H4>Arguments</H4>
197
 
198
<UL>
199
<LI>
200
 
201
<CODE>n</CODE> is the size of the transform.  It can be
202
 any positive integer.
203
 
204
 
205
<UL>
206
<LI>
207
 
208
FFTW is best at handling sizes of the form
209
2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
210
        11<SUP>e</SUP> 13<SUP>f</SUP>,
211
where e+f is either 0 or
212
1, and the other exponents are arbitrary.  Other sizes are
213
computed by means of a slow, general-purpose routine (which nevertheless
214
retains
215
O(n lg n)
216
performance, even for prime sizes).  (It is
217
possible to customize FFTW for different array sizes.
218
See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A> for more information.)  Transforms
219
whose sizes are powers of 2 are especially fast.
220
</UL>
221
 
222
<LI>
223
 
224
<CODE>dir</CODE> is the sign of the exponent in the formula that
225
defines the Fourier transform.  It can be -1 or +1.
226
The aliases <CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE>
227
are provided, where <CODE>FFTW_FORWARD</CODE> stands for -1.
228
 
229
<LI>
230
 
231
<A NAME="IDX113"></A>
232
<CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:
233
 
234
<UL>
235
<LI>
236
 
237
<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
238
actually <EM>computing</EM> several FFTs and measuring their
239
execution time.  Depending on the installation, this can take some
240
time. <A NAME="DOCF2" HREF="fftw_foot.html#FOOT2">(2)</A>
241
 
242
<LI>
243
 
244
<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
245
plan (for a RISC processor with many registers).  If neither
246
<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
247
<CODE>FFTW_ESTIMATE</CODE>.
248
 
249
<LI>
250
 
251
<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input and
252
output arrays will be distinct (this is the default).
253
<A NAME="IDX114"></A>
254
 
255
<LI>
256
 
257
<A NAME="IDX115"></A>
258
<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output
259
in the input array.  The algorithm used is not necessarily in place:
260
FFTW is able to compute true in-place transforms only for small values
261
of <CODE>n</CODE>.  If FFTW is not able to compute the transform in-place, it
262
will allocate a temporary array (unless you provide one yourself),
263
compute the transform out of place, and copy the result back.
264
<EM>Warning: This option changes the meaning of some parameters of
265
<CODE>fftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>).
266
 
267
The in-place option is mainly provided for people who want to write
268
their own in-place multi-dimensional Fourier transform, using FFTW as a
269
base.  For example, consider a three-dimensional <CODE>n * n * n</CODE>
270
transform.  An out-of-place algorithm will need another array (which may
271
be huge).  However, FFTW can compute the in-place transform along
272
each dimension using only a temporary array of size <CODE>n</CODE>.
273
Moreover, if FFTW happens to be able to compute the transform truly
274
in-place, no temporary array and no copying are needed.  As distributed,
275
FFTW `knows' how to compute in-place transforms of size 1, 2, 3, 4, 5, 6,
276
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32 and 64.
277
 
278
The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
279
 
280
<LI>
281
 
282
<A NAME="IDX116"></A>
283
<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
284
in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
285
This can greatly speed the creation of plans, especially with the
286
<CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take
287
advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past
288
measurements) than the estimation heuristic would normally
289
generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
290
will also be generated if the current transform size is not completely
291
understood by existing <CODE>wisdom</CODE>.
292
 
293
</UL>
294
 
295
<LI>
296
 
297
<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for
298
<CODE>fftw_create_plan_specific</CODE>): see corresponding arguments in the
299
description of <CODE>fftw</CODE>.  (See Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>.)  In particular, the <CODE>out</CODE> and <CODE>ostride</CODE>
300
parameters have the same special meaning for <CODE>FFTW_IN_PLACE</CODE>
301
transforms as they have for <CODE>fftw</CODE>.
302
 
303
</UL>
304
 
305
 
306
 
307
<H3><A NAME="SEC20">Discussion on Specific Plans</A></H3>
308
<P>
309
<A NAME="IDX117"></A>
310
We recommend the use of the specific planners, even in cases where you
311
will be transforming arrays different from those passed to the specific
312
planners, as they confer the following advantages:
313
 
314
 
315
 
316
<UL>
317
 
318
<LI>
319
 
320
The resulting plans will be optimized for your specific arrays and
321
strides.  This may or may not make a significant difference, but it
322
certainly doesn't hurt.  (The ordinary planner does its planning based
323
upon a stride-one temporary array that it allocates.)
324
 
325
<LI>
326
 
327
Less intermediate storage is required during the planning process.  (The
328
ordinary planner uses O(<CODE>N</CODE>) temporary storage, where <CODE>N</CODE> is
329
the maximum dimension, while it is creating the plan.)
330
 
331
<LI>
332
 
333
For multi-dimensional transforms, new parameters become accessible for
334
optimization by the planner.  (Since multi-dimensional arrays can be
335
very large, we don't dare to allocate one in the ordinary planner for
336
experimentation.  This prevents us from doing certain optimizations
337
that can yield dramatic improvements in some cases.)
338
 
339
</UL>
340
 
341
<P>
342
On the other hand, note that <EM>the specific planner destroys the
343
contents of the <CODE>in</CODE> and <CODE>out</CODE> arrays</EM>.
344
 
345
 
346
 
347
 
348
<H3><A NAME="SEC21">Computing the One-dimensional Transform</A></H3>
349
 
350
 
351
<PRE>
352
#include &#60;fftw.h&#62;
353
 
354
void fftw(fftw_plan plan, int howmany,
355
          fftw_complex *in, int istride, int idist,
356
          fftw_complex *out, int ostride, int odist);
357
 
358
void fftw_one(fftw_plan plan, fftw_complex *in,
359
          fftw_complex *out);
360
</PRE>
361
 
362
<P>
363
<A NAME="IDX118"></A>
364
<A NAME="IDX119"></A>
365
 
366
 
367
<P>
368
The function <CODE>fftw</CODE> computes the one-dimensional Fourier transform,
369
using a plan created by <CODE>fftw_create_plan</CODE> (See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>.)  The function
370
<CODE>fftw_one</CODE> provides a simplified interface for the common case of
371
single input array of stride 1.
372
<A NAME="IDX120"></A>
373
 
374
 
375
 
376
<H4>Arguments</H4>
377
 
378
<UL>
379
<LI>
380
 
381
<CODE>plan</CODE> is the plan created by <CODE>fftw_create_plan</CODE>
382
(see Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>).
383
 
384
<LI>
385
 
386
<CODE>howmany</CODE> is the number of transforms <CODE>fftw</CODE> will compute.
387
It is faster to tell FFTW to compute many transforms, instead of
388
simply calling <CODE>fftw</CODE> many times.
389
 
390
<LI>
391
 
392
<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
393
There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
394
<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
395
up to <CODE>in + (howmany - 1) * idist</CODE>.  Each input array consists of
396
complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), which are not necessarily
397
contiguous in memory.  Specifically, <CODE>in[0]</CODE> is the first element
398
of the first array, <CODE>in[istride]</CODE> is the second element of the
399
first array, and so on.  In general, the <CODE>i</CODE>-th element of the
400
<CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j *
401
idist]</CODE>.
402
 
403
<LI>
404
 
405
<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
406
array(s).  The format is the same as for the input array.
407
 
408
 
409
<UL>
410
<LI><EM>In-place transforms</EM>:
411
 
412
<A NAME="IDX121"></A>
413
If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and
414
<CODE>odist</CODE> are always ignored.  If <CODE>out</CODE> is <CODE>NULL</CODE>,
415
<CODE>out</CODE> is ignored, too.  Otherwise, <CODE>out</CODE> is interpreted as a
416
pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as
417
temporary space to perform the in-place computation.  <CODE>out</CODE> is used
418
as scratch space and its contents destroyed.  In this case, <CODE>out</CODE>
419
must be an ordinary array whose elements are contiguous in memory (no
420
striding).
421
</UL>
422
 
423
</UL>
424
 
425
<P>
426
The function <CODE>fftw_one</CODE> transforms a single, contiguous input array
427
to a contiguous output array.  By definition, the call
428
 
429
<PRE>
430
fftw_one(plan, in, out)
431
</PRE>
432
 
433
<P>
434
is equivalent to
435
 
436
<PRE>
437
fftw(plan, 1, in, 1, 1, out, 1, 1)
438
</PRE>
439
 
440
 
441
 
442
<H3><A NAME="SEC22">Destroying a One-dimensional Plan</A></H3>
443
 
444
 
445
<PRE>
446
#include &#60;fftw.h&#62;
447
 
448
void fftw_destroy_plan(fftw_plan plan);
449
</PRE>
450
 
451
<P>
452
<A NAME="IDX122"></A>
453
 
454
 
455
<P>
456
The function <CODE>fftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and
457
releases all the memory associated with it.  After destruction, a plan
458
is no longer valid.
459
 
460
 
461
 
462
 
463
<H3><A NAME="SEC23">What FFTW Really Computes</A></H3>
464
<P>
465
<A NAME="IDX123"></A>
466
In this section, we define precisely what FFTW computes.  Please be
467
warned that different authors and software packages might employ
468
different conventions than FFTW does.
469
 
470
 
471
<P>
472
The forward transform of a complex array X of size
473
n computes an array Y, where
474
<center><IMG SRC="equation-1.gif" ALIGN="top"></center>
475
 
476
 
477
<P>
478
The backward transform computes
479
<center><IMG SRC="equation-2.gif" ALIGN="top"></center>
480
 
481
 
482
<P>
483
<A NAME="IDX124"></A>
484
FFTW computes an unnormalized transform, that is, the equation
485
IFFT(FFT(X)) = n X holds.  In other words, applying the forward
486
and then the backward transform will multiply the input by n.
487
 
488
 
489
<P>
490
<A NAME="IDX125"></A>
491
An <CODE>FFTW_FORWARD</CODE> transform corresponds to a sign of -1 in
492
the exponent of the DFT.  Note also that we use the standard
493
"in-order" output ordering--the k-th output corresponds to the
494
frequency k/n (or k/T, where T is your total
495
sampling period).  For those who like to think in terms of positive and
496
negative frequencies, this means that the positive frequencies are
497
stored in the first half of the output and the negative frequencies are
498
stored in backwards order in the second half of the output.  (The
499
frequency -k/n is the same as the frequency (n-k)/n.)
500
 
501
 
502
 
503
 
504
<H2><A NAME="SEC24">Multi-dimensional Transforms Reference</A></H2>
505
<P>
506
<A NAME="IDX126"></A>
507
<A NAME="IDX127"></A>
508
The multi-dimensional complex routines are generally prefixed with
509
<CODE>fftwnd_</CODE>.  Programs using FFTWND should be linked with <CODE>-lfftw
510
-lm</CODE> on Unix systems, or with the FFTW and standard math libraries in
511
general.
512
<A NAME="IDX128"></A>
513
 
514
 
515
 
516
 
517
<H3><A NAME="SEC25">Plan Creation for Multi-dimensional Transforms</A></H3>
518
 
519
 
520
<PRE>
521
#include &#60;fftw.h&#62;
522
 
523
fftwnd_plan fftwnd_create_plan(int rank, const int *n,
524
                               fftw_direction dir, int flags);
525
 
526
fftwnd_plan fftw2d_create_plan(int nx, int ny,
527
                               fftw_direction dir, int flags);
528
 
529
fftwnd_plan fftw3d_create_plan(int nx, int ny, int nz,
530
                               fftw_direction dir, int flags);
531
 
532
fftwnd_plan fftwnd_create_plan_specific(int rank, const int *n,
533
                                        fftw_direction dir,
534
                                        int flags,
535
                                        fftw_complex *in, int istride,
536
                                        fftw_complex *out, int ostride);
537
 
538
fftwnd_plan fftw2d_create_plan_specific(int nx, int ny,
539
                                        fftw_direction dir,
540
                                        int flags,
541
                                        fftw_complex *in, int istride,
542
                                        fftw_complex *out, int ostride);
543
 
544
fftwnd_plan fftw3d_create_plan_specific(int nx, int ny, int nz,
545
                                        fftw_direction dir, int flags,
546
                                        fftw_complex *in, int istride,
547
                                        fftw_complex *out, int ostride);
548
</PRE>
549
 
550
<P>
551
<A NAME="IDX129"></A>
552
<A NAME="IDX130"></A>
553
<A NAME="IDX131"></A>
554
<A NAME="IDX132"></A>
555
<A NAME="IDX133"></A>
556
<A NAME="IDX134"></A>
557
<A NAME="IDX135"></A>
558
<A NAME="IDX136"></A>
559
 
560
 
561
<P>
562
The function <CODE>fftwnd_create_plan</CODE> creates a plan, which is a data
563
structure containing all the information that <CODE>fftwnd</CODE> needs in
564
order to compute a multi-dimensional Fourier transform.  You can create
565
as many plans as you need, but only one plan for a given array size is
566
required (a plan can be reused many times).  The functions
567
<CODE>fftw2d_create_plan</CODE> and <CODE>fftw3d_create_plan</CODE> are optional,
568
alternative interfaces to <CODE>fftwnd_create_plan</CODE> for two and three
569
dimensions, respectively.
570
 
571
 
572
<P>
573
<CODE>fftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
574
some reason, the plan can't be created.  This can happen if memory runs
575
out or if the arguments are invalid in some way (e.g.  if <CODE>rank</CODE> &#60;
576
0).
577
 
578
 
579
<P>
580
The <CODE>create_plan_specific</CODE> variants take as additional arguments
581
specific input/output arrays and their strides.  For the last four
582
arguments, you should pass the arrays and strides that you will
583
eventually be passing to <CODE>fftwnd</CODE>.  The resulting plans will be
584
optimized for those arrays and strides, although they may be used on
585
other arrays as well.  Note: the contents of the in and out arrays are
586
<EM>destroyed</EM> by the specific planner (the initial contents are
587
ignored, so the arrays need not have been initialized).
588
See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans.
589
 
590
 
591
 
592
<H4>Arguments</H4>
593
 
594
<UL>
595
<LI>
596
 
597
<CODE>rank</CODE> is the dimensionality of the arrays to be transformed.  It
598
can be any non-negative integer.
599
 
600
<LI>
601
 
602
<CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the
603
size of each dimension of the arrays to be transformed.  These sizes,
604
which must be positive integers, correspond to the dimensions of
605
<A NAME="IDX137"></A>
606
row-major arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose
607
indices vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for more information on row-major storage.)
608
See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>,
609
for more information regarding optimal array sizes.
610
 
611
<LI>
612
 
613
<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>fftw2d_create_plan</CODE> are positive
614
integers specifying the dimensions of the rank 2 array to be
615
transformed. i.e. they specify that the transform will operate on
616
<CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number
617
of rows and <CODE>ny</CODE> is the number of columns.
618
 
619
<LI>
620
 
621
<CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>fftw3d_create_plan</CODE> are
622
positive integers specifying the dimensions of the rank 3 array to be
623
transformed. i.e. they specify that the transform will operate on
624
<CODE>nx x ny x nz</CODE> arrays in row-major order.
625
 
626
<LI>
627
 
628
<CODE>dir</CODE> is the sign of the exponent in the formula that defines the
629
Fourier transform.  It can be -1 or +1.  The aliases
630
<CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE> are provided, where
631
<CODE>FFTW_FORWARD</CODE> stands for -1.
632
 
633
<LI>
634
 
635
<A NAME="IDX138"></A>
636
<CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:
637
 
638
<UL>
639
<LI>
640
 
641
<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
642
actually <EM>computing</EM> several FFTs and measuring their execution
643
time.
644
 
645
<LI>
646
 
647
<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
648
plan (for a RISC processor with many registers).  If neither
649
<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
650
<CODE>FFTW_ESTIMATE</CODE>.
651
 
652
<LI>
653
 
654
<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
655
  and output arrays will be distinct (this is the default).
656
 
657
<LI>
658
 
659
<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform
660
the transform in-place.  (Unlike the one-dimensional transform, this
661
"really" <A NAME="DOCF3" HREF="fftw_foot.html#FOOT3">(3)</A> performs the
662
transform in-place.) Note that, if you want to perform in-place
663
transforms, you <EM>must</EM> use a plan created with this option.
664
 
665
The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
666
 
667
<LI>
668
 
669
<A NAME="IDX139"></A>
670
<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
671
in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)  This can greatly
672
speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE>
673
option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of
674
<CODE>wisdom</CODE> to produce a more optimal plan (based on past
675
measurements) than the estimation heuristic would normally
676
generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
677
will also be generated if the current transform size is not completely
678
understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE>
679
is shared between one-dimensional and multi-dimensional transforms.
680
 
681
</UL>
682
 
683
<LI>
684
 
685
<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for the
686
<CODE>_create_plan_specific</CODE> variants): see corresponding arguments in
687
the description of <CODE>fftwnd</CODE>.  (See Section <A HREF="fftw_3.html#SEC26">Computing the Multi-dimensional Transform</A>.)
688
 
689
</UL>
690
 
691
 
692
 
693
<H3><A NAME="SEC26">Computing the Multi-dimensional Transform</A></H3>
694
 
695
 
696
<PRE>
697
#include &#60;fftw.h&#62;
698
 
699
void fftwnd(fftwnd_plan plan, int howmany,
700
            fftw_complex *in, int istride, int idist,
701
            fftw_complex *out, int ostride, int odist);
702
 
703
void fftwnd_one(fftwnd_plan p, fftw_complex *in,
704
                fftw_complex *out);
705
</PRE>
706
 
707
<P>
708
<A NAME="IDX140"></A>
709
<A NAME="IDX141"></A>
710
 
711
 
712
<P>
713
The function <CODE>fftwnd</CODE> computes the multi-dimensional Fourier
714
Transform, using a plan created by <CODE>fftwnd_create_plan</CODE>
715
(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
716
the array to be transformed.)  The function <CODE>fftwnd_one</CODE> provides a
717
simplified interface for the common case of single input array of stride
718
1.
719
<A NAME="IDX142"></A>
720
 
721
 
722
 
723
<H4>Arguments</H4>
724
 
725
<UL>
726
<LI>
727
 
728
<CODE>plan</CODE> is the plan created by <CODE>fftwnd_create_plan</CODE>.
729
(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it
730
could also have been created by <CODE>fftw2d_create_plan</CODE> or
731
<CODE>fftw3d_create_plan</CODE>, respectively.
732
 
733
<LI>
734
 
735
<CODE>howmany</CODE> is the number of transforms <CODE>fftwnd</CODE> will compute.
736
 
737
<LI>
738
 
739
<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
740
There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
741
<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
742
up to <CODE>in + (howmany - 1) * idist</CODE>.  Each input array consists of
743
complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), stored in row-major format
744
(see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), which are not necessarily
745
contiguous in memory.  Specifically, <CODE>in[0]</CODE> is the first element
746
of the first array, <CODE>in[istride]</CODE> is the second element of the
747
first array, and so on.  In general, the <CODE>i</CODE>-th element of the
748
<CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j *
749
idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into the row-major
750
format for the multi-dimensional array, rather than an index in any
751
particular dimension.
752
 
753
 
754
<UL>
755
<LI><EM>In-place transforms</EM>:
756
 
757
<A NAME="IDX143"></A>
758
For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is
759
computed in-place--the output is returned in the <CODE>in</CODE> array, using
760
the same strides, etcetera, as were used in the input.
761
</UL>
762
 
763
<LI>
764
 
765
<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output array(s).
766
The format is the same as for the input array.
767
 
768
 
769
<UL>
770
<LI><EM>In-place transforms</EM>:
771
 
772
These parameters are ignored for plans created with the
773
<CODE>FFTW_IN_PLACE</CODE> option.
774
</UL>
775
 
776
</UL>
777
 
778
<P>
779
The function <CODE>fftwnd_one</CODE> transforms a single, contiguous input
780
array to a contiguous output array.  By definition, the call
781
 
782
<PRE>
783
fftwnd_one(plan, in, out)
784
</PRE>
785
 
786
<P>
787
is equivalent to
788
 
789
<PRE>
790
fftwnd(plan, 1, in, 1, 1, out, 1, 1)
791
</PRE>
792
 
793
 
794
 
795
<H3><A NAME="SEC27">Destroying a Multi-dimensional Plan</A></H3>
796
 
797
 
798
<PRE>
799
#include &#60;fftw.h&#62;
800
 
801
void fftwnd_destroy_plan(fftwnd_plan plan);
802
</PRE>
803
 
804
<P>
805
<A NAME="IDX144"></A>
806
 
807
 
808
<P>
809
The function <CODE>fftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE>
810
and releases all the memory associated with it.  After destruction,
811
a plan is no longer valid.
812
 
813
 
814
 
815
 
816
<H3><A NAME="SEC28">What FFTWND Really Computes</A></H3>
817
<P>
818
<A NAME="IDX145"></A>
819
 
820
 
821
<P>
822
The conventions that we follow for the multi-dimensional transform are
823
analogous to those for the one-dimensional transform. In particular, the
824
forward transform has a negative sign in the exponent and neither the
825
forward nor the backward transforms will perform any normalization.
826
Computing the backward transform of the forward transform will multiply
827
the array by the product of its dimensions.  The output is in-order, and
828
the zeroth element of the output is the amplitude of the zero frequency
829
component.
830
 
831
 
832
The Gods forbade using HTML to display mathematical formulas.  Please
833
see the TeX or Postscript version of this manual for the proper
834
definition of the n-dimensional Fourier transform that FFTW
835
uses.  For completeness, we include a bitmap of the TeX output below:
836
<P><center><IMG SRC="equation-3.gif" ALIGN="top"></center>
837
 
838
 
839
 
840
<H2><A NAME="SEC29">Real One-dimensional Transforms Reference</A></H2>
841
 
842
<P>
843
The one-dimensional real routines are generally prefixed with
844
<CODE>rfftw_</CODE>. <A NAME="DOCF4" HREF="fftw_foot.html#FOOT4">(4)</A>  Programs using RFFTW
845
should be linked with <CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with
846
the RFFTW, the FFTW, and the standard math libraries in general.
847
<A NAME="IDX146"></A>
848
<A NAME="IDX147"></A>
849
<A NAME="IDX148"></A>
850
 
851
 
852
 
853
 
854
<H3><A NAME="SEC30">Plan Creation for Real One-dimensional Transforms</A></H3>
855
 
856
 
857
<PRE>
858
#include &#60;rfftw.h&#62;
859
 
860
rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags);
861
 
862
rfftw_plan rfftw_create_plan_specific(int n, fftw_direction dir,
863
            int flags, fftw_real *in, int istride,
864
            fftw_real *out, int ostride);
865
</PRE>
866
 
867
<P>
868
<A NAME="IDX149"></A>
869
<A NAME="IDX150"></A>
870
<A NAME="IDX151"></A>
871
 
872
 
873
<P>
874
The function <CODE>rfftw_create_plan</CODE> creates a plan, which is a data
875
structure containing all the information that <CODE>rfftw</CODE> needs in
876
order to compute the 1D real Fourier transform. You can create as many
877
plans as you need, but only one plan for a given array size is required
878
(a plan can be reused many times).
879
 
880
 
881
<P>
882
<CODE>rfftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
883
some reason, the plan can't be created.  In the default installation,
884
this cannot happen, but it is possible to configure RFFTW in such a way
885
that some input sizes are forbidden, and RFFTW cannot create a plan.
886
 
887
 
888
<P>
889
The <CODE>rfftw_create_plan_specific</CODE> variant takes as additional
890
arguments specific input/output arrays and their strides.  For the last
891
four arguments, you should pass the arrays and strides that you will
892
eventually be passing to <CODE>rfftw</CODE>.  The resulting plans will be
893
optimized for those arrays and strides, although they may be used on
894
other arrays as well.  Note: the contents of the in and out arrays are
895
<EM>destroyed</EM> by the specific planner (the initial contents are
896
ignored, so the arrays need not have been initialized).
897
See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans.
898
 
899
 
900
 
901
<H4>Arguments</H4>
902
 
903
<UL>
904
<LI>
905
 
906
<CODE>n</CODE> is the size of the transform.  It can be
907
 any positive integer.
908
 
909
 
910
<UL>
911
<LI>
912
 
913
RFFTW is best at handling sizes of the form
914
2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
915
        11<SUP>e</SUP> 13<SUP>f</SUP>,
916
where e+f is either 0 or
917
1, and the other exponents are arbitrary.  Other sizes are
918
computed by means of a slow, general-purpose routine (reducing to
919
O(n<sup>2</sup>)
920
performance for prime sizes).  (It is possible to customize RFFTW for
921
different array sizes.  See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for more
922
information.)  Transforms whose sizes are powers of 2 are
923
especially fast.
924
</UL>
925
 
926
<LI>
927
 
928
<CODE>dir</CODE> is the direction of the desired transform, either
929
<CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>,
930
corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>,
931
respectively.
932
<A NAME="IDX152"></A>
933
<A NAME="IDX153"></A>
934
 
935
<LI>
936
 
937
<A NAME="IDX154"></A>
938
<CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:
939
 
940
<UL>
941
<LI>
942
 
943
<CODE>FFTW_MEASURE</CODE>: this flag tells RFFTW to find the optimal plan by
944
actually <EM>computing</EM> several FFTs and measuring their
945
execution time.  Depending on the installation, this can take some
946
time.
947
 
948
<LI>
949
 
950
<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
951
plan (for a RISC processor with many registers).  If neither
952
<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
953
<CODE>FFTW_ESTIMATE</CODE>.
954
 
955
<LI>
956
 
957
<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
958
  and output arrays will be distinct (this is the default).
959
 
960
<LI>
961
 
962
<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output
963
in the input array.  The algorithm used is not necessarily in place:
964
RFFTW is able to compute true in-place transforms only for small values
965
of <CODE>n</CODE>.  If RFFTW is not able to compute the transform in-place, it
966
will allocate a temporary array (unless you provide one yourself),
967
compute the transform out of place, and copy the result back.
968
<EM>Warning: This option changes the meaning of some parameters of
969
<CODE>rfftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>).
970
 
971
The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
972
 
973
<LI>
974
 
975
<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
976
in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
977
This can greatly speed the creation of plans, especially with the
978
<CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take
979
advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past
980
measurements) than the estimation heuristic would normally
981
generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
982
will also be generated if the current transform size is not completely
983
understood by existing <CODE>wisdom</CODE>.
984
 
985
</UL>
986
 
987
<LI>
988
 
989
<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for
990
<CODE>rfftw_create_plan_specific</CODE>): see corresponding arguments in the
991
description of <CODE>rfftw</CODE>.  (See Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>.)  In particular, the <CODE>out</CODE> and
992
<CODE>ostride</CODE> parameters have the same special meaning for
993
<CODE>FFTW_IN_PLACE</CODE> transforms as they have for <CODE>rfftw</CODE>.
994
 
995
</UL>
996
 
997
 
998
 
999
<H3><A NAME="SEC31">Computing the Real One-dimensional Transform</A></H3>
1000
 
1001
 
1002
<PRE>
1003
#include &#60;rfftw.h&#62;
1004
 
1005
void rfftw(rfftw_plan plan, int howmany,
1006
           fftw_real *in, int istride, int idist,
1007
           fftw_real *out, int ostride, int odist);
1008
 
1009
void rfftw_one(rfftw_plan plan, fftw_real *in, fftw_real *out);
1010
</PRE>
1011
 
1012
<P>
1013
<A NAME="IDX155"></A>
1014
<A NAME="IDX156"></A>
1015
 
1016
 
1017
<P>
1018
The function <CODE>rfftw</CODE> computes the Real One-dimensional Fourier
1019
Transform, using a plan created by <CODE>rfftw_create_plan</CODE>
1020
(see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>).  The function <CODE>rfftw_one</CODE> provides a simplified
1021
interface for the common case of single input array of stride 1.
1022
<A NAME="IDX157"></A>
1023
 
1024
 
1025
<P>
1026
<EM>Important:</EM> When invoked for an out-of-place,
1027
<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform, the input array is overwritten
1028
with scratch values by these routines.  The input array is not modified
1029
for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms.
1030
 
1031
 
1032
 
1033
<H4>Arguments</H4>
1034
 
1035
<UL>
1036
<LI>
1037
 
1038
<CODE>plan</CODE> is the plan created by <CODE>rfftw_create_plan</CODE>
1039
(see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>).
1040
 
1041
<LI>
1042
 
1043
<CODE>howmany</CODE> is the number of transforms <CODE>rfftw</CODE> will compute.
1044
It is faster to tell RFFTW to compute many transforms, instead of
1045
simply calling <CODE>rfftw</CODE> many times.
1046
 
1047
<LI>
1048
 
1049
<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
1050
There are two cases.  If the <CODE>plan</CODE> defines a
1051
<CODE>FFTW_REAL_TO_COMPLEX</CODE> transform, <CODE>in</CODE> is a real array.
1052
Otherwise, for <CODE>FFTW_COMPLEX_TO_REAL</CODE> transforms, <CODE>in</CODE> is a
1053
halfcomplex array <EM>whose contents will be destroyed</EM>.
1054
 
1055
<LI>
1056
 
1057
<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
1058
array(s), and have the same meaning as the corresponding parameters for
1059
the input array.
1060
 
1061
 
1062
<UL>
1063
<LI><EM>In-place transforms</EM>:
1064
 
1065
If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and
1066
<CODE>odist</CODE> are always ignored.  If <CODE>out</CODE> is <CODE>NULL</CODE>,
1067
<CODE>out</CODE> is ignored, too.  Otherwise, <CODE>out</CODE> is interpreted as a
1068
pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as
1069
temporary space to perform the in-place computation.  <CODE>out</CODE> is used
1070
as scratch space and its contents destroyed.  In this case, <CODE>out</CODE>
1071
must be an ordinary array whose elements are contiguous in memory (no
1072
striding).
1073
</UL>
1074
 
1075
</UL>
1076
 
1077
<P>
1078
The function <CODE>rfftw_one</CODE> transforms a single, contiguous input array
1079
to a contiguous output array.  By definition, the call
1080
 
1081
<PRE>
1082
rfftw_one(plan, in, out)
1083
</PRE>
1084
 
1085
<P>
1086
is equivalent to
1087
 
1088
<PRE>
1089
rfftw(plan, 1, in, 1, 1, out, 1, 1)
1090
</PRE>
1091
 
1092
 
1093
 
1094
<H3><A NAME="SEC32">Destroying a Real One-dimensional Plan</A></H3>
1095
 
1096
 
1097
<PRE>
1098
#include &#60;rfftw.h&#62;
1099
 
1100
void rfftw_destroy_plan(rfftw_plan plan);
1101
</PRE>
1102
 
1103
<P>
1104
<A NAME="IDX158"></A>
1105
 
1106
 
1107
<P>
1108
The function <CODE>rfftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and
1109
releases all the memory associated with it.  After destruction, a plan
1110
is no longer valid.
1111
 
1112
 
1113
 
1114
 
1115
<H3><A NAME="SEC33">What RFFTW Really Computes</A></H3>
1116
<P>
1117
<A NAME="IDX159"></A>
1118
In this section, we define precisely what RFFTW computes.
1119
 
1120
 
1121
<P>
1122
The real to complex (<CODE>FFTW_REAL_TO_COMPLEX</CODE>) transform of a real
1123
array X of size n computes an hermitian array Y,
1124
where
1125
<center><IMG SRC="equation-1.gif" ALIGN="top"></center>
1126
(That Y is a hermitian array is not intended to be obvious,
1127
although the proof is easy.)  The hermitian array Y is stored in
1128
halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>).  Currently, RFFTW provides no
1129
way to compute a real to complex transform with a positive sign in the
1130
exponent.
1131
 
1132
 
1133
<P>
1134
The complex to real (<CODE>FFTW_COMPLEX_TO_REAL</CODE>) transform of a hermitian
1135
array X of size n computes a real array Y, where
1136
<center><IMG SRC="equation-2.gif" ALIGN="top"></center>
1137
(That Y is a real array is not intended to be obvious, although
1138
the proof is easy.)  The hermitian input array X is stored in
1139
halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>).  Currently, RFFTW provides no
1140
way to compute a complex to real transform with a negative sign in the
1141
exponent.
1142
 
1143
 
1144
<P>
1145
<A NAME="IDX160"></A>
1146
Like FFTW, RFFTW computes an unnormalized transform.  In other words,
1147
applying the real to complex (forward) and then the complex to real
1148
(backward) transform will multiply the input by n.
1149
 
1150
 
1151
 
1152
 
1153
<H2><A NAME="SEC34">Real Multi-dimensional Transforms Reference</A></H2>
1154
<P>
1155
<A NAME="IDX161"></A>
1156
<A NAME="IDX162"></A>
1157
 
1158
 
1159
<P>
1160
The multi-dimensional real routines are generally prefixed with
1161
<CODE>rfftwnd_</CODE>.  Programs using RFFTWND should be linked with
1162
<CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with the FFTW, RFFTW, and
1163
standard math libraries in general.
1164
<A NAME="IDX163"></A>
1165
 
1166
 
1167
 
1168
 
1169
<H3><A NAME="SEC35">Plan Creation for Real Multi-dimensional Transforms</A></H3>
1170
 
1171
 
1172
<PRE>
1173
#include &#60;rfftw.h&#62;
1174
 
1175
rfftwnd_plan rfftwnd_create_plan(int rank, const int *n,
1176
                                 fftw_direction dir, int flags);
1177
 
1178
rfftwnd_plan rfftw2d_create_plan(int nx, int ny,
1179
                                 fftw_direction dir, int flags);
1180
 
1181
rfftwnd_plan rfftw3d_create_plan(int nx, int ny, int nz,
1182
                                 fftw_direction dir, int flags);
1183
</PRE>
1184
 
1185
<P>
1186
<A NAME="IDX164"></A>
1187
<A NAME="IDX165"></A>
1188
<A NAME="IDX166"></A>
1189
<A NAME="IDX167"></A>
1190
<A NAME="IDX168"></A>
1191
 
1192
 
1193
<P>
1194
The function <CODE>rfftwnd_create_plan</CODE> creates a plan, which is a data
1195
structure containing all the information that <CODE>rfftwnd</CODE> needs in
1196
order to compute a multi-dimensional real Fourier transform.  You can
1197
create as many plans as you need, but only one plan for a given array
1198
size is required (a plan can be reused many times).  The functions
1199
<CODE>rfftw2d_create_plan</CODE> and <CODE>rfftw3d_create_plan</CODE> are optional,
1200
alternative interfaces to <CODE>rfftwnd_create_plan</CODE> for two and three
1201
dimensions, respectively.
1202
 
1203
 
1204
<P>
1205
<CODE>rfftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
1206
some reason, the plan can't be created.  This can happen if the
1207
arguments are invalid in some way (e.g. if <CODE>rank</CODE> &#60; 0).
1208
 
1209
 
1210
 
1211
<H4>Arguments</H4>
1212
 
1213
<UL>
1214
<LI>
1215
 
1216
<CODE>rank</CODE> is the dimensionality of the arrays to be transformed.  It
1217
can be any non-negative integer.
1218
 
1219
<LI>
1220
 
1221
<CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the
1222
size of each dimension of the arrays to be transformed.  Note that these
1223
are always the dimensions of the <EM>real</EM> arrays; the complex arrays
1224
have different dimensions (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>).  These sizes, which must be positive
1225
integers, correspond to the dimensions of row-major
1226
arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose indices
1227
vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for
1228
more information.)
1229
 
1230
<UL>
1231
<LI>
1232
 
1233
See Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>,
1234
for more information regarding optimal array sizes.
1235
</UL>
1236
 
1237
<LI>
1238
 
1239
<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>rfftw2d_create_plan</CODE> are positive
1240
integers specifying the dimensions of the rank 2 array to be
1241
transformed. i.e. they specify that the transform will operate on
1242
<CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number
1243
of rows and <CODE>ny</CODE> is the number of columns.
1244
 
1245
<LI>
1246
 
1247
<CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>rfftw3d_create_plan</CODE> are
1248
positive integers specifying the dimensions of the rank 3 array to be
1249
transformed. i.e. they specify that the transform will operate on
1250
<CODE>nx x ny x nz</CODE> arrays in row-major order.
1251
 
1252
<LI>
1253
 
1254
<CODE>dir</CODE> is the direction of the desired transform, either
1255
<CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>,
1256
corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>,
1257
respectively.
1258
 
1259
<LI>
1260
 
1261
<A NAME="IDX169"></A>
1262
<CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:
1263
 
1264
<UL>
1265
<LI>
1266
 
1267
<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
1268
actually <EM>computing</EM> several FFTs and measuring their execution
1269
time.
1270
 
1271
<LI>
1272
 
1273
<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
1274
plan (for a RISC processor with many registers).  If neither
1275
<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
1276
<CODE>FFTW_ESTIMATE</CODE>.
1277
 
1278
<LI>
1279
 
1280
<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
1281
  and output arrays will be distinct (this is the default).
1282
 
1283
<LI>
1284
 
1285
<A NAME="IDX170"></A>
1286
<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform
1287
the transform in-place.  (Unlike the one-dimensional transform, this
1288
"really" performs the transform in-place.) Note that, if you want to
1289
perform in-place transforms, you <EM>must</EM> use a plan created with
1290
this option.  The use of this option has important implications for the
1291
size of the input/output array (see Section <A HREF="fftw_3.html#SEC36">Computing the Real Multi-dimensional Transform</A>).
1292
 
1293
The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.
1294
 
1295
<LI>
1296
 
1297
<A NAME="IDX171"></A>
1298
<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
1299
in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)  This can greatly
1300
speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE>
1301
option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of
1302
<CODE>wisdom</CODE> to produce a more optimal plan (based on past
1303
measurements) than the estimation heuristic would normally
1304
generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
1305
will also be generated if the current transform size is not completely
1306
understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE>
1307
is shared between one-dimensional and multi-dimensional transforms.
1308
 
1309
</UL>
1310
 
1311
</UL>
1312
 
1313
 
1314
 
1315
<H3><A NAME="SEC36">Computing the Real Multi-dimensional Transform</A></H3>
1316
 
1317
 
1318
<PRE>
1319
#include &#60;rfftw.h&#62;
1320
 
1321
void rfftwnd_real_to_complex(rfftwnd_plan plan, int howmany,
1322
                             fftw_real *in, int istride, int idist,
1323
                             fftw_complex *out, int ostride, int odist);
1324
void rfftwnd_complex_to_real(rfftwnd_plan plan, int howmany,
1325
                             fftw_complex *in, int istride, int idist,
1326
                             fftw_real *out, int ostride, int odist);
1327
 
1328
void rfftwnd_one_real_to_complex(rfftwnd_plan p, fftw_real *in,
1329
                                 fftw_complex *out);
1330
void rfftwnd_one_complex_to_real(rfftwnd_plan p, fftw_complex *in,
1331
                                 fftw_real *out);
1332
</PRE>
1333
 
1334
<P>
1335
<A NAME="IDX172"></A>
1336
<A NAME="IDX173"></A>
1337
<A NAME="IDX174"></A>
1338
<A NAME="IDX175"></A>
1339
 
1340
 
1341
<P>
1342
These functions compute the real multi-dimensional Fourier Transform,
1343
using a plan created by <CODE>rfftwnd_create_plan</CODE>
1344
(see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
1345
the array to be transformed.)  The <SAMP>`<CODE>rfftwnd_one_</CODE>'</SAMP> functions
1346
provide a simplified interface for the common case of single input array
1347
of stride 1.  Unlike other transform routines in FFTW, we here use
1348
separate functions for the two directions of the transform in order to
1349
correctly express the datatypes of the parameters.
1350
 
1351
 
1352
<P>
1353
<EM>Important:</EM> When invoked for an out-of-place,
1354
<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform with <CODE>rank &#62; 1</CODE>, the input
1355
array is overwritten with scratch values by these routines.  The input
1356
array is not modified for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms or for
1357
<CODE>FFTW_COMPLEX_TO_REAL</CODE> with <CODE>rank == 1</CODE>.
1358
 
1359
 
1360
 
1361
<H4>Arguments</H4>
1362
 
1363
<UL>
1364
<LI>
1365
 
1366
<CODE>plan</CODE> is the plan created by <CODE>rfftwnd_create_plan</CODE>.
1367
(see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it
1368
could also have been created by <CODE>rfftw2d_create_plan</CODE> or
1369
<CODE>rfftw3d_create_plan</CODE>, respectively.
1370
 
1371
<CODE>FFTW_REAL_TO_COMPLEX</CODE> plans must be used with the
1372
<SAMP>`<CODE>real_to_complex</CODE>'</SAMP> functions, and <CODE>FFTW_COMPLEX_TO_REAL</CODE>
1373
plans must be used with the <SAMP>`<CODE>complex_to_real</CODE>'</SAMP> functions.  It
1374
is an error to mismatch the plan direction and the transform function.
1375
 
1376
<LI>
1377
 
1378
<CODE>howmany</CODE> is the number of transforms to be computed.
1379
 
1380
<LI>
1381
 
1382
<A NAME="IDX176"></A>
1383
<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
1384
There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
1385
<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
1386
up to <CODE>in + (howmany - 1) * idist</CODE>.  Each input array is stored in
1387
row-major format (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), and is not
1388
necessarily contiguous in memory.  Specifically, <CODE>in[0]</CODE> is the
1389
first element of the first array, <CODE>in[istride]</CODE> is the second
1390
element of the first array, and so on.  In general, the <CODE>i</CODE>-th
1391
element of the <CODE>j</CODE>-th input array will be in position <CODE>in[i *
1392
istride + j * idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into
1393
the row-major format for the multi-dimensional array, rather than an
1394
index in any particular dimension.
1395
 
1396
The dimensions of the arrays are different for real and complex data,
1397
and are discussed in more detail below (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>).
1398
 
1399
 
1400
<UL>
1401
<LI><EM>In-place transforms</EM>:
1402
 
1403
For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is
1404
computed in-place--the output is returned in the <CODE>in</CODE> array.  The
1405
meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters in this case is
1406
subtle and is discussed below (see Section <A HREF="fftw_3.html#SEC38">Strides in In-place RFFTWND</A>).
1407
</UL>
1408
 
1409
<LI>
1410
 
1411
<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
1412
array(s).  The format is the same as that for the input array.  See
1413
below for a discussion of the dimensions of the output array for real
1414
and complex data.
1415
 
1416
 
1417
<UL>
1418
<LI><EM>In-place transforms</EM>:
1419
 
1420
These parameters are ignored for plans created with the
1421
<CODE>FFTW_IN_PLACE</CODE> option.
1422
</UL>
1423
 
1424
</UL>
1425
 
1426
<P>
1427
The function <CODE>rfftwnd_one</CODE> transforms a single, contiguous input
1428
array to a contiguous output array.  By definition, the call
1429
 
1430
<PRE>
1431
rfftwnd_one_...(plan, in, out)
1432
</PRE>
1433
 
1434
<P>
1435
is equivalent to
1436
 
1437
<PRE>
1438
rfftwnd_...(plan, 1, in, 1, 1, out, 1, 1)
1439
</PRE>
1440
 
1441
 
1442
 
1443
<H3><A NAME="SEC37">Array Dimensions for Real Multi-dimensional Transforms</A></H3>
1444
 
1445
<P>
1446
<A NAME="IDX177"></A>
1447
The output of a multi-dimensional transform of real data contains
1448
symmetries that, in principle, make half of the outputs redundant
1449
(see Section <A HREF="fftw_3.html#SEC40">What RFFTWND Really Computes</A>).  In practice, it is not
1450
possible to entirely realize these savings in an efficient and
1451
understandable format.  Instead, the output of the rfftwnd transforms is
1452
<EM>slightly</EM> over half of the output of the corresponding complex
1453
transform.  We do not "pack" the data in any way, but store it as an
1454
ordinary array of <CODE>fftw_complex</CODE> values.  In fact, this data is
1455
simply a subsection of what would be the array in the corresponding
1456
complex transform.
1457
 
1458
 
1459
<P>
1460
Specifically, for a real transform of dimensions
1461
n<sub>1</sub> x n<sub>2</sub> x ... x n<sub>d</sub>,
1462
the complex data is an
1463
n<sub>1</sub> x n<sub>2</sub> x ... x (n<sub>d</sub>/2+1)
1464
array of <CODE>fftw_complex</CODE> values in row-major order (with the
1465
division rounded down).  That is, we only store the lower half (plus one
1466
element) of the last dimension of the data from the ordinary complex
1467
transform.  (We could have instead taken half of any other dimension,
1468
but implementation turns out to be simpler if the last, contiguous,
1469
dimension is used.)
1470
 
1471
 
1472
<P>
1473
<A NAME="IDX178"></A>
1474
<A NAME="IDX179"></A>
1475
Since the complex data is slightly larger than the real data, some
1476
complications arise for in-place transforms.  In this case, the final
1477
dimension of the real data must be padded with extra values to
1478
accommodate the size of the complex data--two extra if the last
1479
dimension is even and one if it is odd.  That is, the last dimension of
1480
the real data must physically contain
1481
2 * (n<sub>d</sub>/2+1)
1482
<CODE>fftw_real</CODE> values (exactly enough to hold the complex data).
1483
This physical array size does not, however, change the <EM>logical</EM>
1484
array size--only
1485
n<sub>d</sub>
1486
values are actually stored in the last dimension, and
1487
n<sub>d</sub>
1488
is the last dimension passed to <CODE>rfftwnd_create_plan</CODE>.
1489
 
1490
 
1491
 
1492
 
1493
<H3><A NAME="SEC38">Strides in In-place RFFTWND</A></H3>
1494
 
1495
<P>
1496
<A NAME="IDX180"></A>
1497
<A NAME="IDX181"></A>
1498
The fact that the input and output datatypes are different for rfftwnd
1499
complicates the meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters
1500
of in-place transforms--are they in units of <CODE>fftw_real</CODE> or
1501
<CODE>fftw_complex</CODE> elements?  When reading the input, they are
1502
interpreted in units of the datatype of the input data.  When writing
1503
the output, the <CODE>istride</CODE> and <CODE>idist</CODE> are translated to the
1504
output datatype's "units" in one of two ways, corresponding to the two
1505
most common situations in which <CODE>stride</CODE> and <CODE>dist</CODE> parameters
1506
are useful.  Below, we refer to these "translated" parameters as
1507
<CODE>ostride_t</CODE> and <CODE>odist_t</CODE>.  (Note that these are computed
1508
internally by rfftwnd; the actual <CODE>ostride</CODE> and <CODE>odist</CODE>
1509
parameters are ignored for in-place transforms.)
1510
 
1511
 
1512
<P>
1513
First, there is the case where you are transforming a number of
1514
contiguous arrays located one after another in memory.  In this
1515
situation, <CODE>istride</CODE> is <CODE>1</CODE> and <CODE>idist</CODE> is the product of
1516
the physical dimensions of the array.  <CODE>ostride_t</CODE> and
1517
<CODE>odist_t</CODE> are then chosen so that the output arrays are contiguous
1518
and lie on top of the input arrays.  <CODE>ostride_t</CODE> is therefore
1519
<CODE>1</CODE>.  For a real-to-complex transform, <CODE>odist_t</CODE> is
1520
<CODE>idist/2</CODE>; for a complex-to-real transform, <CODE>odist_t</CODE> is
1521
<CODE>idist*2</CODE>.
1522
 
1523
 
1524
<P>
1525
The second case is when you have an array in which each element has
1526
<CODE>nc</CODE> components (e.g. a structure with <CODE>nc</CODE> numeric fields),
1527
and you want to transform all of the components at once.  Here,
1528
<CODE>istride</CODE> is <CODE>nc</CODE> and <CODE>idist</CODE> is <CODE>1</CODE>.  For this
1529
case, it is natural to want the output to also have <CODE>nc</CODE>
1530
consecutive components, now of the output data type; this is exactly
1531
what rfftwnd does.  Specifically, it uses an <CODE>ostride_t</CODE> equal to
1532
<CODE>istride</CODE>, and an <CODE>odist_t</CODE> of <CODE>1</CODE>.  (Astute readers will
1533
realize that some extra buffer space is required in order to perform
1534
such a transform; this is handled automatically by rfftwnd.)
1535
 
1536
 
1537
<P>
1538
The general rule is as follows.  <CODE>ostride_t</CODE> equals <CODE>istride</CODE>.
1539
If <CODE>idist</CODE> is <CODE>1</CODE>, then <CODE>odist_t</CODE> is <CODE>1</CODE>.
1540
Otherwise, for a real-to-complex transform <CODE>odist_t</CODE> is
1541
<CODE>idist/2</CODE> and for a complex-to-real transform <CODE>odist_t</CODE> is
1542
<CODE>idist*2</CODE>.
1543
 
1544
 
1545
 
1546
 
1547
<H3><A NAME="SEC39">Destroying a Multi-dimensional Plan</A></H3>
1548
 
1549
 
1550
<PRE>
1551
#include &#60;rfftw.h&#62;
1552
 
1553
void rfftwnd_destroy_plan(rfftwnd_plan plan);
1554
</PRE>
1555
 
1556
<P>
1557
<A NAME="IDX182"></A>
1558
 
1559
 
1560
<P>
1561
The function <CODE>rfftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE>
1562
and releases all the memory associated with it.  After destruction,
1563
a plan is no longer valid.
1564
 
1565
 
1566
 
1567
 
1568
<H3><A NAME="SEC40">What RFFTWND Really Computes</A></H3>
1569
<P>
1570
<A NAME="IDX183"></A>
1571
 
1572
 
1573
<P>
1574
The conventions that we follow for the real multi-dimensional transform
1575
are analogous to those for the complex multi-dimensional transform. In
1576
particular, the forward transform has a negative sign in the exponent
1577
and neither the forward nor the backward transforms will perform any
1578
normalization.  Computing the backward transform of the forward
1579
transform will multiply the array by the product of its dimensions (that
1580
is, the logical dimensions of the real data).  The forward transform is
1581
real-to-complex and the backward transform is complex-to-real.
1582
 
1583
 
1584
<P>
1585
<A NAME="IDX184"></A>
1586
<A NAME="IDX185"></A>
1587
The Gods forbade using HTML to display mathematical formulas.  Please
1588
see the TeX or Postscript version of this manual for the proper
1589
definition of the n-dimensional real Fourier transform that RFFTW
1590
uses.  For completeness, we include a bitmap of the TeX output below:
1591
<P><center><IMG SRC="equation-4.gif" ALIGN="top"></center>
1592
 
1593
 
1594
 
1595
 
1596
<H2><A NAME="SEC41">Wisdom Reference</A></H2>
1597
 
1598
<P>
1599
<A NAME="IDX186"></A>
1600
 
1601
 
1602
<H3><A NAME="SEC42">Exporting Wisdom</A></H3>
1603
 
1604
 
1605
<PRE>
1606
#include &#60;fftw.h&#62;
1607
 
1608
void fftw_export_wisdom(void (*emitter)(char c, void *), void *data);
1609
void fftw_export_wisdom_to_file(FILE *output_file);
1610
char *fftw_export_wisdom_to_string(void);
1611
</PRE>
1612
 
1613
<P>
1614
<A NAME="IDX187"></A>
1615
<A NAME="IDX188"></A>
1616
<A NAME="IDX189"></A>
1617
 
1618
 
1619
<P>
1620
These functions allow you to export all currently accumulated
1621
<CODE>wisdom</CODE> in a form from which it can be later imported and
1622
restored, even during a separate run of the program. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)  The current store of <CODE>wisdom</CODE> is not
1623
affected by calling any of these routines.
1624
 
1625
 
1626
<P>
1627
<CODE>fftw_export_wisdom</CODE> exports the <CODE>wisdom</CODE> to any output
1628
medium, as specified by the callback function
1629
<CODE>emitter</CODE>. <CODE>emitter</CODE> is a <CODE>putc</CODE>-like function that
1630
writes the character <CODE>c</CODE> to some output; its second parameter is
1631
the <CODE>data</CODE> pointer passed to <CODE>fftw_export_wisdom</CODE>.  For
1632
convenience, the following two "wrapper" routines are provided:
1633
 
1634
 
1635
<P>
1636
<CODE>fftw_export_wisdom_to_file</CODE> writes the <CODE>wisdom</CODE> to the
1637
current position in <CODE>output_file</CODE>, which should be open with write
1638
permission.  Upon exit, the file remains open and is positioned at the
1639
end of the <CODE>wisdom</CODE> data.
1640
 
1641
 
1642
<P>
1643
<CODE>fftw_export_wisdom_to_string</CODE> returns a pointer to a
1644
<CODE>NULL</CODE>-terminated string holding the <CODE>wisdom</CODE> data. This
1645
string is dynamically allocated, and it is the responsibility of the
1646
caller to deallocate it with <CODE>fftw_free</CODE> when it is no longer
1647
needed.
1648
 
1649
 
1650
<P>
1651
All of these routines export the wisdom in the same format, which we
1652
will not document here except to say that it is LISP-like ASCII text
1653
that is insensitive to white space.
1654
 
1655
 
1656
 
1657
 
1658
<H3><A NAME="SEC43">Importing Wisdom</A></H3>
1659
 
1660
 
1661
<PRE>
1662
#include &#60;fftw.h&#62;
1663
 
1664
fftw_status fftw_import_wisdom(int (*get_input)(void *), void *data);
1665
fftw_status fftw_import_wisdom_from_file(FILE *input_file);
1666
fftw_status fftw_import_wisdom_from_string(const char *input_string);
1667
</PRE>
1668
 
1669
<P>
1670
<A NAME="IDX190"></A>
1671
<A NAME="IDX191"></A>
1672
<A NAME="IDX192"></A>
1673
 
1674
 
1675
<P>
1676
These functions import <CODE>wisdom</CODE> into a program from data stored by
1677
the <CODE>fftw_export_wisdom</CODE> functions above. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)
1678
The imported <CODE>wisdom</CODE> supplements rather than replaces any
1679
<CODE>wisdom</CODE> already accumulated by the running program (except when
1680
there is conflicting <CODE>wisdom</CODE>, in which case the existing wisdom is
1681
replaced).
1682
 
1683
 
1684
<P>
1685
<CODE>fftw_import_wisdom</CODE> imports <CODE>wisdom</CODE> from any input medium,
1686
as specified by the callback function <CODE>get_input</CODE>. <CODE>get_input</CODE>
1687
is a <CODE>getc</CODE>-like function that returns the next character in the
1688
input; its parameter is the <CODE>data</CODE> pointer passed to
1689
<CODE>fftw_import_wisdom</CODE>. If the end of the input data is reached
1690
(which should never happen for valid data), it may return either
1691
<CODE>NULL</CODE> (ASCII 0) or <CODE>EOF</CODE> (as defined in <CODE>&#60;stdio.h&#62;</CODE>).
1692
For convenience, the following two "wrapper" routines are provided:
1693
 
1694
 
1695
<P>
1696
<CODE>fftw_import_wisdom_from_file</CODE> reads <CODE>wisdom</CODE> from the
1697
current position in <CODE>input_file</CODE>, which should be open with read
1698
permission.  Upon exit, the file remains open and is positioned at the
1699
end of the <CODE>wisdom</CODE> data.
1700
 
1701
 
1702
<P>
1703
<CODE>fftw_import_wisdom_from_string</CODE> reads <CODE>wisdom</CODE> from the
1704
<CODE>NULL</CODE>-terminated string <CODE>input_string</CODE>.
1705
 
1706
 
1707
<P>
1708
The return value of these routines is <CODE>FFTW_SUCCESS</CODE> if the wisdom
1709
was read successfully, and <CODE>FFTW_FAILURE</CODE> otherwise. Note that, in
1710
all of these functions, any data in the input stream past the end of the
1711
<CODE>wisdom</CODE> data is simply ignored (it is not even read if the
1712
<CODE>wisdom</CODE> data is well-formed).
1713
 
1714
 
1715
 
1716
 
1717
<H3><A NAME="SEC44">Forgetting Wisdom</A></H3>
1718
 
1719
 
1720
<PRE>
1721
#include &#60;fftw.h&#62;
1722
 
1723
void fftw_forget_wisdom(void);
1724
</PRE>
1725
 
1726
<P>
1727
<A NAME="IDX193"></A>
1728
 
1729
 
1730
<P>
1731
Calling <CODE>fftw_forget_wisdom</CODE> causes all accumulated <CODE>wisdom</CODE>
1732
to be discarded and its associated memory to be freed. (New
1733
<CODE>wisdom</CODE> can still be gathered subsequently, however.)
1734
 
1735
 
1736
 
1737
 
1738
<H2><A NAME="SEC45">Memory Allocator Reference</A></H2>
1739
 
1740
 
1741
<PRE>
1742
#include &#60;fftw.h&#62;
1743
 
1744
void *(*fftw_malloc_hook) (size_t n);
1745
void (*fftw_free_hook) (void *p);
1746
</PRE>
1747
 
1748
<P>
1749
<A NAME="IDX194"></A>
1750
<A NAME="IDX195"></A>
1751
<A NAME="IDX196"></A>
1752
<A NAME="IDX197"></A>
1753
 
1754
 
1755
<P>
1756
Whenever it has to allocate and release memory, FFTW ordinarily calls
1757
<CODE>malloc</CODE> and <CODE>free</CODE>.  
1758
If <CODE>malloc</CODE> fails, FFTW prints an error message and exits.  This
1759
behavior may be undesirable in some applications. Also, special
1760
memory-handling functions may be necessary in certain
1761
environments. Consequently, FFTW provides means by which you can install
1762
your own memory allocator and take whatever error-correcting action you
1763
find appropriate.  The variables <CODE>fftw_malloc_hook</CODE> and
1764
<CODE>fftw_free_hook</CODE> are pointers to functions, and they are normally
1765
<CODE>NULL</CODE>.  If you set those variables to point to other functions,
1766
then FFTW will use your routines instead of <CODE>malloc</CODE> and
1767
<CODE>free</CODE>.  <CODE>fftw_malloc_hook</CODE> must point to a <CODE>malloc</CODE>-like
1768
function, and <CODE>fftw_free_hook</CODE> must point to a <CODE>free</CODE>-like
1769
function.
1770
 
1771
 
1772
 
1773
 
1774
<H2><A NAME="SEC46">Thread safety</A></H2>
1775
 
1776
<P>
1777
<A NAME="IDX198"></A>
1778
<A NAME="IDX199"></A>
1779
Users writing multi-threaded programs must concern themselves with the
1780
<EM>thread safety</EM> of the libraries they use--that is, whether it is
1781
safe to call routines in parallel from multiple threads.  FFTW can be
1782
used in such an environment, but some care must be taken because certain
1783
parts of FFTW use private global variables to share data between calls.
1784
In particular, the plan-creation functions share trigonometric tables
1785
and accumulated <CODE>wisdom</CODE>.  (Users should note that these comments
1786
only apply to programs using shared-memory threads.  Parallelism using
1787
MPI or forked processes involves a separate address-space and global
1788
variables for each process, and is not susceptible to problems of this
1789
sort.)
1790
 
1791
 
1792
<P>
1793
The central restriction of FFTW is that it is not safe to create
1794
multiple plans in parallel.  You must either create all of your plans
1795
from a single thread, or instead use a semaphore, mutex, or other
1796
mechanism to ensure that different threads don't attempt to create plans
1797
at the same time.  The same restriction also holds for destruction of
1798
plans and importing/forgetting <CODE>wisdom</CODE>.  Once created, a plan may
1799
safely be used in any thread.
1800
 
1801
 
1802
<P>
1803
The actual transform routines in FFTW (<CODE>fftw_one</CODE>, etcetera) are
1804
re-entrant and thread-safe, so it is fine to call them simultaneously
1805
from multiple threads.  Another question arises, however--is it safe to
1806
use the <EM>same plan</EM> for multiple transforms in parallel?  (It would
1807
be unsafe if, for example, the plan were modified in some way by the
1808
transform.)  We address this question by defining an additional planner
1809
flag, <CODE>FFTW_THREADSAFE</CODE>.
1810
<A NAME="IDX200"></A>
1811
When included in the flags for any of the plan-creation routines,
1812
<CODE>FFTW_THREADSAFE</CODE> guarantees that the resulting plan will be
1813
read-only and safe to use in parallel by multiple threads.
1814
 
1815
 
1816
<P><HR><P>
1817
Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>.
1818
</BODY>
1819
</HTML>