exebook - 2 months ago 4

C 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`

`short int`

`r`

`b`

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

```
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]
```

Source (Stackoverflow)

Comments