Учимся программированию на С вместе: библиотека буфера FIFO

Сразу же первой строчкой пишу что в программировании я далеко не профи, я не написал ни одного серьезного проекта, поэтому мне еще самому учиться, а не других учить. По этой причине я позиционирую этот пост не как авторскую обучающую статью, а больше как статью, побуждающую к размышлению.

Планирую рассмотреть библиотеку кольцевого буфера, которую я набросал, когда мне таки надоело реализовывать эти буферы при каждом использовании UART… Библиотека представляет из себя всего несколько строк кода, поэтому ее легко описать, и в то же время мне хотелось бы обсудить некоторые недочеты с целью самообучения. Поэтому если будет смысл — возможно появится вторая часть этой стать, с названием «Работа над ошибками».

Что такое кольцевой буфер — я объяснять не буду, т.к. тема данных сисек уже раскрыта очень широко, рассмотрю только мою реализацию.

Заголовочный файл

/*******************************************************************
Библиотека, реализующая кольцевой (циклический) буфер.
Автор: N1X
*******************************************************************/
#ifndef FIFO_H
#define FIFO_H

#include <stm32f10x.h>

/*
Здесь задается длина буфера
*/
#define FIFO_LENGTH 16

/*******************************************************************
fifo_t: Тип, описывающий тело нашего буфера:
data: Массив с данными. Здесь хранится содержимое буфера.
head: Переменная, хранящая в себе индекс головы буфера.
tail: Переменная, хранящая в себе индекс хвоста буфера.
count: Переменная, хранящая кол-во элементов, находящихся в буфере.
*******************************************************************/
typedef struct {
  u8 data[FIFO_LENGTH];
  u8 head;
  u8 tail;
  u8 count;
} fifo_t;

/*******************************************************************
Функция: fifo_init - инициализирует буфер
Аргументы: 
  fifo_t *fifo - указатель на буфер
Значение: --
*******************************************************************/
void fifo_init(fifo_t *fifo);

/*******************************************************************
Функция: fifo_put - "кладет" данные в буфер
Аргументы:
  fifo_t *fifo  - указатель на буфер
  void *data    - указатель на данные (любой тип)
  u8 offset     - смещение с начального адреса (удобно при работе с массивом)
  u8 count      - количество байт данных
Значение:
s8 - целое со снаком.
  0 - все ОК
  -1 - не хватает места в буфере для выволнения операции
*******************************************************************/
s8 fifo_put(fifo_t *fifo, void *data, u8 offset, u8 count);
/*******************************************************************
Функция: fifo_get - "берет" данные из буфера
Аргументы:
  fifo_t *fifo  - указатель на буфер
  void *data    - указатель на место для данных (любой тип)
  u8 offset     - смещение с начального адреса (удобно при работе с массивом)
  u8 count      - количество байт данных для чтения
Значение:
s8 - целое со снаком.
  0 - все ОК
  -1 - запрошено больше данных, чем есть в буфере
*******************************************************************/
s8 fifo_get(fifo_t *fifo, void *data, u8 offset, u8 count);
/*******************************************************************
Функция: fifo_count - возвращает количество байт в буфере
Аргументы:
  fifo_t *fifo  - указатель на буфер
Значение:
  s8 - число байт в буфере
*******************************************************************/
u8 fifo_count(fifo_t *fifo);

#endif


Тело

#include "fifo.h"


s8 fifo_put(fifo_t *fifo, void *data, u8 offset, u8 count)
{
  if ((FIFO_LENGTH - fifo->count) < count)                      //Проверяем, достаточно ли места
    return -1;                                                  //Нет? Возвращаем "-1" и уходим
  for (u8 i = offset; i < (offset + count); i++)                //Цикл заполнения
  {
    fifo->data[fifo->tail++] =((u8*) data)[i];                  //Кладем сами данные и сразу tail++
    fifo->count++;                                              //Увеличиваем переменную-счетчик
    if (fifo->tail == FIFO_LENGTH)                              //Если уперлись в границу длины
    {
      fifo->tail=0;                                             //Обнуляем хвост
    }                                                           //Т.е. "сворачиваем" буфер в кольцо
  }
  return 0;                                                     //Возвращаем "ОК"
}

s8 fifo_get(fifo_t *fifo, void *data, u8 offset, u8 count)
{
  if (fifo->count < count)                                      //Проверяем, можем ли мы выдать столько,
    return -1;                                                  //сколько у нас просят
  for (u8 i = offset; i < (offset + count); i++)                //Цикл записи
  {
    ((u8*)data)[i] = fifo->data[fifo->head++];                  //Пишем байт по указанному адресу, head++
    fifo->count--;                                              //Уменьшаем счетчик байт
    if (fifo->head == FIFO_LENGTH)                              //Если уперлись в границу длины
    {
      fifo->head=0;                                             //Обнуляем голову
    }
  }
  return 0;
}

u8 fifo_count(fifo_t *fifo)
{
  return fifo->count;
}

void fifo_init(fifo_t *fifo)
{
  fifo->head = fifo->tail = fifo->count = 0;
}


А теперь попробуем все это переварить.
Итак, в б заголовочном файле (далее: заголовке), определен пользовательский тип данных по имени fifo_t:

typedef struct {
  u8 data[FIFO_LENGTH];
  u8 head;
  u8 tail;
  u8 count;
} fifo_t;

FIFO_LENGTH — это длина буфера, которую нужно задефайнить в заголовке. Здесь кроется первый косяк реалиации, о нем в конце.
Т.е. если нам нужен буфер, то мы его должны сначала создать:
fifo_t MyBuf;

Данная структура хранит всю необходимую информацию о буфере. Вся дальнейшая работа будет крутиться вокруг этой структуры.
Мы объявили наш буфер, но ее еще нужно инициализировать, иначе там может быть мусор и никаких гарантий корректной работы быть не может… Для этого есть функция:
fifo_init(&MyBuf);

В качестве аргумента функция хавает указатель на нашу структуру, и в дальнейшем обращается по этому указателю, чтобы обнулить переменные.
void fifo_init(fifo_t *fifo)
{
  fifo->head = fifo->tail = fifo->count = 0;
}

Сам массив данных мы не трогаем, т.к. его содержимое не важно — когда в него будут ложиться данные он перезапишется.
На данном этапе буфер готов к использованию. Давайте в него что-нибудь положим:

uint32_t MyData;
char MyAr[] = {1,2,3,4,5};
s8 error = 0;
error = fifo_put(&MyBuf, &MyData, 0, 4); //Положит 4 байта из 32 битной переменной
//гдето здесь следует проверить переменную error
error = fifo_put(&MyBuf, MyAr, 1, 2);    //Положит два байта с 1й позиции, числа 2 и 3
//и здесь тоже

Собственно первым вызовом мы кладем в буфер 32-битную переменную. В буфере она лежит как 4 байта «LSB first», т.е. младший первый.
Вторым вызовом кладем в буфер кусок массива.
В последнем параметре я специально «жестко» указывал количество байт, хотя можно (да и очень просится) использовать вещи вроде sizeof. Это второй нюанс. Функция небезопасна, и если мы укажем к примеру 5 байт в первом вызове, то мы запишем 4 байта полезных данных, и еще один невесть откуда, лежащий в памяти сразу за переменной и принадлежащий хз кому.

Забираем из буфера данные аналогичным образом:
fifo_get(&MyBuf, &MyData, 0, 4);

Буфер на то и FIFO: First In — First Out. Что означает кто первый встал, того и тапки. Если мы положили туда данные, то выйдут они в том же порядке, что и вошли… Причем второй аргумент здесь содержит адрес, по которому функция запишет данные из буфера.
Вообще же буфер предназначен для хранения однообразной информации, и как правило кладем мы в него данные из одной какой-то переменной, а забирает их, например, обработчик прерывания и скармливает регистру передачи… Или наоборот, обработчик скидывает, а мы потом забираем.
Расписывать эти функции отдельно я не буду, надеюсь комментарии в коде достаточно подробны.
Ну и т.к. мой поток сознания подошел к концу, собственно вопросы:
  1. Первый косяк кроется в том, что если мы объявим несколько буферов, то все они будут иметь одну длину FIFO_LENGTH. Есть ли какие-нибудь красивые обходы этой проблемы не вступая в кучу, кроме динамического распределения памяти?
  2. Как по возможности обезопасить работу с указателями?
Ну дальше уточнения, советы, критика приветствуется.
Все это писалось под STM32, но использовались только сокращенные названия типов данных, т.к. приведя их в соответствие ANSI C эта штука должна заработать где угодно.

10 комментариев

avatar
FIFO_LENGTH — это длина буфера, которую нужно задефайнить в заголовке.
Предлагаю тебе внести в fifo_t количество элементов в этому буфере :)
Можно использовать класс и один из чего методов будет количеством записей.

если мы укажем к примеру 5 байт в первом вызове, то мы запишем 4 байта полезных данных
Если ты пишешь на Си, то можно сделать кучу функций «fifo_put_int», «fifo_put_char» итп. Если на C++, то можно перегрузить fifo_put для работы с нужным типом данных, можно сделать шаблон fifo_putв котором вызывать внутреннюю fifo_put c sizeof(T) в качестве размера.

Еще, буферы с count — не потокобезопасны. Если одни поток (прерывания) будут писать, а другой (задача) будет читать, то это все нужно объявлять как volatile и блокировать прерывания на время обращений к count.

В качестве альтернативы можно обойтись без count, используя только head, tail запас в один байт :)
Комментарий отредактирован 2013-01-27 10:15:00 пользователем bsvi
avatar
Вот кстати не мог вспомнить 3й пункт в вопросы, а это как раз были потоковые обращения… Да, на данный момент отключаю прерывания перед вызовом функций, внутрь библиотеки это не вносил, т.к. считаю что про манипуляции с прерываниями нужно помнить в контексте проекта… И кстати без count тоже вопрос… Конструкция вида
fifo->data[fifo->tail++] =((u8*) data)[i];

тоже ведь может быть не атомарной, управление может быть перехвачено уже после обращения к массиву, но до инкремента «хвоста»… Или я не прав?
Вот кстати на данном этапе почитываю C# Троелсена, и действительно в С хочется иметь плюшки ООП =) Теперь понимаю, почему ты на плюсах пишешь… Наверное тоже попробую, только пока углубиться в изучение не получится, боюсь что вместе с шарпом в голове каша получится — буду путать нюансы…
А по поводу длины буфера внутри структуры — вот как-то проскакивала такая мысль, но потом решил что не получится, и даже не проверил…
Как это должно выглядеть? Что-то вида:

typedef struct {
  u8 const len;
  u8 data[len];
  u8 head;
  u8 tail;
  u8 count;
} fifo_t;

Но подозреваю что не совсем так, компилятор то должен знать длину массива уже на этапе объявления… (Сейчас IAR не стоит, точнее стоит только для STM8)
Все, мне пора убегать :) Спасибо за пояснение.
avatar
Перехвачена то может быть, но инкремент хвоста ведется только в прерывании. А в основном потоке ведется инкремент головы. В итоге, они между собой не конфликтуют. Нет, бывают конечно конфликты, когда нужно выяснить сколько элементов в буфере, но тогда уж можно и прерывания запретить.

Как это должно выглядеть? Что-то вида:
Ну, точно не «const», так как ты его только на этапе компиляции заполнить сможешь.

А вообще, правильно. Вообще. нужно как-то найти силы, оформить и выложить свой Fifo.
Комментарий отредактирован 2013-01-27 17:16:18 пользователем bsvi
avatar
Мне понравилась реализация Работа с кольцевым буфером, теперь постоянно использую. Как говорят «просто, дешево, сердито» :)
avatar
Да, реализация действительно красивее :) Особенно понравилось решение с маской, избавляемся от условного перехода, что есть гут ) Да и от лишней переменной…
avatar
1/ Вынеси data из структуры fifo_t, оставь только указатель на внешний массив. Это позволит создавать очереди разной длины. Нужно вбудет объявлять сначала массив, потом экземпляр fifo_t и инициализировать указатель.
2/ Не нужна функция fifo_init() — структуру можно инициализировать при объявлении как обычную переменную
3/ Каждый экземпляр очереди должен работать с элементами одного типа/длины. Соответственно, в fifo_t стоит внести поле element_size и тогда при чтении и записи будет уже известно, сколько байт читать или писать — не потребуется указывать параметры этим функциям.
4/ Зачем функциям чтения и записи параметр offset? Фифо очередь должна сама знать, с какого элемента писать и с какого элемента читать и есть ли элементы вообще. ???
avatar
ложит и бурет в заголовке функций не по русски…
avatar
Благодарю, поправил.
avatar
Оставлю пару полезных, на мой взгляд, мыслей и рекомендаций.

1. Как уже сказали, лучше в структуре объявить лишь указатель на массив. А уж предоставить собственно массив для буфера — пусть будет задача пользователя.
2. Как обезопасить работу с указателями? Возьмите себе за привычку всегда проверять в начале функций все указатели на NULL, и сразу выдавать ошибку если был передан неинициализированный указатель.
3. Ваша функция выдаст ошибку, если данные не помещаются в буфер целиком. Может оно и верно. А возможно будет удобнее, если функция будет класть в очередь что может, и возвращать количество реально записанных байт. Тут стоит подумать. Вообще подход возвращать что-то более полезное чем 0 и -1 приветствуется.
4. Если функция не изменяет никаких данных в массиве, переданном ей в качестве аргумента, то указатель на этот массив стоит объявлять как const void *. Например, если у меня есть строка «Hello, world!» (как раз тип const), и я хочу запихать ее в буфер.
5. Может стоит добавить функции для записи/чтения одного единственного байта, а не массива. Иногда бывает полезно при использовании в алгоритмах.
6. Кто-то предгалал не использовать переменную count, которая хранит размер данных в очереди. Но тут есть одна проблема — когда буфер заполнится полностью, не получится ли так, что head станет равно tail?
Что я хочу сказать: изначально у нас head = 0, tail = 0. Допустим, мы пишем в очередь FIFO_LENGTH байт данных. Тогда и head станет под конец равным FIFO_LENGTH, и выполнится условие if (fifo->tail == FIFO_LENGTH), что сбросит его опять в 0. Тем самым «очистив буфер». Решений тут два:
1) Хранить не tail и head, а tail и length. А head вычислять.
2) Оставлять в буфере всегда 1 байт.

7. Старайтесь не писать в алгоритмах «жесткие» сравнения: по типу if (fifo->head == FIFO_LENGTH).
Особенно это касается сравнений чисел с плавающей запятой. Ваш алгоритм может быть более стойким к изменениям, если написать if (fifo->head >= FIFO_LENGTH). Или, если совсем заморочиться, та же операция в более общем виде:
while(fifo->head >= FIFO_LENGTH){ fifo->head -= FIFO_LENGTH; } // по сути то же, что и fifo->head %= FIFO_LENGTH

8. Если пишете код «для всех» (библиотеку), то старайтесь делать так, чтобы он заработал сразу у всех.
Например, объявления переменных в середине функции и особенно в for(int i = 0; ...) могут вылезти ошибками при компиляции gcc с флагами -pedantic и -ansi. Еще можно порадовать любителей C++, если вставить в нужные места
Спойлер
#ifdef __cplusplus
extern «C» {
#endif

#ifdef __cplusplus
} // extern «C»
#endif


Еще можно отказаться от «нестандартных» названий типов, и выкинуть из кода #include <stm32f10x.h>. Тогда код можно будет использовать, например, для написания программы для AVR.
avatar
Спасибо, очень конструктивно! :)
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.