Учимся программированию на С вместе: библиотека буфера FIFO
Сразу же первой строчкой пишу что в программировании я далеко не профи, я не написал ни одного серьезного проекта, поэтому мне еще самому учиться, а не других учить. По этой причине я позиционирую этот пост не как авторскую обучающую статью, а больше как статью, побуждающую к размышлению.
Планирую рассмотреть библиотеку кольцевого буфера, которую я набросал, когда мне таки надоело реализовывать эти буферы при каждом использовании UART… Библиотека представляет из себя всего несколько строк кода, поэтому ее легко описать, и в то же время мне хотелось бы обсудить некоторые недочеты с целью самообучения. Поэтому если будет смысл — возможно появится вторая часть этой стать, с названием «Работа над ошибками».
Что такое кольцевой буфер — я объяснять не буду, т.к. тема данных сисек уже раскрыта очень широко, рассмотрю только мою реализацию.
А теперь попробуем все это переварить.
Итак, в б заголовочном файле (далее: заголовке), определен пользовательский тип данных по имени fifo_t:
FIFO_LENGTH — это длина буфера, которую нужно задефайнить в заголовке. Здесь кроется первый косяк реалиации, о нем в конце.
Т.е. если нам нужен буфер, то мы его должны сначала создать:
Данная структура хранит всю необходимую информацию о буфере. Вся дальнейшая работа будет крутиться вокруг этой структуры.
Мы объявили наш буфер, но ее еще нужно инициализировать, иначе там может быть мусор и никаких гарантий корректной работы быть не может… Для этого есть функция:
В качестве аргумента функция хавает указатель на нашу структуру, и в дальнейшем обращается по этому указателю, чтобы обнулить переменные.
Сам массив данных мы не трогаем, т.к. его содержимое не важно — когда в него будут ложиться данные он перезапишется.
На данном этапе буфер готов к использованию. Давайте в него что-нибудь положим:
Собственно первым вызовом мы кладем в буфер 32-битную переменную. В буфере она лежит как 4 байта «LSB first», т.е. младший первый.
Вторым вызовом кладем в буфер кусок массива.
В последнем параметре я специально «жестко» указывал количество байт, хотя можно (да и очень просится) использовать вещи вроде sizeof. Это второй нюанс. Функция небезопасна, и если мы укажем к примеру 5 байт в первом вызове, то мы запишем 4 байта полезных данных, и еще один невесть откуда, лежащий в памяти сразу за переменной и принадлежащий хз кому.
Забираем из буфера данные аналогичным образом:
Буфер на то и FIFO: First In — First Out. Что означает кто первый встал, того и тапки. Если мы положили туда данные, то выйдут они в том же порядке, что и вошли… Причем второй аргумент здесь содержит адрес, по которому функция запишет данные из буфера.
Вообще же буфер предназначен для хранения однообразной информации, и как правило кладем мы в него данные из одной какой-то переменной, а забирает их, например, обработчик прерывания и скармливает регистру передачи… Или наоборот, обработчик скидывает, а мы потом забираем.
Расписывать эти функции отдельно я не буду, надеюсь комментарии в коде достаточно подробны.
Ну и т.к. мой поток сознания подошел к концу, собственно вопросы:
Все это писалось под STM32, но использовались только сокращенные названия типов данных, т.к. приведя их в соответствие ANSI C эта штука должна заработать где угодно.
Планирую рассмотреть библиотеку кольцевого буфера, которую я набросал, когда мне таки надоело реализовывать эти буферы при каждом использовании 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. Что означает кто первый встал, того и тапки. Если мы положили туда данные, то выйдут они в том же порядке, что и вошли… Причем второй аргумент здесь содержит адрес, по которому функция запишет данные из буфера.
Вообще же буфер предназначен для хранения однообразной информации, и как правило кладем мы в него данные из одной какой-то переменной, а забирает их, например, обработчик прерывания и скармливает регистру передачи… Или наоборот, обработчик скидывает, а мы потом забираем.
Расписывать эти функции отдельно я не буду, надеюсь комментарии в коде достаточно подробны.
Ну и т.к. мой поток сознания подошел к концу, собственно вопросы:
- Первый косяк кроется в том, что если мы объявим несколько буферов, то все они будут иметь одну длину FIFO_LENGTH. Есть ли какие-нибудь красивые обходы этой проблемы
не вступая в кучу, кроме динамического распределения памяти? - Как по возможности обезопасить работу с указателями?
Все это писалось под STM32, но использовались только сокращенные названия типов данных, т.к. приведя их в соответствие ANSI C эта штука должна заработать где угодно.
10 комментариев
Можно использовать класс и один из чего методов будет количеством записей.
Если ты пишешь на Си, то можно сделать кучу функций «fifo_put_int», «fifo_put_char» итп. Если на C++, то можно перегрузить fifo_put для работы с нужным типом данных, можно сделать шаблон fifo_putв котором вызывать внутреннюю fifo_put c sizeof(T) в качестве размера.
Еще, буферы с count — не потокобезопасны. Если одни поток (прерывания) будут писать, а другой (задача) будет читать, то это все нужно объявлять как volatile и блокировать прерывания на время обращений к count.
В качестве альтернативы можно обойтись без count, используя только head, tail запас в один байт :)
тоже ведь может быть не атомарной, управление может быть перехвачено уже после обращения к массиву, но до инкремента «хвоста»… Или я не прав?
Вот кстати на данном этапе почитываю C# Троелсена, и действительно в С хочется иметь плюшки ООП =) Теперь понимаю, почему ты на плюсах пишешь… Наверное тоже попробую, только пока углубиться в изучение не получится, боюсь что вместе с шарпом в голове каша получится — буду путать нюансы…
А по поводу длины буфера внутри структуры — вот как-то проскакивала такая мысль, но потом решил что не получится, и даже не проверил…
Как это должно выглядеть? Что-то вида:
Но подозреваю что не совсем так, компилятор то должен знать длину массива уже на этапе объявления… (Сейчас IAR не стоит, точнее стоит только для STM8)
Все, мне пора убегать :) Спасибо за пояснение.
Ну, точно не «const», так как ты его только на этапе компиляции заполнить сможешь.
А вообще, правильно. Вообще. нужно как-то найти силы, оформить и выложить свой Fifo.
2/ Не нужна функция fifo_init() — структуру можно инициализировать при объявлении как обычную переменную
3/ Каждый экземпляр очереди должен работать с элементами одного типа/длины. Соответственно, в fifo_t стоит внести поле element_size и тогда при чтении и записи будет уже известно, сколько байт читать или писать — не потребуется указывать параметры этим функциям.
4/ Зачем функциям чтения и записи параметр offset? Фифо очередь должна сама знать, с какого элемента писать и с какого элемента читать и есть ли элементы вообще. ???
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++, если вставить в нужные места
extern «C» {
#endif
…
#ifdef __cplusplus
} // extern «C»
#endif
Еще можно отказаться от «нестандартных» названий типов, и выкинуть из кода #include <stm32f10x.h>. Тогда код можно будет использовать, например, для написания программы для AVR.