Chris@366: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
Chris@366: /*
Chris@366:     Constant-Q library
Chris@366:     Copyright (c) 2013-2014 Queen Mary, University of London
Chris@366: 
Chris@366:     Permission is hereby granted, free of charge, to any person
Chris@366:     obtaining a copy of this software and associated documentation
Chris@366:     files (the "Software"), to deal in the Software without
Chris@366:     restriction, including without limitation the rights to use, copy,
Chris@366:     modify, merge, publish, distribute, sublicense, and/or sell copies
Chris@366:     of the Software, and to permit persons to whom the Software is
Chris@366:     furnished to do so, subject to the following conditions:
Chris@366: 
Chris@366:     The above copyright notice and this permission notice shall be
Chris@366:     included in all copies or substantial portions of the Software.
Chris@366: 
Chris@366:     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
Chris@366:     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
Chris@366:     MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
Chris@366:     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
Chris@366:     CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
Chris@366:     CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
Chris@366:     WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Chris@366: 
Chris@366:     Except as contained in this notice, the names of the Centre for
Chris@366:     Digital Music; Queen Mary, University of London; and Chris Cannam
Chris@366:     shall not be used in advertising or otherwise to promote the sale,
Chris@366:     use or other dealings in this Software without prior written
Chris@366:     authorization.
Chris@366: */
Chris@366: 
Chris@366: #include "FFT.h"
Chris@366: 
Chris@366: #include "MathUtilities.h"
Chris@366: 
Chris@366: #include "kiss_fft.h"
Chris@366: #include "kiss_fftr.h"
Chris@366: 
Chris@366: #include <cmath>
Chris@366: 
Chris@366: #include <iostream>
Chris@366: 
Chris@366: #include <stdexcept>
Chris@366: 
Chris@366: class FFT::D
Chris@366: {
Chris@366: public:
Chris@366:     D(int n) : m_n(n) {
Chris@366:         m_planf = kiss_fft_alloc(m_n, 0, NULL, NULL);
Chris@366:         m_plani = kiss_fft_alloc(m_n, 1, NULL, NULL);
Chris@366:         m_kin = new kiss_fft_cpx[m_n];
Chris@366:         m_kout = new kiss_fft_cpx[m_n];
Chris@366:     }
Chris@366: 
Chris@366:     ~D() {
Chris@366:         kiss_fft_free(m_planf);
Chris@366:         kiss_fft_free(m_plani);
Chris@366:         delete[] m_kin;
Chris@366:         delete[] m_kout;
Chris@366:     }
Chris@366: 
Chris@366:     void process(bool inverse,
Chris@366:                  const double *ri,
Chris@366:                  const double *ii,
Chris@366:                  double *ro,
Chris@366:                  double *io) {
Chris@366: 
Chris@366:         for (int i = 0; i < m_n; ++i) {
Chris@366:             m_kin[i].r = ri[i];
Chris@366:             m_kin[i].i = (ii ? ii[i] : 0.0);
Chris@366:         }
Chris@366: 
Chris@366:         if (!inverse) {
Chris@366: 
Chris@366:             kiss_fft(m_planf, m_kin, m_kout);
Chris@366: 
Chris@366:             for (int i = 0; i < m_n; ++i) {
Chris@366:                 ro[i] = m_kout[i].r;
Chris@366:                 io[i] = m_kout[i].i;
Chris@366:             }
Chris@366: 
Chris@366:         } else {
Chris@366: 
Chris@366:             kiss_fft(m_plani, m_kin, m_kout);
Chris@366: 
Chris@366:             double scale = 1.0 / m_n;
Chris@366: 
Chris@366:             for (int i = 0; i < m_n; ++i) {
Chris@366:                 ro[i] = m_kout[i].r * scale;
Chris@366:                 io[i] = m_kout[i].i * scale;
Chris@366:             }
Chris@366:         }
Chris@366:     }
Chris@366:     
Chris@366: private:
Chris@366:     int m_n;
Chris@366:     kiss_fft_cfg m_planf;
Chris@366:     kiss_fft_cfg m_plani;
Chris@366:     kiss_fft_cpx *m_kin;
Chris@366:     kiss_fft_cpx *m_kout;
Chris@366: };        
Chris@366: 
Chris@366: FFT::FFT(int n) :
Chris@366:     m_d(new D(n))
Chris@366: {
Chris@366: }
Chris@366: 
Chris@366: FFT::~FFT()
Chris@366: {
Chris@366:     delete m_d;
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: FFT::process(bool inverse,
Chris@366:              const double *p_lpRealIn, const double *p_lpImagIn,
Chris@366:              double *p_lpRealOut, double *p_lpImagOut)
Chris@366: {
Chris@366:     m_d->process(inverse,
Chris@366:                  p_lpRealIn, p_lpImagIn,
Chris@366:                  p_lpRealOut, p_lpImagOut);
Chris@366: }
Chris@366:     
Chris@366: class FFTReal::D
Chris@366: {
Chris@366: public:
Chris@366:     D(int n) : m_n(n) {
Chris@366:         if (n % 2) {
Chris@366:             throw std::invalid_argument
Chris@366:                 ("nsamples must be even in FFTReal constructor");
Chris@366:         }
Chris@366:         m_planf = kiss_fftr_alloc(m_n, 0, NULL, NULL);
Chris@366:         m_plani = kiss_fftr_alloc(m_n, 1, NULL, NULL);
Chris@366:         m_c = new kiss_fft_cpx[m_n];
Chris@366:     }
Chris@366: 
Chris@366:     ~D() {
Chris@366:         kiss_fftr_free(m_planf);
Chris@366:         kiss_fftr_free(m_plani);
Chris@366:         delete[] m_c;
Chris@366:     }
Chris@366: 
Chris@366:     void forward(const double *ri, double *ro, double *io) {
Chris@366: 
Chris@366:         kiss_fftr(m_planf, ri, m_c);
Chris@366: 
Chris@366:         for (int i = 0; i <= m_n/2; ++i) {
Chris@366:             ro[i] = m_c[i].r;
Chris@366:             io[i] = m_c[i].i;
Chris@366:         }
Chris@366: 
Chris@366:         for (int i = 0; i + 1 < m_n/2; ++i) {
Chris@366:             ro[m_n - i - 1] =  ro[i + 1];
Chris@366:             io[m_n - i - 1] = -io[i + 1];
Chris@366:         }
Chris@366:     }
Chris@366: 
Chris@366:     void forwardMagnitude(const double *ri, double *mo) {
Chris@366: 
Chris@366:         double *io = new double[m_n];
Chris@366: 
Chris@366:         forward(ri, mo, io);
Chris@366: 
Chris@366:         for (int i = 0; i < m_n; ++i) {
Chris@366:             mo[i] = sqrt(mo[i] * mo[i] + io[i] * io[i]);
Chris@366:         }
Chris@366: 
Chris@366:         delete[] io;
Chris@366:     }
Chris@366: 
Chris@366:     void inverse(const double *ri, const double *ii, double *ro) {
Chris@366: 
Chris@366:         // kiss_fftr.h says
Chris@366:         // "input freqdata has nfft/2+1 complex points"
Chris@366: 
Chris@366:         for (int i = 0; i < m_n/2 + 1; ++i) {
Chris@366:             m_c[i].r = ri[i];
Chris@366:             m_c[i].i = ii[i];
Chris@366:         }
Chris@366:         
Chris@366:         kiss_fftri(m_plani, m_c, ro);
Chris@366: 
Chris@366:         double scale = 1.0 / m_n;
Chris@366: 
Chris@366:         for (int i = 0; i < m_n; ++i) {
Chris@366:             ro[i] *= scale;
Chris@366:         }
Chris@366:     }
Chris@366: 
Chris@366: private:
Chris@366:     int m_n;
Chris@366:     kiss_fftr_cfg m_planf;
Chris@366:     kiss_fftr_cfg m_plani;
Chris@366:     kiss_fft_cpx *m_c;
Chris@366: };
Chris@366: 
Chris@366: FFTReal::FFTReal(int n) :
Chris@366:     m_d(new D(n)) 
Chris@366: {
Chris@366: }
Chris@366: 
Chris@366: FFTReal::~FFTReal()
Chris@366: {
Chris@366:     delete m_d;
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: FFTReal::forward(const double *ri, double *ro, double *io)
Chris@366: {
Chris@366:     m_d->forward(ri, ro, io);
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: FFTReal::forwardMagnitude(const double *ri, double *mo)
Chris@366: {
Chris@366:     m_d->forwardMagnitude(ri, mo);
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: FFTReal::inverse(const double *ri, const double *ii, double *ro)
Chris@366: {
Chris@366:     m_d->inverse(ri, ii, ro);
Chris@366: }
Chris@366: 
Chris@366: 
Chris@366: