Re: Circular buffer
From: Ed Beroset (beroset_at_mindspring.com)
Date: 10/15/03
- Next message: T.M. Sommers: "Re: HLA, Flex, and Bison"
- Previous message: The_Sage: "Re: Which assembler??"
- In reply to: A.Cloos: "Circular buffer"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 15 Oct 2003 02:49:57 GMT
A.Cloos wrote:
> I need to implement a circular buffer as an indexed array of values. How
> do I avoid falling off the end of the array, and make the array wrap
> around, biting its own tail.
The general answer is that whenever you increment or decrement an array
index, you check it against either zero or the maximum value and then
wrap it around to make sure it's never out of bounds.
The typical way to do that, especially in assembly language, is to make
the buffer size equal to a power of two. By doing this, you can assure
that the buffer wraps around just by using a bitwise AND on the index
afer any increment or decrement which is faster than doing an modulus
operation after each increment or decrement. One very common use for
such structures is as a communications buffer in which two array indices
are maintained; one for input and one for output. In that case, two
other operations are useful -- checking to see if the buffer is empty
and checking to see if the buffer is full. By convention, the buffer is
usually considered to be empty when the array indices are equal
(although this is not necessarily the only way to do it) and it's
considered to be full if incrementing the input array index would make
it identical to the output index. Some code might make this clearer:
; put the value in al into the circular buffer
; di = the current array index
; BUFFSIZE = power of two and is the buffer size
; buffer = address of the buffer which is a circular array of bytes
mov [buffer + di], al
inc di
and di, BUFFSIZE - 1 ; take care of wrap
; get the next value from the circular buffer
; si = the current array index
mov al,[buffer + si]
inc si
and si, BUFFSIZE - 1
; check for empty buffer
cmp di, si
jz EmptyBuffer ; branch if empty buffer
; check for full buffer
mov ax,di
inc ax
and ax,BUFFSIZE - 1 ; take care of wrap
cmp ax,si
jz FullBuffer ; branch if full buffer
; initialize buffer
xor di,di ; set both indices to zero
xor si,si
Note that these are not necessarily the most efficient ways of doing
these operations, but they work and they're easy to understand. Once
you have that, and if you do some timing measurements, you can figure
out if you want to optimize any of them. The full buffer check is
probably the easiest to improve if you do decide to do something.
Ed
- Next message: T.M. Sommers: "Re: HLA, Flex, and Bison"
- Previous message: The_Sage: "Re: Which assembler??"
- In reply to: A.Cloos: "Circular buffer"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
