A ring buffer is the simplest form of a bounded queue. It consists of consecutive part of memory, referred to as Buffer and two variables referred to as Head and Tail. Both Head and Tail are initialized to 0, thus pointing to the beginning of the memory space.
The only operation performed on the Head and the Tail is incrementing them. If they happen to exceed the end of the memory, they are reset to the beginning. This wrapping around at the end turns the straight piece of memory into a ring.
The buffer is empty if and only if Head = Tail. Otherwise, the Tail is always ahead of the Head (although the Tail may be less than the Head if the Tail already wrapped around at the end, while the Head did not wrap around yet).
In Figure 1, a ring buffer is shown both as straight memory and as a logical ring.
Fig.1
This design always keeps one slot unallocated and Tail always points to the next slot.
Thus the buffer is full if the Tail refers to the slot preceding the one referred to by the Head
This is a simple, robust, approach that only requires two pointers Head and Tail, at the expense of one buffer slot.
Please support the kernel by clicking the Adds!
Single byte per item, up to 255 items implementation.
/*
RingBuffer - keep up to (256-1) bytes.
Zero based indexing
One byte per data item.
@IMPORTANT One data item slot will remain empty in this approach.Always consider (size+1) buffer allocation.Never use a buffer
of size 1!!!!!
@IMPORTANT The acccess to buffer is not synchronized
*/
#define RINGBUFFER_SIZE 3
#define INDEX_LIMIT RINGBUFFER_SIZE-1 ;zero based index
.dseg
;.ORG 0xFD
head_index: .byte 1
tail_index: .byte 1
buffer: .byte RINGBUFFER_SIZE
.cseg
;************************************************************
;@INPUT:
;@USAGE:r15
;@OUTPUT:
;************************************************************
RingBuffer8_Init:
clr r15
sts head_index,r15
sts tail_index,r15
ret
;*************************************************************
;@INPUT:
;@USAGE: r15,r16
;@OUTPUT: T - 1 not empty; 0 - empty buffer!
;*************************************************************
RingBuffer8_isEmpty:
lds r16,head_index
lds r15,tail_index
cpse r15,r16
rjmp rbisemptygo
clt
ret;empty buffer
rbisemptygo:
set
ret
;*************************************************************
;@INPUT:
;@USAGE: r15,r16
;@OUTPUT: T - 1 not full; 0 - full buffer!
;*************************************************************
RingBuffer8_isFull:
lds r15,head_index
lds r16,tail_index
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbisfull1
clr r16 ;place at the beginning
rjmp rbisfull2
rbisfull1:
inc r16
rbisfull2:
cpse r15,r16
rjmp rbisfullgo
clt;buffer overflow!!!!
ret
rbisfullgo:
set
ret
;************************PUT************************************
;@INPUT:r17
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - full buffer!
;************************************************************
RingBuffer8_Put:
lds r15,head_index
lds r16,tail_index
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbp1
clr r16 ;place at the beginning
rjmp rbp2
rbp1:
inc r16
rbp2:
cp r15,r16
brne rbpgo
clt;buffer overflow!!!!
ret
rbpgo:
lds r15,tail_index ;current position to write into
sts tail_index,r16 ;next free position
ldi XL,low(buffer)
ldi XH,high(buffer)
tst r15
breq rbpgo1
clr r16
add XL, r15
adc XH, r16 ;r16=0;just to add the cerry
rbpgo1:
st X,r17
set
ret
;************************GET************************************
;Points to a valid item if not empty buffer
;@INPUT:
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - empty buffer!
; r15 - result
;************************************************************
RingBuffer8_Get:
lds r16,head_index
lds r15,tail_index
cpse r15,r16
rjmp rbggo
clt
ret;empty buffer
rbggo:
ldi XL,low(buffer) ;position to head
ldi XH,high(buffer)
clr r15
add XL, r16
adc XH, r15 ;r15=0;just to add the carry
ld r15,X
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbg1
clr r16 ;place at the beginning
rjmp rbg2
rbg1:
inc r16
rbg2:
sts head_index,r16
set
ret
;************************PEEK************************************
;Read head item without movin the head pointer.
;@INPUT:
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - empty buffer!
; r15 - result
;************************************************************
RingBuffer8_Peek:
lds r16,head_index
lds r15,tail_index
cpse r15,r16
rjmp rbpeekgo
clt
ret;empty buffer
rbpeekgo:
ldi XL,low(buffer) ;position to head
ldi XH,high(buffer)
clr r15
add XL, r16
adc XH, r15 ;r15=0;just to add the carry
ld r15,X
set
ret
Two bytes per item, up to 2^16 items implementation .
/*
RingBuffer - keep up to (256-1) bytes.
Zero based indexing
2 bytes(Word) per data item.
@IMPORTANT
1. One data item slot will remain empty in this approach.Always consider (size+1) buffer allocation.Never use a buffer
of size 1!!!!!
2. Index calculation is on 2 bytes(Word) content.
@IMPORTANT The acccess to buffer is not synchronized
*/
;16 bit arithmetic
;@MACRO LSL16 MSB,LSB
.MACRO LSL16
lsl @1
rol @0
.ENDMACRO
#define RINGBUFFER_SIZE 3
#define INDEX_LIMIT RINGBUFFER_SIZE-1 ;zero based index
.dseg
;.ORG 0xFC
head_index16: .byte 1
tail_index16: .byte 1
buffer16: .byte RINGBUFFER_SIZE*2
.cseg
;************************************************************
;@INPUT:
;@USAGE:r15
;@OUTPUT:
;************************************************************
RingBuffer16_Init:
clr r15
sts head_index16,r15
sts tail_index16,r15
ret
;*************************************************************
;@INPUT:
;@USAGE: r15,r16
;@OUTPUT: T - 1 not empty; 0 - empty buffer!
;*************************************************************
RingBuffer16_isEmpty:
lds r16,head_index16
lds r15,tail_index16
cpse r15,r16
rjmp rbisemptygo16
clt
ret;empty buffer
rbisemptygo16:
set
ret
;*************************************************************
;@INPUT:
;@USAGE: r15,r16
;@OUTPUT: T - 1 not full; 0 - full buffer!
;*************************************************************
RingBuffer16_isFull:
lds r15,head_index16
lds r16,tail_index16
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbisfull116
clr r16 ;place at the beginning
rjmp rbisfull216
rbisfull116:
inc r16
rbisfull216:
cpse r15,r16
rjmp rbisfullgo16
clt;buffer overflow!!!!
ret
rbisfullgo16:
set
ret
;************************PUT************************************
;@INPUT:Y - 2 byte(word) content
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - full buffer!
;************************************************************
RingBuffer16_Put:
lds r15,head_index16
lds r16,tail_index16
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbp116
clr r16 ;place at the beginning
rjmp rbp216
rbp116:
inc r16
rbp216:
cp r15,r16
brne rbpgo16
clt;buffer overflow!!!!
ret
rbpgo16:
lds r15,tail_index16 ;current position to write into
sts tail_index16,r16 ;next free position
ldi XL,low(buffer16)
ldi XH,high(buffer16)
tst r15
breq rbpgo116
clr r16
LSL16 r16,r15 ;multiply by 2 ->dealing with 2 bytes/word content
add XL, r15
adc XH, r16 ;r16=0;just to add the cerry
rbpgo116:
st X+,YH
st X,YL
set
ret
;************************GET************************************
;Points to a valid item if not empty buffer
;@INPUT:
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - empty buffer!
; Y - 2 byte(word) content
;************************************************************
RingBuffer16_Get:
lds r16,head_index16
lds r15,tail_index16
cpse r15,r16
rjmp rbggo16
clt
ret;empty buffer
rbggo16:
ldi XL,low(buffer16) ;position to head
ldi XH,high(buffer16)
clr r15
LSL16 r15,r16 ;multiply by 2 ->dealing with 2 bytes/word content
add XL, r16
adc XH, r15 ;r15=0;just to add the carry
ld YH,X+
ld YL,X
lds r16,head_index16
cpi r16,INDEX_LIMIT ;wrap to beginning if at the end
brne rbg116
clr r16 ;place at the beginning
rjmp rbg216
rbg116:
inc r16
rbg216:
sts head_index16,r16
set
ret
;************************PEEK************************************
;Read head item without movin the head pointer.
;@INPUT:
;@USAGE:X,r15,r16
;@OUTPUT: T - 1 success; 0 - empty buffer!
; Y - 2 byte(word) content
;************************************************************
RingBuffer16_Peek:
lds r16,head_index16
lds r15,tail_index16
cpse r15,r16
rjmp rbpeekgo16
clt
ret;empty buffer
rbpeekgo16:
ldi XL,low(buffer16) ;position to head
ldi XH,high(buffer16)
clr r15
LSL16 r15,r16 ;multiply by 2 ->dealing with 2 bytes/word content
add XL, r16
adc XH, r15 ;r15=0;just to add the carry
ld YH,X+
ld YL,X
set
ret