Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Contact info
Forum
 
Other projects
   Altirra

Search

Archives

01 Dec - 31 Dec 2013
01 Oct - 31 Oct 2013
01 Aug - 31 Aug 2013
01 May - 31 May 2013
01 Mar - 31 Mar 2013
01 Feb - 29 Feb 2013
01 Dec - 31 Dec 2012
01 Nov - 30 Nov 2012
01 Oct - 31 Oct 2012
01 Sep - 30 Sep 2012
01 Aug - 31 Aug 2012
01 June - 30 June 2012
01 May - 31 May 2012
01 Apr - 30 Apr 2012
01 Dec - 31 Dec 2011
01 Nov - 30 Nov 2011
01 Oct - 31 Oct 2011
01 Sep - 30 Sep 2011
01 Aug - 31 Aug 2011
01 Jul - 31 Jul 2011
01 June - 30 June 2011
01 May - 31 May 2011
01 Apr - 30 Apr 2011
01 Mar - 31 Mar 2011
01 Feb - 29 Feb 2011
01 Jan - 31 Jan 2011
01 Dec - 31 Dec 2010
01 Nov - 30 Nov 2010
01 Oct - 31 Oct 2010
01 Sep - 30 Sep 2010
01 Aug - 31 Aug 2010
01 Jul - 31 Jul 2010
01 June - 30 June 2010
01 May - 31 May 2010
01 Apr - 30 Apr 2010
01 Mar - 31 Mar 2010
01 Feb - 29 Feb 2010
01 Jan - 31 Jan 2010
01 Dec - 31 Dec 2009
01 Nov - 30 Nov 2009
01 Oct - 31 Oct 2009
01 Sep - 30 Sep 2009
01 Aug - 31 Aug 2009
01 Jul - 31 Jul 2009
01 June - 30 June 2009
01 May - 31 May 2009
01 Apr - 30 Apr 2009
01 Mar - 31 Mar 2009
01 Feb - 29 Feb 2009
01 Jan - 31 Jan 2009
01 Dec - 31 Dec 2008
01 Nov - 30 Nov 2008
01 Oct - 31 Oct 2008
01 Sep - 30 Sep 2008
01 Aug - 31 Aug 2008
01 Jul - 31 Jul 2008
01 June - 30 June 2008
01 May - 31 May 2008
01 Apr - 30 Apr 2008
01 Mar - 31 Mar 2008
01 Feb - 29 Feb 2008
01 Jan - 31 Jan 2008
01 Dec - 31 Dec 2007
01 Nov - 30 Nov 2007
01 Oct - 31 Oct 2007
01 Sep - 30 Sep 2007
01 Aug - 31 Aug 2007
01 Jul - 31 Jul 2007
01 June - 30 June 2007
01 May - 31 May 2007
01 Apr - 30 Apr 2007
01 Mar - 31 Mar 2007
01 Feb - 29 Feb 2007
01 Jan - 31 Jan 2007
01 Dec - 31 Dec 2006
01 Nov - 30 Nov 2006
01 Oct - 31 Oct 2006
01 Sep - 30 Sep 2006
01 Aug - 31 Aug 2006
01 Jul - 31 Jul 2006
01 June - 30 June 2006
01 May - 31 May 2006
01 Apr - 30 Apr 2006
01 Mar - 31 Mar 2006
01 Feb - 29 Feb 2006
01 Jan - 31 Jan 2006
01 Dec - 31 Dec 2005
01 Nov - 30 Nov 2005
01 Oct - 31 Oct 2005
01 Sep - 30 Sep 2005
01 Aug - 31 Aug 2005
01 Jul - 31 Jul 2005
01 June - 30 June 2005
01 May - 31 May 2005
01 Apr - 30 Apr 2005
01 Mar - 31 Mar 2005
01 Feb - 29 Feb 2005
01 Jan - 31 Jan 2005
01 Dec - 31 Dec 2004
01 Nov - 30 Nov 2004
01 Oct - 31 Oct 2004
01 Sep - 30 Sep 2004
01 Aug - 31 Aug 2004

Stuff

Powered by Pivot  
XML: RSS feed 
XML: Atom feed 

§ SIMD averaging without SIMD hardware

If you need to average two sets of bitfields using larger word operations, there is a trick derived from a hardware algorithm for constructing adders that can come in handy. The basic comes from the design of a carry-save adder, which splits apart carry and sum signals to allow multiple values to be added with only one carry propagation pass at the end:

a+b = ((a & b) << 1) + (a ^ b)

(& is the C operator for bitwise AND, ^ is bitwise exclusive OR, and << is a left shift.)

To convert this into an average, propagate through the necessary shift:

(a+b) >> 1 = (a & b) + ((a ^ b) >> 1)

...and to apply this to bitfields, just mask off the least significant bits from each bitfield sum to avoid cross-field contamination:

(pel0+pel1) >> 1 = (pel0 & pel1) + (((pel0 ^ pel1) & 0xfefefefe)>>1)

This can be useful even if you have SIMD hardware that has built-in averaging. For instance, SSE has support for unsigned byte averages, but the above algorithm can be used to average four 565 pixels at a time by using the mask 0xf7def7def7def7de.

Note that the above algorithm always rounds down, which isn't always appropriate; MPEG motion prediction, for instance, requires rounding up. There is a trick that can be used to average up without using any additional operations.

The trick is to recognize that the addition can also be formulated using inclusive OR and subtraction:

a+b = ((a & b) << 1) + (a^b) = ((a|b) << 1) - (a^b)

Shifting out the LSB from the exclusive OR result then has the effect of rounding up instead of rounding down, giving:

(a+b+1) >> 1 = (a|b) - ((a^b)>>1)
(pel0+pel1+1)>>1 = (pel0 | pel1) - (((pel0 ^ pel1) & 0xfefefefe)>>1)

Comments

Comments posted:


cool!

in the last line, you mean:

(pel0+pel1+1)>>1 = (pel0 | pel1) ***MINUS*** (((pel0 ^ pel1) & 0xfefefefe)>>1)

User - 06 07 06 - 04:45


How about compiling something like HAKMEM 2... :)

[maven] (link) - 06 07 06 - 06:57


@User:
Whoops, fixed. Thanks!

Phaeron - 06 07 06 - 23:34


Any smart-math way of doing an 8bit alpha blend (8bit source, 8bit destination, 8bit alpha)?

Blight - 07 07 06 - 01:04


Isn't it quite senseless to program without doing it 'the SIMD way'?
I mean, basicly every processor in existence today has some form of SIMD instruction set.

/Zaro

Zaro - 07 07 06 - 04:52


@Zaro, cleaverness like this is probably even more appropriate in SIMD processing. Think harder about the 565 pixel example Avery gave.

@Blight, I take it you, like me, want an improved way to do
Dst += (Src - Dst) * Alpha / 255;
which in regular code could be implemented quickish as
Dst += LookupTable[(Src-Dst)

IanB - 07 07 06 - 22:33


Doh!, Smartarse blog parser! Take 2

*Dst += LookupTable[(Src-Dst) ._lshift_. 8 | alpha]; // 17 bit table*

Which doesn't play well in SIMD.

Thoughts anybody?

IanB - 07 07 06 - 22:42


@Zaro:
You're assuming that the SIMD instruction set natively supports the datatypes you are working with. MMX and SSE are rather rigid in this regard, with some support for unsigned bytes, a lot of support for signed words, and very sketchy support for everything else. Conversion to and from signed words tends to put a lot of pressure on the shift unit, so to the extent that you can find alternate ways to work with odd bitfields, the better performance you can get. I hear that Altivec is a lot nicer with regard to data type and operation orthogonality, but it still isn't going to support every combination of packed data type that you will encounter in the wild.

Phaeron - 08 07 06 - 00:07

Comment form


Please keep comments on-topic for this entry. If you have unrelated comments about VirtualDub, the forum is a better place to post them.
Name:  
Remember personal info?

Email (Optional):
Your email address is only revealed to the blog owner and is not shown to the public.
URL (Optional):
Comment: /

An authentication dialog may appear when you click Post Comment. Simply type in "post" as the user and "now" as the password. I have had to do this to stop automated comment spam.



Small print: All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.