Circular Byte Buffer For Embedded Applications (Index Based)

circularBuffer_uint8.h

// # Circular Byte Buffer For Embedded Applications (Index Based)
// Author: Brian Khuu (July 2020) (briankhuu.com) ([email protected])
// Reason: Malloc free, minimum overhead implementation of a circular buffer.
//   Static inlined handlers for speed and ease of usage in various projects.
//   Index based implementation diverges from harshkn's version, since it is
//   easier for me to grok. However may come at cost of speed and optimisation.
//   Also uses byte based rather than item based for easier understability
//   when used for simpler byte array circular buffers.
//   I have also written an pointer based circular buffer version.
// Based on harshkn's circular buffer: https://gist.github.com/harshkn/909546
// This Gist (Pointer): https://gist.github.com/mofosyne/d7a4a8d6a567133561c18aaddfd82e6f
// This Gist (Index): https://gist.github.com/mofosyne/82020d5c0e1e11af0eb9b05c73734956

#include <stdint.h> // uint8_t
#include <stddef.h> // size_t
#include <stdbool.h> // bool

// Prefill Circular Buffer (Allows for skipping `circularBuffer_uint8_Init()`)
#define circularBuffer_uint8_struct_full_prefill(BuffSize, BuffPtr) \
{                                                                   \
  .capacity  = BuffSize,                                            \
  .count     = 0,                                                   \
  .buffer    = BuffPtr,                                             \
  .head      = 0,                                                   \
  .tail      = 0                                                    \
}
#define circularBuffer_uint8_struct_prefill(Buff) circularBuffer_uint8_struct_full_prefill((sizeof(Buff)/sizeof(Buff[0])), &Buff[0])

typedef struct circularBuffer_uint8_t
{
  size_t capacity; ///< Maximum number of items in the buffer
  size_t count;    ///< Number of items in the buffer
  uint8_t *buffer; ///< Data Buffer
  size_t head;     ///< Head Index
  size_t tail;     ///< Tail Index
} circularBuffer_uint8_t;


/*******************************************************************************
 * Init/IsInit/Reset
*******************************************************************************/

static inline bool circularBuffer_uint8_Init(circularBuffer_uint8_t *cb, size_t capacity, uint8_t *buffPtr)
{
  circularBuffer_uint8_t emptyCB = {0};
  if ((cb == NULL) || (buffPtr == NULL))
    return false; ///< Failed
  // Init Struct
  *cb = emptyCB;
  cb->capacity = capacity;
  cb->buffer = buffPtr;
  cb->count = 0;
  cb->head = 0;
  cb->tail = 0;
  return true; ///< Successful
}

static inline bool circularBuffer_uint8_IsInit(circularBuffer_uint8_t *cb)
{
  return cb->capacity && cb->buffer;
}

static inline bool circularBuffer_uint8_Reset(circularBuffer_uint8_t *cb)
{
  cb->count = 0;
  cb->head = 0;
  cb->tail = 0;
  return true; ///< Successful
}


/*******************************************************************************
 * Circular byte buffer Enqueue/Dequeue (This will modify the buffer)
*******************************************************************************/

static inline bool circularBuffer_uint8_EnqueueOverwrite(circularBuffer_uint8_t *cb, const uint8_t b)
{
  if (cb->count >= cb->capacity)
  {
    // Full. Increment head
    cb->head = (cb->head + 1) % cb->capacity;
  }
  else
  {
    // Not Full. Update Counter
    cb->count = cb->count + 1;
  }
  // Push value
  cb->buffer[cb->tail] = b;
  // Increment tail
  cb->tail = (cb->tail + 1) % cb->capacity;
  return true; ///< Successful
}

static inline bool circularBuffer_uint8_Enqueue(circularBuffer_uint8_t *cb, const uint8_t b)
{
  // Full
  if (cb->count >= cb->capacity)
    return false; ///< Failed
  // Push value
  cb->buffer[cb->tail] = b;
  // Increment tail
  cb->tail = (cb->tail + 1) % cb->capacity;
  cb->count = cb->count + 1;
  return true; ///< Successful
}

static inline bool circularBuffer_uint8_Dequeue(circularBuffer_uint8_t *cb, uint8_t *b)
{
  // Empty
  if (cb->count == 0)
    return false; ///< Failed
  // Pop value
  *b = cb->buffer[cb->head];
  // Increment head
  cb->head = (cb->head + 1) % cb->capacity;
  cb->count = cb->count - 1;
  return true; ///< Successful
}


/*******************************************************************************
 * Circular byte buffer Peek (Will Not Modify Buffer)
*******************************************************************************/

static inline bool circularBuffer_uint8_Peek(circularBuffer_uint8_t *cb, uint8_t *b, const size_t offset)
{
  // Empty?
  if (cb->count == 0)
    return false; ///< Failed
  if (cb->count < offset)
    return false; ///< Failed
  *b = cb->buffer[(cb->head + offset) % cb->capacity];
  return true; ///< Successful
}


/*******************************************************************************
 * Circular byte buffer utility functions (Will Not Modify Buffer)
*******************************************************************************/

static inline size_t circularBuffer_uint8_Capacity(circularBuffer_uint8_t *cb)
{
  return cb->capacity;
}

static inline size_t circularBuffer_uint8_Count(circularBuffer_uint8_t *cb)
{
  return cb->count;
}

static inline bool circularBuffer_uint8_IsFull(circularBuffer_uint8_t *cb)
{
  return (cb->count >= cb->capacity);
}

static inline bool circularBuffer_uint8_IsEmpty(circularBuffer_uint8_t *cb)
{
  return (cb->count == 0);
}


#if 0 // Last Confirmed Working On 2021-07-07 By Brian Khuu [email protected]
/*******************************************************************************
 * Mini Unit Test Of Circular Buffer
*******************************************************************************/
#include <stdio.h>
#define BUFF_TEST_SIZE 4

// Minimum Assert Unit (https://jera.com/techinfo/jtns/jtn002)
#define mu_assert(message, test) do { if (!(test)) return LINEINFO " : (expect:" #test ") " message; } while (0)
#define mu_run_test(test) do { char *message = test(); if (message) return message; } while (0)

// Line Info (Ref: __LINE__ to string http://decompile.com/cpp/faq/file_and_line_error_string.htm)
#define LINEINFO_STR(X) #X
#define LINEINFO__STR(X) LINEINFO_STR(X)
#define LINEINFO __FILE__ " : " LINEINFO__STR(__LINE__)

#if 0 // Dev Note: Use this to debug the content of the circular buffer
void circularBuffer_inspect(circularBuffer_uint8_t *cb, char * msg)
{
  printf("\n%s : ", msg);
  for (int i = 0 ; i < cb->capacity ; i++)
    printf(" %d", cb->buffer[i]);
  printf("\n");
}
#endif

char * cbuff_test_prefill(void)
{
  uint8_t cbuffer[BUFF_TEST_SIZE] = {0};
  circularBuffer_uint8_t prefilledBuff = circularBuffer_uint8_struct_prefill(cbuffer);
  circularBuffer_uint8_t initBuff = {0};
  mu_assert("", !circularBuffer_uint8_IsInit(&initBuff));
  circularBuffer_uint8_Init(&initBuff, BUFF_TEST_SIZE, cbuffer);
  mu_assert("", circularBuffer_uint8_IsInit(&initBuff));
  mu_assert("", circularBuffer_uint8_Capacity(&prefilledBuff) == BUFF_TEST_SIZE);
  mu_assert("", circularBuffer_uint8_Count(&prefilledBuff) == 0);
  mu_assert("", !circularBuffer_uint8_IsFull(&prefilledBuff));
  mu_assert("", circularBuffer_uint8_IsEmpty(&prefilledBuff));
  mu_assert("", prefilledBuff.capacity == initBuff.capacity );
  mu_assert("", prefilledBuff.count    == initBuff.count    );
  mu_assert("", prefilledBuff.buffer   == initBuff.buffer   );
  mu_assert("", prefilledBuff.head     == initBuff.head     );
  mu_assert("", prefilledBuff.tail     == initBuff.tail     );
  circularBuffer_uint8_Reset(&initBuff);
  mu_assert("", prefilledBuff.count    == initBuff.count    );
  mu_assert("", prefilledBuff.head     == initBuff.head     );
  mu_assert("", prefilledBuff.tail     == initBuff.tail     );
  return 0;
}

char * cbuff_test_general(void)
{
  uint8_t cbuffer[BUFF_TEST_SIZE] = {0};
  circularBuffer_uint8_t prefilledBuff = circularBuffer_uint8_struct_prefill(cbuffer);
  for (int i = 0 ; i < BUFF_TEST_SIZE ; i++)
  {
    mu_assert("", !circularBuffer_uint8_IsFull(&prefilledBuff));
    mu_assert("", circularBuffer_uint8_Enqueue(&prefilledBuff, i));
    mu_assert("", !circularBuffer_uint8_IsEmpty(&prefilledBuff));
    mu_assert("", circularBuffer_uint8_Count(&prefilledBuff) == (i+1));
  }
  mu_assert("", !circularBuffer_uint8_Enqueue(&prefilledBuff, 0x33));
  mu_assert("", circularBuffer_uint8_IsFull(&prefilledBuff));
  mu_assert("", !circularBuffer_uint8_IsEmpty(&prefilledBuff));
  for (int i = 0 ; i < BUFF_TEST_SIZE ; i++)
  {
    uint8_t d = -1;
    mu_assert("", circularBuffer_uint8_Dequeue(&prefilledBuff, &d));
    mu_assert("", d == i);
  }
  return 0;
}

char * cbuff_test_overwrite(void)
{
  uint8_t cbuffer[BUFF_TEST_SIZE] = {0};
  circularBuffer_uint8_t prefilledBuff = circularBuffer_uint8_struct_prefill(cbuffer);
  for (int i = 0 ; i < BUFF_TEST_SIZE ; i++)
  {
    circularBuffer_uint8_Enqueue(&prefilledBuff, i);
  }
  for (int i = 0 ; i < BUFF_TEST_SIZE ; i++)
  {
    circularBuffer_uint8_EnqueueOverwrite(&prefilledBuff, i+1);
  }
  for (int i = 0 ; i < BUFF_TEST_SIZE ; i++)
  {
    uint8_t d = -1;
    mu_assert("", circularBuffer_uint8_Dequeue(&prefilledBuff, &d));
    mu_assert("", d == i + 1);
  }
  return 0;
}

char * cbuff_test_peek(void)
{
  uint8_t cbuffer[3] = {0};
  circularBuffer_uint8_t prefilledBuff = circularBuffer_uint8_struct_prefill(cbuffer);
  for (int i = 1 ; i < 5 ; i++)
  {
    circularBuffer_uint8_EnqueueOverwrite(&prefilledBuff, i);
  }
  for (int i = 0 ; i < 3 ; i++)
  {
    uint8_t d = -1;
    mu_assert("", circularBuffer_uint8_Peek(&prefilledBuff, &d, i));
    mu_assert("", d == i+2);
  }
  return 0;
}

static char * all_tests()
{
  mu_run_test(cbuff_test_prefill);
  mu_run_test(cbuff_test_general);
  mu_run_test(cbuff_test_overwrite);
  mu_run_test(cbuff_test_peek);
  return 0;
}

int main(void)
{
  char *result = all_tests();
  printf("%s\n", (result) ? result : "ALL TESTS PASSED\n");
  return result != 0;
}
#endif

Not tested, but I imagine a naive way to overwrite old entries, would be to increment the head directly without popping the value from circularByteBuffer_Dequeue(), as shown below:

static inline bool circularByteBuffer_Enqueue(circularByteBuffer_t *cb, uint8_t b)
{
  // Full
  if (cb->count >= cb->capacity)
  {
    // Increment head
    cb->head = (cb->head + 1) % cb->capacity;
    cb->count = cb->count - 1;
  }
  // Push value
  cb->buffer[cb->tail] = b;
  // Increment tail
  cb->tail = (cb->tail + 1) % cb->capacity;
  cb->count = cb->count + 1;
  return true; ///< Successful
}

I'll still keep the counter, as it is handy to know initially if the buffer is fully filled up.

Thanks, that worked nicely, I still think it is good idea to keep empty and full as state of the circular buffer to for example have easier handshaking and etc.

Glad to see it worked out. I took the time to update this page with improvements based on your suggestions.

• Added mini unit test (Just uncomment and rename as .c to check if the circular buffer is working). This will also effectively provide usage examples.
• Added circularBuffer_uint8_EnqueueOverwrite() which is what you originally seeked out.
• Added circularBuffer_uint8_Peek() which was useful for https://github.com/mofosyne/arduino-gameboy-printer-emulator
• Refactored to add const to certain parameters as best practice coding.
• Renamed functions to add _uint8_ notations, as I have found in practices, you may want multiple circular buffers of varying word sizes.

Hopefully it helps you out. Let me know if it does. :)