[fft] - added kissfft based rfft implementation and unit tests for it

3 files changed, 167 insertions, 0 deletions

diff --git a/xbmc/utils/rfft.cpp b/xbmc/utils/rfft.cpp
new file mode 100644
index 0000000000..f2e6a255fc
--- /dev/null
+++ b/xbmc/utils/rfft.cpp
@@ -0,0 +1,75 @@
+/*
+ *      Copyright (C) 2015 Team Kodi
+ *      http://kodi.tv
+ *
+ *  This Program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2, or (at your option)
+ *  any later version.
+ *
+ *  This Program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with XBMC; see the file COPYING.  If not, see
+ *  <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "rfft.h"
+
+#if defined(TARGET_WINDOWS) && !defined(_USE_MATH_DEFINES)
+#define _USE_MATH_DEFINES
+#endif
+#include <math.h>
+
+RFFT::RFFT(int size, bool windowed) :
+  m_size(size), m_windowed(windowed)
+{
+  m_cfg = kiss_fftr_alloc(m_size,0,nullptr,nullptr);
+}
+
+void RFFT::calc(const float* input, float* output)
+{
+  // temporary buffers
+  std::vector<kiss_fft_scalar> linput(m_size), rinput(m_size);
+  std::vector<kiss_fft_cpx> loutput(m_size), routput(m_size);
+
+  for (size_t i=0;i<m_size;++i)
+  {
+    linput[i] = input[2*i];
+    rinput[i] = input[2*i+1];
+  }
+
+  if (m_windowed)
+  {
+    hann(linput);
+    hann(rinput);
+  }
+
+  // transform channels
+  kiss_fftr(m_cfg, &linput[0], &loutput[0]);
+  kiss_fftr(m_cfg, &rinput[0], &routput[0]);
+
+  auto&& filter = [&](kiss_fft_cpx& data)
+  {
+    return sqrt(data.r*data.r+data.i*data.i) * 2.0/m_size * (m_windowed?sqrt(8.0/3.0):1.0);
+  };
+
+  // interleave while taking magnitudes and normalizing
+  for (size_t i=0;i<m_size/2;++i)
+  {
+    output[2*i] = filter(loutput[i]);
+    output[2*i+1] = filter(routput[i]);
+  }
+}
+
+#include <iostream>
+
+void RFFT::hann(std::vector<kiss_fft_scalar>& data)
+{
+  for (size_t i=0;i<data.size();++i)
+    data[i] *= 0.5*(1.0-cos(2*M_PI*i/(data.size()-1)));
+}
diff --git a/xbmc/utils/rfft.h b/xbmc/utils/rfft.h
new file mode 100644
index 0000000000..2241024449
--- /dev/null
+++ b/xbmc/utils/rfft.h
@@ -0,0 +1,46 @@
+#pragma once
+/*
+ *      Copyright (C) 2015 Team Kodi
+ *      http://kodi.tv
+ *
+ *  This Program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2, or (at your option)
+ *  any later version.
+ *
+ *  This Program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with XBMC; see the file COPYING.  If not, see
+ *  <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "contrib/kissfft/kiss_fftr.h"
+#include <vector>
+
+//! \brief Class performing a RFFT of interleaved stereo data.
+class RFFT
+{
+public:
+  //! \brief The constructor creates a RFFT plan.
+  //! \brief size Length of time data for a single channel.
+  //! \brief windowed Whether or not to apply a Hann window to data.
+  RFFT(int size, bool windowed=false);
+
+  //! \brief Calculate FFTs
+  //! \param input Input data of size 2*m_size
+  //! \param output Output data of size m_size.
+  void calc(const float* input, float* output);
+protected:
+  //! \brief Apply a Hann window to a buffer.
+  //! \param data Vector with data to apply window to.
+  static void hann(std::vector<kiss_fft_scalar>& data);
+
+  size_t m_size;       //!< Size for a single channel.
+  bool m_windowed;     //!< Whether or not a Hann window is applied.
+  kiss_fftr_cfg m_cfg; //!< FFT plan
+};
diff --git a/xbmc/utils/test/Testrfft.cpp b/xbmc/utils/test/Testrfft.cpp
new file mode 100644
index 0000000000..3b382e6479
--- /dev/null
+++ b/xbmc/utils/test/Testrfft.cpp
@@ -0,0 +1,46 @@
+/*
+ *      Copyright (C) 2015 Team Kodi
+ *      http://kodi.tv
+ *
+ *  This Program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2, or (at your option)
+ *  any later version.
+ *
+ *  This Program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with XBMC; see the file COPYING.  If not, see
+ *  <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "utils/rfft.h"
+
+#include "gtest/gtest.h"
+
+TEST(TestRFFT, SimpleSignal)
+{
+  const int size = 32;
+  const int freq1 = 5;
+  const int freq2[] = {1,7};
+  std::vector<float> input(2*size);
+  std::vector<float> output(size);
+  for (size_t i=0;i<size;++i)
+  {
+    input[2*i] = cos(freq1*2.0*M_PI*i/size);
+    input[2*i+1] = cos(freq2[0]*2.0*M_PI*i/size)+cos(freq2[1]*2.0*M_PI*i/size);
+  }
+  RFFT transform(size, false);
+
+  transform.calc(&input[0], &output[0]);
+
+  for (size_t i=0;i<size/2;++i)
+  {
+    EXPECT_NEAR(output[2*i],(i==freq1?1.0:0.0), 1e-7);
+    EXPECT_NEAR(output[2*i+1], ((i==freq2[0]||i==freq2[1])?1.0:0.0), 1e-7);
+  }
+}