Anyone interested in efficient RGB blending?
While this is not an algorithm per se, more like bit ops tips, the underlying idea — SIMD-like operations on unsigned integers with field width sufficient for intermediate results, and unpacking packed numeric fields for this by shifting every second field up by a full record width — is an interesting method; close enough to a neat algorithm to be noted here, IMHO.
If you have two ARGB colors as 32-bit unsigned integers, you only need five bit shifts, six binary and operations (that use one of two 32-bit masks), one binary or operation, and two additions, to calculate their 50% blend:
static inline uint32_t argb8888_blend_half(const uint32_t argb1, const uint32_t argb2)
{
const uint32_t rb1 = (argb1 << 7) & 0x7F807F80u,
ag1 = (argb1 >> 1) & 0x7F807F80u,
rb2 = (argb2 << 7) & 0x7F807F80u,
ag2 = (argb2 >> 1) & 0x7F807F80u;
return (((rb1 + rb2) & 0xFF00FF00u) >> 8)
| ((ag1 + ag2) & 0xFF00FF00u);
}
The exact same approach (just different numeric constants) can be used to calculate 25%, 12.5%, 6.25%, 3.125%, 1.5625%, 0.78125%, and 0.390625% blends as well.
On 64-bit architectures, expanding the above constants to 64-bit, you can do those blends for two different pairs of color values at roughly the same cost (depending on whether the color values are already packed, or if you need to repack them; so the difference is just some ANDs, ORs, and bit shifts at most).
On 64-bit architectures, an arbitrary ARGB8888 blend only needs two (56×9=64 bit) multiplications, four shifts, six binary ands, three binary ors, one subtraction, and one addition:
static inline uint32_t argb8888_blend(const uint32_t argb0,
const uint32_t argb1,
const unsigned int p)
{
const uint64_t c0 = (argb0 & 0x00FF00FF) | ((uint64_t)(argb0 & 0xFF00FF00) << 24),
c1 = (argb1 & 0x00FF00FF) | ((uint64_t)(argb1 & 0xFF00FF00) << 24),
p0 = 256 - p,
p1 = p;
const uint64_t c = p0*c0 + p1*c1;
return ((c >> 8) & 0x00FF00FF) | ((c >> 32) & 0xFF00FF00);
}
and you can even apply that to R10G10B10 (30-bit color) by changing the numerical constants. The "trick" is trivial; second (and fourth) component are shifted up and replaced with enough zeroes to hold the product.
On 32-bit architectures, you can do it with four (24×9=32 bit) multiplications:
static inline uint32_t rgb8888_blend(const uint32_t argb0, const uint32_t argb1, const uint32_t p)
{
const uint32_t rb0 = argb0 & 0x00FF00FF,
ag0 = (argb0 >> 8) & 0x00FF00FF,
rb1 = argb1 & 0x00FF00FF,
ag1 = (argb1 >> 8) & 0x00FF00FF,
p0 = 256 - p,
p1 = p;
return (((p0*rb0 + p1*rb1) & 0xFF00FF00u) >> 8)
| ((p0*ag0 + p1*ag1) & 0xFF00FF00u);
}
(Total cost being four 24×9=32bit multiplications, three eight-bit right shifts, six binary ANDs, one binary OR, two additions, and one subtraction.)
Obviously, on 8- and 16-bit architectures, you're better off handling each color component separately, as the internal register width is too small for more than one color component, as the intermediate results are 16-bit.
On 32-bit (or 64-bit) architectures, there are a few binary tricks with RGB565 also. For example, an arbitrary blend (32 steps) between two color values requires just two multiplications (27×6=32 bit), six binary ands (each using one of two 16-bit masks), four shifts, one subtraction, and one addition:
static inline uint16_t rgb565_blend(const uint16_t rgb0, const uint16_t rgb1, const uint16_t p)
{
const uint32_t c0 = (rgb0 & 0xF81F) | ((uint32_t)(rgb0 & 0x07E0) << 16);
const uint32_t c1 = (rgb1 & 0xF81F) | ((uint32_r)(rgb1 & 0x07E0) << 16);
const uint32_t p0 = 32 - p, p1 = p;
const uint32_t c = p0*c0 + p1*c1;
return ((c >> 5) & 0xF81F) | ((c >> 21) & 0x07E0);
}
On 64-bit architectures, you can trivially expand that to blending pairs of color values, for about the same cost.
Home
Help
Search
Login
Register
