Реализация кольцевого буфера на ассемблере AVR

AVR
Для очередного эксперимента понадобился мне такой вот буфер. Что это такое, можно почитать в Википедии, а также здесь, поэтому углубляться не буду.
Оговорки:
  1. я не профессиональный программист и наверное им не стану, поэтому возможно, что нижеприведенное потребует оптимизации/переработки;
  2. на Сях и прочих высокоуровневых языках не пишу — не умею;
  3. долго искать готовое решение на ассемблере не стал, а изобретать колесо вроде как и не запрещено (хоть иногда и глупо), зато интересно.
Ниже будет краткое описание того, что я наделал.

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

Итак, что необходимо:
КАК МИНИМУМ — несколько байт в оперативной памяти и два указателя. Один указывает куда будем заносить очередной элемент, назовем его IP (Input Pointer); второй указывает откуда будем брать следующий элемент, его назовем OP (Ouput Pointer). Очень важно следить за тем, чтобы эти указатели не выходили за пределы выделенной под КБ области памяти. Т.е. при достижении указателем конечного значения выделенной области присваивать ему начальное значение.
НО для ПОЛНОЦЕННОЙ работы КБ необходимо соблюсти еще несколько условий:
  • OP не должен обгонять IP, иначе из очереди(КБ) получим уже однажды прочитанные данные;
  • IP не должен обгонять OP, иначе из очереди(КБ) будут удалены(перезаписаны) еще неизвлеченные данные;
  • для чего нужно знать состояние КБ («пуст», «непуст/неполон», «полон»).
Для этого введем в код несколько проверок и два флага.

Определения:
; Определение регистров и памяти

.def F_1_D	= R10	; FiFo 1 Data Register
.def F_1_IP	= R11	; Input Pointer FiFo 1 = куда будем писать
.def F_1_OP	= R12	; Ouput Pointer FiFo 1 = откуда будем читать
.def Temp	= R16	; Temp-Var
.def Flag	= R25	; Flag-Register
	.equ FIFO1_L =4	; FiFo 1 пуст
	.equ FIFO1_V =5	; FiFo 1 полон

;	R26	; XL / SRAM Pointer low
;	R27	; XH / SRAM Pointer high

.dseg
FiFo1_Anf:	.byte	64	; размер кольцевого буфера FIFO 1 кратен степени двойки!

Регистры КБ выбрал преднамеренно из младшей области — на них всегда спрос меньше :)
Регистр Flag глобальный для всей программы, из него нужно только два разряда для КБ.
Размер буфера для упрощения процедур выбрал кратным степени двойки, т.е. КБ может иметь длинну 8,16,32,64,128 или 256 байт. Меньше наверное не имеет смысла, а больше не получится ввиду применения однобайтовых указателей.
В результате получим три процедуры (подпрограммы).
Почему три?
Вначале необходимо этот буфер инициализировать:
FIFO_1_INIT:;=================================== Инициализация FIFO 1
			clr F_1_IP
			clr F_1_OP
			sbr Flag, 1<<FIFO1_L	; FIFO 1 пуст
			cbr Flag, 1<<FIFO1_V	; флаг "полон" сбросить
		RET	;=================================================
Здесь все просто: указатели на начало КБ, флаги = «пуст». Инициализировать КБ нужно до его применения где-то в начале программы, например в сегменте общих инициализаций.
Кстати, указатели у нас относительные, т.е. им безразлично где в памяти лежит сам буфер. Конкретный адрес вычислим ниже.

Для заполнения буфера получится такая процедура:
FIFO_1_IN:	;=============================== добавить байт в FIFO 1
			sec
			sbrc Flag, FIFO1_V
				RET	; выход с Carry
			cbr Flag, 1<<FIFO1_L	; флаг "пуст" сбросить
			ldi	XL, low (FiFo1_Anf)	; начальный адрес FIFO 1
			ldi XH, high(FiFo1_Anf)
			add XL, F_1_IP		; вычислить текщий адрес SRAM
			clr Temp
			adc XH, temp
			st X, F_1_D			; данные в FiFo 1
			inc  F_1_IP
			ldi Temp, 0x3F		; FiFo max 64 Bytes
			and F_1_IP, Temp	; Input Pointer = новое значение
			clc
			cpse F_1_IP, F_1_OP	; догнали Ouput Pointer?
		RET
			sbr Flag, 1<<FIFO1_V	; FIFO 1 полон
		RET	;=======================================================
Здесь вначале проверяем не заполнен ли КБ под завязку, и если да, то покидаем процедуру с ошибкой (флаг Carry в SREG).
Далее говорим, что КБ не пуст, поскольку вносим в него элемент.
Вычисляем конкретный адрес в SRAM и пишем туда.
Увеличиваем значение указателя IP (входных данных) и сразу же следим за тем, чтобы он не превысил выделенного размера, т.е. закольцовывание произойдет автоматически обнулением «лишних» старших битов указателя. Понятно, что при максимальном размере КБ (256 байт) инструкции
ldi Temp, 0x3F		; FiFo max 64 Bytes
and F_1_IP, Temp	; Input Pointer = новое значение
следует удалить за ненадобностью.
В случае другого размера КБ нужно соответственно изменить значения в команде
ldi Temp, 0x3F		; FiFo max 64 
каждой из процедур (0x7F для 128, 0x1F для 32, 0x0F для 16, 0x07 для 8 байтов).

Ну и наконец проверим, не догнали ли мы OP (выходной указатель), и если да, то говорим «КБ полон!»

Для извлечения данных следующая процедура, очень похожая на предидущую :)
FIFO_1_OUT:	;================================= выбрать байт из FIFO 1
			sec
			sbrc Flag, FIFO1_L
				RET	; выход с Carry
			cbr Flag, 1<<FIFO1_V	; флаг "полон" сбросить
			ldi	XL, low (FiFo1_Anf)	; начальный адрес FIFO 1
			ldi XH, high(FiFo1_Anf)
			add XL, F_1_OP		; вычислить текщий адрес SRAM
			clr Temp
			adc XH, temp
			ld F_1_D, X			; данные из FiFo 1
			inc F_1_OP		
			ldi Temp, 0x3F		; FiFo max 64 Bytes
			and F_1_OP, Temp	; Output Pointer = новое значение
			clc
			cpse F_1_IP, F_1_OP	; догнали Input Pointer?
		RET
			sbr	Flag, 1<<FIFO1_L	; данных больше нет (флаг "пуст")
		RET	;===========================================================
Здесь все с точностью до наоборот: Проверяем КБ на наличие элементов, берем следующий, увеличиваем указатель OP, проверяем на пустоту (для соответствующего флага).

Вызов процедур возможен и из прерываний, например: при передаче в терминал вызываем FIFO_1_OUT из обработчика прерывания UDRE (регистр данных передатчика пуст). При необходимости нужно позаботиться о сохранении изменяемых регистров в стеке или в выделенных ячейках памяти. Как сделать лучше — решает каждый сам в зависимости от условий. Можно, например, абсолютный адрес КБ и указатели хранить в SRAM и подгружать их в регистры непосредственно в процедурах, однако это увеличит их размер и время выполнения.

Как видно из названия меток, буферов может быть несколько. Символьным меткам нужно тогда присвоить соответствующие порядковые номера и, естественно, выделить свои регистры и области памяти.

Работу приведенных процедур тестировал в симуляторе студии. До полной обкатки в кристале еще не дошел — меня тормозит другая часть (источник этих самых данных), о которой здесь писать нет смысла.

В приложении файл FiFo.txt с исходником вышеописанных процедур. Кому надо — пользуйтесь.
Обсуждение приветствуется.
  • +4
  • 14 апреля 2013, 17:06
  • Fahivec
  • 1
Файлы в топике: FiFo.txt

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

RSS свернуть / развернуть
Сразу бросается в глаза невозможность использования данных проццедур в прерываниях / в условиях любой другой вытесняющей системы.
1) Функция FIFO_1_OUT вызывается для получения данных и выполняет инструкцию
cbr Flag, 1<<FIFO1_V    ; флаг "полон" сбросить

2) Происходит прерывание и вызывается FIFO_1_IN, а поскольку
sbrc Flag, FIFO1_V
RET     ; не будет возврата, флаг уже сброшен.

В итоге: пишем в ячейку, которую собираемся читать.
Также получаем в писателе пропуск
cpse F_1_IP, F_1_OP
но к счастью при читатель потом пометит пуффер пустым, и просто выкенет все остальные данные, уже находящиеся в буффере. К счастью потому, что не будет искажения порядка приёма данных (просто отброс всех данных кэша).
На мой взгляд лучше пожертвовать одной ячейкой в кольцевом буффере и обойтись без дополнительных флагов.

Далее, полное отсутствие атомарности в работе со счетчиками F_1_IP и F_1_OP. Что будет если мы уже увеличили счетчик, но еще не наложили маску, а нас уже вытеснили? На долго? Примерно могу отразить так (возможно где-то ошибся, понедельник):
Исходная ситуация
++++++++++++WR
выполняем чтение ld F_1_D, X
++++++++++++W-
-------------R
прерывание Стороннее, относительно длительное (таймер/кто угодно)
в фоне получаем байт данных, но т.к. АВР:
выполняем inc F_1_OP
--------------R (указатель за пределами буффера)
Обработка отложенного прерывания приема данных
+++++++++++++W
пока были в обработчике, пришел ещё один байт
выполняем ldi Temp, 0x3F
обрабатываем прерывание Прием
--------------R (указатель за пределами буффера)
W+++++++++++++ (переписали непрочитанный байт)
выполняем and F_1_OP, Temp
R+++++++++++++
выполняем cpse F_1_IP, F_1_OP  и sbr Flag, 1<<FIFO1_L
R-------------
В прочем эта ситуация совпадает с описанной во флагах, но если их уберёте, имейте ввиду.

Про совместное использование ячеек памяти (F_1_D — очевидно), вы указали уже сами. Нодо сохранять/загружать. А лучше тогда вообще оперировать аккамулятором (который по определению необходимо сохранять).

Ситуации «надуманные» но имеют место быть в загруженных системах в реальном железе. Даже «это же один на миллион» у меня в реальной системе наблюдался 1 к 10 с завидной постоянностью.
0
Да, что-то в моделировании указателя писателя я напортачил. (переписали непрочитанный байт) — не будет, просто потом отбросится весь кэш.
0
Спасибо за подсказку! Пройдемся по вашим пунктам:
1) если эту команду перенести за чтение буфера
FIFO_1_OUT:     ;==== выбрать байт из FIFO 1
                 sec
                 sbrc Flag, FIFO1_L
                     RET     ; выход с Carry
                 ldi     XL, low (FiFo1_Anf)     ; начальный адрес FIFO 1
                 ldi XH, high(FiFo1_Anf)
                 add XL, F_1_OP          ; вычислить текщий адрес SRAM
                 clr Temp
                 adc XH, temp
                 ld F_1_D, X                     ; данные из FiFo 1
                 inc F_1_OP              
                 ldi Temp, 0x3F          ; FiFo max 64 Bytes
                 and F_1_OP, Temp        ; Output Pointer = новое значение
            cbr Flag, 1<<FIFO1_V    ; <== СЮДА!!! флаг "полон" сбросить
                 clc
то, на мой взгляд, пункт 2) уже не имеет места. Тоже самое сделать и в процедуре FIFO_1_IN.
А значит в полный буфер уже ничего и не запишется.Или нет?

По поводу атомарности, не совсем понял с указателями:
… со счетчиками F_1_IP и F_1_OP. Что будет если мы уже увеличили счетчик, но еще не наложили маску, а нас уже вытеснили?
Если нас вытеснила противоположная процедура, то ничего — указатели-то меняются каждый в своей процедуре. Поправте, если ошибаюсь. В других процедурах/частях программы эти указатели не должны вообще меняться — это очевидно!
Ваше моделирование, к сожалению, я не совсем понял. В частности
выполняем inc F_1_OP
--------------R (указатель за пределами буффера)
как указатель уйдет за пределы буфера, если он маскируется его размером?
Кроме того прием очередного байта в стороннем обработчике не произойдет так быстро (в течении одного машинного цикла)
Обработка отложенного прерывания приема данных
+++++++++++++W
пока были в обработчике, пришел ещё один байт
выполняем ldi Temp, 0x3F
обрабатываем прерывание Прием
--------------R (указатель за пределами буффера)
W+++++++++++++ (переписали непрочитанный байт)
В крайнем случае ведь можно запретить прерывания на эти 16-18 тактов процедуры. А что касается регистра данных — согласен: лучше использовать отдельные для чтения и записи.
0
Предположим, что размер буффера 64 байта, и текущая позиция 63
; тут могла выполняться другое прерывание, во время выполнения которого пришел байт данных
inc F_1_OP    ; теперь текущая позиция 64 - за пределами буффера (АВР выполняет одну инструкцию всегда, при активном флаге прерывания)
; тут возможно выполнение прерывания от принятого раннее байта, во время обработки которого принят очередной байт (текущая обработка то была "подвинута" прошлым прерыванием)
ldi Temp, 0x3F      ; без изменений
; и тут возможно выполнение прерывания
and F_1_OP, Temp    ; и только теперь позиция 0
Потенциально может возникнуть 2 вызова прерывания, пока вы выполняете сложение с учетом переполнения. Это если рассматривать момент высокой нагрузки. Тот самый случай, когда «ну вот так совпало». Тот самый случай, когда отлаживаешь программу уже второй день подряд, в попытке воспроизвести ошибку, а у пользователя она падает чуть ли не каждые 5 минут.

А вот если написать примерно так (синтаксис условно, не помню уже кого, когда можно применять):
ld  Temp, F_1_OP
inc Temp             
andi Temp, 0x3F
ld  F_1_OP, Temp        ; Output Pointer = новое значение
То мы уже получаем «атомарный инкремент для всех читателей». Не важно где и сколько нас вытесняли, в общедоступной переменной всегда содержится действительное значение.
0
lds  Temp, F_1_OP
inc Temp             
andi Temp, 0x3F
sts  F_1_OP, Temp        ; Output Pointer = новое значение
я так понимаю, что F_1_OP уже переменная из SRAM, тогда всё верно при условии, что Temp во всех прерываниях прячется в стеке.
А по поводу «атомарный инкремент для всех читателей», согласен лишь отчасти:
если нас из основного цикла в момент чтения КБ выталкивает читающее прерывание, то тут важен момент, когда это произойдет. Особенно, если получится вложенный вызов процедуры, т.е. основная программа вызвала FIFO_1_OUT и во время ее отработки происходит прерывание с вызовом ее же. Здесь, безусловно, необходимо все продумать глубже. Очень интересно! Я об этом пока не задумывался, поскольку задача еще не выросла до такой ситуации.
0
Еще одна мысль по поводу
«атомарный инкремент для всех читателей»
А ведь «читатели» не должны обращаться к буферу произвольно, а то получат неполные данные. Т.е.:
"----1234567890=="
.....R'''''''''W.    <-Указатели чтения/записи
«Читатель А» прочитывает два элемента (к примеру) и занимается их разбором.
"------34567890=="
.......R'''''''W.    <-Указатели после чтения "А"
В это время доступ к КБ получает «Читатель Б» и прочитывает свой байт «3»
"-------4567890=="
........R''''''W.    <-Указатели после чтения "Б"

«Читатель А» разобрал заголовок сообщения (к примеру) и должен извлечь остальные данные. При этом он прочитает только остаток буфера «4567890», а значит уже неполные данные.
Я понимаю, что это гипотетическая ситуация. Возможна ли она на практике?
0
Естественно возможно. На ББ можете проверить, открываете порт в режиме раздельного чтения 2-мя программами, и вот он результат — часть данных в одном окне, часть в другом. Особо хорошо проявляется у *nix системах
cat /dev/ser1
в нескольких консолях.
Порою доставляет искать баг в разборе пакета, а потом выясняется, что это отладчик не убил предидущую сессию, и в итоге 2 приложения тянут данные с одного порта.
Если требуется доступ к порту из 2-х и более потоков, то лучше сделать работу с портом полностью в отдельном потоке, а все кому надо обмениваются целыми сообщениями.
Так что на этот счет особо можно не заморачиваться.

По поводу атомарности для читателей — указатель чтения для читателей является записываемой переменной (как и указатель записи для нескольких писателей), а такая операция должна быть либо истинно атомарной, либо блокироваться/приминятся прочие методы синхронизации доступа.
По сути можно получить 100% атамарный инкремент, если только инкрементировать переменную (без наложения маски). Тогда маску надо накладывать перед разъинтексацией и учитывать в сравнении. Взамен конструкции cpse F_1_IP, F_1_OP использовать вроде:
ld Temp, F_1_IP
sub Temp, F_1_OP
andi Temp, 0x3F
breq ...
Но даже при этом останется проблема, что момент извлечения индекса на чтение/запись происходит не одновременно с извлечением/записью данных в адресуемой ячейке.
Иными словами тут потребуется синхронизация относительно длинных участков кода, а её надо выполнять отдельно. Так что не стоит париться с этим. А вот одновременная работа читателя и писателя — ситуация вполне реальная и обычная.
если нас из основного цикла в момент чтения КБ выталкивает читающее прерывание
Это уже ошибка архетиктуры. Не стоит читать из основного цикла и из прерывания. Порядок чтения должен быть определен, если чтение имеет побочный эффект (в данном случае побочным эффектом является извлечение данных).
0
Собственно, я тоже так предполагал. Выше были гипотетические соображения.
0
Для исходящего буфера этого набора функций как правило достаточно, а вот для входящего я очень часто использую дополнительные функции. Самые часто используемые:
— функция возвращающая количество байт в буфере;
— функция возвращающая произвольный байт из буфера по заданному смещению относительно его хвоста и при этом не меняющая его состояние;
— функция удаляющая заданное количество байт из буфера.
Это удобно когда буфер используется не только для собственно буферизации но и для разбора принятых данных.
0
как мне повезло, что я не сопровождаю ваш код :)
0
Возможно даже очень повезло. Впрочем я могу поспорить о преимуществах такого подхода.
0
Это удобно когда буфер используется не только для собственно буферизации но и для разбора принятых данных.
Получается, что пока мы данные в буфере «разбираем», новых данных туда вносить нельзя?
0
Почемуже, пока мы работаем с хвостом данные могут вполне себе записываться в голову.
0
Старайтесь писать на С, даже если сложно сперва. Ничего особого в нем нет, тем более если вы понимаете ASM.
+1
Спасибо за вдохновение! Даст бог, займусь «С» всерьез :)
0
флаги «пустой» «полный»…
лишнее это, от лукавого. достаточно одного счетчика.
приняли символ: счетчик+1;
взяли символ: счетчик-1.
и всегда знаем сколько символов в буфере,
и проверки проще: if ( счетчик==размер_буфера ) print ( паника! )
0
Достоинство счетчика очевидно:
всегда знаем сколько символов в буфере
хотя и занимает он в 4 раза больше памяти: 8 бит для максимально возможного здесь КБ против 2 бит(флагов).
А вот начет упрощения проверок, сомневаюсь:
FIFO_1_IN:      ;=============================== добавить байт в FIFO 1
    cpi COUNTER, $3F    ;при использовании R16-R31
    breq FULL    ; там еще что-то делать типа установки флага или прочая реакция
.
.
.
FULL: sec    ; как минимальная реакция
    RET
В принципе те же 3 операции, учитывая установку флага «полон» в предидущей итерации вышепредложенной процедуры.
В случае применения для COUNTER младших регистров или ячейки SRAM, добавляется еще одна инструкция:
mov TEMP, COUNTER
или
lds TEMP, COUNTER
и о сохранении TEMP тоже надо побеспокоиться.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.