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 "CQInverse.h"
Chris@366: 
Chris@366: #include "dsp/Resampler.h"
Chris@366: #include "dsp/MathUtilities.h"
Chris@366: #include "dsp/FFT.h"
Chris@366: 
Chris@366: #include <algorithm>
Chris@366: #include <iostream>
Chris@366: #include <stdexcept>
Chris@366: 
Chris@366: #include <cmath>
Chris@366: 
Chris@366: using std::vector;
Chris@366: using std::cerr;
Chris@366: using std::endl;
Chris@366: 
Chris@366: //#define DEBUG_CQ 1
Chris@366: 
Chris@366: CQInverse::CQInverse(CQParameters params) :
Chris@366:     m_inparams(params),
Chris@366:     m_sampleRate(params.sampleRate),
Chris@366:     m_maxFrequency(params.maxFrequency),
Chris@366:     m_minFrequency(params.minFrequency),
Chris@366:     m_binsPerOctave(params.binsPerOctave),
Chris@366:     m_fft(0)
Chris@366: {
Chris@366:     if (m_minFrequency <= 0.0 || m_maxFrequency <= 0.0) {
Chris@366:         throw std::invalid_argument("Frequency extents must be positive");
Chris@366:     }
Chris@366: 
Chris@366:     initialise();
Chris@366: }
Chris@366: 
Chris@366: CQInverse::~CQInverse()
Chris@366: {
Chris@366:     delete m_fft;
Chris@366:     for (int i = 0; i < (int)m_upsamplers.size(); ++i) {
Chris@366:         delete m_upsamplers[i];
Chris@366:     }
Chris@366:     delete m_kernel;
Chris@366: }
Chris@366: 
Chris@366: double
Chris@366: CQInverse::getMinFrequency() const
Chris@366: {
Chris@366:     return m_p.minFrequency / pow(2.0, m_octaves - 1);
Chris@366: }
Chris@366: 
Chris@366: double
Chris@366: CQInverse::getBinFrequency(double bin) const
Chris@366: {
Chris@366:     // our bins are returned in high->low order
Chris@366:     bin = (getBinsPerOctave() * getOctaves()) - bin - 1;
Chris@366:     return getMinFrequency() * pow(2, (bin / getBinsPerOctave()));
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: CQInverse::initialise()
Chris@366: {
Chris@366:     m_octaves = int(ceil(log(m_maxFrequency / m_minFrequency) / log(2)));
Chris@366: 
Chris@366:     if (m_octaves < 1) {
Chris@366:         m_kernel = 0; // incidentally causing isValid() to return false
Chris@366:         return;
Chris@366:     }
Chris@366: 
Chris@366:     m_kernel = new CQKernel(m_inparams);
Chris@366:     m_p = m_kernel->getProperties();
Chris@366:     
Chris@366:     // Use exact powers of two for resampling rates. They don't have
Chris@366:     // to be related to our actual samplerate: the resampler only
Chris@366:     // cares about the ratio, but it only accepts integer source and
Chris@366:     // target rates, and if we start from the actual samplerate we
Chris@366:     // risk getting non-integer rates for lower octaves
Chris@366: 
Chris@366:     int sourceRate = pow(2, m_octaves);
Chris@366:     vector<int> latencies;
Chris@366: 
Chris@366:     // top octave, no resampling
Chris@366:     latencies.push_back(0);
Chris@366:     m_upsamplers.push_back(0);
Chris@366: 
Chris@366:     for (int i = 1; i < m_octaves; ++i) {
Chris@366: 
Chris@366:         int factor = pow(2, i);
Chris@366: 
Chris@366:         Resampler *r = new Resampler
Chris@366:             (sourceRate / factor, sourceRate, 50, 0.05);
Chris@366: 
Chris@366: #ifdef DEBUG_CQ
Chris@366:         cerr << "inverse: octave " << i << ": resample from " << sourceRate/factor << " to " << sourceRate << endl;
Chris@366: #endif
Chris@366: 
Chris@366: 	// See ConstantQ.cpp for discussion on latency -- output
Chris@366: 	// latency here is at target rate which, this way around, is
Chris@366: 	// what we want
Chris@366: 
Chris@366:         latencies.push_back(r->getLatency());
Chris@366:         m_upsamplers.push_back(r);
Chris@366:     }
Chris@366: 
Chris@366:     // additionally we will have fftHop latency at individual octave
Chris@366:     // rate (before upsampling) for the overlap-add in each octave
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366:         latencies[i] += m_p.fftHop * pow(2, i);
Chris@366:     }
Chris@366: 
Chris@366:     // Now reverse the drop adjustment made in ConstantQ to align the
Chris@366:     // atom centres across different octaves (but this time at output
Chris@366:     // sample rate)
Chris@366: 
Chris@366:     int emptyHops = m_p.firstCentre / m_p.atomSpacing;
Chris@366: 
Chris@366:     vector<int> pushes;
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366: 	int factor = pow(2, i);
Chris@366: 	int pushHops = emptyHops * pow(2, m_octaves - i - 1) - emptyHops;
Chris@366: 	int push = ((pushHops * m_p.fftHop) * factor) / m_p.atomsPerFrame;
Chris@366: 	pushes.push_back(push);
Chris@366:     }
Chris@366: 
Chris@366:     int maxLatLessPush = 0;
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366: 	int latLessPush = latencies[i] - pushes[i];
Chris@366: 	if (latLessPush > maxLatLessPush) maxLatLessPush = latLessPush;
Chris@366:     }
Chris@366: 
Chris@366:     int totalLatency = maxLatLessPush + 10;
Chris@366:     if (totalLatency < 0) totalLatency = 0;
Chris@366: 
Chris@366:     m_outputLatency = totalLatency + m_p.firstCentre * pow(2, m_octaves-1);
Chris@366: 
Chris@366: #ifdef DEBUG_CQ
Chris@366:     cerr << "totalLatency = " << totalLatency << ", m_outputLatency = " << m_outputLatency << endl;
Chris@366: #endif
Chris@366: 
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366: 
Chris@366: 	// Calculate the difference between the total latency applied
Chris@366: 	// across all octaves, and the existing latency due to the
Chris@366: 	// upsampler for this octave.
Chris@366: 
Chris@366:         int latencyPadding = totalLatency - latencies[i] + pushes[i];
Chris@366: 
Chris@366: #ifdef DEBUG_CQ
Chris@366:         cerr << "octave " << i << ": push " << pushes[i] << ", resampler latency inc overlap space " << latencies[i] << ", latencyPadding = " << latencyPadding << " (/factor = " << latencyPadding / pow(2, i) << ")" << endl;
Chris@366: #endif
Chris@366: 
Chris@366:         m_buffers.push_back(RealSequence(latencyPadding, 0.0));
Chris@366:     }
Chris@366: 
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366:         // Fixed-size buffer for IFFT overlap-add
Chris@366:         m_olaBufs.push_back(RealSequence(m_p.fftSize, 0.0));
Chris@366:     }
Chris@366: 
Chris@366:     m_fft = new FFTReal(m_p.fftSize);
Chris@366: }
Chris@366: 
Chris@366: CQInverse::RealSequence
Chris@366: CQInverse::process(const ComplexBlock &block)
Chris@366: {
Chris@366:     // The input data is of the form produced by ConstantQ::process --
Chris@366:     // an unknown number N of columns of varying height. We assert
Chris@366:     // that N is a multiple of atomsPerFrame * 2^(octaves-1), as must
Chris@366:     // be the case for data that came directly from our ConstantQ
Chris@366:     // implementation.
Chris@366: 
Chris@366:     int widthProvided = block.size();
Chris@366: 
Chris@366:     if (widthProvided == 0) {
Chris@366:         return drawFromBuffers();
Chris@366:     }
Chris@366: 
Chris@366:     int blockWidth = m_p.atomsPerFrame * int(pow(2, m_octaves - 1));
Chris@366: 
Chris@366:     if (widthProvided % blockWidth != 0) {
Chris@366:         cerr << "ERROR: CQInverse::process: Input block size ("
Chris@366:              << widthProvided
Chris@366:              << ") must be a multiple of processing block width "
Chris@366:              << "(atoms-per-frame * 2^(octaves-1) = "
Chris@366:              << m_p.atomsPerFrame << " * 2^(" << m_octaves << "-1) = "
Chris@366:              << blockWidth << ")" << endl;
Chris@366:         throw std::invalid_argument
Chris@366:             ("Input block size must be a multiple of processing block width");
Chris@366:     }
Chris@366: 
Chris@366:     // Procedure:
Chris@366:     // 
Chris@366:     // 1. Slice the list of columns into a set of lists of columns,
Chris@366:     // one per octave, each of width N / (2^octave-1) and height
Chris@366:     // binsPerOctave, containing the values present in that octave
Chris@366:     //
Chris@366:     // 2. Group each octave list by atomsPerFrame columns at a time,
Chris@366:     // and stack these so as to achieve a list, for each octave, of
Chris@366:     // taller columns of height binsPerOctave * atomsPerFrame
Chris@366:     //
Chris@366:     // 3. For each taller column, take the product with the inverse CQ
Chris@366:     // kernel (which is the conjugate of the forward kernel) and
Chris@366:     // perform an inverse FFT
Chris@366:     //
Chris@366:     // 4. Overlap-add each octave's resynthesised blocks (unwindowed)
Chris@366:     //
Chris@366:     // 5. Resample each octave's overlap-add stream to the original
Chris@366:     // rate
Chris@366:     //
Chris@366:     // 6. Sum the resampled streams and return
Chris@366:     
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366:         
Chris@366:         // Step 1
Chris@366: 
Chris@366:         ComplexBlock oct;
Chris@366: 
Chris@366:         for (int j = 0; j < widthProvided; ++j) {
Chris@366:             int h = block[j].size();
Chris@366:             if (h < m_binsPerOctave * (i+1)) {
Chris@366:                 continue;
Chris@366:             }
Chris@366:             ComplexColumn col(block[j].begin() + m_binsPerOctave * i,
Chris@366:                               block[j].begin() + m_binsPerOctave * (i+1));
Chris@366:             oct.push_back(col);
Chris@366:         }
Chris@366: 
Chris@366:         // Steps 2, 3, 4, 5
Chris@366:         processOctave(i, oct);
Chris@366:     }
Chris@366:     
Chris@366:     // Step 6
Chris@366:     return drawFromBuffers();
Chris@366: }
Chris@366: 
Chris@366: CQInverse::RealSequence
Chris@366: CQInverse::drawFromBuffers()
Chris@366: {
Chris@366:     // 6. Sum the resampled streams and return
Chris@366: 
Chris@366:     int available = 0;
Chris@366: 
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366:         if (i == 0 || int(m_buffers[i].size()) < available) {
Chris@366:             available = m_buffers[i].size();
Chris@366:         }
Chris@366:     }
Chris@366: 
Chris@366:     RealSequence result(available, 0);
Chris@366: 
Chris@366:     if (available == 0) {
Chris@366:         return result;
Chris@366:     }
Chris@366: 
Chris@366:     for (int i = 0; i < m_octaves; ++i) {
Chris@366:         for (int j = 0; j < available; ++j) {
Chris@366:             result[j] += m_buffers[i][j];
Chris@366:         }
Chris@366:         m_buffers[i] = RealSequence(m_buffers[i].begin() + available,
Chris@366:                                     m_buffers[i].end());
Chris@366:     }
Chris@366: 
Chris@366:     return result;
Chris@366: }
Chris@366: 
Chris@366: CQInverse::RealSequence
Chris@366: CQInverse::getRemainingOutput()
Chris@366: {
Chris@366:     for (int j = 0; j < m_octaves; ++j) {
Chris@366:         int factor = pow(2, j);
Chris@366:         int latency = (j > 0 ? m_upsamplers[j]->getLatency() : 0) / factor;
Chris@366:         for (int i = 0; i < (latency + m_p.fftSize) / m_p.fftHop; ++i) {
Chris@366:             overlapAddAndResample(j, RealSequence(m_olaBufs[j].size(), 0));
Chris@366:         }
Chris@366:     }
Chris@366: 
Chris@366:     return drawFromBuffers();
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: CQInverse::processOctave(int octave, const ComplexBlock &columns)
Chris@366: {
Chris@366:     // 2. Group each octave list by atomsPerFrame columns at a time,
Chris@366:     // and stack these so as to achieve a list, for each octave, of
Chris@366:     // taller columns of height binsPerOctave * atomsPerFrame
Chris@366: 
Chris@366:     int ncols = columns.size();
Chris@366: 
Chris@366:     if (ncols % m_p.atomsPerFrame != 0) {
Chris@366:         cerr << "ERROR: CQInverse::process: Number of columns ("
Chris@366:              << ncols
Chris@366:              << ") in octave " << octave
Chris@366:              << " must be a multiple of atoms-per-frame ("
Chris@366:              << m_p.atomsPerFrame << ")" << endl;
Chris@366:         throw std::invalid_argument
Chris@366:             ("Columns in octave must be a multiple of atoms per frame");
Chris@366:     }
Chris@366: 
Chris@366:     for (int i = 0; i < ncols; i += m_p.atomsPerFrame) {
Chris@366: 
Chris@366:         ComplexColumn tallcol;
Chris@366:         for (int b = 0; b < m_binsPerOctave; ++b) {
Chris@366:             for (int a = 0; a < m_p.atomsPerFrame; ++a) {
Chris@366:                 tallcol.push_back(columns[i + a][m_binsPerOctave - b - 1]);
Chris@366:             }
Chris@366:         }
Chris@366:         
Chris@366:         processOctaveColumn(octave, tallcol);
Chris@366:     }
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: CQInverse::processOctaveColumn(int octave, const ComplexColumn &column)
Chris@366: {
Chris@366:     // 3. For each taller column, take the product with the inverse CQ
Chris@366:     // kernel (which is the conjugate of the forward kernel) and
Chris@366:     // perform an inverse FFT
Chris@366: 
Chris@366:     if ((int)column.size() != m_p.atomsPerFrame * m_binsPerOctave) {
Chris@366:         cerr << "ERROR: CQInverse::processOctaveColumn: Height of column ("
Chris@366:              << column.size() << ") in octave " << octave
Chris@366:              << " must be atoms-per-frame * bins-per-octave ("
Chris@366:              << m_p.atomsPerFrame << " * " << m_binsPerOctave << " = "
Chris@366:              << m_p.atomsPerFrame * m_binsPerOctave << ")" << endl;
Chris@366:         throw std::invalid_argument
Chris@366:             ("Column height must match atoms-per-frame * bins-per-octave");
Chris@366:     }
Chris@366: 
Chris@366:     ComplexSequence transformed = m_kernel->processInverse(column);
Chris@366: 
Chris@366:     int halfLen = m_p.fftSize/2 + 1;
Chris@366: 
Chris@366:     RealSequence ri(halfLen, 0);
Chris@366:     RealSequence ii(halfLen, 0);
Chris@366: 
Chris@366:     for (int i = 0; i < halfLen; ++i) {
Chris@366:         ri[i] = transformed[i].real();
Chris@366:         ii[i] = transformed[i].imag();
Chris@366:     }
Chris@366: 
Chris@366:     RealSequence timeDomain(m_p.fftSize, 0);
Chris@366: 
Chris@366:     m_fft->inverse(ri.data(), ii.data(), timeDomain.data());
Chris@366: 
Chris@366:     overlapAddAndResample(octave, timeDomain);
Chris@366: }
Chris@366: 
Chris@366: void
Chris@366: CQInverse::overlapAddAndResample(int octave, const RealSequence &seq)
Chris@366: {
Chris@366:     // 4. Overlap-add each octave's resynthesised blocks (unwindowed)
Chris@366:     //
Chris@366:     // and
Chris@366:     //
Chris@366:     // 5. Resample each octave's overlap-add stream to the original
Chris@366:     // rate
Chris@366: 
Chris@366:     if (seq.size() != m_olaBufs[octave].size()) {
Chris@366:         cerr << "ERROR: CQInverse::overlapAdd: input sequence length ("
Chris@366:              << seq.size() << ") is expected to match OLA buffer size ("
Chris@366:              << m_olaBufs[octave].size() << ")" << endl;
Chris@366:         throw std::invalid_argument
Chris@366:             ("Input sequence length should match OLA buffer size");
Chris@366:     }
Chris@366: 
Chris@366:     RealSequence toResample(m_olaBufs[octave].begin(),
Chris@366:                             m_olaBufs[octave].begin() + m_p.fftHop);
Chris@366: 
Chris@366:     RealSequence resampled = 
Chris@366:         octave > 0 ?
Chris@366:         m_upsamplers[octave]->process(toResample.data(), toResample.size()) :
Chris@366:         toResample;
Chris@366: 
Chris@366:     m_buffers[octave].insert(m_buffers[octave].end(),
Chris@366:                              resampled.begin(),
Chris@366:                              resampled.end());
Chris@366:     
Chris@366:     m_olaBufs[octave] = RealSequence(m_olaBufs[octave].begin() + m_p.fftHop,
Chris@366:                                      m_olaBufs[octave].end());
Chris@366:     
Chris@366:     RealSequence pad(m_p.fftHop, 0);
Chris@366: 
Chris@366:     m_olaBufs[octave].insert(m_olaBufs[octave].end(),
Chris@366:                              pad.begin(),
Chris@366:                              pad.end());
Chris@366: 
Chris@366:     for (int i = 0; i < m_p.fftSize; ++i) {
Chris@366:         m_olaBufs[octave][i] += seq[i];
Chris@366:     }
Chris@366: }
Chris@366: