Кольцевой буфер
Пусть здесь полежит, а то вдруг с моим репозиторием что случится… А тут, глядишь, кому и сгодится. Код для обслуживания кольцевых буферов, маленький и шустрый.
Собственно так: в секции данных надо поместить массивчик, где будет храниться сам буфер, произвольного размера, до 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
breq pc+16а нельзя ли как-нибудь повразумительнее с лабелем как-нить?
breq GFB_ret
...
GFB_ret: ....Понимаю, что это резервирует некое имя, потенциально приводящее к конфликту. Я обычно делал так: GetFromBuf -> GFB_01, GFB_02 и т.д. В принципе проблем с уникальностью не вызывало
и зачем тиражировать программу буфера? Логичнее сделать вот так:
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
код что я привел выше, работать не будет, сходу не разобрался в деталях. Там загружать нужно конечно вот так:
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
Пушей-попов нагородил, размер оставил константой… И зачем это? Обычно достаточно одного-двух буферов, почему бы просто не сделать отдельные подпрограммы?
Что действительно стоит сделать — заменить подпрограмму на макрос и избавиться либо от «глубины заполнения», либо от «указателя укладки».
Что действительно стоит сделать — заменить подпрограмму на макрос и избавиться либо от «глубины заполнения», либо от «указателя укладки».
не суди, да не судим будешь))) Ну ошибся я, по невнимательности. Пуши-попы — в чем проблема-то? И зачем плодить однообразный код? Смысл есть?
Пуши-попы — в чем проблема-то?Жрут по 2 такта, расходуют стек, да и просто некрасиво…
И зачем плодить однообразный код? Смысл есть?Есть. Зачем усложнять в два раза и замедлять в два раза, лишь бы добиться ненужной «универсальности»?
Эээ, вот эта ваша последняя фраза — она чересчур глубока для меня. В смысле, я не догоняю.
Не могли бы вы высказаться немного понятнее? Каким образом можно избавиться от параметра «глубина заполнения» в кольцевом буфере?
Не могли бы вы высказаться немного понятнее? Каким образом можно избавиться от параметра «глубина заполнения» в кольцевом буфере?
Для индексации буфреа обычно хватает двух переменных. Есть два классических варианта индексации — с указателем чтения и указателем записи, либо с указателем начала данных и текущим количеством данных.
Первый вариант требует блока данных на одну ячейку больше, зато в некоторых условиях не нуждается в синхронизации. Второй вариант в целом удобнее, но требует синхронизации.
Первый вариант требует блока данных на одну ячейку больше, зато в некоторых условиях не нуждается в синхронизации. Второй вариант в целом удобнее, но требует синхронизации.
Есть два классических варианта индексации — с указателем чтения и указателем записи, либо с указателем начала данных и текущим количеством данных.Т.е. во втором варианте значение указателя начала данных будет переменным? Ведь кольцевой буфер — это FIFO.
К «Горнисту»: я как-то выкладывал мой вариант КБ (FIFO) на асме. Получилось примерно столько же команд, только без вычисления кол-ва данных в буфере.
Т.е. во втором варианте значение указателя начала данных будет переменным?
Но ведь и в первом случае указатель начала данных будет переменным. По мере чтения мы передвигаем указатель (иначе нам придётся двигать весь блок данных, с учетом закольцованности, что намного менее эффективно чем передвинуть указатель).
Lifelover прав, обычно используют 2 параметра для кольцевого буфера. Либо хранят указатель «начала» данных (указатель чтения, «хвост») и указатель на «конец» данных (указатель записи, «голова»). Либо хранят значение «хвоста» и количество данных. Этого достаточно – если я знаю значение «головы» и «хвоста» — я могу посчитать сколько данных в буфере (от «головы» отнять «хвост» и учесть закольцованность). Если я знаю «хвост» и длину – можно найти указатель на «голову» (к «хвосту» прибавить длину и
учесть закольцованность).
Первый метод позволяет реализовать «неблокируемую структуру данных», но есть ограничение, «хвост» не должен налезать на «голову». Второй метод – иногда удобнее, ибо мы всегда знаем количество данных в буфере. Но возникают проблемы с синхронизацией, т. к. это самое «количество данных в буфере» должно модифицироваться как при чтении так и при записи.
Надеюсь я не слишком Вас запутал, но по другому это тяжело объяснить, нужно рисовать состояние буфера на каждом шаге…
В случае, когда критично именно быстродействие — вполне можно пожертвовать памятью в его пользу.
Но в данном случае вариант с двумя указателями выигрывает и по быстродействию (нет поля, которое надо менять и при чтении, и при записи — ну и обновление «размера» при наличии двух указателей — лишняя операция и лишнее время). Из минусов — при двух указателях не различить ситуации «буфер пуст» и «буфер полон», потому придется один элемент всегда оставлять пустым (не допускать заполнения).
Но в данном случае вариант с двумя указателями выигрывает и по быстродействию (нет поля, которое надо менять и при чтении, и при записи — ну и обновление «размера» при наличии двух указателей — лишняя операция и лишнее время). Из минусов — при двух указателях не различить ситуации «буфер пуст» и «буфер полон», потому придется один элемент всегда оставлять пустым (не допускать заполнения).
Первый метод позволяет реализовать «неблокируемую структуру данных»Можно поподробнее про lock-free структуры данных в

- well-man2000
- 29 июля 2015, 08:59
- ↑
- ↓
Это не совсем честный lock-free, поэтому я и написал в кавычках. В первом случае, при правильной реализации, мы получим структуру, которая безопасно работает на конкурирующих операциях чтение-запись (даже wait-free), т. к. каждая из этих операций читает чужой указатель и двигает свой. Второй подход – менее привлекательный с этой точки зрения, т. к. каждая из операций модифицирует переменную «количество данных»
Все алгоритмы ведут себя одинаково при правильной реализации.Все алгоритмы ведут себя по-разному. Это отличительная черта алгоритмов. Вести себя индивидуально. А вот если хочется получить правильную реакцию этих алгоритмов — требуется соответствующая реализация. Но в некоторых случаях получить несвойственную реакцию алгоритма — невозможно.
Оба указателя показывают на одну ячейку буфера — буфер пуст или полон.
Все остальное — буфер уже не пуст, но еще не полон.
Так, по крайней мере, реализовано у меня с помощь двух флагов, говорящих о состоянии буфера. Поэтому и нет «пустой» ячейки.
Использование флагов считаю более «скоростным», чем сравнение указателей с учетом закольцованности.
Все остальное — буфер уже не пуст, но еще не полон.
Так, по крайней мере, реализовано у меня с помощь двух флагов, говорящих о состоянии буфера. Поэтому и нет «пустой» ячейки.
Использование флагов считаю более «скоростным», чем сравнение указателей с учетом закольцованности.
Даже с небогатым препроцессором можно сделать локальные метки:
Смысл в том, что при таком написании метка становится локальной, препроцессор после пишет ее в виде @0123GFB_ret:
Номер всегда будет отличаться.
breq GFB_retУ AVR есть строгости в синтаксисе такого написания, сейчас точно не вспомню, на форуме несколько раз об этом говорил…
…
@GFB_ret:…
Смысл в том, что при таком написании метка становится локальной, препроцессор после пишет ее в виде @0123GFB_ret:
Номер всегда будет отличаться.
Это в тулчейне чтоль? В нормальном AVRASM2 не работает. Зато метки в макросах по умолчанию локальные.
Насколько знаю тулчейна для ассемблера не существует. А в нормальном AVRASM2 это работает, есть строгости в синтаксисе такого написания. Во первых локальные метки применимы только в макросах, во вторых метка на строке должна быть одна, в третьих… (уже не помню). Вот ссылка (2012 год) — Your text to link...
Вкратце:
Вкратце:
.MACRO INCOM
INC @0
CPI @0, 10
BRNE OutM
CLR @0
$OutM:
.ENDM
В тулчейне есть ассемблер (as.exe), я его имел в виду.
$-синтакс из A51? А какое он отношение имеет к avrasm2?
$-синтакс из A51? А какое он отношение имеет к avrasm2?
Самое прямое, avrasm2 его поддерживает, хотя он ему и не нужен. Нужен для avrasm. Я тут ошибся с литералами @ и $, подзабыл уже.
Эм, ну вот исходник и lst.
test.asm:
test.lst:
Добавляем "$".
test.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
Комментарии (59)
RSS свернуть / развернуть