Mixing Two 16 Bits Colors

[Dr_Ian]

Yeah that's why it has the:
if (b1>0x001F)b1=0x001F;
part.
My code should have the exact same result as your code just with a few less shifts.

 

[gmiller1018]

I've found a solution:

		unsigned short r1,v1,b1;
		for (iii=0;iii<screenWH;iii++)
		{

		b1=(koukyTiles16[iii]& 31)+(koukyTiles16[iii+screenWH]& 31);
		v1=(  (koukyTiles16[iii]& (63*32))	 )+(  (koukyTiles16[iii+screenWH]& (63*32))	 )>>5;
		r1=(  (koukyTiles16[iii]& (31*64*32))  )+(  (koukyTiles16[iii+screenWH]& (31*64*32))  )>>11;
		
		if (b1>31)b1=31;
		if (v1>63)v1=63;
		if (r1>31)r1=31;

		finalTiles16[iii] =(b1)+ (v1<<5)+(r1<<11);
		}

but it's very heavy coding !
I wish I could optimise it

Just so you know ,the code as is is just a mask operation and an add. The multiplies will never be at runtime because they are in a constant expression so they are free at runtime because the compiler did them.

 

[gmiller1018]

You might try: (sorry for the bad variable names)

		unsigned short r1,v1,b1;
		int * ptr1 = koukyTiles16, *ptr2 = koukyTiles16 + screenWH;
		int p1, p2;

		for (iii=0;iii<screenWH;iii++)
		{

		p1 = *ptr1; // single dereference (hope to keep in register)
		p2 = *ptr2; // single dereference

		b1=(p1 & 31)+(p2 & 31); // constant 5 bits or less so internal to instruction
		v1=(  (p1 & (63*32))	 )+(  (p2 & (63*32))	 )>>5;
		r1=(  (p1 & (31*64*32))  )+(  (p2 & (31*64*32))  )>>11;
		
		ptr1++; // move to next element in array
		ptr2++; // move to next element in array

		if (b1>31)b1=31;
		if (v1>63)v1=63;
		if (r1>31)r1=31;

		finalTiles16[iii] =(b1)+ (v1<<5)+(r1<<11);
		}

I did not try this so it might not be any faster ... (could be syntax errors too)

 

[rabidcow]

		unsigned short r1,v1,b1;
		if (r1>0xF800)r1=0xF800;

This condition will always be false, you're losing the carried bit because you're using shorts.

Slight improvement, hopefully:

		unsigned int rb, g;
		for (iii=0;iii<screenWH;iii++)
		{

		rb=(koukyTiles16[iii] & ~0x07E0) + (koukyTiles16[iii+screenWH] & ~0x07E0);
		g=(koukyTiles16[iii] & 0x07E0) + (koukyTiles16[iii+screenWH] & 0x07E0);
		
		if ((rb&0x0020)!=0)rb=(rb&~0x001F)-1;
		if ((rb&0x10000)!=0)rb|=0xF800;
		if ((g&0x0800)!=0)g=0x07E0;

		finalTiles16[iii] = rb | g;
		}

You also might want to see if the compiler is smart enough to convert the array accesses into pointers:

unsigned short *dest, *src;
dest = koukyTiles16;
src = koukyTiles16 + screenWH;
for (iii=screenWH;iii!=0;--iii)
{
   ...*dest...*src...;
   *dest = rb | g;
   ++dest; ++src;
}

 

[kouky]

Rabidco, your code speeded up the video display by one frame per second.
I still need to check the "convert the array accesses into pointers" thing...

Thanks to all!

 

[gmiller1018]

I missed the fact that the r1, v1, b1 were shorts so those operations take more code because the ARM registers are 32 bit and the extra code to force 16 bit answers will slow things down. So I changes the code in the following section (sorry about that). As you saw in other solutions removing the extra shifts can help too but the barrel shifter in the ARM should allow some of the operation to be combined. I assume (maybe wrongly that the code is being compiled as ARM code not thumb.

You might try: (sorry for the bad variable names)

		unsigned int r1,v1,b1;
		int * ptr1 = koukyTiles16, *ptr2 = koukyTiles16 + screenWH;
		int p1, p2;

		for (iii=0;iii<screenWH;iii++)
		{

		p1 = *ptr1; // single dereference (hope to keep in register)
		p2 = *ptr2; // single dereference

		b1=(p1 & 31)+(p2 & 31); // constant 5 bits or less so internal to instruction
		v1=(  (p1 & (63*32))	 )+(  (p2 & (63*32))	 )>>5;
		r1=(  (p1 & (31*64*32))  )+(  (p2 & (31*64*32))  )>>11;
		
		ptr1++; // move to next element in array
		ptr2++; // move to next element in array

		if (b1>31)b1=31;
		if (v1>63)v1=63;
		if (r1>31)r1=31;

		finalTiles16[iii] =(b1)+ (v1<<5)+(r1<<11);
		}

I did not try this so it might not be any faster ... (could be syntax errors too)

 

[rabidcow]

Ok, if I've done the math right, and assuming koukyTiles16 is properly aligned and screenWH is even:

const unsigned int mask = 0xF81F07E0 >> 1;
const unsigned int carry1 = 0x08010020;
const unsigned int carry2 = 0x80100400;
unsigned int *src = (unsigned int *)koukyTiles16;
unsigned int *dst = (unsigned int *)(koukyTiles16 + screenWH);
for (int n = screenWH; n != 0; n -= 2)
{
  ss = *src++;
  dd = *dst;

  // .....GGG GGG..... rrrrr... ...bbbbb
  d1 = (ss & ~(mask<<1)) + (dd & ~(mask<<1));
  // >RRRRR.. ...>BBBB B....>gg gggg....
  d2 = ((ss>>1) & mask) + ((dd>>1) & mask);

  // .....GGG GGG..... rrrrr... ...bbbbb
  //	 1		   1			1
  c1 = d1 & carry1;
  // >RRRRR.. ...>BBBB B....>gg gggg....
  // 1		   1		  1
  c2 = d2 & carry2;

  // .....GGG GGG..... rrrrr... ...bbbbb
  //	 >>>> >1	 > >>>>1	  >>>>>1  >>5
  //	  111 11*	  11111	   11111  *31
  d1 = (d1 & ~c1) | ((c1 >> 5) * 31);
  // _RRRRR.. ....BBBB B.....gg gggg....
  // >>>>>1	  >>>>> 1	>>> >>1	   >>5
  //  11111	   1111 1	 11 111*	  *31
  d2 = (d2 & ~c2) | ((c2 >> 5) * 31);

  *dst++ = d1 + (d2<<1);
}

This isn't 100% correct because it will max out green to 62 instead of 63 about half the time, but it should be close enough for most uses. Hopefully the comments explain what I'm doing (or at least trying to do).

 

[Dr_Ian]

Surely if you cast the memory to an int pointer, incrementing through it will only give every second pixel?

This condition will always be false, you're losing the carried bit because you're using shorts.

Good point...

The optimizations we have seen so far are:
1. Using pointers instead of array lookups
2. Using ints instead of shorts where possible (good!)
3. Dropping the shifts
4. Combining the r and b in to one variable (cunning)

Here is some code, trying to combine all these in to one.

	int rb, v;
	short *ptr1 = koukyTiles16, *ptr2 = koukyTiles16 + screenWH;
	int p1, p2;
	
	for (iii=0;iii<screenWH;iii++)
	{
	
	p1 = *(ptr1++);
	p2 = *(ptr2++);
	
	rb = (p1 & 0xF81F) + (p2 & 0xF81F);
	v = (p1 & 0x07E0) + (p2 & 0x07E0);
	
	if ((rb&0x0020)) rb = (rb & 0x1F800) | 0x001F;
	if ((rb&0x10000)) rb |= 0xF800;
	if ((g&0x0800)) g = 0x07E0;
	
	finalTiles16[iii] = rb | g;;
	}

And as always, it's untested...

Edit: rabidcow: that's pretty hardcore

 

[kouky]

You're all the best !

I've learn lots of coding tricks with you guys !

Is it a good thing to use pointers instead of regulars arrays whenever it's possible ?
Cause i'm now trying to add lot of pointers stuffs all along my software...
Is it always faster to opt for the "pointer" option ?

 

[kouky]

By the way, here's a screen shot of my add filter, so you can see the result of your contribution

 

[rabidcow]

Is it a good thing to use pointers instead of regulars arrays whenever it's possible ?
Cause i'm now trying to add lot of pointers stuffs all along my software...
Is it always faster to opt for the "pointer" option ?

In C and C++, a is exactly the same as *(a+B). Also, I believe the indirect load/store operations on ARM can automatically adjust the pointer at the same time. Together, this means that you can entirely eliminate one add per array reference here. It's not huge, but it is slightly faster. (and it's usually not worth it if you're not in a loop) Also, it allows you to easily count downwards, which is better because zero is the easiest number to compare against. (I guess you could have done that anyway... I want to think that it would have made a difference with the cache, but that sounds wrong.)

Shifts are very cheap (in ARM mode) if you only shift one operand on a basic operation. ISTR that they do take one extra cycle though, so they aren't completely free. (or maybe that's shifting by a register?)

a & ~b is a single instruction (bic), where you get that cheap shift on b.

Constants that can be formed with an 8 bit value rotated by an even number of bits can be encoded inline. Other constants take an extra memory access. I'm hoping that using a const int to store the masks encourages the compiler to store them in registers, mainly because I'm too lazy to check.

The biggest win though, at least as I would expect, is doing multiple operations in parallel. The original code processed 1 pixel in 3 equations, whereas my code processed 2 pixels in 2 equations. Theoretically that should triple the speed and magnify the effect of other optimizations.