1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*Copyright (c) 2003-2004, Mark Borgerding 2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Lots of modifications by Jean-Marc Valin 3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Copyright (c) 2005-2007, Xiph.Org Foundation 4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Copyright (c) 2008, Xiph.Org Foundation, CSIRO 5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org All rights reserved. 7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Redistribution and use in source and binary forms, with or without 9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org modification, are permitted provided that the following conditions are met: 10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 11885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * Redistributions of source code must retain the above copyright notice, 12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org this list of conditions and the following disclaimer. 13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * Redistributions in binary form must reproduce the above copyright notice, 14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org this list of conditions and the following disclaimer in the 15885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org documentation and/or other materials provided with the distribution. 16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org POSSIBILITY OF SUCH DAMAGE.*/ 28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifndef KISS_FFT_H 30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define KISS_FFT_H 31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include <stdlib.h> 33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include <math.h> 34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "arch.h" 35885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 36885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef __cplusplus 37885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgextern "C" { 38885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 39885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 40885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef USE_SIMD 41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# include <xmmintrin.h> 42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define kiss_fft_scalar __m128 43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define KISS_FFT_MALLOC(nbytes) memalign(16,nbytes) 44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#else 45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define KISS_FFT_MALLOC opus_alloc 46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT 49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "arch.h" 50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define kiss_fft_scalar opus_int32 52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define kiss_twiddle_scalar opus_int16 53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#else 56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# ifndef kiss_fft_scalar 57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* default is float */ 58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define kiss_fft_scalar float 59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define kiss_twiddle_scalar float 60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# define KF_SUFFIX _celt_single 61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org# endif 62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgtypedef struct { 65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org kiss_fft_scalar r; 66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org kiss_fft_scalar i; 67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}kiss_fft_cpx; 68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgtypedef struct { 70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org kiss_twiddle_scalar r; 71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org kiss_twiddle_scalar i; 72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}kiss_twiddle_cpx; 73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#define MAXFACTORS 8 75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* e.g. an fft of length 128 has 4 factors 76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org as far as kissfft is concerned 77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 4*4*4*2 78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org */ 79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgtypedef struct kiss_fft_state{ 81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int nfft; 82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifndef FIXED_POINT 83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org kiss_fft_scalar scale; 84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int shift; 86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_int16 factors[2*MAXFACTORS]; 87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const opus_int16 *bitrev; 88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org const kiss_twiddle_cpx *twiddles; 89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} kiss_fft_state; 90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 91885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*typedef struct kiss_fft_state* kiss_fft_cfg;*/ 92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 93885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/** 94885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * opus_fft_alloc 95885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 96885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * Initialize a FFT (or IFFT) algorithm's cfg/state buffer. 97885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 98885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * typical usage: kiss_fft_cfg mycfg=opus_fft_alloc(1024,0,NULL,NULL); 99885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 100885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * The return value from fft_alloc is a cfg buffer used internally 101885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * by the fft routine or NULL. 102885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 103885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * If lenmem is NULL, then opus_fft_alloc will allocate a cfg buffer using malloc. 104885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * The returned value should be free()d when done to avoid memory leaks. 105885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 106885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * The state can be placed in a user supplied buffer 'mem': 107885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * If lenmem is not NULL and mem is not NULL and *lenmem is large enough, 108885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * then the function places the cfg in mem and the size used in *lenmem 109885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * and returns mem. 110885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 111885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * If lenmem is not NULL and ( mem is NULL or *lenmem is not large enough), 112885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * then the function returns NULL and places the minimum cfg 113885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * buffer size in *lenmem. 114885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * */ 115885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 116885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgkiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem, const kiss_fft_state *base); 117885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 118885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgkiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem); 119885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 120885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/** 121885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * opus_fft(cfg,in_out_buf) 122885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * 123885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * Perform an FFT on a complex input buffer. 124885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * for a forward FFT, 125885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * fin should be f[0] , f[1] , ... ,f[nfft-1] 126885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * fout will be F[0] , F[1] , ... ,F[nfft-1] 127885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * Note that each element is complex and can be accessed like 128885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org f[k].r and f[k].i 129885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org * */ 130885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid opus_fft(const kiss_fft_state *cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout); 131885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid opus_ifft(const kiss_fft_state *cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout); 132885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 133885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid opus_fft_free(const kiss_fft_state *cfg); 134885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 135885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef __cplusplus 136885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 137885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 138885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 139885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 140