From fef594c82518a8fe4c96794852c1fc849c0ed3b3 Mon Sep 17 00:00:00 2001 From: Roland Stigge Date: Sun, 17 Feb 2019 12:55:13 +0100 Subject: Added tunerdemo --- .gitignore | 3 +- Makefile | 29 +++++- autocorrelation.cpp | 29 ++++++ autocorrelation.h | 20 ++++ fft.cpp | 26 ----- fft.h | 11 -- main.cpp | 270 ------------------------------------------------- testsuite.cpp | 283 ++++++++++++++++++++++++++++++++++++++++++++++++++++ tuner.cpp | 24 +++++ tuner.h | 28 ++++++ tunerdemo.cpp | 35 +++++++ 11 files changed, 445 insertions(+), 313 deletions(-) create mode 100644 autocorrelation.cpp create mode 100644 autocorrelation.h delete mode 100644 main.cpp create mode 100644 testsuite.cpp create mode 100644 tuner.cpp create mode 100644 tuner.h create mode 100644 tunerdemo.cpp diff --git a/.gitignore b/.gitignore index 360a8c3..149e563 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ *.o -fft +tunerdemo +testsuite diff --git a/Makefile b/Makefile index b945f7c..c78f4d7 100644 --- a/Makefile +++ b/Makefile @@ -7,20 +7,39 @@ CXXFLAGS=-stdlib=libc++ -Wall -O2 -std=c++17 #CXXFLAGS=-Wall -O2 -std=c++17 -nostdinc++ -I/usr/lib/llvm-7/include/c++/v1 -nodefaultlibs -lc++ -lc++abi -lm -lc -lgcc_s -lgcc # -march=native -mtune=native # doesn't help for gcc -all: fft +DESTDIR=/ +PREFIX=/usr/local/bin -fft: fft.o main.o +all: tunerdemo testsuite + +tunerdemo: fft.o autocorrelation.o tuner.o tunerdemo.o + $(CXX) $(CXXFLAGS) -o $@ $^ + +testsuite: fft.o autocorrelation.o tuner.o testsuite.o $(CXX) $(CXXFLAGS) -o $@ $^ fft.o: fft.cpp fft.h $(CXX) $(CXXFLAGS) -c -o $@ $< -main.o: main.cpp fft.h +autocorrelation.o: autocorrelation.cpp autocorrelation.h + $(CXX) $(CXXFLAGS) -c -o $@ $< + +tuner.o: tuner.cpp tuner.h $(CXX) $(CXXFLAGS) -c -o $@ $< +testsuite.o: testsuite.cpp fft.h autocorrelation.h tuner.h + $(CXX) $(CXXFLAGS) -c -o $@ $< + +tunerdemo.o: tunerdemo.cpp fft.h autocorrelation.h tuner.h + $(CXX) $(CXXFLAGS) -c -o $@ $< + +test: testsuite + ./testsuite + install: + install tunerdemo $(DESTDIR)/$(PREFIX)/tunerdemo clean: - rm -f fft *.o + rm -f tunerdemo *.o -.PHONY: clean +.PHONY: clean install all test diff --git a/autocorrelation.cpp b/autocorrelation.cpp new file mode 100644 index 0000000..5c778c1 --- /dev/null +++ b/autocorrelation.cpp @@ -0,0 +1,29 @@ +#include "autocorrelation.h" + +#include "fft.h" + +struct RIT::AutoCorrelation::Impl { +public: + Impl(int size): mFft(std::make_shared(size)), mIfft(mFft) {} + std::shared_ptr mFft; + RIT::IFFT mIfft; +}; + +RIT::AutoCorrelation::AutoCorrelation(int size): mImpl(std::make_unique(size)) +{ +} + +RIT::AutoCorrelation::~AutoCorrelation() +{ +} + +std::vector> RIT::AutoCorrelation::operator()(const std::vector> &v) const +{ + auto result = (*mImpl->mFft)(v); + + std::transform(std::begin(result), std::end(result), std::begin(result), + [=](const auto& x){return x * std::conj(x);}); + + return mImpl->mIfft(result); +} + diff --git a/autocorrelation.h b/autocorrelation.h new file mode 100644 index 0000000..3be0802 --- /dev/null +++ b/autocorrelation.h @@ -0,0 +1,20 @@ +#pragma once + +#include +#include +#include + +namespace RIT { + +class AutoCorrelation { +public: + AutoCorrelation(int size); + ~AutoCorrelation(); + std::vector> operator()(const std::vector> &v) const; + +private: + struct Impl; + std::unique_ptr mImpl; +}; // class AutoCorrelation + +} // namespace RIT diff --git a/fft.cpp b/fft.cpp index 7d76e23..a8009ad 100644 --- a/fft.cpp +++ b/fft.cpp @@ -42,7 +42,6 @@ RIT::FFT::FFT(int size, bool halfOnly): mSize(size), order(size), expLUT(size/2) } } - std::vector> RIT::FFT::operator()(const std::vector> &v) const { if (v.size() != mSize) throw std::length_error("Bad input size"); @@ -159,28 +158,3 @@ std::vector> RIT::IFFT::operator()(const std::vector(size)), mIfft(mFft) {} - std::shared_ptr mFft; - RIT::IFFT mIfft; -}; - -RIT::AutoCorrelation::AutoCorrelation(int size): mImpl(std::make_unique(size)) -{ -} - -RIT::AutoCorrelation::~AutoCorrelation() -{ -} - -std::vector> RIT::AutoCorrelation::operator()(const std::vector> &v) const -{ - auto result = (*mImpl->mFft)(v); - - std::transform(std::begin(result), std::end(result), std::begin(result), - [=](const auto& x){return x * std::conj(x);}); - - return mImpl->mIfft(result); -} - diff --git a/fft.h b/fft.h index 8c1e161..980b4b3 100644 --- a/fft.h +++ b/fft.h @@ -44,17 +44,6 @@ private: std::unique_ptr mImpl; }; // class IFFT -class AutoCorrelation { -public: - AutoCorrelation(int size); - ~AutoCorrelation(); - std::vector> operator()(const std::vector> &v) const; - -private: - struct Impl; - std::unique_ptr mImpl; -}; // class AutoCorrelation - std::vector magnitudes(std::vector>& v); } // namespace RIT diff --git a/main.cpp b/main.cpp deleted file mode 100644 index 3945cff..0000000 --- a/main.cpp +++ /dev/null @@ -1,270 +0,0 @@ -// FFT Test - -#include "fft.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -const std::complex i(0, 1); - -const double tolerance = 0.000001; - -using namespace std::complex_literals; - -/// CPU time clock -class Timer { -public: - Timer(): mStart(std::clock()){} - void start(){mStart = std::clock();} - double elapsed() { return (double(std::clock()) - mStart) / CLOCKS_PER_SEC; } - static double precision() { - static double result{0}; - - if (result != 0) - return result; - - std::clock_t start = std::clock(); - while (start == std::clock()) {} - start = std::clock(); - - std::clock_t end = start; - while (end == std::clock()) {} - end = std::clock(); - - result = (double(end) - start) / CLOCKS_PER_SEC; - return result; - } -private: - std::clock_t mStart; -}; - -// (Slow) DFT -std::vector> dft(const std::vector> &v) { - std::vector> result(v.size(), 0); - - const double N = v.size(); - - for (int k = 0; k < v.size(); k++) { - for (int j = 0; j < result.size(); j++) { - result[k] += v[j] * std::exp(-i * 2. * M_PI * double(k * j) / N); - } - } - - return result; -} - -std::vector freqs{ 2, 5, 11, 17, 29 }; // known freqs for testing - -void generate(std::vector>& v) { - for (int i = 0; i < v.size(); i++) { - v[i] = 0.; - // sum several known sinusoids into v[] - for(int j = 0; j < freqs.size(); j++) - v[i] += sin(2 * M_PI * freqs[j] * i / v.size() ); - } -} - -namespace CooleyTukey { - -// separate even/odd elements to lower/upper halves of array respectively. -// Due to Butterfly combinations, this turns out to be the simplest way -// to get the job done without clobbering the wrong elements. -void separate(std::vector>::iterator a, int n) { - std::vector> b(n/2); - for(int i=0; i>::iterator X, int N) { - if(N < 2) { - // bottom of recursion. - // Do nothing here, because already X[0] = x[0] - } else { - separate(X,N); // all evens to lower half, all odds to upper half - fft_recursive(X, N/2); // recurse even items - fft_recursive(X+N/2, N/2); // recurse odd items - // combine results of two half recursions - for(int k=0; k e = X[k ]; // even - std::complex o = X[k+N/2]; // odd - // w is the "twiddle-factor" - std::complex w = exp( std::complex(0,-2.*M_PI*k/N) ); - X[k ] = e + w * o; - X[k+N/2] = e - w * o; - } - } -} - -// Cooley-Tukey -std::vector> fft(const std::vector> &v) { - std::vector> result(v); - - fft_recursive(std::begin(result), result.size()); - - return result; -} -}; // namespace CooleyTukey - -class Measure { - Timer mTimer; - -public: - using Data = std::vector>; - -protected: - Measure* mReference; // Reference measurement: we should calculate similar to this one and be faster than this one - - const Data& mIn; - Data mResult; - - std::string mName; - double mElapsed; - -public: - Measure(const Data& in): mReference(nullptr), mIn(in), mResult(in.size()) {} - - virtual void run_impl() = 0; // implemented by subclasses - - void run() { - mTimer.start(); - run_impl(); - mElapsed = mTimer.elapsed(); - std::cout << mName << ": " << mElapsed << "s\n"; - - if (mReference) { - if (mResult != mReference->mResult) { - double diff = std::transform_reduce(std::begin(mResult), std::end(mResult), std::begin(mReference->mResult), double(0.0), - [](const double& x, const double& y) -> double - { return x + y;}, - [](const std::complex& x, const std::complex&y) -> double - { return abs(y - x);} - ); - if (diff > tolerance) - std::cout << "Error: Results diff: " << diff << "\n"; - } - - if (mElapsed > mReference->mElapsed) { - std::cout << "Error: " << mName << " too slow!\n"; - } - } - } - - double elapsed() { return mElapsed; } - - Data& result() { return mResult; } -}; - -class MeasureDFT: public Measure { -public: - MeasureDFT(const Data& in): Measure(in){ mName = "DFT";} - void run_impl() override { - mResult = dft(mIn); - } -}; - -class MeasureFFT: public Measure { -public: - MeasureFFT(const Data& in, Measure& reference): Measure(in) { mName = "FFT Cooley-Tukey"; mReference = &reference;} - void run_impl() override { - mResult = CooleyTukey::fft(mIn); - } -}; - -class MeasureFFT_RR: public Measure { - RIT::FFT mRR; -public: - MeasureFFT_RR(const Data& in, Measure& reference): Measure(in), mRR(in.size()){ mName = "FFT RR"; mReference = &reference;} - void run_impl() override { - mResult = mRR(mIn); - } -}; - -class MeasureFFT_RR_half: public Measure { - RIT::FFT mRR; -public: - MeasureFFT_RR_half(const Data& in, Measure& reference): Measure(in), mRR(in.size(), true){ mName = "FFT RR half"; mReference = &reference; } - void run_impl() override { - mResult = mRR(mIn); - } -}; - -class MeasureFFT_RR_half_magnitudes: public Measure { - RIT::FFT mRR; -public: - MeasureFFT_RR_half_magnitudes(const Data& in, Measure& reference): Measure(in), mRR(in.size(), true){ mName = "FFT RR half magnitudes"; mReference = &reference; } - void run_impl() override { - mResult = mRR(mIn); - RIT::magnitudes(mResult); - } -}; - -class MeasureIFFT_RR: public Measure { - RIT::IFFT mIFFT; -public: - MeasureIFFT_RR(const Data& in): Measure(in), mIFFT(in.size()) { mName = "IFFT RR";} - void run_impl() override { - mResult = mIFFT(mIn); - } -}; - -class MeasureAutoCorrelation_RR: public Measure { - RIT::AutoCorrelation mAC; -public: - MeasureAutoCorrelation_RR(const Data& in): Measure(in), mAC(in.size()) { mName = "AutoCorrelation RR";} - void run_impl() override { - mResult = mAC(mIn); - } -}; - -int main(int argc, char* argv[]) { - std::vector> v(4096, 0); - - generate(v); - - std::cout << "Timer precision: " << Timer::precision() << "s\n"; - - MeasureDFT measureDFT(v); - measureDFT.run(); - - MeasureFFT measureFFT(v, measureDFT); - measureFFT.run(); - - MeasureFFT_RR measureFFT_RR(v, measureFFT); - measureFFT_RR.run(); - - MeasureFFT_RR_half measureFFT_RR_half(v, measureFFT_RR); - measureFFT_RR_half.run(); - - MeasureFFT_RR_half_magnitudes measureFFT_RR_half_magnitudes(v, measureDFT); - measureFFT_RR_half_magnitudes.run(); - - MeasureIFFT_RR measureIFFT_RR(v); - measureIFFT_RR.run(); - - MeasureAutoCorrelation_RR measureAutoCorrelation_RR(v); - measureAutoCorrelation_RR.run(); - - return 0; -} - - diff --git a/testsuite.cpp b/testsuite.cpp new file mode 100644 index 0000000..2b8042b --- /dev/null +++ b/testsuite.cpp @@ -0,0 +1,283 @@ +// FFT Test + +#include "fft.h" +#include "autocorrelation.h" +#include "tuner.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +const std::complex i(0, 1); + +const double tolerance = 0.000001; + +using namespace std::complex_literals; + +/// CPU time clock +class Timer { +public: + Timer(): mStart(std::clock()){} + void start(){mStart = std::clock();} + double elapsed() { return (double(std::clock()) - mStart) / CLOCKS_PER_SEC; } + static double precision() { + static double result{0}; + + if (result != 0) + return result; + + std::clock_t start = std::clock(); + while (start == std::clock()) {} + start = std::clock(); + + std::clock_t end = start; + while (end == std::clock()) {} + end = std::clock(); + + result = (double(end) - start) / CLOCKS_PER_SEC; + return result; + } +private: + std::clock_t mStart; +}; + +// (Slow) DFT +std::vector> dft(const std::vector> &v) { + std::vector> result(v.size(), 0); + + const double N = v.size(); + + for (int k = 0; k < v.size(); k++) { + for (int j = 0; j < result.size(); j++) { + result[k] += v[j] * std::exp(-i * 2. * M_PI * double(k * j) / N); + } + } + + return result; +} + +std::vector freqs{ 2, 5, 11, 17, 29 }; // known freqs for testing + +void generate(std::vector>& v) { + for (int i = 0; i < v.size(); i++) { + v[i] = 0.; + // sum several known sinusoids into v[] + for(int j = 0; j < freqs.size(); j++) + v[i] += sin(2 * M_PI * freqs[j] * i / v.size() ); + } +} + +namespace CooleyTukey { + +// separate even/odd elements to lower/upper halves of array respectively. +// Due to Butterfly combinations, this turns out to be the simplest way +// to get the job done without clobbering the wrong elements. +void separate(std::vector>::iterator a, int n) { + std::vector> b(n/2); + for(int i=0; i>::iterator X, int N) { + if(N < 2) { + // bottom of recursion. + // Do nothing here, because already X[0] = x[0] + } else { + separate(X,N); // all evens to lower half, all odds to upper half + fft_recursive(X, N/2); // recurse even items + fft_recursive(X+N/2, N/2); // recurse odd items + // combine results of two half recursions + for(int k=0; k e = X[k ]; // even + std::complex o = X[k+N/2]; // odd + // w is the "twiddle-factor" + std::complex w = exp( std::complex(0,-2.*M_PI*k/N) ); + X[k ] = e + w * o; + X[k+N/2] = e - w * o; + } + } +} + +// Cooley-Tukey +std::vector> fft(const std::vector> &v) { + std::vector> result(v); + + fft_recursive(std::begin(result), result.size()); + + return result; +} +}; // namespace CooleyTukey + +class Measure { + Timer mTimer; + +public: + using Data = std::vector>; + +protected: + Measure* mReference; // Reference measurement: we should calculate similar to this one and be faster than this one + + const Data& mIn; + Data mResult; + + std::string mName; + double mElapsed; + +public: + Measure(const Data& in): mReference(nullptr), mIn(in), mResult(in.size()) {} + + virtual void run_impl() = 0; // implemented by subclasses + + void run() { + mTimer.start(); + run_impl(); + mElapsed = mTimer.elapsed(); + std::cout << mName << ": " << mElapsed << "s\n"; + + if (mReference) { + if (mResult != mReference->mResult) { + double diff = std::transform_reduce(std::begin(mResult), std::end(mResult), std::begin(mReference->mResult), double(0.0), + [](const double& x, const double& y) -> double + { return x + y;}, + [](const std::complex& x, const std::complex&y) -> double + { return abs(y - x);} + ); + if (diff > tolerance) + std::cout << "Error: Results diff: " << diff << "\n"; + } + + if (mElapsed > mReference->mElapsed) { + std::cout << "Error: " << mName << " too slow!\n"; + } + } + } + + double elapsed() { return mElapsed; } + + Data& result() { return mResult; } +}; + +class MeasureDFT: public Measure { +public: + MeasureDFT(const Data& in): Measure(in){ mName = "DFT";} + void run_impl() override { + mResult = dft(mIn); + } +}; + +class MeasureFFT: public Measure { +public: + MeasureFFT(const Data& in, Measure& reference): Measure(in) { mName = "FFT Cooley-Tukey"; mReference = &reference;} + void run_impl() override { + mResult = CooleyTukey::fft(mIn); + } +}; + +class MeasureFFT_RR: public Measure { + RIT::FFT mRR; +public: + MeasureFFT_RR(const Data& in, Measure& reference): Measure(in), mRR(in.size()){ mName = "FFT RR"; mReference = &reference;} + void run_impl() override { + mResult = mRR(mIn); + } +}; + +class MeasureFFT_RR_half: public Measure { + RIT::FFT mRR; +public: + MeasureFFT_RR_half(const Data& in, Measure& reference): Measure(in), mRR(in.size(), true){ mName = "FFT RR half"; mReference = &reference; } + void run_impl() override { + mResult = mRR(mIn); + } +}; + +class MeasureFFT_RR_half_magnitudes: public Measure { + RIT::FFT mRR; +public: + MeasureFFT_RR_half_magnitudes(const Data& in, Measure& reference): Measure(in), mRR(in.size(), true){ mName = "FFT RR half magnitudes"; mReference = &reference; } + void run_impl() override { + mResult = mRR(mIn); + RIT::magnitudes(mResult); + } +}; + +class MeasureIFFT_RR: public Measure { + RIT::IFFT mIFFT; +public: + MeasureIFFT_RR(const Data& in): Measure(in), mIFFT(in.size()) { mName = "IFFT RR";} + void run_impl() override { + mResult = mIFFT(mIn); + } +}; + +class MeasureAutoCorrelation_RR: public Measure { + RIT::AutoCorrelation mAC; +public: + MeasureAutoCorrelation_RR(const Data& in): Measure(in), mAC(in.size()) { mName = "AutoCorrelation RR";} + void run_impl() override { + mResult = mAC(mIn); + } +}; + +class MeasureTuner_RR: public Measure { + RIT::Tuner mTuner; + RIT::Pitch mPitch; +public: + MeasureTuner_RR(const Data& in): Measure(in), mTuner(in.size(), 44100) { mName = "Tuner RR";} + void run_impl() override { + mPitch = mTuner(mIn); + } +}; + +int main(int argc, char* argv[]) { + std::vector> v(4096, 0); + + generate(v); + + std::cout << "Timer precision: " << Timer::precision() << "s\n"; + + MeasureDFT measureDFT(v); + measureDFT.run(); + + MeasureFFT measureFFT(v, measureDFT); + measureFFT.run(); + + MeasureFFT_RR measureFFT_RR(v, measureFFT); + measureFFT_RR.run(); + + MeasureFFT_RR_half measureFFT_RR_half(v, measureFFT_RR); + measureFFT_RR_half.run(); + + MeasureFFT_RR_half_magnitudes measureFFT_RR_half_magnitudes(v, measureDFT); + measureFFT_RR_half_magnitudes.run(); + + MeasureIFFT_RR measureIFFT_RR(v); + measureIFFT_RR.run(); + + MeasureAutoCorrelation_RR measureAutoCorrelation_RR(v); + measureAutoCorrelation_RR.run(); + + MeasureTuner_RR measureTuner_RR(v); + measureTuner_RR.run(); + + return 0; +} diff --git a/tuner.cpp b/tuner.cpp new file mode 100644 index 0000000..d1833a3 --- /dev/null +++ b/tuner.cpp @@ -0,0 +1,24 @@ +#include "tuner.h" + +#include "autocorrelation.h" +#include "fft.h" + +struct RIT::Tuner::Impl { +public: + Impl(int size, int f_sample): mAC(size), m_f_sample(f_sample) {} + RIT::AutoCorrelation mAC; + int m_f_sample; +}; + +RIT::Tuner::Tuner(int size, int f_sample): mImpl(std::make_unique(size, f_sample)) +{ +} + +RIT::Tuner::~Tuner(){} + +RIT::Pitch RIT::Tuner::operator() (const std::vector> &v) +{ + std::vector> autoCorrelation = mImpl->mAC(v); + + return Pitch(); +} diff --git a/tuner.h b/tuner.h new file mode 100644 index 0000000..df17c0f --- /dev/null +++ b/tuner.h @@ -0,0 +1,28 @@ +#pragma once + +#include +#include +#include +#include + +namespace RIT { + +struct Pitch { + double f{}; // in Hz + double deviation{}; // 0.0 == perfect, +/-1.0: at next note + std::string name; // "" for none, "A", "A#", ... for notes +}; + +class Tuner { +public: + Tuner(int size, int f_sample); + ~Tuner(); + + Pitch operator() (const std::vector> &v); + +private: + struct Impl; + std::unique_ptr mImpl; +}; // class Tuner + +} // namespace RIT diff --git a/tunerdemo.cpp b/tunerdemo.cpp new file mode 100644 index 0000000..716bd8e --- /dev/null +++ b/tunerdemo.cpp @@ -0,0 +1,35 @@ +#include "tuner.h" + +#include +#include +#include + +using namespace std::chrono_literals; + +const int sampleFrequency = 44100; +const int fftSize = 4096; + +std::vector> sample() +{ + return std::vector>(fftSize, 0.0); +} + +int main(int argc, char* argv[]) { + RIT::Tuner tuner(fftSize, sampleFrequency); + + std::vector> dataIn = sample(); + + while (true) { + auto start = std::chrono::high_resolution_clock::now(); + RIT::Pitch pitch = tuner(dataIn); + auto end = std::chrono::high_resolution_clock::now(); + std::cout << "Detected Note: " << pitch.name + << " Deviation: " << pitch.deviation + << " Frequency: " << pitch.f + << ", took " << std::chrono::nanoseconds(end - start).count() * 0.000001 << "ms" + << std::endl; + std::this_thread::sleep_until(start + 100ms); + } + + return 0; +} -- cgit v1.2.3