Bug 94364 – Add saturation arithmetic support to FractionalLayoutUnit

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Emil A Eklund]

Now that we use a custom type for layout sizes and locations it is quite easy to overload the operators to support saturation arithmetic. Add an experimental implementation, guarded by a flag.

[Emil A Eklund]

Created attachment 159167 [details]
Patch

[WebKit Review Bot]

Comment on attachment 159167 [details]
Patch

Attachment 159167 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13517877

New failing tests:
css1/formatting_model/inline_elements.html
fast/html/details-add-summary-1.html
fast/html/details-add-details-child-1.html
fast/html/details-add-child-1.html
fast/forms/datalist/input-appearance-range-with-datalist-zoomed.html
fast/html/details-add-summary-4.html
fast/frames/cached-frame-counter.html
fast/borders/bidi-012.html
fast/encoding/utf-16-little-endian.html
fast/html/details-add-summary-2.html
fast/html/details-add-summary-3-and-click.html
fast/canvas/webgl/shader-precision-format.html
fast/html/details-add-child-2.html
fast/forms/007.html
fast/block/margin-collapse/103.html
fast/forms/date/date-appearance.html
fast/borders/border-radius-huge-assert.html
fast/html/details-add-details-child-2.html
fast/flexbox/flex-hang.html
fast/html/details-add-summary-1-and-click.html
fast/html/details-add-summary-2-and-click.html
fast/css/bidi-override-in-anonymous-block.html
fast/encoding/utf-16-big-endian.html
fast/backgrounds/background-position-parsing.html
fast/borders/bidi-009a.html
fast/html/details-add-summary-4-and-click.html
fast/html/details-add-summary-3.html

[WebKit Review Bot]

Created attachment 159200 [details]
Archive of layout-test-results from gce-cr-linux-05

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-05  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid

[Emil A Eklund]

Created attachment 159489 [details]
Patch

[Abhishek Arya]

Levi Sir! very friendly review ping since you guys are our defacto FractionalLayoutUnit experts. We are pretty excited for this change, since it will fix many of Use-after-free bugs caused in float due to these overflows and wraps. e.g. https://bugs.webkit.org/show_bug.cgi?id=93135

[Levi Weintraub]

Comment on attachment 159489 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=159489&action=review

> Source/WebCore/platform/FractionalLayoutUnit.h:66
> -const int intMinForLayoutUnit = -intMaxForLayoutUnit;
> +const int intMinForLayoutUnit = INT_MIN / kFixedPointDenominator;

A comment in the changelog is warranted. This isn't directly related to the change at hand.

> Source/WebCore/platform/FractionalLayoutUnit.h:78
> +    FractionalLayoutUnit(int value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }
> +    FractionalLayoutUnit(unsigned short value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }
> +    FractionalLayoutUnit(unsigned int value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }

Why not have the REPORT_OVERFLOW functionality in setValue?

Also, I don't think it makes sense to report anything if we're clamping. In that case there's nothing to report!

> Source/WebCore/platform/FractionalLayoutUnit.h:470
> +    return boundedMultiply(a, b);

Perhaps we should rename this to saturatedMultiply for consistency?

[Emil A Eklund]

Created attachment 159759 [details]
Patch

[Emil A Eklund]

(In reply to comment #6)
> (From update of attachment 159489 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=159489&action=review
> 
> > Source/WebCore/platform/FractionalLayoutUnit.h:66
> > -const int intMinForLayoutUnit = -intMaxForLayoutUnit;
> > +const int intMinForLayoutUnit = INT_MIN / kFixedPointDenominator;
> 
> A comment in the changelog is warranted. This isn't directly related to the change at hand.

Done.

> 
> > Source/WebCore/platform/FractionalLayoutUnit.h:78
> > +    FractionalLayoutUnit(int value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }
> > +    FractionalLayoutUnit(unsigned short value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }
> > +    FractionalLayoutUnit(unsigned int value) { REPORT_OVERFLOW(isInBounds(value)); setValue(value); }
> 
> Why not have the REPORT_OVERFLOW functionality in setValue?
> 
> Also, I don't think it makes sense to report anything if we're clamping. In that case there's nothing to report!

Done.

> 
> > Source/WebCore/platform/FractionalLayoutUnit.h:470
> > +    return boundedMultiply(a, b);
> 
> Perhaps we should rename this to saturatedMultiply for consistency?

Kept it as saturatedMultiply for now as it, unlike the saturatedAddition/Subtraction methods, doesn't necessarily use saturation arithmetic (guarded by a different flag) and takes a different type.

[Benjamin Poulain]

Comment on attachment 159759 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=159759&action=review

I would prefer having tests for WTF.

> Source/WTF/ChangeLog:12
> +        * wtf/MathExtras.h:
> +        (saturatedAddition):
> +        (saturatedSubtraction):

Is this better suited for CheckedArithmetic.h?

> Source/WTF/wtf/MathExtras.h:381
> +{
> +    uint32_t ua = a;
> +    uint32_t ub = b;
> +    uint32_t result = ua + ub;
> +
> +    // Can only overflow if the signed bit of the two values match. If the signed
> +    // bit of the result and one of the values differ it did overflow.
> +    if (!((ua ^ ub) >> 31) && (result ^ ua) >> 31)
> +        result = std::numeric_limits<int>::max() + (ua >> 31);
> +
> +    return result;

I am confused by this.

If I do saturatedAddition(0, -1), the result would be 1?.

[Emil A Eklund]

Created attachment 159773 [details]
Test case

[Emil A Eklund]

(In reply to comment #9)
> Is this better suited for CheckedArithmetic.h?

Perhaps, it is not in the Checked namespace though.

> > Source/WTF/wtf/MathExtras.h:381
> > +{
> > +    uint32_t ua = a;
> > +    uint32_t ub = b;
> > +    uint32_t result = ua + ub;
> > +
> > +    // Can only overflow if the signed bit of the two values match. If the signed
> > +    // bit of the result and one of the values differ it did overflow.
> > +    if (!((ua ^ ub) >> 31) && (result ^ ua) >> 31)
> > +        result = std::numeric_limits<int>::max() + (ua >> 31);
> > +
> > +    return result;
> 
> I am confused by this.
> 
> If I do saturatedAddition(0, -1), the result would be 1?.

No, it'll be -1. See the attached test case.

[Benjamin Poulain]

The test case should go in WebKitTestAPI.
I know it is not ideal, but it is better than having it outside WebKit.

[Emil A Eklund]

(In reply to comment #12)
> The test case should go in WebKitTestAPI.
> I know it is not ideal, but it is better than having it outside WebKit.

Better than outside the source tree for sure. I'll convert it to a proper test and move it there. Thanks.

[Benjamin Poulain]

Comment on attachment 159759 [details]
Patch

> > If I do saturatedAddition(0, -1), the result would be 1?.
> 
> No, it'll be -1. See the attached test case.

Of course, my bad. For some reason I thought the return was unsigned or something...

I r- for the tests and because IMHO, this does not belong in MathExtras.h (maybe CheckedArithmetic.h or a new SaturatedArithmetic.h?).

[Darin Adler]

MathExtras.h is supposed to repair and slightly supplement <math.h>. So I agree that these functions should go elsewhere.

[Emil A Eklund]

Created attachment 159829 [details]
Patch

[Emil A Eklund]

Thanks for the review and the suggestions Benjamin.
I moved the functions to a new SaturatedArithmetic.h file and added tests in WebKitTestAPI, please let me know what you think.

[Allan Sandfeld Jensen]

Comment on attachment 159829 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=159829&action=review

> Source/WTF/wtf/SaturatedArithmetic.h:46
> +    if (!((ua ^ ub) >> 31) && (result ^ ua) >> 31)

Use single & if you want to reduce branching.

> Source/WTF/wtf/SaturatedArithmetic.h:60
> +    if ((ua ^ ub) >> 31 && (result ^ ua) >> 31)

ditto

> Source/WebCore/platform/FractionalLayoutUnit.h:84
> +        m_value = std::min<float>(std::max<float>(value * kFixedPointDenominator, intMinForLayoutUnit), intMaxForLayoutUnit);

clampTo from MathExtras.h?

> Source/WebCore/platform/FractionalLayoutUnit.h:93
> +        m_value = std::min<double>(std::max<double>(value * kFixedPointDenominator, intMinForLayoutUnit), intMaxForLayoutUnit);

ditto

> Source/WebCore/platform/FractionalLayoutUnit.h:112
> +        v.m_value = std::min<double>(std::max<double>(ceilf(value * kFixedPointDenominator), INT_MIN), INT_MAX);

clampToInteger

> Source/WebCore/platform/FractionalLayoutUnit.h:124
> +        v.m_value = std::min<double>(std::max<double>(floorf(value * kFixedPointDenominator), INT_MIN), INT_MAX);

ditto

[Emil A Eklund]

(In reply to comment #18)
> (From update of attachment 159829 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=159829&action=review
> 
> > Source/WTF/wtf/SaturatedArithmetic.h:46
> > +    if (!((ua ^ ub) >> 31) && (result ^ ua) >> 31)
> 
> Use single & if you want to reduce branching.

Of course, thank you for catching that.


> > Source/WebCore/platform/FractionalLayoutUnit.h:84
> > +        m_value = std::min<float>(std::max<float>(value * kFixedPointDenominator, intMinForLayoutUnit), intMaxForLayoutUnit);
> 
> clampTo from MathExtras.h?

Good idea, changed here and elsewhere.

[Emil A Eklund]

Created attachment 159955 [details]
Patch

[Levi Weintraub]

Comment on attachment 159955 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=159955&action=review

Looks good once the REPORT_OVERFLOW corrections are made. I'm excited to see how this fares in the PLT. It'd be great to be able to turn this on...

> Source/WebCore/platform/FractionalLayoutUnit.h:82
> +        REPORT_OVERFLOW(isInBounds(value));

REPORT_OVERFLOW should only trigger without saturated arithmetic.

> Source/WebCore/platform/FractionalLayoutUnit.h:91
> +        REPORT_OVERFLOW(isInBounds(value));

Ditto.

> Source/WebCore/platform/FractionalLayoutUnit.h:109
>          REPORT_OVERFLOW(isInBounds(value));

Ditto.

> Source/WebCore/platform/FractionalLayoutUnit.h:142
>      static FractionalLayoutUnit fromFloatRound(float value)
>      {
> +#if ENABLE(SATURATED_LAYOUT_ARITHMETIC)
> +        if (value >= 0)
> +            return clamp(value + epsilon() / 2.0f);
> +        return clamp(value - epsilon() / 2.0f);
> +#else
>          if (value >= 0)
>              return FractionalLayoutUnit(value + epsilon() / 2.0f);
>          return FractionalLayoutUnit(value - epsilon() / 2.0f);
> +#endif
>      }

This function needs a REPORT_OVERFLOW for the non-saturated case.

[Benjamin Poulain]

Comment on attachment 159955 [details]
Patch

Some comments (the patch looks good otherwise):

> Source/WTF/WTF.xcodeproj/project.pbxproj:1068
> +				14F3B0F715E45E4600210069 /* SaturatedArithmetic.h in Headers */,

It would be great if you could order the build section alphabetically. It helps a lot when there are merge conflicts with your local changes.

> Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:979
> +				14F3B11315E45EAB00210069 /* SaturatedArithmeticOperations.cpp in Sources */,

ditto.

[Emil A Eklund]

Created attachment 160176 [details]
Patch

[Emil A Eklund]

Made the ASSERT changed levi suggested and sorted the xcode project files. Please take another look Benjamin.

[Benjamin Poulain]

Comment on attachment 160176 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=160176&action=review

Thank you for fixing the xcodeproj files.

Few little comments bellow, but otherwise this looks correct.

> Source/WTF/ChangeLog:16
> +        * GNUmakefile.list.am:
> +        * WTF.gypi:
> +        * WTF.pro:
> +        * WTF.vcproj/WTF.vcproj:
> +        * WTF.xcodeproj/project.pbxproj:

Not the CMakeLists.txt?

> Source/WTF/wtf/Platform.h:835
> +#if !defined(ENABLE_SATURATED_LAYOUT_ARITHMETIC)
> +#define ENABLE_SATURATED_LAYOUT_ARITHMETIC 0
> +#endif
> +
> +#if ENABLE(ENABLE_SATURATED_LAYOUT_ARITHMETIC) && !ENABLE(ENABLE_SUBPIXEL_LAYOUT)
> +#error "ENABLE_SATURATED_LAYOUT_ARITHMETIC requires ENABLE_SUBPIXEL_LAYOUT"
> +#endif

Just, please, please, please, if that ends up being unused, please remove the code.
We have so much dead code around already. :(

> Source/WTF/wtf/SaturatedArithmetic.h:47
> +    // Can only overflow if the signed bit of the two values match. If the signed
> +    // bit of the result and one of the values differ it did overflow.
> +    if (!((ua ^ ub) >> 31) & (result ^ ua) >> 31)
> +        result = std::numeric_limits<int>::max() + (ua >> 31);

I have the feeling we can do better with assembly and jump-if-overflow.
But for now that is a good start. :)

> Source/WTF/wtf/SaturatedArithmetic.h:61
> +    if ((ua ^ ub) >> 31 & (result ^ ua) >> 31)
> +        result = std::numeric_limits<int>::max() + (ua >> 31);

Ditto.

> Source/WebCore/platform/FractionalLayoutUnit.h:67
> -const int intMinForLayoutUnit = -intMaxForLayoutUnit;
> +const int intMinForLayoutUnit = INT_MIN / kFixedPointDenominator;

This looks correct but can't it be tested?

> Source/WebCore/platform/FractionalLayoutUnit.h:138
> +        REPORT_OVERFLOW(isInBounds(value));

Should't this be?:
REPORT_OVERFLOW(isInBounds(value + epsilon()));
REPORT_OVERFLOW(isInBounds(value - epsilon()));

> Source/WebCore/platform/FractionalLayoutUnit.h:274
> +        REPORT_OVERFLOW(isInBounds(value));

Not sure how that is even correct but that's the original code so....
Value can be in bounds and still have value * kFixedPointDenominator overflow.

> Source/WebCore/platform/FractionalLayoutUnit.h:286
> +        REPORT_OVERFLOW(isInBounds(value));

Ditto.

[Emil A Eklund]

Thank you, I'll address your concerns before committing.

(In reply to comment #25)
> Just, please, please, please, if that ends up being unused, please remove the code.
> We have so much dead code around already. :(

Of course.

[Emil A Eklund]

Created attachment 160229 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 160229 [details]
Patch for landing

Clearing flags on attachment: 160229

Committed r126509: <http://trac.webkit.org/changeset/126509>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.