| 1 | package Peta::Synth::FFT; | ||||||||||||||||||||
| 2 | # ABSTRACT: the discrete Fourier transform: radix 2, in place | ||||||||||||||||||||
| 3 | |||||||||||||||||||||
| 4 | # The discrete Fourier transform, for measuring sound (Peta::Synth::Analysis) | ||||||||||||||||||||
| 5 | # and for making it (Peta::Synth::Wavetable). | ||||||||||||||||||||
| 6 | |||||||||||||||||||||
| 7 | 18 | ▶ | use v5.36; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 8 | |||||||||||||||||||||
| 9 | 18 | our $VERSION = '0.2610180'; | |||||||||||||||||||
| 10 | |||||||||||||||||||||
| 11 | 18 | ▶ | use constant PI => 3.141592653589793; | ||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||
| 12 | |||||||||||||||||||||
| 13 | 18 | my %PLAN; # a plan for each size the transform has been asked for | |||||||||||||||||||
| 14 | |||||||||||||||||||||
| 15 | # What a size of transform needs: the order the input is taken in (each | ||||||||||||||||||||
| 16 | # index with its bits reversed), and the twiddles, cos and sin of | ||||||||||||||||||||
| 17 | # -2 pi k / n for k below n / 2. | ||||||||||||||||||||
| 18 | 26 | ▶ | sub _plan ($n) { | ||||||||||||||||||
|
Subroutine
_plan: called CC=2 SCAR=6.9
| |||||||||||||||||||||
| 19 | 26 | my $bits = 0; | |||||||||||||||||||
| 20 | 26 | ▶ | $bits++ while (1 << $bits) < $n; | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 21 | 26 | my @order = map { _reversed($_, $bits) } 0 .. $n - 1; | |||||||||||||||||||
| 22 | 26 | my @cos = map { cos(-2 * PI * $_ / $n) } 0 .. $n / 2 - 1; | |||||||||||||||||||
| 23 | 26 | my @sin = map { sin(-2 * PI * $_ / $n) } 0 .. $n / 2 - 1; | |||||||||||||||||||
| 24 | 26 | return [ \@order, \@cos, \@sin ]; | |||||||||||||||||||
| 25 | } | ||||||||||||||||||||
| 26 | |||||||||||||||||||||
| 27 | # $k's lowest $bits bits in the reverse order. | ||||||||||||||||||||
| 28 | 56576 | ▶ | sub _reversed ($k, $bits) { | ||||||||||||||||||
|
Subroutine
_reversed: called CC=2 SCAR=6.9
| |||||||||||||||||||||
| 29 | 56576 | my $r = 0; | |||||||||||||||||||
| 30 | 56576 | for (1 .. $bits) { | |||||||||||||||||||
| 31 | 726528 | $r = ($r << 1) | ($k & 1); | |||||||||||||||||||
| 32 | 726528 | $k >>= 1; | |||||||||||||||||||
| 33 | } | ||||||||||||||||||||
| 34 | 56576 | return $r; | |||||||||||||||||||
| 35 | } | ||||||||||||||||||||
| 36 | |||||||||||||||||||||
| 37 | # The discrete Fourier transform, in place, of a power of two of complex | ||||||||||||||||||||
| 38 | # numbers (real parts, imaginary parts): radix 2, iterative. The order and | ||||||||||||||||||||
| 39 | # the twiddles are worked out once a size; the butterflies run on plain | ||||||||||||||||||||
| 40 | # arrays (what pperl's JIT compiles). | ||||||||||||||||||||
| 41 | 4913 | ▶ | sub fft ($re, $im) { | ||||||||||||||||||
|
Subroutine
fft: called CC=7 SCAR=19.5
Pod
documented
| |||||||||||||||||||||
| 42 | 4913 | my $n = @$re; | |||||||||||||||||||
| 43 | 4913 | ▶ | die "an FFT of $n points: not a power of two\n" if $n & ($n - 1); | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 44 | 4912 | ▶ | my ($order, $cos, $sin) = @{ $PLAN{$n} //= _plan($n) }; | ||||||||||||||||||
|
Condition66%2/3
$PLAN{$n} //= _plan($n)
MC/DC0%0/2
$PLAN{$n} //= _plan($n)
$PLAN{$n}
_plan($n)
Truth table66%2/3
A //= B
A= $PLAN{$n}B= _plan($n)
| |||||||||||||||||||||
| 45 | 4912 | my @o = @$order; | |||||||||||||||||||
| 46 | 4912 | my @c = @$cos; | |||||||||||||||||||
| 47 | 4912 | my @s = @$sin; | |||||||||||||||||||
| 48 | 4912 | my @r = @$re; | |||||||||||||||||||
| 49 | 4912 | my @i = @$im; | |||||||||||||||||||
| 50 | 4912 | my @pr = (0.0) x $n; | |||||||||||||||||||
| 51 | 4912 | my @pi = (0.0) x $n; | |||||||||||||||||||
| 52 | 4912 | for my $k (0 .. $n - 1) { | |||||||||||||||||||
| 53 | 5431232 | $pr[ $o[$k] ] = $r[$k]; | |||||||||||||||||||
| 54 | 5431232 | $pi[ $o[$k] ] = $i[$k]; | |||||||||||||||||||
| 55 | } | ||||||||||||||||||||
| 56 | 4912 | my $len = 2; | |||||||||||||||||||
| 57 | 4912 | ▶ | while ($len <= $n) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 58 | 45224 | my $half = int($len / 2); | |||||||||||||||||||
| 59 | 45224 | my $stride = int($n / $len); | |||||||||||||||||||
| 60 | 45224 | my $start = 0; | |||||||||||||||||||
| 61 | 45224 | ▶ | while ($start < $n) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 62 | 5426320 | my $k = 0; | |||||||||||||||||||
| 63 | 5426320 | ▶ | while ($k < $half) { | ||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||
| 64 | 29997824 | my $p = $start + $k; | |||||||||||||||||||
| 65 | 29997824 | my $q = $p + $half; | |||||||||||||||||||
| 66 | 29997824 | my $wr = $c[ $k * $stride ]; | |||||||||||||||||||
| 67 | 29997824 | my $wi = $s[ $k * $stride ]; | |||||||||||||||||||
| 68 | 29997824 | my $tr = $pr[$q] * $wr - $pi[$q] * $wi; | |||||||||||||||||||
| 69 | 29997824 | my $ti = $pr[$q] * $wi + $pi[$q] * $wr; | |||||||||||||||||||
| 70 | 29997824 | $pr[$q] = $pr[$p] - $tr; | |||||||||||||||||||
| 71 | 29997824 | $pi[$q] = $pi[$p] - $ti; | |||||||||||||||||||
| 72 | 29997824 | $pr[$p] += $tr; | |||||||||||||||||||
| 73 | 29997824 | $pi[$p] += $ti; | |||||||||||||||||||
| 74 | 29997824 | $k++; | |||||||||||||||||||
| 75 | } | ||||||||||||||||||||
| 76 | 5426320 | $start += $len; | |||||||||||||||||||
| 77 | } | ||||||||||||||||||||
| 78 | 45224 | $len *= 2; | |||||||||||||||||||
| 79 | } | ||||||||||||||||||||
| 80 | 4912 | @$re = @pr; | |||||||||||||||||||
| 81 | 4912 | @$im = @pi; | |||||||||||||||||||
| 82 | 4912 | return; | |||||||||||||||||||
| 83 | } | ||||||||||||||||||||
| 84 | |||||||||||||||||||||
| 85 | 18 | 1; | |||||||||||||||||||
| 86 | |||||||||||||||||||||
| 87 | __END__ | ||||||||||||||||||||