For a side project involving real-time audio processing I needed a FIFO or Circular Buffer to pass sample data from the microphone sampling thread to the processing thread. The sampling thread happens more often with smaller number of samples to put into the FIFO. The processing thread happens less frequently so requires a faster way to bulk read from the FIFO. The mirroring technique used in this FIFO reduces the bulk read operation to a single memcpy of contiguous memory without worrying about wrap around.

The concept was based on the techniques used in “virtual ring buffers” but without mapping virtual memory. For more information see: The Magic Ring Buffer and Circular (ring) buffer plus neat virtual memory mapping trick posts.

[code light=”true”]
$ ./test.exe
MirroredFifo example usage

Empty fifo: canReadCount=0 canWriteCount=10
One entry in fifo: writeCount=1 canReadCount=1 canWriteCount=9
Contents: [0]
Full fifo: writeCount=9 canReadCount=10 canWriteCount=0
Contents: [0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
One below full fifo: readCount=1 canReadCount=9 canWriteCount=1
Contents: [0, 1, 2, 3, 4, 5, 6, 7, 8]
Empty fifo: readCount=9 canReadCount=0 canWriteCount=10
Contents: []
Half Full fifo: writeCount=5 canReadCount=5 canWriteCount=5
Contents: [0, 1, 2, 3, 4]
Empty fifo: readCount=5 canReadCount=0 canWriteCount=10
Contents: []
Looped Full fifo: writeCount=10 canReadCount=10 canWriteCount=0
Contents: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Empty fifo: readCount=10 canReadCount=0 canWriteCount=10
Contents: []
Full fifo: writeCount=10 canReadCount=10 canWriteCount=0
Contents: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Cleared Empty fifo: canReadCount=0 canWriteCount=10
Contents: []
Half Full fifo: writeCount=5 canReadCount=5 canWriteCount=5
Contents: [0, 1, 2, 3, 4]
Full Overwritten fifo: writeCount=10 canReadCount=10 canWriteCount=0
Contents: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[/code]

Sourcecode follows:

[code language=”cpp” collapse=”true” title=”main.cpp”]
//——————————————————————————
// The MIT License (MIT)
//
// Copyright (c) 2015 Benjamin Sherlock
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//——————————————————————————
//
// main.cpp
//
//——————————————————————————
//
// This has been tested using cygwin and x86_64-w64-mingw32-g++.
//
// Compile: g++ main.cpp -o test.exe -lm -static
// Run: ./test.exe
//
//——————————————————————————

// Includes
#include <iostream>
#include "MirroredFifo.h"

//! Main Function
int main(int argc, char** argv)
{
std::cout << "MirroredFifo example usage" << std::endl << std::endl;

size_t fifoLength = 10;
size_t canReadCount = 0;
size_t canWriteCount = 0;
size_t readCount = 0;
size_t writeCount = 0;

std::vector<int> values(fifoLength);
std::vector<int> readValues(fifoLength, 0);
for( size_t i = 0; i < fifoLength; i++ )
{
values[i] = i;
}

// Create a MirroredFifo
MirroredFifo<int> intFifo(fifoLength);

// Fill and Read
canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Empty fifo: canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;

writeCount = intFifo.write(1, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "One entry in fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

writeCount = intFifo.write(fifoLength, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Full fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

readCount = intFifo.read(1, &readValues[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "One below full fifo: readCount=" << readCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

readCount = intFifo.read(fifoLength, &readValues[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Empty fifo: readCount=" << readCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

writeCount = intFifo.write(fifoLength/2, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Half Full fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

readCount = intFifo.read(fifoLength, &readValues[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Empty fifo: readCount=" << readCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

writeCount = intFifo.write(fifoLength, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Looped Full fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

readCount = intFifo.read(fifoLength, &readValues[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Empty fifo: readCount=" << readCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

writeCount = intFifo.write(fifoLength, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Full fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

intFifo.clear();

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Cleared Empty fifo: "
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

// Now try the overwriting version

writeCount = intFifo.write(fifoLength/2, &values[0]);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Half Full fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

// Now write over again
writeCount = intFifo.write(fifoLength, &values[0], true);

canReadCount = intFifo.canRead();
canWriteCount = intFifo.canWrite();

std::cout << "Full Overwritten fifo: writeCount=" << writeCount
<< " canReadCount=" << canReadCount
<< " canWriteCount=" << canWriteCount << std::endl;
std::cout << "Contents: ";
intFifo.debug_printContents();

return 0;
}
[/code]

[code language=”cpp” collapse=”true” title=”MirroredFifo.h”]
//——————————————————————————
// The MIT License (MIT)
//
// Copyright (c) 2015 Benjamin Sherlock
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//——————————————————————————
//
// MirroredFifo.h
//
//——————————————————————————
//
// https://en.wikipedia.org/wiki/Circular_buffer
// This FIFO uses the "Always keep one slot open" strategy for managing the
// full/empty buffer distinction.
//
// It uses a variation on the "virtual ring buffer" technique, though instead of
// mapped memory it is a direct copy in contiguous memory. This allows block reads
// from contiguous memory.
// http://atastypixel.com/blog/circular-ring-buffer-plus-neat-virtual-memory-mapping-trick/
// https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/
//
//——————————————————————————

#ifndef MIRROREDFIFO_H
#define MIRROREDFIFO_H

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

template <typename DataType>
class MirroredFifo
{
public:

//! Constructor
//! fifoLength = the maximum number of items to be stored
MirroredFifo(size_t fifoLength);

//! Destructor
virtual ~MirroredFifo();

//! Clear the fifo
void clear();

//! How many values we can read from the fifo.
size_t canRead();

//! How many values we can write to the fifo.
size_t canWrite();

//! Write data to fifo – array – returns number of items written
size_t write( size_t length, const DataType * const data, bool overwrite = false );

//! Write data to fifo – single item – returns number of items written
size_t writeOne( const DataType &data, bool overwrite = false );

//! Read data from the fifo – array – returns number of items read
size_t read( size_t length, DataType * data );

//! Debug: Print the contents to std::cout
void debug_printContents();

protected:

private:

//! Usable Fifo Length
size_t m_fifoLength;

//! Total Storage Length
size_t m_totalStorageLength;

//! Storage Vector
std::vector<DataType> m_storage;

//! Head Index (Read from the head)
volatile size_t m_headIndex;

//! Tail Index (Write to the tail)
volatile size_t m_tailIndex;

}; // class MirroredFifo

//! Constructor
template <typename DataType>
MirroredFifo<DataType>::MirroredFifo(size_t fifoLength)
: m_fifoLength(fifoLength+1), m_totalStorageLength(2*m_fifoLength),
m_storage(m_totalStorageLength), m_headIndex(0), m_tailIndex(0)
{
}

//! Destructor
template <typename DataType>
MirroredFifo<DataType>::~MirroredFifo()
{
}

//! Clear the fifo
template <typename DataType>
void MirroredFifo<DataType>::clear()
{
m_headIndex = 0;
m_tailIndex = 0;
}

//! How many values we can read from the fifo.
template <typename DataType>
size_t MirroredFifo<DataType>::canRead()
{
size_t canRead = 0;
if( m_headIndex == m_tailIndex ) {
canRead = 0;
} else if( m_tailIndex > m_headIndex ) {
canRead = m_tailIndex – m_headIndex;
} else {
canRead = (m_tailIndex + m_fifoLength – m_headIndex);
}
return canRead;
}

//! How many values we can write to the fifo.
template <typename DataType>
size_t MirroredFifo<DataType>::canWrite()
{
//size_t canRead = 0;
size_t canWrite = 0;
if( m_headIndex == m_tailIndex ) {
//canRead = 0;
canWrite = m_fifoLength – 1;
} else if( m_tailIndex > m_headIndex ) {
//canRead = m_tailIndex – m_headIndex;
//canWrite = m_fifoLength – canRead – 1;
canWrite = m_fifoLength – ( m_tailIndex – m_headIndex ) – 1;
} else {
//canRead = (m_tailIndex + m_fifoLength – m_headIndex);
//canWrite = m_fifoLength – canRead – 1;
canWrite = m_fifoLength – (m_tailIndex + m_fifoLength – m_headIndex) – 1;
}
return canWrite;
}

//! Write data to fifo – array
template <typename DataType>
size_t MirroredFifo<DataType>::write( size_t length, const DataType * const data, bool overwrite )
{
size_t canWriteCount = canWrite();

if( !overwrite && ( length > canWriteCount ) )
{
length = canWriteCount;
}

size_t i = 0;
// First part in the empty fifo slots
for( i = 0; i < length && i < canWriteCount; i++ )
{
// Write to the tail – and mirror
m_storage[m_tailIndex] = data[i];
m_storage[m_tailIndex+m_fifoLength] = data[i];

// Increment
m_tailIndex++;
if( m_tailIndex == m_fifoLength)
{
// Wrap around
m_tailIndex = 0;
}
}

// Now into the non-empty slots
for( i; i < length; i++)
{
// Write to the tail – and mirror
m_storage[m_tailIndex] = data[i];
m_storage[m_tailIndex+m_fifoLength] = data[i];

// Increment
m_tailIndex++;
if( m_tailIndex == m_fifoLength)
{
// Wrap around
m_tailIndex = 0;
}

// Also increment the head counter
m_headIndex++;
if( m_headIndex == m_fifoLength)
{
// Wrap around
m_headIndex = 0;
}
}

return length;
}

//! Write data to fifo – single item
template <typename DataType>
size_t MirroredFifo<DataType>::writeOne( const DataType &data, bool overwrite )
{
size_t canWriteCount = canWrite();

if( !overwrite && (canWriteCount == 0) )
{
return 0;
}

// Write to the tail – and mirror
m_storage[m_tailIndex] = data;
m_storage[m_tailIndex+m_fifoLength] = data;

// Increment
m_tailIndex++;
if( m_tailIndex == m_fifoLength)
{
// Wrap around
m_tailIndex = 0;
}

if( canWriteCount == 0 )
{
// Also increment the head counter
m_headIndex++;
if( m_headIndex == m_fifoLength)
{
// Wrap around
m_headIndex = 0;
}
}

return 1;
}

//! Read data from the fifo – array – returns number of items read
template <typename DataType>
size_t MirroredFifo<DataType>::read( size_t length, DataType * data )
{
size_t canReadCount = canRead();

if( canReadCount == 0 )
{
return 0;
}

if( length > canReadCount )
{
length = canReadCount;
}

// Copy from fifo to buffer
// Read from the head
memcpy( data, &m_storage[m_headIndex], length*sizeof(DataType) );

// Move the head index
m_headIndex += length;

if( m_headIndex >= m_fifoLength )
{
// Wrap around
m_headIndex -= m_fifoLength;
}

return length;
}

//! Debug: Print the contents to std::cout
template <typename DataType>
void MirroredFifo<DataType>::debug_printContents()
{
size_t canReadCount = canRead();

std::cout << "[";

for( size_t i = 0; i < canReadCount; i++ )
{
std::cout << m_storage[m_headIndex+i];

if( i < (canReadCount-1) )
{
std::cout << ", ";
}
}

std::cout << "]" << std::endl;
}

#endif // MIRROREDFIFO_H
[/code]