need ring buffer source code

Ben Collingsworth wrote:

Anyone have some efficient source code for implementing a ring buffer?

No doubt. But that's not we do here.
Try Google[1].

....and see the FAQ, at:

http://www.eskimo.com/~scs/C-faq/top.html

--ag

[1] or the search engine of your choice
--
Artie Gold -- Austin, Texas

In article <nn********************************@4ax.com>,
bd*************@cfl.rr.com says...

Anyone have some efficient source code for implementing a ring buffer?

Yes, I do.
--
Randy Howard _o
2reply remove FOOBAR \<,
______________________()/ ()______________________________________________
SCO Spam-magnet: po********@sco.com

Ben Collingsworth wrote:

Anyone have some efficient source code for implementing a ring buffer?

Yes, but it's in the source for the PDP-8 in the heart of BetaCom's
microfiche machine. You might write to Gould and ask permission to copy
it, assuming they haven't sold it to someone else. And its in Macro-8
assembler.

--
Martin Ambuhl

In article <nn********************************@4ax.com>,
bd*************@cfl.rr.com says...

Anyone have some efficient source code for implementing a ring buffer?

Yes, I do.
--
Randy Howard _o
2reply remove FOOBAR \<,
______________________()/ ()______________________________________________
SCO Spam-magnet: po********@sco.com

Ben Collingsworth wrote:

Anyone have some efficient source code for implementing a ring buffer?

Yes, but it's in the source for the PDP-8 in the heart of BetaCom's
microfiche machine. You might write to Gould and ask permission to copy
it, assuming they haven't sold it to someone else. And its in Macro-8
assembler.

--
Martin Ambuhl

On Thu, 04 Sep 2003 19:34:06 -0400, Ben Collingsworth
<bd*************@cfl.rr.com> wrote:

Anyone have some efficient source code for implementing a ring buffer?

There are several ways to implement a ring-buffer, depending on
how easy you want to make the tests for buffer empty/full. The
usual way I do it (without optimisations) is:

static unsigned char ringbuffer[ 256 ];
static unsigned short getindex = 0;
static unsigned short putindex = 0;
static unsigned short buffersize = 0;

int putring( char c )
{
if ( buffersize >= sizeof ringbuffer )
return -1;

ringbuffer[ putindex ] = c;
putindex++;
if ( putindex >= sizeof ringbuffer )
putindex = 0;
buffersize++;
return 0;
}

int getring( void )
{
if ( !buffersize )
return -1;
{
char c;

buffersize--;
c = ringbuffer[ getindex ];
getindex++;
if ( getindex >= sizeof ringbuffer )
getindex = 0;
return c;
}
}

Now, to make it faster.

If the size of the ring buffer is always a power-of-two you can
use masking to make the index variables wrap-around. For example
the increment and test for wrap-around becomes:

putindex = ( putindex++ ) & 0xFF;

If you have suitable compiler-extensions then force the start
address of the ring buffer to an alignment that is the same
as its size. That is for a 256-byte buffer it should be
aligned on a 256-byte boundary.

The indexing can then be replaced by pointers:

static char *putpointer = ringbuffer;

*putpointer = c;
putpointer = ( putpointer++ ) & ~0xFF;

Also there are functional efficiencies to consider, for example
the put function could discard the existing buffer contents if
the buffer overflows, this saves a test.

However I find that in real life programming ring buffers
can be considerable more entertaining. For example:

You may be part of a multi-tasking system where the task that
gets is different from the task that puts. The shared index
variables and buffer need to be defined as volatile and there
most likely need to be some kind of semaphore protection.

You want to get/put from within an interrupt handler. Potential
barrel of laughs that one.

Finally you may want to 'block' (i.e. do a non-looping wait)
on buffer full (put) or buffer empty (get). This is non-trivial
to get right, especially when using interrupts.

Nick.

Well, that ain't cool enough... I did mine in HTML
ipo

"Martin Ambuhl" <ma*****@earthlink.net> wrote in message
news:Ra*************@newsread1.news.atl.earthlink. net...

Ben Collingsworth wrote:

Anyone have some efficient source code for implementing a ring buffer?

Yes, but it's in the source for the PDP-8 in the heart of BetaCom's
microfiche machine. You might write to Gould and ask permission to copy
it, assuming they haven't sold it to someone else. And its in Macro-8
assembler.

--
Martin Ambuhl

On Thu, 04 Sep 2003 19:34:06 -0400, Ben Collingsworth
<bd*************@cfl.rr.com> wrote:

Anyone have some efficient source code for implementing a ring buffer?

There are several ways to implement a ring-buffer, depending on
how easy you want to make the tests for buffer empty/full. The
usual way I do it (without optimisations) is:

static unsigned char ringbuffer[ 256 ];
static unsigned short getindex = 0;
static unsigned short putindex = 0;
static unsigned short buffersize = 0;

int putring( char c )
{
if ( buffersize >= sizeof ringbuffer )
return -1;

ringbuffer[ putindex ] = c;
putindex++;
if ( putindex >= sizeof ringbuffer )
putindex = 0;
buffersize++;
return 0;
}

int getring( void )
{
if ( !buffersize )
return -1;
{
char c;

buffersize--;
c = ringbuffer[ getindex ];
getindex++;
if ( getindex >= sizeof ringbuffer )
getindex = 0;
return c;
}
}

Now, to make it faster.

If the size of the ring buffer is always a power-of-two you can
use masking to make the index variables wrap-around. For example
the increment and test for wrap-around becomes:

putindex = ( putindex++ ) & 0xFF;

If you have suitable compiler-extensions then force the start
address of the ring buffer to an alignment that is the same
as its size. That is for a 256-byte buffer it should be
aligned on a 256-byte boundary.

The indexing can then be replaced by pointers:

static char *putpointer = ringbuffer;

*putpointer = c;
putpointer = ( putpointer++ ) & ~0xFF;

Also there are functional efficiencies to consider, for example
the put function could discard the existing buffer contents if
the buffer overflows, this saves a test.

However I find that in real life programming ring buffers
can be considerable more entertaining. For example:

You may be part of a multi-tasking system where the task that
gets is different from the task that puts. The shared index
variables and buffer need to be defined as volatile and there
most likely need to be some kind of semaphore protection.

You want to get/put from within an interrupt handler. Potential
barrel of laughs that one.

Finally you may want to 'block' (i.e. do a non-looping wait)
on buffer full (put) or buffer empty (get). This is non-trivial
to get right, especially when using interrupts.

Nick.

Well, that ain't cool enough... I did mine in HTML
ipo

"Martin Ambuhl" <ma*****@earthlink.net> wrote in message
news:Ra*************@newsread1.news.atl.earthlink. net...

Ben Collingsworth wrote:

Anyone have some efficient source code for implementing a ring buffer?

Yes, but it's in the source for the PDP-8 in the heart of BetaCom's
microfiche machine. You might write to Gould and ask permission to copy
it, assuming they haven't sold it to someone else. And its in Macro-8
assembler.

--
Martin Ambuhl

Nick Austin <ni**********@nildram.co.uk> wrote:

On Thu, 04 Sep 2003 19:34:06 -0400, Ben Collingsworth
<bd*************@cfl.rr.com> wrote:

Anyone have some efficient source code for implementing a ring buffer?
There are several ways to implement a ring-buffer, depending on
how easy you want to make the tests for buffer empty/full. The
usual way I do it (without optimisations) is:

static unsigned char ringbuffer[ 256 ];
static unsigned short getindex = 0;
static unsigned short putindex = 0;
static unsigned short buffersize = 0;

int putring( char c )
{
if ( buffersize >= sizeof ringbuffer )
return -1;

ringbuffer[ putindex ] = c;
putindex++;
if ( putindex >= sizeof ringbuffer )
putindex = 0;

Another way to write those two lines is

putindex = (putindex + 1) % sizeof ringbuffer;

[...]
Now, to make it faster.

If the size of the ring buffer is always a power-of-two you can
use masking to make the index variables wrap-around. For example
the increment and test for wrap-around becomes:

putindex = ( putindex++ ) & 0xFF;
That line has undefined behaviour - it modifies putindex twice without
an intervening sequence point. The correct way to write it is:

putindex = (putindex + 1) & 0xFF;

But it's worth noting that since putindex is unsigned, most compiler
will optimise:

putindex = (putindex + 1) % 256;

to use the bitwise mask, if that's more efficient on the target
hardware.
If you have suitable compiler-extensions then force the start
address of the ring buffer to an alignment that is the same
as its size. That is for a 256-byte buffer it should be
aligned on a 256-byte boundary.

The indexing can then be replaced by pointers:

static char *putpointer = ringbuffer;

*putpointer = c;
putpointer = ( putpointer++ ) & ~0xFF;

If we correct for the above-mentioned problem:

putpointer = (putpointer + 1) & ~0xFF;

then we still have the problem that in C, the bitwise-& operator doesn't
operate on pointer values. Correcting that with the necessary casts:

putpointer = (char *)((unsigned long)(putpointer + 1) & ~0xFF);

....and we have something with implmentation-defined behaviour. If,
however, we assume the common implementation of integer to pointer
conversions, where a pointer converted to an integer becomes a number
representing the offset pointed-to within the addressed segment, then we
have something that *still* doesn't work. That bitmask always zeroes
out the lower 8 bits - which will mean that putpointer will never
change.

Perhaps you meant something like:

putpointer = (char *)((unsigned long)ringbuffer |
((unsigned long)(putpointer + 1) & ~0xFF));

Which despite being fantastically ugly and implementation-defined, and
requiring that ringbuffer be aligned on a 256-byte boundary, is unlikely
to be any faster than the naive implementation - given that most CPUs
have indexed addressing modes.

- Kevin.

Nick Austin <ni**********@nildram.co.uk> wrote:

On Thu, 04 Sep 2003 19:34:06 -0400, Ben Collingsworth
<bd*************@cfl.rr.com> wrote:

Anyone have some efficient source code for implementing a ring buffer?
There are several ways to implement a ring-buffer, depending on
how easy you want to make the tests for buffer empty/full. The
usual way I do it (without optimisations) is:

static unsigned char ringbuffer[ 256 ];
static unsigned short getindex = 0;
static unsigned short putindex = 0;
static unsigned short buffersize = 0;

int putring( char c )
{
if ( buffersize >= sizeof ringbuffer )
return -1;

ringbuffer[ putindex ] = c;
putindex++;
if ( putindex >= sizeof ringbuffer )
putindex = 0;

Another way to write those two lines is

putindex = (putindex + 1) % sizeof ringbuffer;

[...]
Now, to make it faster.

If the size of the ring buffer is always a power-of-two you can
use masking to make the index variables wrap-around. For example
the increment and test for wrap-around becomes:

putindex = ( putindex++ ) & 0xFF;
That line has undefined behaviour - it modifies putindex twice without
an intervening sequence point. The correct way to write it is:

putindex = (putindex + 1) & 0xFF;

But it's worth noting that since putindex is unsigned, most compiler
will optimise:

putindex = (putindex + 1) % 256;

to use the bitwise mask, if that's more efficient on the target
hardware.
If you have suitable compiler-extensions then force the start
address of the ring buffer to an alignment that is the same
as its size. That is for a 256-byte buffer it should be
aligned on a 256-byte boundary.

The indexing can then be replaced by pointers:

static char *putpointer = ringbuffer;

*putpointer = c;
putpointer = ( putpointer++ ) & ~0xFF;

If we correct for the above-mentioned problem:

putpointer = (putpointer + 1) & ~0xFF;

then we still have the problem that in C, the bitwise-& operator doesn't
operate on pointer values. Correcting that with the necessary casts:

putpointer = (char *)((unsigned long)(putpointer + 1) & ~0xFF);

....and we have something with implmentation-defined behaviour. If,
however, we assume the common implementation of integer to pointer
conversions, where a pointer converted to an integer becomes a number
representing the offset pointed-to within the addressed segment, then we
have something that *still* doesn't work. That bitmask always zeroes
out the lower 8 bits - which will mean that putpointer will never
change.

Perhaps you meant something like:

putpointer = (char *)((unsigned long)ringbuffer |
((unsigned long)(putpointer + 1) & ~0xFF));

Which despite being fantastically ugly and implementation-defined, and
requiring that ringbuffer be aligned on a 256-byte boundary, is unlikely
to be any faster than the naive implementation - given that most CPUs
have indexed addressing modes.

- Kevin.