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

Question

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.

Answer 1

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]

Answer 2

Looks like it is meant to check if blue (or red or green) is fully used. It evaluates to 1, when b is 255, and is 0 for all lower values.