[ESNext][BigInt] Implement support for "/" operation
authorticaiolima@gmail.com <ticaiolima@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 17 May 2018 04:27:28 +0000 (04:27 +0000)
committerticaiolima@gmail.com <ticaiolima@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 17 May 2018 04:27:28 +0000 (04:27 +0000)
https://bugs.webkit.org/show_bug.cgi?id=183996

Reviewed by Yusuke Suzuki.

JSTests:

* 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.

Source/JavaScriptCore:

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:

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

15 files changed:
JSTests/ChangeLog
JSTests/bigIntTests.yaml
JSTests/stress/big-int-div-jit.js [new file with mode: 0644]
JSTests/stress/big-int-div-memory-stress.js [new file with mode: 0644]
JSTests/stress/big-int-div-to-primitive.js [new file with mode: 0644]
JSTests/stress/big-int-div-type-error.js [new file with mode: 0644]
JSTests/stress/big-int-div-wrapped-value.js [new file with mode: 0644]
JSTests/stress/big-int-division.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/runtime/BigIntPrototype.cpp
Source/JavaScriptCore/runtime/CommonSlowPaths.cpp
Source/JavaScriptCore/runtime/JSBigInt.cpp
Source/JavaScriptCore/runtime/JSBigInt.h
Source/JavaScriptCore/runtime/JSCJSValue.cpp

index 0f487e8..adb0425 100644 (file)
@@ -1,3 +1,19 @@
+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-16  Saam Barati  <sbarati@apple.com>
 
         Constant fold CheckTypeInfoFlags on ImplementsDefaultHasInstance
index e947dc2..4ff994f 100644 (file)
 - 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
diff --git a/JSTests/stress/big-int-div-jit.js b/JSTests/stress/big-int-div-jit.js
new file mode 100644 (file)
index 0000000..0e217e8
--- /dev/null
@@ -0,0 +1,19 @@
+//@ 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);
+}
+
diff --git a/JSTests/stress/big-int-div-memory-stress.js b/JSTests/stress/big-int-div-memory-stress.js
new file mode 100644 (file)
index 0000000..0cf0b9b
--- /dev/null
@@ -0,0 +1,15 @@
+//@ 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);
+
diff --git a/JSTests/stress/big-int-div-to-primitive.js b/JSTests/stress/big-int-div-to-primitive.js
new file mode 100644 (file)
index 0000000..a297344
--- /dev/null
@@ -0,0 +1,34 @@
+//@ 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);
+
diff --git a/JSTests/stress/big-int-div-type-error.js b/JSTests/stress/big-int-div-type-error.js
new file mode 100644 (file)
index 0000000..27982cd
--- /dev/null
@@ -0,0 +1,106 @@
+//@ 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");
+
diff --git a/JSTests/stress/big-int-div-wrapped-value.js b/JSTests/stress/big-int-div-wrapped-value.js
new file mode 100644 (file)
index 0000000..9bb9aee
--- /dev/null
@@ -0,0 +1,46 @@
+//@ 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");
+
diff --git a/JSTests/stress/big-int-division.js b/JSTests/stress/big-int-division.js
new file mode 100644 (file)
index 0000000..401890a
--- /dev/null
@@ -0,0 +1,131 @@
+//@ 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.");
+}
+
index b2718d0..55a12ad 100644 (file)
@@ -1,3 +1,31 @@
+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  Saam Barati  <sbarati@apple.com>
 
         Constant fold CheckTypeInfoFlags on ImplementsDefaultHasInstance
index 5b0947e..b5815fd 100644 (file)
@@ -75,6 +75,7 @@
 #include "TypedArrayInlines.h"
 #include "VMInlines.h"
 #include <wtf/InlineASM.h>
+#include <wtf/Variant.h>
 
 #if ENABLE(JIT)
 #if ENABLE(DFG_JIT)
@@ -424,10 +425,25 @@ EncodedJSValue JIT_OPERATION operationValueDiv(ExecState* exec, EncodedJSValue e
     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));
 }
 
index 4498158..32d9d14 100644 (file)
@@ -103,7 +103,7 @@ EncodedJSValue JSC_HOST_CALL bigIntProtoFuncToString(ExecState* state)
     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)
index a8a5681..84dd3d2 100644 (file)
@@ -516,12 +516,25 @@ SLOW_PATH_DECL(slow_path_div)
     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);
index fd8e9af..460775d 100644 (file)
@@ -227,10 +227,10 @@ JSBigInt* JSBigInt::stringToBigInt(ExecState* state, StringView s)
     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);
 }
@@ -270,6 +270,59 @@ JSBigInt* JSBigInt::multiply(ExecState* state, JSBigInt* x, JSBigInt* y)
     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, &quotient, remainder);
+    } else
+        absoluteDivWithBigIntDivisor(vm, x, y, &quotient, 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;
@@ -522,6 +575,25 @@ bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
     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.
@@ -529,11 +601,10 @@ bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
 // 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) {
@@ -557,6 +628,209 @@ void JSBigInt::absoluteDivSmall(ExecState& state, JSBigInt* x, Digit divisor, JS
     }
 }
 
+// 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, n + 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:
@@ -604,12 +878,14 @@ uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned
     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());
 
@@ -620,8 +896,8 @@ String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
     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();
     }
 
@@ -646,7 +922,7 @@ String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
         JSBigInt** dividend = &x;
         do {
             Digit chunk;
-            absoluteDivSmall(state, *dividend, chunkDivisor, &rest, chunk);
+            absoluteDivWithDigitDivisor(vm, *dividend, chunkDivisor, &rest, chunk);
             ASSERT(rest);
 
             dividend = &rest;
@@ -694,13 +970,11 @@ JSBigInt* JSBigInt::rightTrim(VM& vm)
     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;
@@ -874,15 +1148,15 @@ inline JSBigInt::Digit* JSBigInt::dataStorage()
     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
index 0244cbb..67650fc 100644 (file)
@@ -82,7 +82,7 @@ public:
     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);
@@ -94,9 +94,12 @@ public:
 
     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,
@@ -118,9 +121,23 @@ private:
     
     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);
@@ -129,7 +146,7 @@ private:
     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();
 
@@ -143,6 +160,7 @@ private:
 
     static JSBigInt* allocateFor(ExecState*, VM&, unsigned radix, unsigned charcount);
 
+    static JSBigInt* copy(VM&, JSBigInt* x);
     JSBigInt* rightTrim(VM&);
 
     void inplaceMultiplyAdd(Digit multiplier, Digit part);
index b5f77be..9edc601 100644 (file)
@@ -382,7 +382,7 @@ JSString* JSValue::toStringSlowCase(ExecState* exec, bool returnEmptyStringOnErr
         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;
     }