circular buffering C code

In comp.dsp,
robert bristow-johnson <rbj@audioimagination.com> wrote:
>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.
>
For a FIR I have used another method. The samples go into a normal circular
buffer and I have a coefficients array that is twice it's normal length
(duplicating the entries). When it's time to calculate the FIR, I calculate
the starting point in the coefficient array from the current buffer index
and always start at 0 in the sample buffer. This way I can do the filter
in a single loop without index checking.

The real advantage of this is that you can unroll the loop. This is what
I did in the final app. This app was on an ARM7 and I moved the function
to assembly. This resulted in only 3 instructions per tap with 32-bit
data en coef and 64-bit intermediate results. One reason for moving to
assembly was that I could not get the C compiler to emit the smlal
instruction which is the perfect instruction for a FIR.


-- 
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

Love and scandal are the best sweeteners of tea.

"James Morrison" <spam1@emorrison.ca> wrote in message 
news:1111117521.8718.78.camel@oxygen.emorrison.ca...
> On Thu, 2005-03-17 at 11:34 -0800, Fred Marshall wrote:
> http://www.ganssle.com/tem/tem111.pdf
>
> Hope that helps.

Thanks James!

FRed 

in article 593d$423a9cdf$54f63171$2604@publishnet.news-service.com, Stef at
stef33d@yahooI-N-V-A-L-I-D.com.invalid wrote on 03/18/2005 04:18:

> For a FIR I have used another method. The samples go into a normal circular
> buffer and I have a coefficients array that is twice it's normal length
> (duplicating the entries). When it's time to calculate the FIR, I calculate
> the starting point in the coefficient array from the current buffer index
> and always start at 0 in the sample buffer. This way I can do the filter
> in a single loop without index checking.

wow, that's a way i hadn't thought about at all.  clever, Stef.

one thing that the order of evaluation of the FIR summation reminds me about
is that it had been useful in single precision floating-point to evaluate
the end tail (for a more minimum phase FIR) or tails (for linear phase)
first and work your way into the portion of the FIR where the tap values are
largest.  you get less quantization error that way.  if you have a double
precision accumulator (be it fixed or floating-point), it shouldn't make any
difference what the order of summation is.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

I am using the 67xx series right now.  I am familiar with the ADI
techniques as RBJ's pointed out, but that is all in assembly as far as
I know.  I have written a fair amount of fixed-pt ADI assembly code,
but writing assembly for the TI processor is a whole different can of
worms from my experience (i.e. not very nice).

Now I have recently found ways to make the TI chips do very efficient
computations using ANSI C and their optimizing compiler - but it does
take some getting used to.  Sometimes the resulting code doesnt read
very well.

In the past I wrote all my algs in embedded DSP assembly, and the
circular buffering issue in C was always a thorn I have been trying to
solve since moving to a C compiled embedded DSP solution...

During this exercise I was also attempting to compare C compilers for
the TI 67xx series and the TigerSharc.  Since I havent used the ADI
Visual DSP toolset, I was attempting to gauge the performance
differences.

My question was and still is:  Since the 6713 maxes out at 300Mhz, and
a TigerSharc goes upwards of 600-700Mhz, which compiler gives you the
better software pipelining/performance?  With C code being equal (or
equivalent optimizations done), will a 300Mhz  TI chip compiled with
their C optimizer perform better than a 600Mhz TigerSharc compiled with
ADI's C tools?

That's the 6 million dollar question.  You can read MIP marketing
blurbs all day, but when it gets down to brass tax you want to know how
typical C code gets optimized.  I've witnessed 50x speedups in TI C
code by just software pipelining certain loops, but I dont have any
reference on how the ADI tools perform without porting over the project
and doing a 1:1 analysis...

in article 1111173831.345519.219870@g14g2000cwa.googlegroups.com, JS at
jshima@timing.com wrote on 03/18/2005 14:23:

> I am using the 67xx series right now.  I am familiar with the ADI
> techniques as RBJ's pointed out, but that is all in assembly as far as
> I know. 

i thought for sure there was a way to assign a register variable in the
ADSP-21000 C language to a particular register in the chip.  it was a
non-ANSI, implementation specific extension to C.  but on my Mac here, i
certainly have no ADI code lying around in it.  can the ADI jocks pipe in
here?  Al Clark, Jim Thomas, someone from ADI?


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

JS--
Good that you finally came around to asking pointed questions, I was a
little hesitant in the begining to directly give info about c67xx without
knowing if thats what you are targetting...Anyways, ill *try* to give you
a fair picture here:

>I am using the 67xx series right now.  I am familiar with the ADI
>techniques as RBJ's pointed out, but that is all in assembly as far as
>I know. 
You are right.There are no known circular addressing mode techniques at C
level for any processor, atleat none that i know of.I can say with
confidence that there is no support for circular addressing in c6000
tools, nor does TI have plans to have this from C due to some difficulties
in implementation. Today, the recommended methods would be:1) hand assembly
(not desirable). 2) Use modulo addressing on the pointer offsets, which
will result in a relatively inexpensive AND instruction, that often comes
with no performance penalty. sum += x[i%32] * y[j%64]. This would result
in implementation of two buffers (sized 32 and 64 elements respectively),
with an AND operation to do the circular addressing. Keep in mind that you
must use a power of 2 (as you would using the hardware)Read the application
note spra645.pdf at ti's website for recommended methods for implementing
circular buffers in c6000.

 I have written a fair amount of fixed-pt ADI assembly code,
>but writing assembly for the TI processor is a whole different can of
>worms from my experience (i.e. not very nice).

I agree some, disagree some. C6000 is not your regular MAC based CISC
DSP,where hand asm coding is the *only* way to eke out performance.C6000
is the most successful VLIW(TI calls it VelociTI) architecture ever there
was barring none.It is a very very deeply pipelined (unprotected)
processor and it is fool hardy to attempt to implement a project
completely in ASM in C6000, It is meant to be programmed in C using the
highly optimizing C compiler provided by the manufacturer. If you
must,then you can program in Linear Assembly(not the same as ASM), which
is very cool and can produce up to 95% of hand coded optimization without
having to do register management and software pipelining the code.The
bottom line is let the tools do the job.But then you shd know how to get
the job done from the tools as well, this involves quite a bit of reading,
i presume.

>
>Now I have recently found ways to make the TI chips do very efficient
>computations using ANSI C and their optimizing compiler - but it does
>take some getting used to.  Sometimes the resulting code doesnt read
>very well.

Well, thats an odd complaint, why wud u want the resulting code to look
good? You would maintain the make file and the source code in C (for
future revisions) so bother about the resulting code.Anyways, the
explanation is that VLIW ASM code is not an ideal diet for a sunday
evening code reading exercise! It is not readable at all in the regular
sense, its a highly paralell code, which with suffiecient experience you
may be able to read and digest but not so for new adopters.

>In the past I wrote all my algs in embedded DSP assembly, and the
>circular buffering issue in C was always a thorn I have been trying to
>solve since moving to a C compiled embedded DSP solution...
>
The simple answer is no. I'm not aware of any DSP compiler that allows C
to use circular buffering hardware. The problem is that C doesn't
understand circular modification of pointers.Most of the solutions that
I've seen are in assembly and then call them from C. 

The easiest solution might be trying to find code that already performs
the necessary algorithm. Baring that, you might be able to write a simple
assembly function to update a pointer with circular modification and then
call it from your C routine. This might be faster than managing the whole
process in C

>During this exercise I was also attempting to compare C compilers for
>the TI 67xx series and the TigerSharc. 

TI's C6000 compiler is highly efficient for programs that have lots loops
and have a certain degree of data-non-dependecy in the algorithm.These two
issues are the red herrings for C6000. Anyways if you are doing DSP
algorithms they tend to be manifestations of those two herrings...Some
think that this and ADS for arm are two best optimizing compilers in the
world.And I agree.

>My question was and still is:  Since the 6713 maxes out at 300Mhz, and
>a TigerSharc goes upwards of 600-700Mhz, which compiler gives you the
>better software pipelining/performance? 

C6713 has 8 *independant* functional units:

1] 2 .M -Multiplier units
2] 2 .D- data units(for load and store,can do simple arithmetic as well)
3] 2 .S -bit manip units (can do arithmetic and branch as well)
4] 2 .L -ALU units

(C67xx have a whopping 16 stage pipeline!)

Now thats, actually 2 multipliers, 6 ALU's and 2 data units! And all of
them can be operated paralelly, i.e 8 instructions can be executed every
clock cycle! Isnt that great? C6713 runs at 300 mhz, so it is capable of
performing 600 Millions of MACs (2 .M units running at 300 mhz!) it can
load or store upto 64 bit data values every clock! Finally, all put
together C6713 can operate at 300*8= 2400 MIPS! And yes the compiler
maximises these units provided you give lots of hints(pragma's) and
assistance(intrinsics,aliasing etc.) to the compiler itself and use the
right build options(-o3,pm,-mt etc.)


 With C code being equal (or
>equivalent optimizations done), will a 300Mhz  TI chip compiled with
>their C optimizer perform better than a 600Mhz TigerSharc compiled with
>ADI's C tools?
Is tigersharc a RISC? if so this comparison is valid, otherwise it is
totally meaningless. I will wait for your reply before dwelling deep on
"tiger compiler vs C6000 compiler".

>
>That's the 6 million dollar question.  You can read MIP marketing
>blurbs all day, but when it gets down to brass tax you want to know how
>typical C code gets optimized.  I've witnessed 50x speedups in TI C
>code by just software pipelining certain loops, but I dont have any
>reference on how the ADI tools perform without porting over the project
>and doing a 1:1 analysis...
>
>

My money is on TI compiler for efficiency, I have used it for more than 5
years now. 


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

robert bristow-johnson wrote:
> 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) 

Yes.

> that
> defines (or divides) which taps are one side of the buffer and which are
> wrapped around to the other side?  
no. The dividing point is detected by the conditional of the first loop.

> 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?  

Once the index goes past the end of the buffer in the first loop, 
subtract the buffer length before starting the second loop. Subtraction 
at the right time keeps the index in the modulus domain.

> 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.  

Yes, I think offset deltas are better than offsets.

> then there is an addition, which seems to me to be on par with an
> ANDing operation.

I don't think the two-loop approach requires any additional addition 
operations as compared to the one-loop-with-ANDing approach.

bhooshaniyer <bhooshaniyer@gmail.com> wrote:
> If I may ask, why code Circular buffer in C at all? Assuming you are using
> a DSP chip for your programming, there is bound to be a hardware circular
> buffer which can be programmed only through assembly.From your question I
> infer that you are worried about cycles and if you are then you shd be
> choosing to code in assembly.Thats your best bet. In fact strictly
> speaking circula buffer is precisely one of the reasons for you to choose
> assembly over C.

But doesn't this assume a lot of things as to what he will be keeping
in the buffer? 

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

-- 
	Sander

+++ Out of cheese error +++

Mark Borgerding <mark@borgerding.net> wrote:
> 
> 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.

Are these actually more efficent - and that includes the explicit and 
for update - any more efficent in practice than coding it all with a 
mod operation in C and having the compiler do the conversion? Compilers
have been converting n % m into various non-division invlving operation
for constant / known m for many decades...

> 
> 
> -- Mark Borgerding

-- 
	Sander

+++ Out of cheese error +++

"Sander Vesik" <sander@haldjas.folklore.ee> wrote in message
news:1111285850.795596@haldjas.folklore.ee...
> Mark Borgerding <mark@borgerding.net> wrote:
> >
> > 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.
>
> Are these actually more efficent - and that includes the
explicit and
> for update - any more efficent in practice than coding it
all with a
> mod operation in C and having the compiler do the
conversion? Compilers
> have been converting n % m into various non-division
invlving operation
> for constant / known m for many decades...
>


while (empty != fill)
{
    <do stuff here using empty>

    if (++empty >= RINGBUFSIZE) empty = 0;
}

The generated code will require far fewer machine cycles
than anything involving modulo computations.