exebook exebook - 1 month ago 3x
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

short int
for blue, and same code is seen for
(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*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]