[JSC] JSBigInt::digitDiv has undefined behavior which causes test failures
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 29 May 2018 06:43:38 +0000 (06:43 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 29 May 2018 06:43:38 +0000 (06:43 +0000)
https://bugs.webkit.org/show_bug.cgi?id=186022

Reviewed by Darin Adler.

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:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@232253 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/JSBigInt.cpp
Source/JavaScriptCore/runtime/JSBigInt.h

index c64ee95..9101f8a 100644 (file)
@@ -1,5 +1,31 @@
 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 Darin Adler.
+
+        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  Yusuke Suzuki  <utatane.tea@gmail.com>
+
         [WTF] Add clz32 / clz64 for MSVC
         https://bugs.webkit.org/show_bug.cgi?id=186023
 
index cfee119..e5fbd19 100644 (file)
@@ -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,59 @@ inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor,
     remainder = rem;
     return quotient;
 #else
-    static const Digit kHalfDigitBase = 1ull << halfDigitBits;
+    static constexpr 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} <= (digitBits - 1) cases. {s} == digitBits 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 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;
+    remainder = (un21 * halfDigitBase + un0 - q0 * divisor) >> s;
+    return q1 * halfDigitBase + q0;
 #endif
 }
 
@@ -843,8 +853,8 @@ constexpr uint8_t maxBitsPerCharTable[] = {
     162, 163, 165, 166,                         // 33..36
 };
 
-static const unsigned bitsPerCharTableShift = 5;
-static const size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
+static constexpr unsigned bitsPerCharTableShift = 5;
+static constexpr size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
 
 // Compute (an overapproximation of) the length of the resulting string:
 // Divide bit length of the BigInt by bits representable per character.
index 533ff4a..9ee0cdd 100644 (file)
@@ -110,17 +110,17 @@ private:
     };
 
     using Digit = uintptr_t;
-    static constexpr const unsigned bitsPerByte = 8;
-    static constexpr const unsigned digitBits = sizeof(Digit) * bitsPerByte;
-    static constexpr const unsigned halfDigitBits = digitBits / 2;
-    static constexpr const Digit halfDigitMask = (1ull << halfDigitBits) - 1;
-    static constexpr const int maxInt = 0x7FFFFFFF;
+    static constexpr unsigned bitsPerByte = 8;
+    static constexpr unsigned digitBits = sizeof(Digit) * bitsPerByte;
+    static constexpr unsigned halfDigitBits = digitBits / 2;
+    static constexpr Digit halfDigitMask = (1ull << halfDigitBits) - 1;
+    static constexpr int maxInt = 0x7FFFFFFF;
     
     // The maximum length that the current implementation supports would be
     // 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 unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
     
     static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);