Attachment 341443 Details for Bug 186022 – Patch

[patch] Patch

bug-186022-20180528134349.patch (text/plain), 8.38 KB, created by Yusuke Suzuki on 2018-05-27 21:43:50 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Yusuke Suzuki

Created: 2018-05-27 21:43:50 PDT

Size: 8.38 KB

patch

obsolete

>Subversion Revision: 232236
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index a6acb1a28ca05f32b765ffdba78080dd5638063d..a60d53033306eddaec4b25eac991e5e127a00ad3 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,29 @@
>+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 an issue (`s` should be casted to signed one before negating). They cause test failures
>+        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. We mask the left value of the
>+        rshift with `digitBits - 1`, which makes `digitBits` 0 while it keeps 0 <= n < digitBits values.
>+        This makes the target rshift well-defined in C++. While produced value by the rshift covers 0 <= `s` < 64 (32
>+        in 32bit envirnoment) cases, this rshift does not shift if `s` is 0. sZeroMask clears the value
>+        if `s` is 0, so that `s == 0` case is also covered. Note that `s == 64` never happens since `divisor`
>+        is never 0 here. We add assertion for that. We also fixes `sZeroMask` calculation.
>+
>+        This patch also fixes naming convention for constant values.
>+
>+        * runtime/JSBigInt.cpp:
>+        (JSC::JSBigInt::digitMul):
>+        (JSC::JSBigInt::digitDiv):
>+        * runtime/JSBigInt.h:
>+
> 2018-05-27  Caio Lima  <ticaiolima@gmail.com>
> 
>         [ESNext][BigInt] Implement "+" and "-" unary operation
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.cpp b/Source/JavaScriptCore/runtime/JSBigInt.cpp
>index cfee1194f7f86e07414278b29c33509bb2dc951f..c3765984fe0323c4b19749e0a05a26adf37990a5 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;
> 
>@@ -410,73 +410,83 @@ inline JSBigInt::Digit JSBigInt::digitPow(Digit base, Digit exponent)
> inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder)
> {
>     ASSERT(high < divisor);
>-#if CPU(X86_64) && COMPILER(GCC_OR_CLANG)
>-    Digit quotient;
>-    Digit rem;
>-    __asm__("divq  %[divisor]"
>-        // Outputs: {quotient} will be in rax, {rem} in rdx.
>-        : "=a"(quotient), "=d"(rem)
>-        // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
>-        // any register or stack slot.
>-        : "d"(high), "a"(low), [divisor] "rm"(divisor));
>-    remainder = rem;
>-    return quotient;
>-#elif CPU(X86) && COMPILER(GCC_OR_CLANG)
>-    Digit quotient;
>-    Digit rem;
>-    __asm__("divl  %[divisor]"
>-        // Outputs: {quotient} will be in eax, {rem} in edx.
>-        : "=a"(quotient), "=d"(rem)
>-        // Inputs: put {high} into edx, {low} into eax, and {divisor} into
>-        // any register or stack slot.
>-        : "d"(high), "a"(low), [divisor] "rm"(divisor));
>-    remainder = rem;
>-    return quotient;
>-#else
>-    static const Digit kHalfDigitBase = 1ull << halfDigitBits;
>+// #if CPU(X86_64) && COMPILER(GCC_OR_CLANG)
>+//     Digit quotient;
>+//     Digit rem;
>+//     __asm__("divq  %[divisor]"
>+//         // Outputs: {quotient} will be in rax, {rem} in rdx.
>+//         : "=a"(quotient), "=d"(rem)
>+//         // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
>+//         // any register or stack slot.
>+//         : "d"(high), "a"(low), [divisor] "rm"(divisor));
>+//     remainder = rem;
>+//     return quotient;
>+// #elif CPU(X86) && COMPILER(GCC_OR_CLANG)
>+//     Digit quotient;
>+//     Digit rem;
>+//     __asm__("divl  %[divisor]"
>+//         // Outputs: {quotient} will be in eax, {rem} in edx.
>+//         : "=a"(quotient), "=d"(rem)
>+//         // Inputs: put {high} into edx, {low} into eax, and {divisor} into
>+//         // any register or stack slot.
>+//         : "d"(high), "a"(low), [divisor] "rm"(divisor));
>+//     remainder = rem;
>+//     return quotient;
>+// #else
>+    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.
>+    // {sZeroMask} which is 0 if s == 0 and all 1-bits otherwise.
>+    // {s} can be 0. If {s} is 0, performing "low >> (digitBits - s)" must not be done since it causes an undefined behavior
>+    // since `>> digitBits` is undefied in C++. 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". We mask the right operand of the shift by {shiftMask} (`digitBits - 1`), which makes `digitBits - 0` zero.
>+    // This shifting produces a value which covers 0 < {s} <= 31 cases. {s} == 32 never happen as we asserted. Since {sZeroMask}
>+    // clears the value in the case of {s} == 0, {s} == 0 case is also covered.
>     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);
>+    Digit sZeroMask = static_cast<Digit>((-static_cast<intptr_t>(s)) >> (digitBits - 1));
>+    static constexpr const unsigned shiftMask = digitBits - 1;
>+    Digit un32 = (high << s) | ((low >> ((digitBits - s) & shiftMask)) & sZeroMask);
>+
>     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;
>-#endif
>+    remainder = (un21 * halfDigitBase + un0 - q0 * divisor) >> s;
>+    return q1 * halfDigitBase + q0;
>+// #endif
> }
> 
> // Multiplies {source} with {factor} and adds {summand} to the result.
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.h b/Source/JavaScriptCore/runtime/JSBigInt.h
>index 533ff4a5cf503a1a11c01e253f7f56b166880193..9506397f7ba1129fb3c75db0f82f699edc0ac1d7 100644
>--- a/Source/JavaScriptCore/runtime/JSBigInt.h
>+++ b/Source/JavaScriptCore/runtime/JSBigInt.h
>@@ -120,7 +120,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