Ring Buffer

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

Comments

Be the first to comment.




 Add Comment

  Comments 1 - 0 of 0  

Screen Name
Subject
Comment