annotate peck_fft.c @ 12:655dc5c14169

backup
author Peter Meerwald <p.meerwald@bct-electronic.com>
date Thu, 22 Sep 2011 16:58:25 +0200
parents abdcde012978
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
1 /*
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
2 Copyright (c) 2003-2010, Mark Borgerding
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
3
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
4 All rights reserved.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
5
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
6 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
7
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
8 * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
9 * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
10 * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
11
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
12 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
13 */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
14
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
15 #include "armv7_cycles.h"
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
16 #include "_peck_fft_guts.h"
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
17 /* The guts header contains all the multiplication and addition macros that are defined for
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
18 * fixed or floating point complex numbers. It also delares the kf_ internal functions.
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
19 */
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
20 #if !BFLY2_ASM
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
21 static void kf_bfly2(
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
22 peck_fft_cpx * __restrict Fout,
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
23 const size_t fstride,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
24 const peck_fft_cfg st,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
25 int m) {
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
26
7
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 6
diff changeset
27 // printf("kf_bfly2, %d\n", fstride);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
28
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
29 peck_fft_cpx * __restrict tw1 = st->twiddles;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
30 peck_fft_cpx * __restrict Fout2 = Fout + m;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
31 do {
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
32 peck_fft_cpx t;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
33 C_MUL(t, *Fout2, *tw1);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
34 tw1 += fstride;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
35 C_SUB(*Fout2, *Fout, t);
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
36 C_ADDTO(*Fout, t);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
37 ++Fout2;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
38 ++Fout;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
39 } while (--m);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
40 }
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
41 #endif
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
42
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
43 #if !BFLY4_ASM
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
44 static void kf_bfly4(
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
45 peck_fft_cpx * __restrict Fout,
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
46 const size_t fstride,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
47 const peck_fft_cfg st,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
48 const size_t m) {
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
49
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
50 peck_fft_cpx scratch[4];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
51 peck_fft_cpx * __restrict tw1, * __restrict tw2, * __restrict tw3;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
52 size_t k = m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
53 const size_t m2 = 2*m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
54 const size_t m3 = 3*m;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
55
7
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 6
diff changeset
56 // printf("kf_bfly4, %d\n", fstride);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
57
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
58 tw3 = tw2 = tw1 = st->twiddles;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
59
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
60 if (st->inverse) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
61 do {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
62 C_MUL(scratch[0], Fout[m], *tw1);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
63 C_MUL(scratch[3], Fout[m2], *tw2);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
64 C_MUL(scratch[2], Fout[m3], *tw3);
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
65
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
66 C_SUB(scratch[1], *Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
67 C_ADDTO(*Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
68
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
69 C_ADD(scratch[3], scratch[0], scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
70 C_SUB(Fout[m2], *Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
71 C_ADDTO(*Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
72
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
73 tw1 += fstride;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
74 tw2 += fstride*2;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
75 tw3 += fstride*3;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
76
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
77 C_SUB(scratch[3], scratch[0], scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
78 Fout[m].r = scratch[1].r - scratch[3].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
79 Fout[m].i = scratch[1].i + scratch[3].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
80 Fout[m3].r = scratch[1].r + scratch[3].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
81 Fout[m3].i = scratch[1].i - scratch[3].r;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
82
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
83 ++Fout;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
84 } while (--k);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
85 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
86 else {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
87 do {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
88 C_MUL(scratch[0], Fout[m], *tw1);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
89 C_MUL(scratch[3], Fout[m2], *tw2);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
90 C_MUL(scratch[2], Fout[m3], *tw3);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
91
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
92 C_SUB(scratch[1], *Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
93 C_ADDTO(*Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
94
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
95 C_ADD(scratch[3], scratch[0], scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
96 C_SUB(Fout[m2], *Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
97 C_ADDTO(*Fout, scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
98
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
99 tw1 += fstride;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
100 tw2 += fstride*2;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
101 tw3 += fstride*3;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
102
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
103 C_SUB(scratch[3], scratch[0], scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
104 Fout[m].r = scratch[1].r + scratch[3].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
105 Fout[m].i = scratch[1].i - scratch[3].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
106 Fout[m3].r = scratch[1].r - scratch[3].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
107 Fout[m3].i = scratch[1].i + scratch[3].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
108
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
109 ++Fout;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
110 } while (--k);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
111 }
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
112 }
10
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 9
diff changeset
113 #endif
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
114
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
115 static void kf_bfly3(
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
116 peck_fft_cpx * Fout,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
117 const size_t fstride,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
118 const peck_fft_cfg st,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
119 size_t m) {
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
120
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
121 size_t k=m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
122 const size_t m2 = 2*m;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
123 peck_fft_cpx *tw1, *tw2;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
124 peck_fft_cpx scratch[5];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
125 peck_fft_cpx epi3;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
126 epi3 = st->twiddles[fstride*m];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
127
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
128 printf("kf_bfly3\n");
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
129
5
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
130 tw1 = tw2 = st->twiddles;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
131
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
132 do {
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
133 C_MUL(scratch[1],Fout[m] , *tw1);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
134 C_MUL(scratch[2],Fout[m2] , *tw2);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
135
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
136 C_ADD(scratch[3],scratch[1],scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
137 C_SUB(scratch[0],scratch[1],scratch[2]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
138 tw1 += fstride;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
139 tw2 += fstride*2;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
140
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
141 Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
142 Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
143
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
144 C_MULBYSCALAR( scratch[0] , epi3.i );
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
145
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
146 C_ADDTO(*Fout,scratch[3]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
147
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
148 Fout[m2].r = Fout[m].r + scratch[0].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
149 Fout[m2].i = Fout[m].i - scratch[0].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
150
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
151 Fout[m].r -= scratch[0].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
152 Fout[m].i += scratch[0].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
153
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
154 ++Fout;
1
cfec79393811 cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 0
diff changeset
155 } while (--k);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
156 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
157
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
158 static void kf_bfly5(
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
159 peck_fft_cpx * Fout,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
160 const size_t fstride,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
161 const peck_fft_cfg st,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
162 int m
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
163 ) {
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
164 peck_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
165 int u;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
166 peck_fft_cpx scratch[13];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
167 peck_fft_cpx * twiddles = st->twiddles;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
168 peck_fft_cpx *tw;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
169 peck_fft_cpx ya,yb;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
170 ya = twiddles[fstride*m];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
171 yb = twiddles[fstride*2*m];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
172
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
173 printf("kf_bfly5\n");
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
174
5
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
175 Fout0 = Fout;
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
176 Fout1 = Fout0 + m;
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
177 Fout2 = Fout0 + 2*m;
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
178 Fout3 = Fout0 + 3*m;
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
179 Fout4 = Fout0 + 4*m;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
180
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
181 tw=st->twiddles;
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
182 for (u = 0; u < m; ++u) {
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
183 scratch[0] = *Fout0;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
184
6
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
185 C_MUL(scratch[1], *Fout1, tw[u*fstride]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
186 C_MUL(scratch[2], *Fout2, tw[2*u*fstride]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
187 C_MUL(scratch[3], *Fout3, tw[3*u*fstride]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
188 C_MUL(scratch[4], *Fout4, tw[4*u*fstride]);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
189
6
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
190 C_ADD(scratch[7], scratch[1], scratch[4]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
191 C_SUB(scratch[10], scratch[1], scratch[4]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
192 C_ADD(scratch[8], scratch[2], scratch[3]);
fee54f1878f7 kill FIXED_POINT stuff, simplify
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 5
diff changeset
193 C_SUB(scratch[9], scratch[2], scratch[3]);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
194
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
195 Fout0->r += scratch[7].r + scratch[8].r;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
196 Fout0->i += scratch[7].i + scratch[8].i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
197
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
198 scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
199 scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
200
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
201 scratch[6].r = S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
202 scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
203
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
204 C_SUB(*Fout1,scratch[5],scratch[6]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
205 C_ADD(*Fout4,scratch[5],scratch[6]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
206
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
207 scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
208 scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
209 scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
210 scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
211
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
212 C_ADD(*Fout2,scratch[11],scratch[12]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
213 C_SUB(*Fout3,scratch[11],scratch[12]);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
214
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
215 ++Fout0;++Fout1;++Fout2;++Fout3;++Fout4;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
216 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
217 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
218
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
219 /* perform the butterfly for one stage of a mixed radix FFT */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
220 static void kf_bfly_generic(
4
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
221 peck_fft_cpx * Fout,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
222 const size_t fstride,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
223 const peck_fft_cfg st,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
224 int m,
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
225 int p) {
2d6c49fcafcb neon2 and neon4 support
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 1
diff changeset
226
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
227 int u,k,q1,q;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
228 peck_fft_cpx * twiddles = st->twiddles;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
229 peck_fft_cpx t;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
230 int Norig = st->nfft;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
231
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
232 printf("kf_bfly_generic\n");
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
233
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
234 peck_fft_cpx * scratch = (peck_fft_cpx*)PECK_FFT_TMP_ALLOC(sizeof(peck_fft_cpx)*p);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
235
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
236 for ( u=0; u<m; ++u ) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
237 k=u;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
238 for (q1 = 0; q1 < p; ++q1) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
239 scratch[q1] = Fout[k];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
240 k += m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
241 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
242
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
243 k=u;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
244 for ( q1=0 ; q1<p ; ++q1 ) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
245 int twidx=0;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
246 Fout[ k ] = scratch[0];
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
247 for (q=1;q<p;++q ) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
248 twidx += fstride * k;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
249 if (twidx>=Norig) twidx-=Norig;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
250 C_MUL(t,scratch[q] , twiddles[twidx] );
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
251 C_ADDTO( Fout[ k ] ,t);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
252 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
253 k += m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
254 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
255 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
256 PECK_FFT_TMP_FREE(scratch);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
257 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
258
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
259 static void kf_work(
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
260 peck_fft_cpx * Fout,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
261 const peck_fft_cpx * f,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
262 const size_t fstride,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
263 int *factors,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
264 const peck_fft_cfg st) {
5
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
265
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
266 peck_fft_cpx *Fout_beg = Fout;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
267 const int p = *factors++; /* the radix */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
268 const int m = *factors++; /* stage's FFT length / p */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
269 const peck_fft_cpx *Fout_end = Fout + p*m;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
270
7
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 6
diff changeset
271 // printf("kf_work, %d\n", fstride);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
272
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
273 if (m == 1) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
274 do {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
275 *Fout = *f;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
276 f += fstride;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
277 } while (++Fout != Fout_end);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
278 } else {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
279 do {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
280 // recursive call:
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
281 // DFT of size m*p performed by doing
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
282 // p instances of smaller DFTs of size m,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
283 // each one takes a decimated version of the input
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
284 kf_work(Fout, f, fstride*p, factors, st);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
285 f += fstride;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
286 } while ((Fout += m) != Fout_end);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
287 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
288
5
c7237a7544eb cleanup
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 4
diff changeset
289 Fout = Fout_beg;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
290
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
291 // recombine the p smaller DFTs
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
292 switch (p) {
9
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
293 case 2:
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
294 kf_bfly2(Fout, fstride, st, m);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 7
diff changeset
295 break;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
296 case 3: kf_bfly3(Fout, fstride, st, m); break;
11
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 10
diff changeset
297 case 4:
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 10
diff changeset
298 {
12
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
299 //static unsigned counter = 0;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
300 // armv7_cycles_start();
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
301 // unsigned int t1 = armv7_cycles_read();
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
302 //printf("%08x %d %d\n", Fout, fstride, m);
11
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 10
diff changeset
303 kf_bfly4(Fout, fstride, st, m);
12
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
304 // unsigned int t2 = armv7_cycles_read();
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
305 // armv7_cycles_stop();
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
306 // counter++;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
307 // if (counter > 150 && counter < 160) printf("XX %d\n", t2-t1);
11
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 10
diff changeset
308 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 10
diff changeset
309 break;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
310 case 5: kf_bfly5(Fout, fstride, st, m); break;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
311 default: kf_bfly_generic(Fout, fstride, st, m, p); break;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
312 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
313 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
314
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
315 /*
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
316 * facbuf is populated by p1, m1, p2, m2, ...
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
317 * where
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
318 * p[i] * m[i] = m[i-1]
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
319 * m0 = n
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
320 */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
321 static void kf_factor(int n, int * facbuf) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
322 int p = 4;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
323 float floor_sqrt;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
324 floor_sqrt = floorf(sqrtf(n));
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
325
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
326 /* factor out powers of 4, powers of 2, then any remaining primes */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
327 do {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
328 while (n % p) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
329 switch (p) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
330 case 4: p = 2; break;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
331 case 2: p = 3; break;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
332 default: p += 2; break;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
333 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
334 if (p > floor_sqrt)
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
335 p = n; /* no more factors, skip to end */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
336 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
337 n /= p;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
338 *facbuf++ = p;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
339 *facbuf++ = n;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
340 } while (n > 1);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
341 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
342
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
343 /*
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
344 * User-callable function to allocate all necessary storage space for the fft.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
345 * The return value is a contiguous block of memory, allocated with malloc. As such,
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
346 * it can be freed with free(), rather than a peck_fft-specific function.
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
347 */
12
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
348 peck_fft_cfg peck_fft_alloc(int nfft, int inverse_fft, void *mem, size_t *lenmem) {
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
349 peck_fft_cfg st = NULL;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
350 size_t memneeded = sizeof(struct peck_fft_state)
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
351 + sizeof(peck_fft_cpx)*(nfft-1); /* twiddle factors */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
352
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
353 if (lenmem == NULL) {
12
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
354 st = (peck_fft_cfg) PECK_FFT_MALLOC(memneeded);
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
355 } else {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
356 if (mem != NULL && *lenmem >= memneeded)
12
Peter Meerwald <p.meerwald@bct-electronic.com>
parents: 11
diff changeset
357 st = (peck_fft_cfg) mem;
0
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
358 *lenmem = memneeded;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
359 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
360
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
361 if (st) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
362 int i;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
363 st->nfft=nfft;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
364 st->inverse = inverse_fft;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
365
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
366 for (i = 0; i < nfft; ++i) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
367 const float pi = 3.14159265359f;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
368 float phase = -2*pi*i / nfft;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
369 if (st->inverse)
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
370 phase *= -1;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
371 kf_cexp(st->twiddles+i, phase);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
372 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
373
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
374 kf_factor(nfft, st->factors);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
375 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
376 return st;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
377 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
378
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
379 void peck_fft(peck_fft_cfg cfg, const peck_fft_cpx *fin, peck_fft_cpx *fout) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
380 kf_work(fout, fin, 1, cfg->factors, cfg);
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
381 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
382
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
383 void peck_fft_cleanup(void) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
384 /* nothing needed any more */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
385 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
386
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
387 int peck_fft_next_fast_size(int n) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
388 while (1) {
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
389 int m = n;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
390 while ((m % 2) == 0) m /= 2;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
391 while ((m % 3) == 0) m /= 3;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
392 while ((m % 5) == 0) m /= 5;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
393 if (m <= 1)
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
394 break; /* n is completely factorable by twos, threes, and fives */
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
395 n++;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
396 }
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
397 return n;
Peter Meerwald <p.meerwald@bct-electronic.com>
parents:
diff changeset
398 }

Repositories maintained by Peter Meerwald, pmeerw@pmeerw.net.