1 /*****************************************************************************/
3 /* Fast Fourier Transform */
4 /* Network Abstraction, Definitions */
5 /* Kevin Peterson, MIT Media Lab, EMS */
7 /* REV: 6/12/87(KHP) - To incorporate link list of different sized networks */
9 /*****************************************************************************/
11 /*****************************************************************************/
12 /* added debug option 5/91 brown@nadia */
13 /* change sign at AAA */
15 /* Fast Fourier Transform */
16 /* FFT Network Interaction and Support Modules */
17 /* Kevin Peterson, MIT Media Lab, EMS */
19 /* REV: 6/12/87(KHP) - Generalized to one procedure call with typed I/O */
21 /*****************************************************************************/
25 My realization of the FFT involves a representation of a network of
26 "butterfly" elements that takes a set of 'N' sound samples as input and
27 computes the discrete Fourier transform. This network consists of a
28 series of stages (log2 N), each stage consisting of N/2 parallel butterfly
29 elements. Consecutive stages are connected by specific, predetermined flow
30 paths, (see Oppenheim, Schafer for details) and each butterfly element has
31 an associated multiplicative coefficient.
35 ____ _ ____ _ ____ _ ____ _ ____
36 o--| |o-| |-o| |o-| |-o| |o-| |-o| |o-| |-o| |--o
37 |reg1| | | |W^r1| | | |reg1| | | |W^r1| | | |reg1|
38 | | | | | | | | | | | | | | | | | | .....
39 | | | | | | | | | | | | | | | | | |
40 o--|____|o-| |-o|____|o-| |-o|____|o-| |-o|____|o-| |-o|____|--o
43 ____ | | ____ | | ____ | | ____ | | ____
44 o--| |o-| |-o| |o-| |-o| |o-| |-o| |o-| |-o| |--o
45 |reg2| | | |W^r2| | | |reg2| | | |W^r2| | | |reg2|
46 | | | | | | | | | | | | | | | | | | .....
47 | | | | | | | | | | | | | | | | | |
48 o--|____|o-| |-o|____|o-| |-o|____|o-| |-o|____|o-| |-o|____|--o
57 ____ | | ____ | | ____ | | ____ | | ____
58 o--| |o-| |-o| |o-| |-o| |o-| |-o| |o-| |-o| |--o
59 |reg | | | |W^r | | | |reg | | | |W^r | | | |reg |
60 | N/2| | | | N/2| | | | N/2| | | | N/2| | | | N/2| .....
61 | | | | | | | | | | | | | | | | | |
62 o--|____|o-|_|-o|____|o-|_|-o|____|o-|_|-o|____|o-|_|-o|____|--o
65 Initial | Bttrfly | Rd/Wrt | Bttrfly | Rd/Wrt
66 Buffer | | Register | | Register
67 |____________|____________|____________|
73 The use of "in-place" computation permits one to use only one set of
74 registers realized by an array of complex number structures. To describe
75 the coefficients for each butterfly I am using a two dimensional array
76 (stage, butterfly) of complex numbers. The predetermined stage connections
77 will be described in a two dimensional array of indicies. These indicies
78 will be used to determine the order of reading at each stage of the
83 /*****************************************************************************/
85 /*****************************************************************************/
89 #include "../../pdbox.h"
96 /* the following is needed only to declare pd_fft() as exportable in MSW */
99 /* some basic definitions */
106 #define SAMPLE float /* data type used in calculation */
108 #define SHORT_SIZE sizeof(short)
109 #define INT_SIZE sizeof(int)
110 #define FLOAT_SIZE sizeof(float)
111 #define SAMPLE_SIZE sizeof(SAMPLE)
112 #define PNTR_SIZE sizeof(char *)
115 #define TWO_PI 6.2831854
117 /* type definitions for I/O buffers */
118 #define REAL 0 /* real only */
119 #define IMAG 2 /* imaginary only */
120 #define RECT 8 /* real and imaginary */
121 #define MAG 16 /* magnitude only */
122 #define PHASE 32 /* phase only */
123 #define POLAR 64 /* magnitude and phase*/
125 /* scale definitions for I/O buffers */
127 #define DB 1 /* 20log10 */
129 /* transform direction definition */
130 #define FORWARD 1 /* Forward FFT */
131 #define INVERSE 2 /* Inverse FFT */
133 /* window type definitions */
135 #define RECTANGULAR 0
139 /* network structure definition */
141 typedef struct Tfft_net
{
148 SAMPLE
*window
, *inv_window
;
155 SAMPLE
*coeffr
, *inv_coeffr
;
156 SAMPLE
*coeffi
, *inv_coeffi
;
157 struct Tfft_net
*next
;
161 void cfft(int trnsfrm_dir
, int npnt
, int window
,
162 float *source_buf
, int source_form
, int source_scale
,
163 float *result_buf
, int result_form
, int result_scale
, int debug
);
166 /*****************************************************************************/
167 /* GLOBAL DECLARATIONS */
168 /*****************************************************************************/
170 static FFT_NET
*firstnet
;
174 void net_alloc(FFT_NET
*fft_net
);
175 void net_dealloc(FFT_NET
*fft_net
);
176 int power_of_two(int n
);
177 void create_hanning(SAMPLE
*window
, int n
, SAMPLE scale
);
178 void create_rectangular(SAMPLE
*window
, int n
, SAMPLE scale
);
179 void short_to_float(short *short_buf
, float *float_buf
, int n
);
180 void load_registers(FFT_NET
*fft_net
, float *buf
, int buf_form
,
181 int buf_scale
, int trnsfrm_dir
);
182 void compute_fft(FFT_NET
*fft_net
);
183 void store_registers(FFT_NET
*fft_net
, float *buf
, int buf_form
,
184 int buf_scale
, int debug
);
185 void build_fft_network(FFT_NET
*fft_net
, int n
, int window_type
);
187 /*****************************************************************************/
188 /* GENERALIZED FAST FOURIER TRANSFORM MODULE */
189 /*****************************************************************************/
191 void cfft(int trnsfrm_dir
, int npnt
, int window
,
192 float *source_buf
, int source_form
, int source_scale
,
193 float *result_buf
, int result_form
, int result_scale
, int debug
)
195 /* modifies: result_buf
196 effects: Computes npnt FFT specified by form, scale, and dir parameters.
197 Source samples (single precision float) are taken from soure_buf and
198 the transfrmd representation is stored in result_buf (single precision
199 float). The parameters are defined as follows:
201 trnsfrm_dir = FORWARD | INVERSE
202 npnt = 2^k for some any positive integer k
203 window = HANNING | RECTANGULAR
204 (RECT = real and imag parts, POLAR = magnitude and phase)
205 source_form = REAL | IMAG | RECT | POLAR
206 result_form = REAL | IMAG | RECT | MAG | PHASE | POLAR
207 xxxxxx_scale= LINEAR | DB ( 20log10 |mag| )
209 The input/output buffers are stored in a form appropriate to the type.
210 For example: REAL => {real, real, real ...},
211 MAG => {mag, mag, mag, ... },
212 RECT => {real, imag, real, imag, ... },
213 POLAR => {mag, phase, mag, phase, ... }.
215 To look at the magnitude (in db) of a 1024 point FFT of a real time
218 fft(FORWARD, 1024, RECTANGULAR, input, REAL, LINEAR, output, MAG, DB)
220 All possible input and output combinations are possible given the
221 choice of type and scale parameters.
225 FFT_NET
*thisnet
= (FFT_NET
*)0;
226 FFT_NET
*lastnet
= (FFT_NET
*)0;
228 /* A linked list of fft networks of different sizes is maintained to
229 avoid building with every call. The network is built on the first
230 call but reused for subsequent calls requesting the same size
236 if (!(thisnet
->n
== npnt
) || !(thisnet
->window_type
== window
)) {
237 /* current net doesn't match size or window type */
239 thisnet
=thisnet
->next
;
240 continue; /* keep looking */
243 else { /* network matches desired size */
244 load_registers(thisnet
, source_buf
, source_form
, source_scale
,
246 compute_fft(thisnet
); /* do transformation */
247 store_registers(thisnet
, result_buf
, result_form
, result_scale
,debug
);
252 /* none of existing networks match required size*/
254 if (lastnet
) { /* add new network to end of list */
255 thisnet
= (FFT_NET
*)malloc(sizeof(FFT_NET
)); /* allocate */
257 lastnet
->next
= thisnet
; /* add to end of list */
259 else { /* first network to be created */
260 thisnet
=firstnet
=(FFT_NET
*)malloc(sizeof(FFT_NET
)); /* alloc. */
264 /* build new network and compute transformation */
265 build_fft_network(thisnet
, npnt
, window
);
266 load_registers(thisnet
, source_buf
, source_form
, source_scale
,
268 compute_fft(thisnet
);
269 store_registers(thisnet
, result_buf
, result_form
, result_scale
,debug
);
275 /* effects: Deallocates all preserved FFT networks. Should be used when
276 finished with all computations.
280 FFT_NET
*thisnet
, *nextnet
;
285 nextnet
= thisnet
->next
;
286 net_dealloc(thisnet
);
287 free((char *)thisnet
);
288 } while ((thisnet
= nextnet
));
293 /*****************************************************************************/
294 /* NETWORK CONSTRUCTION */
295 /*****************************************************************************/
297 void build_fft_network(FFT_NET
*fft_net
, int n
, int window_type
)
301 effects: Constructs the fft network as described in fft.h. Butterfly
302 coefficients, read/write indicies, bit reversed load indicies,
303 and array allocations are computed.
309 int **p
, **q
, *pp
, *qp
;
310 SAMPLE two_pi_div_n
= TWO_PI
/ n
;
313 /* network definition */
315 fft_net
->bps
= bps
= n
/2;
316 for (i
= 0, j
= n
; j
> 1; j
>>= 1, i
++);
317 fft_net
->stages
= stages
= i
;
318 fft_net
->direction
= FORWARD
;
319 fft_net
->window_type
= window_type
;
320 fft_net
->next
= (FFT_NET
*)0;
322 /* allocate registers, index, coefficient arrays */
326 /* create appropriate windows */
327 if (window_type
==HANNING
) {
328 create_hanning(fft_net
->window
, n
, 1.);
329 create_hanning(fft_net
->inv_window
, n
, 1./n
);
332 create_rectangular(fft_net
->window
, n
, 1.);
333 create_rectangular(fft_net
->inv_window
, n
, 1./n
);
337 /* calculate butterfly coefficients */ {
339 int num_diff_coeffs
, power_inc
, power
;
340 SAMPLE
*coeffpr
= fft_net
->coeffr
;
341 SAMPLE
*coeffpi
= fft_net
->coeffi
;
342 SAMPLE
*inv_coeffpr
= fft_net
->inv_coeffr
;
343 SAMPLE
*inv_coeffpi
= fft_net
->inv_coeffi
;
345 /* stage one coeffs are 1 + 0j */
346 for (i
= 0; i
< bps
; i
++) {
347 *coeffpr
= *inv_coeffpr
= 1.;
348 *coeffpi
= *inv_coeffpi
= 0.;
349 coeffpr
++; inv_coeffpr
++;
350 coeffpi
++; inv_coeffpi
++;
353 /* stage 2 to last stage coeffs need calculation */
355 for (s
= 2; s
<= stages
; s
++) {
357 num_diff_coeffs
= n
/ (1 << (stages
- s
+ 1));
358 power_inc
= 1 << (stages
-s
);
361 for (i
= bps
/num_diff_coeffs
; i
> 0; i
--) {
365 for (j
= num_diff_coeffs
; j
> 0; j
--) {
366 *coeffpr
= cos(two_pi_div_n
*power
);
367 *inv_coeffpr
= cos(two_pi_div_n
*power
);
368 /* AAA change these signs */ *coeffpi
= -sin(two_pi_div_n
*power
);
369 /* change back */ *inv_coeffpi
= sin(two_pi_div_n
*power
);
371 coeffpr
++; inv_coeffpr
++;
372 coeffpi
++; inv_coeffpi
++;
378 /* calculate network indicies: stage exchange indicies are
379 calculated and then used as offset values from the base
380 register locations. The final addresses are then stored in
385 SAMPLE
**indexpr
= fft_net
->indexpr
;
386 SAMPLE
**indexpi
= fft_net
->indexpi
;
387 SAMPLE
**indexqr
= fft_net
->indexqr
;
388 SAMPLE
**indexqi
= fft_net
->indexqi
;
389 SAMPLE
*regr
= fft_net
->regr
;
390 SAMPLE
*regi
= fft_net
->regi
;
393 /* allocate temporary 2d stage exchange index, 1d temp
395 p
= (int **)malloc(stages
* PNTR_SIZE
);
396 q
= (int **)malloc(stages
* PNTR_SIZE
);
398 for (s
= 0; s
< stages
; s
++) {
399 p
[s
] = (int *)malloc(bps
* INT_SIZE
);
400 q
[s
] = (int *)malloc(bps
* INT_SIZE
);
403 /* calculate stage exchange indicies: */
404 for (s
= 0; s
< stages
; s
++) {
408 cntr
= 1 << (stages
-s
-1);
421 /* compute actual address values using indicies as offsets */
422 for (s
= 0; s
< stages
; s
++) {
423 for (i
= 0; i
< bps
; i
++) {
424 *indexpr
++ = regr
+ p
[s
][i
];
425 *indexpi
++ = regi
+ p
[s
][i
];
426 *indexqr
++ = regr
+ q
[s
][i
];
427 *indexqi
++ = regi
+ q
[s
][i
];
433 /* calculate load indicies (bit reverse ordering) */
434 /* bit reverse ordering achieved by passing normal
435 order indicies backwards through the network */
437 /* init to normal order indicies */ {
438 int *load_index
,*load_indexp
;
439 int *temp_indexp
, *temp_index
;
440 temp_index
=temp_indexp
=(int *)malloc(n
* INT_SIZE
);
443 load_index
= load_indexp
= fft_net
->load_index
;
446 *load_indexp
++ = i
++;
448 /* pass indicies backwards through net */
449 for (s
= stages
- 1; s
> 0; s
--) {
453 for (i
= 0; i
< bps
; i
++) {
454 temp_index
[pp
[i
]]=load_index
[2*i
];
455 temp_index
[qp
[i
]]=load_index
[2*i
+1];
458 load_indexp
= load_index
;
459 temp_indexp
= temp_index
;
461 *load_indexp
++ = *temp_indexp
++;
464 /* free all temporary arrays */
465 free((char *)temp_index
);
466 for (s
= 0; s
< stages
; s
++) {
467 free((char *)p
[s
]);free((char *)q
[s
]);
469 free((char *)p
);free((char *)q
);
475 /*****************************************************************************/
476 /* REGISTER LOAD AND STORE */
477 /*****************************************************************************/
479 void load_registers(FFT_NET
*fft_net
, float *buf
, int buf_form
,
480 int buf_scale
, int trnsfrm_dir
)
482 /* effects: Multiplies the input buffer with the appropriate window and
483 stores the resulting values in the initial registers of the
484 network. Input buffer must contain values appropriate to form.
485 For RECT, the buffer contains real num. followed by imag num,
486 and for POLAR, it contains magnitude followed by phase. Pure
487 inputs are listed normally. Both LINEAR and DB scales are
492 int *load_index
= fft_net
->load_index
;
494 SAMPLE
*window
= NULL
;
498 int index
, i
= 0, n
= fft_net
->n
;
501 if (trnsfrm_dir
==FORWARD
) window
= fft_net
->window
;
502 else if (trnsfrm_dir
==INVERSE
) window
= fft_net
->inv_window
;
505 fprintf(stderr
, "load_registers:illegal transform direction\n");
509 fft_net
->direction
= trnsfrm_dir
;
515 case REAL
: { /* pure REAL */
516 while (i
< fft_net
->n
) {
517 index
= load_index
[i
];
518 fft_net
->regr
[i
]=(SAMPLE
)buf
[index
] * window
[index
];
524 case IMAG
: { /* pure IMAGinary */
525 while (i
< fft_net
->n
) {
526 index
= load_index
[i
];
528 fft_net
->regi
[i
]=(SAMPLE
)buf
[index
] * window
[index
];
533 case RECT
: { /* both REAL and IMAGinary */
534 while (i
< fft_net
->n
) {
535 index
= load_index
[i
];
536 fft_net
->regr
[i
]=(SAMPLE
)buf
[index
*2] * window
[index
];
537 fft_net
->regi
[i
]=(SAMPLE
)buf
[index
*2+1] * window
[index
];
542 case POLAR
: { /* magnitude followed by phase */
543 while (i
< fft_net
->n
) {
544 index
= load_index
[i
];
545 fft_net
->regr
[i
]=(SAMPLE
)(buf
[index
*2] * cos(buf
[index
*2+1]))
547 fft_net
->regi
[i
]=(SAMPLE
)(buf
[index
*2] * sin(buf
[index
*2+1]))
555 fprintf(stderr
, "load_registers:illegal input form\n");
565 case REAL
: { /* log pure REAL */
566 while (i
< fft_net
->n
) {
567 index
= load_index
[i
];
568 fft_net
->regr
[i
]=(SAMPLE
)pow(10., (1./20.)*buf
[index
])
569 * window
[index
]; /* window scaling after linearization */
575 case IMAG
: { /* log pure IMAGinary */
576 while (i
< fft_net
->n
) {
577 index
= load_index
[i
];
579 fft_net
->regi
[i
]=(SAMPLE
)pow(10., (1./20.)*buf
[index
])
585 case RECT
: { /* log REAL and log IMAGinary */
586 while (i
< fft_net
->n
) {
587 index
= load_index
[i
];
588 fft_net
->regr
[i
]=(SAMPLE
)pow(10., (1./20.)*buf
[index
*2])
590 fft_net
->regi
[i
]=(SAMPLE
)pow(10., (1./20.)*buf
[index
*2+1])
596 case POLAR
: { /* log mag followed by phase */
597 while (i
< fft_net
->n
) {
598 index
= load_index
[i
];
599 fft_net
->regr
[i
]=(SAMPLE
)(pow(10., (1./20.)*buf
[index
*2])
600 * cos(buf
[index
*2+1])) * window
[index
];
601 fft_net
->regi
[i
]=(SAMPLE
)(pow(10., (1./20.)*buf
[index
*2])
602 * sin(buf
[index
*2+1])) * window
[index
];
609 fprintf(stderr
, "load_registers:illegal input form\n");
618 fprintf(stderr
, "load_registers:illegal input scale\n");
626 void store_registers(FFT_NET
*fft_net
, float *buf
, int buf_form
,
627 int buf_scale
, int debug
)
630 effects: Writes the final contents of the network registers into buf in
631 either linear or db scale, polar or rectangular form. If any of
632 the pure forms(REAL, IMAG, MAG, or PHASE) are used then only the
633 corresponding part of the registers is stored in buf.
644 SAMPLE real
, imag
, mag
, phase
;
655 case REAL
: { /* pure REAL */
657 *buf
++ = (float)fft_net
->regr
[i
];
661 case IMAG
: { /* pure IMAGinary */
663 *buf
++ = (float)fft_net
->regi
[i
];
667 case RECT
: { /* both REAL and IMAGinary */
669 *buf
++ = (float)fft_net
->regr
[i
];
670 *buf
++ = (float)fft_net
->regi
[i
];
674 case MAG
: { /* magnitude only */
676 real
= fft_net
->regr
[i
];
677 imag
= fft_net
->regi
[i
];
678 *buf
++ = (float)sqrt(real
*real
+imag
*imag
);
682 case PHASE
: { /* phase only */
684 real
= fft_net
->regr
[i
];
685 imag
= fft_net
->regi
[i
];
687 *buf
++ = (float)atan2(imag
, real
);
688 else { /* deal with bad case */
690 if (imag
> 0){ *buf
++ = PI
/ 2.;
692 else if (imag
< 0){ *buf
++ = -PI
/ 2.;
697 if (imag
> 0){ *buf
++ = PI
/ 2.;
698 if(debug
) fprintf(stderr
,"real=0 and imag > 0\n");}
699 else if (imag
< 0){ *buf
++ = -PI
/ 2.;
700 if(debug
) fprintf(stderr
,"real=0 and imag < 0\n");}
702 if(debug
) fprintf(stderr
,"real=0 and imag=0\n");}
708 case POLAR
: { /* magnitude and phase */
710 real
= fft_net
->regr
[i
];
711 imag
= fft_net
->regi
[i
];
712 *buf
++ = (float)sqrt(real
*real
+imag
*imag
);
713 if (real
) /* a hack to avoid div by zero */
714 *buf
++ = (float)atan2(imag
, real
);
715 else { /* deal with bad case */
716 if (imag
> 0) *buf
++ = PI
/ 2.;
717 else if (imag
< 0) *buf
++ = -PI
/ 2.;
725 fprintf(stderr
, "store_registers:illegal output form\n");
735 case REAL
: { /* real only */
737 *buf
++ = (float)20.*log10(fft_net
->regr
[i
]);
741 case IMAG
: { /* imag only */
743 *buf
++ = (float)20.*log10(fft_net
->regi
[i
]);
747 case RECT
: { /* real and imag */
749 *buf
++ = (float)20.*log10(fft_net
->regr
[i
]);
750 *buf
++ = (float)20.*log10(fft_net
->regi
[i
]);
754 case MAG
: { /* magnitude only */
756 real
= fft_net
->regr
[i
];
757 imag
= fft_net
->regi
[i
];
758 *buf
++ = (float)20.*log10(sqrt(real
*real
+imag
*imag
));
762 case PHASE
: { /* phase only */
764 real
= fft_net
->regr
[i
];
765 imag
= fft_net
->regi
[i
];
767 *buf
++ = (float)atan2(imag
, real
);
768 else { /* deal with bad case */
769 if (imag
> 0) *buf
++ = PI
/ 2.;
770 else if (imag
< 0) *buf
++ = -PI
/ 2.;
776 case POLAR
: { /* magnitude and phase */
778 real
= fft_net
->regr
[i
];
779 imag
= fft_net
->regi
[i
];
780 *buf
++ = (float)20.*log10(sqrt(real
*real
+imag
*imag
));
782 *buf
++ = (float)atan2(imag
, real
);
783 else { /* deal with bad case */
784 if (imag
> 0) *buf
++ = PI
/ 2.;
785 else if (imag
< 0) *buf
++ = -PI
/ 2.;
793 fprintf(stderr
, "store_registers:illegal output form\n");
802 fprintf(stderr
, "store_registers:illegal output scale\n");
811 /*****************************************************************************/
812 /* COMPUTE TRANSFORMATION */
813 /*****************************************************************************/
815 void compute_fft(FFT_NET
*fft_net
)
819 effects: Passes the values (already loaded) in the registers through
820 the network, multiplying with appropriate coefficients at each
821 stage. The fft result will be in the registers at the end of
822 the computation. The direction of the transformation is indicated
823 by the network flag 'direction'. The form of the computation is:
825 X(pn) = X(p) + C*X(q)
826 X(qn) = X(p) - C*X(q)
828 where X(pn,qn) represents the output of the registers at each stage.
829 The calculations are actually done in place. Register pointers are
830 used to speed up the calculations.
832 Register and coefficient addresses involved in the calculations
833 are stored sequentially and are accessed as such. fft_net->indexp,
834 indexq contain pointers to the relevant addresses, and fft_net->coeffs,
835 inv_coeffs points to the appropriate coefficients at each stage of the
840 SAMPLE
**xpr
, **xpi
, **xqr
, **xqi
, *cr
, *ci
;
842 SAMPLE tpr
, tpi
, tqr
, tqi
;
843 int bps
= fft_net
->bps
;
844 int cnt
= bps
* (fft_net
->stages
- 1);
846 /* predetermined register addresses and coefficients */
847 xpr
= fft_net
->indexpr
;
848 xpi
= fft_net
->indexpi
;
849 xqr
= fft_net
->indexqr
;
850 xqi
= fft_net
->indexqi
;
852 if (fft_net
->direction
==FORWARD
) { /* FORWARD FFT coefficients */
853 cr
= fft_net
->coeffr
;
854 ci
= fft_net
->coeffi
;
856 else { /* INVERSE FFT coefficients */
857 cr
= fft_net
->inv_coeffr
;
858 ci
= fft_net
->inv_coeffi
;
861 /* stage one coefficients are 1 + 0j so C*X(q)=X(q) */
862 /* bps mults can be avoided */
864 for (i
= 0; i
< bps
; i
++) {
866 /* add X(p) and X(q) */
872 /* exchange register with temp */
878 /* next set of register for calculations: */
879 xpr
++; xpi
++; xqr
++; xqi
++; cr
++; ci
++;
883 for (i
= 0; i
< cnt
; i
++) {
885 /* mult X(q) by coeff C */
886 tqr
= **xqr
* *cr
- **xqi
* *ci
;
887 tqi
= **xqr
* *ci
+ **xqi
* *cr
;
889 /* exchange register with temp */
893 /* add X(p) and X(q) */
899 /* exchange register with temp */
904 /* next set of register for calculations: */
905 xpr
++; xpi
++; xqr
++; xqi
++; cr
++; ci
++;
910 /****************************************************************************/
911 /* SUPPORT MODULES */
912 /****************************************************************************/
914 void net_alloc(FFT_NET
*fft_net
)
917 /* effects: Allocates appropriate two dimensional arrays and assigns
918 correct internal pointers.
926 stages
= fft_net
->stages
;
930 /* two dimensional arrays with elements stored sequentially */
932 fft_net
->load_index
= (int *)malloc(n
* INT_SIZE
);
933 fft_net
->regr
= (SAMPLE
*)malloc(n
* SAMPLE_SIZE
);
934 fft_net
->regi
= (SAMPLE
*)malloc(n
* SAMPLE_SIZE
);
935 fft_net
->coeffr
= (SAMPLE
*)malloc(stages
*bps
*SAMPLE_SIZE
);
936 fft_net
->coeffi
= (SAMPLE
*)malloc(stages
*bps
*SAMPLE_SIZE
);
937 fft_net
->inv_coeffr
= (SAMPLE
*)malloc(stages
*bps
*SAMPLE_SIZE
);
938 fft_net
->inv_coeffi
= (SAMPLE
*)malloc(stages
*bps
*SAMPLE_SIZE
);
939 fft_net
->indexpr
= (SAMPLE
**)malloc(stages
* bps
* PNTR_SIZE
);
940 fft_net
->indexpi
= (SAMPLE
**)malloc(stages
* bps
* PNTR_SIZE
);
941 fft_net
->indexqr
= (SAMPLE
**)malloc(stages
* bps
* PNTR_SIZE
);
942 fft_net
->indexqi
= (SAMPLE
**)malloc(stages
* bps
* PNTR_SIZE
);
944 /* one dimensional load window */
945 fft_net
->window
= (SAMPLE
*)malloc(n
* SAMPLE_SIZE
);
946 fft_net
->inv_window
= (SAMPLE
*)malloc(n
* SAMPLE_SIZE
);
949 void net_dealloc(FFT_NET
*fft_net
)
952 /* effects: Deallocates given FFT network.
957 free((char *)fft_net
->load_index
);
958 free((char *)fft_net
->regr
);
959 free((char *)fft_net
->regi
);
960 free((char *)fft_net
->coeffr
);
961 free((char *)fft_net
->coeffi
);
962 free((char *)fft_net
->inv_coeffr
);
963 free((char *)fft_net
->inv_coeffi
);
964 free((char *)fft_net
->indexpr
);
965 free((char *)fft_net
->indexpi
);
966 free((char *)fft_net
->indexqr
);
967 free((char *)fft_net
->indexqi
);
968 free((char *)fft_net
->window
);
969 free((char *)fft_net
->inv_window
);
977 /* effects: Returns TRUE if n is a power of two, otherwise FALSE.
983 for (i
= n
; i
> 1; i
>>= 1)
984 if (i
& 1) return FALSE
; /* more than one bit high */
989 void create_hanning(SAMPLE
*window
, int n
, SAMPLE scale
)
991 /* effects: Fills the buffer window with a hanning window of the appropriate
992 size scaled by scale.
996 SAMPLE a
, pi_div_n
= PI
/n
;
999 for (k
=1; k
<= n
; k
++) {
1000 a
= sin(k
* pi_div_n
);
1001 *window
++ = scale
* a
* a
;
1006 void create_rectangular(SAMPLE
*window
, int n
, SAMPLE scale
)
1008 /* effects: Fills the buffer window with a rectangular window of the
1009 appropriate size of height scale.
1018 void short_to_float(short *short_buf
, float *float_buf
, int n
)
1020 /* effects; Converts short_buf to floats and stores them in float_buf.
1025 *float_buf
++ = (float)*short_buf
++;
1030 /* here's the meat: */
1032 void pd_fft(float *buf
, int npoints
, int inverse
)
1041 renorm
= (inverse
? npoints
: 1.);
1042 cfft((inverse
? INVERSE
: FORWARD
), npoints
, RECTANGULAR
,
1043 buf
, RECT
, LINEAR
, buf
, RECT
, LINEAR
, 0);
1044 for (i
= npoints
<< 1, fp
= buf
; i
--; fp
++) *fp
*= renorm
;