En esta entrada vamos a implementar un buffer circular en Arduino. ¿Qué es y para qué sirve un buffer circular?
Imaginemos que vamos a recibir una serie de valores pero, normalmente para ahorrar memoria, no queremos almacenar todos ellos. Únicamente tenemos interés en almacenar los últimos N valores recibidos, manteniendo el orden de recepción.
La primera alternativa que se nos puede ocurrir es emplear un array de dimensión N, almacenar cada valor recibido en la posición 0, y desplazar el resto de valores a la derecha para alojar nuevo valor.
Este primer método es ineficiente porque requiere que desplacemos N-1 valores (cuando está lleno) cada vez que recibimos un nuevo valor, por lo que obtenemos un algoritmo de O(n).
Por si os lo preguntáis, la cosa no mejora guardando en la última posición. En el momento que nuestro buffer se llene, igualmente tendremos que ser desplazar N-1 valores e nuevamente tenemos un algoritmo de O(n).
Un buffer circular (o buffer en anillo) es una alternativa para conseguir un orden O(1) en esta situación. Nuevamente empleamos un array de longitud N pero, en lugar de desplazar los valores almacenados, variamos la posición en la que insertamos el elemento
Para ello únicamente tenemos que almacenar y gestionar el índice de la posición actual. También tendremos que lidiar con los límites del array en las operaciones de lectura y escritura, por ejemplo, reiniciando el índice del buffer a 0 cuando sobrepasemos el límite superior del array.
La lectura de los M últimos valores de un buffer circular es ineficiente porque los valores no están en posiciones consecutivas en la memoria, por lo que no podemos copiarlo directamente.
Si esta pérdida de eficiencia es un problema y la memoria no es un factor crítico, podríamos emplear un buffer de longitud 2N. Grabando simultáneamente los valores en I e I+N, los M últimos valores siempre están almacenados entre I-M e I+N-M.
Los buffer circulares son frecuentes en sistemas de comunicación, almacenado de órdenes en un sistema y filtrado de sensores. En una próxima entrada veremos cómo usar un buffer circular para calcular rápidamente un filtro de media.
Buffer circular simple con índice
Aquí tenemos una implementación muy reducida de un buffer circular. Empleamos la variable ‘circularBufferIndex’ para almacenar la posición actual, y al añadir al buffer tratamos con los límites del Array.
const int circularBufferLength = 10;
int circularBuffer[circularBufferLength];
int circularBufferIndex = 0;
void appendToBuffer(int value)
{
circularBuffer[circularBufferIndex] = value;
circularBufferIndex++;
if (circularBufferIndex >= circularBufferLength) circularBufferIndex = 0;
}
void getFromBuffer(int* out, int outLength)
{
int readIndex = (circularBufferIndex - outLength + circularBufferLength) % circularBufferLength;
for (int iCount = 0; iCount < outLength; iCount++)
{
if (readIndex >= circularBufferLength) readIndex = 0;
out[iCount] = circularBuffer[readIndex];
readIndex++;
}
}
void getFromBufferInvert(int* out, int outLength)
{
int readIndex = circularBufferIndex - 1;
for (int iCount = 0; iCount < outLength; iCount++)
{
if (readIndex < 0) readIndex = circularBufferLength - 1;
out[iCount] = circularBuffer[readIndex];
readIndex--;
}
}
void printArray(int* x, int length)
{
for (int iCount = 0; iCount < length; iCount++)
{
Serial.print(x[iCount]);
Serial.print(',');
}
Serial.println();
}
void setup()
{
Serial.begin(115200);
Serial.println("Store 0 - 12");
for (int iCount = 0; iCount <= 12; iCount++)
{
appendToBuffer(iCount);
printArray(circularBuffer, circularBufferLength);
}
Serial.println("");
Serial.println("Get last 5");
int data[5];
int M = sizeof(data) / sizeof(int);
getFromBuffer(data, M);
printArray(data, M);
Serial.println("");
Serial.println("Get last 5 invert");
getFromBufferInvert(data, M);
printArray(data, M);
}
void loop()
{
}Estos son los resultados de ejecutar este código. Vemos que los números se almacenan en el buffer y, cuando este se llenan, empiezan a sobreescribirse. De esta forma podemos obtener los N últimos números.
Buffer circular simple con puntero
El ejemplo anterior hemos empleado el índice para acceder a la posición actual del buffer porque resulta adecuado para explicar el funcionamiento. Pero, en general, lo normal es que usemos un puntero (de hecho, es un código que está pidiendo a gritos un puntero).
Así que, para que no se diga, aquí tenéis el código modificado para emplear un puntero en lugar del índice. Básicamente el funcionamiento es el mismo que el anterior, y los resultados que obtenéis son exactamente iguales a los mostrados anteriormente.
const int circularBufferLength = 10;
int circularBuffer[circularBufferLength];
int* circularBufferAccessor = circularBuffer;
void appendToBuffer(int value)
{
circularBufferAccessor++;
if (circularBufferAccessor >= circularBuffer + circularBufferLength) circularBufferAccessor = circularBuffer;
*circularBufferAccessor = value;
}
int getFromBuffer()
{
int rst = *circularBufferAccessor;
circularBufferAccessor--;
if (circularBufferAccessor < circularBuffer) circularBufferAccessor = circularBuffer + circularBufferLength - 1;
return rst;
}
void getFromBuffer(int* out, int outLength)
{
int* readAccessor = circularBufferAccessor - outLength + 1;
if (circularBufferAccessor < circularBuffer) circularBufferAccessor = circularBuffer + circularBufferLength - 1;
for (int iCount = 0; iCount < outLength; iCount++)
{
if (readAccessor >= circularBuffer + circularBufferLength) readAccessor = circularBuffer;
out[iCount] = *readAccessor;
readAccessor++;
}
}
void getFromBufferInvert(int* out, int outLength)
{
int* readAccessor = circularBufferAccessor;
for (int iCount = 0; iCount < outLength; iCount++)
{
if (readAccessor < circularBuffer) readAccessor = circularBuffer + circularBufferLength - 1;
out[iCount] = *readAccessor;
readAccessor--;
}
}
void printArray(int* x, int length)
{
for (int iCount = 0; iCount < length; iCount++)
{
Serial.print(x[iCount]);
Serial.print(',');
}
Serial.println();
}
void setup()
{
Serial.begin(115200);
Serial.println("Store 0 - 12");
for (int iCount = 0; iCount <= 12; iCount++)
{
appendToBuffer(iCount);
printArray(circularBuffer, circularBufferLength);
}
Serial.println("");
Serial.println("Get last 5");
int data[5];
int M = sizeof(data) / sizeof(int);
getFromBuffer(data, M);
printArray(data, M);
Serial.println("");
Serial.println("Get last 5 invert");
getFromBufferInvert(data, M);
printArray(data, M);
}
void loop()
{
}Buffer circular en una librería
¿Y si lo metemos en una librería? ¡Por supuesto que sí! Aquí tenéis una librería que implementa un buffer circular en Arduino. La implementación es algo más compleja que la de esta entrada, pero a cambio es más sencilla de usar y potente. ¡A disfrutar!
Descarga el código
Todo el código de esta entrada está disponible para su descarga en Github. 