#!/bin/sh: This is a shar archive.  Extract with sh, not csh.: This archive ends with exit, so do not worry about trailing junk.: --------------------------- cut here --------------------------PATH=/bin:/usr/bin:/usr/ucbif test -f 'fft'then	echo Removing   'fft'	rm 'fft'fiif test -d 'fft'then	:else	echo Creating   'fft'	mkdir 'fft'fichmod 'u=rwx,g=rx,o=rx' 'fft'echo Extracting 'fft/README'sed 's/^X//' > 'fft/README' << '+ END-OF-FILE ''fft/README'XThis directory contains the packages realfft(3) and fft(3) that do Cooley-TukeyXfast Fourier transform on an arbitrary number of real or complex samples,Xrespectively.XXThe package was tested on 4.[12] bsd & Sun Release 3.5, but it should work onXany UNIX system featuring sin(3M) and malloc(3).XXContents:X	complex.h	- include file (for users of fft(3) routines).X	fft		- manual and source of fft(3).X	realfft		- manual and source of realfft(3).X	example		- example of how to use realfft(3).XXSee the README's in fft/, realfft/ and example/ to find out how to compile andXuse things.+ END-OF-FILE fft/READMEchmod 'u=rw,g=r,o=r' 'fft/README'set `wc -c 'fft/README'`count=$1case $count in585)	:;;*)	echo 'Bad character count in ''fft/README' >&2		echo 'Count should be 585' >&2esacif test -f 'fft/complex'then	echo Removing   'fft/complex'	rm 'fft/complex'fiif test -d 'fft/complex'then	:else	echo Creating   'fft/complex'	mkdir 'fft/complex'fichmod 'u=rwx,g=rx,o=rx' 'fft/complex'echo Extracting 'fft/complex/Makefile'sed 's/^X//' > 'fft/complex/Makefile' << '+ END-OF-FILE ''fft/complex/Makefile'XLTYPE=A18XTARGET=fft.aXCFLAGS=-OXPREFLAGS=XIDIRS=-I../XLLIBS=XXLINT=lint -uhbaxpcXCTAGS=ctagsXPRINT=@pr -tXXCFILES=\X	fourier.c\X	ft.c\X	w.cXHFILES=\X	/usr/include/math.h\X	../complex.h\X	w.hXOBJECTS=\X	fourier.o\X	ft.o\X	w.oXX.SUFFIXES: .iXX$(TARGET):	$(OBJECTS)X	ar rv $@ $?X	ranlib $@XXlint:X	$(LINT) $(PREFLAGS) $(IDIRS) $(CFILES) $(LLIBS) -lcXXtags:	$(HFILES) $(CFILES)X	$(CTAGS) $(HFILES) $(CFILES)XXprint:	fft.manX	$(PRINT) fft.man tech complex.h w.h $(CFILES)XXfft.man:	fft.3X	@nroff -man fft.3 > fft.manXX.c.o:X	$(CC) $(CFLAGS) -c $(IDIRS) $<XX.c.i:X	$(CC) $(CFLAGS) -P $(IDIRS) $<XX.c.s:X	$(CC) $(CFLAGS) -S $(IDIRS) $<XXfourier.o:\X	../complex.h\X	w.hXXft.o:\X	../complex.h\X	w.hXXw.o:\X	../complex.h\X	w.h\X	/usr/include/math.h\+ END-OF-FILE fft/complex/Makefilechmod 'u=rw,g=r,o=r' 'fft/complex/Makefile'set `wc -c 'fft/complex/Makefile'`count=$1case $count in741)	:;;*)	echo 'Bad character count in ''fft/complex/Makefile' >&2		echo 'Count should be 741' >&2esacecho Extracting 'fft/complex/README'sed 's/^X//' > 'fft/complex/README' << '+ END-OF-FILE ''fft/complex/README'XThis fft(3) package does Cooley-Tukey fast Fourier transform on an arbitraryXnumber of complex samples.XXHow to make the stuff:X	make		- create library "fft.a"X	make fft.man	- nroff manual page "fft.3" into "fft.man"X	make print	- print source, "tech" and "fft.man"XXFile "tech" contains a short description of the functions and variables in theXimplementation.XXPrograms using fft(3), should include "../complex.h" and be loaded (ld(1)) withXlibraries "fft.a" and "/usr/lib/libm.a".  The package also uses malloc(3) ofXthe standard C-library.+ END-OF-FILE fft/complex/READMEchmod 'u=rw,g=r,o=r' 'fft/complex/README'set `wc -c 'fft/complex/README'`count=$1case $count in544)	:;;*)	echo 'Bad character count in ''fft/complex/README' >&2		echo 'Count should be 544' >&2esacecho Extracting 'fft/complex/fft.3'sed 's/^X//' > 'fft/complex/fft.3' << '+ END-OF-FILE ''fft/complex/fft.3'X.TH FFT 3X.SH NAMEXfft, rft \- forward and reverse complex fourier transformX.SH SYNOPSISX.nfX#include "complex.h"XXfft (in, n, out)XCOMPLEX *in;Xunsigned n;XCOMPLEX *out;XXrft (in, n, out)XCOMPLEX *in;Xunsigned n;XCOMPLEX *out;XXc_re (c)XCOMPLEX c;XXc_im (c)XCOMPLEX c;X.fiX.SH DESCRIPTIONX.IXFftXandX.I rftXperform, respectively, forward and reverse discreteXfast fourier transform on theX.I nX(an arbitrary number) complexXsamples of arrayX.IR in .XThe result is placed inX.IR out .X.brXThe functions are a recursive implementation of the Cooley-Tukey algorithm.XBoth use OX.RI ( nX*X.RI ( p1X+ .. +X.IR pk ))Xoperations, whereX.I piXis theX.IR i -thXfactor in theXprime-decomposition of sizeX.I kXofX.IR n .X.brXBoth functions compute a sine/cosine table internally.XThis table is not recomputed on successive calls with the sameX.IR n .XX.I C_reXandX.I c_imXare C preprocessor defines that yield the real and imaginaryXparts ofX.IR c ,Xrespectively.XThey are used to assign and inspect arraysX.I inXandX.IR out .X.SH FILESXfft.a \- library containing fft and rft.X.brX/usr/lib/libm.a \- library used by fft.a.X.SH DIAGNOSTICSX.I FftXandX.I rftXreturn -1 if allocating space for the internal table fails, else 0.X.SH BUGSXThe original contents ofX.I inXare destroyed.XXThe transform isn't optimized for interesting special cases ofX.IR n ,Xe.g.\&X.I nXis a power of 2, although it will work in OX.RI ( nX* 2logX.RI ( n )).XXThe error for a forward-reverse sequence is about 10e-13 forX.I nX= 1024.X.SH AUTHORXPeter Valkenburg (valke@cs.vu.nl).+ END-OF-FILE fft/complex/fft.3chmod 'u=rw,g=r,o=r' 'fft/complex/fft.3'set `wc -c 'fft/complex/fft.3'`count=$1case $count in1548)	:;;*)	echo 'Bad character count in ''fft/complex/fft.3' >&2		echo 'Count should be 1548' >&2esacecho Extracting 'fft/complex/fourier.c'sed 's/^X//' > 'fft/complex/fourier.c' << '+ END-OF-FILE ''fft/complex/fourier.c'X/*X * "fourier.c", Pjotr '87.X */XX#include	<complex.h>X#include	"w.h"XX/*X * Recursive (reverse) complex fast Fourier transform on the nX * complex samples of array in, with the Cooley-Tukey method.X * The result is placed in out.  The number of samples, n, is arbitrary.X * The algorithm costs O (n * (r1 + .. + rk)), where k is the numberX * of factors in the prime-decomposition of n (also the maximumX * depth of the recursion), and ri is the i-th primefactor.X */XFourier (in, n, out)XCOMPLEX *in;Xunsigned n;XCOMPLEX *out;X{X	unsigned r;X	unsigned radix ();XX	if ((r = radix (n)) < n)X		split (in, r, n / r, out);X	join (in, n / r, n, out);X}XX/*X * Give smallest possible radix for n samples.X * Determines (in a rude way) the smallest primefactor of n.X */Xstatic unsigned radix (n)Xunsigned n;X{X	unsigned r;XX	if (n < 2)X		return 1;XX	for (r = 2; r < n; r++)X		if (n % r == 0)X			break;X	return r;X}XX/*X * Split array in of r * m samples in r parts of each m samples,X * such that in [i] goes to out [(i % r) * m + (i / r)].X * Then call for each part of out Fourier, so the r recursivelyX * transformed parts will go back to in.X */Xstatic split (in, r, m, out)XCOMPLEX *in;Xregister unsigned r, m;XCOMPLEX *out;X{X	register unsigned k, s, i, j;XX	for (k = 0, j = 0; k < r; k++)X		for (s = 0, i = k; s < m; s++, i += r, j++)X			out [j] = in [i];XX	for (k = 0; k < r; k++, out += m, in += m)X		Fourier (out, m, in);X}XX/*X * Sum the n / m parts of each m samples of in to n samples in out.X * 		   r - 1X * Out [j] becomes  sum  in [j % m] * W (j * k).  Here in is the k-thX * 		   k = 0   k	       n		 kX * part of in (indices k * m ... (k + 1) * m - 1), and r is the radix.X * For k = 0, a complex multiplication with W (0) is avoided.X */Xstatic join (in, m, n, out)XCOMPLEX *in;Xregister unsigned m, n;XCOMPLEX *out;X{X	register unsigned i, j, jk, s;XX	for (s = 0; s < m; s++)X		for (j = s; j < n; j += m) {X			out [j] = in [s];X			for (i = s + m, jk = j; i < n; i += m, jk += j)X				c_add_mul (out [j], in [i], W (n, jk));X		}X}+ END-OF-FILE fft/complex/fourier.cchmod 'u=rw,g=r,o=r' 'fft/complex/fourier.c'set `wc -c 'fft/complex/fourier.c'`count=$1case $count in2046)	:;;*)	echo 'Bad character count in ''fft/complex/fourier.c' >&2		echo 'Count should be 2046' >&2esacecho Extracting 'fft/complex/ft.c'sed 's/^X//' > 'fft/complex/ft.c' << '+ END-OF-FILE ''fft/complex/ft.c'X/*X * "ft.c", Pjotr '87.X */XX#include	<complex.h>X#include	"w.h"XX/*X * Forward Fast Fourier Transform on the n samples of complex array in.X * The result is placed in out.  The number of samples, n, is arbitrary.X * The W-factors are calculated in advance.X */Xint fft (in, n, out)XCOMPLEX *in;Xunsigned n;XCOMPLEX *out;X{X	unsigned i;XX	for (i = 0; i < n; i++)X		c_conj (in [i]);X	X	if (W_init (n) == -1)X		return -1;XX	Fourier (in, n, out);XX	for (i = 0; i < n; i++) {X		c_conj (out [i]);X		c_realdiv (out [i], n);X	}XX	return 0;X}XX/*X * Reverse Fast Fourier Transform on the n complex samples of array in.X * The result is placed in out.  The number of samples, n, is arbitrary.X * The W-factors are calculated in advance.X */Xrft (in, n, out)XCOMPLEX *in;Xunsigned n;XCOMPLEX *out;X{X	if (W_init (n) == -1)X		return -1;XX	Fourier (in, n, out);XX	return 0;X}+ END-OF-FILE fft/complex/ft.cchmod 'u=rw,g=r,o=r' 'fft/complex/ft.c'set `wc -c 'fft/complex/ft.c'`count=$1case $count in865)	:;;*)	echo 'Bad character count in ''fft/complex/ft.c' >&2		echo 'Count should be 865' >&2esacecho Extracting 'fft/complex/tech'sed 's/^X//' > 'fft/complex/tech' << '+ END-OF-FILE ''fft/complex/tech'X	Short technical description of functions in the fft(3) packageXXX"ft.c"XThe entry-points:X	fft	- Forward Complex Fast Fourier TransformX	rft	- Reverse Complex Fast Fourier TransformXX"fourier.c"XRecursive implementation of the Cooley-Tukey algorithm:X	Fourier	- top level callX	radix	- determine radix for a number of samplesX	split	- split samples in groups, and recursively call FourierX	join	- join (add) groups of samples into a new groupXX"complex.h"XManipulation of complex numbers:X	COMPLEX	- type for complex numbersX	c_re	- real part of complex numberX	c_im	- imaginary part of complex numberX	c_add_mul - multiply and add complex numbersX	c_conj	- convert a complex number into its conjugateX	c_realdiv - divide a complex by a real numberXX"w.h"XW-factors:X	W	- give previously calculated W-factorXX"w.c"XComputation of W-factors:X	W_factors - array of W-factorsX	Nfactors - number of factors in W_factorsX	W_init	- prepare W-factors array+ END-OF-FILE fft/complex/techchmod 'u=rw,g=r,o=r' 'fft/complex/tech'set `wc -c 'fft/complex/tech'`count=$1case $count in951)	:;;*)	echo 'Bad character count in ''fft/complex/tech' >&2		echo 'Count should be 951' >&2esacecho Extracting 'fft/complex/w.c'sed 's/^X//' > 'fft/complex/w.c' << '+ END-OF-FILE ''fft/complex/w.c'X/*X * "w.c", Pjotr '87.X */XX#include	<complex.h>X#include	"w.h"X#include	<math.h>XXCOMPLEX *W_factors = 0;		/* array of W-factors */Xunsigned Nfactors = 0;		/* number of entries in W-factors */XX/*X * W_init puts Wn ^ k (= e ^ (2pi * i * k / n)) in W_factors [k], 0 <= k < n.X * If n is equal to Nfactors then nothing is done, so the same W_factorsX * array can used for several transforms of the same number of samples.X * Notice the explicit calculation of sines and cosines, an iterative approachX * introduces substantial errors.X */Xint W_init (n)Xunsigned n;X{X	char *malloc ();X#	define pi	3.1415926535897932384626434X	unsigned k;XX	if (n == Nfactors)X		return 0;X	if (Nfactors != 0 && W_factors != 0)X		free ((char *) W_factors);X	if ((Nfactors = n) == 0)X		return 0;X	if ((W_factors = (COMPLEX *) malloc (n * sizeof (COMPLEX))) == 0)X		return -1;XX	for (k = 0; k < n; k++) {X		c_re (W_factors [k]) = cos (2 * pi * k / n);X		c_im (W_factors [k]) = sin (2 * pi * k / n);X	}XX	return 0;X}+ END-OF-FILE fft/complex/w.cchmod 'u=rw,g=r,o=r' 'fft/complex/w.c'set `wc -c 'fft/complex/w.c'`