Debian Codegraph @

common/kiss_fft/kiss_fftr.c

raw
1 /*
2 * Copyright (c) 2003-2004, Mark Borgerding. All rights reserved.
3 * This file is part of KISS FFT - https://github.com/mborgerding/kissfft
4 *
5 * SPDX-License-Identifier: BSD-3-Clause
6 * See COPYING file for more information.
7 */
8
9 #include "kiss_fftr.h"
10 #include "_kiss_fft_guts.h"
11
12 struct kiss_fftr_state{
13 kiss_fft_cfg substate;
14 kiss_fft_cpx * tmpbuf;
15 kiss_fft_cpx * super_twiddles;
16 #ifdef USE_SIMD
17 void * pad;
18 #endif
19 };
20
21 kiss_fftr_cfg kiss_fftr_alloc(int nfft,int inverse_fft,void * mem,size_t * lenmem)
22 {
23 int i;
24 kiss_fftr_cfg st = NULL;
25 size_t subsize = 0, memneeded;
26
27 if (nfft & 1) {
28 fprintf(stderr,"Real FFT optimization must be even.\n");
29 return NULL;
30 }
31 nfft >>= 1;
32
33 kiss_fft_alloc (nfft, inverse_fft, NULL, &subsize);
34 memneeded = sizeof(struct kiss_fftr_state) + subsize + sizeof(kiss_fft_cpx) * ( nfft * 3 / 2);
35
36 if (lenmem == NULL) {
37 st = (kiss_fftr_cfg) KISS_FFT_MALLOC (memneeded);
38 } else {
39 if (*lenmem >= memneeded)
40 st = (kiss_fftr_cfg) mem;
41 *lenmem = memneeded;
42 }
43 if (!st)
44 return NULL;
45
46 st->substate = (kiss_fft_cfg) (st + 1); /*just beyond kiss_fftr_state struct */
47 st->tmpbuf = (kiss_fft_cpx *) (((char *) st->substate) + subsize);
48 st->super_twiddles = st->tmpbuf + nfft;
49 kiss_fft_alloc(nfft, inverse_fft, st->substate, &subsize);
50
51 for (i = 0; i < nfft/2; ++i) {
52 double phase =
53 -3.14159265358979323846264338327 * ((double) (i+1) / nfft + .5);
54 if (inverse_fft)
55 phase *= -1;
56 kf_cexp (st->super_twiddles+i,phase);
57 }
58 return st;
59 }
60
61 void kiss_fftr(kiss_fftr_cfg st,const kiss_fft_scalar *timedata,kiss_fft_cpx *freqdata)
62 {
63 /* input buffer timedata is stored row-wise */
64 int k,ncfft;
65 kiss_fft_cpx fpnk,fpk,f1k,f2k,tw,tdc;
66
67 if ( st->substate->inverse) {
68 fprintf(stderr,"kiss fft usage error: improper alloc\n");
69 exit(1);
70 }
71
72 ncfft = st->substate->nfft;
73
74 /*perform the parallel fft of two real signals packed in real,imag*/
75 kiss_fft( st->substate , (const kiss_fft_cpx*)timedata, st->tmpbuf );
76 /* The real part of the DC element of the frequency spectrum in st->tmpbuf
77 * contains the sum of the even-numbered elements of the input time sequence
78 * The imag part is the sum of the odd-numbered elements
79 *
80 * The sum of tdc.r and tdc.i is the sum of the input time sequence.
81 * yielding DC of input time sequence
82 * The difference of tdc.r - tdc.i is the sum of the input (dot product) [1,-1,1,-1...
83 * yielding Nyquist bin of input time sequence
84 */
85
86 tdc.r = st->tmpbuf[0].r;
87 tdc.i = st->tmpbuf[0].i;
88 C_FIXDIV(tdc,2);
89 CHECK_OVERFLOW_OP(tdc.r ,+, tdc.i);
90 CHECK_OVERFLOW_OP(tdc.r ,-, tdc.i);
91 freqdata[0].r = tdc.r + tdc.i;
92 freqdata[ncfft].r = tdc.r - tdc.i;
93 #ifdef USE_SIMD
94 freqdata[ncfft].i = freqdata[0].i = _mm_set1_ps(0);
95 #else
96 freqdata[ncfft].i = freqdata[0].i = 0;
97 #endif
98
99 for ( k=1;k <= ncfft/2 ; ++k ) {
100 fpk = st->tmpbuf[k];
101 fpnk.r = st->tmpbuf[ncfft-k].r;
102 fpnk.i = - st->tmpbuf[ncfft-k].i;
103 C_FIXDIV(fpk,2);
104 C_FIXDIV(fpnk,2);
105
106 C_ADD( f1k, fpk , fpnk );
107 C_SUB( f2k, fpk , fpnk );
108 C_MUL( tw , f2k , st->super_twiddles[k-1]);
109
110 freqdata[k].r = HALF_OF(f1k.r + tw.r);
111 freqdata[k].i = HALF_OF(f1k.i + tw.i);
112 freqdata[ncfft-k].r = HALF_OF(f1k.r - tw.r);
113 freqdata[ncfft-k].i = HALF_OF(tw.i - f1k.i);
114 }
115 }
116
117 void kiss_fftri(kiss_fftr_cfg st,const kiss_fft_cpx *freqdata,kiss_fft_scalar *timedata)
118 {
119 /* input buffer timedata is stored row-wise */
120 int k, ncfft;
121
122 if (st->substate->inverse == 0) {
123 fprintf (stderr, "kiss fft usage error: improper alloc\n");
124 exit (1);
125 }
126
127 ncfft = st->substate->nfft;
128
129 st->tmpbuf[0].r = freqdata[0].r + freqdata[ncfft].r;
130 st->tmpbuf[0].i = freqdata[0].r - freqdata[ncfft].r;
131 C_FIXDIV(st->tmpbuf[0],2);
132
133 for (k = 1; k <= ncfft / 2; ++k) {
134 kiss_fft_cpx fk, fnkc, fek, fok, tmp;
135 fk = freqdata[k];
136 fnkc.r = freqdata[ncfft - k].r;
137 fnkc.i = -freqdata[ncfft - k].i;
138 C_FIXDIV( fk , 2 );
139 C_FIXDIV( fnkc , 2 );
140
141 C_ADD (fek, fk, fnkc);
142 C_SUB (tmp, fk, fnkc);
143 C_MUL (fok, tmp, st->super_twiddles[k-1]);
144 C_ADD (st->tmpbuf[k], fek, fok);
145 C_SUB (st->tmpbuf[ncfft - k], fek, fok);
146 #ifdef USE_SIMD
147 st->tmpbuf[ncfft - k].i *= _mm_set1_ps(-1.0);
148 #else
149 st->tmpbuf[ncfft - k].i *= -1;
150 #endif
151 }
152 kiss_fft (st->substate, st->tmpbuf, (kiss_fft_cpx *) timedata);
153 }