Alpha-blending per one-pixel multiplication on Windows Mobile

Those who were engaged in graphics on Windows Mobile, probably heard about the graphics library GapiDraw . If you look at their Feature List , then in the High Performance section you can find the following words: "drawing surfaces with opacity". That is, they claim that it takes only one multiplication per pixel to draw translucent images.

In this article I will try to explain how this is possible.

First, most Windows Mobile devices have a screen with 65 thousand colors. That is, for each pixel on the screen, 2 bytes are allocated in memory. Secondly, such devices have a 32-bit processor. On such a processor, the speed of performing mathematical operations with 2-byte numbers differs little from the speed of working with 4-byte numbers. This is where one of the computation optimizations is hidden. The graphics library processes 2 pixels at a time.

Let's see how the 16-bit pixel works. The upper 5 bits are reserved for red, then 6 bits - for green and the remaining 5 bits - for blue.

P = [RRRR RGGG GGGB BBBB] 15 8 7 0 

At the same time, the colors themselves can be obtained using shifts and masks according to the formulas:

 int R = (P >> 11) & 0x1f; int G = (P >> 5) & 0x3f; int B = P & 0x1f; 

And the pixel is obtained by the inverse transformation:

 unsigned short P = (R << 11) + (G << 5) + B; 

When we try to draw one pixel on top of another with transparency, the colors are mixed. Both pixels are divided into 3 components: red, blue, green. Then the components are mixed, the red is mixed with red, the blue with blue, and the green with green. And from the obtained values ​​a new pixel is composed.
')
In general, the color mixing looks like this:

 C = C1*α + C2*(1 - α) 

C1 - the value of red, green or blue from the first pixel.
C2 - the value of the same color in the second pixel.
C is the resulting color.
α - coefficient of transparency, takes values ​​from 0 to 1.

It’s quite expensive to store the real value of α, especially on handheld computers, so it is limited to a certain integer range. Usually, values ​​of 0-255 are used, but for 5-bit color, 5-bit α will suffice.

First, let's pay attention to how colors are mixed with 50% transparency:

 C = C1/2 + C2/2 

The division by 2 can be replaced by a shift:

 C = (C1 >> 1) + (C2 >> 1) 

Now let's see what happens when two pixels are mixed one by one:

 P = (R1 >> 1 + R2 >> 1) << 11 + (G1 >> 1 + G2 >> 1) << 5 + (B1 >> 1 + B2 >> 1) 

Opening the brackets we get:

 P = (P1 & 0xf7de) >> 1 + (P2 & 0xf7de) >> 1 

The mask 0xf7de appears to ensure the correct shift by 1 in each color component. Compare:

 [RRRR RGGG GGGB BBBB] = P [0RRR RRGG GGGG BBBB] = P >> 1 //         [RRRR RGGG GGGB BBBB] = P [1111 0111 1101 1110] = 0xf7de [RRRR 0GGG GG0B BBB0] = P & 0xf7de //      [0RRR R0GG GGG0 BBBB] = P & 0xf7de >> 1 

Similar to this method, you can do the same operations for mixing pixels 1 to 3, 1 to 7 ... But in this respect, this method is completely ineffective, mainly due to the fact that the division goes before multiplication. Therefore, you must first make room for multiplication. Note that multiplying the m-bit unsigned number by n-bit, we get a number occupying no more than m + n bits. That is, it is necessary to release 5 bits before each color, and for this you can divide the pixel colors into even and odd and operate with them. So we come to the following blending procedure using 2 multiplications per pixel:

 #define Shift(p) ((p)>>5) #define OddCol(p) ((p) & 0x07E0F81F) #define EvenCol(p) ((p) & 0xF81F07E0) //      2  register unsigned int p1 = *dst; register unsigned int p2 = *(src++); //  4 ,    2   *(dst++) = OddCol( Shift(OddCol(p1)*a + OddCol(p2)*(32 - a)) ) | EvenCol( Shift(EvenCol(p1))*a + Shift(EvenCol(p2))*(32 - a) ); 

How to get rid of another multiplication? Let's try to open the brackets and regroup the items:

 C = (C1*α + C2*(32 - α)) >> 5 = (C1 - C2)*α >> 5 + C2 

But in parentheses you can get a negative number, and arithmetic operations with negative numbers are based on overflow. Thus, it is impossible to apply the formula in this form to parallelize the calculations. Therefore, we get rid of negative values ​​by adding the maximum possible:

 C = (C1 - C2 + 32 - 32)*α >> 5 + C2 = (C1 - C2 + 32)*α >> 5 + C2 - α 

Using this formula and a trick with even and odd colors, you can get a pixel blending procedure that uses just one multiplication per pixel:

 #define OddCol(p) ((p) & 0x07E0F81F) #define EvenCol(p) ((p) & 0xF81F07E0) register unsigned int p1 = *dst; register unsigned int p2 = *(src++); register unsigned int oddA = (a<<22) | (a<<11) | (a); register unsigned int evenA = (a<<27) | (a<<16) | (a<<6); register unsigned int oddP2 = OddCol(p2); register unsigned int evenP2 = EvenCol(p2); // 2    2  oddCol = (((OddCol(p1) - oddP2 + 0x08010020) * a) >> 5) + oddP2 - oddA; evenCol = ((( (EvenCol(p1)>>5) - (evenP2>>5) + 0x08010040) * a) + evenP2 - evenA ); *(dst++) = OddCol(oddCol) | EvenCol(evenCol);