Bug 139854 – Simplify saturated integer add/sub

• Component: New Bugs
• Status: RESOLVED FIXED

[Benjamin Poulain]

Use the overflow builtins when available for the trivial saturated arithmetic

[Benjamin Poulain]

Created attachment 243611 [details]
Patch

[Darin Adler]

Comment on attachment 243611 [details]
Patch

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

Not sure why the patch didn’t apply.

> Source/WTF/wtf/Compiler.h:38
> +/* COMPILER_HAS_BUILTIN() - wether the compiler supports a particular builtin. */

"whether" is misspelled here

Anders chose a different approach for __has_feature, a different macro for each feature. His approach can work for compilers that don’t use __has_feature or for checks that somehow need to be more complex. I suggest we follow the same pattern for __has_builtin and not add a general COMPILER_HAS_BUILTIN.

> Source/WTF/wtf/SaturatedArithmetic.h:45
> +        result = std::numeric_limits<int>::max() + (static_cast<uint32_t>(a) >> 31);

Would be nicer to structure things this so this line of code was shared.

I imagine code more like this:

    inline bool sadd_overflow(int32_t a, int32_t b, int32_t* result)
    {
#if COMPILER_SUPPORTS(BUILTIN_SADD_OVERFLOW)
        return __builtin_sadd_overflow(a, b, &result);
#else
        uint32_t ua = a;
        uint32_t ub = b;
        uint32_t uresult = ua + ub;
        *result = uresult;
        // 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.
        return !((ua ^ ub) >> 31) & (uresult ^ ua) >> 31;
#endif
    }

    inline int32_t saturatedAddition(int32_t a, int32_b)
    {
        int32_t result;
        if (__builtin_sadd_overflow(a, b, &result))
            result = std::numeric_limits<int>::max() + (static_cast<uint32_t>(a) >> 31);
        return result;
    }

[Benjamin Poulain]

(In reply to comment #2)
> Anders chose a different approach for __has_feature, a different macro for
> each feature. His approach can work for compilers that don’t use
> __has_feature or for checks that somehow need to be more complex. I suggest
> we follow the same pattern for __has_builtin and not add a general
> COMPILER_HAS_BUILTIN.

This is not completely similar.

The features are standard features that a compiler supports or don't support.

Builtins have different names and behavior depending on the compiler. MSVC uses completely different names for its builtins.

If we really want to abstract all of that, we will need 2 macros for each builtins: one to know if the builtin is defined, and one to abstract the name between compilers.

[Darin Adler]

(In reply to comment #3)
> (In reply to comment #2)
> > Anders chose a different approach for __has_feature, a different macro for
> > each feature. His approach can work for compilers that don’t use
> > __has_feature or for checks that somehow need to be more complex. I suggest
> > we follow the same pattern for __has_builtin and not add a general
> > COMPILER_HAS_BUILTIN.
> 
> This is not completely similar.
> 
> The features are standard features that a compiler supports or don't support.
> 
> Builtins have different names and behavior depending on the compiler. MSVC
> uses completely different names for its builtins.

OK. I’m still not certain this is the right design for compiler-independent macros to guard compiler-specific built-in. I can imagine two different compilers having built-ins with the same name but different arguments or semantics, and I’m not sure how COMPILER_HAS_BUILTIN(x) would be helpful for that case. I think that COMPILER_HAS_CLANG_BUILTIN(x) might be a more honest name for this macro if we might need a different one for different sets of built-ins.

[Anders Carlsson]

(In reply to comment #4)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > Anders chose a different approach for __has_feature, a different macro for
> > > each feature. His approach can work for compilers that don’t use
> > > __has_feature or for checks that somehow need to be more complex. I suggest
> > > we follow the same pattern for __has_builtin and not add a general
> > > COMPILER_HAS_BUILTIN.
> > 
> > This is not completely similar.
> > 
> > The features are standard features that a compiler supports or don't support.
> > 
> > Builtins have different names and behavior depending on the compiler. MSVC
> > uses completely different names for its builtins.
> 
> OK. I’m still not certain this is the right design for compiler-independent
> macros to guard compiler-specific built-in. I can imagine two different
> compilers having built-ins with the same name but different arguments or
> semantics, and I’m not sure how COMPILER_HAS_BUILTIN(x) would be helpful for
> that case. I think that COMPILER_HAS_CLANG_BUILTIN(x) might be a more honest
> name for this macro if we might need a different one for different sets of
> built-ins.

I agree with Darin, other compilers are going to be different enough that we should have separate feature macros.

[Benjamin Poulain]

Created attachment 243662 [details]
Patch

[WebKit Commit Bot]

Attachment 243662 [details] did not pass style-queue:


ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:58:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:62:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:45:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:58:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:62:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:58:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:62:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:80:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:92:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:75:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:80:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:92:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:80:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:92:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
Total errors found: 17 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Darin Adler]

Comment on attachment 243662 [details]
Patch

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

> Source/WTF/wtf/Compiler.h:38
> +/* COMPILER_HAS_BUILTIN() - wether the compiler supports a particular builtin. */

Comment still has the old name.

> Source/WTF/wtf/SaturatedArithmetic.h:54
>      uint32_t result = ua + ub;

Need to name the local variable something different, and also put the result into the reference passed in. Maybe:

   uint32_t uresult = ua + ub;
   result = uresult;

And then use uresult below instead of result. Or maybe you can just use result directly, but not sure if that would be right for the expression below.

> Source/WTF/wtf/SaturatedArithmetic.h:66
> +        result = std::numeric_limits<int>::max() + (static_cast<uint32_t>(a) >> 31);

It’s a little strange that we use int32_t type for the arguments, but just <int> for the template argument.

> Source/WTF/wtf/SaturatedArithmetic.h:70
> +inline bool signedSubstractOverflows(int32_t a, int32_t b, int32_t& result)

Typo here: "substract" with an extra "s".

> Source/WTF/wtf/SaturatedArithmetic.h:84
>      uint32_t result = ua - ub;

Ditto.

> Source/WTF/wtf/SaturatedArithmetic.h:96
> +        result = std::numeric_limits<int>::max() + (static_cast<uint32_t>(a) >> 31);

Ditto.

[Benjamin Poulain]

Created attachment 243687 [details]
Patch

[WebKit Commit Bot]

Attachment 243687 [details] did not pass style-queue:


ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:55:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:59:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:63:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:45:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:55:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:59:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:63:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:50:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:55:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:59:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:63:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:81:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:86:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:94:  Wrong number of spaces before statement. (expected: 8)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:76:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:81:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:86:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:94:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:81:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:86:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/SaturatedArithmetic.h:94:  Wrong number of spaces before statement. (expected: 12)  [whitespace/indent] [4]
Total errors found: 23 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Darin Adler]

Comment on attachment 243687 [details]
Patch

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

> Source/WTF/wtf/SaturatedArithmetic.h:48
> +#if CPU(ARM_THUMB2)
> +    asm("qadd %[sum], %[addend], %[augend]"
> +        : [sum]"=r"(result)
> +        : [augend]"r"(a), [addend]"r"(b)
> +        : /* Nothing is clobbered. */
> +    );
> +    return false;

I don’t think this is exactly right. I think this conditional part should be in the saturatedAddition function below, not here. It’s a way to do saturated addition, not a way to do an addition and detect overflow.

> Source/WTF/wtf/SaturatedArithmetic.h:55
> +    result = static_cast<int32_t>(uresult);

I don’t think we need a cast here, unless it’s maybe to prevent warnings with certain compilers?

> Source/WTF/wtf/SaturatedArithmetic.h:59
> +    return !((ua ^ ub) >> 31) & (result ^ ua) >> 31;

I think this should use uresult instead of result (as you do below in signedSubtractOverflows.

But if it’s OK for this to use a signed integer here, then we don’t need uresult at all.

> Source/WTF/wtf/SaturatedArithmetic.h:79
> +#if CPU(ARM_THUMB2)
> +    asm("qsub %[difference], %[minuend], %[subtrahend]"
> +        : [difference]"=r"(result)
> +        : [minuend]"r"(a), [subtrahend]"r"(b)
> +        : /* Nothing is clobbered. */
> +        );
> +    return false;

Same comment as above.

> Source/WTF/wtf/SaturatedArithmetic.h:86
> +    result = static_cast<int32_t>(uresult);

Same comment as above.

[Benjamin Poulain]

Committed r177729: <http://trac.webkit.org/changeset/177729>

[Benjamin Poulain]

I hope I did not mess up this time :)

I kept the cast for people who enable the warnings.

[Darin Adler]

Looks like saturated subtract might is broken:

    result = std::numeric_limits<uint32_t>::max() + (static_cast<uint32_t>(a) >> 31); 

I think that should be std::numeric_limits<int32_t>::max().

Also, technically to get defined overflow behavior I think we need to cast that to uint32_t in both places it is used. But that’s just a pedantic nitpick that doesn’t really matter.

[Alexey Proskuryakov]

Yes, this broke an API test:

[ RUN      ] WTF.SaturatedArithmeticSubtraction
/Volumes/Data/slave/yosemite-debug/build/Tools/TestWebKitAPI/Tests/WTF/SaturatedArithmeticOperations.cpp:89: Failure
Value of: 2147483647
Expected: saturatedSubtraction(2147483647 - 1, -2)
Which is: -1
[  FAILED  ] WTF.SaturatedArithmeticSubtraction (1 ms)

[Alexey Proskuryakov]

> I think that should be std::numeric_limits<int32_t>::max().

Landed this change in <http://trac.webkit.org/r177736> after verifying that it fixes API tests locally.

(In reply to comment #12)
> Committed r177729: <http://trac.webkit.org/changeset/177729>

I reverted that use of __builtin_s{add,sub}_overflow in <http://trac.webkit.org/r177753>, because it was causing a compiler used at Apple to crash.

(In reply to comment #17)
> (In reply to comment #12)
> > Committed r177729: <http://trac.webkit.org/changeset/177729>
> 
> I reverted that use of __builtin_s{add,sub}_overflow in
> <http://trac.webkit.org/r177753>, because it was causing a compiler used at
> Apple to crash.

I reverted the reversion in <http://trac.webkit.org/r184369>.