Attachment 341424 Details for Bug 186022 – Patch

[patch] Patch

bug-186022-20180528030356.patch (text/plain), 5.76 KB, created by Yusuke Suzuki on 2018-05-27 11:03:57 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Yusuke Suzuki

Created: 2018-05-27 11:03:57 PDT

Size: 5.76 KB

patch

obsolete

>Subversion Revision: 232227
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index af3750dbd8078b60b991510cce07a747579a80f1..f41ebea494d12edb5ae21538ec7c833fa7bc623f 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,25 @@
>+2018-05-27  Yusuke Suzuki  <utatane.tea@gmail.com>
>+
>+        [JSC] JSBigInt::digitDiv has undefined behavior which causes test failures
>+        https://bugs.webkit.org/show_bug.cgi?id=186022
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        digitDiv performs Value64Bit >> 64 / Value32Bit >> 32, which is undefined behavior. And zero mask
>+        creation has a bug (s should be casted to signed one before negating). These behaviors break
>+        tests in non x86 / x86_64 environments. x86 and x86_64 work well since they have a fast path written
>+        in asm.
>+
>+        This patch fixes digitDiv by carefully avoiding undefined behaviors. According to the dumped asm,
>+        using TwoDigit before rshift generates correct and efficient code compared to `if (s)` check. So
>+        we added optimized path with TwoDigit. This is important since while x86 does not use it, ARM64
>+        uses this code.
>+
>+        * runtime/JSBigInt.cpp:
>+        (JSC::JSBigInt::digitMul):
>+        (JSC::JSBigInt::digitDiv):
>+        * runtime/JSBigInt.h:
>+
> 2018-05-26  Yusuke Suzuki  <utatane.tea@gmail.com>
> 
>         [JSC] Rename Array#flatten to flat
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.cpp b/Source/JavaScriptCore/runtime/JSBigInt.cpp
>index 0e021f1380cad9bcd8c2f8f5dffefdbae9f71a8b..f5e74e47945aa86f0768bfd6f26a5d48fac8031f 100644
>--- a/Source/JavaScriptCore/runtime/JSBigInt.cpp
>+++ b/Source/JavaScriptCore/runtime/JSBigInt.cpp
>@@ -354,7 +354,7 @@ inline JSBigInt::Digit JSBigInt::digitSub(Digit a, Digit b, Digit& borrow)
> // Returns the low half of the result. High half is in {high}.
> inline JSBigInt::Digit JSBigInt::digitMul(Digit a, Digit b, Digit& high)
> {
>-#if HAVE_TWO_DIGIT
>+#if HAVE(TWO_DIGIT)
>     TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
>     high = result >> digitBits;
> 
>@@ -433,49 +433,58 @@ inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor,
>     remainder = rem;
>     return quotient;
> #else
>-    static const Digit kHalfDigitBase = 1ull << halfDigitBits;
>+    static constexpr const Digit halfDigitBase = 1ull << halfDigitBits;
>     // Adapted from Warren, Hacker's Delight, p. 152.
> #if USE(JSVALUE64)
>     unsigned s = clz64(divisor);
> #else
>     unsigned s = clz32(divisor);
> #endif
>+    // If {s} is digitBits here, it causes an undefined behavior.
>+    // But {s} is never digitBits since {divisor} is never zero here.
>+    ASSERT(s != digitBits);
>     divisor <<= s;
>-    
>+
>     Digit vn1 = divisor >> halfDigitBits;
>     Digit vn0 = divisor & halfDigitMask;
> 
>-    // {s} can be 0. "low >> digitBits == low" on x86, so we "&" it with
>-    // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
>-    STATIC_ASSERT(sizeof(intptr_t) == sizeof(Digit));
>-    Digit sZeroMask = static_cast<Digit>(static_cast<intptr_t>(-s) >> (digitBits - 1));
>-    Digit un32 = (high << s) | ((low >> (digitBits - s)) & sZeroMask);
>+    // {s} can be 0. If {s} is 0, performing "low >> (digitBits - s)" must not be done since it causes an undefined behavior.
>+    // If we have TwoDigit, we can extend the left operand before performing the right shift with digitBits.
>+    // Quoted from C++ spec: "The type of the result is that of the promoted left operand. The behavior is undefined if the
>+    // right operand is negative, or greater than or equal to the length in bits of the promoted left operand".
>+#if HAVE(TWO_DIGIT)
>+    Digit un32 = (high << s) | static_cast<Digit>((static_cast<TwoDigit>(low) >> (digitBits - s)));
>+#else
>+    Digit un32 = (high << s);
>+    if (s)
>+        un32 += (low >> (digitBits - s));
>+#endif
>     Digit un10 = low << s;
>     Digit un1 = un10 >> halfDigitBits;
>     Digit un0 = un10 & halfDigitMask;
>     Digit q1 = un32 / vn1;
>     Digit rhat = un32 - q1 * vn1;
> 
>-    while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
>+    while (q1 >= halfDigitBase || q1 * vn0 > rhat * halfDigitBase + un1) {
>         q1--;
>         rhat += vn1;
>-        if (rhat >= kHalfDigitBase)
>+        if (rhat >= halfDigitBase)
>             break;
>     }
> 
>-    Digit un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
>+    Digit un21 = un32 * halfDigitBase + un1 - q1 * divisor;
>     Digit q0 = un21 / vn1;
>     rhat = un21 - q0 * vn1;
> 
>-    while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
>+    while (q0 >= halfDigitBase || q0 * vn0 > rhat * halfDigitBase + un0) {
>         q0--;
>         rhat += vn1;
>-        if (rhat >= kHalfDigitBase)
>+        if (rhat >= halfDigitBase)
>             break;
>     }
> 
>-    remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
>-    return q1 * kHalfDigitBase + q0;
>+    remainder = (un21 * halfDigitBase + un0 - q0 * divisor) >> s;
>+    return q1 * halfDigitBase + q0;
> #endif
> }
> 
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.h b/Source/JavaScriptCore/runtime/JSBigInt.h
>index 67650fc2f368b58fdee550c677e2c628476b7200..8c53bf6bb0054e5c0d0f99c1a38f3ff12ce1bcf8 100644
>--- a/Source/JavaScriptCore/runtime/JSBigInt.h
>+++ b/Source/JavaScriptCore/runtime/JSBigInt.h
>@@ -117,7 +117,7 @@ class JSBigInt final : public JSCell {
>     // maxInt / digitBits. However, we use a lower limit for now, because
>     // raising it later is easier than lowering it.
>     // Support up to 1 million bits.
>-    static const unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
>+    static constexpr const unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
>     
>     static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);
>

Actions: View | Formatted Diff | Diff

Attachments on bug 186022: 341424 | 341425 | 341426 | 341427 | 341443 | 341444 | 341445