SlidingWindow.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreMinimal.h"
 
 
namespace Audio
{
    // Forward delcaration
    template <typename InSampleType>
    class TSlidingWindow;
 
 
    template <typename InSampleType>
    class TSlidingBuffer
    {
        public:
 
            TSlidingBuffer(const int32 InNumWindowSamples, const int32 InNumHopSamples)
            : NumWindowSamples(InNumWindowSamples)
            , NumHopSamples(InNumHopSamples)
            , NumUnderflowSamples(0)
            {
                check(NumWindowSamples >= 1);
                check(NumHopSamples >= 1);
            }
 
            TSlidingBuffer()
            : TSlidingBuffer(1, 1)
            {
            }
 
            TSlidingBuffer(const TSlidingBuffer&) = default;
            TSlidingBuffer(TSlidingBuffer&&) = default;
 
            TSlidingBuffer& operator=(const TSlidingBuffer& InOther) = default;
            TSlidingBuffer& operator=(TSlidingBuffer&& InOther) = default;
 
            int32 GetNumWindowSamples() const
            {
                return NumWindowSamples;
            }
 
            int32 GetNumHopSamples() const
            {
                return NumHopSamples;
            }
 
            int32 GetNumUnderflowSamples() const
            {
                return NumUnderflowSamples;
            }
 
            TArrayView<const InSampleType> GetStorage() const
            {
                return StorageBuffer;
            }
 
            void StoreForFutureWindows(TArrayView<const InSampleType> InBuffer)
            {
                if (NumUnderflowSamples > 0)
                {
                    // Consume some underflow samples from the storage buffer.
                    if (StorageBuffer.Num() > NumUnderflowSamples)
                    {
                        StorageBuffer.RemoveAt(0, NumUnderflowSamples);
                        NumUnderflowSamples = 0;
                    }
                    else
                    {
                        NumUnderflowSamples -= StorageBuffer.Num();
                        StorageBuffer.Reset();
                    }
                }
 
                // Total number of samples starting at beginning of first window generated from this buffer
                int32 NumSamples = InBuffer.Num() + StorageBuffer.Num() - NumUnderflowSamples;
 
                if (NumSamples < 0)
                {
                    // No windows generated, but some underflow samples accounted for
                    NumUnderflowSamples -= InBuffer.Num();
                }
                else if (NumSamples < NumWindowSamples)
                {
                    // No windows generated, but we should store data for future windows.
                    int32 NumToCopy = NumSamples - StorageBuffer.Num();
                    int32 InBufferIndex = InBuffer.Num() - NumToCopy;
                    StorageBuffer.Append(&InBuffer.GetData()[InBufferIndex], NumToCopy);
 
                    // All underflow samples accounted for.
                    NumUnderflowSamples = 0;
                }
                else
                {
                    // Calculate number of windows generated from samples in StorageBuffer and InBuffer.
                    int32 NumWindowsGenerated = (NumSamples - NumWindowSamples) / NumHopSamples + 1;
 
                    // Calculate number of samples to keep for future windows
                    int32 NumRemainingSamples = NumSamples - (NumWindowsGenerated * NumHopSamples);
 
                    if (NumRemainingSamples > InBuffer.Num())
                    {
                        // Need to keep some samples from storage buffer and from InBuffer
                        int32 NumToKeep = NumRemainingSamples - InBuffer.Num();
                        int32 NumToRemove = StorageBuffer.Num() - NumToKeep;
 
                        if (NumToRemove > 0)
                        {
                            // May need to remove soem from the storage buffer
                            StorageBuffer.RemoveAt(0, NumToRemove);
                        }
 
                        StorageBuffer.Append(InBuffer.GetData(), InBuffer.Num());
                    }
                    else if (NumRemainingSamples > 0)
                    {
                        // Only need to keep samples from InBuffer. Can discard samples in StorageBuffer
                        StorageBuffer.Reset(NumRemainingSamples);
                        StorageBuffer.AddUninitialized(NumRemainingSamples);
 
                        int32 NewBufferCopyIndex = InBuffer.Num() - NumRemainingSamples;
                        FMemory::Memcpy(StorageBuffer.GetData(), &InBuffer.GetData()[NewBufferCopyIndex], NumRemainingSamples * sizeof(InSampleType));
                    }
                    else
                    {
                        // This occurs when HopSize > WindowSize. We have hopped to the next window, but don't have enough samples
                        // to account for the hop. We track the number of underflow samples to make sure they are consumed before
                        // the next window starts.
                        NumUnderflowSamples = -NumRemainingSamples;
                        StorageBuffer.Reset(0);
                    }
                }
            }
 
            void Reset()
            {
                StorageBuffer.Reset();
                NumUnderflowSamples = 0;
            }
 
        private:
            // NumWindowSamples describes the number of samples in a window.
            int32 NumWindowSamples;
 
            // NumHopSamples describes the number of samples between adjacent windows.
            int32 NumHopSamples;
 
            // Stores samples from previous calls which are still needed for future buffers
            TArray<InSampleType> StorageBuffer;
 
            // When HopSize is greater than WindowSize a situation can occur where we need 
            // to account for hop samples that we have not yet ingested.  
            int32 NumUnderflowSamples;
    };
 
    template <typename InSampleType>
    class TSlidingWindow
    {
        friend class TSlidingWindowIterator;
 
        protected:
            // Accessed from friendship with TSlidingBuffer
            TArrayView<const InSampleType> StorageBuffer;
 
            // New buffer passed in.
            TArrayView<const InSampleType> NewBuffer;
 
            // Copied from TSlidingBuffer
            const int32 NumWindowSamples;
 
            // Copied from TSlidingBuffer
            const int32 NumHopSamples;
 
        private:
 
            int32 MaxReadIndex;
            int32 NumUnderflowSamples;
 
        public:
 
            template<typename InAllocator = FDefaultAllocator>
            class TSlidingWindowIterator
            {
                    const TSlidingWindow SlidingWindow;
 
                    // Samples in window will be copied into this array.
                    TArray<InSampleType, InAllocator>& WindowBuffer;
 
                    // Index into array for reading out data.
                    int32 ReadIndex;
 
                public:
 
                    // Sentinel value marking that the last possible window has been generated.
                    static const int32 ReadIndexEnd = INDEX_NONE;
 
                    TSlidingWindowIterator(const TSlidingWindow& InSlidingWindow, TArray<InSampleType, InAllocator>& OutWindowBuffer, int32 InReadIndex)
                    :   SlidingWindow(InSlidingWindow)
                    ,   WindowBuffer(OutWindowBuffer)
                    ,   ReadIndex(InReadIndex)
                    {
                        if (ReadIndex > SlidingWindow.MaxReadIndex)
                        {
                            ReadIndex = ReadIndexEnd;
                        }
                    }
 
                    TSlidingWindowIterator operator++()
                    {
                        if (ReadIndex != ReadIndexEnd)
                        {
                            ReadIndex += SlidingWindow.NumHopSamples;
                            if (ReadIndex > SlidingWindow.MaxReadIndex)
                            {
                                ReadIndex = ReadIndexEnd;
                            }
                        }
 
                        return *this;
                    }
 
                    bool operator!=(const TSlidingWindowIterator& Other) const
                    {
                        return ReadIndex != Other.ReadIndex;
                    }
 
                    TArray<InSampleType, InAllocator>& operator*()
                    {
                        if (ReadIndex != ReadIndexEnd)
                        {
                            // Resize output window
                            WindowBuffer.Reset(SlidingWindow.NumWindowSamples);
                            WindowBuffer.AddUninitialized(SlidingWindow.NumWindowSamples);
 
                            int32 SamplesFilled = 0;
 
                            if (ReadIndex < SlidingWindow.StorageBuffer.Num())
                            {
                                // The output window overlaps the storage buffer. Copy appropriate samples from the storage buffer.
                                int32 SamplesToCopy = SlidingWindow.StorageBuffer.Num() - ReadIndex;
                                FMemory::Memcpy(WindowBuffer.GetData(), &SlidingWindow.StorageBuffer.GetData()[ReadIndex], SamplesToCopy * sizeof(InSampleType));
                                SamplesFilled += SamplesToCopy;
                            }
 
                            if (SamplesFilled < SlidingWindow.NumWindowSamples)
                            {
                                // The output window overlaps the new buffer. Copy appropriate samples from the new buffer.
                                int32 NewBufferIndex = ReadIndex - SlidingWindow.StorageBuffer.Num() + SamplesFilled;
                                int32 NewBufferRemaining = SlidingWindow.NewBuffer.Num() - NewBufferIndex;
                                int32 SamplesToCopy = FMath::Min(SlidingWindow.NumWindowSamples - SamplesFilled, NewBufferRemaining);
                                
                                if (SamplesToCopy > 0)
                                {
                                    FMemory::Memcpy(&WindowBuffer.GetData()[SamplesFilled], &SlidingWindow.NewBuffer.GetData()[NewBufferIndex], SamplesToCopy * sizeof(InSampleType));
 
                                    SamplesFilled += SamplesToCopy;
                                }
                            }
 
                            if (SamplesFilled < SlidingWindow.NumWindowSamples)
                            {
                                // The output window still needs more samples (due to zeropadding & flushing), so set zeros.
                                int32 SamplesToZeropad = SlidingWindow.NumWindowSamples - SamplesFilled;
                                FMemory::Memset(&WindowBuffer.GetData()[SamplesFilled], 0, sizeof(InSampleType) * SamplesToZeropad);
                            }
                        }
                        else
                        {
                            // Empty window if past end sliding window. ReadIndex == ReadIndexEnd
                            WindowBuffer.Reset();
                        }
 
                        return WindowBuffer;
                    }
            };
 
            TSlidingWindow(const TSlidingBuffer<InSampleType>& InSlidingBuffer, TArrayView<const InSampleType> InNewBuffer, bool bDoFlush)
            :   StorageBuffer(InSlidingBuffer.GetStorage())
            ,   NewBuffer(InNewBuffer)
            ,   NumWindowSamples(InSlidingBuffer.GetNumWindowSamples())
            ,   NumHopSamples(InSlidingBuffer.GetNumHopSamples())
            ,   MaxReadIndex(0)
            ,   NumUnderflowSamples(InSlidingBuffer.GetNumUnderflowSamples())
            {
                // Total samples to be slid over.
                int32 NumSamples = NewBuffer.Num() + StorageBuffer.Num();
 
                if (bDoFlush && (NumSamples > 0))
                {
                    // If flushing, calculate the number of samples to zeropad
                    int32 NumZeroPad = 0;
 
                    if (NumSamples < NumWindowSamples)
                    {
                        NumZeroPad = NumWindowSamples - NumSamples;
                    }
                    else
                    {
                        // Determine number of windows 
                        int32 NumWindowsGenerated = (NumSamples - NumWindowSamples - NumUnderflowSamples) / NumHopSamples + 1;
                        int32 NumRemaining = NumSamples - (NumWindowsGenerated * NumHopSamples);
                        if (NumRemaining > 0)
                        {
                            NumZeroPad = NumWindowSamples - NumRemaining;
                        }
                    }
 
                    NumSamples += NumZeroPad;
                }
 
                MaxReadIndex = NumSamples - NumWindowSamples;
 
                if (MaxReadIndex < 0)
                {
                    MaxReadIndex = TSlidingWindowIterator<>::ReadIndexEnd;
                }
            }
 
            virtual ~TSlidingWindow()
            {
            }
 
            template<typename InAllocator = FDefaultAllocator>
            TSlidingWindowIterator<InAllocator> begin(TArray<InSampleType, InAllocator>& OutWindowBuffer) const
            {
                if (MaxReadIndex == TSlidingWindowIterator<>::ReadIndexEnd)
                {
                    return end<InAllocator>(OutWindowBuffer);
                }
                // Set the starting read index to NumUnderflowSamples to account for samples that still need to be consumed.
                return TSlidingWindowIterator<InAllocator>(*this, OutWindowBuffer, NumUnderflowSamples);
            }
 
            template<typename InAllocator = FDefaultAllocator>
            TSlidingWindowIterator<InAllocator> end(TArray<InSampleType, InAllocator>& OutWindowBuffer) const
            {
                return TSlidingWindowIterator<InAllocator>(*this, OutWindowBuffer, TSlidingWindowIterator<InAllocator>::ReadIndexEnd);
            }
    };
 
    template <class InSampleType>
    class TScopedSlidingWindow : public TSlidingWindow<InSampleType>
    {
            // Do not allow copying or moving since that may cause the destructor to be called inadvertently.
            TScopedSlidingWindow(TScopedSlidingWindow const &) = delete;
            void operator=(TScopedSlidingWindow const &) = delete;
            TScopedSlidingWindow(TScopedSlidingWindow&&) = delete;
            TScopedSlidingWindow& operator=(TScopedSlidingWindow&&) = delete;
 
            TSlidingBuffer<InSampleType>& SlidingBuffer;
        public:
 
            TScopedSlidingWindow(TSlidingBuffer<InSampleType>& InSlidingBuffer, TArrayView<const InSampleType> InNewBuffer, bool bDoFlush = false)
            :   TSlidingWindow<InSampleType>(InSlidingBuffer, InNewBuffer, bDoFlush)
            ,   SlidingBuffer(InSlidingBuffer)
            {}
 
            virtual ~TScopedSlidingWindow()
            {
                SlidingBuffer.StoreForFutureWindows(TSlidingWindow<InSampleType>::NewBuffer);
            }
    };
 
    template <typename InSampleType, typename InAllocator = FDefaultAllocator>
    class TAutoSlidingWindow : public TScopedSlidingWindow<InSampleType>
    {
        TArray<InSampleType, InAllocator>& WindowBuffer;
 
        typedef typename TSlidingWindow<InSampleType>::template TSlidingWindowIterator<InAllocator> TAutoSlidingWindowIterator;
 
        public:
            TAutoSlidingWindow(TSlidingBuffer<InSampleType>& InBuffer, TArrayView<const InSampleType> InNewBuffer, TArray<InSampleType, InAllocator>& OutWindow, bool bDoFlush = false)
            :   TScopedSlidingWindow<InSampleType>(InBuffer, InNewBuffer, bDoFlush)
            ,   WindowBuffer(OutWindow)
            {}
 
            TAutoSlidingWindowIterator begin() 
            {
                return TSlidingWindow<InSampleType>::template begin<InAllocator>(WindowBuffer);
            }
 
            TAutoSlidingWindowIterator end()
            {
                return TSlidingWindow<InSampleType>::template end<InAllocator>(WindowBuffer);
            }
    };
}