| 1 |
/* |
| 2 |
* Copyright (c) 2003-2010, 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 |
/* kiss_fft.h |
| 10 |
defines kiss_fft_scalar as either short or a float type |
| 11 |
and defines |
| 12 |
typedef struct { kiss_fft_scalar r; kiss_fft_scalar i; }kiss_fft_cpx; */ |
| 13 |
#include "kiss_fft.h" |
| 14 |
#include <limits.h> |
| 15 |
|
| 16 |
#define MAXFACTORS 32 |
| 17 |
/* e.g. an fft of length 128 has 4 factors |
| 18 |
as far as kissfft is concerned |
| 19 |
4*4*4*2 |
| 20 |
*/ |
| 21 |
|
| 22 |
struct kiss_fft_state{ |
| 23 |
int nfft; |
| 24 |
int inverse; |
| 25 |
int factors[2*MAXFACTORS]; |
| 26 |
kiss_fft_cpx twiddles[1]; |
| 27 |
}; |
| 28 |
|
| 29 |
/* |
| 30 |
Explanation of macros dealing with complex math: |
| 31 |
|
| 32 |
C_MUL(m,a,b) : m = a*b |
| 33 |
C_FIXDIV( c , div ) : if a fixed point impl., c /= div. noop otherwise |
| 34 |
C_SUB( res, a,b) : res = a - b |
| 35 |
C_SUBFROM( res , a) : res -= a |
| 36 |
C_ADDTO( res , a) : res += a |
| 37 |
* */ |
| 38 |
#ifdef FIXED_POINT |
| 39 |
#include <stdint.h> |
| 40 |
#if (FIXED_POINT==32) |
| 41 |
# define FRACBITS 31 |
| 42 |
# define SAMPPROD int64_t |
| 43 |
#define SAMP_MAX INT32_MAX |
| 44 |
#define SAMP_MIN INT32_MIN |
| 45 |
#else |
| 46 |
# define FRACBITS 15 |
| 47 |
# define SAMPPROD int32_t |
| 48 |
#define SAMP_MAX INT16_MAX |
| 49 |
#define SAMP_MIN INT16_MIN |
| 50 |
#endif |
| 51 |
|
| 52 |
#if defined(CHECK_OVERFLOW) |
| 53 |
# define CHECK_OVERFLOW_OP(a,op,b) \ |
| 54 |
if ( (SAMPPROD)(a) op (SAMPPROD)(b) > SAMP_MAX || (SAMPPROD)(a) op (SAMPPROD)(b) < SAMP_MIN ) { \ |
| 55 |
fprintf(stderr,"WARNING:overflow @ " __FILE__ "(%d): (%d " #op" %d) = %ld\n",__LINE__,(a),(b),(SAMPPROD)(a) op (SAMPPROD)(b) ); } |
| 56 |
#endif |
| 57 |
|
| 58 |
|
| 59 |
# define smul(a,b) ( (SAMPPROD)(a)*(b) ) |
| 60 |
# define sround( x ) (kiss_fft_scalar)( ( (x) + (1<<(FRACBITS-1)) ) >> FRACBITS ) |
| 61 |
|
| 62 |
# define S_MUL(a,b) sround( smul(a,b) ) |
| 63 |
|
| 64 |
# define C_MUL(m,a,b) \ |
| 65 |
do{ (m).r = sround( smul((a).r,(b).r) - smul((a).i,(b).i) ); \ |
| 66 |
(m).i = sround( smul((a).r,(b).i) + smul((a).i,(b).r) ); }while(0) |
| 67 |
|
| 68 |
# define DIVSCALAR(x,k) \ |
| 69 |
(x) = sround( smul( x, SAMP_MAX/k ) ) |
| 70 |
|
| 71 |
# define C_FIXDIV(c,div) \ |
| 72 |
do { DIVSCALAR( (c).r , div); \ |
| 73 |
DIVSCALAR( (c).i , div); }while (0) |
| 74 |
|
| 75 |
# define C_MULBYSCALAR( c, s ) \ |
| 76 |
do{ (c).r = sround( smul( (c).r , s ) ) ;\ |
| 77 |
(c).i = sround( smul( (c).i , s ) ) ; }while(0) |
| 78 |
|
| 79 |
#else /* not FIXED_POINT*/ |
| 80 |
|
| 81 |
# define S_MUL(a,b) ( (a)*(b) ) |
| 82 |
#define C_MUL(m,a,b) \ |
| 83 |
do{ (m).r = (a).r*(b).r - (a).i*(b).i;\ |
| 84 |
(m).i = (a).r*(b).i + (a).i*(b).r; }while(0) |
| 85 |
# define C_FIXDIV(c,div) /* NOOP */ |
| 86 |
# define C_MULBYSCALAR( c, s ) \ |
| 87 |
do{ (c).r *= (s);\ |
| 88 |
(c).i *= (s); }while(0) |
| 89 |
#endif |
| 90 |
|
| 91 |
#ifndef CHECK_OVERFLOW_OP |
| 92 |
# define CHECK_OVERFLOW_OP(a,op,b) /* noop */ |
| 93 |
#endif |
| 94 |
|
| 95 |
#define C_ADD( res, a,b)\ |
| 96 |
do { \ |
| 97 |
CHECK_OVERFLOW_OP((a).r,+,(b).r)\ |
| 98 |
CHECK_OVERFLOW_OP((a).i,+,(b).i)\ |
| 99 |
(res).r=(a).r+(b).r; (res).i=(a).i+(b).i; \ |
| 100 |
}while(0) |
| 101 |
#define C_SUB( res, a,b)\ |
| 102 |
do { \ |
| 103 |
CHECK_OVERFLOW_OP((a).r,-,(b).r)\ |
| 104 |
CHECK_OVERFLOW_OP((a).i,-,(b).i)\ |
| 105 |
(res).r=(a).r-(b).r; (res).i=(a).i-(b).i; \ |
| 106 |
}while(0) |
| 107 |
#define C_ADDTO( res , a)\ |
| 108 |
do { \ |
| 109 |
CHECK_OVERFLOW_OP((res).r,+,(a).r)\ |
| 110 |
CHECK_OVERFLOW_OP((res).i,+,(a).i)\ |
| 111 |
(res).r += (a).r; (res).i += (a).i;\ |
| 112 |
}while(0) |
| 113 |
|
| 114 |
#define C_SUBFROM( res , a)\ |
| 115 |
do {\ |
| 116 |
CHECK_OVERFLOW_OP((res).r,-,(a).r)\ |
| 117 |
CHECK_OVERFLOW_OP((res).i,-,(a).i)\ |
| 118 |
(res).r -= (a).r; (res).i -= (a).i; \ |
| 119 |
}while(0) |
| 120 |
|
| 121 |
|
| 122 |
#ifdef FIXED_POINT |
| 123 |
# define KISS_FFT_COS(phase) floor(.5+SAMP_MAX * cos (phase)) |
| 124 |
# define KISS_FFT_SIN(phase) floor(.5+SAMP_MAX * sin (phase)) |
| 125 |
# define HALF_OF(x) ((x)>>1) |
| 126 |
#elif defined(USE_SIMD) |
| 127 |
# define KISS_FFT_COS(phase) _mm_set1_ps( cos(phase) ) |
| 128 |
# define KISS_FFT_SIN(phase) _mm_set1_ps( sin(phase) ) |
| 129 |
# define HALF_OF(x) ((x)*_mm_set1_ps(.5)) |
| 130 |
#else |
| 131 |
# define KISS_FFT_COS(phase) (kiss_fft_scalar) cos(phase) |
| 132 |
# define KISS_FFT_SIN(phase) (kiss_fft_scalar) sin(phase) |
| 133 |
# define HALF_OF(x) ((x)*.5) |
| 134 |
#endif |
| 135 |
|
| 136 |
#define kf_cexp(x,phase) \ |
| 137 |
do{ \ |
| 138 |
(x)->r = KISS_FFT_COS(phase);\ |
| 139 |
(x)->i = KISS_FFT_SIN(phase);\ |
| 140 |
}while(0) |
| 141 |
|
| 142 |
|
| 143 |
/* a debugging function */ |
| 144 |
#define pcpx(c)\ |
| 145 |
fprintf(stderr,"%g + %gi\n",(double)((c)->r),(double)((c)->i) ) |
| 146 |
|
| 147 |
|
| 148 |
#ifdef KISS_FFT_USE_ALLOCA |
| 149 |
// define this to allow use of alloca instead of malloc for temporary buffers |
| 150 |
// Temporary buffers are used in two case: |
| 151 |
// 1. FFT sizes that have "bad" factors. i.e. not 2,3 and 5 |
| 152 |
// 2. "in-place" FFTs. Notice the quotes, since kissfft does not really do an in-place transform. |
| 153 |
#include <alloca.h> |
| 154 |
#define KISS_FFT_TMP_ALLOC(nbytes) alloca(nbytes) |
| 155 |
#define KISS_FFT_TMP_FREE(ptr) |
| 156 |
#else |
| 157 |
#define KISS_FFT_TMP_ALLOC(nbytes) KISS_FFT_MALLOC(nbytes) |
| 158 |
#define KISS_FFT_TMP_FREE(ptr) KISS_FFT_FREE(ptr) |
| 159 |
#endif |