1

Тема: ring buffer

Всім привіт.

Ніяк не можу розібратись.

Оголошую дефайни, структуру, функції, буфер:

#define BUFFER_SIZE 8
#define BUFFER_MASK BUFFER_SIZE - 1

typedef struct {
  size_t first;
  size_t last;
  uint8_t data[BUFFER_SIZE];
} CircularBuffer;

void ClearBuf(CircularBuffer* pBuf)
{
  pBuf->first = 0;
  pBuf->last = 0;
}

bool IsEmpty(CircularBuffer* pBuf)
{
  return (pBuf->first == pBuf->last);
}

bool IsFull(CircularBuffer* pBuf)
{
    return (((pBuf->last + 1) & (BUFFER_MASK)) == pBuf->first);
}

bool WriteByte(CircularBuffer* pBuf, uint8_t value)
{
  size_t next = (pBuf->last + 1) & (BUFFER_SIZE - 1);
  if (next == pBuf->first)
    return false;
  pBuf->data[pBuf->last] = value;
  pBuf->last = next;
  return true;
}

size_t GetByteBuffer(CircularBuffer* pBuf)
{
  return ((pBuf->last - pBuf->first) & (BUFFER_MASK));
}

void PrintBuffer(CircularBuffer* pBuf)
{
  if (pBuf->first == pBuf->last)
    printf(" Empty");
  size_t pos;
  for (pos = pBuf->first; pos != pBuf->last; pos = (pos + 1) & (BUFFER_SIZE - 1))
    printf(" %02x", pBuf->data[pos]);
  printf("\r\n");
}

CircularBuffer bufferA;

Роблю тестову перевірку:

ClearBuf(&bufferA);

int var = 0;
  while(!IsFull(&bufferA))
  {
      if(IsEmpty(&bufferA))
          printf("buffer is empty\r\n");
      else
          printf("buffer is not empty\r\n");

      WriteByte(&bufferA, var);
      printf("write %i byte, number byte in buffer: %i\r\n", var, (int) GetByteBuffer(&bufferA));

      if(IsFull(&bufferA))
          printf("buffer is full\r\n");
      else
            printf("buffer is not full\r\n");

     var++;
  }

  printf("BufferA after write:");
  PrintBuffer(&bufferA);

Результат:
buffer is empty
write 0 byte, number byte in buffer: 1
buffer is not full
buffer is not empty
write 1 byte, number byte in buffer: 2
buffer is not full
buffer is not empty
write 2 byte, number byte in buffer: 3
buffer is not full
buffer is not empty
write 3 byte, number byte in buffer: 4
buffer is not full
buffer is not empty
write 4 byte, number byte in buffer: 5
buffer is not full
buffer is not empty
write 5 byte, number byte in buffer: 6
buffer is not full
buffer is not empty
write 6 byte, number byte in buffer: 7
buffer is full
BufferA after write: 00 01 02 03 04 05 06

Неначе і все вірно, але де 8 байт буферу? Чого після 6 байту вважається що вже повний? Чи це нормально, що кільцевий буфер має розмір на один байт менше, щоб не було переповнення? Накладок хвоста на голову?

Пробував і так:

for (int var = 0; var < BUFFER_SIZE; var++)
  {
    if(IsEmpty(&bufferA))
        printf("buffer is empty\r\n");
    else
        printf("buffer is not empty\r\n");

    WriteByte(&bufferA, var);
    printf("write %i byte, number byte in buffer: %i\r\n", var, (int) GetByteBuffer(&bufferA));
    
    if(IsFull(&bufferA))
        printf("buffer is full\r\n");
    else
        printf("buffer is not full\r\n");
  }

  printf("BufferA after write:");
  PrintBuffer(&bufferA);

Результат дещо інший. На 6 і 7 байті вважається що буфер повний і кількість байт записано 7 і 7, хоча очукую 7 і 8:

buffer is empty
write 0 byte, number byte in buffer: 1
buffer is not full
buffer is not empty
write 1 byte, number byte in buffer: 2
buffer is not full
buffer is not empty
write 2 byte, number byte in buffer: 3
buffer is not full
buffer is not empty
write 3 byte, number byte in buffer: 4
buffer is not full
buffer is not empty
write 4 byte, number byte in buffer: 5
buffer is not full
buffer is not empty
write 5 byte, number byte in buffer: 6
buffer is not full
buffer is not empty
write 6 byte, number byte in buffer: 7
buffer is full
buffer is not empty
write 7 byte, number byte in buffer: 7
buffer is full
BufferA after write: 00 01 02 03 04 05 06

Якщо не морочитись і записати 5 байт, наприклад, то все ОК.

UART1 transmit is normal.
buffer is empty
write 0 byte, number byte in buffer: 1
buffer is not full
buffer is not empty
write 1 byte, number byte in buffer: 2
buffer is not full
buffer is not empty
write 2 byte, number byte in buffer: 3
buffer is not full
buffer is not empty
write 3 byte, number byte in buffer: 4
buffer is not full
buffer is not empty
write 4 byte, number byte in buffer: 5
buffer is not full
BufferA after write: 00 01 02 03 04

2

Re: ring buffer

не можеш написати код, що працює пиши коменти, використовуй дебагер

3 Востаннє редагувалося wander (11.08.2020 20:58:44)

Re: ring buffer

taburyak написав:

Неначе і все вірно, але де 8 байт буферу? Чого після 6 байту вважається що вже повний?

Ну, якби ви самі так сказали:

bool IsFull(CircularBuffer* pBuf)
{
    return (((pBuf->last + 1) & (BUFFER_MASK)) == pBuf->first);
}

На 6 ітерації маєте - (7 + 1) & 7, що відповідно поверне 0.

taburyak написав:

Чи це нормально, що кільцевий буфер має розмір на один байт менше, щоб не було переповнення?

Кільцевий буфер має розмір на один байт менше ніж ЩО?

taburyak написав:

На 6 і 7 байті вважається що буфер повний і кількість байт записано 7 і 7, хоча очукую 7 і 8

А 8 там звідки має взятись? Я б очікував результат: 00 01 02 03 04 05 06 07

Дам вам підказку, у вашій ф-ї WriteByte є перевірка, яка і не дає записатися 7 елементу.
І ф-я PrintBuffer чомусь так складно написана, хоча там достатньо і простого

for (size_t i = 0; i < BUFFER_SIZE; i++)
Подякували: leofun01, taburyak2

4 Востаннє редагувалося koala (11.08.2020 23:27:01)

Re: ring buffer

Перед тим, як писати, треба продумати алгоритм. Це типова задача про паркан і кілки.
Кільцевий буфер на n елементів може мати n+1 стан (без урахування значень елементів) - від порожнього до повного (в цьому випадку від 0 до 8 ). Відповідно, неможливо представити розмір буфера однією змінною на 8 значень просто тому, що значень буде 9. Можна, наприклад, додати ще одну змінну, що визначатиме, чи буфер пустий і таким чином розрізнятиме ситуації first==last. Або використовувати особливе значення first, скажімо, -1, для позначення цього.
Ну й ігри з масками вам, швидше за все, ні до чого. Заміна BUFFER_SIZE на 9 ламає увесь код при вашому підході. Також, якщо ви вже використовуєте макроси, то беріть вирази в дужки в define, а не при використанні. Один раз не візьмете і BUFFER_MASK * 5 перетвориться з 35 на 3.

Подякували: leofun01, taburyak2

5

Re: ring buffer

Всім дякую за критику, поради - ціную.

Зробив функцію переносу даних з одного кільцевого буфера в інший за допомоги memcpy. таке завдання. Треба, щоб порції використались якомога більші, щоб менше було викликів memcpy. Я зробив, щоб максимум два рази коли є перехід від кінця масиву на початок. Але, як на мене, багато перевірок, умов і все таке. Вирішив в лоб. Якось можна це оптимізувати? Чи по іншому?

size_t BufMoveFast(CircularBuffer* pDest, CircularBuffer* pSource)
{
  if ((pDest == pSource) || (IsEmpty(pSource)) || (IsFull(pDest)))
    return 0;

  size_t result    = 0;        //кількость байт які перенесли з буферу в буфер
  size_t sourcePortion;        //яку порцію необхідно перенести
  size_t destPortion;        //яку порцію можна впіхнути
  size_t byEndOf;            //яка максимальна порція до кінця буферу

  while((!IsEmpty(pSource)) && (!IsFull(pDest)))    //якщо джерело не пусте, а приймач не повний
  {
      sourcePortion = GetByteBuffer(pSource);        //визначаємо кількість байт для переносу

      if(pDest->last >= pDest->first) //перевіряємо де знаходиться перша вільна комірка буфера
      {
        destPortion = BUFFER_SIZE - GetByteBuffer(pDest); //визначаємо вільне місце в буфері який приймає
        byEndOf = BUFFER_SIZE - pDest->last; //визначаємо скільки не переривного простору до кінця масиву
        if(byEndOf < sourcePortion)    //як до кінця масиву менше байт чим потрібно перекинути 
            destPortion = byEndOf; //то присвоюємо, те що можемо прийняти, як кількість до кінця масиву (1-ша порція)
      }
      else
      {
        destPortion = pDest->first - pDest->last; //присвоюємо кількість байт до першої зайнятої комірки буфера
      }

      if(sourcePortion <= destPortion) //якщо порція джерела менша або рівна можливостям прийому
          destPortion = sourcePortion; //присвоюємо що будемо приймати кількість байтів джерела

      memcpy(&pDest->data[pDest->last], &pSource->data[pSource->first], destPortion); //переносимо дані
      pSource->first = (pSource->first + destPortion) & BUFFER_MASK; //зміщуємо в джерелі маркер першого байту
      if(((pDest->last + destPortion) & BUFFER_MASK) == pDest->first) //якщо маркер кінця даних дорівнює початку,
          destPortion--; //то зменшуємо на одиницю свої можливості в прийомі (таке життя, така сутність цього методу, жертвуємо одним байтом щоб розрізняти пустий і повний буфер)
      pDest->last = (pDest->last + destPortion) & BUFFER_MASK; //зміщюємо маркер першого байту для запису.
      result += destPortion; //рахуємо кількість перенесених даних
  }

  return result; //повертаємо результат
}

6

Re: ring buffer

Підозрюю, що запис можна зробити кращим, якщо активно використовувати std::min та функцію перенесення на початок буфера (ваше & BUFFER_MASK). Але по суті - так, там буде купа перевірок і до 3 викликів memcpy.

Подякували: ReAl1

7

Re: ring buffer

Щось подібне і я сказав. Наробити спочатку допоміжних функцій «скільки неперервних вільного місця/даних є» (до відповідного індекса або до кінця масиву, там теж min чи його річне втілення буде), а потім з них від різних буферів тим же min-ом отримувати довжину для memcpy().
А далі компілятор утовче.

Лише якщо дуже треба у конкретних умовах можна думати про те, щоб піти від купи перевірок >/< на жонглювання бітовими масками, але боюся, що у таких випадках для пришвидшення вже буде корисніше думати про zero-copy + scatter-gather (якщо сам DMA не виміє, то вручну в його обробниках переривань), а в кільцьовому буфері тримати структури вказівник+довжина і від початкового джерела з буфера у буфер до кінцевого споживача ганяти такі структури.