Generic programming has become a bit of an obsession of mine lately. I've been studying this website:
Generic Programming[^]
And I've been intrigued by applying generic programming techiniques to DSP programming. I've posted about this in the past with a generic example of a delay line as well as a small parameter handling toolkit.
A key concept of generic programming is called Lifting[^]. It's where you examine a concrete algorithm and look for ways to make it generic. For example, here is a concrete copy algorithm:
void Copy(float *first, float *last, float *out)
{
while(first != last)
{
*out = *first;
first++;
out++;
}
}
Fair enough. But what if we wanted a copy algorithm for integers? We'd have to do this:
void Copy(int *first, int *last, int *out)
{
while(first != last)
{
*out = *first;
first++;
out++;
}
}
In examining the two algorithms we see they are exactly the same except for the type. So we can "lift" the algorithm up by making it type independent:
template<typename InputIterator, typename OutputIterator>
void Copy(InputIterator *first,
InputIterator *last,
OutputIterator *out)
{
while(first != last)
{
*out = *first;
first++;
out++;
}
}
Now we have a Copy function that can work on any type provided that the iterators meet the requirement of the algorithm. This is an important point. It's usually impossible to lift an algorithm to the point that it is so generic it can work on anything. There are usually some requirements. The above algorithm requires that the InputIterator support the postfix increment operator as well as the * operator for reading its value. The OutputIterator must also support the postfix increment operator and the * operator for writing to its value.
So how about applying this to DSP? Can we "lift" some of the algorithms used in DSP and VST programming?
Take a basic sine oscillator function:
float SineOscillator(float *first,
float *last,
float phase,
float increment)
{
while(first != last)
{
phase += increment;
while(phase > PI2)
{
phase = PI2;
}
*first = sin(phase);
first++;
}
return phase;
}
What can we do to "lift" this algorithm?
We can make it type independent for one. That's easy enough. But it would also be cool to make it waveform independent as well. And it would also be nice to pack up the phase and increment values into one object instead of passing them in seperately.
So applying the above, we come up with this:
template<typename OutputIterator,
typename Oscillator,
typename Waveform>
Oscillator Oscillate(OutputIterator first,
OutputIterator last,
Oscillator osc,
Waveform wave)
{
while(first != last)
{
osc.phase += osc.increment;
while(osc.phase >= osc.length)
{
osc.phase = osc.length;
}
*first = wave(osc.phase);
first++;
}
return osc;
}
The algorithm has several requirements. Oscillator must have a phase, increment, and length values. Waveform must provide a () operator that takes the current phase and returns a result.
One challenge with this kind of approach is maintaining state after each function call. If we call the above function like this:
Oscillate(&buffer[0], &buffer[BUFFER_SIZE], myOsc, sin);
Both the oscillator and waveform objects are passed in by value. We can update our oscillator object by assigning the return value to it:
myOsc = Oscillate(&buffer[0],
&buffer[BUFFER_SIZE],
myOsc,
sin);
That's fine but may not be very efficient if the oscillator is very large.
Instead we can pass the oscillator object in as a reference so whatever state changes that take place within the function persist afterwards:
Oscillate<float *, MyOscillator &, Sine>(&buffer[0],
&buffer[BUFFER_SIZE],
myOsc,
Sine());
If we need to persist changes in state to our waveform, we can use the same technique:
Oscillate<float *, MyOscillator &, Sine &>(&buffer[0],
&buffer[BUFFER_SIZE],
myOsc,
mySine);
This just scratches the surface. But the idea is to abstract algorithms to make them generic so that they can be reused in many different contexts.
modified on Sunday, July 20, 2008 9:14 PM
