+2018-05-16 Caio Lima <ticaiolima@gmail.com>
+
+ [ESNext][BigInt] Implement support for "/" operation
+ https://bugs.webkit.org/show_bug.cgi?id=183996
+
+ Reviewed by Yusuke Suzuki.
+
+ * bigIntTests.yaml:
+ * stress/big-int-div-jit.js: Added.
+ * stress/big-int-div-memory-stress.js: Added.
+ * stress/big-int-div-to-primitive-precedence.js: Added.
+ * stress/big-int-div-to-primitive.js: Added.
+ * stress/big-int-div-type-error.js: Added.
+ * stress/big-int-div-wrapped-value.js: Added.
+ * stress/big-int-division.js: Added.
+
2018-05-14 Leo Balter <leonardo.balter@gmail.com>
Fix a legacy CRLF eol from Test262
- path: stress/big-int-multiply-memory-stress.js
cmd: runBigIntEnabled
+- path: stress/big-int-div-jit.js
+ cmd: runBigIntEnabled
+
+- path: stress/big-int-div-memory-stress.js
+ cmd: runBigIntEnabled
+
+- path: stress/big-int-div-to-primitive.js
+ cmd: runBigIntEnabled
+
+- path: stress/big-int-div-type-error.js
+ cmd: runBigIntEnabled
+
+- path: stress/big-int-div-wrapped-value.js
+ cmd: runBigIntEnabled
+
+- path: stress/big-int-division.js
+ cmd: runBigIntEnabled
--- /dev/null
+//@ runBigIntEnabled
+
+let assert = {
+ sameValue: function(i, e, m) {
+ if (i !== e)
+ throw new Error(m);
+ }
+}
+
+function bigIntDiv(x, y) {
+ return x / y;
+}
+noInline(bigIntDiv);
+
+for (let i = 0; i < 10000; i++) {
+ let r = bigIntDiv(30n, 10n);
+ assert.sameValue(r, 3n, 30n + " / " + 10n + " = " + r);
+}
+
--- /dev/null
+//@ runBigIntEnabled
+
+function assert(a) {
+ if (!a)
+ throw new Error("Bad assertion");
+}
+
+let a = 0n;
+let b = 30n;
+for (let i = 0; i < 1000000; i++) {
+ a = b / 2n;
+}
+
+assert(a === 15n);
+
--- /dev/null
+//@ runBigIntEnabled
+
+function assert(a) {
+ if (!a)
+ throw new Error("Bad assertion");
+}
+
+assert.sameValue = function (input, expected, message) {
+ if (input !== expected)
+ throw new Error(message);
+}
+
+function testDiv(x, y, z) {
+ assert.sameValue(x / y, z, x + " / " + y + " = " + z);
+}
+
+let o = {
+ [Symbol.toPrimitive]: function () { return 300000000000n; }
+}
+
+testDiv(500000000000438n, o, 1666n);
+
+o.valueOf = function () {
+ throw new Error("Should never execute it");
+};
+
+testDiv(700000000000438n, o, 2333n);
+
+o.toString = function () {
+ throw new Error("Should never execute it");
+};
+
+testDiv(700000000000438n, o, 2333n);
+
--- /dev/null
+//@ runBigIntEnabled
+
+function assert(a, message) {
+ if (!a)
+ throw new Error(message);
+}
+
+function assertThrowTypeError(a, b, message) {
+ try {
+ let n = a / b;
+ assert(false, message + ": Should throw TypeError, but executed without exception");
+ } catch (e) {
+ assert(e instanceof TypeError, message + ": expected TypeError, got: " + e);
+ }
+}
+
+assertThrowTypeError(30n, "foo", "BigInt / String");
+assertThrowTypeError("bar", 18757382984821n, "String / BigInt");
+assertThrowTypeError(30n, Symbol("foo"), "BigInt / Symbol");
+assertThrowTypeError(Symbol("bar"), 18757382984821n, "Symbol / BigInt");
+assertThrowTypeError(30n, 3320, "BigInt / Int32");
+assertThrowTypeError(33256, 18757382984821n, "Int32 / BigInt");
+assertThrowTypeError(30n, 0.543, "BigInt / Double");
+assertThrowTypeError(230.19293, 18757382984821n, "Double / BigInt");
+assertThrowTypeError(30n, NaN, "BigInt / NaN");
+assertThrowTypeError(NaN, 18757382984821n, "NaN / BigInt");
+assertThrowTypeError(30n, NaN, "BigInt / NaN");
+assertThrowTypeError(NaN, 18757382984821n, "NaN / BigInt");
+assertThrowTypeError(30n, +Infinity, "BigInt / NaN");
+assertThrowTypeError(+Infinity, 18757382984821n, "NaN / BigInt");
+assertThrowTypeError(30n, -Infinity, "BigInt / -Infinity");
+assertThrowTypeError(-Infinity, 18757382984821n, "-Infinity / BigInt");
+assertThrowTypeError(30n, null, "BigInt / null");
+assertThrowTypeError(null, 18757382984821n, "null / BigInt");
+assertThrowTypeError(30n, undefined, "BigInt / undefined");
+assertThrowTypeError(undefined, 18757382984821n, "undefined / BigInt");
+assertThrowTypeError(30n, true, "BigInt * true");
+assertThrowTypeError(true, 18757382984821n, "true / BigInt");
+assertThrowTypeError(30n, false, "BigInt / false");
+assertThrowTypeError(false, 18757382984821n, "false / BigInt");
+
+// Error when returning from object
+
+let o = {
+ valueOf: function () { return Symbol("Foo"); }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.valueOf returning Symbol");
+assertThrowTypeError(o, 18757382984821n, "Object.valueOf returning Symbol / BigInt");
+
+o = {
+ valueOf: function () { return 33256; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.valueOf returning Int32");
+assertThrowTypeError(o, 18757382984821n, "Object.valueOf returning Int32 / BigInt");
+
+o = {
+ valueOf: function () { return 0.453; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.valueOf returning Double");
+assertThrowTypeError(o, 18757382984821n, "Object.valueOf returning Double / BigInt");
+
+o = {
+ toString: function () { return Symbol("Foo"); }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.toString returning Symbol");
+assertThrowTypeError(o, 18757382984821n, "Object.toString returning Symbol / BigInt");
+
+o = {
+ toString: function () { return 33256; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.toString returning Int32");
+assertThrowTypeError(o, 18757382984821n, "Object.toString returning Int32 / BigInt");
+
+o = {
+ toString: function () { return 0.453; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.toString returning Double");
+assertThrowTypeError(o, 18757382984821n, "Object.toString returning Double / BigInt");
+
+o = {
+ [Symbol.toPrimitive]: function () { return Symbol("Foo"); }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.@@toPrimitive returning Symbol");
+assertThrowTypeError(o, 18757382984821n, "Object.@@toPrimitive returning Symbol / BigInt");
+
+o = {
+ [Symbol.toPrimitive]: function () { return 33256; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.@@toPrimitive returning Int32");
+assertThrowTypeError(o, 18757382984821n, "Object.@@toPrimitive returning Int32 / BigInt");
+
+o = {
+ [Symbol.toPrimitive]: function () { return 0.453; }
+};
+
+assertThrowTypeError(30n, o, "BigInt / Object.@@toPrimitive returning Double");
+assertThrowTypeError(o, 18757382984821n, "Object.@@toPrimitive returning Double / BigInt");
+
--- /dev/null
+//@ runBigIntEnabled
+
+assert = {
+ sameValue: function (input, expected, message) {
+ if (input !== expected)
+ throw new Error(message);
+ }
+};
+
+function testDiv(x, y, z, message) {
+ assert.sameValue(x / y, z, message);
+}
+
+testDiv(Object(2n), 1n, 2n, "ToPrimitive: unbox object with internal slot");
+
+let o = {
+ [Symbol.toPrimitive]: function() {
+ return 2n;
+ }
+};
+testDiv(o, 1n, 2n, "ToPrimitive: @@toPrimitive");
+
+o = {
+ valueOf: function() {
+ return 2n;
+ }
+};
+testDiv(o, 1n, 2n, "ToPrimitive: valueOf");
+
+o = {
+ toString: function() {
+ return 2n;
+ }
+}
+testDiv(o, 1n, 2n, "ToPrimitive: toString");
+
+o = {
+ valueOf: function() {
+ return 2n;
+ },
+ toString: function () {
+ throw new Error("Should never execute it");
+ }
+};
+testDiv(o, 1n, 2n, "ToPrimitive: valueOf");
+
--- /dev/null
+//@ runBigIntEnabled
+
+// Copyright (C) 2017 Robin Templeton. All rights reserved.
+// This code is governed by the BSD license found in the LICENSE file.
+
+function assert(a) {
+ if (!a)
+ throw new Error("Bad assertion");
+}
+
+assert.sameValue = function (input, expected, message) {
+ if (input !== expected)
+ throw new Error(message);
+}
+
+function testDiv(x, y, z) {
+ assert.sameValue(x / y, z, x + " / " + y + " = " + z);
+}
+
+testDiv(0xFEDCBA9876543210n, 0xFEDCBA9876543210n, 0x1n);
+testDiv(0xFEDCBA9876543210n, 0xFEDCBA987654320Fn, 0x1n);
+testDiv(0xFEDCBA9876543210n, 0xFEDCBA98n, 0x100000000n);
+testDiv(0xFEDCBA9876543210n, 0xFEDCBA97n, 0x100000001n);
+testDiv(0xFEDCBA9876543210n, 0x1234n, 0xE0042813BE5DCn);
+testDiv(0xFEDCBA9876543210n, 0x3n, 0x54F43E32D21C10B0n);
+testDiv(0xFEDCBA9876543210n, 0x2n, 0x7F6E5D4C3B2A1908n);
+testDiv(0xFEDCBA9876543210n, 0x1n, 0xFEDCBA9876543210n);
+testDiv(0xFEDCBA9876543210n, BigInt("-1"), BigInt("-18364758544493064720"));
+testDiv(0xFEDCBA9876543210n, BigInt("-2"), BigInt("-9182379272246532360"));
+testDiv(0xFEDCBA9876543210n, BigInt("-3"), BigInt("-6121586181497688240"));
+testDiv(0xFEDCBA9876543210n, BigInt("-4275878551"), BigInt("-4294967297"));
+testDiv(0xFEDCBA9876543210n, BigInt("-18364758544493064719"), BigInt("-1"));
+testDiv(0xFEDCBA987654320Fn, 0xFEDCBA9876543210n, 0x0n);
+testDiv(0xFEDCBA987654320Fn, 0xFEDCBA987654320Fn, 0x1n);
+testDiv(0xFEDCBA987654320Fn, 0xFEDCBA98n, 0x100000000n);
+testDiv(0xFEDCBA987654320Fn, 0xFEDCBA97n, 0x100000001n);
+testDiv(0xFEDCBA987654320Fn, 0x1234n, 0xE0042813BE5DCn);
+testDiv(0xFEDCBA987654320Fn, 0x3n, 0x54F43E32D21C10AFn);
+testDiv(0xFEDCBA987654320Fn, 0x2n, 0x7F6E5D4C3B2A1907n);
+testDiv(0xFEDCBA987654320Fn, 0x1n, 0xFEDCBA987654320Fn);
+testDiv(0xFEDCBA98n, 0xFEDCBA9876543210n, 0x0n);
+testDiv(0xFEDCBA98n, 0xFEDCBA987654320Fn, 0x0n);
+testDiv(0xFEDCBA98n, 0xFEDCBA98n, 0x1n);
+testDiv(0xFEDCBA98n, 0xFEDCBA97n, 0x1n);
+testDiv(0xFEDCBA98n, 0x1234n, 0xE0042n);
+testDiv(0xFEDCBA98n, 0x3n, 0x54F43E32n);
+testDiv(0xFEDCBA98n, 0x2n, 0x7F6E5D4Cn);
+testDiv(0xFEDCBA98n, 0x1n, 0xFEDCBA98n);
+testDiv(0xFEDCBA98n, BigInt("-1"), BigInt("-4275878552"));
+testDiv(0xFEDCBA98n, BigInt("-2"), BigInt("-2137939276"));
+testDiv(0xFEDCBA98n, BigInt("-3"), BigInt("-1425292850"));
+testDiv(0xFEDCBA98n, BigInt("-4275878551"), BigInt("-1"));
+testDiv(0xFEDCBA98n, BigInt("-18364758544493064719"), 0x0n);
+testDiv(0xFEDCBA97n, 0xFEDCBA9876543210n, 0x0n);
+testDiv(0xFEDCBA97n, 0xFEDCBA987654320Fn, 0x0n);
+testDiv(0xFEDCBA97n, 0xFEDCBA98n, 0x0n);
+testDiv(0xFEDCBA97n, 0xFEDCBA97n, 0x1n);
+testDiv(0xFEDCBA97n, 0x1234n, 0xE0042n);
+testDiv(0xFEDCBA97n, 0x3n, 0x54F43E32n);
+testDiv(0xFEDCBA97n, 0x2n, 0x7F6E5D4Bn);
+testDiv(0xFEDCBA97n, 0x1n, 0xFEDCBA97n);
+testDiv(0x3n, 0xFEDCBA9876543210n, 0x0n);
+testDiv(0x3n, 0xFEDCBA98n, 0x0n);
+testDiv(0x3n, 0x1234n, 0x0n);
+testDiv(0x3n, 0x3n, 0x1n);
+testDiv(0x3n, 0x2n, 0x1n);
+testDiv(0x3n, 0x1n, 0x3n);
+testDiv(0x3n, BigInt("-2"), BigInt("-1"));
+testDiv(0x3n, BigInt("-3"), BigInt("-1"));
+testDiv(0x3n, BigInt("-4275878551"), 0x0n);
+testDiv(0x3n, BigInt("-18364758544493064719"), 0x0n);
+testDiv(0x2n, 0xFEDCBA98n, 0x0n);
+testDiv(0x2n, 0xFEDCBA97n, 0x0n);
+testDiv(0x2n, 0x3n, 0x0n);
+testDiv(0x2n, 0x1n, 0x2n);
+testDiv(0x2n, BigInt("-1"), BigInt("-2"));
+testDiv(0x2n, BigInt("-2"), BigInt("-1"));
+testDiv(0x2n, BigInt("-3"), 0x0n);
+testDiv(0x1n, 0x1234n, 0x0n);
+testDiv(0x1n, 0x3n, 0x0n);
+testDiv(0x1n, 0x2n, 0x0n);
+testDiv(0x1n, 0x1n, 0x1n);
+testDiv(0x1n, BigInt("-1"), BigInt("-1"));
+testDiv(0x1n, BigInt("-3"), 0x0n);
+testDiv(0x1n, BigInt("-4660"), 0x0n);
+testDiv(0x1n, BigInt("-18364758544493064719"), 0x0n);
+testDiv(BigInt("-1"), 0xFEDCBA9876543210n, 0x0n);
+testDiv(BigInt("-1"), 0xFEDCBA987654320Fn, 0x0n);
+testDiv(BigInt("-1"), 0xFEDCBA98n, 0x0n);
+testDiv(BigInt("-1"), 0xFEDCBA97n, 0x0n);
+testDiv(BigInt("-1"), 0x3n, 0x0n);
+testDiv(BigInt("-1"), 0x1n, BigInt("-1"));
+testDiv(BigInt("-1"), BigInt("-3"), 0x0n);
+testDiv(BigInt("-1"), BigInt("-4660"), 0x0n);
+testDiv(BigInt("-1"), BigInt("-18364758544493064719"), 0x0n);
+testDiv(BigInt("-2"), 0xFEDCBA9876543210n, 0x0n);
+testDiv(BigInt("-3"), 0x3n, BigInt("-1"));
+testDiv(BigInt("-3"), 0x2n, BigInt("-1"));
+testDiv(BigInt("-3"), BigInt("-1"), 0x3n);
+testDiv(BigInt("-3"), BigInt("-3"), 0x1n);
+testDiv(BigInt("-3"), BigInt("-4660"), 0x0n);
+testDiv(BigInt("-3"), BigInt("-4275878551"), 0x0n);
+testDiv(BigInt("-3"), BigInt("-4275878552"), 0x0n);
+testDiv(BigInt("-3"), BigInt("-18364758544493064720"), 0x0n);
+testDiv(BigInt("-18364758544493064719"), 0xFEDCBA97n, BigInt("-4294967297"));
+testDiv(BigInt("-18364758544493064719"), 0x1234n, BigInt("-3940935309977052"));
+testDiv(BigInt("-18364758544493064719"), 0x3n, BigInt("-6121586181497688239"));
+testDiv(BigInt("-18364758544493064719"), 0x2n, BigInt("-9182379272246532359"));
+testDiv(BigInt("-18364758544493064719"), 0x1n, BigInt("-18364758544493064719"));
+testDiv(BigInt("-18364758544493064719"), BigInt("-1"), 0xFEDCBA987654320Fn);
+testDiv(BigInt("-18364758544493064719"), BigInt("-4275878551"), 0x100000001n);
+testDiv(BigInt("-18364758544493064719"), BigInt("-18364758544493064719"), 0x1n);
+testDiv(BigInt("-18364758544493064720"), 0xFEDCBA9876543210n, BigInt("-1"));
+testDiv(BigInt("-18364758544493064720"), 0x1234n, BigInt("-3940935309977052"));
+testDiv(BigInt("-18364758544493064720"), 0x3n, BigInt("-6121586181497688240"));
+testDiv(BigInt("-18364758544493064720"), 0x2n, BigInt("-9182379272246532360"));
+testDiv(BigInt("-18364758544493064720"), 0x1n, BigInt("-18364758544493064720"));
+testDiv(BigInt("-18364758544493064720"), BigInt("-1"), 0xFEDCBA9876543210n);
+testDiv(BigInt("-18364758544493064720"), BigInt("-3"), 0x54F43E32D21C10B0n);
+testDiv(BigInt("-18364758544493064720"), BigInt("-4660"), 0xE0042813BE5DCn);
+testDiv(BigInt("-18364758544493064720"), BigInt("-4275878552"), 0x100000000n);
+testDiv(BigInt("-18364758544493064720"), BigInt("-18364758544493064720"), 0x1n);
+
+// Test division by 0
+try {
+ let a = 102122311n / 0n;
+} catch (e) {
+ assert(e instanceof RangeError);
+ assert(e.message == "0 is an invalid divisor value.");
+}
+
+2018-05-16 Caio Lima <ticaiolima@gmail.com>
+
+ [ESNext][BigInt] Implement support for "/" operation
+ https://bugs.webkit.org/show_bug.cgi?id=183996
+
+ Reviewed by Yusuke Suzuki.
+
+ This patch is introducing the support for BigInt into divide
+ operation int LLInt and JIT layers.
+
+ * dfg/DFGOperations.cpp:
+ * runtime/CommonSlowPaths.cpp:
+ (JSC::SLOW_PATH_DECL):
+ * runtime/JSBigInt.cpp:
+ (JSC::JSBigInt::divide):
+ (JSC::JSBigInt::copy):
+ (JSC::JSBigInt::unaryMinus):
+ (JSC::JSBigInt::absoluteCompare):
+ (JSC::JSBigInt::absoluteDivLarge):
+ (JSC::JSBigInt::productGreaterThan):
+ (JSC::JSBigInt::inplaceAdd):
+ (JSC::JSBigInt::inplaceSub):
+ (JSC::JSBigInt::inplaceRightShift):
+ (JSC::JSBigInt::specialLeftShift):
+ (JSC::JSBigInt::digit):
+ (JSC::JSBigInt::setDigit):
+ * runtime/JSBigInt.h:
+
2018-05-16 Alberto Garcia <berto@igalia.com>
[CMake] Properly detect compiler flags, needed libs, and fallbacks for usage of 64-bit atomic operations
#include "TypedArrayInlines.h"
#include "VMInlines.h"
#include <wtf/InlineASM.h>
+#include <wtf/Variant.h>
#if ENABLE(JIT)
#if ENABLE(DFG_JIT)
JSValue op1 = JSValue::decode(encodedOp1);
JSValue op2 = JSValue::decode(encodedOp2);
- double a = op1.toNumber(exec);
+ auto leftNumeric = op1.toNumeric(exec);
+ RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ auto rightNumeric = op2.toNumeric(exec);
RETURN_IF_EXCEPTION(scope, encodedJSValue());
+
+ if (WTF::holds_alternative<JSBigInt*>(leftNumeric) || WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
+ if (WTF::holds_alternative<JSBigInt*>(leftNumeric) && WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
+ JSBigInt* result = JSBigInt::divide(exec, WTF::get<JSBigInt*>(leftNumeric), WTF::get<JSBigInt*>(rightNumeric));
+ RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ return JSValue::encode(result);
+ }
+
+ return throwVMTypeError(exec, scope, "Invalid operand in BigInt operation.");
+ }
+
scope.release();
- double b = op2.toNumber(exec);
+
+ double a = WTF::get<double>(leftNumeric);
+ double b = WTF::get<double>(rightNumeric);
return JSValue::encode(jsNumber(a / b));
}
int32_t radix = extractToStringRadixArgument(state, state->argument(0), scope);
RETURN_IF_EXCEPTION(scope, encodedJSValue());
- String resultString = value->toString(*state, radix);
+ String resultString = value->toString(state, radix);
RETURN_IF_EXCEPTION(scope, encodedJSValue());
scope.release();
if (resultString.length() == 1)
BEGIN();
JSValue left = OP_C(2).jsValue();
JSValue right = OP_C(3).jsValue();
- double a = left.toNumber(exec);
- if (UNLIKELY(throwScope.exception()))
- RETURN(JSValue());
- double b = right.toNumber(exec);
- if (UNLIKELY(throwScope.exception()))
- RETURN(JSValue());
+ auto leftNumeric = left.toNumeric(exec);
+ CHECK_EXCEPTION();
+ auto rightNumeric = right.toNumeric(exec);
+ CHECK_EXCEPTION();
+
+ if (WTF::holds_alternative<JSBigInt*>(leftNumeric) || WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
+ if (WTF::holds_alternative<JSBigInt*>(leftNumeric) && WTF::holds_alternative<JSBigInt*>(rightNumeric)) {
+ JSValue result(JSBigInt::divide(exec, WTF::get<JSBigInt*>(leftNumeric), WTF::get<JSBigInt*>(rightNumeric)));
+ CHECK_EXCEPTION();
+ RETURN_WITH_PROFILING(result, {
+ updateArithProfileForBinaryArithOp(exec, pc, result, left, right);
+ });
+ }
+
+ THROW(createTypeError(exec, "Invalid mix of BigInt and other type in division."));
+ }
+
+ double a = WTF::get<double>(leftNumeric);
+ double b = WTF::get<double>(rightNumeric);
JSValue result = jsNumber(a / b);
RETURN_WITH_PROFILING(result, {
updateArithProfileForBinaryArithOp(exec, pc, result, left, right);
return parseInt(state, s, ErrorParseMode::IgnoreExceptions);
}
-String JSBigInt::toString(ExecState& state, unsigned radix)
+String JSBigInt::toString(ExecState* state, unsigned radix)
{
if (this->isZero())
- return state.vm().smallStrings.singleCharacterStringRep('0');
+ return state->vm().smallStrings.singleCharacterStringRep('0');
return toStringGeneric(state, this, radix);
}
return result->rightTrim(vm);
}
+JSBigInt* JSBigInt::divide(ExecState* state, JSBigInt* x, JSBigInt* y)
+{
+ // 1. If y is 0n, throw a RangeError exception.
+ VM& vm = state->vm();
+ auto scope = DECLARE_THROW_SCOPE(vm);
+
+ if (y->isZero()) {
+ throwRangeError(state, scope, ASCIILiteral("0 is an invalid divisor value."));
+ return nullptr;
+ }
+
+ // 2. Let quotient be the mathematical value of x divided by y.
+ // 3. Return a BigInt representing quotient rounded towards 0 to the next
+ // integral value.
+ if (absoluteCompare(x, y) == ComparisonResult::LessThan)
+ return createZero(vm);
+
+ JSBigInt* quotient = nullptr;
+ bool resultSign = x->sign() != y->sign();
+ if (y->length() == 1) {
+ Digit divisor = y->digit(0);
+ if (divisor == 1)
+ return resultSign == x->sign() ? x : unaryMinus(vm, x);
+
+ Digit remainder;
+ absoluteDivWithDigitDivisor(vm, x, divisor, "ient, remainder);
+ } else
+ absoluteDivWithBigIntDivisor(vm, x, y, "ient, nullptr);
+
+ quotient->setSign(resultSign);
+ return quotient->rightTrim(vm);
+}
+
+JSBigInt* JSBigInt::copy(VM& vm, JSBigInt* x)
+{
+ ASSERT(!x->isZero());
+
+ JSBigInt* result = JSBigInt::createWithLength(vm, x->length());
+ std::copy(x->dataStorage(), x->dataStorage() + x->length(), result->dataStorage());
+ result->setSign(x->sign());
+ return result;
+}
+
+JSBigInt* JSBigInt::unaryMinus(VM& vm, JSBigInt* x)
+{
+ if (x->isZero())
+ return x;
+
+ JSBigInt* result = copy(vm, x);
+ result->setSign(!x->sign());
+ return result;
+}
+
#if USE(JSVALUE32_64)
#define HAVE_TWO_DIGIT 1
typedef uint64_t TwoDigit;
return true;
}
+inline JSBigInt::ComparisonResult JSBigInt::absoluteCompare(JSBigInt* x, JSBigInt* y)
+{
+ ASSERT(!x->length() || x->digit(0));
+ ASSERT(!y->length() || y->digit(0));
+
+ int diff = x->length() - y->length();
+ if (diff)
+ return diff < 0 ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
+
+ int i = x->length() - 1;
+ while (i >= 0 && x->digit(i) == y->digit(i))
+ i--;
+
+ if (i < 0)
+ return ComparisonResult::Equal;
+
+ return x->digit(i) > y->digit(i) ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
+}
+
// Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
// Mathematically, the contract is:
// quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
// allocated for it; otherwise the caller must ensure that it is big enough.
// {quotient} can be the same as {x} for an in-place division. {quotient} can
// also be nullptr if the caller is only interested in the remainder.
-void JSBigInt::absoluteDivSmall(ExecState& state, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
+void JSBigInt::absoluteDivWithDigitDivisor(VM& vm, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
{
ASSERT(divisor);
- VM& vm = state.vm();
ASSERT(!x->isZero());
remainder = 0;
if (divisor == 1) {
}
}
+// Divides {dividend} by {divisor}, returning the result in {quotient} and
+// {remainder}. Mathematically, the contract is:
+// quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
+// Both {quotient} and {remainder} are optional, for callers that are only
+// interested in one of them.
+// See Knuth, Volume 2, section 4.3.1, Algorithm D.
+void JSBigInt::absoluteDivWithBigIntDivisor(VM& vm, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)
+{
+ ASSERT(divisor->length() >= 2);
+ ASSERT(dividend->length() >= divisor->length());
+
+ // The unusual variable names inside this function are consistent with
+ // Knuth's book, as well as with Go's implementation of this algorithm.
+ // Maintaining this consistency is probably more useful than trying to
+ // come up with more descriptive names for them.
+ unsigned n = divisor->length();
+ unsigned m = dividend->length() - n;
+
+ // The quotient to be computed.
+ JSBigInt* q = nullptr;
+ if (quotient != nullptr)
+ q = createWithLength(vm, m + 1);
+
+ // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
+ // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
+ JSBigInt* qhatv = createWithLength(vm, m + 1);
+
+ // D1.
+ // Left-shift inputs so that the divisor's MSB is set. This is necessary
+ // to prevent the digit-wise divisions (see digit_div call below) from
+ // overflowing (they take a two digits wide input, and return a one digit
+ // result).
+ Digit lastDigit = divisor->digit(n - 1);
+ unsigned shift = sizeof(lastDigit) == 8 ? clz64(lastDigit) : clz32(lastDigit);
+
+ if (shift > 0)
+ divisor = absoluteLeftShiftAlwaysCopy(vm, divisor, shift, LeftShiftMode::SameSizeResult);
+
+ // Holds the (continuously updated) remaining part of the dividend, which
+ // eventually becomes the remainder.
+ JSBigInt* u = absoluteLeftShiftAlwaysCopy(vm, dividend, shift, LeftShiftMode::AlwaysAddOneDigit);
+
+ // D2.
+ // Iterate over the dividend's digit (like the "grad school" algorithm).
+ // {vn1} is the divisor's most significant digit.
+ Digit vn1 = divisor->digit(n - 1);
+ for (int j = m; j >= 0; j--) {
+ // D3.
+ // Estimate the current iteration's quotient digit (see Knuth for details).
+ // {qhat} is the current quotient digit.
+ Digit qhat = std::numeric_limits<Digit>::max();
+
+ // {ujn} is the dividend's most significant remaining digit.
+ Digit ujn = u->digit(j + n);
+ if (ujn != vn1) {
+ // {rhat} is the current iteration's remainder.
+ Digit rhat = 0;
+ // Estimate the current quotient digit by dividing the most significant
+ // digits of dividend and divisor. The result will not be too small,
+ // but could be a bit too large.
+ qhat = digitDiv(ujn, u->digit(j + n - 1), vn1, rhat);
+
+ // Decrement the quotient estimate as needed by looking at the next
+ // digit, i.e. by testing whether
+ // qhat * v_{n-2} > (rhat << digitBits) + u_{j+n-2}.
+ Digit vn2 = divisor->digit(n - 2);
+ Digit ujn2 = u->digit(j + n - 2);
+ while (productGreaterThan(qhat, vn2, rhat, ujn2)) {
+ qhat--;
+ Digit prevRhat = rhat;
+ rhat += vn1;
+ // v[n-1] >= 0, so this tests for overflow.
+ if (rhat < prevRhat)
+ break;
+ }
+ }
+
+ // D4.
+ // Multiply the divisor with the current quotient digit, and subtract
+ // it from the dividend. If there was "borrow", then the quotient digit
+ // was one too high, so we must correct it and undo one subtraction of
+ // the (shifted) divisor.
+ internalMultiplyAdd(divisor, qhat, 0, n, qhatv);
+ Digit c = u->absoluteInplaceSub(qhatv, j);
+ if (c) {
+ c = u->absoluteInplaceAdd(divisor, j);
+ u->setDigit(j + n, u->digit(j + n) + c);
+ qhat--;
+ }
+
+ if (quotient != nullptr)
+ q->setDigit(j, qhat);
+ }
+
+ if (quotient != nullptr) {
+ // Caller will right-trim.
+ *quotient = q;
+ }
+
+ if (remainder != nullptr) {
+ u->inplaceRightShift(shift);
+ *remainder = u;
+ }
+}
+
+// Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
+inline bool JSBigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low)
+{
+ Digit resultHigh;
+ Digit resultLow = digitMul(factor1, factor2, resultHigh);
+ return resultHigh > high || (resultHigh == high && resultLow > low);
+}
+
+// Adds {summand} onto {this}, starting with {summand}'s 0th digit
+// at {this}'s {startIndex}'th digit. Returns the "carry" (0 or 1).
+JSBigInt::Digit JSBigInt::absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex)
+{
+ Digit carry = 0;
+ unsigned n = summand->length();
+ ASSERT(length() >= startIndex + n);
+ for (unsigned i = 0; i < n; i++) {
+ Digit newCarry = 0;
+ Digit sum = digitAdd(digit(startIndex + i), summand->digit(i), newCarry);
+ sum = digitAdd(sum, carry, newCarry);
+ setDigit(startIndex + i, sum);
+ carry = newCarry;
+ }
+
+ return carry;
+}
+
+// Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
+// at {this}'s {startIndex}-th digit. Returns the "borrow" (0 or 1).
+JSBigInt::Digit JSBigInt::absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex)
+{
+ Digit borrow = 0;
+ unsigned n = subtrahend->length();
+ ASSERT(length() >= startIndex + n);
+ for (unsigned i = 0; i < n; i++) {
+ Digit newBorrow = 0;
+ Digit difference = digitSub(digit(startIndex + i), subtrahend->digit(i), newBorrow);
+ difference = digitSub(difference, borrow, newBorrow);
+ setDigit(startIndex + i, difference);
+ borrow = newBorrow;
+ }
+
+ return borrow;
+}
+
+void JSBigInt::inplaceRightShift(unsigned shift)
+{
+ ASSERT(shift < digitBits);
+ ASSERT(!(digit(0) & ((static_cast<Digit>(1) << shift) - 1)));
+
+ if (!shift)
+ return;
+
+ Digit carry = digit(0) >> shift;
+ unsigned last = length() - 1;
+ for (unsigned i = 0; i < last; i++) {
+ Digit d = digit(i + 1);
+ setDigit(i, (d << (digitBits - shift)) | carry);
+ carry = d >> shift;
+ }
+ setDigit(last, carry);
+}
+
+// Always copies the input, even when {shift} == 0.
+JSBigInt* JSBigInt::absoluteLeftShiftAlwaysCopy(VM& vm, JSBigInt* x, unsigned shift, LeftShiftMode mode)
+{
+ ASSERT(shift < digitBits);
+ ASSERT(!x->isZero());
+
+ unsigned n = x->length();
+ unsigned resultLength = mode == LeftShiftMode::AlwaysAddOneDigit ? n + 1 : n;
+ JSBigInt* result = createWithLength(vm, resultLength);
+
+ if (!shift) {
+ for (unsigned i = 0; i < n; i++)
+ result->setDigit(i, x->digit(i));
+ if (mode == LeftShiftMode::AlwaysAddOneDigit)
+ result->setDigit(n, 0);
+
+ return result;
+ }
+
+ Digit carry = 0;
+ for (unsigned i = 0; i < n; i++) {
+ Digit d = x->digit(i);
+ result->setDigit(i, (d << shift) | carry);
+ carry = d >> (digitBits - shift);
+ }
+
+ if (mode == LeftShiftMode::AlwaysAddOneDigit)
+ result->setDigit(n, carry);
+ else {
+ ASSERT(mode == LeftShiftMode::SameSizeResult);
+ ASSERT(!carry);
+ }
+
+ return result;
+}
+
// Lookup table for the maximum number of bits required per character of a
// base-N string representation of a number. To increase accuracy, the array
// value is the actual value multiplied by 32. To generate this table:
return maximumCharactersRequired;
}
-String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
+String JSBigInt::toStringGeneric(ExecState* state, JSBigInt* x, unsigned radix)
{
// FIXME: [JSC] Revisit usage of Vector into JSBigInt::toString
// https://bugs.webkit.org/show_bug.cgi?id=18067
Vector<LChar> resultString;
+ VM& vm = state->vm();
+
ASSERT(radix >= 2 && radix <= 36);
ASSERT(!x->isZero());
uint64_t maximumCharactersRequired = calculateMaximumCharactersRequired(length, radix, x->digit(length - 1), sign);
if (maximumCharactersRequired > JSString::MaxLength) {
- auto scope = DECLARE_THROW_SCOPE(state.vm());
- throwOutOfMemoryError(&state, scope);
+ auto scope = DECLARE_THROW_SCOPE(vm);
+ throwOutOfMemoryError(state, scope);
return String();
}
JSBigInt** dividend = &x;
do {
Digit chunk;
- absoluteDivSmall(state, *dividend, chunkDivisor, &rest, chunk);
+ absoluteDivWithDigitDivisor(vm, *dividend, chunkDivisor, &rest, chunk);
ASSERT(rest);
dividend = &rest;
if (isZero())
return this;
- ASSERT(m_length);
-
- int nonZeroIndex = m_length - 1;
- while (nonZeroIndex >= 0 && !digit(nonZeroIndex))
+ unsigned nonZeroIndex = m_length - 1;
+ while (!digit(nonZeroIndex))
nonZeroIndex--;
- if (nonZeroIndex == static_cast<int>(m_length - 1))
+ if (nonZeroIndex == m_length - 1)
return this;
unsigned newLength = nonZeroIndex + 1;
return reinterpret_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
}
-JSBigInt::Digit JSBigInt::digit(unsigned n)
+inline JSBigInt::Digit JSBigInt::digit(unsigned n)
{
- ASSERT(n >= 0 && n < length());
+ ASSERT(n < length());
return dataStorage()[n];
}
-void JSBigInt::setDigit(unsigned n, Digit value)
+inline void JSBigInt::setDigit(unsigned n, Digit value)
{
- ASSERT(n >= 0 && n < length());
+ ASSERT(n < length());
dataStorage()[n] = value;
}
JSObject* JSBigInt::toObject(ExecState* exec, JSGlobalObject* globalObject) const
static JSBigInt* stringToBigInt(ExecState*, StringView);
std::optional<uint8_t> singleDigitValueForString();
- String toString(ExecState&, unsigned radix);
+ String toString(ExecState*, unsigned radix);
JS_EXPORT_PRIVATE static bool equals(JSBigInt*, JSBigInt*);
bool equalsToNumber(JSValue);
static JSBigInt* multiply(ExecState*, JSBigInt* x, JSBigInt* y);
+ static JSBigInt* divide(ExecState*, JSBigInt* x, JSBigInt* y);
+ static JSBigInt* unaryMinus(VM&, JSBigInt* x);
+
private:
- enum ComparisonResult {
+ enum class ComparisonResult {
Equal,
Undefined,
GreaterThan,
static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);
- static void absoluteDivSmall(ExecState&, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder);
+ static ComparisonResult absoluteCompare(JSBigInt* x, JSBigInt* y);
+ static void absoluteDivWithDigitDivisor(VM&, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder);
static void internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned, JSBigInt* result);
static void multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex);
+ static void absoluteDivWithBigIntDivisor(VM&, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder);
+
+ enum class LeftShiftMode {
+ SameSizeResult,
+ AlwaysAddOneDigit
+ };
+
+ static JSBigInt* absoluteLeftShiftAlwaysCopy(VM&, JSBigInt* x, unsigned shift, LeftShiftMode);
+ static bool productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low);
+
+ Digit absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex);
+ Digit absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex);
+ void inplaceRightShift(unsigned shift);
// Digit arithmetic helpers.
static Digit digitAdd(Digit a, Digit b, Digit& carry);
static Digit digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder);
static Digit digitPow(Digit base, Digit exponent);
- static String toStringGeneric(ExecState&, JSBigInt*, unsigned radix);
+ static String toStringGeneric(ExecState*, JSBigInt*, unsigned radix);
bool isZero();
static JSBigInt* allocateFor(ExecState*, VM&, unsigned radix, unsigned charcount);
+ static JSBigInt* copy(VM&, JSBigInt* x);
JSBigInt* rightTrim(VM&);
void inplaceMultiplyAdd(Digit multiplier, Digit part);
JSBigInt* bigInt = asBigInt(*this);
if (auto digit = bigInt->singleDigitValueForString())
return vm.smallStrings.singleCharacterString(*digit + '0');
- JSString* returnString = jsNontrivialString(&vm, bigInt->toString(*exec, 10));
+ JSString* returnString = jsNontrivialString(&vm, bigInt->toString(exec, 10));
RETURN_IF_EXCEPTION(scope, errorValue());
return returnString;
}
git://git.webkit.org / WebKit-https.git / commitdiff