Version 1.11.0-dev.5.5
Cherry-pick f6f338ce67eb8801b350417baacf6d3681b26002 into dev
Cherry-pick 90315a1694a40ba738a5197295b0c1a7b9d03c5f into dev
Cherry-pick 9edc6e5a6d31ec926be7743c06f500f125a04b54 into dev
Cherry-pick 16bb52b88ded9da50508d72bf86825b243ad8258 into dev
Cherry-pick 1009d587de88ec04a66cd60409aba3a281e21f64 into dev
Cherry-pick 3ce2b95070a26d7aa5173673095d49e0494c4151 into dev
diff --git a/runtime/lib/bigint.dart b/runtime/lib/bigint.dart
index f4ff408..04b85b7 100644
--- a/runtime/lib/bigint.dart
+++ b/runtime/lib/bigint.dart
@@ -1265,15 +1265,9 @@
return other._toBigintOrDouble()._mulFromInteger(this);
}
num operator ~/(num other) {
- if ((other is int) && (other == 0)) {
- throw const IntegerDivisionByZeroException();
- }
return other._toBigintOrDouble()._truncDivFromInteger(this);
}
num operator %(num other) {
- if ((other is int) && (other == 0)) {
- throw const IntegerDivisionByZeroException();
- }
return other._toBigintOrDouble()._moduloFromInteger(this);
}
int operator &(int other) {
@@ -1368,9 +1362,15 @@
return other._toBigint()._mul(this)._toValidInt();
}
int _truncDivFromInteger(int other) {
+ if (_used == 0) {
+ throw const IntegerDivisionByZeroException();
+ }
return other._toBigint()._div(this)._toValidInt();
}
int _moduloFromInteger(int other) {
+ if (_used == 0) {
+ throw const IntegerDivisionByZeroException();
+ }
_Bigint result = other._toBigint()._rem(this);
if (result._neg) {
if (_neg) {
@@ -1382,6 +1382,9 @@
return result._toValidInt();
}
int _remainderFromInteger(int other) {
+ if (_used == 0) {
+ throw const IntegerDivisionByZeroException();
+ }
return other._toBigint()._rem(this)._toValidInt();
}
bool _greaterThanFromInteger(int other) {
@@ -1534,6 +1537,218 @@
assert(!is1);
return z._revert(r_digits, r_used)._toValidInt();
}
+
+ // Returns 1/this % m, with m > 0.
+ int modInverse(int m) {
+ if (m is! int) throw new ArgumentError(m);
+ if (m <= 0) throw new RangeError(m);
+ if (m == 1) return 0;
+ m = m._toBigint();
+ var t = this;
+ if (t._neg || (t._absCompare(m) >= 0)) {
+ t %= m;
+ t = t._toBigint();
+ }
+ final bool ac = m.isEven;
+ final t_used = t._used;
+ if ((t_used == 1) && (t._digits[0] == 1)) return 1;
+ if ((t_used == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
+ final m_digits = m._digits;
+ final m_used = m._used;
+ final tuv_len = m_used + (m_used & 1);
+ final t_digits = _cloneDigits(t._digits, 0, t_used, tuv_len);
+ var u_digits = _cloneDigits(m_digits, 0, m_used, tuv_len);
+ var v_digits = _cloneDigits(t_digits, 0, t_used, tuv_len);
+
+ // Variables a, b, c, and d require one more digit.
+ final abcd_used = m_used + 1;
+ final abcd_len = abcd_used + (abcd_used & 1) + 2; // +2 to satisfy _absAdd.
+ var a_digits, b_digits, c_digits, d_digits;
+ bool a_neg, b_neg, c_neg, d_neg;
+ if (ac) {
+ a_digits = new Uint32List(abcd_len);
+ a_neg = false;
+ a_digits[0] = 1;
+ c_digits = new Uint32List(abcd_len);
+ c_neg = false;
+ }
+ b_digits = new Uint32List(abcd_len);
+ b_neg = false;
+ d_digits = new Uint32List(abcd_len);
+ d_neg = false;
+ d_digits[0] = 1;
+
+ while (true) {
+ while ((u_digits[0] & 1) == 0) {
+ _rsh(u_digits, m_used, 1, u_digits);
+ if (ac) {
+ if (((a_digits[0] & 1) == 1) || ((b_digits[0] & 1) == 1)) {
+ if (a_neg) {
+ if ((a_digits[m_used] != 0) ||
+ (_compareDigits(a_digits, m_used, t_digits, m_used)) > 0) {
+ _absSub(a_digits, abcd_used, t_digits, m_used, a_digits);
+ } else {
+ _absSub(t_digits, m_used, a_digits, m_used, a_digits);
+ a_neg = false;
+ }
+ } else {
+ _absAdd(a_digits, abcd_used, t_digits, m_used, a_digits);
+ }
+ if (b_neg) {
+ _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else if ((b_digits[m_used] != 0) ||
+ (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else {
+ _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ b_neg = true;
+ }
+ }
+ _rsh(a_digits, abcd_used, 1, a_digits);
+ } else if ((b_digits[0] & 1) == 1) {
+ if (b_neg) {
+ _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else if ((b_digits[m_used] != 0) ||
+ (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+ } else {
+ _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+ b_neg = true;
+ }
+ }
+ _rsh(b_digits, abcd_used, 1, b_digits);
+ }
+ while ((v_digits[0] & 1) == 0) {
+ _rsh(v_digits, m_used, 1, v_digits);
+ if (ac) {
+ if (((c_digits[0] & 1) == 1) || ((d_digits[0] & 1) == 1)) {
+ if (c_neg) {
+ if ((c_digits[m_used] != 0) ||
+ (_compareDigits(c_digits, m_used, t_digits, m_used) > 0)) {
+ _absSub(c_digits, abcd_used, t_digits, m_used, c_digits);
+ } else {
+ _absSub(t_digits, m_used, c_digits, m_used, c_digits);
+ c_neg = false;
+ }
+ } else {
+ _absAdd(c_digits, abcd_used, t_digits, m_used, c_digits);
+ }
+ if (d_neg) {
+ _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = true;
+ }
+ }
+ _rsh(c_digits, abcd_used, 1, c_digits);
+ } else if ((d_digits[0] & 1) == 1) {
+ if (d_neg) {
+ _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = true;
+ }
+ }
+ _rsh(d_digits, abcd_used, 1, d_digits);
+ }
+ if (_compareDigits(u_digits, m_used, v_digits, m_used) >= 0) {
+ _absSub(u_digits, m_used, v_digits, m_used, u_digits);
+ if (ac) {
+ if (a_neg == c_neg) {
+ var a_cmp_c =
+ _compareDigits(a_digits, abcd_used, c_digits, abcd_used);
+ if (a_cmp_c > 0) {
+ _absSub(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+ } else {
+ _absSub(c_digits, abcd_used, a_digits, abcd_used, a_digits);
+ a_neg = !a_neg && (a_cmp_c != 0);
+ }
+ } else {
+ _absAdd(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+ }
+ }
+ if (b_neg == d_neg) {
+ var b_cmp_d =
+ _compareDigits(b_digits, abcd_used, d_digits, abcd_used);
+ if (b_cmp_d > 0) {
+ _absSub(b_digits, abcd_used, d_digits, abcd_used, b_digits);
+ } else {
+ _absSub(d_digits, abcd_used, b_digits, abcd_used, b_digits);
+ b_neg = !b_neg && (b_cmp_d != 0);
+ }
+ } else {
+ _absAdd(b_digits, abcd_used, d_digits, abcd_used, b_digits);
+ }
+ } else {
+ _absSub(v_digits, m_used, u_digits, m_used, v_digits);
+ if (ac) {
+ if (c_neg == a_neg) {
+ var c_cmp_a =
+ _compareDigits(c_digits, abcd_used, a_digits, abcd_used);
+ if (c_cmp_a > 0) {
+ _absSub(c_digits, abcd_used, a_digits, abcd_used, c_digits);
+ } else {
+ _absSub(a_digits, abcd_used, c_digits, abcd_used, c_digits);
+ c_neg = !c_neg && (c_cmp_a != 0);
+ }
+ } else {
+ _absAdd(c_digits, abcd_used, a_digits, abcd_used, c_digits);
+ }
+ }
+ if (d_neg == b_neg) {
+ var d_cmp_b =
+ _compareDigits(d_digits, abcd_used, b_digits, abcd_used);
+ if (d_cmp_b > 0) {
+ _absSub(d_digits, abcd_used, b_digits, abcd_used, d_digits);
+ } else {
+ _absSub(b_digits, abcd_used, d_digits, abcd_used, d_digits);
+ d_neg = !d_neg && (d_cmp_ab != 0);
+ }
+ } else {
+ _absAdd(d_digits, abcd_used, b_digits, abcd_used, d_digits);
+ }
+ }
+ // Exit loop if u == 0.
+ var i = m_used;
+ while ((i > 0) && (u_digits[i - 1] == 0)) --i;
+ if (i == 0) break;
+ }
+ // No inverse if v != 1.
+ var i = m_used - 1;
+ while ((i > 0) && (v_digits[i] == 0)) --i;
+ if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime");
+
+ if (d_neg) {
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = false;
+ }
+ } else {
+ _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+ d_neg = false;
+ }
+ } else if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ if ((d_digits[m_used] != 0) ||
+ (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+ _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+ }
+ }
+ return new _Bigint(false, m_used, d_digits)._toValidInt();
+ }
}
// Interface for modular reduction.
diff --git a/runtime/lib/integers.dart b/runtime/lib/integers.dart
index 857a415..1267d15 100644
--- a/runtime/lib/integers.dart
+++ b/runtime/lib/integers.dart
@@ -275,7 +275,6 @@
if (e is _Bigint || m is _Bigint) {
return _toBigint().modPow(e, m);
}
- if (e < 1) return 1;
int b = this;
if (b < 0 || b > m) {
b %= m;
@@ -290,6 +289,73 @@
}
return r;
}
+
+ // Returns 1/this % m, with m > 0.
+ int modInverse(int m) {
+ if (m is! int) throw new ArgumentError(m);
+ if (m <= 0) throw new RangeError(m);
+ if (m == 1) return 0;
+ if (m is _Bigint) {
+ return _toBigint().modInverse(m);
+ }
+ int t = this;
+ if ((t < 0) || (t >= m)) t %= m;
+ if (t == 1) return 1;
+ final bool ac = m.isEven;
+ if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
+ int u = m;
+ int v = t;
+ int a = 1,
+ b = 0,
+ c = 0,
+ d = 1;
+ do {
+ while (u.isEven) {
+ u >>= 1;
+ if (ac) {
+ if (!a.isEven || !b.isEven) {
+ a += t;
+ b -= m;
+ }
+ a >>= 1;
+ } else if (!b.isEven) {
+ b -= m;
+ }
+ b >>= 1;
+ }
+ while (v.isEven) {
+ v >>= 1;
+ if (ac) {
+ if (!c.isEven || !d.isEven) {
+ c += t;
+ d -= m;
+ }
+ c >>= 1;
+ } else if (!d.isEven) {
+ d -= m;
+ }
+ d >>= 1;
+ }
+ if (u >= v) {
+ u -= v;
+ if (ac) a -= c;
+ b -= d;
+ } else {
+ v -= u;
+ if (ac) c -= a;
+ d -= b;
+ }
+ } while (u != 0);
+ if (v != 1) throw new RangeError("Not coprime");
+ if (d < 0) {
+ d += m;
+ if (d < 0) d += m;
+ } else if (d > m) {
+ d -= m;
+ if (d > m) d -= m;
+ }
+ return d;
+ }
}
class _Smi extends _IntegerImplementation implements int {
diff --git a/runtime/vm/heap.h b/runtime/vm/heap.h
index 928e7c5..6d8752c 100644
--- a/runtime/vm/heap.h
+++ b/runtime/vm/heap.h
@@ -105,10 +105,13 @@
bool CodeContains(uword addr) const;
bool StubCodeContains(uword addr) const;
- // Visit all pointers.
+ // Visit all pointers. Caller must ensure concurrent sweeper is not running,
+ // and the visitor must not allocate (see issue 21620).
void VisitObjectPointers(ObjectPointerVisitor* visitor) const;
- // Visit all objects.
+ // Visit all objects, including FreeListElement "objects". Caller must ensure
+ // concurrent sweeper is not running, and the visitor must not allocate (see
+ // issue 21620).
void VisitObjects(ObjectVisitor* visitor) const;
// Find an object by visiting all pointers in the specified heap space,
diff --git a/runtime/vm/object_graph.cc b/runtime/vm/object_graph.cc
index 773839d..b07fe0a 100644
--- a/runtime/vm/object_graph.cc
+++ b/runtime/vm/object_graph.cc
@@ -172,6 +172,11 @@
void ObjectGraph::IterateObjects(ObjectGraph::Visitor* visitor) {
NoSafepointScope no_safepoint_scope_;
+ PageSpace* old_space = isolate()->heap()->old_space();
+ MonitorLocker ml(old_space->tasks_lock());
+ while (old_space->tasks() > 0) {
+ ml.Wait();
+ }
Stack stack(isolate());
isolate()->VisitObjectPointers(&stack, false, false);
stack.TraverseGraph(visitor);
@@ -182,6 +187,11 @@
void ObjectGraph::IterateObjectsFrom(const Object& root,
ObjectGraph::Visitor* visitor) {
NoSafepointScope no_safepoint_scope_;
+ PageSpace* old_space = isolate()->heap()->old_space();
+ MonitorLocker ml(old_space->tasks_lock());
+ while (old_space->tasks() > 0) {
+ ml.Wait();
+ }
Stack stack(isolate());
RawObject* root_raw = root.raw();
stack.VisitPointer(&root_raw);
diff --git a/runtime/vm/object_graph_test.cc b/runtime/vm/object_graph_test.cc
index 66771db..00f7768 100644
--- a/runtime/vm/object_graph_test.cc
+++ b/runtime/vm/object_graph_test.cc
@@ -112,6 +112,8 @@
{
HANDLESCOPE(isolate);
Array& path = Array::Handle(Array::New(6, Heap::kNew));
+ // Trigger a full GC to increase probability of concurrent tasks.
+ isolate->heap()->CollectAllGarbage();
intptr_t length = graph.RetainingPath(&c, path);
EXPECT_LE(3, length);
Array& expected_c = Array::Handle();
diff --git a/runtime/vm/pages.cc b/runtime/vm/pages.cc
index 810554a..18eec36 100644
--- a/runtime/vm/pages.cc
+++ b/runtime/vm/pages.cc
@@ -83,6 +83,7 @@
void HeapPage::VisitObjects(ObjectVisitor* visitor) const {
+ NoSafepointScope no_safepoint;
uword obj_addr = object_start();
uword end_addr = object_end();
while (obj_addr < end_addr) {
@@ -95,6 +96,7 @@
void HeapPage::VisitObjectPointers(ObjectPointerVisitor* visitor) const {
+ NoSafepointScope no_safepoint;
uword obj_addr = object_start();
uword end_addr = object_end();
while (obj_addr < end_addr) {
diff --git a/sdk/lib/_internal/compiler/js_lib/js_number.dart b/sdk/lib/_internal/compiler/js_lib/js_number.dart
index 8ea8a03..8822911 100644
--- a/sdk/lib/_internal/compiler/js_lib/js_number.dart
+++ b/sdk/lib/_internal/compiler/js_lib/js_number.dart
@@ -411,6 +411,70 @@
return r;
}
+ // Returns 1/this % m, with m > 0.
+ int modInverse(int m) {
+ if (m is! int) throw new ArgumentError(m);
+ if (m <= 0) throw new RangeError(m);
+ if (m == 1) return 0;
+ int t = this;
+ if ((t < 0) || (t >= m)) t %= m;
+ if (t == 1) return 1;
+ final bool ac = m.isEven;
+ if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
+ int u = m;
+ int v = t;
+ int a = 1,
+ b = 0,
+ c = 0,
+ d = 1;
+ do {
+ while (u.isEven) {
+ u ~/= 2;
+ if (ac) {
+ if (!a.isEven || !b.isEven) {
+ a += t;
+ b -= m;
+ }
+ a ~/= 2;
+ } else if (!b.isEven) {
+ b -= m;
+ }
+ b ~/= 2;
+ }
+ while (v.isEven) {
+ v ~/= 2;
+ if (ac) {
+ if (!c.isEven || !d.isEven) {
+ c += t;
+ d -= m;
+ }
+ c ~/= 2;
+ } else if (!d.isEven) {
+ d -= m;
+ }
+ d ~/= 2;
+ }
+ if (u >= v) {
+ u -= v;
+ if (ac) a -= c;
+ b -= d;
+ } else {
+ v -= u;
+ if (ac) c -= a;
+ d -= b;
+ }
+ } while (u != 0);
+ if (v != 1) throw new RangeError("Not coprime");
+ if (d < 0) {
+ d += m;
+ if (d < 0) d += m;
+ } else if (d > m) {
+ d -= m;
+ if (d > m) d -= m;
+ }
+ return d;
+ }
+
// Assumes i is <= 32-bit and unsigned.
static int _bitCount(int i) {
// See "Hacker's Delight", section 5-1, "Counting 1-Bits".
diff --git a/sdk/lib/core/int.dart b/sdk/lib/core/int.dart
index 1d29a72..5aee609 100644
--- a/sdk/lib/core/int.dart
+++ b/sdk/lib/core/int.dart
@@ -111,6 +111,15 @@
*/
int modPow(int exponent, int modulus);
+ /**
+ * Returns the modular multiplicative inverse of this integer
+ * modulo [modulus].
+ *
+ * The [modulus] must be positive.
+ * Throws a RangeError if no modular inverse exists.
+ */
+ int modInverse(int modulus);
+
/** Returns true if and only if this integer is even. */
bool get isEven;
diff --git a/tests/corelib/big_integer_arith_vm_test.dart b/tests/corelib/big_integer_arith_vm_test.dart
index 4c04c03..3353756 100644
--- a/tests/corelib/big_integer_arith_vm_test.dart
+++ b/tests/corelib/big_integer_arith_vm_test.dart
@@ -223,6 +223,76 @@
Expect.equals(40128068573873018143207285483, x.modPow(e, m));
}
+testBigintModInverse() {
+ var x, m;
+ x = 1;
+ m = 1;
+ Expect.equals(0, x.modInverse(m));
+ x = 0;
+ m = 1000000001;
+ Expect.throws(() => x.modInverse(m), (e) => e is RangeError); // Not coprime.
+ x = 1234567890;
+ m = 19;
+ Expect.equals(11, x.modInverse(m));
+ x = 1234567890;
+ m = 1000000001;
+ Expect.equals(189108911, x.modInverse(m));
+ x = 19;
+ m = 1000000001;
+ Expect.throws(() => x.modInverse(m), (e) => e is RangeError); // Not coprime.
+ x = 19;
+ m = 1234567890;
+ Expect.equals(519818059, x.modInverse(m));
+ x = 1000000001;
+ m = 1234567890;
+ Expect.equals(1001100101, x.modInverse(m));
+ x = 1000000001;
+ m = 19;
+ Expect.throws(() => x.modInverse(m), (e) => e is RangeError); // Not coprime.
+ x = 12345678901234567890;
+ m = 19;
+ Expect.equals(3, x.modInverse(m));
+ x = 12345678901234567890;
+ m = 10000000000000000001;
+ Expect.equals(9736746307686209582, x.modInverse(m));
+ x = 19;
+ m = 10000000000000000001;
+ Expect.equals(6315789473684210527, x.modInverse(m));
+ x = 19;
+ m = 12345678901234567890;
+ Expect.equals(10396361179987004539, x.modInverse(m));
+ x = 10000000000000000001;
+ m = 12345678901234567890;
+ Expect.equals(325004555487045911, x.modInverse(m));
+ x = 10000000000000000001;
+ m = 19;
+ Expect.equals(7, x.modInverse(m));
+ x = 12345678901234567890;
+ m = 10000000000000000001;
+ Expect.equals(9736746307686209582, x.modInverse(m));
+ x = 12345678901234567890;
+ m = 19;
+ Expect.equals(3, x.modInverse(m));
+ x = 123456789012345678901234567890;
+ m = 123456789012345678901234567899;
+ Expect.throws(() => x.modInverse(m), (e) => e is RangeError); // Not coprime.
+ x = 123456789012345678901234567890;
+ m = 123456789012345678901234567891;
+ Expect.equals(123456789012345678901234567890, x.modInverse(m));
+ x = 123456789012345678901234567899;
+ m = 123456789012345678901234567891;
+ Expect.equals(77160493132716049313271604932, x.modInverse(m));
+ x = 123456789012345678901234567899;
+ m = 123456789012345678901234567890;
+ Expect.throws(() => x.modInverse(m), (e) => e is RangeError); // Not coprime.
+ x = 123456789012345678901234567891;
+ m = 123456789012345678901234567890;
+ Expect.equals(1, x.modInverse(m));
+ x = 123456789012345678901234567891;
+ m = 123456789012345678901234567899;
+ Expect.equals(46296295879629629587962962962, x.modInverse(m));
+}
+
testBigintNegate() {
var a = 0xF000000000000000F;
var b = ~a; // negate.
@@ -254,6 +324,7 @@
testBigintDiv();
testBigintModulo();
testBigintModPow();
+ testBigintModInverse();
testBigintNegate();
testShiftAmount();
Expect.equals(12345678901234567890, (12345678901234567890).abs());
diff --git a/tools/VERSION b/tools/VERSION
index b996cf7..1782662 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -28,4 +28,4 @@
MINOR 11
PATCH 0
PRERELEASE 5
-PRERELEASE_PATCH 4
+PRERELEASE_PATCH 5
