exebook - 1 year ago 49
C Question

# what (r+1 + (r >> 8)) >> 8 does?

In some old C/C++ graphics related code, that I have to port to Java and JavaScript I found this:

``````b = (b+1 + (b >> 8)) >> 8; // very fast
``````

Where
`b`
is
`short int`
for blue, and same code is seen for
`r`
and
`b`
(red & blue). The comment is not helpful.

I cannot figure out what it does, apart from obvious shifting and adding. I can port without understanding, I just ask out of curiosity.

``````y = ( x + 1 + (x>>8) ) >> 8 // very fast
``````

This is a fixed-point approximation of division by 255. Conceptually, this is useful for normalizing calculations based on pixel values such that 255 (typically the maximum pixel value) maps to exactly 1.

It is described as very fast because fully general integer division is a relatively slow operation on many CPUs -- although it is possible that your compiler would make a similar optimization for you if it can deduce the input constraints.

This works based on the idea that `257/(256*256)` is a very close approximation of `1/255`, and that `x*257/256` can be formulated as `x+(x>>8)`. The `+1` is rounding support which allows the formula to exactly match the integer division `x/255` for all values of `x` in [0..65534].

Some algebra on the inner portion may make things a bit more clear...

``````       x*257/256
= (x*256+x)/256
= x + x/256
= x + (x>>8)
``````

There is more discussion here: How to do alpha blend fast? and here: Division via Multiplication

By the way, if you want round-to-nearest, and your CPU can do fast multiplies, the following is accurate for all uint16_t dividend values -- actually [0..(2^16)+126].

``````y = ((x+128)*257)>>16 // divide by 255 with round-to-nearest for x in [0..65662]
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download