Introduction

Image crossfading is a kind of alpha blending where a final pixel is the result of linear interpolation of pixels from two images:

result_pixel = pixel1 * alpha + pixel2 * (1 - alpha)

where alpha lie in range [0, 1]. Of course when operating on "pixels" color components are considered; components are unsigned bytes.

SSSE3 introduced instruction PMADDUBSW. This instruction multiply a destination vector of unsigned bytes by a source vector of signed bytes — the result is a vector of signed words. Then adjacent words are added with signed saturation (the same operation as PHADDSW).

This is exactly what crossafading needs.

The obvious drawback is that instruction operates on signed values. Because alpha must be positive, this reduces resolution of alpha from 8 to 7 bits. (was: Because multiplication results are signed and then added, the sum must not be greater than 32767 — this requirement reduces resolution by another bit. Finally alpha must lie in range [0..63].) Dmitry Petrov pointed out that alpha can be a 7-bit value, as such value never cause an overflow. Let's assume that both pixel1 and pixel2 have maximum value, and check if following inequality is true:

(1) 255 * alpha + 255 * (127 - alpha) < 2^15 - 1
(2)                         255 * 127 < 2^15 - 1
(3)                             32385 < 32767

Obviously the inequality is true.

Algorithm outline

1. Prepare constant vector of 127*alpha/127*(1-alpha):

   xmm6 = packed_byte(alpha, 127-alpha, alpha, 127-alpha, ..., alpha, 127-alpha)
   

2. Load 16 components from images X and Y:

   movdqa (%eax), %xmm0    // xmm0 = packed_byte(rX1, gX1, bX1, _, rX2, gX2, bX2, _, ...)
   movdqa (%ebx), %xmm1    // xmm1 = packed_byte(rY1, gY1, bY1, _, rY2, gY2, bY2, _, ...)
   

3. Interleave components:

   movdqa    %xmm0, %xmm2
   punpcklbw %xmm1, %xmm0  // xmm0 = packed_byte(rX1, rY1, gX1, gY1, bX1, bY2, ...)
   punpcklbw %xmm1, %xmm2  // xmm2 = packed_byte(rX8, rY8, gX10, gY10, bX11, bY11, ...)
   

4. Interpolate components with PMADDUBSW:

   pmaddubsw %xmm6, %xmm0  // xmm0 = packed_byte(127*((rX1 * alpha) + rY1*(1 - alpha)), ...)
   pmaddubsw %xmm6, %xmm2  // xmm2 = packed_byte(127*((rX8 * alpha) + rY8*(1 - alpha)), ...)
   

5. Divide by 64 — now all words lie in range [0..255]:

   psrlw       $16, %xmm0  // xmm0 = packed_byte((rX1 * alpha) + rY1*(1 - alpha), ...)
   psrlw       $16, %xmm2  // xmm2 = packed_byte((rX8 * alpha) + rY8*(1 - alpha), ...)
   

6. Pack words to bytes and save result:

   packuswb  %xmm2, %xmm0
   movdqa    %xmm0, (%ecx)
   

7. goto 2

SWAR

Crossfading using SWAR approach is possible and on 64-bit machines is pretty fast. The core SWAR idea is to perform 4 multiplications using single multiplication instruction. When a register has following byte layout:

[00aa|00bb|00cc|00dd]

then multiplication by value in range [0..255] yields a vector of four 16-bit values.

Sample program

Sample program contains following procedures:

• x86 — C implementation (blend);
• SSE4 — SSE approach: first components are extended from byte to word, then multiply with PMULUHW and finally packed back (SSE4_blend); I called it SSE4 because for extending instruction PMOVZXBW is used, however this task could be accomplished with an old good PUNPCKxBW;
• SSE4-2 — implementation of above algorithm (SSE42_blend);
• swar — implementation of SWAR;
• SSE(1) — SSE translation of the SWAR algorithm;
• SSE(2) — SSE translation of the SWAR algorithm, with reduced numbers of shifts.

Test results

Program was compiled with following options:

gcc -O3 -Wall -pedantic -std=c99 mix_32bpp.c -o mix

Image 1024 x 768 pixels were crossfaded 100 times, total time is given

Conclusions

• And what is worth to note that gcc invoked with the -O3 switch produced quite fast x86 code. Without any optimization x86 code was almost 10 times slower! I am surprised, and in my private ranking of the best open source application GCC has gone up.