memset or not ?

I have a workbuffer with values that needs to be re-arranged, 
so...initially...I did it like this:

for (i = (N - 1); i >= 0; i--)
{
   workbuffer[Q * i] = workbuffer[i];
   memset(&workbuffer[(Q * i) + 1], 0, (Q-1) * sizeof(int16));
}

but I was told not to use memset. I don't know exactly why I am not allowed 
to use memset in a loop.
I guess it's not efficient enough? So I changed the code to this:

for (i = (N - 1); i >= 0; i--)
{
   workbuffer[Q * i] = workbuffer[i];
   for (j = 0; j < (Q - 1); j++)
   {
      workbuffer[(Q * i) + 1 + j] = 0;
   }
}

Let's say we have a 16 cell workbuffer B.

Four values have been stored in the first 4 cells in the workbuffer: B[0], 
B[1], B[2] and B[3] the remaining B[k] for k=4 to k=15 are undefined. The 
code must re-arrange the 4 values so the workbuffer looks like this:

B[0],0,0,0,B[1],0,0,0,B[2],0,0,0,B[3],0,0,0

The code is for an interpolator and in the above example N is the number of 
samples in the workbuffer before re-arrangement. So N would be 4! And Q 
would be an interpolation factor equal to 4.

Any suggestions for improvement?

Comments about not using memset in a loop are also welcomed.

Thank you.

Jake wrote:
> I have a workbuffer with values that needs to be re-arranged, 
> so...initially...I did it like this:
> 
> for (i = (N - 1); i >= 0; i--)
> {
>   workbuffer[Q * i] = workbuffer[i];
>   memset(&workbuffer[(Q * i) + 1], 0, (Q-1) * sizeof(int16));
> }

You are pathetic lamer.

src = workbuffer + N - 1;
dest = workbuffer + Q*N - 1;
i = N;

while(i--)
  {
  j = Q - 1;
  while(j--) *dest-- = 0;
  *dest-- = *src--;
  }


//-----------

VLV

Jake wrote:


> The code must re-arrange the 4 values so the workbuffer looks 
> like this:
> 
> B[0],0,0,0,B[1],0,0,0,B[2],0,0,0,B[3],0,0,0
> 
> The code is for an interpolator and in the above example N is the number 
> of samples in the workbuffer before re-arrangement. So N would be 4! And 
> Q would be an interpolation factor equal to 4.
> 
> Any suggestions for improvement?

This rearangement is absolutely unnecessary for the interpolator.

> Comments about not using memset in a loop are also welcomed.

Comments?  You are the imbecile indeed.



VLV

>
> Comments?  You are the imbecile indeed.

I appreciate your help, but your attitude really sucks. You must be very 
lonely.

Anyway...Thank you for the code snippet. 

Jake wrote:

>>
>> Comments?  You are the imbecile indeed.
> 
> 
> I appreciate your help, but your attitude really sucks. You must be very 
> lonely.
> 
> Anyway...Thank you for the code snippet.

Your "thank you" is a very valuable thing. There is no need to thank, 
just send me $100.

VLV

On 09/15/2010 07:07 AM, Jake wrote:
> I have a workbuffer with values that needs to be re-arranged,
> so...initially...I did it like this:
>
> for (i = (N - 1); i >= 0; i--)
> {
> workbuffer[Q * i] = workbuffer[i];
> memset(&workbuffer[(Q * i) + 1], 0, (Q-1) * sizeof(int16));
> }
>
> but I was told not to use memset. I don't know exactly why I am not
> allowed to use memset in a loop.
> I guess it's not efficient enough? So I changed the code to this:
>
> for (i = (N - 1); i >= 0; i--)
> {
> workbuffer[Q * i] = workbuffer[i];
> for (j = 0; j < (Q - 1); j++)
> {
> workbuffer[(Q * i) + 1 + j] = 0;
> }
> }
>
> Let's say we have a 16 cell workbuffer B.
>
> Four values have been stored in the first 4 cells in the workbuffer:
> B[0], B[1], B[2] and B[3] the remaining B[k] for k=4 to k=15 are
> undefined. The code must re-arrange the 4 values so the workbuffer looks
> like this:
>
> B[0],0,0,0,B[1],0,0,0,B[2],0,0,0,B[3],0,0,0
>
> The code is for an interpolator and in the above example N is the number
> of samples in the workbuffer before re-arrangement. So N would be 4! And
> Q would be an interpolation factor equal to 4.
>
> Any suggestions for improvement?
>
> Comments about not using memset in a loop are also welcomed.

I don't see any huge reason not to use memset in a loop.  When I first 
glanced at your code I thought that you were writing to position 0 then 
using memset to zero out 1 to the end, then writing to position 1 then 
using memset to zero out 2 to the end, etc.  _That_ would be a stupid 
and inefficient way to use memset.

Your way should, in an environment with decent library code, suffer only 
from the function call overhead.  That may be severe, but the code is 
readable.

If you need to whip the code out and the processor has cycles to spare, 
I don't see it as a bad way to go.  If you're willing to trade 
readability for speed then implement your interpolator differently, or 
use Vladimir's code snippet (assuming it tests out).

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

"Jake" <jake@nospam.invalid.com> writes:
> [...]
> The code is for an interpolator and in the above example N is the
> number of samples in the workbuffer before re-arrangement. So N would
> be 4! And Q would be an interpolation factor equal to 4.

You don't need to actually stuff zeros in your input for an
interpolator. Google for "polyphase filter" or "multirate filter".
-- 
Randy Yates                      % "She has an IQ of 1001, she has a jumpsuit
Digital Signal Labs              %            on, and she's also a telephone."
mailto://yates@ieee.org          % 
http://www.digitalsignallabs.com %        'Yours Truly, 2095', *Time*, ELO   

> You don't need to actually stuff zeros in your input for an
> interpolator. Google for "polyphase filter" or "multirate filter".

Isn't that only true if the filter in your interpolator is an FIR filter ?

The filter I am using is an IIR filter (to lower the number of 
multiplications and additions). Transition band is very narrow and there is 
a requirement for high attenuation in the stopband.

"Jake" <jake@nospam.invalid.com> writes:

>> You don't need to actually stuff zeros in your input for an
>> interpolator. Google for "polyphase filter" or "multirate filter".
>
> Isn't that only true if the filter in your interpolator is an FIR
> filter ?

That is correct. 

> The filter I am using is an IIR filter (to lower the number of
> multiplications and additions). Transition band is very narrow and
> there is a requirement for high attenuation in the stopband.

Realize that there are multiple efficiencies in using a polyphase
FIR for interpolation:

  1. If the interpolation ratio is M, then the computational complexity
  is reduced by a factor of M. That is, if your filter is N taps at
  the original sample rate, computationally it will only require N/M
  taps.

  2. If you use a linear-phase FIR, you gain another factor of two
  in complexity reduction (assuming you have an architecture in which
  an addition is less expensive than two multiply-accumulates).

  3. If you have a half-band filter, you gain another factor of two
  in complexity reduction.

I've never seen anyone implement an interpolator using an IIR, hence my
suggestion.
-- 
Randy Yates                      % "And all that I can do
Digital Signal Labs              %  is say I'm sorry, 
mailto://yates@ieee.org          %  that's the way it goes..."
http://www.digitalsignallabs.com % Getting To The Point', *Balance of Power*, ELO

On 09/15/2010 08:52 AM, Jake wrote:
>> You don't need to actually stuff zeros in your input for an
>> interpolator. Google for "polyphase filter" or "multirate filter".
>
> Isn't that only true if the filter in your interpolator is an FIR filter ?

Actually no -- but I'm not aware of any literature on the subject that I 
could quote.  The interpolated values when there's no input will be 
wholly determined by the state of the filter at the end of the last 
update with an input and the number of output sample times that has 
occurred.

The theory required to make a linear IIR polyphase filter is fairly 
direct -- I'm cooking it up in my head as I type -- although I don't 
know if anyone's reduced it down to a recipe the way that has been done 
for FIR polyphase filters.

> The filter I am using is an IIR filter (to lower the number of
> multiplications and additions). Transition band is very narrow and there
> is a requirement for high attenuation in the stopband.

Reasonable.

If you describe the filter in state space, with u as the filter input, x 
as the filter state, and y as the filter output, then the filter system 
equation is

x(n) = A * x(n-1) + B * u(n),       (1)
y(n) = C * x(n-1) + D * u(n).       (2)

Assume inputs every N'th sample, and let m be the index of the input 
samples.  Then for n = m * N you get

x(m*N) = A * x(m*N-1) + B * u(m),   (3)
y(m*N) = C * x(m*N-1) + D * u(m)    (4)

and for n != m * N

x(n) = A * x(n-1)                   (5)
y(n) = C * x(n-1)                   (6)

now let p = n - m*N; keeping the same condition that n != m * N:

x(m*N + p) = A^p * x(m*N)           (7)
y(m*N + p) = C * A^(p-1) * x(m*N)   (8)

And finally, revisit (3) and (4):

x(m*N) = A^N * x((m-1)*N) + B * u(m),                 (9)
y(m*N) = C * A^(N-1) * x((m-1)*N) + D * u(m)          (10)

So (10), (9), (8) and (7) describe polyphase filtering for linear IIR 
filters.  Note that you can't break this up: you'd have to describe the 
whole filter in state-space, and the connection between the state-space 
realization and a more "DSP traditional" cascade-of-biquads may be 
obscure.  It's in there somewhere, but it'd be obscure.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html