Кольцевой буфер

AVR
Пусть здесь полежит, а то вдруг с моим репозиторием что случится… А тут, глядишь, кому и сгодится.
Код для обслуживания кольцевых буферов, маленький и шустрый.
Собственно так: в секции данных надо поместить массивчик, где будет храниться сам буфер, произвольного размера, до 255 байт. Глубина буфера задаётся константой RBSIZE, и массив получается на три байта больше размером. В первом байте лежит глубина заполнения, то есть сколько данных сейчас в буфере. При укладке байта — увеличивается, при выгрузке — уменьшается; если ноль — буфер пуст. Второй и третий байты — служебные, указатели загрузки и выгрузки. Для инита буфера надо эти три байта обнулить.
А дальше всё стандартно — процедурой PutToBuf укладываем в буфер содержимое r16, процедурой GetFromBuf — достаём. Если буфер переполнен — очередной байт туда не ляжет, если пуст — содержимое r16 не изменится.
Портит xl,xh,r17, загрузка/выгрузка занимает по 29 тактов. Локальных меток не имеет, так что можно легко тиражировать в любом количестве экземпляров внутри программы.


; В секции данных:
;.equ RBSIZE=11
; ringbuf:	.byte RBSIZE+3
; Конструкция кольцевого буфера: 
;+0 - глубина заполнения
;+1 - указатель укладки
;+2 - указатель выгрузки
;+3... - данные
; Использованные регистры: xh,xl,r16,r17
; укладка в буфер. 29 тактов
PutToBuf:	ldi	xh,high(ringbuf+3) ;загрузка базы буфера
		ldi	xl,low (ringbuf+3)
		lds	r17,ringbuf+0	;load rbdept
		cpi	r17,RBSIZE        ; проверка на переполнение
		brcc	pc+16
		inc	r17
		sts	ringbuf+0,r17    ;store rbdept
		lds	r17,ringbuf+1 	;load rbputptr
		add	xl,r17            ; складываем указатель с базой
		brcc	pc+2
		inc	xh
		st	x,r16            ; помещаем байт в буфер
		inc	r17               ; приращение указателя укладки
		cpi	r17,RBSIZE        ; закольцовка, если достигнута граница
		brcs	PC+2
		clr	r17
		sts	ringbuf+1,r17	;store rbputptr
		ret

; выгрузка из буфера. 29 тактов
GetFromBuf:	ldi	xh,high(ringbuf+3)
		ldi	xl,low (ringbuf+3)
		lds	r17,ringbuf+0	;load rbdept
		tst	r17            ; проверка наличия данных
		breq	pc+16
		dec	r17
		sts	ringbuf+0,r17	;store rbdept
		lds	r17,ringbuf+2	;rbgetptr
		add	xl,r17
		brcc	pc+2
		inc	xh
		inc	r17
		cpi	r17,RBSIZE
		brcs	PC+2
		clr	r17
		sts	ringbuf+2,r17	;rbgetptr
		ld	r16,x
		ret

  • +10
  • 26 июля 2015, 20:12
  • Gornist

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

RSS свернуть / развернуть
Прикольно. Не хватает только хорошего заголовка. Если вдруг кто-то захочет сослаться на ваше творение, а вы после захотите заголовочек сменить — то ссылка потеряется.
Обзовите как-нибудь FIFO буфер, или кольцевой буфер, каким-то образом, чтобы было понятно сразу, о чем речь.
0
breq    pc+16

а нельзя ли как-нибудь повразумительнее с лабелем как-нить?
breq    GFB_ret
...
GFB_ret:    ....


Понимаю, что это резервирует некое имя, потенциально приводящее к конфликту. Я обычно делал так: GetFromBuf -> GFB_01, GFB_02 и т.д. В принципе проблем с уникальностью не вызывало
0
тогда не получится
легко тиражировать в любом количестве экземпляров внутри программы.
+1
Жалко, что транслятор не поддерживает локальных меток, да и вообще препроцессор слабый. Недоработка, да. Под x86 почти все трансляторы умели такое делать, и не приходилось извращаться.
+1
и зачем тиражировать программу буфера? Логичнее сделать вот так:


                ldi     yh,high(ringbuf+3)
                ldi     yl,low (ringbuf+3)
                rcall PutToBuf
...
PutToBuf:
                ld      r17,Y             ;load rbdept
                cpi     r17,RBSIZE        ; проверка на переполнение
                brcc    pc+16
                inc     r17
                st      Y,r17            ;store rbdept
                ldd     r17,Y+1           ;load rbputptr
                push    yh
                push    yl
                add     yl,r17            ; складываем указатель с базой
                brcc    pc+2
                inc     yh
                st      y,r16            ; помещаем байт в буфер
                pop     yl
                pop     yh
                inc     r17               ; приращение указателя укладки
                cpi     r17,RBSIZE        ; закольцовка, если достигнута граница
                brcs    PC+2
                clr     r17
                std     y+1,r17   ;store rbputptr
                ret
+1
можно конечно и регистровую пару xh,xl оставить, но она не поддерживает ldd std. В этом случае можно просто ld r17,x+
второй раз ld r17,x, а потом суммировать это значение, на 1 меньшее, так как адрес уже сдвинулся.
0
код что я привел выше, работать не будет, сходу не разобрался в деталях. Там загружать нужно конечно вот так:

                ldi     yh,high(ringbuf)
                ldi     yl,low (ringbuf)
                rcall PutToBuf
...
PutToBuf:
                ld      r17,y             ;load rbdept
                cpi     r17,RBSIZE        ; проверка на переполнение
                brcc    PTB_End
                inc     r17
                st      y,r17            ;store rbdept
                ld      r17,y+1          ;load rbputptr
                push    yh
                push    yl
                add     yl,r17           ; складываем указатель с базой
                brcc    pc+2
                inc     yh
                std     y+3,r16            ; помещаем байт в буфер
                pop     yl
                pop     yh
                inc     r17               ; приращение указателя укладки
                cpi     r17,RBSIZE        ; закольцовка, если достигнута граница
                brcs    PC+2
                clr     r17
                std     y+1,r17   ;store rbputptr
                ret
0
Пушей-попов нагородил, размер оставил константой… И зачем это? Обычно достаточно одного-двух буферов, почему бы просто не сделать отдельные подпрограммы?

Что действительно стоит сделать — заменить подпрограмму на макрос и избавиться либо от «глубины заполнения», либо от «указателя укладки».
0
не суди, да не судим будешь))) Ну ошибся я, по невнимательности. Пуши-попы — в чем проблема-то? И зачем плодить однообразный код? Смысл есть?
0
Пуши-попы — в чем проблема-то?
Жрут по 2 такта, расходуют стек, да и просто некрасиво…

И зачем плодить однообразный код? Смысл есть?
Есть. Зачем усложнять в два раза и замедлять в два раза, лишь бы добиться ненужной «универсальности»?
0
некрасиво…
Говорят, что некрасиво, некрасиво, некрасиво отбивать подружек у друзей. А тут еще и push-pop некрасиво оказывается… Ну каждому на вкус и цвет… если уж считать такты, то думаю, можно опитимизировать «add,brcc,inc» в «add,adc r4», присвоив этому r4 нуль один раз в программе. Так что…
0
Нулевой регистр — это правильно, хотя в данном случае даст выигрыш всего в один такт. Пуши-попы — восемь тактов впустую.
0
можно и без push-pop, но тогда местами блоки программы надо переставить. И сохраняться не будет Y по выходу. Короче, всем все понятно.
0
Эээ, вот эта ваша последняя фраза — она чересчур глубока для меня. В смысле, я не догоняю.
Не могли бы вы высказаться немного понятнее? Каким образом можно избавиться от параметра «глубина заполнения» в кольцевом буфере?
0
Для индексации буфреа обычно хватает двух переменных. Есть два классических варианта индексации — с указателем чтения и указателем записи, либо с указателем начала данных и текущим количеством данных.
Первый вариант требует блока данных на одну ячейку больше, зато в некоторых условиях не нуждается в синхронизации. Второй вариант в целом удобнее, но требует синхронизации.
+1
Есть два классических варианта индексации — с указателем чтения и указателем записи, либо с указателем начала данных и текущим количеством данных.
Т.е. во втором варианте значение указателя начала данных будет переменным? Ведь кольцевой буфер — это FIFO.
К «Горнисту»: я как-то выкладывал мой вариант КБ (FIFO) на асме. Получилось примерно столько же команд, только без вычисления кол-ва данных в буфере.
0
Пусть расцветают тысячи цветов!
В смысле, вариантов много не бывает.
+1
Т.е. во втором варианте значение указателя начала данных будет переменным?

Но ведь и в первом случае указатель начала данных будет переменным. По мере чтения мы передвигаем указатель (иначе нам придётся двигать весь блок данных, с учетом закольцованности, что намного менее эффективно чем передвинуть указатель).

Lifelover прав, обычно используют 2 параметра для кольцевого буфера. Либо хранят указатель «начала» данных (указатель чтения, «хвост») и указатель на «конец» данных (указатель записи, «голова»). Либо хранят значение «хвоста» и количество данных. Этого достаточно – если я знаю значение «головы» и «хвоста» — я могу посчитать сколько данных в буфере (от «головы» отнять «хвост» и учесть закольцованность). Если я знаю «хвост» и длину – можно найти указатель на «голову» (к «хвосту» прибавить длину и
учесть закольцованность).

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

Надеюсь я не слишком Вас запутал, но по другому это тяжело объяснить, нужно рисовать состояние буфера на каждом шаге…
+1
Ну первый вариант реализован и у меня (см. выше), поэтому я хорошо его себе представляю. Про второй вариант я (скорее всего) в свое время «прослушал», потому и хотел уточнить.
0
Надо будет попробовать реализовать и другой вариант. Вопрос в том — будет ли он более экономичным?
Возможно, придётся ловить сообщения на скорости 1-2 мегабита. А это 80-160 тактов между поступающими байтами. В таких условиях быстродействие имеет значение.
0
В случае, когда критично именно быстродействие — вполне можно пожертвовать памятью в его пользу.
Но в данном случае вариант с двумя указателями выигрывает и по быстродействию (нет поля, которое надо менять и при чтении, и при записи — ну и обновление «размера» при наличии двух указателей — лишняя операция и лишнее время). Из минусов — при двух указателях не различить ситуации «буфер пуст» и «буфер полон», потому придется один элемент всегда оставлять пустым (не допускать заполнения).
0
Но больше регистров придётся заюзать. В прерывании неудобно.
0
да, причем жирный плюс отсутствия синхронизации — а это главное его преимущество, настолько полезно, что мелкий минусик можно и не принимать во внимание.
0
Какой плюс? Какой минусик? Чьё преимущество?
Ничего не понятно.
0
Слушайте, у вас кризис какой-то? Что вы докопались? Сложно нажать ↑ и посмотреть, о чем ведется речь?
0
Я нажимал, но так и не понял какие плюсики, минусики и преимущества имеются в виду.
0
Хотя дошло. Под «отсутствием синхронизации» следует понимать отсутствие необходимости в ней.
0
Первый метод позволяет реализовать «неблокируемую структуру данных»
Можно поподробнее про lock-free структуры данных в bare metal coding MCU-кодировании, и почему именно первый метод lock-free?
0
Это не совсем честный lock-free, поэтому я и написал в кавычках. В первом случае, при правильной реализации, мы получим структуру, которая безопасно работает на конкурирующих операциях чтение-запись (даже wait-free), т. к. каждая из этих операций читает чужой указатель и двигает свой. Второй подход – менее привлекательный с этой точки зрения, т. к. каждая из операций модифицирует переменную «количество данных»
0
да, три управляющих байта — это перебор. Достаточно два указателя. Однако Внезапно! Это не позволит сократить буфер на один байт, поскольку в таком варианте одна ячейка всегда должна быть пустой!
0
А как насчёт подумать в чём разница между «управляющим» байтом и байтом данных?
0
Если вы хотели что-то сказать, то скажите
+1
Я предложил подумать. По твоему комменту я понял, что ты считаешь, что указатель (который нужно читать, писать, и вообще обрабатывать) и лишняя ячейка в массиве (которая просто существует и никому не мешает) — это один и тот же фиг, раз то байт и это байт.
0
Подумать над тем что вы поняли? Прежде нужно изъяснить ваше понимание, чтобы о нем думать)) В том посте я говорил о общем размере буфера. С этой точки зрения — и ячейка данных и ячейка управления — одно и то же. Эту мысль можно было бы прочитать здесь: «Это не позволит сократить буфер на один байт»
0
Из фразы «Это не позволит сократить буфер» (тем более — «внезапно не позволит»), можно понять что буфер хотели именно сократить.
0
… в таком варианте одна ячейка всегда должна быть пустой!
Почему?
0
Я же выше уже говорил.
0
Вы сказали об этом видимо слишком сложно)) Суть такова, что что если два указателя указывают на одну и ту же ячейку — то буфер считается пустым. Так вот, при заполнении буфера нужно не перестараться с этим, чтобы не заполнить последнюю ячейку, иначе полный буфер == пустой буфер.
0
Стараться не нужно. Все алгоритмы ведут себя одинаково при правильной реализации.
0
Все алгоритмы ведут себя одинаково при правильной реализации.
Все алгоритмы ведут себя по-разному. Это отличительная черта алгоритмов. Вести себя индивидуально. А вот если хочется получить правильную реакцию этих алгоритмов — требуется соответствующая реализация. Но в некоторых случаях получить несвойственную реакцию алгоритма — невозможно.
0
Все приведённые алгоритмы FIFO совершенно одинаково вернут ошибку, если при заполнении закончится свободное место.
0
Оба указателя показывают на одну ячейку буфера — буфер пуст или полон.
Все остальное — буфер уже не пуст, но еще не полон.
Так, по крайней мере, реализовано у меня с помощь двух флагов, говорящих о состоянии буфера. Поэтому и нет «пустой» ячейки.
Использование флагов считаю более «скоростным», чем сравнение указателей с учетом закольцованности.
0
Использование флагов считаю более «скоростным», чем сравнение указателей с учетом закольцованности.
А что так? Указатели всё равно нужно обрабатывать. Если равны — пусто, если новый указатель записи налезает на указатель чтения — полон.
0
Конечно нужно обрабатывать! Но перед тем как писать в буфер (или читать из него) проверяю соотв. флаг, а уж потом все остальное, включая обработку указателя.
0
Даже с небогатым препроцессором можно сделать локальные метки:
breq GFB_ret

@GFB_ret:…
У AVR есть строгости в синтаксисе такого написания, сейчас точно не вспомню, на форуме несколько раз об этом говорил…
Смысл в том, что при таком написании метка становится локальной, препроцессор после пишет ее в виде @0123GFB_ret:
Номер всегда будет отличаться.
+1
Это в тулчейне чтоль? В нормальном AVRASM2 не работает. Зато метки в макросах по умолчанию локальные.
0
Насколько знаю тулчейна для ассемблера не существует. А в нормальном AVRASM2 это работает, есть строгости в синтаксисе такого написания. Во первых локальные метки применимы только в макросах, во вторых метка на строке должна быть одна, в третьих… (уже не помню). Вот ссылка (2012 год) — Your text to link...
Вкратце:
.MACRO INCOM
INC @0
CPI @0, 10
BRNE OutM
CLR @0
$OutM:
.ENDM
0
В тулчейне есть ассемблер (as.exe), я его имел в виду.
$-синтакс из A51? А какое он отношение имеет к avrasm2?
0
Самое прямое, avrasm2 его поддерживает, хотя он ему и не нужен. Нужен для avrasm. Я тут ошибся с литералами @ и $, подзабыл уже.
0
А откуда информация про поддержку? Похоже, $ просто игнорируется в почти любом месте.
0
Практика, некая программа ранее была написана на avrasm2 и прекрасно работала. Но потребовалось отдать ее в чужие руки. Т.к. компилятор был неизвестен, метки в макросах переделаны в локальные таким способом. А информация? Сейчас уже и не вспомню…
0
Хм, avrasm (1.77) как и avrasm2 делает метки в макросах локальными по умолчанию. При этом $ или @ перед меткой вообще считает ошибкой.
0
Насчет avrasm вы ошибаетесь, достаточно посмотреть *.lst после компиляции. $ перед меткой в макросе принимают оба.
0
Эм, ну вот исходник и lst.

test.asm:
.macro rot10
    inc        @0
    cpi        @0,10
    brne    _1
    clr        @0
_1:
.endm

.cseg
;(...)
    rot10    R16
    rot10    R16
;(...)

d:\Temp>avrasm32 test.asm -l test.lst -I "D:\Programs\Atmel\AVR Tools\AvrAssembler\Appnotes"
AVRASM: AVR macro assembler version 1.77.3 (Aug 25 2011 20:29:36)
Copyright (C) 1995-2005 ATMEL Corporation

Creating   'test.obj'
Creating   'test.lst'

Assembling 'test.asm'
Including  'D:\Programs\Atmel\AVR Tools\AvrAssembler\Appnotes\m8def.inc'

Program memory usage:
Code             :   13 words
Constants (dw/db):    0 words
Unused           :    0 words
Total            :   13 words

Assembly complete with no errors.

test.lst:
000004   +      rot10    R16
000004 9503          inc        r16
000005 300a          cpi        r16,10
000006 f409          brne    _1
000007 2700          clr        r16
          _1:
          .endm
000008   +      rot10    R16
000008 9503          inc        r16
000009 300a          cpi        r16,10
00000a f409          brne    _1
00000b 2700          clr        r16
          _1:
          .endm

Добавляем "$".

test.asm:
.macro rot10
    inc        @0
    cpi        @0,10
    brne    _1
    clr        @0
$_1:
.endm

.cseg
;(...)
    rot10    R16
    rot10    R16
;(...)

d:\Temp>avrasm32 test.asm -l test.lst -I "D:\Programs\Atmel\AVR Tools\AvrAssembler\Appnotes"
AVRASM: AVR macro assembler version 1.77.3 (Aug 25 2011 20:29:36)
Copyright (C) 1995-2005 ATMEL Corporation

Creating   'test.obj'
Creating   'test.lst'

Assembling 'test.asm'
Including  'D:\Programs\Atmel\AVR Tools\AvrAssembler\Appnotes\m8def.inc'
test.asm(23) : error : Undefined variable referenced
test.asm(23) : error : Syntax error
test.asm(24) : error : Undefined variable referenced
test.asm(24) : error : Syntax error

Assembly complete with 4 errors

Deleting   'test.obj'

test.lst:
000004   +      rot10    R16
000004 9503          inc        r16
000005 300a          cpi        r16,10
000006           brne    _1
error : Undefined variable referenced
000007 2700          clr        r16
error : Syntax error ; $_1:
          .endm
000008   +      rot10    R16
000008 9503          inc        r16
000009 300a          cpi        r16,10
00000a           brne    _1
error : Undefined variable referenced
00000b 2700          clr        r16
error : Syntax error ; $_1:
          .endm
0
Вдогонку, если кто забыл, литерал @ это то-же самое что и PC, т.е. содержание регистра счетчика команд…
0
Только сейчас дошло… Локальные метки актуальны для макросов, их тушка вставляется непосредственно в место применения. А у вас подпрограмма, она всегда будет в единственном числе.
0
Можно еще укоротить за счет выбрасывания сравнения конца, а маркер просто инкрементить, обрезая по маске. Правда размер буфера станет дискретным, кратным степени двойки.
0
Ну, получится всего на две команды меньше, зато гибкость потеряется.
+1
А вообще в AVR. Пусть будет там.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.