Title: [232253] trunk/Source/_javascript_Core
- Revision
- 232253
- Author
- utatane....@gmail.com
- Date
- 2018-05-28 23:43:38 -0700 (Mon, 28 May 2018)
Log Message
[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:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (232252 => 232253)
--- trunk/Source/_javascript_Core/ChangeLog 2018-05-29 03:46:35 UTC (rev 232252)
+++ trunk/Source/_javascript_Core/ChangeLog 2018-05-29 06:43:38 UTC (rev 232253)
@@ -1,5 +1,31 @@
2018-05-27 Yusuke Suzuki <utatane....@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....@gmail.com>
+
[WTF] Add clz32 / clz64 for MSVC
https://bugs.webkit.org/show_bug.cgi?id=186023
Modified: trunk/Source/_javascript_Core/runtime/JSBigInt.cpp (232252 => 232253)
--- trunk/Source/_javascript_Core/runtime/JSBigInt.cpp 2018-05-29 03:46:35 UTC (rev 232252)
+++ trunk/Source/_javascript_Core/runtime/JSBigInt.cpp 2018-05-29 06:43:38 UTC (rev 232253)
@@ -354,7 +354,7 @@
// 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,7 +433,7 @@
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);
@@ -440,16 +440,26 @@
#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;
@@ -456,26 +466,26 @@
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 @@
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.
Modified: trunk/Source/_javascript_Core/runtime/JSBigInt.h (232252 => 232253)
--- trunk/Source/_javascript_Core/runtime/JSBigInt.h 2018-05-29 03:46:35 UTC (rev 232252)
+++ trunk/Source/_javascript_Core/runtime/JSBigInt.h 2018-05-29 06:43:38 UTC (rev 232253)
@@ -110,17 +110,17 @@
};
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);
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
