c++ccastingroundingfloor

What is correct by common sense: (int) blabla * 255.99999999999997 or round(blabla*255)?


Recently I found this interesting thing in webkit sources, related to color conversions (hsl to rgb):

http://osxr.org/android/source/external/webkit/Source/WebCore/platform/graphics/Color.cpp#0111

const double scaleFactor = nextafter(256.0, 0.0); // it's here something like 255.99999999999997
// .. some code skipped
return makeRGBA(static_cast<int>(calcSomethingFrom0To1(blablabla) * scaleFactor), 

Same I found here: http://www.filewatcher.com/p/kdegraphics-4.6.0.tar.bz2.5101406/kdegraphics-4.6.0/kolourpaint/imagelib/effects/kpEffectHSV.cpp.html

(int)(value * 255.999999)

Is it correct to use such technique at all? Why dont' use something straight like round(blabla * 255)? Is it features of C/C++? As I see strictly speaking is will return not always correct results, in 27 cases of 100. See spreadsheet at https://docs.google.com/spreadsheets/d/1AbGnRgSp_5FCKAeNrELPJ5j9zON9HLiHoHC870PwdMc/edit?usp=sharing

Somebody pls explain — I think it should be something basic.


Solution

  • Short answer: (int)(blabla * 255.99999999999997) should be preferred.

    Explanation follows.

    Normally we want to map a real value x in the (closed) interval [0,1] to an integer value j in the range [0 ...255].

    And we want to do it in a "fair" way, so that, if the reals are uniformly distributed in the range, the discrete values will be approximately equiprobable: each of the 256 discrete values should get "the same share" (1/256) from the [0,1] interval. That is, we want a mapping like this:

    [0    , 1/256) -> 0
    [1/256, 2/256) -> 1 
    ...
    [254/256, 255/256) -> 254
    [255/256, 1]       -> 255
    

    We are not much concerned about the transition points [*], but we do want to cover the full the range [0,1]. How to accomplish that?

    If we simply do j = (int)(x *255): the value 255 would almost never appear (only when x=1); and the rest of the values 0...254 would each get a share of 1/255 of the interval. This would be unfair, regardless of the rounding behaviour at the limit points.

    If we instead do j = (int)(x * 256): this partition would be fair, except for a sngle problem: we would get the value 256 (out of range!) when x=1 [**]

    That's why j = (int)(x * 255.9999...) (where 255.9999... is actually the largest double less than 256) will do.

    An alternative implementation (also reasonable, almost equivalent) would be

    j = (int)(x * 256); 
    if(j == 256)  j = 255;  
    // j = x == 1.0 ? 255 : (int)(x * 256); // alternative
    

    but this would be more clumsy and probably less efficient.

    round() does not help here. For example, j = (int)round(x * 255) would give a 1/255 share to the integers j=1...254 and half that value to the extreme points j=0, j=255.

    enter image description here

    [*] I mean: we are not extremely interested in what happens in the 'small' neighbourhood of, say, 3/256: rounding might give 2 or 3, it doesn't matter. But we are interested in the extrema: we want to get 0 and 255, for x=0 and x=1respectively.

    [**] The IEEE floating point standard guarantees that there's no rounding ambiguity here: integers admit an exact floating point representation, the product will be exact, and the casting will give always 256. Further, we are guaranteed that 1.0 * z = z.