| 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 |
} |