Suggestions for optimization?

Well, you could use 3dnow/sse assembly to speed this stuff up... but that''s fairly complex....

I assume a lot of your time is being taken up by floating point ops. Each of those channel lines does:
2 int->float (quick)
2 float mults (kinda slow)
1 float add (kinda slow)
1 float sub (kinda slow)
1 float->int (slow)

How ''bout something like this:

inline void Blend(const PIXEL *p, float fNewPart)
{
    unsigned short iNewPart = 256 * fNewPart;

    a = (p->a*iNewPart + a*(256-iNewPart) / 256;
    // etc.

}

This does one float-mult and one float->int for the entire function, and then uses int operations the rest of the time. Code is untested; use at your own risk.

---

How appropriate. You fight like a cow.

1) No idea how your compiler is already optimizating things...

float omf = 1-fNewPart;

Try putting this at the top of your Blend() function and use omf instead of (1-fNewPart) four times

2) Also, if you''re inling Blend, then this:

pDstCur->Blend(pCurSrc+1, fabsf(fSrcXMiss));

becomes this:

a = (BYTE)((pCurSrc+1)->a*(fabsf(fSrcXMiss)) + a*(1-(fabsf(fSrcXMiss))));
r = (BYTE)((pCurSrc+1)->r*(fabsf(fSrcXMiss)) + r*(1-(fabsf(fSrcXMiss))));
g = (BYTE)((pCurSrc+1)->g*(fabsf(fSrcXMiss)) + g*(1-(fabsf(fSrcXMiss))));
b = (BYTE)((pCurSrc+1)->b*(fabsf(fSrcXMiss)) + b*(1-(fabsf(fSrcXMiss))));

but that probably gets optimized to this, right?

const PIXEL *p = (pCurSrc+1);
float fNewPart = fabsf(fSrcXMiss);
a = (BYTE)(p->a*fNewPart + a*(1-fNewPart));
r = (BYTE)(p->r*fNewPart + r*(1-fNewPart));
g = (BYTE)(p->g*fNewPart + g*(1-fNewPart));
b = (BYTE)(p->b*fNewPart + b*(1-fNewPart));

3) Can you store floats instead of BYTEs? Does the cast add any cost?

Thanks for the suggestions so far! rypyr, I''d already implemented most of your suggestions after posting, but I didn''t think about the inlining fabsf problem. Sneftel, good idea on minimizing the FP->Fixed conversions.

Any other ideas?



~BenDilts( void );

OK, here's my somewhat updated code. Instead of several arithmetic operations, I made a lookup table for all combinations of BYTE*BYTE/255. The population code for the lookup table is not listed here, but it is in essence:

bBlendLookups[j][t] = j*t/255;
   

OK, here's my latest attempt. Any other suggestions are welcome!



~BenDilts( void );

BYTE bBlendLookups[256][256];

struct PIXEL
{
	BYTE r;
	BYTE g;
	BYTE b;
	BYTE a;
};
#define BLEND(x,y,p) { 		if(*((DWORD*)x) != *((DWORD*)y))		{			bNewPart = (BYTE)(p*255.0f);			bOldPart = 255-bNewPart;			x->r = bBlendLookups[y->r][bNewPart] + bBlendLookups[x->r][bOldPart];			x->g = bBlendLookups[y->g][bNewPart] + bBlendLookups[x->g][bOldPart];			x->b = bBlendLookups[y->b][bNewPart] + bBlendLookups[x->b][bOldPart];		}}

STDMETHODIMP CESAntiAliaser::AntiAlias(SAFEARRAY **aData, long lWidth, long lHeight, long lNewWidth, long lNewHeight, SAFEARRAY **aResult)
{
 	//aData is a byte array containing 32-bit color data for an image, elements are from 0 to lWidth*lHeight*4

 
 	SAFEARRAYBOUND rgsabound[1];
 	rgsabound[0].lLbound = 0;
 	rgsabound[0].cElements = lNewWidth*lNewHeight*4;
 
 	*aResult = SafeArrayCreate(VT_I1/*BYTE*/, 1, rgsabound);
 
 	PIXEL *pSrc = NULL;
 	PIXEL *pDst = NULL;
 	SafeArrayAccessData(*aData, (void**)&pSrc);
 	SafeArrayAccessData(*aResult, (void**)&pDst);
 
 	PIXEL *pDstCur = pDst;

	float fSrcX = 0, fSrcY = 0;
	float fDeltaSrcX = (float)lWidth/(float)lNewWidth;
	float fDeltaSrcY = (float)lHeight/(float)lNewHeight;

	long iSrcX, iSrcY;
	float fSrcXMiss, fSrcYMiss;
	float fAbsSrcXMiss, fAbsSrcYMiss;
	PIXEL *pCurSrc;
	BYTE bNewPart, bOldPart;

	long iYOffset;
	for(long y = 0; y < lNewHeight; y++)
 	{
		iSrcY = (long)(fSrcY+.5f);
		fSrcYMiss = fSrcY-iSrcY;
		fAbsSrcYMiss = fabsf(fSrcYMiss);
		iYOffset = iSrcY*lWidth;

 		for(long x = 0; x < lNewWidth; x++)
 		{
			iSrcX = (long)(fSrcX+.5f);
			fSrcXMiss = fSrcX-iSrcX;
			fAbsSrcXMiss = fabsf(fSrcXMiss);
			
			pCurSrc = pSrc + (iSrcX+iYOffset);
 			*pDstCur = *pCurSrc;
			
			if(fSrcXMiss > 0 && iSrcX+1 < lWidth)
				BLEND(pDstCur, (pCurSrc+1), fAbsSrcXMiss) //pDstCur->Blend(pCurSrc+1, fabsf(fSrcXMiss));

			else if(fSrcXMiss < 0 && iSrcX > 0)
				BLEND(pDstCur, (pCurSrc-1), fAbsSrcXMiss) //pDstCur->Blend(pCurSrc-1, fabsf(fSrcXMiss));


			if(fSrcYMiss > 0 && iSrcY+1 < lHeight)
				BLEND(pDstCur, (pCurSrc+lWidth), fAbsSrcYMiss) //pDstCur->Blend(pCurSrc+lWidth, fabsf(fSrcYMiss));

			else if(fSrcYMiss < 0 && iSrcY > 0)
				BLEND(pDstCur, (pCurSrc-lWidth), fAbsSrcYMiss) //pDstCur->Blend(pCurSrc-lWidth, fabsf(fSrcYMiss));


 			pDstCur++;
			fSrcX += fDeltaSrcX;
 		}
		fSrcX = 0;
		fSrcY += fDeltaSrcY;
 	}
 
 	SafeArrayUnaccessData(*aData);
 	SafeArrayUnaccessData(*aResult);

	return S_OK;
}
  

[edited by - BeanDog on August 5, 2003 10:15:55 AM]

[edited by - BeanDog on August 8, 2003 8:39:20 AM]

PLEASE use the [ s o u r c e ] [ / s o u r c e ] (no spaces) tags instead of the code ones

What kind of speedups did those changes make?

Putting a mul in a LUT has never been of use for me, the CPU does the work pretty quickly.
Also, you can rid one mul:

a0*(1-t) + a1*t =
a0 + t(a1 - a0)

coelurus: good call.
With all the improvements, I''m up to about a 20% speed increase.

Further suggestions welcome :-)



~BenDilts( void );

iSrcX = (int)(fSrcX+.5f);
iSrcY = (int)(fSrcY+.5f);
fSrcXMiss = fSrcX-iSrcX;
fSrcYMiss = fSrcY-iSrcY;

move the Y calculations to the outer loop
and precalculate the X ones once.

I did this @home and reduced the loop overhead
with 67%

also for a big speed gain split the loop into multiple
parts for boundry cases and one for the general case

(i.e. one for top, bottom, most left, most right)
and one loop that takes the interior

that way you get rid of the if for every pixel
that should give you an enormous speed gain

I heard a lot of think about slowness of if statements. I remember that it destroys the pipelining so slow much.

You can get rid of if statement using function pointers.

Here is some code that does something like that

  #include <stdio.h>

  void func1(int a)
  {
    printf("func1 %d\n",a);
  }

  void func2(int a)
  {
   printf("func2 %d\n",a);
  }


ypedef void (*tpfunc) (int);

  void main()
  {
    int i;

    printf("\n\n");

    tpfunc pfunc[2];
    pfunc[0]=func2;
    pfunc[1]=func1;
.
    for (i=0;i<10;i++)
    {
/// Origonal if statement

/*      if (i%3==1)
          func1(1);
       else
          func2(1);
 */
/// Here is the function that does the same job with if statement

      pfunc[i%3==1](222);
    }
  }

This shows how you can get rid of if statement.
Here is a link about function pointers.
http://www.function-pointer.org/

Not sure if it''s already been tried, but if you can keep the calcs into int-range with FPM, use it. FPM is slow only when you account for over/under-flows. Also, mixing floats with frame-buffer operations isn''t the best I think (lotsa casts).

Chaging the blend range from 0 - 1 to 0 - 256 would give
a huge increase, also the conversion coupled with precalculation
would effectivly remove FP from the innermost loop leaving
but a few conversion steps in the outermost (Y) loop
and FPM (Fixed Point Math) could get rid of those too.

Using 0 -> 256 for blend range gave me a 4x speed up on the blend routine, though it does give a slightly diffrent result due
to rounding but it''s +-1 and rare.

Excellent job! It is now approximately 10 times faster than it was. Almost every suggestion was useful. Here's the code as it now stands (too bad the [ s o u r c e ] tags make my BLEND #define turn into one line):

struct PIXEL
{
	BYTE r;
	BYTE g;
	BYTE b;
	BYTE a;
};

#define BLEND(x,y,p) { 		if(*((DWORD*)(x)) != *((DWORD*)(y))) 		{ 			bNewPart = (BYTE)((p)*255.0f); 			(x)->r = bNewPart*((y)->r - (x)->r)/255 + (x)->r; 			(x)->g = bNewPart*((y)->g - (x)->g)/255 + (x)->g; 			(x)->b = bNewPart*((y)->b - (x)->b)/255 + (x)->b; 		} }

#define SGNFNX(x) ((x)<0 ? -1 : 1)
#define SGNFNY(y) ((y)<0 ? -lWidth : lWidth)

STDMETHODIMP CESAntiAliaser::AntiAlias(SAFEARRAY **aData, long lWidth, long lHeight, long lNewWidth, long lNewHeight, SAFEARRAY **aResult)
{
 	//aData is a byte array containing 32-bit color data for an image, elements are from 0 to lWidth*lHeight*4

 
 	SAFEARRAYBOUND rgsabound[1];
 	rgsabound[0].lLbound = 0;
 	rgsabound[0].cElements = lNewWidth*lNewHeight*4;
 
 	*aResult = SafeArrayCreate(VT_I1/*BYTE*/, 1, rgsabound);
 
 	PIXEL *pSrc = NULL;
 	PIXEL *pDst = NULL;
 	SafeArrayAccessData(*aData, (void**)&pSrc);
 	SafeArrayAccessData(*aResult, (void**)&pDst);
 
 	PIXEL *pDstCur = pDst;

	float *fSrcX, fSrcY = 0;
	float fDeltaSrcX = (float)(lWidth-2)/(float)lNewWidth;
	float fDeltaSrcY = (float)(lHeight-2)/(float)lNewHeight;

	long *iSrcX, iSrcY;
	float *fSrcXMiss, fSrcYMiss;
	float *fAbsSrcXMiss, fAbsSrcYMiss;
	PIXEL *pCurSrc;
	PIXEL *pCurBase;
	BYTE bNewPart;

	fSrcXMiss = new float[lNewWidth];
	fAbsSrcXMiss = new float[lNewWidth];
	iSrcX = new long[lNewWidth];
	fSrcX = new float[lNewWidth];

	long x,y;
	float f = 1;

	for(x = 0; x < lNewWidth; x++)
	{
		fSrcX[x] = f;
		iSrcX[x] = (long)(fSrcX[x]+.5f);
		fSrcXMiss[x] = fSrcX[x]-iSrcX[x];
		fAbsSrcXMiss[x] = fabsf(fSrcXMiss[x]);
		f += fDeltaSrcX;
	}
	long lYSgnFn;
	long iYOffset;
	for(y = 0; y < lNewHeight; y++)
 	{
		iSrcY = (long)(fSrcY+.5f);
		fSrcYMiss = fSrcY-iSrcY;
		fAbsSrcYMiss = fabsf(fSrcYMiss);
		iYOffset = iSrcY*lWidth;
		pCurBase = pSrc + iYOffset;
		lYSgnFn = SGNFNY(fSrcYMiss);

 		for(x = 0; x < lNewWidth; x++)
 		{
			pCurSrc = pCurBase + iSrcX[x];
 			*pDstCur = *pCurSrc;
			
			BLEND(pDstCur, pCurSrc+SGNFNX(fSrcXMiss[x]), fAbsSrcXMiss[x]);
			BLEND(pDstCur, pCurSrc+lYSgnFn, fAbsSrcYMiss);

 			pDstCur++;
 		}
		fSrcY += fDeltaSrcY;
 	}
 
	delete [] fSrcXMiss;
	delete [] fAbsSrcXMiss;
	delete [] iSrcX;
	delete [] fSrcX;

 	SafeArrayUnaccessData(*aData);
 	SafeArrayUnaccessData(*aResult);

	return S_OK;
}

Again, further suggestions are very welcome.

Note that there is still (in the BLEND macro) an 'if' statement in the very inner loop. While this is generally not a good idea, since I'm working with screenshot data mostly it quite often (90% of the time) saves me from running the whole BLEND routine.



~BenDilts( void );

[edited by - BeanDog on August 8, 2003 9:07:11 AM]

[edited by - BeanDog on August 8, 2003 9:13:09 AM]

I would suggest using

inline void BLEND(PIXEL *x, const PIXEL *y,float fBlend)
{ 
	if(*((DWORD*)(x)) != *((DWORD*)(y)))
	{ 			
		int iNewPart = fBlend * 256.0f; 			
		x->r += iNewPart * (y->r - x->r) >> 8; 			
		x->g += iNewPart * (y->g - x->g) >> 8; 			
		x->b += iNewPart * (y->b - x->b) >> 8; 		
	}
}

instead of the blend macro, for clarity and you could use
__forceinline to get the macro effect.

also for possible better locality (meaning less chache trashing
don't use separate arrays for your precalculated data put them into a struct instead (i.e. giving you one array instead of 4)

[edited by - DigitalDelusion on August 8, 2003 9:31:31 AM]

[edited by - DigitalDelusion on August 8, 2003 9:32:30 AM]

Dunno if anyone follows this thread any longer
but this is a resonible MMX implementation of the blend
function cuts that routine with ~40%
assumes MSVC++

void PIXEL::Blend( const PIXEL *p, int iNewPart)
{
	_asm
	{
			mov		ebx, p
			mov		ecx, this
			punpcklbw mm0, [ebx] 
			movd	mm7, [ecx]
			punpcklbw mm1, mm7
			psrlw	mm0, 8
			psrlw	mm1, 8

			psubw	mm0, mm1

			movd	mm2, iNewPart
			movq	mm3, mm2
			psllq	mm3, 16
			por		mm2, mm3
			movq	mm3, mm2
			psllq	mm3, 32
			por		mm2, mm3

			pmullw	mm0, mm2
			psrlw	mm0, 8

			packuswb mm0, mm0
			paddb	mm7, mm0
			movd	[ecx], mm7
			emms
	}
}

[edited by - DigitalDelusion on August 12, 2003 6:37:42 AM]

Oh, I'm still following this thread. Thanks a whole heap! That routine helped speed it up a little bit more, though not a whole lot... it actually slowed it down until I put back in my if(x!=y) statement. My images are screenshots and so that if statement can completely bypass the blending code 95% of the time.

At this point, I can process a 1500x1500 image in about 0.14 seconds, which is plenty fast. The bottleneck is now in GetDIBits and SetDIBits, which I just cannot optimize :-( Oh well. Thanks a heap!



~BenDilts( void );

[edited by - BeanDog on August 12, 2003 9:02:19 AM]

Get rid of that emms, it''s a terribly slow instruction. Do it by writing the loop in assembly as well, and doing all float-point stuff with SSE instead of FPU. I''m having exams so sorry I can''t show you my implementation but I''m sure it can be 300% faster!

quote:

---

Original post by BeanDog
Oh, I''m still following this thread. Thanks a whole heap! That routine helped speed it up a little bit more, though not a whole lot... it actually slowed it down until I put back in my if(x!=y) statement. My images are screenshots and so that if statement can completely bypass the blending code 95% of the time.



~BenDilts( void );

---

Well, ofcourse it won''t increase speed terribly much if you skip
that portion 95% of the time =)

But if you ever come to a situation where you actually need
to blend every pixel you''ll notice the differance

quote:

---

Original post by C0D1F1ED
Get rid of that emms, it''s a terribly slow instruction. Do it by writing the loop in assembly as well, and doing all float-point stuff with SSE instead of FPU. I''m having exams so sorry I can''t show you my implementation but I''m sure it can be 300% faster!

---

Well, If rewriting the whole thing is an option it would be
quite possible to get much better throughput but that''s to
classify as major surgery, everything done henceforth is
local enhancements.