GP32 Additive Blending


pea

developer
Joined
Oct 3, 2004
Messages
1,089
Age
46
Location
New Zealand
Website
www.projectitis.com
Hi all,

I have an additive blending formula, but I think it can be sped up. It has to work seperately on each channel.

Basic formula:

return min( (((dest) >> shift) & 0x1F) + (((dest) >> shift) & 0x1F), 31 )<<shift;

dest is colour (unsigned short) at destination
source is colour at source

shift is a different value for each channel - 11 for R, 5 for G and 1 for B due to the position of each channel within the 16 bits of he unsigned short.

Any obvious ways to get it faster?

'min' is obviously just
if a<b return a else return b
 
well i would make min() a macro so you don't need an extra function call everytime, but you may have been planning this anyway.

sam
 
isn't min normally a macro anyway?

pea: I can't see anything to optimize in your code, so the only thing I can suggest is check the generated code and see if that could be possibly optimized.
 
pea posted on Aug 31 2005 at 09:13 AM said:
Hi all,

I have an additive blending formula, but I think it can be sped up. It has to work seperately on each channel.

Basic formula:

return min( (((dest) >> shift) & 0x1F) + (((dest) >> shift) & 0x1F), 31 )<<shift;

dest is colour (unsigned short) at destination
source is colour at source

shift is a different value for each channel - 11 for R, 5 for G and 1 for B due to the position of each channel within the 16 bits of he unsigned short.

Any obvious ways to get it faster?

'min' is obviously just
if a<b return a else return b


Its not an obious way, but you can try to rip my sprite library routines tha basicaly do some bit trick to get rid of the if's and make less operarions.

you can get them here
http://gp32spain.com/files/utilidades/libr...GP32SDK_cpp.rar

The interesting file for you is uColor.h. There are funtions for Add, Sub & Blend two 16bits(551) colors or two paris of 16bit colors each pair on a 32bits dword. This last mode is faster ofcourse....

Unai.
 
Last edited by a moderator:
This can be sped up loads!

Basically it is a very bad idea to have comparative branching in code that needs to be fast. You should either use a look up table or think of some clever maths.

I've dug up some code i wrote a long time ago.
It was in the days of DirectX 3 and 1mb gfx cards.
Should be adaptable to GP32. (it is 16bit)
tho it's R5G6B5 format, but i can supply R5G5B5 shifts and hex values if you require.

Code:
word* p1; // pointer to src
word* p2; // pointer to dest
dword rb1, g1;
dword rb2, g2;
dword a;
[For Loop]
rb1 = *p1 & 0xf81f;
g1 = *p1++ & 0x07e0;

// this is my original code which used alpha data to blend the source sprite...
a = (dword)(*pAlpha++);
a >>= 3;
rb1 *= a;
g1 *= a;
// or for a simple additive blend this code should work...
a = 0xf;
rb1 *= a;
g1 *= a;
// now follows the pixel magic...

rb2 = *p2 & 0xf81f;
g2 = *p2 & 0x07e0;
	
a ^= 0x1f;
rb2 *= a;
g2 *= a;

rb2 += rb1;
rb2 >>= 5;
rb2 &= 0xf81f;
	
g2 += g1;
g2 >>= 5;
g2 &= 0x07e0;

*p2++ = rb2|g2;
[Next]
You can probably get rid of a few of those multiplies for simple blending.

Ok, i took a look at my code again, it's for proper src/dest alpha blending, not additive, for additive you are probably best with a lookup table to replace min(). (any index above 31 returns 31)
 
having a look at my code, it has a comparison (which is heavy on processing), 3 shifts (fast, barrel shifter), an addition and two binary ANDs.

Having a look at yours Feebles, it drops the comparison, but adds quite a few multiplies, which as far as I know are more expensive than a comparison, and still has about the same amounts of shifts and binary operations (when split down to a single channel).
 
pea posted on Aug 31 2005 at 10:04 PM said:
having a look at my code, it has a comparison (which is heavy on processing), 3 shifts (fast, barrel shifter), an addition and two binary ANDs.

Having a look at yours Feebles, it drops the comparison, but adds quite a few multiplies, which as far as I know are more expensive than a comparison, and still has about the same amounts of shifts and binary operations (when split down to a single channel).


The fastest code I can think of in an instant is:

Code:
; r2 is the destination pixel
; r3 is the source pixel
  mov	#$1f,r4  ; move constant to reg
  mov	r0,r2, lsr #11; R part in lower 5 bits
  and	r0,r0,r4; mask out non-R bits
  mov	r1,r3, lsr #11; same for the source pixel
  and	r1,r1,r4;
  add	r0,r0,r1; add the values
  cmp	r0,r4  ; compare with 31
  movgt	r4,r0  ; if greater then use 31

You can optimize further in avoiding data conflicts:

Code:
  mov	r4,#$1f  ; move constant to reg
  mov	r0,r2, lsr #11; R part in lower 5 bits
  mov	r1,r3, lsr #11; same for the source pixel
  and	r0,r0,r4; mask out non-R bits
  and	r1,r1,r4;
  add	r0,r0,r1; add the values
  cmp	r0,r4  ; compare with 31
  movgt	r4,r0  ; if greater then use 31

This is ofcourse just for one color chanel. If oyu do all channels you should interleave them ( avoiding data conflicts).
I did not made any tests or something, but using a Look-Up-Table is maybe NOT faster.
But whatever you do, don't use Branch instructions ( Pipeline flushing!)

Just a quick tip.


CORRECTION/ ADDITION:
The instruction reordering is not needed!
The ARM9 has just load-use hazards. that is:
Code:
  ldr r0, [r1]
  add r2, r0, r1

stalls the pipeline, because the loading of register r0 is not finished when the add instruction uses it.
in sequences like:
Code:
  add r0, r1, r2
  sub r4, r0, r9
"data forwarding" is taking place.

in short:
you just have to watch out for data conflicts when you use load instructions. Easy, isn't it? :)
 
Last edited by a moderator:
Well I'l post my example here so you can look at the bits arithmetic I hace use to avoid ANY comparision.

It results in about 5 "simple" instructions per color component, and even less if you preoces colous in pairs


Here some definitions for components manipulation
Code:
// --------------------------------------------------------------------------------------------------------------------
// Some 555 Color space defines.
// --------------------------------------------------------------------------------------------------------------------
  enum
  {
      COLORSPACE_555x_RED_MASK             = (0xF800),
      COLORSPACE_555x_GREEN_MASK           = (0x07C0),
      COLORSPACE_555x_BLUE_MASK            = (0x003E),
  
      COLORSPACE_555x_SATURATE_RED_BIT     = (0x10000),
      COLORSPACE_555x_SATURATE_GREEN_BIT   = (0x00800),
      COLORSPACE_555x_SATURATE_BLUE_BIT    = (0x00040),
  };
//----------------------------------------------------------------------------
// Some more defines
//----------------------------------------------------------------------------
  enum
  {
    MAXIMO_NUM_BITS_COLOR   = 5   ,
    BITS_BAJOS              = 5   ,
  
    MASCARA_A               =(COLORSPACE_555x_GREEN_MASK)                                        	,
    MASCARA_B               =(COLORSPACE_555x_RED_MASK|COLORSPACE_555x_BLUE_MASK)                	,
  
    MASCARA_SAT_A           =(COLORSPACE_555x_SATURATE_GREEN_BIT )                                ,
    MASCARA_SAT_B           =(COLORSPACE_555x_SATURATE_RED_BIT|COLORSPACE_555x_SATURATE_BLUE_BIT) ,
  
    MASCARA_A_TWICE         =( ((COLORSPACE_555x_RED_MASK|COLORSPACE_555x_BLUE_MASK)<<16)|(COLORSPACE_555x_GREEN_MASK<<0 ))  ,
    MASCARA_B_TWICE         =( ((COLORSPACE_555x_RED_MASK|COLORSPACE_555x_BLUE_MASK)<<0 )|(COLORSPACE_555x_GREEN_MASK<<16))  ,
  
    MASCARA_SAT_A_TWICE     =( ((COLORSPACE_555x_SATURATE_RED_BIT|COLORSPACE_555x_SATURATE_BLUE_BIT)<<(16-BITS_BAJOS))|(COLORSPACE_555x_SATURATE_GREEN_BIT>>BITS_BAJOS) )                              ,
    MASCARA_SAT_B_TWICE     =((((COLORSPACE_555x_SATURATE_RED_BIT|COLORSPACE_555x_SATURATE_BLUE_BIT)                 )|(COLORSPACE_555x_SATURATE_GREEN_BIT<<16)) <<(MAXIMO_NUM_BITS_COLOR-BITS_BAJOS) )
  };


Funtion to add only 2 colors
Code:
  //  This function add two 5551 colors
  //  c1 = 0x0000r1g1b1
  //  c2 = 0x0000r2g2b2
  //  return = c1+c2, saturated to white
  //   
  inline  unsigned AddColors( const unsigned c1, const unsigned c2)
  {
    //  Separacion:
    //  SetUp:
    unsigned  t1_a = (c1 & MASCARA_A);                              //  0000__g1__
    unsigned  t2_a = (c2 & MASCARA_A);                              //  0000__g2__

    unsigned  t1_b = (c1 & MASCARA_B);                              //  0000r1__b1
    unsigned  t2_b = (c2 & MASCARA_B);                              //  0000r2__b2

    //  Suma_A:
    //  Suma_B:                                                     
    t1_a  = t2_a = t1_a + t2_a;                                     //  00__gT__    * T means Total
    t1_b  = t2_b = t1_b + t2_b;                                     //  00rT__bT

    t2_a &= MASCARA_SAT_A;                                          //  00_1____    *** 1 appears ONLY where saturation happened.
    t2_b &= MASCARA_SAT_B;                                          //  01___1__    *** 1 appears ONLY where saturation happened.

    t2_a -= (t2_a>>MAXIMO_NUM_BITS_COLOR);                          //  00__11__    *** 1 appears ONLY where saturation happened.
    t2_b -= (t2_b>>BITS_BAJOS);                                     //  0011__11    *** 1 appears ONLY where saturation happened.

    t1_a |= t2_a;                                                   //  00__gS__    * S means Saturated
    t1_b |= t2_b;                                                   //  00rS__bS  

    //  Comoposicion:
    return(t1_a | t1_b);
  }


Function to ads 2 pais of colors
Code:
  //  This function add two 5551 pair
  //  c1  = 0xR1G1B1r1g1b1
  //  c2  = 0xR2G2B2r2g2b2
  //  c1  = (colorA0<<16)           | (colorB0);
  //  c2  = (colorA1<<16)           | (colorB1);
  //  res =((colorA0+colorA1)<<16)  | (colorB0+colorB1)
  inline  unsigned AddColorsTwice( const unsigned c1, const unsigned c2)
  {
    //  Separacion:
    //  SetUp:
    unsigned  t1_a = (c1 & MASCARA_A_TWICE) >> BITS_BAJOS;                          //  __R1__B1__g1
    unsigned  t2_a = (c2 & MASCARA_A_TWICE) >> BITS_BAJOS;                          //  __R2__B2__g2

    unsigned  t1_b = (c1 & MASCARA_B_TWICE) << (MAXIMO_NUM_BITS_COLOR-BITS_BAJOS);  //  __G1__r1__b1
    unsigned  t2_b = (c2 & MASCARA_B_TWICE) << (MAXIMO_NUM_BITS_COLOR-BITS_BAJOS);  //  __G2__r2__b2

    //  Suma_A:
    //  Suma_B:                                                     
    t1_a  = t2_a = t1_a + t2_a;                                                     //  __RT__BT__gT  * T means Total
    t1_b  = t2_b = t1_b + t2_b;                                                     //  __GT__rT__bT

    t2_a &= MASCARA_SAT_A_TWICE;                                                    //  _1___1___1__  *** 1 appears ONLY where saturation happened.
    t2_b &= MASCARA_SAT_B_TWICE;                                                    //  _1___1___1__  *** 1 appears ONLY where saturation happened.

    t2_a -= (t2_a>>MAXIMO_NUM_BITS_COLOR);                                          //  __11__11__11  *** 1 appears ONLY where saturation happened.
    t2_b -= (t2_b>>MAXIMO_NUM_BITS_COLOR);                                          //  __11__11__11  *** 1 appears ONLY where saturation happened.

    t1_a |= t2_a;                                                                   //  __RSxxBSxxgS  * S means Saturated
    t1_b |= t2_b;                                                                   //  __GSxxrSxxbS  * xx Garbage that appeared betwen the color components.

    t1_a  = (t1_a<<BITS_BAJOS) & (MASCARA_A_TWICE);                                 //  11xx11xx11xx  * Moves all to its correct place.
                                                                                    //  11__11__11__  * Cleans the space betwen components.   
    t1_b  = (t1_b>>MAXIMO_NUM_BITS_COLOR-BITS_BAJOS) & (MASCARA_B_TWICE);           //  11xx11xx11xx  * Moves all to its correct place.
                                                                                    //  __11__11__11  * Cleans the space betwen components.   
    //  Comoposicion:
    return(t1_a | t1_b);
  }
 
Hi all,

Thanks heaps for all your help everyone. I think I will try una-i's solution for the reason it is in pure c, but I need to adjust it so that it works with a single channel only (like creatureXL's solution) as I only need one channel at any time.

Cheers,
Pea
 
Here is my final solution. I used una-i's solution of masking out the bits higher. yet to test it:

Code:
unsigned short addColorChannel( const unsigned short dest, const unsigned short source, unsigned long shift){
   unsigned  dest_a = (dest>>shift) & 0x1F;  	// Destination colour channel in lower 5 bits
   unsigned  source_a = (source>>shift) & 0x1F;	// Source colour channel in lower 5 bits
                                                   
   dest_a  = source_a = dest_a + source_a;    // Sum of colours including overflow
   source_a &= 0x20;              	// Mask out overflow bit
   source_a -= (source_a>>5);          	// Create channel saturation mask from overflow bit
   dest_a |= source_a;              // Mask overflow
   
   return (dest & ~(0x1F<<shift)) | (dest_a & 0x1F)<<shift;	// Mask out channel and add back to dest
}

Where:
dest is colour at destination
source is colour at source
shift is dependant on channel to mix (11=R, 6=G, 1=B )

What it should do:
Blend a single channel of the source colour with the whole destination colour

Doubts:
Need to benchmark it because I have my doubts that:
5 shifts, an addition, a subtraction and 7 binary operations
is faster than:
1 comparison/branch, 3 shifts, an addition and 2 binary operations
But then, what do I know :)
 
Code:
  inline int Add(int a, int b, int hiBit, int hiMask)
  {
    int t;
    t = (a&(~hiMask)) + b;
    t = (t&(1<<hiBit)) - (t>>hiBit);
    return (a|(t&hiMask))
  }
hiBit = Overflo


I think this way is a bit more compact, But I wold recomend you to apply tje operation two pixels at a time this way the cost per pixel wold be smaller.

About the ops, the arm achitecture has what the cal "shifter" that meas that the output of any operation can be sifted by a constant for free...

Also if you are ussing c++ you cold do a function template thar gets hiBit and hiMask as compile time constants so the code would be optimiced by de compler.

Code:
  template<int hiBit,int hiMask>
  inline int AddT(int a, int b)
  {
    int t;
    t = (a&(~hiMask)) + b;
    t = (t&(1<<hiBit)) - (t>>hiBit);
    return (a|(t&hiMask))
  }

And the use wold be somthing like this...
Code:
int resColorR = AddT<(1<< 6),(0x1f<< 1)>(colA,colB);  // Modifies RED
int resColorG = AddT<(1<<11),(0x1f<< 6)>(colA,colB);  // Modifies GREEN
int resColorB = AddT<(1<<16),(0x1f<<11)>(colA,colB);  // Modifies BLUE

P.D: all the abobe code is untested so...


Unai.
 
pea posted on Sep 4 2005 at 11:35 PM said:
Here is my final solution. I used una-i's solution of masking out the bits higher. yet to test it:

Code:
unsigned short addColorChannel( const unsigned short dest, const unsigned short source, unsigned long shift){
   unsigned  dest_a = (dest>>shift) & 0x1F;  	// Destination colour channel in lower 5 bits
   unsigned  source_a = (source>>shift) & 0x1F;	// Source colour channel in lower 5 bits
                                                   
   dest_a  = source_a = dest_a + source_a;    // Sum of colours including overflow
   source_a &= 0x20;              	// Mask out overflow bit
   source_a -= (source_a>>5);          	// Create channel saturation mask from overflow bit
   dest_a |= source_a;              // Mask overflow
   
   return (dest & ~(0x1F<<shift)) | (dest_a & 0x1F)<<shift;	// Mask out channel and add back to dest
}

Where:
dest is colour at destination
source is colour at source
shift is dependant on channel to mix (11=R, 6=G, 1=B )

What it should do:
Blend a single channel of the source colour with the whole destination colour

Doubts:
Need to benchmark it because I have my doubts that:
5 shifts, an addition, a subtraction and 7 binary operations
is faster than:
1 comparison/branch, 3 shifts, an addition and 2 binary operations
But then, what do I know :)

I may sound a bit dickish, but this board is for discussing code aswell, so I wonder if my thoughts are correct AND I am still of the opinion that my code is the fastest :)

My proposal has:
2 shifts ( needed for aligning the R G B values, could be leaved out for B value!)
2 bitwise-operations ( needed to mask out all unneeded bits.
1 add ( obviusoly needed for ADDitive-blending :)
1 compare ( which is the same computation as arithmetik ( SUB)
and 1 simple move which is just executed when saturation should be done!

BTW, the "mov r4, #$1f" isn't needed, cause immeadite is as fast as register addressing, so just replace all "r4" to "#$1f", like: "and r0, r0, #$1f".

So we have 6 or 7 instructions compared to the 12 ( without branch) and the 7 ( with branch).

One of the key ideas is, that the saturated value and the AND-mask are always identical! The only thing I dont know by heart is, if the CPU issues a real NOP instruction when the condition for the "movGT" instruction isn't met and if then a pipeline flush occures as well. I see no need for that, but if it is implemented that way in the ARM 9 core, then my proposal hjas to be overthougth :)

You can further use a specilized route for every channel, then you can get rid of the shifting, dont forget, you have to shift back your result, so you can save always a shift more for R and G channles.

looks like this:
Code:
MASK_R	equ $1f << 11
MASK_G	equ $1f <<  6
MASK_B	equ $1f

; for each channel do like the following
and r0, r2, #MASK_R; mask off
and r1, r3, #MASK_R;
add r0, r0, r1                  ; mix colors
cmp r0, #MASK_R        ; check for saturation
mov r0, #MASK_R        ; saturated value ( if needed)

Further optimization is ofcourse possible when you caluclate two (16 bit) pixels in one (32-bit) word, then you have to use the carry bit for the overflow of the highest Red bit. But this approache is not so generic but ( obviuosly) delivers double the speed :)

I would recommend to compile your C code to assembnler src ( -S option in GCC if I am not mistaken) and count the instructions. Because it is not guaranteed that the C compiler translates every C instruction with one ARM 9 instruction :)

If your problem is to use the asm code, I can try to make a C macro for this ( asm statement). I never done it before, so I can't add it now.


Any corrections are highly welcomed, cause I have no time to test it and therefore can't say it is 100% correct. Sorry for this :(

salut,
creature
 
Last edited by a moderator:
Creature XL posted on Sep 5 2005 at 12:44 PM said:
I may sound a bit dickish, but this board is for discussing code aswell, so I wonder if my thoughts are correct AND I am still of the opinion that my code is the fastest
Not you dont, :p

I thing that yours ir better... I designed my set of functions to work with 6 color components at a time (two pairs of colors) later I downgraded for 3 components and were ok, but for just one componet I thing there is no advantage, and arm architectre very god with conditional moves...

So pea if you only are going to change one color componet in one color a time this solution is the best, If not we can start another thread :p

btw.. Thanks for your time creature & pea

Unai.
 
Last edited by a moderator:
If you have separate functions for R,G & B, the R version you only need to do an adds so you also set the flags.
Code:
and r0, r2, #MASK_R; mask off
and r1, r3, #MASK_R;
adds r0, r0, r1                 ; mix colors
movcs r0, #MASK_R       ; saturated value ( if needed)
for the B channel you can use:
Code:
mov r0, r2, lsl#10
adds r0, r0, r3,lsl#10     ; mix colors
movcs r0, #MASK_R       ; saturated value ( if needed)
mov r0, r0, lsr#10
 
FluBBa posted on Sep 8 2005 at 11:22 AM said:
If you have separate functions for R,G & B, the R version you only need to do an adds so you also set the flags.
Code:
and r0, r2, #MASK_R; mask off
and r1, r3, #MASK_R;
adds r0, r0, r1               ; mix colors
movcs r0, #MASK_R     ; saturated value ( if needed)
for the B channel you can use:
Code:
mov r0, r2, lsl#10
adds r0, r0, r3,lsl#10   ; mix colors
movcs r0, #MASK_R     ; saturated value ( if needed)
mov r0, r0, lsr#10

Yeah nice :) you won!
BUT I could argue that you can't use it for two-pixel-at-once things, but we ( or just me) was looking for a "generic" thing :)

Do you happen to know if the ARM9 issues a real NOP instruction which flushes the pipeline ( or better, synchronizes the pipeline when you use conditional instructions?

salut,
creature

P.S.:
I love ARM for the "shifting for free".
 
Last edited by a moderator:
I haven't read anything specific about the ARM9, but I can't see the point in designing a CPU around the idea that every opcode can be conditional and then have it act like that?
 
FluBBa posted on Sep 10 2005 at 10:55 AM said:
I haven't read anything specific about the ARM9, but I can't see the point in designing a CPU around the idea that every opcode can be conditional and then have it act like that?


Think harder then! B)
ARM design is very clever. There are a few bits at the top of the opcode (the condition) which can be completely seperated out and calculated in parallel with the opcode itself.

So at the same time as it's working out the value, it can be working out whether the condition is true. It can then, and only then, assign the result to the target register.
With other cpus you'd have to work out the condition, do the arithmetic and then save to the target. Extra work, not parallel processing.

Very very clever people in Cambridge I tell ya.
 
Last edited by a moderator:
Creature XL posted on Sep 9 2005 at 06:09 PM said:
Do you happen to know if the ARM9 issues a real NOP instruction which flushes the pipeline ( or better, synchronizes the pipeline when you use conditional instructions?
So FDave, does it issue a real NOP then? or what did you try to point out? :rolleyes:
 
Last edited by a moderator:
Back
Top