Кольцевой буфер на С++ для МК.

Кольцевой буфер (КБ)(Ring Buffer) — структура данных типа FIFO (First In First Out — первым вошел, первым вышел), находит очень широкое применение в том числе при программировании МК. Кольцевые буферы часто используют для организации различных очередей сообщений и буферов приёма-передачи различных коммуникационных интерфейсов. Популярность КБ обусловлена тем, что это один из самых простых и эффективных способов организовать FIFO без использования динамической памяти. Существует множество разновидностей КБ, о них можно почитать, например тут en.wikipedia.org/wiki/Circular_buffer Рассмотрим одну очень быструю и компактную реализацию КБ на С++.
В для реализации КБ я выбрал так называемую схему с абсолютными индексами, то есть нам понадобятся только две дополнительные переменные для организации буфера. Одна хранит количество элементов записанных в буфер, другая — количество прочитанных элементов. При этом количество элементов в буфере всегда будет равно разности записанных и прочитанных элементов, даже с учетом того, что это счетчики будут проворачиваться через ноль. Чтобы вычислить относительные индексы нам понадобится взять остаток от деления (модуль) абсолютных индексов на длину буфера, если возможные длины буфера ограничить степенями двойки, то модуль можно реализовать с помощью побитового И. Битовая маска для вычисления относительных индексов будет равна длине буфера минус единица, например:

Длина буфера = 16 = b00010000,
Маска = 16 — 1 = 15 = b00001111.

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

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


// Шаблон кольцевого буфера
// принимает два параметра:
// размер буфера - должен быть степенью двойки,
// тип элементов хранящихся в буфере, по умолчанию unsigned char
template<int SIZE, class DATA_T=unsigned char>
class RingBuffer
{
public:
// определяем псевдоним для индексов 
	typedef uint16_t INDEX_T;
private:
// память под буфер
	DATA_T _data[SIZE];
// количество чтений
	volatile INDEX_T _readCount;
// количество записей
	volatile INDEX_T _writeCount;
// маска для индексов
	static const INDEX_T _mask = SIZE - 1;
public:
// запись в буфер, возвращает true если значение записано
	inline bool Write(DATA_T value)
	{
		if(IsFull())
			return false;
		_data[_writeCount++ & _mask] = value;
		return true;
	}
// чтение из буфера, возвращает true если значение прочитано
	inline bool Read(DATA_T &value)
	{
		if(IsEmpty())
			return false;
		value = _data[_readCount++ & _mask];
		return true;
	}
// возвращает первый элемент из буфера, не удаляя его
	inline DATA_T First()const
	{
		return operator[](0);
	}
// возвращает последний элемент из буфера, не удаляя его
	inline DATA_T Last()const
	{
		return operator[](Count());
	}
// возвращает элемент по индексу
	inline DATA_T& operator[] (INDEX_T i)
	{
		if(IsEmpty() || i > Count())
			return DATA_T();
		return _data[(_readCount + i) & _mask];
	}

	inline const DATA_T operator[] (INDEX_T i)const
	{
		if(IsEmpty())
			return DATA_T();
		return _data[(_readCount + i) & _mask];
	}
// пуст ли буфер
	inline bool IsEmpty()const
	{
		return _writeCount == _readCount;
	}
// полон ли буфер
	inline bool IsFull()const
	{
		return ((INDEX_T)(_writeCount - _readCount) & (INDEX_T)~(_mask)) != 0;
	}
// количество элементов в буфере
	INDEX_T Count()const
	{
		return (_writeCount - _readCount) & _mask;
	}
// очистить буфер
	inline void Clear()
	{
		_readCount=0;
    		_writeCount=0;
	}
// размер буфера
	inline unsigned Size()
	{return SIZE;}
};

Интересной особенностью этого буфера является то, что при чтении и записи модифицируются разные переменные. Значит если, например, только один поток (или прерывания) пишет в буфер и только один поток читает из него, то нет необходимости в критических секциях при обращении к буферу. Например, USART — запись только в прерывании на приём байта, чтение — в главном цикле. Ну а если по несколько потоков пишут и/или читают в буфер, то без критических секций уже не обойтись. Например в очереди задач в диспетчере, где задачи добавляются как в главном цикле, так и в прерываниях.
Как уже упоминалось раньше, размер буфера должен быть степенью двойки, однако сейчас это отдано на откуп того, кто его использовать. Сейчас, если создать буфер неправильного размера, программа скомпилируется, но будет не правильно работать. Нужно чтобы, при попытке создания буфера неправильного размера программа не компилировалась, желательно с понятным сообщением об ошибке. Здесь нам в помощь такая штука, как Static Assert (статическое утверждение). Это такой макрос, который принимает в качестве параметра логическое выражение, вычисляемое во время компиляции. Если это выражение истинно, то Static Assert никак не влияет на дальнейшую компиляцию и не генерируют никакого машинного кода. Если-же переданное выражение ложно — компиляция оборвётся с сообщением об ошибке. Простейшая реализация статического утверждения, работающего как для С++, так и для чистого Си, выглядит так:

#define CONCAT2(First, Second) (First ## Second)
#define CONCAT(First, Second) CONCAT2(First, Second)
#define STATIC_ASSERT(expr) typedef char CONCAT(static_assert_failed_at_line_, __LINE__) [(expr) ? 1 : -1]

Здесь если параметр макроса истина, создается псевдоним для массива единичной длинны. Если ложь — псевдоним для массива отрицательной длины, что приводит к ошибке компиляции. Макросы CONCAT служат для генерации уникального имени для этого псевдонима на основе текущей строки.
А как теперь определить, является ли переданная в наш шаблон буфера длина степенью двойки? Есть очень простой способ: выражение SIZE&(SIZE-1) должно быть равно нулю, почему это так, легко понять взглянув на двоичное представление степеней двойки и степень двойки минус единица.
Добавим теперь эту проверку в шаблон:

...
template<int SIZE, class DATA_T=unsigned char>
class RingBuffer
{
STATIC_ASSERT((SIZE&(SIZE-1))==0);//SIZE must be a power of 2
public:
...

Теперь создать буфер неправильного размера нельзя. Однако у нас остался еще простор для творчества. В большинстве случаев КБ будут иметь небольшой размер и должно хватить 8 разрядных индексов, а сейчас они всегда 16 разрядные. Можно конечно передавать тип данных для хранения индексов в виде отдельного параметра шаблона, но это не удобно и не спортивно, гораздо лучше, чтобы этот тип автоматически определялся исходя из размера буфера. Для этого воспользуемся приёмами шаблонного метапрограммирования. Эта конструкция осуществляет выбор типа по логическому условию:

	// condition - логическое условие
	// TypeIfTrue - тип возвращаемый, если условие истинно,
	// TypeIfFale - тип возвращаемый, если условие ложно,
	template<bool condition, class TypeIfTrue, class TypeIfFale>
	struct StaticIf
	{
		typedef TypeIfTrue Result;
	};

	template<class TypeIfTrue, class TypeIfFale>
	struct StaticIf<false, TypeIfTrue, TypeIfFale>
	{
		 typedef TypeIfFale Result;
	};

Результат получаем (КО нам подсказывает) в виде псевдонима Result.
Теперь напишем шаблон, который в зависимости от потребной длины буфера, будет отдавать нужный тип для индексов:

	template<unsigned size>
	struct SelectSizeForLength
	{
		static const bool LessOrEq8 = size <= 0xff;
		static const bool LessOrEq16 = size <= 0xffff;

		typedef typename StaticIf<
		// если поместится в 8 бит - вернем uint8_t
				LessOrEq8,
				uint8_t,
		// поместится в 16 бит - вернём - uint16_t, иначе - uint32_t
				typename StaticIf<LessOrEq16, uint16_t, uint32_t>::Result>
				::Result Result;
	};

Вставим определялку типа в исходный шаблон буфера:

template<int SIZE, class DATA_T=unsigned char>
class RingBuffer
{
STATIC_ASSERT((SIZE&(SIZE-1))==0);//SIZE must be a power of 2
public:
typedef typename SelectSizeForLength<SIZE>::Result INDEX_T;

Теперь буфером можно пользоваться (пример компилировался avr-gcc):

// буфер на 16 элементов по умолчанию - unsigned char
RingBuffer<16> buf;
…
// запишем значение из PORTB
buf.Write(PORTB);
// и прочитаем  в PORTA
uint8_t v;
buf.Read(v);
PORTA = v;

Для чтения из буфере генерируется примерно такой ассемблерный листинг:

// buf.Read(v);
lds	r25, 0x0071
lds	r24, 0x0070
cp	r25, r24
breq	.+24

lds	r24, 0x0070
mov	r30, r24
ldi	r31, 0x00
andi	r30, 0x0F
andi	r31, 0x00
subi	r30, 0xA0
sbci	r31, 0xFF
ld	r30, Z
subi	r24, 0xFF
sts	0x0070, r24
// PORTA = v;
out	0x1b, r30	; 27

Неплохо. Здесь есть одна лишняя инструкция, но компилятор от нее избавится, к сожалению, не может.
Теперь пример посерьёзней. USART на прерываниях с кольцевыми буферами на прием и передачу.



#ifdef URSEL
enum{ursel = 1 << URSEL};
#else
enum{ursel = 0};
#endif
// Макрос создает класс обёртку вокруг регистра, чтобы его можно было передать 
// как параметр шаблону.
#define IO_REG_WRAPPER(REG_NAME, CLASS_NAME, DATA_TYPE) \
	struct CLASS_NAME\
	{\
		typedef DATA_TYPE DataT;\
		static DataT Get(){return REG_NAME;}\
		static void Set(DataT value){REG_NAME = value;}\
		static void Or(DataT value){REG_NAME |= value;}\
		static void And(DataT value){REG_NAME &= value;}\
		static void Xor(DataT value){REG_NAME ^= value;}\
		static void AndOr(DataT andMask, DataT orMask){REG_NAME = (REG_NAME & andMask) | orMask;}\
		template<int Bit>\
		static bool BitIsSet(){return REG_NAME & (1 << Bit);}\
		template<int Bit>\
		static bool BitIsClear(){return !(REG_NAME & (1 << Bit));}\
	}

// создает классы-обёртки для всех регистров USART
#define DECLARE_HW_USART(ClassName, UDR_Reg, UCSRA_Reg, UCSRB_Reg, UCSRC_Reg, UBRRL_Reg, UBRRH_Reg)\
struct ClassName\
{\
	IO_REG_WRAPPER(UDR_Reg, Udr, uint8_t);\
	IO_REG_WRAPPER(UCSRA_Reg, Ucsra, uint8_t);\
	IO_REG_WRAPPER(UCSRB_Reg, Ucsrb, uint8_t);\
	IO_REG_WRAPPER(UCSRC_Reg, Ucsrc, uint8_t);\
	IO_REG_WRAPPER(UBRRL_Reg, Ubrrl, uint8_t);\
	IO_REG_WRAPPER(UBRRH_Reg, Ubrrh, uint8_t);\
};
// если у нас один USART
#ifdef UDR //the one usart
DECLARE_HW_USART(Usart0Regs, UDR, UCSRA, UCSRB, UCSRC, UBRRL, UBRRH)
#endif
// если два
// для первого
#ifdef UDR0 //first usart
DECLARE_HW_USART(Usart0Regs, UDR0, UCSR0A, UCSR0B, UCSR0C, UBRR0L, UBRR0H)
#endif
// для второго
#ifdef UDR1 //second usart
DECLARE_HW_USART(Usart1Regs, UDR1, UCSR1A, UCSR1B, UCSR1C, UBRR1L, UBRR1H)
#endif

// TxSize - размер буфера передачи
// RxSize - размер буфера приёма
// Regs тип в котором определены классы обёртки регистров USART
template<int TxSize, int RxSize, class Regs=Usart0Regs>
class Usart
{
public:
	static inline void EnableTxRx()
	{
		Regs::Ucsrb::Set(0x00); 
		Regs::Ucsrc::Set(ursel | (1 << UCSZ1) | (1 << UCSZ0));
		Regs::Ucsrb::Set( (1 << RXCIE) | (0 << TXCIE) | (1 << UDRIE) | (1 << RXEN) | (1 << TXEN));
	}

	template<unsigned long baund>
	static inline void SetBaundRate()
	{
		const unsigned int ubrr = (F_CPU/16/baund-1);
		const unsigned int ubrr2x 	(F_CPU/8/baund-1);
		const unsigned long rbaund = (F_CPU/16/(ubrr+1));	
 		const unsigned long rbaund2x (F_CPU/8/(ubrr2x+1));

		unsigned long err1;
		if(baund > rbaund)
			err1 = (baund - rbaund)*1000/baund;
		else
			err1 = (rbaund - baund)*1000/rbaund;

		unsigned long err2;
		if(baund > rbaund2x)
			err2 = (baund - rbaund2x)*1000/baund;
		else
			err2 = (rbaund2x - baund)*1000/rbaund2x;

		unsigned int ubrrToUse;
		if(err1 > err2)
		{
			Regs::Ucsra::Set(1 << U2X);
			ubrrToUse = ubrr2x;
		}
		else
		{
			Regs::Ucsra::Set(0x00);
			ubrrToUse = ubrr;
		}
		Regs::Ubrrl::Set(ubrrToUse);
		Regs::Ubrrh::Set(ubrrToUse>>8);
	}

	template<unsigned long baund>
	static inline void Init()
	{
		SetBaundRate<baund>();
		EnableTxRx();
	}
// отправить байт
// возвращает true если байт записан в буффер или отправлен,
// если буфер полон - false
	static bool Putch(uint8_t c)
	{
		if(_tx.IsEmpty())
		{
			while(!Regs::Ucsra::template BitIsSet<(UDRE)>() );
			Regs::Udr::Set(c);
			Regs::Ucsrb::Or(1 << UDRIE);
			return true;
		}else 
		return _tx.Write(c);
	}
// прочитать байт
// возвращает true если байт прочитан
	static bool Getch(uint8_t &c)
	{
		return _rx.Read(c);
	}
// обработчик преравания по передачи байта
// должен вызываться из USART_UDRE_vect
	static inline void TxHandler()
	{
		uint8_t c;
		if(_tx.Read(c))
			Regs::Udr::Set(c);
		else
			Regs::Ucsrb::And( ~(1 << UDRIE) );
	}
// обработчик преравания по приёму байта
// должен вызываться из USART_RXC_vect
	static inline void RxHandler()
	{
		if(!_rx.Write(Regs::Udr::Get() ))//buffer overlow
		{
			//TODO: error handling
			_rx.Clear();
		}	
	}

	static void DropBuffers()
	{
		_rx.Clear();
	}

	static void Disable()
	{
		Regs::Ucsra::Set(0);
		Regs::Ucsrb::Set(0);
		Regs::Ucsrc::Set(ursel | 0);
		Regs::Ubrrl::Set(0);
		Regs::Ubrrh::Set(0);

		_rx.Clear();
		_tx.Clear();
	}

	static uint8_t BytesRecived()
	{
		return _rx.Count();
	}
private:
	static RingBuffer<RxSize> _rx;
	static RingBuffer<TxSize> _tx;
};

template<int TxSize, int RxSize, class Regs>
	RingBuffer<RxSize> Usart<TxSize, RxSize, Regs>::_rx;
template<int TxSize, int RxSize, class Regs>
	RingBuffer<TxSize> Usart<TxSize, RxSize, Regs>::_tx;


Пример программы, использующей класс Usart:

// 8 bytes tx fifo buffer, 
// 16 bytes rx fifo buffer
// interrupt driven USART
typedef Usart<16, 16> usart;

ISR(USART_UDRE_vect)
{	
	usart::TxHandler();
}

ISR(USART_RXC_vect)
{
	usart::RxHandler();
}

int main()
{
	usart::Init<115200>();
	uint8_t c;
	while(1)
	{	
		// echo recived data back
		if(usart::Getch(c))
			usart::Putch(c);
	}
}

Посмотрим какой ассемблерный листинг сгенерировал компилятор, например, для прерывания USART_RXC_vect:

push	r1
push	r0
in	r0, 0x3f
push	r0
eor	r1, r1
push	r18
push	r24
push	r25
push	r30
push	r31
in	r18, 0x0c

lds	r24, 0x0071
lds	r25, 0x0070
sub	r24, r25
andi	r24, 0xF0
brne	.+26

lds	r24, 0x0071
mov	r30, r24
ldi	r31, 0x00
andi	r30, 0x0F
andi	r31, 0x00
subi	r30, 0xA0
sbci	r31, 0xFF
st	Z, r18
subi	r24, 0xFF
sts	0x0071, r24
rjmp	.+8

sts	0x0070, r1
sts	0x0071, r1

pop	r31
pop	r30
pop	r25
pop	r24
pop	r18
pop	r0
out	0x3f, r0
pop	r0
pop	r1
reti

Всё компилятор всё оптимизировал лучшим образом — нет вызовов функций, всё встроено непосредственно в сам обработчик, используется минимум регистров. При этом программа осталась модульной и хорошо читаемой.
Размер машинного кода для этого примера 414 байт для МК AtMega16, компилятор avr-gcc 4.3.

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

Исходник к статье

  • +5
  • 13 марта 2011, 01:04
  • neiver

Комментарии (71)

RSS свернуть / развернуть
Круто. Правда, чтобы эффективно юзать С++ для МК — его надо очень хорошо знать)
Код правда не столь уж просто понять, надо быть более-менее прожженым сишником.

Вопросы.
1) Зачем макрос CONCAT? Что мешает использовать сразу CONCAT2?
2) Почему RingBuffer? Буржуи ж его Circular называют.

>TypeIfFale
False.
Ну и Baud/Baund.
0
  • avatar
  • Vga
  • 13 марта 2011, 01:45
А вы попробуйте сами сразу и поймете в чем разница :)
Baud верно вроде как
0
И правда. Но меня же интересует с объяснением, почему так получается.
0
По препроцессору Си можно очень много написать — не одну статью, а так между прочим сложно все расписать.
0
Но на один-то конкретный вопрос ответить можно.
0
если в CONCAT2 передать одним из параметров другой макрос, то он не развернется полностью
т.е. (утрировано)

#define str1 hello
#define str2 world
CONCAT2(str1,str2) => str1str2
CONCAT(str1,str2) => helloworld

как-то так вроде
0
нет, я встречал название и ring buffer
0
В приведенной статье в Википедии этот буфер называется circular buffer, cyclic buffer или ring buffer.
0
Статья полезная, правда код больше подойдет для копи-паста в проект, ибо шаблоны не самая простая тема для «новичков C++».

По поводу степеней двойки могу сказать что на контроллерах оно не стоит того. Когда сравнивал ассемблерные коды, разницы от наложения маски и условного перехода (с учетом неверного предсказания перехода и сбросом конвеера) не нашел. А вот ограничения на размер получаем явные. Так если надо иметь «запас» в 40 байт, мы обязаны использовать буффер в 64 байта, и получим заюзанные в пустую 24 байта.
Да, памяти сейчас много, 2к есть на борту — нам хватит, а что если «запас» должен быть 550байт? А вот для компа да — там разница в производительности небо и земля, а лишнего килобайта не жалко.

P.S.: а почему в столь универсальном классе и не добавили возможность аппаратного контроля передачи?
0
Уважаемый neiver!
Как в шаблоне задать тип элементов хранящихся в буфере, отличный от unsigned char?
С уважением. Спасибо.
0
RingBuffer<16, int>
0
Вспомнил. Параметр class это же любой тип. Спасибо.
0
template<int TxSize, int RxSize, class Regs>
        RingBuffer<TxSize> Usart<TxSize, RxSize, Regs>::_tx;

Поясните пожалуйста, что это за конструкция. Это шаблон чего?
Т.е. при конкретизации данного шаблона создается переменная буфера, член класса Usart? Где точка конкретизации? Спасибо.
0
Это обычный способ оределения статических переменных-членов шаблонов. Поскольку это определение должно находится вне объявления класса, для него тоже нужно указывать список шаблонных параметров.
Не сильно отличается от определения статической переменной в обычном классе.
template<int TxSize, int RxSize, class Regs>// список параметров шаблона
        RingBuffer<TxSize> // тип статической переменной(зависит от параметра TxSize)
        Usart<TxSize, RxSize, Regs> // полностью квалифицированное имя шаблона
        ::_tx; // имя статической переменной
0
Еще один вопрос. Если тип данных в буфере отличный от «по умолчанию», как будет выглядеть конкретизация шаблона
Usart<16, 16> usart;
, где этот параметр? Спасибо.
0
Конкретно в этом примере, тип данных в буфере всегда по умолчанию. И соответствующего параметра нет, чтоб не загромождать код лишними деталями. Однако его легко ввести в этот шаблон:
template<int TxSize, int RxSize, class Regs=Usart0Regs, class DataT=unsigned char>
class Usart
...
static bool Putch(DataT c)
...
static bool Getch(DataT &c)
...
private:
        static RingBuffer<RxSize, DataT> _rx;
        static RingBuffer<TxSize, DataT> _tx;
};

template<int TxSize, int RxSize, class Regs, class DataT>
        RingBuffer<RxSize, DataT> Usart<TxSize, RxSize, Regs, DataT>::_rx;
template<int TxSize, int RxSize, class Regs, class DataT>
        RingBuffer<TxSize, DataT> Usart<TxSize, RxSize, Regs, DataT>::_tx;

Конкретизация будет выглядеть так:
Usart<16, 16, Usart0Regs, signed char> usart;
0
А как правильно определить статическую переменную не шаблон?
0
В смысле статическую переменную-член не шаблонного класса?
Как-то так:

// файл foo.h
class Foo
{
    static int bar;
};
...
// файл foo.cpp
int Foo::bar = 100;
0
Я имел в виду такое —

template<int Var>
class Box
...
static void Func (void)
...
private:
        <em>static uint8 Flags;</em>
};

И по аналогии с вашей записью наверное нужно дописать:
template<int Var> uint8 Box<Var>::Flags;

Верна ли такая запись?
0
Вполне.
0
Еще вот такой общий вопрос. Возможно вам покажется, что ответ слишком очевиден, но как говорится «поднявшись на гору, окрестности видны как на ладони...» Возможно кому-то из идущих тоже поможет.
В каких случаях уместно использовать статический класс, т.е. не создавая экземпляр класса, а в каких рациональнее идти «класическим» способом — объявляем класс, создаем экземпляр класса. Или вся «фишка» именно в статике (применительно к эмбед)?
0
Общее правило примерно такое:
если у некой сущьности (класса) может быть множество объектов, то это будет обычный класс. Если же может быть только один объект, или создание объекта вообще бессмысленно, то вероятно это должен быть «статический» класс. Хотя в программировании «больших» компьютеров в последнем случае обычно применяют паттерн проектирования «одиночка», а вот эмбед всё-таки уместнее «статический» класс по причинам производительности.
А вообще основная фишка «статических» классов в том, что их можно использовать как параметры шаблонов, что позволяет использовать некоторые эффективные приёмы программирования.
0
А и правда ведь. Хотя если мы забулдырили шаблон, то скорей всего один экземпляр и надо. Интересно, намного-ли отличается размер кода «статического» класса и аналогичного, но с объектом?
0
Это зависит от целевой платформы и от компилятора. Например, avr-gcc при работе со статическими данными чаще использует четырёх-байтные команды lds/sts, а при работе с экземплярами классов к данным обращается через указатель this и использует команды ld/st. Получается, работа со статическими данными чуть быстрее, но размер кода чуть больше. Компилятор IAR в обоих случаях использует команды ld/st и размер кода почти одинаковый.
0
typedef RingBuffer <4, unsigned int> RingBufferRX0;
RingBufferRX0::Write(2);

Почему то при вызове любой функции выдает ошибку (компилятор IAR)
Error[Pe245]: a nonstatic member reference must be relative to a specific object
0
Это потому, что нужно создать объект буффера, это не «статический» класс.
RingBuffer <4, unsigned int> RingBufferRX0;
RingBufferRX0.Write(2);

В статье-же есть пример использования.
0
Ага… Действительно, «проскакал пришпорив...».
А теперь вот на это:
inline const DATA_T operator[] (INDEX_T i)const
        {
                if(IsEmpty())
                   return DATA_T();
                return Data[(ReadCount + i) & Mask];
        }

Выдает это:
Error[Pe1086]: the object has cv-qualifiers that are not compatible with the member function «RingBuffer<SIZE, DATA_T>::IsEmpty»
Если убрать const
inline const DATA_T operator[] (INDEX_T i)const
inline const DATA_T operator[] (INDEX_T i)
то компилируется.
0
IsEmpty у вас почему-то не имеет модификатора const по этому не может вызываться в методе с таковым модификатором. Проверьте описание, должно быть:
inline bool IsEmpty()const
0
И функции
inline DATA_T& operator[] (INDEX_T i)
inline const DATA_T operator[] (INDEX_T i)

не дает перегружать.
Error[Pe311]: cannot overload functions distinguished by return type alone
0
и не даст. Внимательно списываем с поста:
inline const DATA_T operator[] (INDEX_T i)const
0
Убрал свою самодеятельность и все заработало.
Спасибо за ответы. А язык будем учить. С++ того стоит.
Спасибо neiverу за статьи по С++ для встр. систем, очень дельно.
Завораживают Ваши манипуляции с этим поистине могучим инструментом.
Ждем еще. Удачи!
0
О да. Паскаль/Дельфи конечно чистый и приятный язык, но такие фокусы там не сделать даже с выходом Delphi 2009 (в которой ввели генерики).
0
реализации перегруженных операторов
inline DATA_T& operator[] (INDEX_T i)
и
inline const DATA_T operator[] (INDEX_T i)const

отличаются поведением, при i > Count() это так надо? или это баг.
0
  • avatar
  • XIX
  • 31 июля 2011, 13:48
Это особенность реализации. В принципе обе версии должны быть одинаковыми. Наглядный пример вреда копипасты.
0
Объясните пожалуйста принцип работы функции isFull. По моим подсчетам она будет возвращать true всегда, когда счетчик на чтение больше счетчика на запись, так? Тогда смысл от нее? Возможно я туплю, поправьте если не так.
0
  • avatar
  • porex
  • 16 сентября 2011, 15:58
Нет, true будет только когда, беззнаковая разница счетчиком на запись и счетчиком на чтение будет больше размера буфера. С учетом, что счетчики проворачиваются через ноль. В общем, она работает так, как если бы было написанно так:
inline bool IsFull()const
{
     return (_writeCount - _readCount) > SIZE;
}

Но приведённый в статье выриант более эффективен, хотя и более сложен для понимания. Можите скомпилировать оба варианта и посмотреть чем они отличаются в ассемблерном листинге.
0
Спасибо, разобрался! Я думал, что после превышения размера буфера счетчики сбрасываются.
0
вот моя реализация на макросах:
#define RBUF_DECLARE( buf_type, buf_name, buf_count) \
	struct { \
		buf_type *rd; \
		buf_type *wr; \
		buf_type buf[buf_count]; \
	} buf_name

#define RBUF_INIT( buf_ptr )  { (buf_ptr)->rd = (buf_ptr)->wr = &(buf_ptr)->buf[0]; }
#define RBUF_SIZE( buf_ptr )  ( sizeof((buf_ptr)->buf) )
#define RBUF_COUNT( buf_ptr ) ( sizeof((buf_ptr)->buf) / sizeof((buf_ptr)->buf[0]) )
#define RBUF_START( buf_ptr ) ( &(buf_ptr)->buf[0] )
#define RBUF_END( buf_ptr ) ( &(buf_ptr)->buf[ RBUF_COUNT(buf_ptr) - 1 ] )
#define RBUF_EMPTY( buf_ptr ) ( (buf_ptr)->rd == (buf_ptr)->wr )

#define RBUF_WR( buf_ptr, data  ) { *((buf_ptr)->wr) = data; ((buf_ptr)->wr)++; if ((buf_ptr)->wr > RBUF_END(buf_ptr)) (buf_ptr)->wr = RBUF_START(buf_ptr); }
#define RBUF_RD( buf_ptr  ) *((buf_ptr)->rd); ((buf_ptr)->rd)++; if ((buf_ptr)->rd > RBUF_END(buf_ptr)) (buf_ptr)->rd = RBUF_START(buf_ptr)
0
В RBUF_WR нет проверки на переполнение — может перезаписывать ещё не прочитанные данные.
В RBUF_RD нет проверки на наличие в буфере непрочитанных данных — может повторно вычитывать то, что уже было прочитано.
RBUF_RD вообще очень кучерявый макрос. Исполльзовать его нужно очень осторожно и всегда помнить во что именно он разворачивается. Например:
if(RBUF_RD(buffer) == 'A') {...}
char c = RBUF_RD(buffer), c2 = 0;

Выглядит корректно, если бы RBUF_RD был обычной функцией, но компилироваться не будет.
Вобщем этот макрос можно употредлять исключительно в одиночном операторе присваивания.
0
В RBUF_WR нет проверки на переполнение… В RBUF_RD нет проверки на наличие
нет, но если корректно работать (не допускать переполнения и вовремя считывать — то проверок не нужно
всегда помнить во что именно он разворачивается
угу, а шо поделать ?
if(RBUF_RD(buffer)
так низзя — кроме собственно считывания происходит инкремент указателя, поэтому считывать нужно в промежуточную переменную. Можно сделать дополнительтый макрос считывания без инкремента, тогда такой синтаксис прокатит.
0
Во-о-о-т! :)
0
как-то так:
//declares ring buffer buf_type with elements type buf_type and count buf_count
#define RBUF_DECLARE( buf_name, buf_type, buf_count) \
	struct { \
		buf_type *rd; \
		buf_type *wr; \
		buf_type buf[buf_count]; \
	} buf_name

//returns pointer to first element
#define RBUF_START( buf_ptr ) ( &(buf_ptr)->buf[0] )
//returns pointer to last element
#define RBUF_END( buf_ptr ) ( &(buf_ptr)->buf[ RBUF_COUNT(buf_ptr) - 1 ] )
//initializes read and write pointers
#define RBUF_INIT( buf_ptr )  { (buf_ptr)->rd = (buf_ptr)->wr = RBUF_START(buf_ptr); }
//returns buffer suze
#define RBUF_SIZE( buf_ptr )  ( sizeof((buf_ptr)->buf) )
//returns elements count
#define RBUF_COUNT( buf_ptr ) ( sizeof((buf_ptr)->buf) / sizeof((buf_ptr)->buf[0]) )
//checks if buffer is empty
#define RBUF_EMPTY( buf_ptr ) ( (buf_ptr)->rd == (buf_ptr)->wr )

//increment read pointer
#define RBUF_INC_RD(buf_ptr) { ((buf_ptr)->rd)++; if ((buf_ptr)->rd > RBUF_END(buf_ptr)) (buf_ptr)->rd = RBUF_START(buf_ptr); }
//read without increment
#define RBUF_GET(buf_ptr) (*((buf_ptr)->rd))
//read with increment
#define RBUF_RD( buf_ptr  ) RBUF_GET(buf_ptr); RBUF_INC_RD(buf_ptr);

//increment write pointer
#define RBUF_INC_WR(buf_ptr) { ((buf_ptr)->wr)++; if ((buf_ptr)->wr > RBUF_END(buf_ptr)) (buf_ptr)->wr = RBUF_START(buf_ptr); }
//write last element without increment
#define RBUF_SET(buf_ptr, data) *((buf_ptr)->wr) = data;
//write to buffer with increment
#define RBUF_WR( buf_ptr, data  ) { RBUF_SET(buf_ptr, data); RBUF_INC_WR(buf_ptr); }
//write string str to buffer, write0==TRUE to write last '0'
#define RBUF_WR_STR( buf_ptr, str, write0 ) { \
	for (U8 *s1=(U8 *)str; *s1!=0; s1++) RBUF_WR( buf_ptr, *s1 ); \
	if (write0) RBUF_WR( buf_ptr, 0 ); \
}
0
Чтобы снять ограничение на размер буфера, можно вместо маски использовать деление по модулю.
Правда, это немного менее эффективно, но вроде бы совсем немного.
0
Деление на avr — это больше 100 тактов. Эта на Кортексах деление аппаратное за пару тактов — там можно.
Лучше тогда как писал reptile в примере выше делеать проверку на «проворачивание» буфера при каждой операции. Но это опять-же медленнее чем в моём примере. У меня здесь пример именно максимально быстрого буфера, но с ограничением на размер.
0
Блин, пардон. Совсем меня на кортексах заклинило.

А вот не подскажите ли, как по-человечески в такой буфер добавлять не по одному байту, а сразу помногу?
0
Конкретно в этот буфер примерно так:
inline int Write(DATA_T *buffer, unsigned size)
{
   unsigned count = min(Count(), size);
   for(unsigned i=0; i<count; i++)
      _data[_writeCount++ & _mask] = buffer[i];
   return count;
}
0
То есть, фактически, побайтно?
0
Поэлементно. Можно еще разбить задачу копирования на две: копирование от текущей позиции до конца буфера и копирование от начала буфера и до сколько осталось. И использовать для копирования memcpy. Это будет быстрее для достоточно больших буферов как минимум в сотни элементов.
0
Понятно, спасибо. Я смутно надеялся, что есть какой-то третий способ.
0
Деление на avr — это больше 100 тактов
Деление на переменную — да.
Деление на константу весьма оптимизируется компилятором.
0
Деление беззнаковых переменных на степени двойки — да. На произвольные константы в общем случее — нет.
Если есть возможность, пусть лучше компилятор во время компиляции поделит и в объектный код попадёт уже результат.
0
Это я почему-то с умножением на константу перепутал. Совсем забыл, что в нашем веке компиляторы сами не умеют ещё.
Ссылка — первая попавшаяся нагуглиная.
0
В функции inline DATA_T& operator[] (INDEX_T i) при некорректном индексе выполняется возврат временного объекта:
return DATA_T();
Но он же, по идее — константен. Нет ли здесь ошибки? Мой компилятор выдает
"… initial value of reference to non-const must be an lvalue"
0
Вы совершенно правы — это грабли, которые могут стукнуть по лбу. Так нормально:
if(buffer[index_out_of_range] == 0)
...

А вот так граблями по лбу:
BufferElemT &ref = buffer[index_out_of_range];
do_something(ref);

Я некоторое время назад полностью переписал этот кольцевой буфер.
Возможно, лучше совсем проверку на выход индекса за границы буфера убрать. Всё равно пределы буфера не выйдет — будет просто проворачиваться.
0
Корректно ли в качестве обертки для регистров UART использовать структуру, содержащую ссылку на структуру регистров UART? Выглядит проще:
struct uart1_regs_wrapper {
	static volatile UART_REGS_T &uart_regs;
};
volatile UART_REGS_T &uart1_regs_wrapper::uart_regs = *UART1;
0
Вполне корректно. Только надо убедиться, что компилятор генерирует при этом более-менее оптимальный код. Компилятор может не оптимизировать ссылку и реализовать её посредствам указателя, в этом случае при обращении к регистрам будет лишнее чтение из памяти(этого указателя) и косвенное обращение к регистрам. Хотя на ARM-ах это не критично — всего несколько лишних тактов.
Когда регистры периферии упорядочены в структуру, я обычно использую такую обёртку:
#define IO_STRUCT_WRAPPER(STRUCT_PTR, CLASS_NAME, STRUCT_TYPE) \
struct CLASS_NAME\
{\
	typedef STRUCT_TYPE DataT;\
	STRUCT_TYPE* operator->(){return ((STRUCT_TYPE *)(STRUCT_PTR));}\
}

IO_STRUCT_WRAPPER(USART1, Usart1, UsartRegsStruct);
template<class Regs>
class Usart
{
...
void Foo()
{
    Regs()->SomeRegName = Something;
}
...
};

Здесь косвенное обращение к регистрам по указателю исключено.
0
Проверил. Действительно с моим вариантом получалось лишнее чтение указателя, а в вашем случае все оптимально.
0
В текущей версии буфера (которая на гитхабе) насколько я понял все же используются критические секции, а _writeCount, _readCount не volatile, здесь — наоборот. Почему решили изменить? Оба варианта безопасны при условии одного писателя и одного читателя?
0
В новой версии по умолчанию не используются критические секции, там есть возможность их подсунуть если надо. Тип Atomic по умолчанию является VoidAtomic, который просто читает-пишет по указателю без критической секции. Однако его можно заменить на платформо-зависимый Atomic с критической секцией. В случае одного читателя и одного писателя из разных потоков (прерывания) без использования критическихсекций оба варианта безопасены пока индексы _readCount и _writeCount обнобайтные. Для двух-байтных индексов по-хорошему должны использоваться критический секции. В противном случае возможны ситуации, когда IsEmpty() и IsFull() ложно возвращают true, вернуть ложно false они не могут. По этому обычно ошибок это не вызывает.
0
Да, и почему в новой версии в pop_front() просто удаляете элемент без возврата значения?
0
Для совместимости с STL.
0
Не могли бы подсказать ли по одному вопросу?
Дело в том, что я недавно посмотрел в примеры, идущие к lpc11xx (uart) и увидел там следующее:

volatile uint8_t  UARTTxEmpty = 1;
volatile uint8_t  UARTBuffer[BUFSIZE];
volatile uint32_t UARTCount = 0;

Необходимо ли объявлять UARTBuffer как volatile-переменную?
Предполагается что UARTBuffer пишется в прерывании и читается в основной программе?

Спасибо.
0
Желательно. Но скорее для душевного спокойствия. Если объявить буфер без volatile, то работать будет точно также потому, что компиляторы обычно не кешируют в регистрах содержимое глобальных массивов (в отличии от скалярных переменных).
0
Не поделитесь опытом, есть ли резон использования контейнеров STL в проектах для МК? Насколько они тяжелы, избыточны?
0
В большинстве сдучаев STL тяжелы и избыточны, в первую очередь из-за динамичаского распределения памяти, со всеми вытекающеми. А вот легковесный колцевой буфер со статически выделенной памятью другое дело. А интерфейс как у STL контейнеров — для привычности и единообразия.
А если памяти много и нежалко, то можно и STL.
0
Нагуглил облегченную STL: uSTL, возможно, как-нибудь поэкспериментирую.
Насчет динамического распределения памяти: так ли это страшно неэффективно? В этой статье для возможности задания различного размера буфера у разных экземпляров вы используете шаблоны. Но шаблоны могут быть нежелательны, если: класс содержит значительный объем кода (насколько я понимаю, код целиком будет дублироваться для разных специализаций класса, т.е. для экземпляров с разным размером буфера), либо если необходимо, чтобы экземпляры имели одинаковый тип. Как поступают в таких случаях? Выглядит логичным выделять память динамически. К каким проблемам это может привести?
Мне также показалось, что использование шаблонов для задания размера буфера несколько ограничивает применение приведенного в статье модуля: классы использующие этот буфер также должны быть шаблонными, чтобы сохранить возможность задания размерности, что может быть нежелательным по перечисленным причинам. Это компромисс (производительность/универсальность), или то, что я посчитал проблемой легко решаемо?
0
Насчет динамического распределения памяти: так ли это страшно неэффективно?
Не обязательно. У динамического выделения памяти есть несколько проблем специфичных для МК: а) (как правило) маленький объем оперативной памяти, б) возможность (легко, а главное — неожиданно) создать ситуацию нехватки памяти, что приведет к отказу устройства, в) код использующий динамическое распределение памяти может иметь плавающее время выполнения, что крайне нежелательно если этот код отвечает за реакцию на событие. Если есть уверенность, что (б) не возникнет, а (а) и (в) не критичны, то вполне можно использовать и динамическое распределение памяти.
0
Мне кажется, код будет работать не совсем, как ожидалось, а точнее буфер передачи(_tx) не используется вообще.

static bool Putch(uint8_t c)
{
    if(_tx.IsEmpty()) //сначала tx пустой
    {
	while(!Regs::Ucsra::template BitIsSet<(UDRE)>() );
	Regs::Udr::Set(C);
	Regs::Ucsrb::Or(1 << UDRIE);
	return true; 
        //здесь мы нигде не записывали в tx, 
        //следовательно он продолжает быть пустым, при последующем вызове этой функции
    }else
    {
        //этот код никогда не выполнится
  	return _tx.Write(C);
    }
}


Возможное решение:

static volatile bool DataIsSending=false;
static bool Putch(uint8_t c)
{
    ATOMIC_BLOCK(ATOMIC_RESTORESTATE) if(!DataIsSending)
    {
	Regs::Udr::Set(C);
	Regs::Ucsrb::Or(1 << UDRIE);
        DataIsSending=true;
	return true;
    }
    else
    {
        return _tx.Write(C);
    }
}
static inline void TxHandler()
{
    uint8_t c;
    if(_tx.Read(C))
        Regs::Udr::Set(C);
    else
    {
        DataIsSending=false;
        Regs::Ucsrb::And( ~(1 << UDRIE) );
    }
}

Блокировка нужна для следующей ситуации: буфер пустой, один байт отсылается; мы вызвали функцию Putch, DataIsSending равно false, во время выполнения _tx.Write(C) байт отослался и произошло прерывание.
В итоге получим состояние когда прерывание UDRIE отключено, а в буфере хранится 1 байт. При последующих вызовах функции будет нарушен порядок передачи байтов.
0
Да, похоже так.
0
Эта конструкция, при заполненном буфере, возвращает ноль
// количество элементов в буфере
        INDEX_T Count()const
        {
                return (_writeCount - _readCount) & _mask;
        }

Может быть надо так?
// количество элементов в буфере
        INDEX_T Count()const
        {
                return (_writeCount - _readCount) & (_mask | SIZE);
        }
0
Немного не по теме но всёже (создание буфера, нужного имеми, нужного размера и нужного типа), есть недочёты но всёже:

#define CREATION_FIFO_BUF( name_buf, size_buf,type )  \
  static type buf_##name_buf[size_buf];       \
  struct{type const *val_tx;Uint16 back;Uint16 font;Uint16 count;Uint16 const size;}name_buf = { &buf_##name_buf[0], 0, 0,0,size_buf }
0
  • avatar
  • CHIP
  • 31 августа 2017, 16:51
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.