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 160