lib/PDL/FFT.pd

filter: Statementstmt 100% 95 / 95 Branchbran 64.7% 22 / 34 Conditioncond 66.6% 4 / 6 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 100% 13 / 13 Podpod 0.0% 0 / 6 totaltotal 84.8% 134 / 158 CC 22 SCAR 17.4
CC
22
Cov
90%
fftnd
9.2
ifftnd
9.2
realifft
3.0
CRAP 5.7
« blib/lib/PDL/Compression.pm ↑ Summary blib/lib/Inline/Pdlpp.pm »
1 use strict;
2 use warnings;
3 use PDL::Types qw(types);
4 my $F = [map $_->ppsym, grep $_->real && !$_->integer, types()];
5  
6 { no warnings 'once'; # pass info back to Makefile.PL
7 $PDL::Core::Dev::EXTRAS{$::PDLMOD}{OBJECT} .= join '', map " $::PDLBASE/$_\$(OBJ_EXT)", qw(fftn);
8 $PDL::Core::Dev::EXTRAS{$::PDLMOD}{DEFINE} .= qq{ -DFFT_FLOAT -DFFT_DOUBLE -DFFT_LDOUBLE};
9 $PDL::Core::Dev::EXTRAS{$::PDLMOD}{INC} .= qq{ "-I$::PDLBASE"};
10 }
11  
12 pp_addpm({At=>'Top'},<<'EOD');
13 =head1 NAME
14  
15 PDL::FFT - FFTs for PDL
16  
17 =head1 DESCRIPTION
18  
19 !!!!!!!!!!!!!!!!!!!!!!!!!!WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
20 As of PDL-2.006_04, the direction of the FFT/IFFT has been
21 reversed to match the usage in the FFTW library and the convention
22 in use generally.
23 !!!!!!!!!!!!!!!!!!!!!!!!!!WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
24  
25 FFTs for PDL. These work for arrays of any dimension, although ones
26 with small prime factors are likely to be the quickest. The forward
27 FFT is unnormalized while the inverse FFT is normalized so that the
28 IFFT of the FFT returns the original values.
29  
30 For historical reasons, these routines work in-place and do not recognize
31 the in-place flag. That should be fixed.
32  
33 =head1 SYNOPSIS
34  
35 use PDL::FFT qw/:Func/;
36  
37 fft($real, $imag);
38 ifft($real, $imag);
39 realfft($real);
40 realifft($real);
41  
42 fftnd($real,$imag);
43 ifftnd($real,$imag);
44  
45 $kernel = kernctr($image,$smallk);
46 fftconvolve($image,$kernel);
47  
48 =head1 DATA TYPES
49  
50 The underlying C library upon which this module is based performs FFTs
51 on both single precision and double precision floating point ndarrays.
52 The PP functions are defined to only take those data types.
53 Therefore, if you pass in an ndarray of integer datatype (byte, short,
54 ushort, long) to any of the routines in PDL::FFT, your data will be
55 promoted to a double-precision ndarray. If you pass in a float, the
56 single-precision FFT will be performed.
57  
58 =head1 FREQUENCIES
59  
60 For even-sized input arrays, the frequencies are packed like normal
61 for FFTs (where N is the size of the array and D is the physical step
62 size between elements):
63  
64 0, 1/ND, 2/ND, ..., (N/2-1)/ND, 1/2D, -(N/2-1)/ND, ..., -1/ND.
65  
66 which can easily be obtained (taking the Nyquist frequency to be
67 positive) using
68  
69 C<< $kx = $real->xlinvals(-($N/2-1)/$N/$D,1/2/$D)->rotate(-($N/2 -1)); >>
70  
71 For odd-sized input arrays the Nyquist frequency is not directly
72 acessible, and the frequencies are
73  
74 0, 1/ND, 2/ND, ..., (N/2-0.5)/ND, -(N/2-0.5)/ND, ..., -1/ND.
75  
76 which can easily be obtained using
77  
78 C<< $kx = $real->xlinvals(-($N/2-0.5)/$N/$D,($N/2-0.5)/$N/$D)->rotate(-($N-1)/2); >>
79  
80  
81 =head1 ALTERNATIVE FFT PACKAGES
82  
83 Various other modules - such as L<PDL::FFTW3> and L<PDL::Slatec> -
84 contain FFT routines.
85 However, unlike PDL::FFT, these modules are optional,
86 and so may not be installed.
87  
88 =cut
89  
90 EOD
91  
92 pp_def('fft',
93 Pars => '[io]real(n); [io]imag(n);',
94 GenericTypes => $F,
95 CHeader => qq{#include "fftn.h"\n},
96 Code => 'fftn$TFDE(f,,l)($SIZE(n), NULL, $P(real), $P(imag), -1, 1.);',
97 Doc=><<'EOF',
98 =for ref
99  
100 Complex 1-D FFT of the "real" and "imag" arrays [inplace]. A single
101 cfloat/cdouble input ndarray can also be used.
102 EOF
103 PMCode=><<'EOF',
104 sub PDL::fft {
105 # Convert the first argument to decimal and check for trouble.
106 my ($re, $im) = @_;
107 if (!$re->type->real) {
108 $im=$re->im;
109 $re=$re->re;
110 }
111 eval { todecimal($re); };
112 if ($@) {
113 $@ =~ s/ at .*//s;
114 barf("Error in FFT with first argument: $@");
115 }
116 # Convert the second argument to decimal and check for trouble.
117 eval { todecimal($im); };
118 if ($@) {
119 $@ =~ s/ at .*//s;
120 my $message = "Error in FFT with second argument: $@";
121 $message .= '. Did you forget to supply the second (imaginary) ndarray?'
122 if ($message =~ /undefined value/);
123 barf($message);
124 }
125 PDL::_fft_int($re,$im);
126 if (!$_[0]->type->real) {
127 $_[0]= czip($re, $im);
128 } else {
129 $_[0]=$re,$_[1]=$im;
130 }
131 }
132 EOF
133 );
134  
135 pp_def('ifft',
136 Pars => '[io]real(n); [io]imag(n);',
137 GenericTypes => $F,
138 CHeader => qq{#include "fftn.h"\n},
139 Code => 'fftn$TFDE(f,,l)($SIZE(n), NULL, $P(real), $P(imag), 1, -1.);',
140 Doc=><<'EOF',
141 =for ref
142  
143 Complex inverse 1-D FFT of the "real" and "imag" arrays [inplace]. A single
144 cfloat/cdouble input ndarray can also be used.
145 EOF
146 PMCode=><<'EOF',
147 sub PDL::ifft {
148 # Convert the first argument to decimal and check for trouble.
149 my ($re, $im) = @_;
150 if (!$re->type->real) {
151 $im=$re->im;
152 $re=$re->re;
153 }
154 eval { todecimal($re); };
155 if ($@) {
156 $@ =~ s/ at .*//s;
157 barf("Error in FFT with first argument: $@");
158 }
159 # Convert the second argument to decimal and check for trouble.
160 eval { todecimal($im); };
161 if ($@) {
162 $@ =~ s/ at .*//s;
163 my $message = "Error in FFT with second argument: $@";
164 $message .= '. Did you forget to supply the second (imaginary) ndarray?'
165 if ($message =~ /undefined value/);
166 barf($message);
167 }
168 PDL::_ifft_int($re,$im);
169 if (!$_[0]->type->real) {
170 $_[0]= czip($re, $im);
171 } else {
172 $_[0]=$re,$_[1]=$im;
173 }
174 }
175 EOF
176 );
177  
178 pp_add_exported('',"fftnd ifftnd fftconvolve realfft realifft kernctr");
179  
180 pp_addpm(<<'EOD');
181 5 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
182 5 ▶use PDL::Core qw/:Func/;
Subroutine BEGIN: called CC=1 SCAR=0.0
183 5 ▶use PDL::Basic qw/:Func/;
Subroutine BEGIN: called CC=1 SCAR=0.0
184 5 ▶use PDL::Types;
Subroutine BEGIN: called CC=1 SCAR=0.0
185 5 ▶use PDL::ImageND qw/kernctr/; # moved to ImageND since FFTW uses it too
Subroutine BEGIN: called CC=1 SCAR=0.0
186 5 ▶use PDL::Ops qw/czip/;
Subroutine BEGIN: called CC=1 SCAR=0.0
187  
188 182 ▶sub todecimal {
Subroutine todecimal: called CC=2 SCAR=6.9
Pod undocumented
189 182 my ($arg) = @_;
190 182 ▶ $arg = $arg->double if $arg->type->integer;
Branch: 1 branch
BranchTrueFalseTotal
if $arg->type->integer 10 170 180
191 180 $_[0] = $arg;
192 180 1;}
193  
194 =head2 realfft()
195  
196 =for ref
197  
198 One-dimensional FFT of real function [inplace].
199  
200 The real part of the transform ends up in the first half of the array
201 and the imaginary part of the transform ends up in the second half of
202 the array.
203  
204 =for usage
205  
206 realfft($real);
207  
208 =cut
209  
210 *realfft = \&PDL::realfft;
211  
212 1 ▶sub PDL::realfft {
Subroutine realfft: called CC=2 SCAR=6.9
Pod undocumented
213 1 ▶ barf("Usage: realfft(real(*)") if $#_ != 0;
Branch: 1 branch
BranchTrueFalseTotal
if $#_ != 0 0 1 1
214 1 my ($x) = @_;
215 1 todecimal($x);
216 # FIX: could eliminate $y
217 1 my ($y) = 0*$x;
218 1 fft($x,$y);
219 1 my ($n) = int((($x->dims)[0]-1)/2); my($t);
220 1 ($t=$x->slice("-$n:-1")) .= $y->slice("1:$n");
221 1 undef;
222 }
223  
224 =head2 realifft()
225  
226 =for ref
227  
228 Inverse of one-dimensional realfft routine [inplace].
229  
230 =for usage
231  
232 realifft($real);
233  
234 =cut
235  
236 *realifft = \&PDL::realifft;
237  
238 1 ▶sub PDL::realifft {
Subroutine realifft: called CC=3 SCAR=11.0
Pod undocumented
239 5 ▶ use PDL::Ufunc 'max';
Subroutine BEGIN: called CC=1 SCAR=0.0
240 1 ▶ barf("Usage: realifft(xfm(*)") if $#_ != 0;
Branch: 1 branch
BranchTrueFalseTotal
if $#_ != 0 0 1 1
241 1 my ($x) = @_;
242 1 todecimal($x);
243 1 my ($n) = int((($x->dims)[0]-1)/2); my($t);
244 # FIX: could eliminate $y
245 1 my ($y) = 0*$x;
246 1 ($t=$y->slice("1:$n")) .= $x->slice("-$n:-1");
247 1 ($t=$x->slice("-$n:-1")) .= $x->slice("$n:1");
248 1 ($t=$y->slice("-$n:-1")) .= -$y->slice("$n:1");
249 1 ifft($x,$y);
250 # Sanity check -- shouldn't happen
251 1 ▶ carp "Bad inverse transform in realifft" if max(abs($y)) > 1e-6*max(abs($x));
Branch: 1 branch
BranchTrueFalseTotal
if max(abs $y) > "1e-06" * max(abs $x) 0 1 1
252 1 undef;
253 }
254  
255 =head2 fftnd()
256  
257 =for ref
258  
259 N-dimensional FFT over all pdl dims of input (inplace)
260  
261 =for example
262  
263 fftnd($real,$imag);
264  
265 =cut
266  
267 *fftnd = \&PDL::fftnd;
268  
269 16 ▶sub PDL::fftnd {
Subroutine fftnd: called CC=9 SCAR=22.2
Pod undocumented
270 16 my ($r,$i) = @_;
271 16 ▶ barf "Must have real and imaginary parts or complex for fftnd"
Branch: 1 branch
BranchTrueFalseTotal
if $r->type->real and @_ != 2 0 16 16
Condition66%2/3
$r->type->real and @_ != 2
!ll&&!rl&&r
5110
MC/DC0%0/2
$r->type->real and @_ != 2
$r->type->real @_ != 2
Truth table66%2/3
A and B
A= $r->type->realB= @_ != 2
ABresult
0X0
100
111
272 if $r->type->real and @_ != 2;
273 16 ▶ if (!$r->type->real) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($r->type->real) 5 11 16
274 5 $i=$r->im;
275 5 $r=$r->re;
276 }
277 16 my ($n) = $r->getndims;
278 16 ▶ barf "Dimensions of real and imag must be the same for fft"
Branch: 1 branch
BranchTrueFalseTotal
if $n != $i->getndims 0 16 16
279 if ($n != $i->getndims);
280 16 $n--;
281 16 todecimal($r);
282 16 todecimal($i);
283 # need the copy in case $r and $i point to same memory
284 21 $i = $i->copy;
285 21 foreach (0..$n) {
286 39 fft($r,$i);
287 39 ▶ $r = $r->mv(0,$n) if 0 != $n;
Branch: 1 branch
BranchTrueFalseTotal
if 0 != $n 34 0 34
288 39 ▶ $i = $i->mv(0,$n) if 0 != $n;
Branch: 1 branch
BranchTrueFalseTotal
if 0 != $n 34 0 34
289 }
290 16 ▶ if (!$_[0]->type->real) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $_[0]->type->real) { } 5 11 16
291 5 $_[0]= czip($r, $i);
292 } else {
293 11 $_[0] = $r; $_[1] = $i;
294 }
295 16 undef;
296 }
297  
298 =head2 ifftnd()
299  
300 =for ref
301  
302 N-dimensional inverse FFT over all pdl dims of input (inplace)
303  
304 =for example
305  
306 ifftnd($real,$imag);
307  
308 =cut
309  
310 *ifftnd = \&PDL::ifftnd;
311  
312 8 ▶sub PDL::ifftnd {
Subroutine ifftnd: called CC=9 SCAR=22.2
Pod undocumented
313 8 my ($r,$i) = @_;
314 8 ▶ barf "Must have real and imaginary parts or complex for ifftnd"
Branch: 1 branch
BranchTrueFalseTotal
if $r->type->real and @_ != 2 0 8 8
Condition66%2/3
$r->type->real and @_ != 2
!ll&&!rl&&r
350
MC/DC0%0/2
$r->type->real and @_ != 2
$r->type->real @_ != 2
Truth table66%2/3
A and B
A= $r->type->realB= @_ != 2
ABresult
0X0
100
111
315 if $r->type->real and @_ != 2;
316 8 ▶ if (!$r->type->real) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($r->type->real) 3 5 8
317 3 $i=$r->im;
318 3 $r=$r->re;
319 }
320 8 my ($n) = $r->getndims;
321 8 ▶ barf "Dimensions of real and imag must be the same for ifft"
Branch: 1 branch
BranchTrueFalseTotal
if $n != $i->getndims 0 8 8
322 if ($n != $i->getndims);
323 8 todecimal($r);
324 8 todecimal($i);
325 # need the copy in case $r and $i point to same memory
326 8 $i = $i->copy;
327 8 $n--;
328 8 foreach (0..$n) {
329 16 ifft($r,$i);
330 16 ▶ $r = $r->mv(0,$n) if 0 != $n;
Branch: 1 branch
BranchTrueFalseTotal
if 0 != $n 16 0 16
331 16 ▶ $i = $i->mv(0,$n) if 0 != $n;
Branch: 1 branch
BranchTrueFalseTotal
if 0 != $n 16 0 16
332 }
333 8 ▶ if (!$_[0]->type->real) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $_[0]->type->real) { } 3 5 8
334 3 $_[0]= czip($r, $i);
335 } else {
336 5 $_[0] = $r; $_[1] = $i;
337 }
338 8 undef;
339 }
340  
341 =head2 fftconvolve()
342  
343 =for ref
344  
345 N-dimensional convolution with periodic boundaries (FFT method)
346  
347 =for usage
348  
349 $kernel = kernctr($image,$smallk);
350 fftconvolve($image,$kernel);
351  
352 fftconvolve works inplace, and returns an error array in kernel as an
353 accuracy check -- all the values in it should be negligible.
354  
355 See also L<PDL::ImageND::convolveND|PDL::ImageND/convolveND>, which
356 performs speed-optimized convolution with a variety of boundary conditions.
357  
358 The sizes of the image and the kernel must be the same.
359 L<kernctr|PDL::ImageND/kernctr> centres a small kernel to emulate the
360 behaviour of the direct convolution routines.
361  
362 The speed cross-over between using straight convolution
363 (L<PDL::Image2D::conv2d()|PDL::Image2D/conv2d>) and
364 these fft routines is for kernel sizes roughly 7x7.
365  
366 =cut
367  
368 *fftconvolve = \&PDL::fftconvolve;
369  
370 2 ▶sub PDL::fftconvolve {
Subroutine fftconvolve: called CC=2 SCAR=6.9
Pod undocumented
371 2 ▶ barf "Must have image & kernel for fftconvolve" if $#_ != 1;
Branch: 1 branch
BranchTrueFalseTotal
if $#_ != 1 0 2 2
372 2 my ($im, $k) = map $_->r2C, @_;
373 2 fftnd($im);
374 2 fftnd($k);
375 2 my $c = $im * $k;
376 2 ifftnd($c);
377 2 $_[0] = $c->re->sever;
378 2 $_[1] = $c->im->sever;
379 2 @_;
380 }
381 EOD
382  
383 pp_addpm({At=>'Bot'},<<'EOD');
384 =head1 BUGS
385  
386 Where the source is marked `FIX', could re-implement using phase-shift
387 factors on the transforms and some real-space bookkeeping, to save
388 some temporary space and redundant transforms.
389  
390 =head1 AUTHOR
391  
392 This file copyright (C) 1997, 1998 R.J.R. Williams
393 (rjrw@ast.leeds.ac.uk), Karl Glazebrook (kgb@aaoepp.aao.gov.au),
394 Tuomas J. Lukka, (lukka@husc.harvard.edu). All rights reserved. There
395 is no warranty. You are allowed to redistribute this software /
396 documentation under certain conditions. For details, see the file
397 COPYING in the PDL distribution. If this file is separated from the
398 PDL distribution, the copyright notice should be included in the file.
399  
400 =cut
401 EOD
402  
403 pp_done();
« blib/lib/PDL/Compression.pm ↑ Summary blib/lib/Inline/Pdlpp.pm »