Version 1.11.1
Cherry-pick 3a0edfba72e27781e98f5debfafc5f01450bd423 to stable
Cherry-pick 6a69915cf53136cf637f1e0f23f89b0372f1210a to stable
Update version of pub to d6855962e0221f0ca3b2756877803916bafd296c in stable
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 9c36150..9e2340d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,10 @@
+## 1.11.1
+
+### Tool changes
+
+* Pub will always load Dart SDK assets from the SDK whose `pub` executable was
+ run, even if a `DART_SDK` environment variable is set.
+
## 1.11.0
### Core library changes
diff --git a/DEPS b/DEPS
index 0a901f2..d66cdbd 100644
--- a/DEPS
+++ b/DEPS
@@ -82,7 +82,7 @@
"ply_rev": "@604b32590ffad5cbb82e4afef1d305512d06ae93",
"plugin_tag": "@0.1.0",
"pool_rev": "@22e12aeb16ad0b626900dbe79e4a25391ddfb28c",
- "pub_rev": "@68308887177ef3b78fdd52f068e4eaefe1b17e07",
+ "pub_rev": "@d6855962e0221f0ca3b2756877803916bafd296c",
"pub_semver_tag": "@1.2.1",
"scheduled_test_tag": "@0.11.8+1",
"shelf_rev": "@1e87b79b21ac5e6fa2f93576d6c06eaa65285ef4",
diff --git a/runtime/lib/bigint.dart b/runtime/lib/bigint.dart
index adfb0db..ce151cf 100644
--- a/runtime/lib/bigint.dart
+++ b/runtime/lib/bigint.dart
@@ -267,7 +267,9 @@
return r_used;
}
- // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n.
+ // r_digits[ds..x_used+ds] = x_digits[0..x_used-1] << (n % _DIGIT_BITS)
+ // where ds = ceil(n / _DIGIT_BITS)
+ // Doesn't clear digits below ds.
static void _lsh(Uint32List x_digits, int x_used, int n,
Uint32List r_digits) {
final ds = n ~/ _DIGIT_BITS;
@@ -292,7 +294,7 @@
return _dlShift(ds);
}
var r_used = _used + ds + 1;
- var r_digits = new Uint32List(r_used + 2 + (r_used & 1)); // +2 for 64-bit.
+ var r_digits = new Uint32List(r_used + 2 - (r_used & 1)); // for 64-bit.
_lsh(_digits, _used, n, r_digits);
return new _Bigint(_neg, r_used, r_digits);
}
@@ -307,7 +309,7 @@
return _dlShiftDigits(x_digits, x_used, ds, r_digits);
}
var r_used = x_used + ds + 1;
- assert(r_digits.length >= r_used + 2 + (r_used & 1)); // +2 for 64-bit.
+ assert(r_digits.length >= r_used + 2 - (r_used & 1)); // for 64-bit.
_lsh(x_digits, x_used, n, r_digits);
var i = ds;
while (--i >= 0) {
@@ -1404,7 +1406,7 @@
if (e == 0) return 1;
m = m._toBigint();
final m_used = m._used;
- final m_used2p4 = 2*m_used + 4;
+ final m_used2p4 = 2 * m_used + 4;
final e_bitlen = e.bitLength;
if (e_bitlen <= 0) return 1;
final bool cannotUseMontgomery = m.isEven || _abs() >= m;
@@ -1562,7 +1564,7 @@
if (((x_used == 1) && (x_digits[0] == 1)) ||
((y_used == 1) && (y_digits[0] == 1))) return 1;
bool xy_cloned = false;
- while (x.isEven && y.isEven) {
+ while (((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0)) {
_rsh(x_digits, x_used, 1, x_digits);
_rsh(y_digits, y_used, 1, y_digits);
s++;
@@ -1583,7 +1585,7 @@
}
}
var u_digits = _cloneDigits(x_digits, 0, x_used, m_len);
- var v_digits = _cloneDigits(y_digits, 0, y_used, m_len);
+ var v_digits = _cloneDigits(y_digits, 0, y_used, m_len + 2); // +2 for lsh.
final bool ac = (x_digits[0] & 1) == 0;
// Variables a, b, c, and d require one more digit.
@@ -1747,7 +1749,7 @@
}
if (!inv) {
if (s > 0) {
- _lsh(v_digits, m_used, s, v_digits);
+ m_used = _lShiftDigits(v_digits, m_used, s, v_digits);
}
return new _Bigint(false, m_used, v_digits)._toValidInt();
}
diff --git a/tests/corelib/corelib.status b/tests/corelib/corelib.status
index f107d2c..c029ea4 100644
--- a/tests/corelib/corelib.status
+++ b/tests/corelib/corelib.status
@@ -36,6 +36,9 @@
int_parse_radix_test/02: Fail # No bigints.
double_parse_test/01: Pass, Fail # JS implementations disagree on U+0085 being whitespace.
integer_to_radix_string_test: RuntimeError # issue 22045
+int_modulo_arith_test/bignum: RuntimeError # No bigints.
+int_modulo_arith_test/modPow: RuntimeError # No bigints.
+
# With the exception of 'void', const Symbol() should not accept reserved
# words.
diff --git a/tests/corelib/int_modulo_arith_test.dart b/tests/corelib/int_modulo_arith_test.dart
new file mode 100644
index 0000000..87d253d
--- /dev/null
+++ b/tests/corelib/int_modulo_arith_test.dart
@@ -0,0 +1,207 @@
+// Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import "package:expect/expect.dart";
+
+import "dart:math" show pow;
+
+var smallNumber = 1234567890; // is 31-bit integer.
+var mediumNumber = 1234567890123456; // is 53-bit integer
+var bigNumber = 590295810358705600000; // is > 64-bit integer, exact as double.
+
+testModPow() {
+ test(x, e, m, expectedResult) {
+ // Check that expected result is correct, using an unoptimized version.
+ assert(() {
+ if (1 is double) return true; // Don't have bignums.
+ slowModPow(x, e, m) {
+ var r = 1;
+ while (e > 0) {
+ if (e.isOdd) r = (r * x) % m;
+ e >>= 1;
+ x = (x * x) % m;
+ }
+ return r;
+ }
+ return slowModPow(x, e, m) == expectedResult;
+ });
+ var result = x.modPow(e, m);
+ Expect.equals(expectedResult, result, "$x.modPow($e, $m)");
+ }
+
+ test(10, 20, 1, 0);
+ test(1234567890, 1000000001, 19, 11);
+ test(1234567890, 19, 1000000001, 122998977);
+ test(19, 1234567890, 1000000001, 619059596);
+ test(19, 1000000001, 1234567890, 84910879);
+ test(1000000001, 19, 1234567890, 872984351);
+ test(1000000001, 1234567890, 19, 0);
+ test(12345678901234567890, 10000000000000000001, 19, 2);
+ test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625);
+ test(19, 12345678901234567890, 10000000000000000001, 4544207837373941034);
+ test(19, 10000000000000000001, 12345678901234567890, 11135411705397624859);
+ test(10000000000000000001, 19, 12345678901234567890, 2034013733189773841);
+ test(10000000000000000001, 12345678901234567890, 19, 1);
+ test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625);
+ test(12345678901234567890, 10000000000000000001, 19, 2);
+ test(123456789012345678901234567890,
+ 123456789012345678901234567891,
+ 123456789012345678901234567899,
+ 116401406051033429924651549616);
+ test(123456789012345678901234567890,
+ 123456789012345678901234567899,
+ 123456789012345678901234567891,
+ 123456789012345678901234567890);
+ test(123456789012345678901234567899,
+ 123456789012345678901234567890,
+ 123456789012345678901234567891,
+ 35088523091000351053091545070);
+ test(123456789012345678901234567899,
+ 123456789012345678901234567891,
+ 123456789012345678901234567890,
+ 18310047270234132455316941949);
+ test(123456789012345678901234567891,
+ 123456789012345678901234567899,
+ 123456789012345678901234567890,
+ 1);
+ test(123456789012345678901234567891,
+ 123456789012345678901234567890,
+ 123456789012345678901234567899,
+ 40128068573873018143207285483);
+
+}
+
+testModInverse() {
+ test(x, m, expectedResult) {
+ //print("$x op $m == $expectedResult");
+ // Check that expectedResult is an inverse.
+ assert(expectedResult < m);
+ // The 1 % m handles the m = 1 special case.
+ // This test may overflow if we don't have bignums, so only run on VM.
+ assert(1 is double || (((x % m) * expectedResult) - 1) % m == 0);
+
+ var result = x.modInverse(m);
+ Expect.equals(expectedResult, result, "$x modinv $m");
+
+ if (x > m) {
+ x = x % m;
+ var result = x.modInverse(m);
+ Expect.equals(expectedResult, result, "$x modinv $m");
+ }
+ }
+
+ testThrows(x, m) {
+ // Throws if not co-prime, which is a symmetric property.
+ Expect.throws(() => x.modInverse(m), null, "$x modinv $m");
+ Expect.throws(() => m.modInverse(x), null, "$m modinv $x");
+ }
+
+ test(1, 1, 0);
+
+ testThrows(0, 1000000001);
+ testThrows(2, 4);
+ testThrows(99, 9);
+ testThrows(19, 1000000001);
+ testThrows(123456789012345678901234567890, 123456789012345678901234567899);
+
+ // Co-prime numbers
+ test(1234567890, 19, 11);
+ test(1234567890, 1000000001, 189108911);
+ test(19, 1234567890, 519818059);
+ test(1000000001, 1234567890, 1001100101);
+
+ test(12345, 12346, 12345);
+ test(12345, 12346, 12345);
+
+ test(smallNumber, 137, 42);
+ test(137, smallNumber, 856087223);
+ test(mediumNumber, 137, 77);
+ test(137, mediumNumber, 540686667207353);
+ test(bigNumber, 137, 128); /// bignum: ok
+ // Bigger numbers as modulo is tested in big_integer_arith_vm_test.dart.
+ // Big doubles are not co-prime, so there is nothing to test for dart2js.
+}
+
+testGcd() {
+ // Call testFunc with all combinations and orders of plus/minus
+ // value and other.
+ callCombos(value, other, testFunc) {
+ testFunc(value, other);
+ testFunc(value, -other);
+ testFunc(-value, other);
+ testFunc(-value, -other);
+ if (value == other) return;
+ testFunc(other, value);
+ testFunc(other, -value);
+ testFunc(-other, value);
+ testFunc(-other, -value);
+ }
+
+ // Test that gcd of value and other (non-negative) is expectedResult.
+ // Tests all combinations of positive and negative values and order of
+ // operands, so use positive values and order is not important.
+ test(value, other, [expectedResult]) {
+ assert(value % expectedResult == 0); // Check for bug in test.
+ assert(other % expectedResult == 0);
+ callCombos(value, other, (a, b) {
+ var result = a.gcd(b);
+ /// Check that the result is a divisor.
+ Expect.equals(0, a % result, "$result | $a");
+ Expect.equals(0, b % result, "$result | $b");
+ // Check for bug in test. If assert fails, the expected value is too low,
+ // and the gcd call has found a greater common divisor.
+ assert(result >= expectedResult);
+ Expect.equals(expectedResult, result, "$a.gcd($b)");
+ });
+ }
+
+ // Test that gcd of value and other (non-negative) throws.
+ testThrows(value, other) {
+ callCombos(value, other, (a, b) {
+ Expect.throws(() => a.gcd(b), null, "$a.gcd($b)");
+ });
+ }
+
+ // Throws if either operand is zero, and if both operands are zero.
+ testThrows(0, 1000);
+ testThrows(0, 0);
+
+ // Format:
+ // test(value1, value2, expectedResult);
+ test(1, 1, 1); // both are 1
+ test(1, 2, 1); // one is 1
+ test(3, 5, 1); // coprime.
+ test(37, 37, 37); // Same larger prime.
+
+ test(9999, 7272, 909); // Larger numbers
+
+ // Multiplying both operands by a number multiplies result by same number.
+ test(693, 609, 21);
+ test(693 << 5, 609 << 5, 21 << 5);
+ test(693 * 937, 609 * 937, 21 * 937);
+ test(693 * pow(2, 32), 609 * pow(2, 32), 21 * pow(2, 32));
+ test(693 * pow(2, 52), 609 * pow(2, 52), 21 * pow(2, 52));
+ test(693 * pow(2, 53), 609 * pow(2, 53), 21 * pow(2, 53)); // Regression.
+ test(693 * pow(2, 99), 609 * pow(2, 99), 21 * pow(2, 99));
+
+ test(1234567890, 19, 1);
+ test(1234567890, 1000000001, 1);
+ test(19, 1000000001, 19);
+
+ test(0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF);
+ test(0x3FFFFFFF, 0x40000000, 1);
+
+ test(pow(2, 54), pow(2, 53), pow(2, 53));
+
+ test((pow(2, 52) - 1) * pow(2, 14),
+ (pow(2, 26) - 1) * pow(2, 22),
+ (pow(2, 26) - 1) * pow(2, 14));
+}
+
+main() {
+ testModPow(); /// modPow: ok
+ testModInverse();
+ testGcd();
+}
+
diff --git a/tools/VERSION b/tools/VERSION
index 18c087c..098b2ed 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -26,6 +26,6 @@
CHANNEL stable
MAJOR 1
MINOR 11
-PATCH 0
+PATCH 1
PRERELEASE 0
PRERELEASE_PATCH 0