1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
#include "fft.h"
#include <math.h>
#include <stdlib.h>
#define MaxFastBits 16
int **gFFTBitTable = NULL;
void FFT(int NumSamples,
gboolean InverseTransform,
float *RealIn, float *ImagIn, float *RealOut, float *ImagOut)
{
int NumBits; /* Number of bits needed to store indices */
int i, j, k, n;
int BlockSize, BlockEnd;
double angle_numerator = 2.0 * M_PI;
double tr, ti; /* temp real, temp imaginary */
/*
if (!IsPowerOfTwo(NumSamples)) {
fprintf(stderr, "%d is not a power of two\n", NumSamples);
exit(1);
}
*/
if (!gFFTBitTable)
InitFFT();
if (!InverseTransform)
angle_numerator = -angle_numerator;
NumBits = NumberOfBitsNeeded(NumSamples);
/*
** Do simultaneous data copy and bit-reversal ordering into outputs...
*/
for (i = 0; i < NumSamples; i++) {
j = FastReverseBits(i, NumBits);
RealOut[j] = RealIn[i];
ImagOut[j] = (ImagIn == NULL) ? 0.0 : ImagIn[i];
}
/*
** Do the FFT itself...
*/
BlockEnd = 1;
for (BlockSize = 2; BlockSize <= NumSamples; BlockSize <<= 1) {
double delta_angle = angle_numerator / (double) BlockSize;
double sm2 = sin(-2 * delta_angle);
double sm1 = sin(-delta_angle);
double cm2 = cos(-2 * delta_angle);
double cm1 = cos(-delta_angle);
double w = 2 * cm1;
double ar0, ar1, ar2, ai0, ai1, ai2;
for (i = 0; i < NumSamples; i += BlockSize) {
ar2 = cm2;
ar1 = cm1;
ai2 = sm2;
ai1 = sm1;
for (j = i, n = 0; n < BlockEnd; j++, n++) {
ar0 = w * ar1 - ar2;
ar2 = ar1;
ar1 = ar0;
ai0 = w * ai1 - ai2;
ai2 = ai1;
ai1 = ai0;
k = j + BlockEnd;
tr = ar0 * RealOut[k] - ai0 * ImagOut[k];
ti = ar0 * ImagOut[k] + ai0 * RealOut[k];
RealOut[k] = RealOut[j] - tr;
ImagOut[k] = ImagOut[j] - ti;
RealOut[j] += tr;
ImagOut[j] += ti;
}
}
BlockEnd = BlockSize;
}
/*
** Need to normalize if inverse transform...
*/
if (InverseTransform) {
float denom = (float) NumSamples;
for (i = 0; i < NumSamples; i++) {
RealOut[i] /= denom;
ImagOut[i] /= denom;
}
}
}
void InitFFT()
{
gFFTBitTable = malloc(MaxFastBits*sizeof(int));
int len = 2;
int b, i;
for (b=1; b<=MaxFastBits; b++) {
gFFTBitTable[b-1]=malloc(len*sizeof(int));
for (i=0; i<len; i++)
gFFTBitTable[b-1][i] = ReverseBits(i, b);
len <<= 1;
}
}
int NumberOfBitsNeeded(int PowerOfTwo)
{
int i;
/*
if (PowerOfTwo < 2) {
fprintf(stderr, "Error: FFT called with size %d\n", PowerOfTwo);
exit(1);
}
*/
for (i = 0;; i++)
if (PowerOfTwo & (1 << i))
return i;
}
inline int FastReverseBits(int i, int NumBits)
{
if (NumBits <= MaxFastBits)
return gFFTBitTable[NumBits - 1][i];
else
return ReverseBits(i, NumBits);
}
int ReverseBits(int index, int NumBits)
{
int i, rev;
for (i = rev = 0; i < NumBits; i++) {
rev = (rev << 1) | (index & 1);
index >>= 1;
}
return rev;
}
|
