File: newfft.C

package info (click to toggle)
mixviews 1.10-3
  • links: PTS
  • area: main
  • in suites: hamm
  • size: 2,440 kB
  • ctags: 6,314
  • sloc: cpp: 31,647; ansic: 2,100; makefile: 1,782; sh: 17
file content (174 lines) | stat: -rw-r--r-- 4,868 bytes parent folder | download | duplicates (3)
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <math.h>

/******************************************************************************
 *
 *  MiXViews - an X window system based sound & data editor/processor
 *
 *  Copyright (c) 1993, 1994 Regents of the University of California
 *
 *  Author:     Douglas Scott
 *  Date:       December 13, 1994
 *
 *  Permission to use, copy and modify this software and its documentation
 *  for research and/or educational purposes and without fee is hereby granted,
 *  provided that the above copyright notice appear in all copies and that
 *  both that copyright notice and this permission notice appear in
 *  supporting documentation. The author reserves the right to distribute this
 *  software and its documentation.  The University of California and the author
 *  make no representations about the suitability of this software for any 
 *  purpose, and in no event shall University of California be liable for any
 *  damage, loss of data, or profits resulting from its use.
 *  It is provided "as is" without express or implied warranty.
 *
 ******************************************************************************/


void rfft(float*, int, int);
void cfft(float*, int, int);

double twopi = M_PI * 2.0;
double pi = M_PI;

/* If forward is true, rfft replaces 2*N real data points in buf with
	 N complex values representing the positive frequency half of their
	 Fourier spectrum, with *(buf+1) replaced with the real part of the Nyquist
	 frequency value.	If forward is false, rfft expects buf to contain a
	 positive frequency spectrum arranged as before, and replaces it with
	 2*N real values.	N MUST be a power of 2. */

void
rfft(float* buf, int N2, int forward) {
	float 	c2,
		h1r,h1i,
		h2r,h2i,
		temp;
	float 	br,bi;

	float theta = pi/N2;
	float wr = 1.;
	float wi = 0.;
	float c1 = 0.5;
	if ( forward ) {
		c2 = -0.5;
		cfft(buf, N2, forward);
		br = *buf;
		bi = *(buf+1);
	}
	else {
		c2 = 0.5;
		theta = -theta;
		br = *(buf+1);
		bi = 0.;
		*(buf+1) = 0.;
	}
	float wpr = -2. * pow( sin( 0.5*theta ), 2. );
	float wpi = sin(theta);
	int N2p1 = (N2 <<1) + 1;
	for (int i = 0; i <= N2 >> 1; i++) {
		int i1 = i<<1;
		int i2 = i1 + 1;
		int i3 = N2p1 - i2;
		int i4 = i3 + 1;
		if ( i == 0 ) {
			h1r =	c1 * ( *(buf+i1) + br );
			h1i =	c1 * ( *(buf+i2) - bi );
			h2r = -c2 * ( *(buf+i2) + bi );
			h2i =	c2 * ( *(buf+i1) - br );
			*(buf+i1) =	h1r + (wr * h2r) - (wi * h2i);
			*(buf+i2) =	h1i + (wr * h2i) + (wi * h2r);
			br =	h1r - (wr * h2r) + (wi * h2i);
			bi = -h1i + (wr * h2i) + (wi * h2r);
		}
		else {
			h1r =	c1 * ( *(buf+i1) + *(buf+i3) );
			h1i =	c1 * ( *(buf+i2) - *(buf+i4) );
			h2r = -c2 * ( *(buf+i2) + *(buf+i4) );
			h2i =	c2 * ( *(buf+i1) - *(buf+i3) );
			*(buf+i1) =	h1r + wr*h2r - wi*h2i;
			*(buf+i2) =	h1i + wr*h2i + wi*h2r;
			*(buf+i3) =	h1r - wr*h2r + wi*h2i;
			*(buf+i4) = -h1i + wr*h2i + wi*h2r;
		}
		wr = ((temp = wr) * wpr) - (wi * wpi) + wr;
		wi = (wi * wpr) + (temp * wpi) + wi;
	}
	if ( forward )
		*(buf+1) = br;
	else
		cfft(buf, N2, forward);
}

/* cfft replaces float array x containing NC complex values
	 (2*NC float values alternating real, imagininary, etc.)
	 by its Fourier transform if forward is true, or by its
	 inverse Fourier transform if forward is false, using a
	 recursive Fast Fourier transform method due to Danielson
	 and Lanczos.	NC MUST be a power of 2. */

void bitreverse(float *, int);

void
cfft(float* buf, int N2, int forward) {
	int delta;
	int ND = N2<<1;
	
	bitreverse( buf, ND );

	for ( int mmax = 2; mmax < ND; mmax = delta ) {
		delta = mmax<<1;
		float theta = twopi / ( forward? mmax : -mmax );
		float wpr = -2. * pow( sin( 0.5*theta ), 2. );
		float wpi = sin(theta);
		float wr = 1.;
		float wi = 0.;
		
		for ( int m = 0; m < mmax; m += 2 ) {
			float rtemp, itemp;
			for ( int i = m; i < ND; i += delta ) {
				int j = i + mmax;
				rtemp = ( wr * *(buf+j) ) - ( wi * *(buf+j+1) );
				itemp = ( wr * *(buf+j+1) ) + ( wi * *(buf+j) );
				*(buf+j) = *(buf+i) - rtemp;
				*(buf+j+1) = *(buf+i+1) - itemp;
				*(buf+i) += rtemp;
				*(buf+i+1) += itemp;
			}
			wr = ((rtemp = wr) * wpr) - (wi * wpi) + wr;
			wi = (wi * wpr) + (rtemp * wpi) + wi;
		}
	}

/* scale output */

//	float scale = forward ? 1./ND : 2.;		/* this is the original */
	float scale = forward ? 1.0 : 1.0/ND;
	
	if(scale != 1.0) { 
		register float *bi=buf, *be=buf + ND;
		while ( bi < be )
			*bi++ *= scale;
	}
}

// bitreverse places float array x containing N/2 complex values
//	 into bit-reversed order

void
bitreverse(float* buf, int N) {
	int i,j,m;

	for ( i = j = 0; i < N; i += 2, j += m ) {
		if ( j > i ) {
			float rtemp = *(buf+j);	/* complex exchange */
			float itemp = *(buf+j+1);
			
			*(buf+j) = *(buf+i);
			*(buf+j+1) = *(buf+i+1);
			
			*(buf+i) = rtemp;
			*(buf+i+1) = itemp;
		}
		for ( m = N>>1; m >= 2 && j >= m; m >>= 1 )
			j -= m;
	}
}