changeset 1297:5cc969b236b0 3.0-integration

Merge

--- a/data/fileio/CodedAudioFileReader.cpp	Fri Nov 25 11:33:34 2016 +0000
+++ b/data/fileio/CodedAudioFileReader.cpp	Fri Nov 25 11:37:06 2016 +0000
@@ -47,7 +47,10 @@
     m_fileFrameCount(0),
     m_normalised(normalised),
     m_max(0.f),
-    m_gain(1.f)
+    m_gain(1.f),
+    m_clippedCount(0),
+    m_firstNonzero(0),
+    m_lastNonzero(0)
 {
     SVDEBUG << "CodedAudioFileReader:: cache mode: " << cacheMode
             << " (" << (cacheMode == CacheInTemporaryFile
@@ -334,6 +337,20 @@
             (StorageAdviser::MemoryAllocation,
              (m_data.size() * sizeof(float)) / 1024);
     }
+
+    SVDEBUG << "CodedAudioFileReader: File decodes to " << m_fileFrameCount
+            << " frames" << endl;
+    if (m_fileFrameCount != m_frameCount) {
+        SVDEBUG << "CodedAudioFileReader: Resampled to " << m_frameCount
+                << " frames" << endl;
+    }
+    SVDEBUG << "CodedAudioFileReader: Signal abs max is " << m_max
+            << ", " << m_clippedCount
+            << " samples clipped, first non-zero frame is at "
+            << m_firstNonzero << ", last at " << m_lastNonzero << endl;
+    if (m_normalised) {
+        SVDEBUG << "CodedAudioFileReader: Normalising, gain is " << m_gain << endl;
+    }
 }
 
 void
@@ -359,24 +376,36 @@
     float clip = 1.0;
     sv_frame_t count = sz * m_channelCount;
 
-    if (m_normalised) {
-        for (sv_frame_t i = 0; i < count; ++i) {
-            float v = fabsf(buffer[i]);
-            if (v > m_max) {
-                m_max = v;
-                m_gain = 1.f / m_max;
+    for (sv_frame_t j = 0; j < sz; ++j) {
+        for (int c = 0; c < m_channelCount; ++c) {
+            sv_frame_t i = j * m_channelCount + c;
+            float v = buffer[i];
+            if (!m_normalised) {
+                if (v > clip) {
+                    buffer[i] = clip;
+                    ++m_clippedCount;
+                } else if (v < -clip) {
+                    buffer[i] = -clip;
+                    ++m_clippedCount;
+                }
+            }
+            v = fabsf(v);
+            if (v != 0.f) {
+                if (m_firstNonzero == 0) {
+                    m_firstNonzero = m_frameCount;
+                }
+                m_lastNonzero = m_frameCount;
+                if (v > m_max) {
+                    m_max = v;
+                }
             }
         }
-    } else {
-        for (sv_frame_t i = 0; i < count; ++i) {
-            if (buffer[i] >  clip) buffer[i] =  clip;
-        }
-        for (sv_frame_t i = 0; i < count; ++i) {
-            if (buffer[i] < -clip) buffer[i] = -clip;
-        }
+        ++m_frameCount;
     }
 
-    m_frameCount += sz;
+    if (m_max > 0.f) {
+        m_gain = 1.f / m_max; // used when normalising only
+    }
 
     switch (m_cacheMode) {
 
@@ -390,6 +419,16 @@
 
     case CacheInMemory:
         m_dataLock.lock();
+        /*
+        if (m_data.size() < 5120) {
+            for (int i = 0; i < count && i < 5120; ++i) {
+                if (i % 8 == 0) cerr << i << ": ";
+                cerr << buffer[i] << " ";
+                if (i % 8 == 7) cerr << endl;
+            }
+        }
+        cerr << endl;
+        */
         m_data.insert(m_data.end(), buffer, buffer + count);
         m_dataLock.unlock();
         break;

--- a/data/fileio/CodedAudioFileReader.h	Fri Nov 25 11:33:34 2016 +0000
+++ b/data/fileio/CodedAudioFileReader.h	Fri Nov 25 11:37:06 2016 +0000
@@ -103,6 +103,10 @@
     bool m_normalised;
     float m_max;
     float m_gain;
+
+    sv_frame_t m_clippedCount;
+    sv_frame_t m_firstNonzero;
+    sv_frame_t m_lastNonzero;
 };
 
 #endif

--- a/data/fileio/MP3FileReader.cpp	Fri Nov 25 11:33:34 2016 +0000
+++ b/data/fileio/MP3FileReader.cpp	Fri Nov 25 11:37:06 2016 +0000
@@ -32,8 +32,6 @@
 #include <id3tag.h>
 #endif
 
-//#define DEBUG_ID3TAG 1
-
 #include <QFileInfo>
 
 #ifdef _MSC_VER
@@ -48,6 +46,7 @@
     CodedAudioFileReader(mode, targetRate, normalised),
     m_source(source),
     m_path(source.getLocalFilename()),
+    m_decodeErrorShown(false),
     m_decodeThread(0)
 {
     SVDEBUG << "MP3FileReader: local path: \"" << m_path
@@ -61,6 +60,7 @@
     m_bitrateNum = 0;
     m_bitrateDenom = 0;
     m_cancelled = false;
+    m_mp3FrameCount = 0;
     m_completion = 0;
     m_done = false;
     m_reporter = reporter;
@@ -73,9 +73,11 @@
 
     m_fileSize = stat.st_size;
 
-    m_filebuffer = 0;
-    m_samplebuffer = 0;
-    m_samplebuffersize = 0;
+    m_fileBuffer = 0;
+    m_fileBufferSize = 0;
+
+    m_sampleBuffer = 0;
+    m_sampleBufferSize = 0;
 
     int fd = -1;
     if ((fd = ::open(m_path.toLocal8Bit().data(), O_RDONLY
@@ -88,7 +90,12 @@
     }	
 
     try {
-        m_filebuffer = new unsigned char[m_fileSize];
+        // We need a mysterious MAD_BUFFER_GUARD (== 8) zero bytes at
+        // end of input, to ensure libmad decodes the last frame
+        // correctly. Otherwise the decoded audio is truncated.
+        m_fileBufferSize = m_fileSize + MAD_BUFFER_GUARD;
+        m_fileBuffer = new unsigned char[m_fileBufferSize];
+        memset(m_fileBuffer + m_fileSize, 0, MAD_BUFFER_GUARD);
     } catch (...) {
         m_error = QString("Out of memory");
         ::close(fd);
@@ -98,17 +105,19 @@
     ssize_t sz = 0;
     ssize_t offset = 0;
     while (offset < m_fileSize) {
-        sz = ::read(fd, m_filebuffer + offset, m_fileSize - offset);
+        sz = ::read(fd, m_fileBuffer + offset, m_fileSize - offset);
         if (sz < 0) {
             m_error = QString("Read error for file %1 (after %2 bytes)")
                 .arg(m_path).arg(offset);
-            delete[] m_filebuffer;
+            delete[] m_fileBuffer;
             ::close(fd);
             return;
         } else if (sz == 0) {
-            cerr << QString("MP3FileReader::MP3FileReader: Warning: reached EOF after only %1 of %2 bytes")
+            SVCERR << QString("MP3FileReader::MP3FileReader: Warning: reached EOF after only %1 of %2 bytes")
                 .arg(offset).arg(m_fileSize) << endl;
             m_fileSize = offset;
+            m_fileBufferSize = m_fileSize + MAD_BUFFER_GUARD;
+            memset(m_fileBuffer + m_fileSize, 0, MAD_BUFFER_GUARD);
             break;
         }
         offset += sz;
@@ -126,12 +135,12 @@
                 (tr("Decoding %1...").arg(QFileInfo(m_path).fileName()));
         }
 
-        if (!decode(m_filebuffer, m_fileSize)) {
+        if (!decode(m_fileBuffer, m_fileBufferSize)) {
             m_error = QString("Failed to decode file %1.").arg(m_path);
         }
         
-        delete[] m_filebuffer;
-        m_filebuffer = 0;
+        delete[] m_fileBuffer;
+        m_fileBuffer = 0;
 
         if (isDecodeCacheInitialised()) finishDecodeCache();
         endSerialised();
@@ -148,7 +157,7 @@
             usleep(10);
         }
         
-        SVDEBUG << "MP3FileReader ctor: exiting with file rate = " << m_fileRate << endl;
+        SVDEBUG << "MP3FileReader: decoding startup complete, file rate = " << m_fileRate << endl;
     }
 
     if (m_error != "") {
@@ -194,22 +203,25 @@
 
     m_title = loadTag(tag, "TIT2"); // work title
     if (m_title == "") m_title = loadTag(tag, "TIT1");
+    if (m_title == "") SVDEBUG << "MP3FileReader::loadTags: No title found" << endl;
 
     m_maker = loadTag(tag, "TPE1"); // "lead artist"
     if (m_maker == "") m_maker = loadTag(tag, "TPE2");
+    if (m_maker == "") SVDEBUG << "MP3FileReader::loadTags: No artist/maker found" << endl;
 
     for (unsigned int i = 0; i < tag->nframes; ++i) {
         if (tag->frames[i]) {
             QString value = loadTag(tag, tag->frames[i]->id);
-            if (value != "") m_tags[tag->frames[i]->id] = value;
+            if (value != "") {
+                m_tags[tag->frames[i]->id] = value;
+            }
         }
     }
 
     id3_file_close(file);
 
 #else
-    SVDEBUG << "MP3FileReader::loadTags: ID3 tag support not compiled in"
-            << endl;
+    SVDEBUG << "MP3FileReader::loadTags: ID3 tag support not compiled in" << endl;
 #endif
 }
 
@@ -221,47 +233,38 @@
 
     id3_frame *frame = id3_tag_findframe(tag, name, 0);
     if (!frame) {
-#ifdef DEBUG_ID3TAG
-        cerr << "MP3FileReader::loadTags: No \"" << name << "\" in ID3 tag" << endl;
-#endif
+        SVDEBUG << "MP3FileReader::loadTag: No \"" << name << "\" frame found in ID3 tag" << endl;
         return "";
     }
         
     if (frame->nfields < 2) {
-        cerr << "MP3FileReader::loadTags: WARNING: Not enough fields (" << frame->nfields << ") for \"" << name << "\" in ID3 tag" << endl;
+        cerr << "MP3FileReader::loadTag: WARNING: Not enough fields (" << frame->nfields << ") for \"" << name << "\" in ID3 tag" << endl;
         return "";
     }
 
     unsigned int nstrings = id3_field_getnstrings(&frame->fields[1]);
     if (nstrings == 0) {
-#ifdef DEBUG_ID3TAG
-        cerr << "MP3FileReader::loadTags: No strings for \"" << name << "\" in ID3 tag" << endl;
-#endif
+        SVDEBUG << "MP3FileReader::loadTag: No strings for \"" << name << "\" in ID3 tag" << endl;
         return "";
     }
 
     id3_ucs4_t const *ustr = id3_field_getstrings(&frame->fields[1], 0);
     if (!ustr) {
-#ifdef DEBUG_ID3TAG
-        cerr << "MP3FileReader::loadTags: Invalid or absent data for \"" << name << "\" in ID3 tag" << endl;
-#endif
+        SVDEBUG << "MP3FileReader::loadTag: Invalid or absent data for \"" << name << "\" in ID3 tag" << endl;
         return "";
     }
         
     id3_utf8_t *u8str = id3_ucs4_utf8duplicate(ustr);
     if (!u8str) {
-        cerr << "MP3FileReader::loadTags: ERROR: Internal error: Failed to convert UCS4 to UTF8 in ID3 title" << endl;
+        SVDEBUG << "MP3FileReader::loadTag: ERROR: Internal error: Failed to convert UCS4 to UTF8 in ID3 tag" << endl;
         return "";
     }
         
     QString rv = QString::fromUtf8((const char *)u8str);
     free(u8str);
 
-#ifdef DEBUG_ID3TAG
-	cerr << "MP3FileReader::loadTags: tag \"" << name << "\" -> \""
-	<< rv << "\"" << endl;
-#endif
-
+    SVDEBUG << "MP3FileReader::loadTag: Tag \"" << name << "\" -> \""
+            << rv << "\"" << endl;
 
     return rv;
 
@@ -273,19 +276,19 @@
 void
 MP3FileReader::DecodeThread::run()
 {
-    if (!m_reader->decode(m_reader->m_filebuffer, m_reader->m_fileSize)) {
+    if (!m_reader->decode(m_reader->m_fileBuffer, m_reader->m_fileBufferSize)) {
         m_reader->m_error = QString("Failed to decode file %1.").arg(m_reader->m_path);
     }
 
-    delete[] m_reader->m_filebuffer;
-    m_reader->m_filebuffer = 0;
+    delete[] m_reader->m_fileBuffer;
+    m_reader->m_fileBuffer = 0;
 
-    if (m_reader->m_samplebuffer) {
+    if (m_reader->m_sampleBuffer) {
         for (int c = 0; c < m_reader->m_channelCount; ++c) {
-            delete[] m_reader->m_samplebuffer[c];
+            delete[] m_reader->m_sampleBuffer[c];
         }
-        delete[] m_reader->m_samplebuffer;
-        m_reader->m_samplebuffer = 0;
+        delete[] m_reader->m_sampleBuffer;
+        m_reader->m_sampleBuffer = 0;
     }
 
     if (m_reader->isDecodeCacheInitialised()) m_reader->finishDecodeCache();
@@ -303,35 +306,47 @@
     struct mad_decoder decoder;
 
     data.start = (unsigned char const *)mm;
-    data.length = (unsigned long)sz;
+    data.length = sz;
     data.reader = this;
 
-    mad_decoder_init(&decoder, &data, input, 0, 0, output, error, 0);
+    mad_decoder_init(&decoder,          // decoder to initialise
+                     &data,             // our own data block for callbacks
+                     input_callback,    // provides (entire) input to mad
+                     0,                 // checks header
+                     filter_callback,   // filters frame before decoding
+                     output_callback,   // receives decoded output
+                     error_callback,    // handles decode errors
+                     0);                // "message_func"
+
     mad_decoder_run(&decoder, MAD_DECODER_MODE_SYNC);
     mad_decoder_finish(&decoder);
 
+    SVDEBUG << "MP3FileReader: Decoding complete, decoded " << m_mp3FrameCount
+            << " mp3 frames" << endl;
+    
     m_done = true;
     return true;
 }
 
 enum mad_flow
-MP3FileReader::input(void *dp, struct mad_stream *stream)
+MP3FileReader::input_callback(void *dp, struct mad_stream *stream)
 {
     DecoderData *data = (DecoderData *)dp;
 
     if (!data->length) return MAD_FLOW_STOP;
 
     unsigned char const *start = data->start;
-    unsigned long length = data->length;
+    sv_frame_t length = data->length;
 
 #ifdef HAVE_ID3TAG
-    if (length > ID3_TAG_QUERYSIZE) {
+    while (length > ID3_TAG_QUERYSIZE) {
         ssize_t taglen = id3_tag_query(start, ID3_TAG_QUERYSIZE);
-        if (taglen > 0) {
-//            cerr << "ID3 tag length to skip: " << taglen << endl;
-            start += taglen;
-            length -= taglen;
+        if (taglen <= 0) {
+            break;
         }
+        SVDEBUG << "MP3FileReader: ID3 tag length to skip: " << taglen << endl;
+        start += taglen;
+        length -= taglen;
     }
 #endif
 
@@ -342,9 +357,41 @@
 }
 
 enum mad_flow
-MP3FileReader::output(void *dp,
-		      struct mad_header const *header,
-		      struct mad_pcm *pcm)
+MP3FileReader::filter_callback(void *dp,
+                               struct mad_stream const *stream,
+                               struct mad_frame *frame)
+{
+    DecoderData *data = (DecoderData *)dp;
+    return data->reader->filter(stream, frame);
+}
+
+enum mad_flow
+MP3FileReader::filter(struct mad_stream const *stream,
+                      struct mad_frame *)
+{
+    if (m_mp3FrameCount > 0) {
+        return MAD_FLOW_CONTINUE;
+    } else {
+        struct mad_bitptr ptr = stream->anc_ptr;
+        unsigned long fourcc = mad_bit_read(&ptr, 32);
+        std::string magic("....");
+        for (int i = 0; i < 4; ++i) {
+            magic[3-i] = char((fourcc >> (8*i)) & 0xff);
+        }
+        if (magic == "Xing" || magic == "Info" || magic == "LAME") {
+            SVDEBUG << "MP3FileReader: Discarding metadata frame (magic = \""
+                    << magic << "\")" << endl;
+            return MAD_FLOW_IGNORE;
+        } else {
+            return MAD_FLOW_CONTINUE;
+        }
+    }
+}
+
+enum mad_flow
+MP3FileReader::output_callback(void *dp,
+                               struct mad_header const *header,
+                               struct mad_pcm *pcm)
 {
     DecoderData *data = (DecoderData *)dp;
     return data->reader->accept(header, pcm);
@@ -356,7 +403,7 @@
 {
     int channels = pcm->channels;
     int frames = pcm->length;
-
+    
     if (header) {
         m_bitrateNum = m_bitrateNum + double(header->bitrate);
         m_bitrateDenom ++;
@@ -392,24 +439,27 @@
         }
     }
 
-    if (m_cancelled) return MAD_FLOW_STOP;
+    if (m_cancelled) {
+        SVDEBUG << "MP3FileReader: Decoding cancelled" << endl;
+        return MAD_FLOW_STOP;
+    }
 
     if (!isDecodeCacheInitialised()) {
         initialiseDecodeCache();
     }
 
-    if (int(m_samplebuffersize) < frames) {
-        if (!m_samplebuffer) {
-            m_samplebuffer = new float *[channels];
+    if (m_sampleBufferSize < size_t(frames)) {
+        if (!m_sampleBuffer) {
+            m_sampleBuffer = new float *[channels];
             for (int c = 0; c < channels; ++c) {
-                m_samplebuffer[c] = 0;
+                m_sampleBuffer[c] = 0;
             }
         }
         for (int c = 0; c < channels; ++c) {
-            delete[] m_samplebuffer[c];
-            m_samplebuffer[c] = new float[frames];
+            delete[] m_sampleBuffer[c];
+            m_sampleBuffer[c] = new float[frames];
         }
-        m_samplebuffersize = frames;
+        m_sampleBufferSize = frames;
     }
 
     int activeChannels = int(sizeof(pcm->samples) / sizeof(pcm->samples[0]));
@@ -424,29 +474,39 @@
 	    }
 	    float fsample = float(sample) / float(MAD_F_ONE);
             
-            m_samplebuffer[ch][i] = fsample;
+            m_sampleBuffer[ch][i] = fsample;
 	}
     }
 
-    addSamplesToDecodeCache(m_samplebuffer, frames);
+    addSamplesToDecodeCache(m_sampleBuffer, frames);
+
+    ++m_mp3FrameCount;
 
     return MAD_FLOW_CONTINUE;
 }
 
 enum mad_flow
-MP3FileReader::error(void *dp,
-		     struct mad_stream *stream,
-		     struct mad_frame *)
+MP3FileReader::error_callback(void *dp,
+                              struct mad_stream *stream,
+                              struct mad_frame *)
 {
-    static bool errorShown = false;
+    DecoderData *data = (DecoderData *)dp;
+
+    if (stream->error == MAD_ERROR_LOSTSYNC &&
+        data->length == 0) {
+        // We are at end of file, losing sync is expected behaviour
+        return MAD_FLOW_CONTINUE;
+    }
     
-    if (!errorShown) {
-        DecoderData *data = (DecoderData *)dp;
-        fprintf(stderr, "Warning: MP3 decoding error 0x%04x (%s) at byte offset %lu\n",
-                stream->error, mad_stream_errorstr(stream),
-                (unsigned long)(stream->this_frame - data->start));
-        fprintf(stderr, "(Suppressing any further errors of this sort)\n");
-        errorShown = true;
+    if (!data->reader->m_decodeErrorShown) {
+        char buffer[256];
+        snprintf(buffer, 255,
+                 "MP3 decoding error 0x%04x (%s) at byte offset %lu",
+                 stream->error, mad_stream_errorstr(stream),
+                 (unsigned long)(stream->this_frame - data->start));
+        SVCERR << "Warning: in file \"" << data->reader->m_path << "\": "
+               << buffer << " (continuing; will not report any further decode errors for this file)" << endl;
+        data->reader->m_decodeErrorShown = true;
     }
 
     return MAD_FLOW_CONTINUE;

--- a/data/fileio/MP3FileReader.h	Fri Nov 25 11:33:34 2016 +0000
+++ b/data/fileio/MP3FileReader.h	Fri Nov 25 11:37:06 2016 +0000
@@ -71,29 +71,38 @@
     sv_frame_t m_fileSize;
     double m_bitrateNum;
     int m_bitrateDenom;
+    int m_mp3FrameCount;
     int m_completion;
     bool m_done;
 
-    unsigned char *m_filebuffer;
-    float **m_samplebuffer;
-    int m_samplebuffersize;
+    unsigned char *m_fileBuffer;
+    size_t m_fileBufferSize;
+    
+    float **m_sampleBuffer;
+    size_t m_sampleBufferSize;
 
     ProgressReporter *m_reporter;
     bool m_cancelled;
 
-    struct DecoderData
-    {
+    bool m_decodeErrorShown;
+
+    struct DecoderData {
 	unsigned char const *start;
-	unsigned long length;
+	sv_frame_t length;
 	MP3FileReader *reader;
     };
 
     bool decode(void *mm, sv_frame_t sz);
+    enum mad_flow filter(struct mad_stream const *, struct mad_frame *);
     enum mad_flow accept(struct mad_header const *, struct mad_pcm *);
 
-    static enum mad_flow input(void *, struct mad_stream *);
-    static enum mad_flow output(void *, struct mad_header const *, struct mad_pcm *);
-    static enum mad_flow error(void *, struct mad_stream *, struct mad_frame *);
+    static enum mad_flow input_callback(void *, struct mad_stream *);
+    static enum mad_flow output_callback(void *, struct mad_header const *,
+                                         struct mad_pcm *);
+    static enum mad_flow filter_callback(void *, struct mad_stream const *,
+                                         struct mad_frame *);
+    static enum mad_flow error_callback(void *, struct mad_stream *,
+                                        struct mad_frame *);
 
     class DecodeThread : public Thread
     {

--- a/data/model/Labeller.h	Fri Nov 25 11:33:34 2016 +0000
+++ b/data/model/Labeller.h	Fri Nov 25 11:37:06 2016 +0000
@@ -171,37 +171,35 @@
         }
     }
         
+    /**
+     * Relabel all points in the given model that lie within the given
+     * multi-selection, according to the labelling properties of this
+     * labeller.  Return a command that has been executed but not yet
+     * added to the history.
+     */
     template <typename PointType>
-    void labelAll(SparseModel<PointType> &model, MultiSelection *ms) {
+    Command *labelAll(SparseModel<PointType> &model, MultiSelection *ms) {
 
-        typename SparseModel<PointType>::PointList::iterator i;
-        typename SparseModel<PointType>::PointList pl(model.getPoints());
-
-        typename SparseModel<PointType>::EditCommand *command =
-            new typename SparseModel<PointType>::EditCommand
+        auto points(model.getPoints());
+        auto command = new typename SparseModel<PointType>::EditCommand
             (&model, tr("Label Points"));
 
         PointType prevPoint(0);
+        bool havePrevPoint(false);
 
-        for (i = pl.begin(); i != pl.end(); ++i) {
+        for (auto p: points) {
 
-            bool inRange = true;
             if (ms) {
-                Selection s(ms->getContainingSelection(i->frame, false));
-                if (s.isEmpty() || !s.contains(i->frame)) {
-                    inRange = false;
+                Selection s(ms->getContainingSelection(p.frame, false));
+                if (!s.contains(p.frame)) {
+                    prevPoint = p;
+                    havePrevPoint = true;
+                    continue;
                 }
             }
 
-            PointType p(*i);
-
-            if (!inRange) {
-                prevPoint = p;
-                continue;
-            }
-
             if (actingOnPrevPoint()) {
-                if (i != pl.begin()) {
+                if (havePrevPoint) {
                     command->deletePoint(prevPoint);
                     label<PointType>(p, &prevPoint);
                     command->addPoint(prevPoint);
@@ -213,9 +211,94 @@
             }
 
             prevPoint = p;
+            havePrevPoint = true;
         }
 
-        command->finish();
+        return command->finish();
+    }
+
+    /**
+     * For each point in the given model (except the last), if that
+     * point lies within the given multi-selection, add n-1 new points
+     * at equally spaced intervals between it and the following point.
+     * Return a command that has been executed but not yet added to
+     * the history.
+     */
+    template <typename PointType>
+    Command *subdivide(SparseModel<PointType> &model, MultiSelection *ms, int n) {
+        
+        auto points(model.getPoints());
+        auto command = new typename SparseModel<PointType>::EditCommand
+            (&model, tr("Subdivide Points"));
+
+        for (auto i = points.begin(); i != points.end(); ++i) {
+
+            auto j = i;
+            // require a "next point" even if it's not in selection
+            if (++j == points.end()) {
+                break;
+            }
+
+            if (ms) {
+                Selection s(ms->getContainingSelection(i->frame, false));
+                if (!s.contains(i->frame)) {
+                    continue;
+                }
+            }
+
+            PointType p(*i);
+            PointType nextP(*j);
+
+            // n is the number of subdivisions, so we add n-1 new
+            // points equally spaced between p and nextP
+
+            for (int m = 1; m < n; ++m) {
+                sv_frame_t f = p.frame + (m * (nextP.frame - p.frame)) / n;
+                PointType newPoint(p);
+                newPoint.frame = f;
+                newPoint.label = tr("%1.%2").arg(p.label).arg(m+1);
+                command->addPoint(newPoint);
+            }
+        }
+
+        return command->finish();
+    }
+
+    /**
+     * Return a command that has been executed but not yet added to
+     * the history.
+     */
+    template <typename PointType>
+    Command *winnow(SparseModel<PointType> &model, MultiSelection *ms, int n) {
+        
+        auto points(model.getPoints());
+        auto command = new typename SparseModel<PointType>::EditCommand
+            (&model, tr("Winnow Points"));
+
+        int counter = 0;
+        
+        for (auto p: points) {
+
+            if (ms) {
+                Selection s(ms->getContainingSelection(p.frame, false));
+                if (!s.contains(p.frame)) {
+                    counter = 0;
+                    continue;
+                }
+            }
+
+            ++counter;
+
+            if (counter == n+1) counter = 1;
+            if (counter == 1) {
+                // this is an Nth instant, don't remove it
+                continue;
+            }
+            
+            command->deletePoint(p);
+        }
+
+        return command->finish();
     }
 
     template <typename PointType>