Subversion Repositories shark

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 pj 1
/*
2
 * Copyright (c) 1997-1999 Massachusetts Institute of Technology
3
 *
4
 * This program is free software; you can redistribute it and/or modify
5
 * it under the terms of the GNU General Public License as published by
6
 * the Free Software Foundation; either version 2 of the License, or
7
 * (at your option) any later version.
8
 *
9
 * This program is distributed in the hope that it will be useful,
10
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 * GNU General Public License for more details.
13
 *
14
 * You should have received a copy of the GNU General Public License
15
 * along with this program; if not, write to the Free Software
16
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
 *
18
 */
19
 
20
/*
21
 * fftw_test.c : test program for complex-complex transforms
22
 */
23
 
24
/* $Id: fftw_tes.c,v 1.1.1.1 2002-03-29 14:12:59 pj Exp $ */
25
#include <fftw-int.h>
26
#include <stdlib.h>
27
#include <stdio.h>
28
#include <string.h>
29
#include <math.h>
30
#include <time.h>
31
 
32
#include "test_main.h"
33
 
34
char fftw_prefix[] = "fftw";
35
 
36
void test_ergun(int n, fftw_direction dir, fftw_plan plan);
37
extern void (*fftw_plan_hook)(fftw_plan plan);
38
 
39
/*************************************************
40
 * Speed tests
41
 *************************************************/
42
 
43
void zero_arr(int n, fftw_complex *a)
44
{
45
     int i;
46
     for (i = 0; i < n; ++i)
47
          c_re(a[i]) = c_im(a[i]) = 0.0;
48
}
49
 
50
void test_speed_aux(int n, fftw_direction dir, int flags, int specific)
51
{
52
     fftw_complex *in, *out;
53
     fftw_plan plan;
54
     double t;
55
     fftw_time begin, end;
56
 
57
     in = (fftw_complex *) fftw_malloc(n * howmany_fields
58
                                       * sizeof(fftw_complex));
59
     out = (fftw_complex *) fftw_malloc(n * howmany_fields
60
                                        * sizeof(fftw_complex));
61
 
62
     if (specific) {
63
          begin = fftw_get_time();
64
          plan = fftw_create_plan_specific(n, dir,
65
                                        speed_flag | flags | wisdom_flag,
66
                                           in, howmany_fields,
67
                                           out, howmany_fields);
68
          end = fftw_get_time();
69
     } else {
70
          begin = fftw_get_time();
71
          plan = fftw_create_plan(n, dir, speed_flag | flags | wisdom_flag);
72
          end = fftw_get_time();
73
     }
74
     CHECK(plan != NULL, "can't create plan");
75
 
76
     t = fftw_time_to_sec(fftw_time_diff(end, begin));
77
     WHEN_VERBOSE(2, printf("time for planner: %f s\n", t));
78
 
79
     WHEN_VERBOSE(2, fftw_print_plan(plan));
80
 
81
     if (paranoid && !(flags & FFTW_IN_PLACE)) {
82
          begin = fftw_get_time();
83
          test_ergun(n, dir, plan);
84
          end = fftw_get_time();
85
          t = fftw_time_to_sec(fftw_time_diff(end, begin));
86
          WHEN_VERBOSE(2, printf("time for validation: %f s\n", t));
87
     }
88
     FFTW_TIME_FFT(fftw(plan, howmany_fields,
89
                        in, howmany_fields, 1, out, howmany_fields, 1),
90
                   in, n * howmany_fields, t);
91
 
92
     fftw_destroy_plan(plan);
93
 
94
     WHEN_VERBOSE(1, printf("time for one fft: %s", smart_sprint_time(t)));
95
     WHEN_VERBOSE(1, printf(" (%s/point)\n", smart_sprint_time(t / n)));
96
     WHEN_VERBOSE(1, printf("\"mflops\" = 5 (n log2 n) / (t in microseconds)"
97
                            " = %f\n", howmany_fields * mflops(t, n)));
98
 
99
     fftw_free(in);
100
     fftw_free(out);
101
 
102
     WHEN_VERBOSE(1, printf("\n"));
103
}
104
 
105
void test_speed_nd_aux(struct size sz,
106
                       fftw_direction dir, int flags, int specific)
107
{
108
     fftw_complex *in;
109
     fftwnd_plan plan;
110
     double t;
111
     fftw_time begin, end;
112
     int i, N;
113
 
114
     /* only bench in-place multi-dim transforms */
115
     flags |= FFTW_IN_PLACE;   
116
 
117
     N = 1;
118
     for (i = 0; i < sz.rank; ++i)
119
          N *= (sz.narray[i]);
120
 
121
     in = (fftw_complex *) fftw_malloc(N * howmany_fields *
122
                                       sizeof(fftw_complex));
123
 
124
     if (specific) {
125
          begin = fftw_get_time();
126
          plan = fftwnd_create_plan_specific(sz.rank, sz.narray, dir,
127
                                        speed_flag | flags | wisdom_flag,
128
                                             in, howmany_fields, 0, 1);
129
     } else {
130
          begin = fftw_get_time();
131
          plan = fftwnd_create_plan(sz.rank, sz.narray,
132
                                  dir, speed_flag | flags | wisdom_flag);
133
     }
134
     end = fftw_get_time();
135
     CHECK(plan != NULL, "can't create plan");
136
 
137
     t = fftw_time_to_sec(fftw_time_diff(end, begin));
138
     WHEN_VERBOSE(2, printf("time for planner: %f s\n", t));
139
 
140
     WHEN_VERBOSE(2, printf("\n"));
141
     WHEN_VERBOSE(2, (fftwnd_print_plan(plan)));
142
     WHEN_VERBOSE(2, printf("\n"));
143
 
144
     FFTW_TIME_FFT(fftwnd(plan, howmany_fields,
145
                          in, howmany_fields, 1, 0, 0, 0),
146
                   in, N * howmany_fields, t);
147
 
148
     fftwnd_destroy_plan(plan);
149
 
150
     WHEN_VERBOSE(1, printf("time for one fft: %s", smart_sprint_time(t)));
151
     WHEN_VERBOSE(1, printf(" (%s/point)\n", smart_sprint_time(t / N)));
152
     WHEN_VERBOSE(1, printf("\"mflops\" = 5 (N log2 N) / (t in microseconds)"
153
                            " = %f\n", howmany_fields * mflops(t, N)));
154
 
155
     fftw_free(in);
156
 
157
     WHEN_VERBOSE(1, printf("\n"));
158
}
159
 
160
/*************************************************
161
 * correctness tests
162
 *************************************************/
163
void fill_random(fftw_complex *a, int n)
164
{
165
     int i;
166
 
167
     /* generate random inputs */
168
     for (i = 0; i < n; ++i) {
169
          c_re(a[i]) = DRAND();
170
          c_im(a[i]) = DRAND();
171
     }
172
}
173
 
174
void array_copy(fftw_complex *out, fftw_complex *in, int n)
175
{
176
     int i;
177
 
178
     for (i = 0; i < n; ++i)
179
          out[i] = in[i];
180
}
181
 
182
/* C = A + B */
183
void array_add(fftw_complex *C, fftw_complex *A, fftw_complex *B, int n)
184
{
185
     int i;
186
 
187
     for (i = 0; i < n; ++i) {
188
          c_re(C[i]) = c_re(A[i]) + c_re(B[i]);
189
          c_im(C[i]) = c_im(A[i]) + c_im(B[i]);
190
     }
191
}
192
 
193
/* C = A - B */
194
void array_sub(fftw_complex *C, fftw_complex *A, fftw_complex *B, int n)
195
{
196
     int i;
197
 
198
     for (i = 0; i < n; ++i) {
199
          c_re(C[i]) = c_re(A[i]) - c_re(B[i]);
200
          c_im(C[i]) = c_im(A[i]) - c_im(B[i]);
201
     }
202
}
203
 
204
/* B = rotate left A */
205
void array_rol(fftw_complex *B, fftw_complex *A,
206
               int n, int n_before, int n_after)
207
{
208
     int i, ib, ia;
209
 
210
     for (ib = 0; ib < n_before; ++ib) {
211
          for (i = 0; i < n - 1; ++i)
212
               for (ia = 0; ia < n_after; ++ia)
213
                    B[(ib * n + i) * n_after + ia] =
214
                        A[(ib * n + i + 1) * n_after + ia];
215
 
216
          for (ia = 0; ia < n_after; ++ia)
217
               B[(ib * n + n - 1) * n_after + ia] = A[ib * n * n_after + ia];
218
     }
219
}
220
 
221
/* A = alpha * A  (in place) */
222
void array_scale(fftw_complex *A, fftw_complex alpha, int n)
223
{
224
     int i;
225
 
226
     for (i = 0; i < n; ++i) {
227
          fftw_complex a = A[i];
228
          c_re(A[i]) = c_re(a) * c_re(alpha) - c_im(a) * c_im(alpha);
229
          c_im(A[i]) = c_re(a) * c_im(alpha) + c_im(a) * c_re(alpha);
230
     }
231
}
232
 
233
void array_compare(fftw_complex *A, fftw_complex *B, int n)
234
{
235
     double d = compute_error_complex(A, 1, B, 1, n);
236
     if (d > TOLERANCE) {
237
          fflush(stdout);
238
          fprintf(stderr, "Found relative error %e\n", d);
239
          fftw_die("failure in Ergun's verification procedure\n");
240
     }
241
}
242
 
243
/*
244
 * guaranteed out-of-place transform.  Does the necessary
245
 * copying if the plan is in-place.
246
 */
247
static void fftw_out_of_place(fftw_plan plan, int n,
248
                              fftw_complex *in, fftw_complex *out)
249
{
250
     if (plan->flags & FFTW_IN_PLACE) {
251
          array_copy(out, in, n);
252
          fftw(plan, 1, out, 1, n, (fftw_complex *)0, 1, n);
253
     } else {
254
          fftw(plan, 1, in, 1, n, out, 1, n);
255
     }
256
}
257
 
258
/*
259
 * Implementation of the FFT tester described in
260
 *
261
 * Funda Ergün. Testing multivariate linear functions: Overcoming the
262
 * generator bottleneck. In Proceedings of the Twenty-Seventh Annual
263
 * ACM Symposium on the Theory of Computing, pages 407-416, Las Vegas,
264
 * Nevada, 29 May--1 June 1995.
265
 */
266
void test_ergun(int n, fftw_direction dir, fftw_plan plan)
267
{
268
     fftw_complex *inA, *inB, *inC, *outA, *outB, *outC;
269
     fftw_complex *tmp;
270
     fftw_complex impulse;
271
     int i;
272
     int rounds = 20;
273
     FFTW_TRIG_REAL twopin = FFTW_K2PI / (FFTW_TRIG_REAL) n;
274
 
275
     inA = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
276
     inB = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
277
     inC = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
278
     outA = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
279
     outB = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
280
     outC = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
281
     tmp = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex));
282
 
283
     WHEN_VERBOSE(2,
284
                  printf("Validating plan, n = %d, dir = %s\n", n,
285
                         dir == FFTW_FORWARD ? "FORWARD" : "BACKWARD"));
286
 
287
     /* test 1: check linearity */
288
     for (i = 0; i < rounds; ++i) {
289
          fftw_complex alpha, beta;
290
          c_re(alpha) = DRAND();
291
          c_im(alpha) = DRAND();
292
          c_re(beta) = DRAND();
293
          c_im(beta) = DRAND();
294
          fill_random(inA, n);
295
          fill_random(inB, n);
296
          fftw_out_of_place(plan, n, inA, outA);
297
          fftw_out_of_place(plan, n, inB, outB);
298
          array_scale(outA, alpha, n);
299
          array_scale(outB, beta, n);
300
          array_add(tmp, outA, outB, n);
301
          array_scale(inA, alpha, n);
302
          array_scale(inB, beta, n);
303
          array_add(inC, inA, inB, n);
304
          fftw_out_of_place(plan, n, inC, outC);
305
          array_compare(outC, tmp, n);
306
     }
307
 
308
     /* test 2: check that the unit impulse is transformed properly */
309
 
310
     c_re(impulse) = 1.0;
311
     c_im(impulse) = 0.0;
312
 
313
     for (i = 0; i < n; ++i) {
314
          /* impulse */
315
          c_re(inA[i]) = 0.0;
316
          c_im(inA[i]) = 0.0;
317
 
318
          /* transform of the impulse */
319
          outA[i] = impulse;
320
     }
321
     inA[0] = impulse;
322
 
323
     for (i = 0; i < rounds; ++i) {
324
          fill_random(inB, n);
325
          array_sub(inC, inA, inB, n);
326
          fftw_out_of_place(plan, n, inB, outB);
327
          fftw_out_of_place(plan, n, inC, outC);
328
          array_add(tmp, outB, outC, n);
329
          array_compare(tmp, outA, n);
330
     }
331
 
332
     /* test 3: check the time-shift property */
333
     /* the paper performs more tests, but this code should be fine too */
334
     for (i = 0; i < rounds; ++i) {
335
          int j;
336
 
337
          fill_random(inA, n);
338
          array_rol(inB, inA, n, 1, 1);
339
          fftw_out_of_place(plan, n, inA, outA);
340
          fftw_out_of_place(plan, n, inB, outB);
341
          for (j = 0; j < n; ++j) {
342
               FFTW_TRIG_REAL s = dir * FFTW_TRIG_SIN(j * twopin);
343
               FFTW_TRIG_REAL c = FFTW_TRIG_COS(j * twopin);
344
               c_re(tmp[j]) = c_re(outB[j]) * c - c_im(outB[j]) * s;
345
               c_im(tmp[j]) = c_re(outB[j]) * s + c_im(outB[j]) * c;
346
          }
347
 
348
          array_compare(tmp, outA, n);
349
     }
350
 
351
     WHEN_VERBOSE(2, printf("Validation done\n"));
352
 
353
     fftw_free(tmp);
354
     fftw_free(outC);
355
     fftw_free(outB);
356
     fftw_free(outA);
357
     fftw_free(inC);
358
     fftw_free(inB);
359
     fftw_free(inA);
360
}
361
 
362
static void fftw_plan_hook_function(fftw_plan p)
363
{
364
     WHEN_VERBOSE(3, printf("Validating tentative plan\n"));
365
     WHEN_VERBOSE(3, fftw_print_plan(p));
366
     test_ergun(p->n, p->dir, p);
367
}
368
 
369
/* Same as test_ergun, but for multi-dimensional transforms: */
370
void testnd_ergun(int rank, int *n, fftw_direction dir, fftwnd_plan plan)
371
{
372
     fftw_complex *inA, *inB, *inC, *outA, *outB, *outC;
373
     fftw_complex *tmp;
374
     fftw_complex impulse;
375
 
376
     int N, n_before, n_after, dim;
377
     int i, which_impulse;
378
     int rounds = 20;
379
     FFTW_TRIG_REAL twopin;
380
 
381
     N = 1;
382
     for (dim = 0; dim < rank; ++dim)
383
          N *= n[dim];
384
 
385
     inA = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
386
     inB = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
387
     inC = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
388
     outA = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
389
     outB = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
390
     outC = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
391
     tmp = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
392
 
393
     WHEN_VERBOSE(2,
394
                  printf("Validating plan, N = %d, dir = %s\n", N,
395
                         dir == FFTW_FORWARD ? "FORWARD" : "BACKWARD"));
396
 
397
     /* test 1: check linearity */
398
     for (i = 0; i < rounds; ++i) {
399
          fftw_complex alpha, beta;
400
          c_re(alpha) = DRAND();
401
          c_im(alpha) = DRAND();
402
          c_re(beta) = DRAND();
403
          c_im(beta) = DRAND();
404
          fill_random(inA, N);
405
          fill_random(inB, N);
406
          fftwnd(plan, 1, inA, 1, N, outA, 1, N);
407
          fftwnd(plan, 1, inB, 1, N, outB, 1, N);
408
          array_scale(outA, alpha, N);
409
          array_scale(outB, beta, N);
410
          array_add(tmp, outA, outB, N);
411
          array_scale(inA, alpha, N);
412
          array_scale(inB, beta, N);
413
          array_add(inC, inA, inB, N);
414
          fftwnd(plan, 1, inC, 1, N, outC, 1, N);
415
          array_compare(outC, tmp, N);
416
     }
417
 
418
     /*
419
      * test 2: check that the unit impulse is transformed properly -- we
420
      * need to test both the real and imaginary impulses
421
      */
422
 
423
     for (which_impulse = 0; which_impulse < 2; ++which_impulse) {
424
          if (which_impulse == 0) {     /* real impulse */
425
               c_re(impulse) = 1.0;
426
               c_im(impulse) = 0.0;
427
          } else {              /* imaginary impulse */
428
               c_re(impulse) = 0.0;
429
               c_im(impulse) = 1.0;
430
          }
431
 
432
          for (i = 0; i < N; ++i) {
433
               /* impulse */
434
               c_re(inA[i]) = 0.0;
435
               c_im(inA[i]) = 0.0;
436
 
437
               /* transform of the impulse */
438
               outA[i] = impulse;
439
          }
440
          inA[0] = impulse;
441
 
442
          for (i = 0; i < rounds; ++i) {
443
               fill_random(inB, N);
444
               array_sub(inC, inA, inB, N);
445
               fftwnd(plan, 1, inB, 1, N, outB, 1, N);
446
               fftwnd(plan, 1, inC, 1, N, outC, 1, N);
447
               array_add(tmp, outB, outC, N);
448
               array_compare(tmp, outA, N);
449
          }
450
     }
451
 
452
     /* test 3: check the time-shift property */
453
     /* the paper performs more tests, but this code should be fine too */
454
     /* -- we have to check shifts in each dimension */
455
 
456
     n_before = 1;
457
     n_after = N;
458
     for (dim = 0; dim < rank; ++dim) {
459
          int n_cur = n[dim];
460
 
461
          n_after /= n_cur;
462
          twopin = FFTW_K2PI / (FFTW_TRIG_REAL) n_cur;
463
 
464
          for (i = 0; i < rounds; ++i) {
465
               int j, jb, ja;
466
 
467
               fill_random(inA, N);
468
               array_rol(inB, inA, n_cur, n_before, n_after);
469
               fftwnd(plan, 1, inA, 1, N, outA, 1, N);
470
               fftwnd(plan, 1, inB, 1, N, outB, 1, N);
471
 
472
               for (jb = 0; jb < n_before; ++jb)
473
                    for (j = 0; j < n_cur; ++j) {
474
                         FFTW_TRIG_REAL s = dir * FFTW_TRIG_SIN(j * twopin);
475
                         FFTW_TRIG_REAL c = FFTW_TRIG_COS(j * twopin);
476
 
477
                         for (ja = 0; ja < n_after; ++ja) {
478
                              c_re(tmp[(jb * n_cur + j) * n_after + ja]) =
479
                                  c_re(outB[(jb * n_cur + j) * n_after + ja]) * c
480
                                  - c_im(outB[(jb * n_cur + j) * n_after + ja]) * s;
481
                              c_im(tmp[(jb * n_cur + j) * n_after + ja]) =
482
                                  c_re(outB[(jb * n_cur + j) * n_after + ja]) * s
483
                                  + c_im(outB[(jb * n_cur + j) * n_after + ja]) * c;
484
                         }
485
                    }
486
 
487
               array_compare(tmp, outA, N);
488
          }
489
 
490
          n_before *= n_cur;
491
     }
492
 
493
     WHEN_VERBOSE(2, printf("Validation done\n"));
494
 
495
     fftw_free(tmp);
496
     fftw_free(outC);
497
     fftw_free(outB);
498
     fftw_free(outA);
499
     fftw_free(inC);
500
     fftw_free(inB);
501
     fftw_free(inA);
502
}
503
 
504
void test_out_of_place(int n, int istride, int ostride,
505
                       int howmany, fftw_direction dir,
506
                       fftw_plan validated_plan,
507
                       int specific)
508
{
509
     fftw_complex *in1, *in2, *out1, *out2;
510
     fftw_plan plan;
511
     int i, j;
512
     int flags = measure_flag | wisdom_flag | FFTW_OUT_OF_PLACE;
513
 
514
     if (coinflip())
515
          flags |= FFTW_THREADSAFE;
516
 
517
     in1 = (fftw_complex *)
518
          fftw_malloc(istride * n * sizeof(fftw_complex) * howmany);
519
     in2 = (fftw_complex *)
520
          fftw_malloc(n * sizeof(fftw_complex) * howmany);
521
     out1 = (fftw_complex *)
522
          fftw_malloc(ostride * n * sizeof(fftw_complex) * howmany);
523
     out2 = (fftw_complex *)
524
          fftw_malloc(n * sizeof(fftw_complex) * howmany);
525
 
526
     if (!specific)
527
          plan = fftw_create_plan(n, dir, flags);
528
     else
529
          plan = fftw_create_plan_specific(n, dir,
530
                                           flags,
531
                                           in1, istride, out1, ostride);
532
 
533
     /* generate random inputs */
534
     for (i = 0; i < n * howmany; ++i) {
535
          c_re(in1[i * istride]) = c_re(in2[i]) = DRAND();
536
          c_im(in1[i * istride]) = c_im(in2[i]) = DRAND();
537
     }
538
 
539
     /*
540
      * fill in other positions of the array, to make sure that
541
      * fftw doesn't overwrite them
542
      */
543
     for (j = 1; j < istride; ++j)
544
          for (i = 0; i < n * howmany; ++i) {
545
               c_re(in1[i * istride + j]) = i * istride + j;
546
               c_im(in1[i * istride + j]) = i * istride - j;
547
          }
548
 
549
     for (j = 1; j < ostride; ++j)
550
          for (i = 0; i < n * howmany; ++i) {
551
               c_re(out1[i * ostride + j]) = -i * ostride + j;
552
               c_im(out1[i * ostride + j]) = -i * ostride - j;
553
          }
554
 
555
     CHECK(plan != NULL, "can't create plan");
556
     WHEN_VERBOSE(2, fftw_print_plan(plan));
557
 
558
     /* fft-ize */
559
     if (howmany != 1 || istride != 1 || ostride != 1 || coinflip())
560
          fftw(plan, howmany, in1, istride, n * istride, out1, ostride,
561
               n * ostride);
562
     else
563
          fftw_one(plan, in1, out1);
564
 
565
     fftw_destroy_plan(plan);
566
 
567
     /* check for overwriting */
568
     for (j = 1; j < istride; ++j)
569
          for (i = 0; i < n * howmany; ++i)
570
               CHECK(c_re(in1[i * istride + j]) == i * istride + j &&
571
                     c_im(in1[i * istride + j]) == i * istride - j,
572
                     "input has been overwritten");
573
     for (j = 1; j < ostride; ++j)
574
          for (i = 0; i < n * howmany; ++i)
575
               CHECK(c_re(out1[i * ostride + j]) == -i * ostride + j &&
576
                     c_im(out1[i * ostride + j]) == -i * ostride - j,
577
                     "output has been overwritten");
578
 
579
     for (i = 0; i < howmany; ++i) {
580
          fftw(validated_plan, 1, in2 + n * i, 1, n, out2 + n * i, 1, n);
581
     }
582
 
583
     CHECK(compute_error_complex(out1, ostride, out2, 1, n * howmany) < TOLERANCE,
584
           "test_out_of_place: wrong answer");
585
     WHEN_VERBOSE(2, printf("OK\n"));
586
 
587
     fftw_free(in1);
588
     fftw_free(in2);
589
     fftw_free(out1);
590
     fftw_free(out2);
591
}
592
 
593
void test_in_place(int n, int istride, int howmany, fftw_direction dir,
594
                   fftw_plan validated_plan, int specific)
595
{
596
     fftw_complex *in1, *in2, *out2;
597
     fftw_plan plan;
598
     int i, j;
599
     int flags = measure_flag | wisdom_flag | FFTW_IN_PLACE;
600
 
601
     if (coinflip())
602
          flags |= FFTW_THREADSAFE;
603
 
604
     in1 = (fftw_complex *) fftw_malloc(istride * n * sizeof(fftw_complex) * howmany);
605
     in2 = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex) * howmany);
606
     out2 = (fftw_complex *) fftw_malloc(n * sizeof(fftw_complex) * howmany);
607
 
608
     if (!specific)
609
          plan = fftw_create_plan(n, dir, flags);
610
     else
611
          plan = fftw_create_plan_specific(n, dir, flags,
612
                                           in1, istride,
613
                                           (fftw_complex *) NULL, 0);
614
 
615
     /* generate random inputs */
616
     for (i = 0; i < n * howmany; ++i) {
617
          c_re(in1[i * istride]) = c_re(in2[i]) = DRAND();
618
          c_im(in1[i * istride]) = c_im(in2[i]) = DRAND();
619
     }
620
 
621
     /*
622
      * fill in other positions of the array, to make sure that
623
      * fftw doesn't overwrite them
624
      */
625
     for (j = 1; j < istride; ++j)
626
          for (i = 0; i < n * howmany; ++i) {
627
               c_re(in1[i * istride + j]) = i * istride + j;
628
               c_im(in1[i * istride + j]) = i * istride - j;
629
          }
630
     CHECK(plan != NULL, "can't create plan");
631
     WHEN_VERBOSE(2, fftw_print_plan(plan));
632
 
633
     /* fft-ize */
634
     if (howmany != 1 || istride != 1 || coinflip())
635
          fftw(plan, howmany, in1, istride, n * istride,
636
               (fftw_complex *) NULL, 0, 0);
637
     else
638
          fftw_one(plan, in1, NULL);
639
 
640
     fftw_destroy_plan(plan);
641
 
642
     /* check for overwriting */
643
     for (j = 1; j < istride; ++j)
644
          for (i = 0; i < n * howmany; ++i)
645
               CHECK(c_re(in1[i * istride + j]) == i * istride + j &&
646
                     c_im(in1[i * istride + j]) == i * istride - j,
647
                     "input has been overwritten");
648
 
649
     for (i = 0; i < howmany; ++i) {
650
          fftw(validated_plan, 1, in2 + n * i, 1, n, out2 + n * i, 1, n);
651
     }
652
 
653
     CHECK(compute_error_complex(in1, istride, out2, 1, n * howmany) < TOLERANCE,
654
           "test_in_place: wrong answer");
655
     WHEN_VERBOSE(2, printf("OK\n"));
656
 
657
     fftw_free(in1);
658
     fftw_free(in2);
659
     fftw_free(out2);
660
}
661
 
662
void test_out_of_place_both(int n, int istride, int ostride,
663
                            int howmany,
664
                            fftw_plan validated_plan_forward,
665
                            fftw_plan validated_plan_backward)
666
{
667
     int specific;
668
 
669
     for (specific = 0; specific <= 1; ++specific) {
670
          WHEN_VERBOSE(2,
671
               printf("TEST CORRECTNESS (out of place, FFTW_FORWARD, %s)"
672
                   " n = %d  istride = %d  ostride = %d  howmany = %d\n",
673
                      SPECIFICP(specific),
674
                      n, istride, ostride, howmany));
675
          test_out_of_place(n, istride, ostride, howmany, FFTW_FORWARD,
676
                            validated_plan_forward, specific);
677
 
678
          WHEN_VERBOSE(2,
679
              printf("TEST CORRECTNESS (out of place, FFTW_BACKWARD, %s)"
680
                   " n = %d  istride = %d  ostride = %d  howmany = %d\n",
681
                     SPECIFICP(specific),
682
                     n, istride, ostride, howmany));
683
          test_out_of_place(n, istride, ostride, howmany, FFTW_BACKWARD,
684
                            validated_plan_backward, specific);
685
     }
686
}
687
 
688
void test_in_place_both(int n, int istride, int howmany,
689
                        fftw_plan validated_plan_forward,
690
                        fftw_plan validated_plan_backward)
691
{
692
     int specific;
693
 
694
     for (specific = 0; specific <= 1; ++specific) {
695
          WHEN_VERBOSE(2,
696
                  printf("TEST CORRECTNESS (in place, FFTW_FORWARD, %s) "
697
                         "n = %d  istride = %d  howmany = %d\n",
698
                         SPECIFICP(specific),
699
                         n, istride, howmany));
700
          test_in_place(n, istride, howmany, FFTW_FORWARD,
701
                        validated_plan_forward, specific);
702
 
703
          WHEN_VERBOSE(2,
704
                 printf("TEST CORRECTNESS (in place, FFTW_BACKWARD, %s) "
705
                        "n = %d  istride = %d  howmany = %d\n",
706
                        SPECIFICP(specific),
707
                        n, istride, howmany));
708
          test_in_place(n, istride, howmany, FFTW_BACKWARD,
709
                        validated_plan_backward, specific);
710
     }
711
}
712
 
713
void test_correctness(int n)
714
{
715
     int istride, ostride, howmany;
716
     fftw_plan validated_plan_forward, validated_plan_backward;
717
 
718
     WHEN_VERBOSE(1,
719
                  printf("Testing correctness for n = %d...", n);
720
                  fflush(stdout));
721
 
722
     /* produce a *good* plan (validated by Ergun's test procedure) */
723
     validated_plan_forward =
724
         fftw_create_plan(n, FFTW_FORWARD, measure_flag | wisdom_flag);
725
     test_ergun(n, FFTW_FORWARD, validated_plan_forward);
726
     validated_plan_backward =
727
         fftw_create_plan(n, FFTW_BACKWARD, measure_flag | wisdom_flag);
728
     test_ergun(n, FFTW_BACKWARD, validated_plan_backward);
729
 
730
     for (istride = 1; istride <= MAX_STRIDE; ++istride)
731
          for (ostride = 1; ostride <= MAX_STRIDE; ++ostride)
732
               for (howmany = 1; howmany <= MAX_HOWMANY; ++howmany)
733
                    test_out_of_place_both(n, istride, ostride, howmany,
734
                                           validated_plan_forward,
735
                                           validated_plan_backward);
736
 
737
     for (istride = 1; istride <= MAX_STRIDE; ++istride)
738
          for (howmany = 1; howmany <= MAX_HOWMANY; ++howmany)
739
               test_in_place_both(n, istride, howmany,
740
                                  validated_plan_forward,
741
                                  validated_plan_backward);
742
 
743
     fftw_destroy_plan(validated_plan_forward);
744
     fftw_destroy_plan(validated_plan_backward);
745
 
746
     if (!(wisdom_flag & FFTW_USE_WISDOM) && chk_mem_leak)
747
          fftw_check_memory_leaks();
748
 
749
     WHEN_VERBOSE(1, printf("OK\n"));
750
}
751
 
752
/*************************************************
753
 * multi-dimensional correctness tests
754
 *************************************************/
755
 
756
void testnd_out_of_place(int rank, int *n, fftw_direction dir,
757
                         fftwnd_plan validated_plan)
758
{
759
     int istride, ostride;
760
     int N, dim, i;
761
     fftw_complex *in1, *in2, *out1, *out2;
762
     fftwnd_plan p;
763
     int flags = measure_flag | wisdom_flag;
764
 
765
     if (coinflip())
766
          flags |= FFTW_THREADSAFE;
767
 
768
     N = 1;
769
     for (dim = 0; dim < rank; ++dim)
770
          N *= n[dim];
771
 
772
     in1 = (fftw_complex *) fftw_malloc(N * MAX_STRIDE * sizeof(fftw_complex));
773
     out1 = (fftw_complex *) fftw_malloc(N * MAX_STRIDE * sizeof(fftw_complex));
774
     in2 = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
775
     out2 = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
776
 
777
     p = fftwnd_create_plan(rank, n, dir, flags);
778
 
779
     for (istride = 1; istride <= MAX_STRIDE; ++istride) {
780
          /* generate random inputs */
781
          for (i = 0; i < N; ++i) {
782
               int j;
783
               c_re(in2[i]) = DRAND();
784
               c_im(in2[i]) = DRAND();
785
               for (j = 0; j < istride; ++j) {
786
                    c_re(in1[i * istride + j]) = c_re(in2[i]);
787
                    c_im(in1[i * istride + j]) = c_im(in2[i]);
788
               }
789
          }
790
 
791
          for (ostride = 1; ostride <= MAX_STRIDE; ++ostride) {
792
               int howmany = (istride < ostride) ? istride : ostride;
793
 
794
               if (howmany != 1 || istride != 1 || ostride != 1 || coinflip())
795
                    fftwnd(p, howmany, in1, istride, 1, out1, ostride, 1);
796
               else
797
                    fftwnd_one(p, in1, out1);
798
 
799
               fftwnd(validated_plan, 1, in2, 1, 1, out2, 1, 1);
800
 
801
               for (i = 0; i < howmany; ++i)
802
                    CHECK(compute_error_complex(out1 + i, ostride, out2, 1, N)
803
                          < TOLERANCE,
804
                          "testnd_out_of_place: wrong answer");
805
          }
806
     }
807
 
808
     fftwnd_destroy_plan(p);
809
 
810
     fftw_free(out2);
811
     fftw_free(in2);
812
     fftw_free(out1);
813
     fftw_free(in1);
814
}
815
 
816
void testnd_in_place(int rank, int *n, fftw_direction dir,
817
                     fftwnd_plan validated_plan,
818
                     int alternate_api, int specific, int force_buffered)
819
{
820
     int istride;
821
     int N, dim, i;
822
     fftw_complex *in1, *in2, *out2;
823
     fftwnd_plan p;
824
     int flags = measure_flag | wisdom_flag | FFTW_IN_PLACE;
825
 
826
     if (coinflip())
827
          flags |= FFTW_THREADSAFE;
828
 
829
     if (force_buffered)
830
          flags |= FFTWND_FORCE_BUFFERED;
831
 
832
     N = 1;
833
     for (dim = 0; dim < rank; ++dim)
834
          N *= n[dim];
835
 
836
     in1 = (fftw_complex *) fftw_malloc(N * MAX_STRIDE * sizeof(fftw_complex));
837
     in2 = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
838
     out2 = (fftw_complex *) fftw_malloc(N * sizeof(fftw_complex));
839
 
840
     if (!specific) {
841
          if (alternate_api && (rank == 2 || rank == 3)) {
842
               if (rank == 2)
843
                    p = fftw2d_create_plan(n[0], n[1], dir, flags);
844
               else
845
                    p = fftw3d_create_plan(n[0], n[1], n[2], dir, flags);
846
          } else                /* standard api */
847
               p = fftwnd_create_plan(rank, n, dir, flags);
848
     } else {                   /* specific plan creation */
849
          if (alternate_api && (rank == 2 || rank == 3)) {
850
               if (rank == 2)
851
                    p = fftw2d_create_plan_specific(n[0], n[1], dir, flags,
852
                                                    in1, 1,
853
                                               (fftw_complex *) NULL, 1);
854
               else
855
                    p = fftw3d_create_plan_specific(n[0], n[1], n[2], dir, flags,
856
                                                    in1, 1,
857
                                               (fftw_complex *) NULL, 1);
858
          } else                /* standard api */
859
               p = fftwnd_create_plan_specific(rank, n, dir, flags,
860
                                               in1, 1,
861
                                               (fftw_complex *) NULL, 1);
862
 
863
     }
864
 
865
     for (istride = 1; istride <= MAX_STRIDE; ++istride) {
866
          /*
867
           * generate random inputs */
868
          for (i = 0; i < N; ++i) {
869
               int j;
870
               c_re(in2[i]) = DRAND();
871
               c_im(in2[i]) = DRAND();
872
               for (j = 0; j < istride; ++j) {
873
                    c_re(in1[i * istride + j]) = c_re(in2[i]);
874
                    c_im(in1[i * istride + j]) = c_im(in2[i]);
875
               }
876
          }
877
 
878
          if (istride != 1 || istride != 1 || coinflip())
879
               fftwnd(p, istride, in1, istride, 1, (fftw_complex *) NULL, 1, 1);
880
          else
881
               fftwnd_one(p, in1, NULL);
882
 
883
          fftwnd(validated_plan, 1, in2, 1, 1, out2, 1, 1);
884
 
885
          for (i = 0; i < istride; ++i)
886
               CHECK(compute_error_complex(in1 + i, istride, out2, 1, N) < TOLERANCE,
887
                     "testnd_in_place: wrong answer");
888
     }
889
 
890
     fftwnd_destroy_plan(p);
891
 
892
     fftw_free(out2);
893
     fftw_free(in2);
894
     fftw_free(in1);
895
}
896
 
897
void testnd_correctness(struct size sz, fftw_direction dir,
898
                        int alt_api, int specific, int force_buf)
899
{
900
     fftwnd_plan validated_plan;
901
 
902
     validated_plan = fftwnd_create_plan(sz.rank, sz.narray,
903
                                         dir, measure_flag | wisdom_flag);
904
     testnd_ergun(sz.rank, sz.narray, dir, validated_plan);
905
 
906
     testnd_out_of_place(sz.rank, sz.narray, dir, validated_plan);
907
     testnd_in_place(sz.rank, sz.narray, dir, validated_plan, alt_api, specific, force_buf);
908
 
909
     fftwnd_destroy_plan(validated_plan);
910
}
911
 
912
/*************************************************
913
 * planner tests
914
 *************************************************/
915
 
916
void test_planner(int rank)
917
{
918
     /*
919
      * create and destroy many plans, at random.  Check the
920
      * garbage-collecting allocator of twiddle factors
921
      */
922
     int i, dim;
923
     int r, s;
924
     fftw_plan p[PLANNER_TEST_SIZE];
925
     fftwnd_plan pnd[PLANNER_TEST_SIZE];
926
     int *narr, maxdim;
927
 
928
     chk_mem_leak = 0;
929
     verbose--;
930
 
931
     please_wait();
932
     if (rank < 1)
933
          rank = 1;
934
 
935
     narr = (int *) fftw_malloc(rank * sizeof(int));
936
 
937
     maxdim = (int) pow(8192.0, 1.0/rank);
938
 
939
     for (i = 0; i < PLANNER_TEST_SIZE; ++i) {
940
          p[i] = (fftw_plan) 0;
941
          pnd[i] = (fftwnd_plan) 0;
942
     }
943
 
944
     for (i = 0; i < PLANNER_TEST_SIZE * PLANNER_TEST_SIZE; ++i) {
945
          r = rand();
946
          if (r < 0)
947
               r = -r;
948
          r = r % PLANNER_TEST_SIZE;
949
 
950
          for (dim = 0; dim < rank; ++dim) {
951
               do {
952
                    s = rand();
953
                    if (s < 0)
954
                         s = -s;
955
                    s = s % maxdim + 1;
956
               } while (s == 0);
957
               narr[dim] = s;
958
          }
959
 
960
          if (rank == 1) {
961
               if (p[r])
962
                    fftw_destroy_plan(p[r]);
963
 
964
               p[r] = fftw_create_plan(narr[0], random_dir(), measure_flag |
965
                                       wisdom_flag);
966
               if (paranoid && narr[0] < 200)
967
                    test_correctness(narr[0]);
968
          }
969
 
970
          if (pnd[r])
971
               fftwnd_destroy_plan(pnd[r]);
972
 
973
          pnd[r] = fftwnd_create_plan(rank, narr,
974
                                      random_dir(), measure_flag |
975
                                      wisdom_flag);
976
 
977
          if (i % (PLANNER_TEST_SIZE * PLANNER_TEST_SIZE / 20) == 0) {
978
               WHEN_VERBOSE(0, printf("test planner: so far so good\n"));
979
               WHEN_VERBOSE(0, printf("test planner: iteration %d out of %d\n",
980
                              i, PLANNER_TEST_SIZE * PLANNER_TEST_SIZE));
981
          }
982
     }
983
 
984
     for (i = 0; i < PLANNER_TEST_SIZE; ++i) {
985
          if (p[i])
986
               fftw_destroy_plan(p[i]);
987
          if (pnd[i])
988
               fftwnd_destroy_plan(pnd[i]);
989
     }
990
 
991
     fftw_free(narr);
992
     verbose++;
993
     chk_mem_leak = 1;
994
}
995
 
996
/*************************************************
997
 * test initialization
998
 *************************************************/
999
 
1000
void test_init(int *argc, char **argv)
1001
{
1002
}
1003
 
1004
void test_finish(void)
1005
{
1006
}
1007
 
1008
void enter_paranoid_mode(void)
1009
{
1010
     fftw_plan_hook = fftw_plan_hook_function;
1011
}
1012
 
1013
int get_option(int argc, char **argv, char *argval, int argval_maxlen)
1014
{
1015
     return default_get_option(argc,argv,argval,argval_maxlen);
1016
}