198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* 298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectCopyright (c) 2003-2004, Mark Borgerding 398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectAll rights reserved. 598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectRedistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 1098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission. 1198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source ProjectTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project*/ 1498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define MIN(a,b) ((a)<(b) ? (a):(b)) 1698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define MAX(a,b) ((a)>(b) ? (a):(b)) 1798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 1898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* kiss_fft.h 1998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project defines kiss_fft_scalar as either short or a float type 2098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project and defines 2198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project typedef struct { kiss_fft_scalar r; kiss_fft_scalar i; }kiss_fft_cpx; */ 2298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "kiss_fft.h" 2398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "math_approx.h" 2498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 2598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define MAXFACTORS 32 2698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* e.g. an fft of length 128 has 4 factors 2798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project as far as kissfft is concerned 2898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 4*4*4*2 2998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project */ 3098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 3198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Projectstruct kiss_fft_state{ 3298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int nfft; 3398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int inverse; 3498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project int factors[2*MAXFACTORS]; 3598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project kiss_fft_cpx twiddles[1]; 3698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project}; 3798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 3898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* 3998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project Explanation of macros dealing with complex math: 4098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 4198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_MUL(m,a,b) : m = a*b 4298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_FIXDIV( c , div ) : if a fixed point impl., c /= div. noop otherwise 4398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUB( res, a,b) : res = a - b 4498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_SUBFROM( res , a) : res -= a 4598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project C_ADDTO( res , a) : res += a 4698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project * */ 4798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#ifdef FIXED_POINT 4898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#include "arch.h" 4998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define FRACBITS 15 5098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define SAMPPROD spx_int32_t 5198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define SAMP_MAX 32767 5298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 5398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define SAMP_MIN -SAMP_MAX 5498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 5598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#if defined(CHECK_OVERFLOW) 5698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define CHECK_OVERFLOW_OP(a,op,b) \ 5798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project if ( (SAMPPROD)(a) op (SAMPPROD)(b) > SAMP_MAX || (SAMPPROD)(a) op (SAMPPROD)(b) < SAMP_MIN ) { \ 5898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project fprintf(stderr,"WARNING:overflow @ " __FILE__ "(%d): (%d " #op" %d) = %ld\n",__LINE__,(a),(b),(SAMPPROD)(a) op (SAMPPROD)(b) ); } 5998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 6098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 6198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 6298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define smul(a,b) ( (SAMPPROD)(a)*(b) ) 6398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define sround( x ) (kiss_fft_scalar)( ( (x) + (1<<(FRACBITS-1)) ) >> FRACBITS ) 6498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 6598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define S_MUL(a,b) sround( smul(a,b) ) 6698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 6798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_MUL(m,a,b) \ 6898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ (m).r = sround( smul((a).r,(b).r) - smul((a).i,(b).i) ); \ 6998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (m).i = sround( smul((a).r,(b).i) + smul((a).i,(b).r) ); }while(0) 7098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 7198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_MUL4(m,a,b) \ 7298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ (m).r = PSHR32( smul((a).r,(b).r) - smul((a).i,(b).i),17 ); \ 7398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (m).i = PSHR32( smul((a).r,(b).i) + smul((a).i,(b).r),17 ); }while(0) 7498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 7598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define DIVSCALAR(x,k) \ 7698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (x) = sround( smul( x, SAMP_MAX/k ) ) 7798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 7898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_FIXDIV(c,div) \ 7998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do { DIVSCALAR( (c).r , div); \ 8098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project DIVSCALAR( (c).i , div); }while (0) 8198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 8298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_MULBYSCALAR( c, s ) \ 8398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ (c).r = sround( smul( (c).r , s ) ) ;\ 8498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (c).i = sround( smul( (c).i , s ) ) ; }while(0) 8598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 8698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#else /* not FIXED_POINT*/ 8798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 8898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define S_MUL(a,b) ( (a)*(b) ) 8998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_MUL(m,a,b) \ 9098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ (m).r = (a).r*(b).r - (a).i*(b).i;\ 9198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (m).i = (a).r*(b).i + (a).i*(b).r; }while(0) 9298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 9398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_MUL4(m,a,b) C_MUL(m,a,b) 9498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 9598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_FIXDIV(c,div) /* NOOP */ 9698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define C_MULBYSCALAR( c, s ) \ 9798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ (c).r *= (s);\ 9898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (c).i *= (s); }while(0) 9998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 10098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 10198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#ifndef CHECK_OVERFLOW_OP 10298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define CHECK_OVERFLOW_OP(a,op,b) /* noop */ 10398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 10498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 10598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_ADD( res, a,b)\ 10698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do { \ 10798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((a).r,+,(b).r)\ 10898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((a).i,+,(b).i)\ 10998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (res).r=(a).r+(b).r; (res).i=(a).i+(b).i; \ 11098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(0) 11198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_SUB( res, a,b)\ 11298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do { \ 11398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((a).r,-,(b).r)\ 11498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((a).i,-,(b).i)\ 11598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (res).r=(a).r-(b).r; (res).i=(a).i-(b).i; \ 11698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(0) 11798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_ADDTO( res , a)\ 11898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do { \ 11998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((res).r,+,(a).r)\ 12098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((res).i,+,(a).i)\ 12198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (res).r += (a).r; (res).i += (a).i;\ 12298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(0) 12398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 12498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define C_SUBFROM( res , a)\ 12598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do {\ 12698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((res).r,-,(a).r)\ 12798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project CHECK_OVERFLOW_OP((res).i,-,(a).i)\ 12898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (res).r -= (a).r; (res).i -= (a).i; \ 12998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(0) 13098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 13198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 13298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#ifdef FIXED_POINT 13398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_COS(phase) floor(MIN(32767,MAX(-32767,.5+32768 * cos (phase)))) 13498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_SIN(phase) floor(MIN(32767,MAX(-32767,.5+32768 * sin (phase)))) 13598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define HALF_OF(x) ((x)>>1) 13698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#elif defined(USE_SIMD) 13798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_COS(phase) _mm_set1_ps( cos(phase) ) 13898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_SIN(phase) _mm_set1_ps( sin(phase) ) 13998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define HALF_OF(x) ((x)*_mm_set1_ps(.5)) 14098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#else 14198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_COS(phase) (kiss_fft_scalar) cos(phase) 14298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define KISS_FFT_SIN(phase) (kiss_fft_scalar) sin(phase) 14398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project# define HALF_OF(x) ((x)*.5) 14498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#endif 14598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 14698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define kf_cexp(x,phase) \ 14798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ \ 14898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (x)->r = KISS_FFT_COS(phase);\ 14998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (x)->i = KISS_FFT_SIN(phase);\ 15098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project }while(0) 15198913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define kf_cexp2(x,phase) \ 15298913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project do{ \ 15398913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (x)->r = spx_cos_norm((phase));\ 15498913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project (x)->i = spx_cos_norm((phase)-32768);\ 15598913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project}while(0) 15698913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 15798913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project 15898913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project/* a debugging function */ 15998913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project#define pcpx(c)\ 16098913fed6520d8849fb2e246be943e04474aefaThe Android Open Source Project fprintf(stderr,"%g + %gi\n",(double)((c)->r),(double)((c)->i) ) 161