494664 - NS_ComposeColors is broken for bgcolor with alpha != 255

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Timothy Nikkel (:tnikkel)]

Attachment: patch

To see that it is broken one only need to read this comment "First compute what we get drawing aBG onto RGBA(0,0,0,0)". Drawing any color c on top of RGBA(0,0,0,0) should give you c. But if aBG is say RGBA(255,0,0,128) then that part of the function will give you (128,0,0,128).

It's not too hard to convince yourself that my code will produce the same results as the old function when the bgcolor has alpha=255. I don't think there is any use of NS_ComposeColors (currently) that uses a bgcolor with alpha!=255. nsTextFrameThebes.cpp uses a bgcolor that comes from platform specific nsILookAndFeel; I did a quick skim of these, it doesn't look like they use any colors with alpha!=255.

I checked my new version of NS_ComposeColors by comparing it to a python version at
http://canvex.lazyilluminati.com/tests/composite/composite.py (linked from here http://lists.whatwg.org/pipermail/whatwg-whatwg.org/2007-March/010608.html). The python code uses floating point (I corrected a slight bug where it inadvertently used floor instead of round because python's formatted print uses floor to print floats in int format), so an int version will not match up exactly. I checked the output for every combination of background/foreground and color component/alpha in the set [0,1,63,64,85,86,127,128,177,178,200,201,254,255]. Then I did a line-for-line port of the python code to C++ using doubles and did an exhaustive check of every case 0-255 (256^4 total cases as you only need to check one color component). The only problems I found were small due to using ints vs floats. (For the gory details, the metric I used was to convert the colors to premultiplied alpha, then took the sum of the squares of the differences between each of the four components. The G,B components were always zero, so it was really just two components. Premultiplying was necessary because bg=(254,0,0,1) fg=(0,0,0,1) would produce int version=(0,0,0,1) and double version=(127,0,0,2), which are very close in what they will actually draw, but far numerically. The average error with this metric was 1.08919, maximum error  was 8.51405. The max error occurred on bg = (27,0,0,242), fg = (255,0,0,187), where the int version produced (195,0,0,251) and the double version produced (197,0,0,252).)

This function could use floats, I don't think its used anyplace where absolute speed is needed.

This is needed for bug 488242.

Comment 1

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 379417 [details] [diff] [review]
patch

>diff --git a/gfx/public/nsColor.h b/gfx/public/nsColor.h
>--- a/gfx/public/nsColor.h
>+++ b/gfx/public/nsColor.h
>@@ -72,30 +72,23 @@ typedef PRUint32 nscolor;
> //
> // equivalent to target=v/255
> #define FAST_DIVIDE_BY_255(target,v)               \
>   PR_BEGIN_MACRO                                   \
>     unsigned tmp_ = v;                             \
>     target = ((tmp_ << 8) + tmp_ + 255) >> 16;     \
>   PR_END_MACRO
> 
>-// Blending macro
>-//
>-// equivalent to target=(bg*(255-alpha)+fg*alpha)/255
>-#define MOZ_BLEND(target, bg, fg, alpha) \
>-        FAST_DIVIDE_BY_255(target, (bg)*(255-(alpha)) + (fg)*(alpha))
>-
> // Translate a hex string to a color. Return true if it parses ok,
> // otherwise return false.
> // This accepts only 3 or 6 digits
> NS_GFX_(PRBool) NS_HexToRGB(const nsString& aBuf, nscolor* aResult);
> 
>-// Compose one NS_RGB color onto another. The result is what you get
>-// if you draw aBG onto RGBA(0,0,0,0) and then aFG on top of that,
>-// with operator OVER.
>+// Compose one NS_RGB color onto another. The result is what
>+// you get if you draw aFG on top of aBG with operator OVER.
> NS_GFX_(nscolor) NS_ComposeColors(nscolor aBG, nscolor aFG);
> 
> // Translate a hex string to a color. Return true if it parses ok,
> // otherwise return false.
> // This version accepts 1 to 9 digits (missing digits are 0)
> NS_GFX_(PRBool) NS_LooseHexToRGB(const nsString& aBuf, nscolor* aResult);
> 
> // There is no function to translate a color to a hex string, because
>diff --git a/gfx/src/nsColor.cpp b/gfx/src/nsColor.cpp
>--- a/gfx/src/nsColor.cpp
>+++ b/gfx/src/nsColor.cpp
>@@ -70,17 +70,17 @@ void nsColorNames::AddRefTable(void)
> {
>   NS_ASSERTION(!gColorTable, "pre existing array!");
>   if (!gColorTable) {
>     gColorTable = new nsStaticCaseInsensitiveNameTable();
>     if (gColorTable) {
> #ifdef DEBUG
>     {
>       // let's verify the table...
>-      for (PRInt32 index = 0; index < eColorName_COUNT; ++index) {
>+      for (PRUint32 index = 0; index < eColorName_COUNT; ++index) {

This is an unrelated change and should be in a separate patch.

>         nsCAutoString temp1(kColorNames[index]);
>         nsCAutoString temp2(kColorNames[index]);
>         ToLowerCase(temp1);
>         NS_ASSERTION(temp1.Equals(temp2), "upper case char in table");
>       }
>     }
> #endif      
>       gColorTable->Init(kColorNames, eColorName_COUNT); 
>@@ -211,35 +211,47 @@ NS_GFX_(PRBool) NS_ColorNameToRGB(const 
>     if (aResult) {
>       *aResult = kColors[id];
>     }
>     return PR_TRUE;
>   }
>   return PR_FALSE;
> }
> 
>+// Macro to blend two colors
>+//
>+// equivalent to target = (bg*(255-fgalpha) + fg*fgalpha)/255
>+#define MOZ_BLEND(target, bg, fg, fgalpha)       \
>+  FAST_DIVIDE_BY_255(target, (bg)*(255-fgalpha) + (fg)*(fgalpha))
>+

why change and move this macro?

> NS_GFX_(nscolor)
> NS_ComposeColors(nscolor aBG, nscolor aFG)
> {
>-  PRIntn bgAlpha = NS_GET_A(aBG);
>+  // This function uses colors that are non premultiplied alpha.
>   PRIntn r, g, b, a;
> 
>-  // First compute what we get drawing aBG onto RGBA(0,0,0,0)
>-  MOZ_BLEND(r, 0, NS_GET_R(aBG), bgAlpha);
>-  MOZ_BLEND(g, 0, NS_GET_G(aBG), bgAlpha);
>-  MOZ_BLEND(b, 0, NS_GET_B(aBG), bgAlpha);
>-  a = bgAlpha;
>+  PRIntn bgAlpha = NS_GET_A(aBG);
>+  PRIntn fgAlpha = NS_GET_A(aFG);
> 
>-  // Now draw aFG on top of that
>-  PRIntn fgAlpha = NS_GET_A(aFG);
>-  MOZ_BLEND(r, r, NS_GET_R(aFG), fgAlpha);
>-  MOZ_BLEND(g, g, NS_GET_G(aFG), fgAlpha);
>-  MOZ_BLEND(b, b, NS_GET_B(aFG), fgAlpha);
>-  MOZ_BLEND(a, a, 255, fgAlpha);
>-  
>+  // Compute the final alpha of the blended color
>+  // a = fgAlpha + bgAlpha*(255 - fgAlpha)/255;
>+  FAST_DIVIDE_BY_255(a, bgAlpha*(255-fgAlpha));
>+  a = fgAlpha + a;
>+  if (a == 0) {
>+    // In this case the blended color is totally trasparent,
>+    // we preserve the color information of the foreground color.
>+    fgAlpha = 255;
>+  } else {
>+    fgAlpha = (fgAlpha*255)/a;
>+  }
>+  bgAlpha = 255 - fgAlpha;

This value of bgAlpha doesn't seem to be used

>+  MOZ_BLEND(r, NS_GET_R(aBG), NS_GET_R(aFG), fgAlpha);
>+  MOZ_BLEND(g, NS_GET_G(aBG), NS_GET_G(aFG), fgAlpha);
>+  MOZ_BLEND(b, NS_GET_B(aBG), NS_GET_B(aFG), fgAlpha);

The calculation looks correct to me.

>   return NS_RGBA(r, g, b, a);
> }
> 
> // Functions to convert from HSL color space to RGB color space.
> // This is the algorithm described in the CSS3 specification
> 
> // helper
> static float
>diff --git a/gfx/thebes/public/gfxColor.h b/gfx/thebes/public/gfxColor.h
>--- a/gfx/thebes/public/gfxColor.h
>+++ b/gfx/thebes/public/gfxColor.h
>@@ -112,18 +112,18 @@
>     p1 = 0xFF000000 | ((rgbr) << 16) | ((gbrg) >> 16); \
>     p2 = 0xFF000000 | ((gbrg) <<  8) | ((brgb) >> 24); \
>     p3 = 0xFF000000 | (brgb); \
>     to[0] = p0; to[1] = p1; to[2] = p2; to[3] = p3; \
>   PR_END_MACRO
> 
> /**
>  * Fast approximate division by 255. It has the property that
>- * for all 0 <= n <= 255*255, FAST_DIVIDE_BY_255(n) == n/255.
>- * But it only uses two adds and two shifts instead of an 
>+ * for all 0 <= n <= 255*255, GFX_DIVIDE_BY_255(n) == n/255.
>+ * But it only uses two adds and two shifts instead of an

Cosmetic changes are better in a separate patch

>  * integer division (which is expensive on many processors).
>  *
>  * equivalent to ((v)/255)
>  */
> #define GFX_DIVIDE_BY_255(v)  \
>      (((((unsigned)(v)) << 8) + ((unsigned)(v)) + 255) >> 16)
> 
> /**
>diff --git a/layout/style/nsCSSParser.cpp b/layout/style/nsCSSParser.cpp
>--- a/layout/style/nsCSSParser.cpp
>+++ b/layout/style/nsCSSParser.cpp
>@@ -3837,17 +3837,19 @@ CSSParserImpl::ParseColorOpacity(PRUint8
> 
>   if (mToken.mNumber < 0.0f) {
>     mToken.mNumber = 0.0f;
>   } else if (mToken.mNumber > 1.0f) {
>     mToken.mNumber = 1.0f;
>   }
> 
>   PRUint8 value = nsStyleUtil::FloatToColorComponent(mToken.mNumber);
>-  NS_ASSERTION(fabs(mToken.mNumber - value/255.0f) <= 0.5f,
>+  // Need to compare to something slightly larger
>+  // than 0.5 due to floating point inaccuracies.
>+  NS_ASSERTION(fabs(255.0f*mToken.mNumber - value) <= 0.51f,
>                "FloatToColorComponent did something weird");
> 

This seems unrelated too...

>   if (!ExpectSymbol(')', PR_TRUE)) {
>     REPORT_UNEXPECTED_TOKEN(PEExpectedCloseParen);
>     return PR_FALSE;
>   }
> 
>   aOpacity = value;

Comment 2

[Timothy Nikkel (:tnikkel)]

Attachment: patch v2

Removed the unrelated cleanups. Got rid of unneeded bgAlpha calculation.

I moved the MOZ_BLEND macro out of the header because it wasn't used anywhere else. I changed alpha to fgalpha to make it clear what the alpha parameter meant.

Comment 3

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 379628 [details] [diff] [review]
patch v2

Looks good. Can you come up with a better name for the final alpha used in the MOZ_BLEND instead of reusing fgAlpha though?

Comment 4

[Timothy Nikkel (:tnikkel)]

Attachment: patch v3

Comment 5

[Timothy Nikkel (:tnikkel)]

Attachment: minor cleanups

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

http://hg.mozilla.org/mozilla-central/rev/c97e700b3bbf

Thanks.

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

http://hg.mozilla.org/mozilla-central/rev/ddee37e8a38e

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #0)
> To see that it is broken one only need to read this comment "First compute what
> we get drawing aBG onto RGBA(0,0,0,0)". Drawing any color c on top of
> RGBA(0,0,0,0) should give you c. But if aBG is say RGBA(255,0,0,128) then that
> part of the function will give you (128,0,0,128).

I don't think that means it's broken.  It means that the input color is non-premultiplied, but compositing math works much better on premultiplied colors.


As I pointed out in bug 561959 comment 15, I think this code is broken, though I think it was broken before the patch too.  I think before this patch, NS_ComposeColors took two non-premultiplied colors as input and produced premultiplied output; the patch changed it so that aBG was expected to be premultiplied.  But I think the callers want all three to be non-premultiplied (as the comment added in this patch says they are).

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Er, I missed that the final blendAlpha computation divides by a, so the current result isn't premultiplied, but I think that just makes it even weirder.

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Er, never mind the whole mess; the current code is correct.

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Anyway, perhaps everyone else knew this formula already, but it was a
bit of a surprise to me.  In any case, here's a proof that the current
code is equivalent to what I expected:


So compositing is normally described in terms of premultiplied color
components cᵢ, which are computed from non-premultplied color components
by multiplying by the alpha:
  cᵢ = αᵢ * Cᵢ

The normal compositing formula for compositing 1 OVER 2 to produce
output o is (treating all values as in the range 0-1 rather than the
range 0-255):

  cₒ = c₁ + (1 - α₁) * c₂
  αₒ = α₁ + (1 - α₁) * α₂

The Porter-Duff paper has an intuitive explanation for this formula.

The obvious way to represent this in terms of non-premultiplied colors
(by simply substituting the definition of premultiplication) is:

        cₒ     α₁ * C₁ + (1 - α₁) * α₂ * C₂
  Cₒ = ---- = ------------------------------
        αₒ                 αₒ

However, what NS_ComposeColors does instead is:
             α₁                α₁
  Cₒ = C₁ * ---- + C₂ * ( 1 - ---- )
             αₒ                αₒ

This actually turns out to be equivalent, since putting everything
over αₒ gives:

         α₁ * C₁ + (αₒ - α₁) * C₂
      = --------------------------
                    αₒ

and substituting for αₒ inside the numerator gives:

         α₁ * C₁ + (1 - α₁) * α₂ * C₂
      = ------------------------------
                      αₒ

which is the same as the straightforwardly-derived formula above.