circular buffering C code

in article qoadnV3_srfCf6TfRVn-ug@centurytel.net, Fred Marshall at
fmarshallx@remove_the_x.acm.org wrote on 03/17/2005 15:02:

> When I'm managing software developers I insist that they *not* use
> assembler - well .... without very good reason.

...

> OK - maybe for a circular buffer it might be warranted.  But I wouldn't
> start there!

the C language support for most DSP chips (well, at least the SHArC, i would
assume so for the TI chips) have some form of extension to the language to
support efficient circular buffers.  so, for the most part, this well known
bit masking the index technique used in an ANSI C situation (running on a
general purpose CPU) won't be needed in one of these DSP chip
implementations.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Hey Robert,

Can you expound on how the Sharc C compiler supports circular
buffering?  I am stuck right now using TI's Code Composter, and as far
as I can tell it doesnt support C-like circular buffering (no big
surprise, eh?).   Plus I am trying to show the higher up folks here
that the Sharc is a better way to go than the TI floating pt POS.

Jim

in article 1111100844.376234.247750@z14g2000cwz.googlegroups.com, JS at
jshima@timing.com wrote on 03/17/2005 18:07:

> Can you expound on how the Sharc C compiler supports circular
> buffering?

it's been nearly a decade, but, as i recall, there was a way you could
assign register variables to particular registers.  the SHArC had four
registers in a set, there was an I register (the pointer), the B register
(where you would put the base of your buffer), and M register (which could
index in from the I registers - the M register did not have to be associated
with any particular I registers), and an L register (defining the buffer
length).  i do not remember the syntax of assigning a particular register to
a particular pointer (for In or Bn) or integer (for Mn and Ln) register
variable.  i think it was ugly, but there was a way.

> I am trying to show the higher up folks here
> that the Sharc is a better way to go than the TI floating pt POS.

you should get the Bittware people or Al Clark or other sharks to say.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Randy Yates wrote:
> "dsp_rookie" <mk_gandhi4@yahoo.com> writes:
> 
> 
>>hi,
>>i am trying to implement the circular buffering mechanism in a c code
>>using pointers for one of the applications. can anyone explain to me an
>>efficient algorithm (instruction cycles wise) to implement this. 
> 
> 
> The easiest thing I know to do is make your buffer size 2^M. Then updating
> the index is done by ANDing it with 2^M - 1.


I've used a differnt method that is
a) not assembly
b) not restricted to powers of 2
c) often faster than bitwise and-ing the index

Break up the iteration over the circular buffer into a pair of 
for-loops.  One for handling all operations from the current position to 
the end, and the other loop to handle the beginning of the circular buffer.

The extra overhead of adding a second loop is probably less than the 
bitwise AND incurred for each iteration.  One possible exception is for 
very small circular buffers.  In that case, the designer should question 
the use of a circular buffer at all.


-- Mark Borgerding

On Thu, 2005-03-17 at 11:34 -0800, Fred Marshall wrote:
> > You might want to take a look at it.  I think the URL is
> > www.ganssle.com.  I hope I'm spelling his name correctly--forgive me
> > Jack if I'm butchering it.
> 
> I looked it up but couldn't find the "clarified" part.  It seems the article 
> was in the last issue posted on the site. ??

I checked through my email and found it.  Its originally in "Embedded
Muse 110" and then a few extra comments and feedback from readers in
issue 111.  Here's a link to a pdf from his site for issue 111.  Just
change the number to get to the previous issue.

http://www.ganssle.com/tem/tem111.pdf

Hope that helps.

in article Kxr_d.3203$h22.1424@fe1.columbus.rr.com, Mark Borgerding at
mark@borgerding.net wrote on 03/17/2005 22:03:

>> The easiest thing I know to do is make your buffer size 2^M. Then updating
>> the index is done by ANDing it with 2^M - 1.
> 
> 
> I've used a differnt method that is
> a) not assembly
> b) not restricted to powers of 2
> c) often faster than bitwise and-ing the index
> 
> Break up the iteration over the circular buffer into a pair of
> for-loops.  One for handling all operations from the current position to
> the end, and the other loop to handle the beginning of the circular buffer.

this is for doing an FIR, right, Mark?  i tried to allude to it, i guess it
was this morning.  that "current position" in the buffer is a state that you
have to keep track of (and save and restore) and when you increment (or
decrement, if you like to express delays as a positive displacement) that
current position pointer (only once per sample), you do need to check to see
if wrapping is necessary.  but that's only once per sample, not for every
tap of the FIR.

> The extra overhead of adding a second loop is probably less than the
> bitwise AND incurred for each iteration.  One possible exception is for
> very small circular buffers.

another possible exception is a sparsely tapped long delay line where the
taps are at sorta randomly spaced intervals.  (like an FIR where nearly all
of the taps have zero coefficients, but the non-zero taps are spaced at
weird intervals.  a sorta reverberator.)  then, i think, the power of 2 and
masking technique is the simplest reasonably foolproof method.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

JS-

> I am stuck right now using TI's Code Composter, and as far
>as I can tell it doesnt support C-like circular buffering (no big
>surprise, eh?).   

Well you are right, in a way...although you might wanna mention the TI
processor series that you are looking at for me to suggest a better
technique if possible... TI processors and code generation - that I have
expertise on - dont support circular buffer at C level and I dont think/
know of any techniques that could expose this addressing mode at C level
for any processor for that matter...(though I have heard that ANSI folks
who are working on the embedded C standard have this in their agenda as
well...).So am skeptical about this shark story of circular buffer support
at C level.I need to check it up to be sure but am sticking my neck out
here... Anyways, I have thought about this issue and I dont think fixes
like explosing few instrinsics could help the situation either...So the
best way to be efficient as far as TI chips go, is to go native! Now, Iam
a big fan TI chips so I will sure be up with my cudgels if someone at my
office suggested that we go sharc simply because TI tools for floating
point series C6000 are just awesone and if you learn how to program
VLIW/VelociTI architectures (its a steep learning curve however) they can
produce amazing results.And all using ANSI C! Good Deal, I would have
thought.

--Bhooshan

		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

robert bristow-johnson wrote:
> in article Kxr_d.3203$h22.1424@fe1.columbus.rr.com, Mark Borgerding at

>>Break up the iteration over the circular buffer into a pair of
>>for-loops.  One for handling all operations from the current position to
>>the end, and the other loop to handle the beginning of the circular buffer.
> 
> 
> this is for doing an FIR, right, Mark?  i tried to allude to it, i guess it
> was this morning.  that "current position" in the buffer is a state that you
> have to keep track of (and save and restore) and when you increment (or
> decrement, if you like to express delays as a positive displacement) that
> current position pointer (only once per sample), you do need to check to see
> if wrapping is necessary.  but that's only once per sample, not for every
> tap of the FIR.
> 
> 
>>The extra overhead of adding a second loop is probably less than the
>>bitwise AND incurred for each iteration.  One possible exception is for
>>very small circular buffers.
> 
> 
> another possible exception is a sparsely tapped long delay line where the
> taps are at sorta randomly spaced intervals.  (like an FIR where nearly all
> of the taps have zero coefficients, but the non-zero taps are spaced at
> weird intervals.  a sorta reverberator.)  then, i think, the power of 2 and
> masking technique is the simplest reasonably foolproof method.
> 
> 

The technique works best in the first case (FIR), but I've also used it 
in the second (sparse).  It is a bit trickier, though.

in article Utt_d.981$rL3.667@fe2.columbus.rr.com, Mark Borgerding at
mark@borgerding.net wrote on 03/18/2005 00:15:

> robert bristow-johnson wrote:
...
>> 
>> another possible exception is a sparsely tapped long delay line where the
>> taps are at sorta randomly spaced intervals.  (like an FIR where nearly all
>> of the taps have zero coefficients, but the non-zero taps are spaced at
>> weird intervals.  a sorta reverberator.)  then, i think, the power of 2 and
>> masking technique is the simplest reasonably foolproof method.
> 
> The technique works best in the first case (FIR), but I've also used it
> in the second (sparse).  It is a bit trickier, though.

so what do you do?  do you have a pointer to your ordered tap list
(containing the tap coefficient and delay for each non-zero tap) that
defines (or divides) which taps are one side of the buffer and which are
wrapped around to the other side?  and then test to see when that pointer
has to be moved?  how do you know (easily) how far to index into the
circular buffer for the first tap that comes after the wrap-around?  i guess
you would need a countdown state for that, too, which would also inform you
of when to move the dividing pointer in the ordered tap list.  i think the
tap list would not have the absolute delays (from the input pointer
position) of the taps, but would be the delay relative to the tap preceding
it.  then there is an addition, which seems to me to be on par with an
ANDing operation.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Mark Borgerding wrote:

> Randy Yates wrote:
>
>> "dsp_rookie" <mk_gandhi4@yahoo.com> writes:
>>
>>
>>> hi,
>>> i am trying to implement the circular buffering mechanism in a c code
>>> using pointers for one of the applications. can anyone explain to me an
>>> efficient algorithm (instruction cycles wise) to implement this. 
>>
>>
>>
>> The easiest thing I know to do is make your buffer size 2^M. Then 
>> updating
>> the index is done by ANDing it with 2^M - 1.
>
>
>
> I've used a differnt method that is
> a) not assembly
> b) not restricted to powers of 2
> c) often faster than bitwise and-ing the index
>
> Break up the iteration over the circular buffer into a pair of 
> for-loops.  One for handling all operations from the current position 
> to the end, and the other loop to handle the beginning of the circular 
> buffer.
>
> The extra overhead of adding a second loop is probably less than the 
> bitwise AND incurred for each iteration.  One possible exception is 
> for very small circular buffers.  In that case, the designer should 
> question the use of a circular buffer at all.

That's one traditional way. How well it works depends on the processor, 
though. It works really poorly if you have access some SIMD 
instructions. In those cases it is often more efficient to have a double 
length buffer, keep two copies of each sample in it, and use one loop.

In many processors the AND will incur no overhead at all (I am thinking 
of things like FP calculations on a Pentium, where the AND will occur in 
parallel with the operations in the FP unit). Two loops can add more 
delay through trashing the pipe than through the extra calculations. For 
typical filter lengths that might be rather a significant overhead.

Optimising these things is highly dependant on the target architecture.

Regards,
Steve