[Vm-dev] Re: Little speed up of BitBlt alpha-blending
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Tue Dec 24 04:59:21 UTC 2013
I only measured gain of 25%, not 50%, maybe the division is a bit complex...
2013/12/24 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
>
> 2013/12/23 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
>
>>
>> 2013/12/23 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>
>>
>>> Currently we use a very clear but naive algorithm
>>>
>>> alpha := sourceWord >> 24. "High 8 bits of source pixel"
>>> alpha = 0 ifTrue: [ ^ destinationWord ].
>>> alpha = 255 ifTrue: [ ^ sourceWord ].
>>> unAlpha := 255 - alpha.
>>> colorMask := 16rFF.
>>> result := 0.
>>>
>>> "red"
>>> shift := 0.
>>> blend := ((sourceWord >> shift bitAnd: colorMask) * alpha) +
>>> ((destinationWord>>shift bitAnd: colorMask) * unAlpha)
>>> + 254 // 255 bitAnd: colorMask.
>>> result := result bitOr: blend << shift.
>>> "green"
>>> shift := 8.
>>> blend := ((sourceWord >> shift bitAnd: colorMask) * alpha) +
>>> ((destinationWord>>shift bitAnd: colorMask) * unAlpha)
>>> + 254 // 255 bitAnd: colorMask.
>>> result := result bitOr: blend << shift.
>>> "blue"
>>> shift := 16.
>>> blend := ((sourceWord >> shift bitAnd: colorMask) * alpha) +
>>> ((destinationWord>>shift bitAnd: colorMask) * unAlpha)
>>> + 254 // 255 bitAnd: colorMask.
>>> result := result bitOr: blend << shift.
>>> "alpha (pre-multiplied)"
>>> shift := 24.
>>> blend := (alpha * 255) +
>>> ((destinationWord>>shift bitAnd: colorMask) * unAlpha)
>>> + 254 // 255 bitAnd: colorMask.
>>> result := result bitOr: blend << shift.
>>> ^ result
>>>
>>>
>>> Of course, the best we could do to improve it is using a native OS
>>> library when it exists on the whole bitmap. I let this path apart, it can
>>> be handled at platform specific source like tim did for Pi.
>>> But still, with our own crafted bits, we could do better than current
>>> implementation.
>>> See
>>> http://stackoverflow.com/questions/1102692/how-to-do-alpha-blend-fast
>>>
>>> Using specific hardware instructions by ourselves is not really an
>>> option for a portable VM, it's better to call a native library if we cant
>>> to have specific optimizations, so i let SSE instructions apart.
>>>
>>> But there are two simple ideas we can recycle from above SO reference:
>>>
>>> 1) multiplex Red+Blue and Alpha+Green computations
>>> 2) avoid division by 255
>>>
>>> Here it is:
>>>
>>> "red and blue"
>>> blend := ((sourceWord bitAnd: 16rFF00FF) * alpha) +
>>> ((destinationWord bitAnd: 16rFF00FF) * unAlpha) +
>>> 16rFE00FE.
>>> "divide by 255"
>>> blend := blend + 16r10001 + (blend >> 8 bitAnd: 16rFF00FF) >> 8.
>>>
>> I forgot to protect bitAnd: 16rFF00FF but you get the idea...
>>
>>
>>> result := blend.
>>>
>>> "alpha and green"
>>> blend := (((sourceWord>> 8 bitOr: 16rFF0000) bitAnd: 16rFF00FF) *
>>> alpha) +
>>> ((destinationWord>>8 bitAnd: 16rFF00FF) * unAlpha) +
>>> 16rFE00FE.
>>> "divide by 255"
>>> blend := blend + 16r10001 + (blend >> 8 bitAnd: 16rFF00FF) >> 8.
>>>
>>
>> bitAnd: 16rFF00FF too of course...
>>
>>
>>> result := result bitOr: blend<<8.
>>> ^ result
>>>
>>> For bytes B1 and B2 in (0..255), alpha*B1+unAlpha*B2 is in (0..16rFE01)
>>> alpha*B1+unAlpha*B2+254 is in (0..16rFEFF)
>>> So when we multiplex non adjacent components, we're safe from overflow.
>>>
>>> Now for division by 255 we are also safe: when adding 1 -> (1..16rFF00)
>>> And when adding blend>>8 bitAnd 16rFF -> (1..16rFFFF)
>>> We are still free of overflow and can extend the //255 division trick to
>>> 32bit word (the formula given on SO is for 16bit only).
>>>
>>> I expect roughly a x2 factor in throughput, but it's hard to measure.
>>> What do you think? Is this interesting?
>>>
>>
>> Find corresponding code attached
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20131224/7ab24807/attachment.htm
More information about the Vm-dev
mailing list