Attachment 340413 Details for Bug 183996 – Patch

[patch] Patch

big-int-div.diff (text/plain), 34.34 KB, created by Caio Lima on 2018-05-15 08:51:30 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Caio Lima

Created: 2018-05-15 08:51:30 PDT

Size: 34.34 KB

patch

obsolete

>diff --git a/JSTests/ChangeLog b/JSTests/ChangeLog
>index fbf7d3f..e3c2073 100644
>--- a/JSTests/ChangeLog
>+++ b/JSTests/ChangeLog
>@@ -1,5 +1,21 @@
> 2018-05-13  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-13  Caio Lima  <ticaiolima@gmail.com>
>+
>         [BigInt] stress/big-int-spec-to-primitive.js test is failing
>         https://bugs.webkit.org/show_bug.cgi?id=185582
> 
>diff --git a/JSTests/bigIntTests.yaml b/JSTests/bigIntTests.yaml
>index e947dc2..4ff994f 100644
>--- a/JSTests/bigIntTests.yaml
>+++ b/JSTests/bigIntTests.yaml
>@@ -118,3 +118,20 @@
> - 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
>index 0000000..0e217e8
>--- /dev/null
>+++ b/JSTests/stress/big-int-div-jit.js
>@@ -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
>index 0000000..0cf0b9b
>--- /dev/null
>+++ b/JSTests/stress/big-int-div-memory-stress.js
>@@ -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
>index 0000000..a297344
>--- /dev/null
>+++ b/JSTests/stress/big-int-div-to-primitive.js
>@@ -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
>index 0000000..27982cd
>--- /dev/null
>+++ b/JSTests/stress/big-int-div-type-error.js
>@@ -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
>index 0000000..9bb9aee
>--- /dev/null
>+++ b/JSTests/stress/big-int-div-wrapped-value.js
>@@ -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
>index 0000000..401890a
>--- /dev/null
>+++ b/JSTests/stress/big-int-division.js
>@@ -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.");
>+}
>+
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 5f404d9..8c7c4af 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,31 @@
>+2018-05-15  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-14  Dominik Infuehr  <dinfuehr@igalia.com>
> 
>         [MIPS] Use btpz to compare against 0 instead of bpeq
>diff --git a/Source/JavaScriptCore/dfg/DFGOperations.cpp b/Source/JavaScriptCore/dfg/DFGOperations.cpp
>index 9c2f44b..032c552 100644
>--- a/Source/JavaScriptCore/dfg/DFGOperations.cpp
>+++ b/Source/JavaScriptCore/dfg/DFGOperations.cpp
>@@ -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));
> }
> 
>diff --git a/Source/JavaScriptCore/runtime/CommonSlowPaths.cpp b/Source/JavaScriptCore/runtime/CommonSlowPaths.cpp
>index a8a5681..781d7fc 100644
>--- a/Source/JavaScriptCore/runtime/CommonSlowPaths.cpp
>+++ b/Source/JavaScriptCore/runtime/CommonSlowPaths.cpp
>@@ -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);
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.cpp b/Source/JavaScriptCore/runtime/JSBigInt.cpp
>index fd8e9af..0c0a0d1 100644
>--- a/Source/JavaScriptCore/runtime/JSBigInt.cpp
>+++ b/Source/JavaScriptCore/runtime/JSBigInt.cpp
>@@ -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, 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:
>@@ -646,7 +920,7 @@ String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
>         JSBigInt** dividend = &x;
>         do {
>             Digit chunk;
>-            absoluteDivSmall(state, *dividend, chunkDivisor, &rest, chunk);
>+            absoluteDivWithDigitDivisor(state.vm(), *dividend, chunkDivisor, &rest, chunk);
>             ASSERT(rest);
> 
>             dividend = &rest;
>@@ -694,13 +968,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 +1146,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
>diff --git a/Source/JavaScriptCore/runtime/JSBigInt.h b/Source/JavaScriptCore/runtime/JSBigInt.h
>index 0244cbb..9b9d27a 100644
>--- a/Source/JavaScriptCore/runtime/JSBigInt.h
>+++ b/Source/JavaScriptCore/runtime/JSBigInt.h
>@@ -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);
>@@ -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);

Actions: View | Formatted Diff | Diff

Attachments on bug 183996: 336498 | 337576 | 338187 | 338995 | 339410 | 339510 | 339608 | 340161 | 340267 | 340413 | 340463 | 340471 | 340550