Templates in blitter functions

[Eric Fortier]

Hi all,

Last year I posted a message regarding templates use in blitter functions, but
the single answer I got didn't help.

My problem is that I was writing blitter functions which takes a "Flag"
argument which may radically change the behavior of a function. I have read
that the best way to handle this particular issue was with meta-programming
using templates, as can be read on this page:

http://www.gapidraw.com/gapidraw-features.php
(in the section about templates)

I must now continue that project and I am faced with that same old problem with
an even larger increase in complexity. The number of possible flags for the
main "BltFast()" function alone is around 10, meaning that I either bloat and
slow the inner loop with tons of if/then/else, or I find a new way to manage
the complexity.

I'm working for devices with a very limited CPU in term of speed, so every
cycle count. Are templates a way to solve my problem?

Any information would be welcome. I spent quite a bit of time investigating
this, but still have no idea how templates can help me in this case.

--Eric

 

[Owen Jacobson]

Hi all,

Last year I posted a message regarding templates use in blitter functions, but
the single answer I got didn't help.

My problem is that I was writing blitter functions which takes a "Flag"
argument which may radically change the behavior of a function. I have read
that the best way to handle this particular issue was with meta-programming
using templates, as can be read on this page:

http://www.gapidraw.com/gapidraw-features.php
(in the section about templates)

I must now continue that project and I am faced with that same old problem with
an even larger increase in complexity. The number of possible flags for the
main "BltFast()" function alone is around 10, meaning that I either bloat and
slow the inner loop with tons of if/then/else, or I find a new way to manage
the complexity.

I'm working for devices with a very limited CPU in term of speed, so every
cycle count. Are templates a way to solve my problem?

Are you familiar with the idea of a code smell[0]? Having one method do
more than one thing based on a flag value is a code smell. It doesn't
mean the design is wrong in and of itself, but it's a really good
indicator.

Without seeing any actual code, the number of suggestions anyone can offer
is strongly limited, but here's an idea:

Break the BltFast function into independent functions that perform one
part of the blt process and have no flags at all. Then consider either
the Decorator[1] or the Template Method[2] pattern for controlling which
of or which group of individual functions are composed into the final
function.



[0] <http://c2.com/cgi/wiki?CodeSmell>
[1] <http://c2.com/cgi/wiki?DecoratorPattern>
[2] This has nothing to do with C++ templates. See
<http://c2.com/cgi/wiki?TemplateMethodPattern>

 

[Eric Fortier]

Hi Owen, thanks for your reply.

Are you familiar with the idea of a code smell[0]? Having one method do
more than one thing based on a flag value is a code smell. It doesn't

You are right. I'm looking into cleaning that code.

Without seeing any actual code, the number of suggestions anyone can offer
is strongly limited.

Ok, here are a few examples (minus any setup code).

Normal (source copy) Blt loop:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{
lpDest[x] = lpSrc[x];
}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

Now a Blit with source color keying:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{
if( ColorKey != lpSrc[x] )
{
lpDest[x] = lpSrc[x];
}
}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

Now an Alpha blit:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{
if( Alpha != 0 )
{
lpDest[x] = CALCULATE_ALPHA( src, dest );
}
}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

(this is all unoptimized code for better understanding what it does)

Now, you can combine alpha with color keying which leads to one more if() check
in the inner loop. I am asked to add at least two other draw mode (multiply &
invert) that also must combine with normal, color keying and alpha blending.

The number of loops is quickly getting out of control. And this is without
mentioning the setup code which also weights in (in term of if()s).

And replicating code all over the place is also a smell I don't like! The
reason I use flags is to get an interface that closely mimics DirectX and other
graphics library which also use such an interface.

Break the BltFast function into independent functions that perform one
part of the blt process and have no flags at all. Then consider either
the Decorator[1] or the Template Method[2] pattern for controlling which
of or which group of individual functions are composed into the final
function.

I'd look into that but I can't view the pages you provided in either IE or
Firefox.

Thanks again,

 

[Owen Jacobson]

Ok, here are a few examples (minus any setup code).

Normal (source copy) Blt loop:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{

/* Pixel function--> */

lpDest[x] = lpSrc[x];

/* <--Pixel function */

}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

Now a Blit with source color keying:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{

/* Pixel function--> */

if( ColorKey != lpSrc[x] )
{
lpDest[x] = lpSrc[x];
}

/* <--Pixel function */

}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

Now an Alpha blit:

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{ /* Pixel function --> */
if( Alpha != 0 )
{
lpDest[x] = CALCULATE_ALPHA( src, dest );
} /* <-- Pixel function */
}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

(this is all unoptimized code for better understanding what it does)

Now, you can combine alpha with color keying which leads to one more if() check
in the inner loop. I am asked to add at least two other draw mode (multiply &
invert) that also must combine with normal, color keying and alpha blending.

I've added /* Pixel function--> */ /* <--Pixel function */ markers to the
code to demarcate the parts of the three loops that are different. You
could write all three as

for( int y=0 ; y<h ; ++y )
{
for( int x=0 ; x<w ; ++x )
{
pixelFunction (lpDest[x], lpSource[x]);
}
lpDest += nPitchY;
lpSrc += nSrcWidth;
}

Then the question is, what type is pixelFunction? I did a bit of
experimentation and came up with something that both works and allows for
stateful functions like your alpha conversion function, which rely on
information specific to the function.

// BEGIN blitter.cpp
#include <iostream>

void passthrough (int &dest, const int &src) {
dest = src;
}

void invert (int &dest, const int &src) {
dest = ~src;
}

struct adder {
adder (int c):
constant (c)
{}

void operator () (int &dest, const int &src) {
dest = src + constant;
}

private:
const int constant;
};

template<typename Filter>
void arrayblit (int dest[], const int src[], std::size_t ints, Filter f) {
for (int i = 0; i < ints; ++i)
f(dest, src);
}

int main () {
int src[] = {1, 2, 3, 4, 5};
int copied[5];
int flipped[5];
int added[5];

arrayblit (copied, src, 5, passthrough);
arrayblit (flipped, src, 5, invert);
arrayblit (added, src, 5, adder(2));

for (int i = 0; i < 5; ++i)
std::cout << src << '\t'
<< copied << '\t'
<< flipped << '\t'
<< added << std::endl;
}
// END blitter.cpp

With a bit of prodding I was able to get g++ to inline the first two pixel
functions into the template instantiations rather than invoking the pixel
function through a function pointer.

Break the BltFast function into independent functions that perform one
part of the blt process and have no flags at all. Then consider either
the Decorator[1] or the Template Method[2] pattern for controlling
which of or which group of individual functions are composed into the
final function.

I'd look into that but I can't view the pages you provided in either IE
or Firefox.

Weird. The c2 wiki contains the simplest HTML you'll probably find on the
internet at large. Any sign of an error message so I can at least let
them know what's wrong?

 

[Eric Fortier]

Owen,

Then the question is, what type is pixelFunction? I did a bit of
experimentation and came up with something that both works and allows for
stateful functions like your alpha conversion function, which rely on
information specific to the function.

I had to look at your code quite a bit in order to understand it. Since you
came up with this code on your own it's pretty clear that your skills surpass
mine by a fair bit.

void operator () (int &dest, const int &src)

I didn't knew you could override the function operator!

template<typename Filter>

And I sure didn't knew you could do THAT with templates.

After a bit of retooling, I was able to write a blit function that takes a
pixel shader class as input and have that shader inlined into the main loop. I
can now call the blit function like this:

ShaderBlit( CInvertPixelsShader(), x, y, Surface, Rect, Flags );

I can pass whatever arguments I need into the shader class and that ends up
inlined into the blit function too.

And along the way I was able to get rid of a whole level of abstraction into my
graphics engine. Thanks for taking some of your time on this, it helped me
solve a problem and learn quite a few things.

Weird. The c2 wiki contains the simplest HTML you'll probably find on the
internet at large. Any sign of an error message so I can at least let
them know what's wrong?

I just get a blank white page in both browser and the page source is empty. I
don't have problems browsing anywhere else. Pretty weird.

Thanks again.

 

[Owen Jacobson]

I didn't knew you could override the function operator!

Oh, indeed. Functors -- objects that act like functions -- are incredibly
useful for a lot of things, not least STL-heavy programming. Most STL
algorithms take a function or functor.

After a bit of retooling, I was able to write a blit function that takes
a pixel shader class as input and have that shader inlined into the main
loop. I can now call the blit function like this:

ShaderBlit( CInvertPixelsShader(), x, y, Surface, Rect, Flags );

I can pass whatever arguments I need into the shader class and that ends
up inlined into the blit function too.

I see you still have 'Flags' as an argument; I assume this pattern lets
you reduce the number of flags but not, so far eliminate them entirely?
I'd be interested in seeing what else the flags control that could be
turned into a strategy function/functor.

And along the way I was able to get rid of a whole level of abstraction
into my graphics engine. Thanks for taking some of your time on this, it
helped me solve a problem and learn quite a few things.

No problem. It was an interesting challenge, actually; my own template
metaprogramming skills are a bit weak. Normally I'd implement this
pattern with an abstract base class for the functor interface and an
instance pointer/reference as an argument, because I'd find it clearer,
but for speed-intensive applications a version that's nearly as readable
that can be inlined by the compiler is handy.

Thanks for giving me the idea!