libcelt/kiss_fft.h

   1 /*
   2 Copyright (c) 2003-2004, Mark Borgerding
   3 Lots of modifications by Jean-Marc Valin
   4 Copyright (c) 2005-2007, Xiph.Org Foundation
   5 Copyright (c) 2008,      Xiph.Org Foundation, CSIRO
   6
   7 All rights reserved.
   8
   9 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
  10
  11     * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  12     * 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.
  13     * 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.
  14
  15 THIS 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.
  16 */
  17
  18
  19 #ifndef KISS_FFT_H
  20 #define KISS_FFT_H
  21
  22 #include <stdlib.h>
  23 #include <math.h>
  24 #include "arch.h"
  25
  26 #ifdef __cplusplus
  27 extern "C" {
  28 #endif
  29
  30 /*
  31  ATTENTION!
  32  If you would like a :
  33  -- a utility that will handle the caching of fft objects
  34  -- real-only (no imaginary time component ) FFT
  35  -- a multi-dimensional FFT
  36  -- a command-line utility to perform ffts
  37  -- a command-line utility to perform fast-convolution filtering
  38
  39  Then see kfc.h kiss_fftr.h kiss_fftnd.h fftutil.c kiss_fastfir.c
  40   in the tools/ directory.
  41 */
  42
  43 #ifdef USE_SIMD
  44 # include <xmmintrin.h>
  45 # define kiss_fft_scalar __m128
  46 #define KISS_FFT_MALLOC(nbytes) memalign(16,nbytes)
  47 #else
  48 #define KISS_FFT_MALLOC celt_alloc
  49 #endif
  50
  51
  52 #ifdef FIXED_POINT
  53 #include "arch.h"
  54 #define DOUBLE_PRECISION
  55
  56 #ifdef DOUBLE_PRECISION
  57 #  define kiss_fft_scalar celt_int32
  58 #  define kiss_twiddle_scalar celt_int16
  59 #  define KF_SUFFIX _celt_double
  60 #else
  61 #  define kiss_fft_scalar celt_int16
  62 #  define kiss_twiddle_scalar celt_int16
  63 #  define KF_SUFFIX _celt_single
  64 #endif
  65 #else
  66 # ifndef kiss_fft_scalar
  67 /*  default is float */
  68 #   define kiss_fft_scalar float
  69 #   define kiss_twiddle_scalar float
  70 #   define KF_SUFFIX _celt_single
  71 # endif
  72 #endif
  73
  74 #if 0
  75 /* This adds a suffix to all the kiss_fft functions so we
  76    can easily link with more than one copy of the fft */
  77 #define CAT_SUFFIX(a,b) a ## b
  78 #define SUF(a,b) CAT_SUFFIX(a, b)
  79
  80 #define kiss_fft_alloc_twiddles SUF(kiss_fft_alloc_twiddles,KF_SUFFIX)
  81 #define kiss_fft_alloc SUF(kiss_fft_alloc,KF_SUFFIX)
  82 #define kiss_fft SUF(kiss_fft,KF_SUFFIX)
  83 #define kiss_ifft SUF(kiss_ifft,KF_SUFFIX)
  84 #define kiss_fft_stride SUF(kiss_fft_stride,KF_SUFFIX)
  85 #define kiss_ifft_stride SUF(kiss_ifft_stride,KF_SUFFIX)
  86 #define kiss_fft_free SUF(kiss_fft_free,KF_SUFFIX)
  87
  88 #endif
  89
  90 typedef struct {
  91     kiss_fft_scalar r;
  92     kiss_fft_scalar i;
  93 }kiss_fft_cpx;
  94
  95 typedef struct {
  96    kiss_twiddle_scalar r;
  97    kiss_twiddle_scalar i;
  98 }kiss_twiddle_cpx;
  99
 100 #define MAXFACTORS 8
 101 /* e.g. an fft of length 128 has 4 factors
 102  as far as kissfft is concerned
 103  4*4*4*2
 104  */
 105
 106 typedef struct kiss_fft_state{
 107     int nfft;
 108 #ifndef FIXED_POINT
 109     kiss_fft_scalar scale;
 110 #endif
 111     int shift;
 112     celt_int16 factors[2*MAXFACTORS];
 113     const celt_int16 *bitrev;
 114     const kiss_twiddle_cpx *twiddles;
 115 } kiss_fft_state;
 116
 117 //typedef struct kiss_fft_state* kiss_fft_cfg;
 118
 119 /**
 120  *  kiss_fft_alloc
 121  *
 122  *  Initialize a FFT (or IFFT) algorithm's cfg/state buffer.
 123  *
 124  *  typical usage:      kiss_fft_cfg mycfg=kiss_fft_alloc(1024,0,NULL,NULL);
 125  *
 126  *  The return value from fft_alloc is a cfg buffer used internally
 127  *  by the fft routine or NULL.
 128  *
 129  *  If lenmem is NULL, then kiss_fft_alloc will allocate a cfg buffer using malloc.
 130  *  The returned value should be free()d when done to avoid memory leaks.
 131  *
 132  *  The state can be placed in a user supplied buffer 'mem':
 133  *  If lenmem is not NULL and mem is not NULL and *lenmem is large enough,
 134  *      then the function places the cfg in mem and the size used in *lenmem
 135  *      and returns mem.
 136  *
 137  *  If lenmem is not NULL and ( mem is NULL or *lenmem is not large enough),
 138  *      then the function returns NULL and places the minimum cfg
 139  *      buffer size in *lenmem.
 140  * */
 141
 142 kiss_fft_state *kiss_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem, const kiss_fft_state *base);
 143
 144 kiss_fft_state *kiss_fft_alloc(int nfft,void * mem,size_t * lenmem);
 145
 146 /**
 147  * kiss_fft(cfg,in_out_buf)
 148  *
 149  * Perform an FFT on a complex input buffer.
 150  * for a forward FFT,
 151  * fin should be  f[0] , f[1] , ... ,f[nfft-1]
 152  * fout will be   F[0] , F[1] , ... ,F[nfft-1]
 153  * Note that each element is complex and can be accessed like
 154     f[k].r and f[k].i
 155  * */
 156 void kiss_fft(const kiss_fft_state *cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout);
 157 void kiss_ifft(const kiss_fft_state *cfg,const kiss_fft_cpx *fin,kiss_fft_cpx *fout);
 158
 159 void kiss_fft_free(const kiss_fft_state *cfg);
 160
 161
 162 #ifdef __cplusplus
 163 }
 164 #endif
 165
 166 #endif