From 4d47718e301ca993b293c93368384c009e18beee Mon Sep 17 00:00:00 2001 From: Andy Ayers Date: Mon, 11 Jan 2016 17:40:56 -0800 Subject: Add miscellaneous benchmarks Burgers and the three V8 benchmarks: Richards, Crypto, Deltablue. --- .../JIT/Performance/CodeQuality/Burgers/Burgers.cs | 332 +++ .../Performance/CodeQuality/Burgers/Burgers.csproj | 45 + .../Performance/CodeQuality/V8/Crypto/Crypto.cs | 2105 ++++++++++++++++++++ .../CodeQuality/V8/Crypto/Crypto.csproj | 45 + .../CodeQuality/V8/DeltaBlue/DeltaBlue.cs | 1060 ++++++++++ .../CodeQuality/V8/DeltaBlue/DeltaBlue.csproj | 45 + .../CodeQuality/V8/Richards/Richards.cs | 756 +++++++ .../CodeQuality/V8/Richards/Richards.csproj | 45 + tests/src/JIT/config/benchmark/project.json | 1 + tests/src/JIT/config/benchmark/project.lock.json | 84 + 10 files changed, 4518 insertions(+) create mode 100644 tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.csproj create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.cs create mode 100644 tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.csproj (limited to 'tests/src') diff --git a/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.cs b/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.cs new file mode 100644 index 0000000000..0c0ced1b61 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.cs @@ -0,0 +1,332 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// +// .NET SIMD to solve Burgers' equation +// +// Benchmark based on +// http://taumuon-jabuka.blogspot.co.uk/2014/10/net-simd-to-solve-burgers-equation.html + +using Microsoft.Xunit.Performance; +using System; +using System.Linq; +using System.Numerics; +using System.Runtime.CompilerServices; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +public class Burgers +{ + private static double BurgersAnalytical(double t, double x, double nu) + { + return -2 * nu * (-(-8 * t + 2 * x) * Math.Exp(-Math.Pow((-4 * t + x), 2) / (4 * nu * (t + 1))) / (4 * nu * (t + 1)) - (-8 * t + 2 * x - 12.5663706143592) * Math.Exp(-Math.Pow(-4 * t + x - 6.28318530717959, 2) / (4 * nu * (t + 1))) / (4 * nu * (t + 1))) / (Math.Exp(-Math.Pow(-4 * t + x - 6.28318530717959, 2) / (4 * nu * (t + 1))) + Math.Exp(-Math.Pow(-4 * t + x, 2) / (4 * nu * (t + 1)))) + 4; + } + + private static double[] linspace(double first, double last, int num) + { + var step = (last - first) / (double)num; + return Enumerable.Range(0, num).Select(v => (v * step) + first).ToArray(); + } + + private static double[] GetAnalytical(double[] x, double t, double nu) + { + double[] u = new double[x.Length]; + + for (int i = 0; i < x.Length; ++i) + { + u[i] = BurgersAnalytical(t, x[i], nu); + } + + return u; + } + + private static double[] GetCalculated0(int nt, int nx, double dx, double dt, double nu, double[] initial) + { + double[] u = new double[nx]; + Array.Copy(initial, u, u.Length); + + for (int tStep = 0; tStep < nt; tStep++) + { + double[] un = new double[nx]; + Array.Copy(u, un, u.Length); + + for (int i = 1; i < nx - 1; i++) + { + u[i] = un[i] - un[i] * dt / dx * (un[i] - un[i - 1]) + Math.Pow(nu * dt / dx, 2.0) * + (un[i + 1] - 2 * un[i] + un[i - 1]); + } + + u[0] = un[0] - un[0] * dt / dx * (un[0] - un[nx - 1]) + Math.Pow(nu * dt / dx, 2.0) * + (un[1] - 2 * un[0] + un[nx - 1]); + + u[nx - 1] = un[nx - 1] - un[nx - 1] * dt / dx * (un[nx - 1] - un[nx - 2]) + Math.Pow(nu * dt / dx, 2.0) * + (un[0] - 2 * un[nx - 1] + un[nx - 2]); + } + + return u; + } + + // Reduce new array allocation and copying, ping-pong between them + private static double[] GetCalculated1(int nt, int nx, double dx, double dt, double nu, double[] initial) + { + double[] u = new double[nx]; + double[] un = new double[nx]; + Array.Copy(initial, un, un.Length); + + for (int tStep = 0; tStep < nt; tStep++) + { + for (int i = 1; i < nx - 1; i++) + { + u[i] = un[i] - un[i] * dt / dx * (un[i] - un[i - 1]) + Math.Pow(nu * dt / dx, 2.0) * + (un[i + 1] - 2 * un[i] + un[i - 1]); + } + + u[0] = un[0] - un[0] * dt / dx * (un[0] - un[nx - 1]) + Math.Pow(nu * dt / dx, 2.0) * + (un[1] - 2 * un[0] + un[nx - 1]); + + u[nx - 1] = un[nx - 1] - un[nx - 1] * dt / dx * (un[nx - 1] - un[nx - 2]) + Math.Pow(nu * dt / dx, 2.0) * + (un[0] - 2 * un[nx - 1] + un[nx - 2]); + + double[] swap = u; + u = un; + un = swap; + } + + return un; + } + + // Pull calculation of (nu * dt / dx)^2 out into a variable + private static double[] GetCalculated2(int nt, int nx, double dx, double dt, double nu, double[] initial) + { + double[] u = new double[nx]; + double[] un = new double[nx]; + Array.Copy(initial, un, un.Length); + + double factor = Math.Pow(nu * dt / dx, 2.0); + + for (int tStep = 0; tStep < nt; tStep++) + { + for (int i = 1; i < nx - 1; i++) + { + u[i] = un[i] - un[i] * dt / dx * (un[i] - un[i - 1]) + factor * + (un[i + 1] - 2 * un[i] + un[i - 1]); + } + + u[0] = un[0] - un[0] * dt / dx * (un[0] - un[nx - 1]) + factor * + (un[1] - 2 * un[0] + un[nx - 1]); + + u[nx - 1] = un[nx - 1] - un[nx - 1] * dt / dx * (un[nx - 1] - un[nx - 2]) + factor * + (un[0] - 2 * un[nx - 1] + un[nx - 2]); + + double[] swap = u; + u = un; + un = swap; + } + + return un; + } + + // SIMD + private static double[] GetCalculated3(int nt, int nx, double dx, double dt, double nu, double[] initial) + { + var nx2 = nx + (Vector.Count - (nx % Vector.Count)); + + double[] u = new double[nx2]; + double[] un = new double[nx2]; + Array.Copy(initial, un, initial.Length); + + double factor = Math.Pow(nu * dt / dx, 2.0); + + for (int tStep = 0; tStep < nt; tStep++) + { + for (int i = 1; i < nx2 - 1; i += Vector.Count) + { + var vectorIn0 = new Vector(un, i); + var vectorInPrev = new Vector(un, i - 1); + var vectorInNext = new Vector(un, i + 1); + + var vectorOut = vectorIn0 - vectorIn0 * (dt / dx) * (vectorIn0 - vectorInPrev) + factor * + (vectorInNext - 2.0 * vectorIn0 + vectorInPrev); + + vectorOut.CopyTo(u, i); + } + + u[0] = un[0] - un[0] * dt / dx * (un[0] - un[nx - 1]) + factor * + (un[1] - 2 * un[0] + un[nx - 1]); + + u[nx - 1] = un[nx - 1] - un[nx - 1] * dt / dx * (un[nx - 1] - un[nx - 2]) + factor * + (un[0] - 2 * un[nx - 1] + un[nx - 2]); + + double[] swap = u; + u = un; + un = swap; + } + + return un; + } + + public static int Main() + { + if (!Vector.IsHardwareAccelerated) + { + Console.WriteLine("Not hardware accelerated!"); + } + else + { + Console.WriteLine("Vector.Length: " + Vector.Count); + } + + int nx = 10001; + int nt = 10000; + double dx = 2.0 * Math.PI / (nx - 1.0); + double nu = 0.07; + double dt = dx * nu; + double[] x = linspace(0.0, 2.0 * Math.PI, nx); + double[] initial = GetAnalytical(x, 0.0, nu); + + // Warmup + + GetCalculated0(1, nx, dx, dt, nu, initial); + GetCalculated1(1, nx, dx, dt, nu, initial); + GetCalculated2(1, nx, dx, dt, nu, initial); + GetCalculated3(1, nx, dx, dt, nu, initial); + + double[][] results = new double[4][]; + + var stopwatch = new System.Diagnostics.Stopwatch(); + + stopwatch.Start(); + results[0] = GetCalculated0(nt, nx, dx, dt, nu, initial); + stopwatch.Stop(); + Console.WriteLine("Baseline: " + stopwatch.ElapsedMilliseconds); + stopwatch.Reset(); + + stopwatch.Start(); + results[1] = GetCalculated1(nt, nx, dx, dt, nu, initial); + stopwatch.Stop(); + Console.WriteLine("Reduce copy: " + stopwatch.ElapsedMilliseconds); + stopwatch.Reset(); + + stopwatch.Start(); + results[2] = GetCalculated2(nt, nx, dx, dt, nu, initial); + stopwatch.Stop(); + Console.WriteLine("CSE of Math.Pow: " + stopwatch.ElapsedMilliseconds); + stopwatch.Reset(); + + stopwatch.Start(); + results[3] = GetCalculated3(nt, nx, dx, dt, nu, initial); + stopwatch.Stop(); + Console.WriteLine("SIMD: " + stopwatch.ElapsedMilliseconds); + stopwatch.Reset(); + + for (int i = 0; i < x.Length; i += 33) + { + double expected = results[0][i]; + for (int j = 1; j < results.Length; j++) + { + bool valid = Math.Abs(expected - results[j][i]) < 1e-4; + if (!valid) + { + Console.WriteLine("Failed to validate"); + return -1; + } + } + } + + return 100; + } + + static volatile object VolatileObject; + + [MethodImpl(MethodImplOptions.NoInlining)] + static void Escape(object obj) + { + VolatileObject = obj; + } + + [Benchmark] + public static void Test0() + { + int nx = 10001; + int nt = 10000; + double dx = 2.0 * Math.PI / (nx - 1.0); + double nu = 0.07; + double dt = dx * nu; + double[] x = linspace(0.0, 2.0 * Math.PI, nx); + double[] initial = GetAnalytical(x, 0.0, nu); + + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + double[] results = GetCalculated0(nt, nx, dx, dt, nu, initial); + Escape(results); + } + } + } + + [Benchmark] + public static void Test1() + { + int nx = 10001; + int nt = 10000; + double dx = 2.0 * Math.PI / (nx - 1.0); + double nu = 0.07; + double dt = dx * nu; + double[] x = linspace(0.0, 2.0 * Math.PI, nx); + double[] initial = GetAnalytical(x, 0.0, nu); + + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + double[] results = GetCalculated1(nt, nx, dx, dt, nu, initial); + Escape(results); + } + } + } + + [Benchmark] + public static void Test2() + { + int nx = 10001; + int nt = 10000; + double dx = 2.0 * Math.PI / (nx - 1.0); + double nu = 0.07; + double dt = dx * nu; + double[] x = linspace(0.0, 2.0 * Math.PI, nx); + double[] initial = GetAnalytical(x, 0.0, nu); + + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + double[] results = GetCalculated2(nt, nx, dx, dt, nu, initial); + Escape(results); + } + } + } + + [Benchmark] + public static void Test3() + { + // Make SIMD version work a bit harder.... + int nx = 10001; + int nt = 2 * 10000; + double dx = 2.0 * Math.PI / (nx - 1.0); + double nu = 0.07; + double dt = dx * nu; + double[] x = linspace(0.0, 2.0 * Math.PI, nx); + double[] initial = GetAnalytical(x, 0.0, nu); + + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + double[] results = GetCalculated3(nt, nx, dx, dt, nu, initial); + Escape(results); + } + } + } +} + diff --git a/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.csproj b/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.csproj new file mode 100644 index 0000000000..43fc827205 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/Burgers/Burgers.csproj @@ -0,0 +1,45 @@ + + + + + Debug + AnyCPU + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + 7a9bfb7d + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs new file mode 100644 index 0000000000..34031a73e4 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.cs @@ -0,0 +1,2105 @@ +/* + * Copyright (c) 2003-2005 Tom Wu + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, + * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY + * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + * + * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL, + * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER + * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF + * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT + * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * In addition, the following condition applies: + * + * All redistributions must retain an intact copy of this copyright notice + * and disclaimer. + */ + +// Comment this out to use a fixed random number seed. + +#define USE_RANDOM_SEED + +// The code has been adapted for use as a benchmark by Microsoft. + +using Microsoft.Xunit.Performance; +using System; +using System.Collections.Generic; +using System.Globalization; + +namespace Crypto +{ + public class Support + { + private const string INPUT = "The quick brown fox jumped over the extremely lazy frogs!"; + + public static int Main(String[] args) + { + int n = 1; + + if (args.Length > 0) + { + n = Int32.Parse(args[0]); + } + + bool verbose = false; + + if (args.Length > 1) + { + switch (args[1]) + { + case "verbose": + verbose = true; + break; + default: + Console.WriteLine("Bad arg: '{0}'.\n", args[1]); + return -1; + } + } + + Measure(n, verbose); + + bool result = s_TEXT.Equals(INPUT); + + return (result ? 100 : -1); + } + + [Benchmark] + public static void Bench() + { + const int Iterations = 10; + const int n = 8; + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + for (int i = 0; i < Iterations; i++) + { + Measure(n, false); + } + } + } + } + + public static void Measure(int n, bool verbose) + { + DateTime start = DateTime.Now; + Setup(); + for (int i = 0; i < n; i++) + { + runEncrypt(verbose); + runDecrypt(verbose); + } + DateTime end = DateTime.Now; + TimeSpan dur = end - start; + if (verbose) + { + Console.WriteLine("Doing {0} iters of Crytpo takes {1} ms; {2} usec/iter.", + n, dur.TotalMilliseconds, dur.TotalMilliseconds * 1000 / n); + } + } + + private static RSAKey s_RSA; + private static String s_TEXT; + + private static void Setup() + { + String nValue = "a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3"; + String eValue = "10001"; + String dValue = "8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161"; + String pValue = "d090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d"; + String qValue = "cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f"; + String dmp1Value = "1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25"; + String dmq1Value = "3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd"; + String coeffValue = "3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250"; + + BigInteger.setupEngine(new BigInteger.AMSig(BigInteger.am3), 28); + + s_RSA = new RSAKey(); + s_RSA.setPublic(nValue, eValue); + s_RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue); + + s_TEXT = INPUT; + } + + public static void runEncrypt(bool verbose) + { + var res = s_RSA.encrypt(s_TEXT); + if (verbose) Console.WriteLine("encrypt '{0}' is '{1}'", s_TEXT, res); + s_TEXT = res; + } + public static void runDecrypt(bool verbose) + { + var res = s_RSA.decrypt(s_TEXT); + if (verbose) Console.WriteLine("decrypt '{0}' is '{1}'", s_TEXT, res); + s_TEXT = res; + } + } + + internal class ListX : List + { + public ListX() : base() { } + public ListX(int cap) : base(cap) { } + + public new T this[int index] + { + get { return base[index]; } + set + { + if (index < Count) + { + base[index] = value; + } + else + { + for (int j = Count; j < index; j++) + { + base.Add(default(T)); + } + base.Add(value); + } + } + } + } + + // Basic JavaScript BN library - subset useful for RSA encryption. + + internal class BigInteger + { + private ListX _array; + private int _t; + private int _s; + + // Bits per digit + private static int s_dbits; + private static int s_BI_DB; + private static int s_BI_DM; + private static int s_BI_DV; + + private static int s_BI_FP; + private static ulong s_BI_FV; + private static int s_BI_F1; + private static int s_BI_F2; + + // JavaScript engine analysis + private const long canary = 0xdeadbeefcafe; + private const bool j_lm = ((canary & 0xffffff) == 0xefcafe); + + // (public) Constructor + public BigInteger(int a, int b, SecureRandom c) + { + _array = new ListX(); + this.fromNumber(a, b, c); + } + + public BigInteger() + { + _array = new ListX(); + } + + public BigInteger(String a) + { + _array = new ListX(); + this.fromString(a, 256); + } + public BigInteger(byte[] ba) + { + _array = new ListX(); + this.fromByteArray(ba); + } + public BigInteger(String a, int b) + { + _array = new ListX(); + this.fromString(a, b); + } + + // return new, unset BigInteger + private static BigInteger nbi() { return new BigInteger(); } + + public delegate int AMSig(BigInteger bi, int i, int x, BigInteger w, int j, int c, int n); + + private static AMSig s_am; + + // am: Compute w_j += (x*this_i), propagate carries, + // c is initial carry, returns final carry. + // c < 3*dvalue, x < 2*dvalue, this_i < dvalue + // We need to select the fastest one that works in this environment. + + // These appear to be unused +#if false + // am1: use a single mult and divide to get the high bits, + // max digit bits should be 26 because + // max internal value = 2*dvalue^2-2*dvalue (< 2^53) + function am1(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + while(--n >= 0) { + var v = x*this_array[i++]+w_array[j]+c; + c = Math.floor(v/0x4000000); + w_array[j++] = v&0x3ffffff; + } + return c; + } + + // am2 avoids a big mult-and-extract completely. + // Max digit bits should be <= 30 because we do bitwise ops + // on values up to 2*hdvalue^2-hdvalue-1 (< 2^31) + function am2(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + var xl = x&0x7fff, xh = x>>15; + while(--n >= 0) { + var l = this_array[i]&0x7fff; + var h = this_array[i++]>>15; + var m = xh*l+h*xl; + l = xl*l+((m&0x7fff)<<15)+w_array[j]+(c&0x3fffffff); + c = (l>>>30)+(m>>>15)+xh*h+(c>>>30); + w_array[j++] = l&0x3fffffff; + } + return c; + } +#endif + + // Alternately, set max digit bits to 28 since some + // browsers slow down when dealing with 32-bit numbers. + public static int am3(BigInteger bi, int i, int x, BigInteger w, int j, int c, int n) + { + var this_array = bi._array; + var w_array = w._array; + + var xl = x & 0x3fff; var xh = x >> 14; + while (--n >= 0) + { + var l = this_array[i] & 0x3fff; + var h = this_array[i++] >> 14; + var m = xh * l + h * xl; + l = xl * l + ((m & 0x3fff) << 14) + w_array[j] + c; + c = (l >> 28) + (m >> 14) + xh * h; + w_array[j++] = l & 0xfffffff; + } + return c; + } + + +#if false + // This is tailored to VMs with 2-bit tagging. It makes sure + // that all the computations stay within the 29 bits available. + function am4(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + + var xl = x&0x1fff, xh = x>>13; + while(--n >= 0) { + var l = this_array[i]&0x1fff; + var h = this_array[i++]>>13; + var m = xh*l+h*xl; + l = xl*l+((m&0x1fff)<<13)+w_array[j]+c; + c = (l>>26)+(m>>13)+xh*h; + w_array[j++] = l&0x3ffffff; + } + return c; + } +#endif + + // Digit conversions + private const String BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz"; + private static int[] s_BI_RC; + + // am3/28 is best for SM, Rhino, but am4/26 is best for v8. + // Kestrel (Opera 9.5) gets its best result with am4/26. + // IE7 does 9% better with am3/28 than with am4/26. + // Firefox (SM) gets 10% faster with am3/28 than with am4/26. + + + public static void setupEngine(AMSig fn, int bits) + { + BigInteger.s_am = fn; + s_dbits = bits; + + s_BI_DB = s_dbits; + s_BI_DM = ((((int)1) << (int)s_dbits) - 1); + s_BI_DV = (((int)1) << (int)s_dbits); + + s_BI_FP = 52; + // The RHS had been Math.Pow(2,BI_FP); + s_BI_FV = (((ulong)1) << (int)s_BI_FP); + s_BI_F1 = s_BI_FP - s_dbits; + s_BI_F2 = 2 * s_dbits - s_BI_FP; + + s_BI_RC = new int[256]; + + // char rr = "0".charCodeAt(0); + char rr = '0'; + for (int vv = 0; vv <= 9; ++vv) s_BI_RC[rr++] = vv; + // rr = 'a".charCodeAt(0); + rr = 'a'; + for (int vv = 10; vv < 36; ++vv) s_BI_RC[rr++] = vv; + // rr = "A".charCodeAt(0); + rr = 'A'; + for (int vv = 10; vv < 36; ++vv) s_BI_RC[rr++] = vv; + } + + private static char int2char(int n) { return BI_RM[(int)n]; } + private static int intAt(String s, int i) + { + // int c = (int)BI_RC[s[(int)i]]; + // return (c==null)?-1:c; + if (i > s_BI_RC.Length) return -1; + else return (int)s_BI_RC[s[(int)i]]; + } + + // (protected) copy this to r + private void copyTo(BigInteger r) + { + var this_array = _array; + var r_array = r._array; + + for (var i = _t - 1; i >= 0; --i) r_array[i] = this_array[i]; + r._t = _t; + r._s = _s; + } + + // (protected) set from integer value x, -DV <= x < DV + private void fromInt(int x) + { + var this_array = _array; + _t = 1; + _s = (x < 0) ? -1 : 0; + if (this_array.Count == 0) + { + if (x > 0) + this_array.Add(x); + else if (x < -1) + this_array.Add(x + s_BI_DV); + else + _t = 0; + } + else + { + if (x > 0) this_array[0] = (int)x; + else if (x < -1) this_array[0] = (int)(x + s_BI_DV); + else _t = 0; + } + } + + // return bigint initialized to value + private static BigInteger nbv(int i) { var r = nbi(); r.fromInt(i); return r; } + + // (protected) set from string and radix + private void fromString(String s, int b) + { + var this_array = _array; + int k; + if (b == 16) k = 4; + else if (b == 8) k = 3; + else if (b == 256) k = 8; // byte array + else if (b == 2) k = 1; + else if (b == 32) k = 5; + else if (b == 4) k = 2; + else { this.fromRadix(s, b); return; } + _t = 0; + _s = 0; + int i = s.Length; bool mi = false; var sh = 0; + while (--i >= 0) + { + int x = (k == 8) ? (s[i] & 0xff) : intAt(s, (int)i); + if (x < 0) + { + if (s[i] == '-') mi = true; + continue; + } + mi = false; + if (sh == 0) + this_array[_t++] = (int)x; + else if (sh + k > s_BI_DB) + { + this_array[_t - 1] |= ((int)x & ((((int)1) << (s_BI_DB - sh)) - 1)) << sh; + this_array[_t++] = ((int)x >> (s_BI_DB - sh)); + } + else + this_array[_t - 1] |= ((int)x) << sh; + sh += (int)k; + if (sh >= s_BI_DB) sh -= s_BI_DB; + } + if (k == 8 && (s[0] & 0x80) != 0) + { + _s = -1; + if (sh > 0) this_array[_t - 1] |= ((((int)1) << (s_BI_DB - sh)) - 1) << sh; + } + this.clamp(); + if (mi) BigInteger.ZERO.subTo(this, this); + } + + private void fromByteArray(byte[] ba) + { + var this_array = _array; + _t = 0; + _s = 0; + int i = ba.Length; bool mi = false; var sh = 0; + while (--i >= 0) + { + int x = ba[i] & 0xff; + mi = false; + if (sh == 0) + this_array[_t++] = (int)x; + else if (sh + 8 > s_BI_DB) + { + this_array[_t - 1] |= ((int)x & ((((int)1) << (s_BI_DB - sh)) - 1)) << sh; + this_array[_t++] = ((int)x >> (s_BI_DB - sh)); + } + else + this_array[_t - 1] |= ((int)x) << sh; + sh += 8; + if (sh >= s_BI_DB) sh -= s_BI_DB; + } + if ((ba[0] & 0x80) != 0) + { + _s = -1; + if (sh > 0) this_array[_t - 1] |= ((((int)1) << (s_BI_DB - sh)) - 1) << sh; + } + this.clamp(); + if (mi) BigInteger.ZERO.subTo(this, this); + } + + // (protected) clamp off excess high words + private void clamp() + { + var this_array = _array; + var c = _s & s_BI_DM; + while (_t > 0 && this_array[_t - 1] == c) --_t; + } + + // (public) return string representation in given radix + public String toString(int b) + { + var this_array = _array; + if (_s < 0) return "-" + this.negate().toString(b); + int k; + if (b == 16) k = 4; + else if (b == 8) k = 3; + else if (b == 2) k = 1; + else if (b == 32) k = 5; + else if (b == 4) k = 2; + else return this.toRadix(b); + int km = ((int)1 << k) - 1; + int d; bool m = false; var r = ""; int i = (int)_t; + int p = (s_BI_DB - (i * s_BI_DB) % k); + if (i-- > 0) + { + if (p < s_BI_DB && (d = this_array[i] >> p) > 0) { m = true; r = new String(int2char(d), 1); } + while (i >= 0) + { + if (p < k) + { + d = (this_array[i] & ((((int)1) << p) - 1)) << (k - p); + d |= this_array[--i] >> (p += (int)(s_BI_DB - k)); + } + else + { + d = (this_array[i] >> (p -= k)) & km; + if (p <= 0) { p += (int)s_BI_DB; --i; } + } + if (d > 0) m = true; + if (m) r += int2char(d); + } + } + return m ? r : "0"; + } + + // (public) -this + public BigInteger negate() { var r = nbi(); BigInteger.ZERO.subTo(this, r); return r; } + + // (public) |this| + public BigInteger abs() { return (_s < 0) ? this.negate() : this; } + + // (public) return + if this > a, - if this < a, 0 if equal + public int compareTo(BigInteger a) + { + var this_array = _array; + var a_array = a._array; + + var r = _s - a._s; + if (r != 0) return r; + int i = (int)_t; + r = i - (int)a._t; + if (r != 0) return r; + while (--i >= 0) if ((r = (int)(this_array[i] - a_array[i])) != 0) return r; + return 0; + } + + // returns bit length of the integer x + public int nbits(int x) + { + int r = 1; + int t; + if ((t = x >> 16) != 0) { x = t; r += 16; } + if ((t = x >> 8) != 0) { x = t; r += 8; } + if ((t = x >> 4) != 0) { x = t; r += 4; } + if ((t = x >> 2) != 0) { x = t; r += 2; } + if ((t = x >> 1) != 0) { x = t; r += 1; } + return r; + } + + // (public) return the number of bits in "this" + public int bitLength() + { + var this_array = _array; + if (_t <= 0) return 0; + return ((int)s_BI_DB) * (_t - 1) + nbits(this_array[_t - 1] ^ (int)(_s & s_BI_DM)); + } + + // (protected) r = this << n*DB + private void dLShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + for (int i = (int)_t - 1; i >= 0; --i) r_array[i + n] = this_array[i]; + for (int i = (int)n - 1; i >= 0; --i) r_array[i] = 0; + r._t = _t + (int)n; + r._s = _s; + } + + // (protected) r = this >> n*DB + private void dRShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + for (var i = n; i < _t; ++i) r_array[i - n] = this_array[i]; + r._t = (int)Math.Max(_t - n, 0); + r._s = _s; + } + + // (protected) r = this << n + private void lShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + int bs = (int)(n % s_BI_DB); + int cbs = (int)(s_BI_DB - bs); + var bm = ((int)1 << cbs) - 1; + int ds = n / s_BI_DB; int c = ((int)_s << bs) & s_BI_DM; + for (int i = (int)_t - 1; i >= 0; --i) + { + r_array[i + ds + 1] = (this_array[i] >> cbs) | c; + c = (this_array[i] & bm) << bs; +#if TRACING + Console.WriteLine(" i = {0}, this_array[i] = {3}, r_array[i + ds + 1] = {1}; c = {2}.", i, r_array[i + ds + 1], c, this_array[i]); +#endif + } + for (int i = (int)ds - 1; i >= 0; --i) r_array[i] = 0; + r_array[ds] = c; + r._t = _t + (int)ds + 1; + r._s = _s; + r.clamp(); + } + + // (protected) r = this >> n + private void rShiftTo(int n, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + r._s = _s; + var ds = n / s_BI_DB; + if (ds >= _t) { r._t = 0; return; } + int bs = (int)(n % s_BI_DB); + int cbs = (int)(s_BI_DB - bs); + int bm = ((int)1 << bs) - 1; + r_array[0] = this_array[ds] >> bs; + for (int i = ds + 1; i < _t; ++i) + { + r_array[i - ds - 1] |= (this_array[i] & bm) << cbs; + r_array[i - ds] = this_array[i] >> bs; + } + if (bs > 0) r_array[(int)_t - ds - 1] |= ((int)_s & bm) << cbs; + r._t = _t - (int)ds; + r.clamp(); + } + + // (protected) r = this - a + private void subTo(BigInteger a, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + var a_array = a._array; + int i = 0; int c = 0; var m = Math.Min(a._t, _t); + while (i < m) + { + c += (int)this_array[i] - (int)a_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + if (a._t < _t) + { + c -= a._s; + while (i < _t) + { + c += (int)this_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + c += _s; + } + else + { + c += _s; + while (i < a._t) + { + c -= (int)a_array[i]; + r_array[i++] = (int)c & s_BI_DM; + c >>= (int)s_BI_DB; + } + c -= a._s; + } + r._s = (c < 0) ? -1 : 0; + if (c < -1) r_array[i++] = (int)((int)s_BI_DV + c); + else if (c > 0) r_array[i++] = (int)c; + r._t = i; + r.clamp(); + } + + // (protected) r = this * a, r != this,a (HAC 14.12) + // "this" should be the larger one if appropriate. + private void multiplyTo(BigInteger a, BigInteger r) + { + var this_array = _array; + var r_array = r._array; + var x = this.abs(); var y = a.abs(); + var y_array = y._array; + + int i = (int)x._t; + r._t = (int)i + y._t; + while (--i >= 0) r_array[i] = 0; + for (i = 0; i < y._t; ++i) r_array[i + (int)x._t] = s_am(x, 0, y_array[i], r, (int)i, 0, (int)x._t); + r._s = 0; + r.clamp(); + if (_s != a._s) BigInteger.ZERO.subTo(r, r); + } + + // (protected) r = this^2, r != this (HAC 14.16) + private void squareTo(BigInteger r) + { + var x = this.abs(); + var x_array = x._array; + var r_array = r._array; + + int i = (int)(2 * x._t); + r._t = (int)i; + while (--i >= 0) r_array[i] = 0; + for (i = 0; i < x._t - 1; ++i) + { + var c = s_am(x, (int)i, x_array[i], r, (int)(2 * i), 0, 1); + if ((r_array[(int)i + x._t] += s_am(x, (int)(i + 1), 2 * x_array[i], r, (int)(2 * i + 1), c, (int)x._t - i - 1)) >= s_BI_DV) + { + r_array[(int)i + x._t] -= s_BI_DV; + r_array[(int)i + x._t + 1] = 1; + } + } + if (r._t > 0) r_array[r._t - 1] += s_am(x, (int)i, x_array[i], r, (int)(2 * i), 0, 1); + r._s = 0; + r.clamp(); + } + + // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20) + // r != q, this != m. q or r may be null. + private void divRemTo(BigInteger m, BigInteger q, BigInteger r) + { +#if TRACING + this.PrintArray("this"); +#endif + var pm = m.abs(); + if (pm._t <= 0) return; + var pt = this.abs(); +#if TRACING + pt.PrintArray("pt"); +#endif + if (pt._t < pm._t) + { + if (q != null) q.fromInt(0); + if (r != null) this.copyTo(r); + return; + } + if (r == null) r = nbi(); + var y = nbi(); var ts = _s; var ms = m._s; + var pm_array = pm._array; + int nsh = s_BI_DB - (int)nbits(pm_array[pm._t - 1]); // normalize modulus + if (nsh > 0) { pm.lShiftTo(nsh, y); pt.lShiftTo(nsh, r); } + else { pm.copyTo(y); pt.copyTo(r); } + int ys = y._t; + + var y_array = y._array; + double y0 = (double)y_array[ys - 1]; + if (y0 == 0) return; + double yt = (y0 * (double)((int)1 << s_BI_F1) + ((ys > 1) ? y_array[ys - 2] >> s_BI_F2 : 0)); + double d1 = ((double)s_BI_FV) / yt; + double d2 = ((double)(1 << s_BI_F1)) / yt; + var e = 1 << s_BI_F2; + int i = (int)r._t; int j = i - (int)ys; var t = (q == null) ? nbi() : q; + y.dLShiftTo(j, t); + +#if TRACING + Console.WriteLine("y is"); + for (int kk = 0; kk < y.array.Count; kk++) + Console.WriteLine("{0}", y.array[kk]); +#endif + + var r_array = r._array; + if (r.compareTo(t) >= 0) + { + r_array[r._t++] = 1; + r.subTo(t, r); + } + BigInteger.ONE.dLShiftTo((int)ys, t); + t.subTo(y, y); // "negative" y so we can replace sub with am later + while (y._t < ys) y_array[y._t++] = 0; + while (--j >= 0) + { + // Estimate quotient digit + int qd = (r_array[--i] == y0) ? s_BI_DM : + (int)Math.Floor((double)r_array[i] * d1 + ((double)(r_array[i - 1] + e)) * d2); + if ((r_array[i] += s_am(y, 0, qd, r, (int)j, 0, (int)ys)) < qd) + { // Try it out + y.dLShiftTo(j, t); + r.subTo(t, r); + while (r_array[i] < --qd) r.subTo(t, r); + } + } + if (q != null) + { + r.dRShiftTo((int)ys, q); + if (ts != ms) BigInteger.ZERO.subTo(q, q); + } + r._t = (int)ys; + r.clamp(); + if (nsh > 0) r.rShiftTo(nsh, r); // Denormalize remainder + if (ts < 0) BigInteger.ZERO.subTo(r, r); + } + + // (public) this mod a + public BigInteger mod(BigInteger a) + { + var r = nbi(); + this.abs().divRemTo(a, null, r); + if (_s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r, r); + return r; + } + + // Modular reduction using "classic" algorithm + public class ClassicReducer : Reducer + { + private BigInteger _m; + + public ClassicReducer(BigInteger m) { _m = m; } + + public void reduce(BigInteger x) { x.divRemTo(_m, null, x); } + + public override BigInteger convert(BigInteger x) + { + if (x._s < 0 || x.compareTo(_m) >= 0) return x.mod(_m); + else return x; + } + + public override BigInteger revert(BigInteger x) { return x; } + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); this.reduce(r); } + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + } + + // (protected) return "-1/this % 2^DB"; useful for Mont. reduction + // justification: + // xy == 1 (mod m) + // xy = 1+km + // xy(2-xy) = (1+km)(1-km) + // x[y(2-xy)] = 1-k^2m^2 + // x[y(2-xy)] == 1 (mod m^2) + // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 + // should reduce x and y(2-xy) by m^2 at each step to keep size bounded. + // JS multiply "overflows" differently from C/C++, so care is needed here. + private int invDigit() + { + var this_array = _array; + if (_t < 1) return 0; + int x = (int)this_array[0]; + if ((x & 1) == 0) return 0; + int y = x & 3; // y == 1/x mod 2^2 + y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4 + y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8 + y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16 + // last step - calculate inverse mod DV directly; + // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints + y = (y * (2 - x * y % (int)s_BI_DV)) % (int)s_BI_DV; // y == 1/x mod 2^dbits + // we really want the negative inverse, and -DV < y < DV + return (y > 0) ? (int)s_BI_DV - y : -y; + } + + public abstract class Reducer + { + abstract public BigInteger convert(BigInteger x); + abstract public BigInteger revert(BigInteger x); + // DELETEME + // abstract public void reduce(BigInteger x); + abstract public void sqrTo(BigInteger x, BigInteger r); + abstract public void mulTo(BigInteger x, BigInteger y, BigInteger r); + }; + + private class MontgomeryReducer : Reducer + { + private BigInteger _m; + private int _mp; + private int _mpl; + private int _mph; + private int _um; + private int _mt2; + + public MontgomeryReducer(BigInteger m) + { + _m = m; + _mp = m.invDigit(); + _mpl = _mp & 0x7fff; + _mph = _mp >> 15; + _um = (1 << (s_BI_DB - 15)) - 1; + _mt2 = 2 * m._t; + } + + // xR mod m + public override BigInteger convert(BigInteger x) + { + var r = nbi(); + x.abs().dLShiftTo(_m._t, r); + r.divRemTo(_m, null, r); + if (x._s < 0 && r.compareTo(BigInteger.ZERO) > 0) _m.subTo(r, r); + return r; + } + + public override BigInteger revert(BigInteger x) + { + var r = nbi(); + x.copyTo(r); + this.reduce(r); + return r; + } + + // x = x/R mod m (HAC 14.32) + public void reduce(BigInteger x) + { + var x_array = x._array; + while (x._t <= _mt2) // pad x so am has enough room later + x_array[x._t++] = 0; + for (var i = 0; i < _m._t; ++i) + { + // faster way of calculating u0 = x[i]*mp mod DV + var j = x_array[i] & 0x7fff; + var u0 = (j * _mpl + (((j * _mph + (x_array[i] >> 15) * _mpl) & _um) << 15)) & s_BI_DM; + // use am to combine the multiply-shift-add into one call + j = i + _m._t; + x_array[j] += s_am(_m, 0, u0, x, i, 0, _m._t); + // propagate carry + while (x_array[j] >= s_BI_DV) { x_array[j] -= s_BI_DV; x_array[++j]++; } + } + x.clamp(); + x.dRShiftTo(_m._t, x); + if (x.compareTo(_m) >= 0) x.subTo(_m, x); + } + + // r = "x^2/R mod m"; x != r + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + + // r = "xy/R mod m"; x,y != r + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) + { + x.multiplyTo(y, r); this.reduce(r); + } + } + + + // (protected) true iff this is even + private bool isEven() + { + var this_array = _array; + return ((_t > 0) ? (int)(this_array[0] & 1) : _s) == 0; + } + + // (protected) this^e, e < 2^32, doing sqr and mul with "z" (HAC 14.79) + private BigInteger exp(uint e, Reducer z) + { + if (e > 0xffffffff || e < 1) return BigInteger.ONE; + var r = nbi(); var r2 = nbi(); var g = z.convert(this); int i = (int)nbits((int)e) - 1; + g.copyTo(r); + while (--i >= 0) + { + z.sqrTo(r, r2); + if ((e & (1 << i)) > 0) z.mulTo(r2, g, r); + else { var t = r; r = r2; r2 = t; } + } + return z.revert(r); + } + + // (public) this^e % m, 0 <= e < 2^32 + public BigInteger modPowInt(uint e, BigInteger m) + { + Reducer z; + if (e < 256 || m.isEven()) z = new ClassicReducer(m); else z = new MontgomeryReducer(m); + return this.exp(e, z); + } + + // "constants" + public static BigInteger ZERO = nbv(0); + public static BigInteger ONE = nbv(1); + + // Copyright (c) 2005 Tom Wu + // All Rights Reserved. + // See "LICENSE" for details. + + // Extended JavaScript BN functions, required for RSA private ops. + + // (public) + public BigInteger clone() { var r = nbi(); this.copyTo(r); return r; } + + // (public) return value as integer + public int intValue() + { + var this_array = _array; + if (_s < 0) + { + if (_t == 1) return (int)this_array[0] - (int)s_BI_DV; + else if (_t == 0) return -1; + } + else if (_t == 1) return (int)this_array[0]; + else if (_t == 0) return 0; + // assumes 16 < DB < 32 + // return ((this_array[1]&((1<<(32-BI_DB))-1))<> 24); + } + + // (public) return value as short (assumes DB>=16) + public ushort shortValue() + { + var this_array = _array; + return (_t == 0) ? (ushort)_s : (ushort)((this_array[0] << 16) >> 16); + } + + private static double s_LN2 = Math.Log(2.0); + + // (protected) return x s.t. r^x < DV + private int chunkSize(int r) { return (int)Math.Floor(s_LN2 * (double)s_BI_DB / Math.Log(r)); } + + // (public) 0 if this == 0, 1 if this > 0 + public int signum() + { + var this_array = _array; + if (_s < 0) return -1; + else if (_t <= 0 || (_t == 1 && this_array[0] <= 0)) return 0; + else return 1; + } + + private static String s_sdigits = "0123456789abcdefghijklmnopqrstuvwxyz"; + + private static String IntToString(int i, int radix) + { + if (radix == 10) + { + return i.ToString(); + } + else if (radix == 16) + { + return i.ToString("X"); + } + else + { + bool neg = false; + if (i < 0) + { + neg = true; i = -i; + } + String res = ""; + while (i != 0) + { + int digit = i % radix; + res = s_sdigits.Substring(digit, 1) + res; + i = i / radix; + } + if (neg) res = "-" + res; + return res; + } + } + + // (protected) convert to radix string + public String toRadix(int b) + { + // if (b == null) b = 10; + if (this.signum() == 0 || b < 2 || b > 36) return "0"; + var cs = this.chunkSize(b); + var a = (int)Math.Pow((double)b, (double)cs); + Console.WriteLine("a = {0}.", a); + var d = nbv(a); var y = nbi(); var z = nbi(); var r = ""; + Console.WriteLine("d.intValue = {0}.", d.intValue()); + this.divRemTo(d, y, z); + Console.WriteLine("y.signum = {0}", y.signum()); + Console.WriteLine("z.intValue = " + z.intValue()); + while (y.signum() > 0) + { + r = IntToString(a + z.intValue(), (int)b).Substring(1) + r; + y.divRemTo(d, y, z); + Console.WriteLine("y.signum = {0}", y.signum()); + Console.WriteLine("z.intValue = " + z.intValue()); + } + return IntToString(z.intValue(), (int)b) + r; + } + + private static int IntPow(int n, int p) + { + int res = 1; + for (int k = 1; k < p; k++) + { + res *= n; + } + return res; + } + + // (protected) convert from radix string + private void fromRadix(String s, int b) + { + this.fromInt(0); + var cs = this.chunkSize(b); + var d = IntPow(b, cs); bool mi = false; int j = 0; int w = 0; + for (int i = 0; i < s.Length; ++i) + { + int x = intAt(s, i); + if (x < 0) + { + if (s[(int)i] == '-' && this.signum() == 0) mi = true; + continue; + } + w = b * w + (int)x; + if (++j >= cs) + { + this.dMultiply(d); + this.dAddOffset(w, 0); + j = 0; + w = 0; + } + } + if (j > 0) + { + this.dMultiply(IntPow(b, j)); + this.dAddOffset(w, 0); + } + if (mi) BigInteger.ZERO.subTo(this, this); + } + + // (protected) alternate constructor + private void fromNumber(int a, int b, SecureRandom c) + { + if (a < 2) this.fromInt(1); + else + { + this.fromNumber(a, c); + if (!this.testBit(a - 1)) // force MSB set + this.bitwiseTo(BigInteger.ONE.shiftLeft((int)a - 1), op_or, this); + if (this.isEven()) this.dAddOffset(1, 0); // force odd + while (!this.isProbablePrime(b)) + { + this.dAddOffset(2, 0); + if (this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft((int)a - 1), this); + } + } + } + + private void fromNumber(int a, SecureRandom b) + { + // new BigInteger(int,RNG) + byte[] x = new byte[(a >> 3) + 1]; + int t = (int)a & 7; + b.nextBytes(x); + if (t > 0) + x[0] &= (byte)((1 << (int)t) - 1); + else + x[0] = 0; + this.fromByteArray(x); + } + + // (public) convert to bigendian byte array + public byte[] toByteArray() + { + var this_array = _array; + int i = (int)_t; var r = new ListX(); + r[0] = (byte)_s; + int p = (int)s_BI_DB - (i * (int)s_BI_DB) % 8; + int d; int k = 0; + if (i-- > 0) + { + if (p < s_BI_DB && (d = this_array[i] >> p) != (_s & s_BI_DM) >> p) + r[k++] = (byte)(d | ((int)_s << (int)(s_BI_DB - p))); + while (i >= 0) + { + if (p < 8) + { + d = (this_array[i] & (((int)1 << p) - 1)) << (8 - p); + d |= this_array[--i] >> (p += s_BI_DB - 8); + } + else + { + d = (this_array[i] >> (p -= 8)) & 0xff; + if (p <= 0) { p += s_BI_DB; --i; } + } + if ((d & 0x80) != 0) d = (int)((int)d | -256); + if (k == 0 && (_s & 0x80) != (d & 0x80)) ++k; + if (k > 0 || d != _s) r[k++] = (byte)d; + } + } + return r.ToArray(); + } + + public bool Equals(BigInteger a) { return (this.compareTo(a) == 0); } + public BigInteger min(BigInteger a) { return (this.compareTo(a) < 0) ? this : a; } + public BigInteger max(BigInteger a) { return (this.compareTo(a) > 0) ? this : a; } + + // (protected) r = this op a (bitwise) + public delegate int BinOpInt(int x1, int x2); + + private void bitwiseTo(BigInteger a, BinOpInt op, BigInteger r) + { + var this_array = _array; + var a_array = a._array; + var r_array = r._array; + var m = Math.Min(a._t, _t); + for (int i = 0; i < m; ++i) r_array[i] = op(this_array[i], a_array[i]); + int f; + if (a._t < _t) + { + f = (int)a._s & s_BI_DM; + for (int i = m; i < _t; ++i) r_array[i] = op(this_array[i], f); + r._t = _t; + } + else + { + f = (int)_s & s_BI_DM; + for (int i = m; i < a._t; ++i) r_array[i] = op(f, a_array[i]); + r._t = a._t; + } + r._s = (int)op((int)_s, (int)a._s); + r.clamp(); + } + + // (public) this & a + private static int op_and(int x, int y) { return x & y; } + public BigInteger and(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_and, r); return r; } + + // (public) this | a + private static int op_or(int x, int y) { return x | y; } + public BigInteger or(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_or, r); return r; } + + // (public) this ^ a + private static int op_xor(int x, int y) { return x ^ y; } + public BigInteger xor(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_xor, r); return r; } + + // (public) this & ~a + private static int op_andnot(int x, int y) { return x & ~y; } + public BigInteger andNot(BigInteger a) { var r = nbi(); this.bitwiseTo(a, op_andnot, r); return r; } + + // (public) ~this + public BigInteger not() + { + var this_array = _array; + var r = nbi(); + var r_array = r._array; + + for (var i = 0; i < _t; ++i) r_array[i] = s_BI_DM & ~this_array[i]; + r._t = _t; + r._s = ~_s; + return r; + } + + // (public) this << n + public BigInteger shiftLeft(int n) + { + var r = nbi(); + if (n < 0) this.rShiftTo(-n, r); else this.lShiftTo(n, r); + return r; + } + + // (public) this >> n + public BigInteger shiftRight(int n) + { + var r = nbi(); + if (n < 0) this.lShiftTo(-n, r); else this.rShiftTo(n, r); + return r; + } + + // return index of lowest 1-bit in x, x < 2^31 (-1 for no set bits) + public static int lbit(int x) + { + if (x == 0) return -1; + int r = 0; + if ((x & 0xffff) == 0) { x >>= 16; r += 16; } + if ((x & 0xff) == 0) { x >>= 8; r += 8; } + if ((x & 0xf) == 0) { x >>= 4; r += 4; } + if ((x & 3) == 0) { x >>= 2; r += 2; } + if ((x & 1) == 0) ++r; + return r; + } + + // (public) returns index of lowest 1-bit (or -1 if none) + public int getLowestSetBit() + { + var this_array = _array; + for (var i = 0; i < _t; ++i) + if (this_array[i] != 0) return i * s_BI_DB + lbit(this_array[i]); + if (_s < 0) return (int)_t * s_BI_DB; + return -1; + } + + // return number of 1 bits in x + private static int cbit(int x) + { + int r = 0; + while (x != 0) { x &= x - 1; ++r; } + return r; + } + + // (public) return number of set bits + public int bitCount() + { + int r = 0; + int x = (int)_s & s_BI_DM; + for (int i = 0; i < _t; ++i) r += cbit(_array[i] ^ x); + return r; + } + + // (public) true iff nth bit is set + public bool testBit(int n) + { + var this_array = _array; + int j = n / (int)s_BI_DB; + if (j >= _t) return (_s != 0); + return ((this_array[j] & ((int)1 << (int)(n % s_BI_DB))) != 0); + } + + // (protected) this op (1<>= s_BI_DB; + } + if (a._t < _t) + { + c += (int)a._s; + while (i < _t) + { + c += this_array[i]; + r_array[i++] = c & s_BI_DM; + c >>= s_BI_DB; + } + c += (int)_s; + } + else + { + c += (int)_s; + while (i < a._t) + { + c += a_array[i]; + r_array[i++] = c & s_BI_DM; + c >>= s_BI_DB; + } + c += (int)a._s; + } + r._s = (c < 0) ? -1 : 0; + if (c > 0) r_array[i++] = c; + else if (c < -1) r_array[i++] = s_BI_DV + c; + r._t = i; + r.clamp(); + } + + // (public) this + a + public BigInteger add(BigInteger a) { var r = nbi(); this.addTo(a, r); return r; } + + // (public) this - a + public BigInteger subtract(BigInteger a) { var r = nbi(); this.subTo(a, r); return r; } + + // (public) this * a + public BigInteger multiply(BigInteger a) { var r = nbi(); this.multiplyTo(a, r); return r; } + + // (public) this / a + public BigInteger divide(BigInteger a) { var r = nbi(); this.divRemTo(a, r, null); return r; } + + // (public) this % a + public BigInteger remainder(BigInteger a) { var r = nbi(); this.divRemTo(a, null, r); return r; } + + public struct BigIntPair + { + public BigInteger p1; + public BigInteger p2; + public BigIntPair(BigInteger p1, BigInteger p2) { this.p1 = p1; this.p2 = p2; } + } + // (public) [this/a,this%a] + public BigIntPair divideAndRemainder(BigInteger a) + { + var q = nbi(); var r = nbi(); + this.divRemTo(a, q, r); + return new BigIntPair(q, r); + } + + // (protected) this *= n, this >= 0, 1 < n < DV + private void dMultiply(int n) + { + var this_array = _array; + this_array[_t] = s_am(this, 0, n - 1, this, 0, 0, _t); + ++_t; + this.clamp(); + } + + // (protected) this += n << w words, this >= 0 + private void dAddOffset(int n, int w) + { + var this_array = _array; + while (_t <= w) this_array[_t++] = 0; + this_array[w] += n; + while (this_array[w] >= s_BI_DV) + { + this_array[w] -= s_BI_DV; + if (++w >= _t) this_array[_t++] = 0; + ++this_array[w]; + } + } + + private class NullReducer : Reducer + { + public NullReducer() { } + + + public override BigInteger convert(BigInteger x) { return x; } + public override BigInteger revert(BigInteger x) { return x; } + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); } + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); } + } + + // (public) this^e + // public BigInteger pow(BigInteger e) { return this.exp(e,new NullReducer()); } + + // (protected) r = lower n words of "this * a", a.t <= n + // "this" should be the larger one if appropriate. + private void multiplyLowerTo(BigInteger a, int n, BigInteger r) + { + var r_array = r._array; + var a_array = a._array; + var i = Math.Min(_t + a._t, n); + r._s = 0; // assumes a,this >= 0 + r._t = i; + while (i > 0) r_array[--i] = 0; + for (int j = r._t - _t; i < j; ++i) r_array[i + _t] = s_am(this, 0, a_array[i], r, i, 0, _t); + for (int j = Math.Min(a._t, n); i < j; ++i) s_am(this, 0, a_array[i], r, i, 0, n - i); + r.clamp(); + } + + // (protected) r = "this * a" without lower n words, n > 0 + // "this" should be the larger one if appropriate. + public void multiplyUpperTo(BigInteger a, int n, BigInteger r) + { + var r_array = r._array; + var a_array = a._array; + --n; + int i = r._t = _t + a._t - n; + r._s = 0; // assumes a,this >= 0 + while (--i >= 0) r_array[i] = 0; + for (i = Math.Max(n - _t, 0); i < a._t; ++i) + r_array[_t + i - n] = s_am(this, n - i, a_array[i], r, 0, 0, _t + i - n); + r.clamp(); + r.dRShiftTo(1, r); + } + + // Barrett modular reduction + public class BarrettReducer : Reducer + { + private BigInteger _r2; + private BigInteger _q3; + private BigInteger _mu; + private BigInteger _m; + + public BarrettReducer(BigInteger m) + { + // setup Barrett + _r2 = nbi(); + _q3 = nbi(); + BigInteger.ONE.dLShiftTo(2 * m._t, _r2); + _mu = _r2.divide(m); + _m = m; + } + + public override BigInteger convert(BigInteger x) + { + if (x._s < 0 || x._t > 2 * _m._t) return x.mod(_m); + else if (x.compareTo(_m) < 0) return x; + else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; } + } + + public override BigInteger revert(BigInteger x) { return x; } + + // x = x mod m (HAC 14.42) + public void reduce(BigInteger x) + { + x.dRShiftTo(_m._t - 1, _r2); + if (x._t > _m._t + 1) { x._t = _m._t + 1; x.clamp(); } + _mu.multiplyUpperTo(_r2, _m._t + 1, _q3); + _m.multiplyLowerTo(_q3, _m._t + 1, _r2); + while (x.compareTo(_r2) < 0) x.dAddOffset(1, _m._t + 1); + x.subTo(_r2, x); + while (x.compareTo(_m) >= 0) x.subTo(_m, x); + } + + // r = x^2 mod m; x != r + public override void sqrTo(BigInteger x, BigInteger r) { x.squareTo(r); this.reduce(r); } + + // r = x*y mod m; x,y != r + public override void mulTo(BigInteger x, BigInteger y, BigInteger r) { x.multiplyTo(y, r); this.reduce(r); } + } + + // (public) this^e % m (HAC 14.85) + public BigInteger modPow(BigInteger e, BigInteger m) + { + var e_array = e._array; + var i = e.bitLength(); int k; BigInteger r = nbv(1); Reducer z; + if (i <= 0) return r; + else if (i < 18) k = 1; + else if (i < 48) k = 3; + else if (i < 144) k = 4; + else if (i < 768) k = 5; + else k = 6; + if (i < 8) + z = new ClassicReducer(m); + else if (m.isEven()) + z = new BarrettReducer(m); + else + z = new MontgomeryReducer(m); + + // precomputation + var g = new ListX(); + int n = 3; + int k1 = k - 1; + int km = (1 << k) - 1; + g[1] = z.convert(this); + if (k > 1) + { + var g2 = nbi(); + z.sqrTo(g[1], g2); + while (n <= km) + { + g[n] = nbi(); + z.mulTo(g2, g[n - 2], g[n]); + n += 2; + } + } + + int j = e._t - 1; int w; bool is1 = true; BigInteger r2 = nbi(); BigInteger t; + i = nbits(e_array[j]) - 1; + while (j >= 0) + { + if (i >= k1) w = (e_array[j] >> (i - k1)) & km; + else + { + w = (e_array[j] & ((1 << (i + 1)) - 1)) << (k1 - i); + if (j > 0) w |= e_array[j - 1] >> (s_BI_DB + i - k1); + } + + n = k; + while ((w & 1) == 0) { w >>= 1; --n; } + if ((i -= n) < 0) { i += s_BI_DB; --j; } + if (is1) + { // ret == 1, don't bother squaring or multiplying it + g[w].copyTo(r); + is1 = false; + } + else + { + while (n > 1) { z.sqrTo(r, r2); z.sqrTo(r2, r); n -= 2; } + if (n > 0) z.sqrTo(r, r2); else { t = r; r = r2; r2 = t; } + z.mulTo(r2, g[w], r); + } + + while (j >= 0 && (e_array[j] & (1 << i)) == 0) + { + z.sqrTo(r, r2); t = r; r = r2; r2 = t; + if (--i < 0) { i = s_BI_DB - 1; --j; } + } + } + return z.revert(r); + } + + // (public) gcd(this,a) (HAC 14.54) + public BigInteger gcd(BigInteger a) + { + var x = (_s < 0) ? this.negate() : this.clone(); + var y = (a._s < 0) ? a.negate() : a.clone(); + if (x.compareTo(y) < 0) { var t = x; x = y; y = t; } + var i = x.getLowestSetBit(); var g = y.getLowestSetBit(); + if (g < 0) return x; + if (i < g) g = i; + if (g > 0) + { + x.rShiftTo(g, x); + y.rShiftTo(g, y); + } + while (x.signum() > 0) + { + if ((i = x.getLowestSetBit()) > 0) x.rShiftTo(i, x); + if ((i = y.getLowestSetBit()) > 0) y.rShiftTo(i, y); + if (x.compareTo(y) >= 0) + { + x.subTo(y, x); + x.rShiftTo(1, x); + } + else + { + y.subTo(x, y); + y.rShiftTo(1, y); + } + } + if (g > 0) y.lShiftTo(g, y); + return y; + } + + // (protected) this % n, n < 2^26 + private int modInt(int n) + { + var this_array = _array; + if (n <= 0) return 0; + var d = s_BI_DV % n; int r = (_s < 0) ? n - 1 : 0; + if (_t > 0) + if (d == 0) r = this_array[0] % n; + else for (var i = _t - 1; i >= 0; --i) r = (d * r + this_array[i]) % n; + return r; + } + + // (public) 1/this % m (HAC 14.61) + public BigInteger modInverse(BigInteger m) + { + var ac = m.isEven(); + if ((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO; + var u = m.clone(); var v = this.clone(); + var a = nbv(1); var b = nbv(0); var c = nbv(0); var d = nbv(1); + while (u.signum() != 0) + { + while (u.isEven()) + { + u.rShiftTo(1, u); + if (ac) + { + if (!a.isEven() || !b.isEven()) { a.addTo(this, a); b.subTo(m, b); } + a.rShiftTo(1, a); + } + else if (!b.isEven()) b.subTo(m, b); + b.rShiftTo(1, b); + } + while (v.isEven()) + { + v.rShiftTo(1, v); + if (ac) + { + if (!c.isEven() || !d.isEven()) { c.addTo(this, c); d.subTo(m, d); } + c.rShiftTo(1, c); + } + else if (!d.isEven()) d.subTo(m, d); + d.rShiftTo(1, d); + } + if (u.compareTo(v) >= 0) + { + u.subTo(v, u); + if (ac) a.subTo(c, a); + b.subTo(d, b); + } + else + { + v.subTo(u, v); + if (ac) c.subTo(a, c); + d.subTo(b, d); + } + } + if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO; + if (d.compareTo(m) >= 0) return d.subtract(m); + if (d.signum() < 0) d.addTo(m, d); else return d; + if (d.signum() < 0) return d.add(m); else return d; + } + + private static int[] s_lowprimes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 }; + private static int s_lplim = (1 << 26) / s_lowprimes[s_lowprimes.Length - 1]; + + // (public) test primality with certainty >= 1-.5^t + public bool isProbablePrime(int t) + { + int i; var x = this.abs(); + var x_array = x._array; + if (x._t == 1 && x_array[0] <= s_lowprimes[s_lowprimes.Length - 1]) + { + for (i = 0; i < s_lowprimes.Length; ++i) + if (x_array[0] == s_lowprimes[i]) return true; + return false; + } + if (x.isEven()) return false; + i = 1; + while (i < s_lowprimes.Length) + { + var m = s_lowprimes[i]; var j = i + 1; + while (j < s_lowprimes.Length && m < s_lplim) m *= s_lowprimes[j++]; + m = x.modInt(m); + while (i < j) if (m % s_lowprimes[i++] == 0) return false; + } + return x.millerRabin(t); + } + + // (protected) true if probably prime (HAC 4.24, Miller-Rabin) + private bool millerRabin(int t) + { + var n1 = this.subtract(BigInteger.ONE); + var k = n1.getLowestSetBit(); + if (k <= 0) return false; + var r = n1.shiftRight(k); + t = (t + 1) >> 1; + if (t > s_lowprimes.Length) t = s_lowprimes.Length; + var a = nbi(); + for (var i = 0; i < t; ++i) + { + a.fromInt(s_lowprimes[i]); + var y = a.modPow(r, this); + if (y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) + { + var j = 1; + while (j++ < k && y.compareTo(n1) != 0) + { + y = y.modPowInt(2, this); + if (y.compareTo(BigInteger.ONE) == 0) return false; + } + if (y.compareTo(n1) != 0) return false; + } + } + return true; + } + + public void PrintArray(String nm) + { + for (int kk = 0; kk < _array.Count; kk++) Console.WriteLine(" {0}.array[{1}] = {2}", nm, kk, _array[kk]); + } + + // BigInteger interfaces not implemented in jsbn: + + // BigInteger(int signum, byte[] magnitude) + // double doubleValue() + // float floatValue() + // int hashCode() + // long longValue() + // static BigInteger valueOf(long val) + // prng4.js - uses Arcfour as a PRNG + } + + internal abstract class RNG + { + abstract public void init(int[] key); + abstract public int next(); + } + + internal class Arcfour : RNG + { + private int _i; + private int _j; + private int[] _S; + + public Arcfour() + { + _i = 0; + _j = 0; + _S = new int[256]; + } + + // Initialize arcfour context from key, an array of ints, each from [0..255] + public override void init(int[] key) + { + for (int i = 0; i < 256; ++i) + _S[i] = i; + int j = 0; + for (int i = 0; i < 256; ++i) + { + j = (j + _S[i] + key[i % key.Length]) & 255; + int t = _S[i]; + _S[i] = _S[j]; + _S[j] = t; + } + _i = 0; + _j = 0; + } + + public override int next() + { + _i = (_i + 1) & 255; + _j = (_j + _S[_i]) & 255; + int t = _S[_i]; + _S[_i] = _S[_j]; + _S[_j] = t; + return _S[(t + _S[_i]) & 255]; + } + } + + internal class SecureRandom + { + // Pool size must be a multiple of 4 and greater than 32. + // An array of bytes the size of the pool will be passed to init() + private const int rng_psize = 256; + + // Random number generator - requires a PRNG backend, e.g. prng4.js + + // For best results, put code like + // + // in your main HTML document. + + private RNG _rng_state; + private int[] _rng_pool; + private int _rng_pptr; + + public SecureRandom() + { + _rng_pool = new int[rng_psize]; + _rng_pptr = 0; +#if USE_RANDOM_SEED + Random rnd = new Random(); +#endif + while (_rng_pptr < rng_psize) + { // extract some randomness from Math.random() +#if USE_RANDOM_SEED + int t = (int)Math.Floor(65536.0 * rnd.NextDouble()); +#else + int t = 1000; +#endif + _rng_pool[_rng_pptr++] = (int)((uint)t >> 8); + _rng_pool[_rng_pptr++] = t & 255; + } + _rng_pptr = 0; + rng_seed_time(); + } + + // Mix in a 32-bit integer into the pool + private void rng_seed_int(int x) + { + _rng_pool[_rng_pptr++] ^= x & 255; + _rng_pool[_rng_pptr++] ^= (x >> 8) & 255; + _rng_pool[_rng_pptr++] ^= (x >> 16) & 255; + _rng_pool[_rng_pptr++] ^= (x >> 24) & 255; + if (_rng_pptr >= rng_psize) _rng_pptr -= rng_psize; + } + + // Mix in the current time (w/milliseconds) into the pool + private void rng_seed_time() + { +#if USE_RANDOM_SEED + rng_seed_int((int)(new DateTime().Ticks)); +#endif + } + + + // Plug in your RNG constructor here + private RNG prng_newstate() + { + return new Arcfour(); + } + + private byte rng_get_byte() + { + if (_rng_state == null) + { + rng_seed_time(); + _rng_state = prng_newstate(); + _rng_state.init(_rng_pool); + for (_rng_pptr = 0; _rng_pptr < _rng_pool.Length; ++_rng_pptr) + _rng_pool[_rng_pptr] = 0; + _rng_pptr = 0; + //rng_pool = null; + } + // TODO: allow reseeding after first request + return (byte)_rng_state.next(); + } + + public void nextBytes(byte[] ba) + { + for (int i = 0; i < ba.Length; ++i) ba[i] = rng_get_byte(); + } + } + + internal class RSAKey + { + private BigInteger _n; + private int _e; + private BigInteger _d; + private BigInteger _p; + private BigInteger _q; + private BigInteger _dmp1; + private BigInteger _dmq1; + private BigInteger _coeff; + + // "empty" RSA key constructor + public RSAKey() + { + _n = null; + _e = 0; + _d = null; + _p = null; + _q = null; + _dmp1 = null; + _dmq1 = null; + _coeff = null; + } + + // convert a (hex) string to a bignum object + private static BigInteger parseBigInt(String str, int r) + { + return new BigInteger(str, r); + } + + private static String linebrk(String s, int n) + { + var ret = ""; + var i = 0; + while (i + n < s.Length) + { + ret += s.Substring(i, i + n) + "\n"; + i += n; + } + return ret + s.Substring(i, s.Length); + } + + private static String byte2Hex(byte b) + { + if (b < 0x10) + return "0" + b.ToString("X"); + else + return b.ToString("X"); + } + + // PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint + private static BigInteger pkcs1pad2(String s, int n) + { + if (n < s.Length + 11) + { + throw new ArgumentException("Message too long for RSA"); + } + var ba = new byte[n]; + var i = s.Length - 1; + while (i >= 0 && n > 0) ba[--n] = (byte)s[i--]; + ba[--n] = 0; + var rng = new SecureRandom(); + byte[] x = new byte[1]; + while (n > 2) + { // random non-zero pad + x[0] = 0; + while (x[0] == 0) rng.nextBytes(x); + ba[--n] = x[0]; + } + ba[--n] = 2; + ba[--n] = 0; + // for (int k = 0; k < ba.Length; k++) Console.WriteLine("ba[{0}] = {1}", k, (int)ba[k]); + return new BigInteger(ba); + } + + // Set the public key fields N and e from hex strings + public void setPublic(String N, String E) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + } + else + throw new ArgumentException("Invalid RSA public key"); + } + + // Perform raw public operation on "x": return x^e (mod n) + private BigInteger doPublic(BigInteger x) + { + return x.modPowInt((uint)_e, _n); + } + + // Return the PKCS#1 RSA encryption of "text" as an even-length hex string + public String encrypt(String text) + { + var m = pkcs1pad2(text, (_n.bitLength() + 7) >> 3); +#if TRACING + m.PrintArray("m"); + Console.WriteLine(m.toString(10)); +#endif + if (m == null) return null; + var c = this.doPublic(m); + if (c == null) return null; + var h = c.toString(16); + if ((h.Length & 1) == 0) return h; else return "0" + h; + } + + // Return the PKCS#1 RSA encryption of "text" as a Base64-encoded string + //function RSAEncryptB64(text) { + // var h = this.encrypt(text); + // if(h) return hex2b64(h); else return null; + //} + + // Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext + private String pkcs1unpad2(BigInteger d, int n) + { + var b = d.toByteArray(); + var i = 0; + while (i < b.Length && b[i] == 0) ++i; + if (b.Length - i != n - 1 || b[i] != 2) + return null; + ++i; + while (b[i] != 0) + if (++i >= b.Length) return null; + var ret = ""; + char[] oneChar = new char[1]; + while (++i < b.Length) + { + oneChar[0] = (char)b[i]; + ret += new String(oneChar); + } + return ret; + } + + // Set the private key fields N, e, and d from hex strings + private void setPrivate(String N, String E, String D) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + _d = parseBigInt(D, 16); + } + else + throw new ArgumentException("Invalid RSA private key"); + } + + // Set the private key fields N, e, d and CRT params from hex strings + public void setPrivateEx(String N, + String E, + String D, + String P, + String Q, + String DP, + String DQ, + String C) + { + if (N != null && E != null && N.Length > 0 && E.Length > 0) + { + _n = parseBigInt(N, 16); + _e = Int32.Parse(E, NumberStyles.HexNumber); + _d = parseBigInt(D, 16); + _p = parseBigInt(P, 16); + _q = parseBigInt(Q, 16); + _dmp1 = parseBigInt(DP, 16); + _dmq1 = parseBigInt(DQ, 16); + _coeff = parseBigInt(C, 16); + } + else + throw new ArgumentException("Invalid RSA private key"); + } + + // Generate a new random private key B bits long, using public expt E + private void generate(int B, String E) + { + var rng = new SecureRandom(); + var qs = B >> 1; + _e = Int32.Parse(E, NumberStyles.HexNumber); + var ee = new BigInteger(E, 16); + for (; ;) + { + for (; ;) + { + _p = new BigInteger(B - qs, 1, rng); + if (_p.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && _p.isProbablePrime(10)) break; + } + for (; ;) + { + _q = new BigInteger(qs, 1, rng); + if (_q.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && _q.isProbablePrime(10)) break; + } + if (_p.compareTo(_q) <= 0) + { + var t = _p; + _p = _q; + _q = t; + } + var p1 = _p.subtract(BigInteger.ONE); + var q1 = _q.subtract(BigInteger.ONE); + var phi = p1.multiply(q1); + if (phi.gcd(ee).compareTo(BigInteger.ONE) == 0) + { + _n = _p.multiply(_q); + _d = ee.modInverse(phi); + _dmp1 = _d.mod(p1); + _dmq1 = _d.mod(q1); + _coeff = _q.modInverse(_p); + break; + } + } + } + + // Perform raw private operation on "x": return x^d (mod n) + private BigInteger doPrivate(BigInteger x) + { + if (_p == null || _q == null) + return x.modPow(_d, _n); + + // TODO: re-calculate any missing CRT params + var xp = x.mod(_p).modPow(_dmp1, _p); + var xq = x.mod(_q).modPow(_dmq1, _q); + + while (xp.compareTo(xq) < 0) + xp = xp.add(_p); + return xp.subtract(xq).multiply(_coeff).mod(_p).multiply(_q).add(xq); + } + + // Return the PKCS#1 RSA decryption of "ctext". + // "ctext" is an even-length hex string and the output is a plain string. + public String decrypt(String ctext) + { + var c = parseBigInt(ctext, 16); + var m = this.doPrivate(c); + if (m == null) return null; + return pkcs1unpad2(m, (_n.bitLength() + 7) >> 3); + } + } +} + diff --git a/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.csproj b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.csproj new file mode 100644 index 0000000000..8849531764 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/Crypto/Crypto.csproj @@ -0,0 +1,45 @@ + + + + + Debug + AnyCPU + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + 7a9bfb7d + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.cs b/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.cs new file mode 100644 index 0000000000..746f6ef10b --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.cs @@ -0,0 +1,1060 @@ +/* + This is a Java implemention of the DeltaBlue algorithm described in: + "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" + by Bjorn N. Freeman-Benson and John Maloney + January 1990 Communications of the ACM, + also available as University of Washington TR 89-08-06. + + This implementation by Mario Wolczko, Sun Microsystems, Sep 1996, + based on the Smalltalk implementation by John Maloney. + +*/ + +// The code has been adapted for use as a C# benchmark by Microsoft. + +#define USE_STACK + +using Microsoft.Xunit.Performance; +using System; +using System.Collections; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +/* +Strengths are used to measure the relative importance of constraints. +New strengths may be inserted in the strength hierarchy without +disrupting current constraints. Strengths cannot be created outside +this class, so pointer comparison can be used for value comparison. +*/ + +internal class Strength +{ + private int _strengthValue; + private String _name; + + private Strength(int strengthValue, String name) + { + _strengthValue = strengthValue; + _name = name; + } + + public static Boolean stronger(Strength s1, Strength s2) + { + return s1._strengthValue < s2._strengthValue; + } + + public static Boolean weaker(Strength s1, Strength s2) + { + return s1._strengthValue > s2._strengthValue; + } + + public static Strength weakestOf(Strength s1, Strength s2) + { + return weaker(s1, s2) ? s1 : s2; + } + + public static Strength strongest(Strength s1, Strength s2) + { + return stronger(s1, s2) ? s1 : s2; + } + + // for iteration + public Strength nextWeaker() + { + switch (_strengthValue) + { + case 0: return weakest; + case 1: return weakDefault; + case 2: return normal; + case 3: return strongDefault; + case 4: return preferred; + case 5: return strongPreferred; + + case 6: + default: + Console.Error.WriteLine("Invalid call to nextStrength()!"); + //System.exit(1); + return null; + } + } + + // Strength constants + public static Strength required = new Strength(0, "required"); + public static Strength strongPreferred = new Strength(1, "strongPreferred"); + public static Strength preferred = new Strength(2, "preferred"); + public static Strength strongDefault = new Strength(3, "strongDefault"); + public static Strength normal = new Strength(4, "normal"); + public static Strength weakDefault = new Strength(5, "weakDefault"); + public static Strength weakest = new Strength(6, "weakest"); + + public void print() + { + Console.Write("strength[" + _strengthValue + "]"); + } +} + + + + +//------------------------------ variables ------------------------------ + +// I represent a constrained variable. In addition to my value, I +// maintain the structure of the constraint graph, the current +// dataflow graph, and various parameters of interest to the DeltaBlue +// incremental constraint solver. + +internal class Variable +{ + public int value; // my value; changed by constraints + public ArrayList constraints; // normal constraints that reference me + public Constraint determinedBy; // the constraint that currently determines + // my value (or null if there isn't one) + public int mark; // used by the planner to mark constraints + public Strength walkStrength; // my walkabout strength + public Boolean stay; // true if I am a planning-time constant + public String name; // a symbolic name for reporting purposes + + + private Variable(String name, int initialValue, Strength walkStrength, + int nconstraints) + { + value = initialValue; + constraints = new ArrayList(nconstraints); + determinedBy = null; + mark = 0; + this.walkStrength = walkStrength; + stay = true; + this.name = name; + } + + public Variable(String name, int value) : this(name, value, Strength.weakest, 2) + { + } + + public Variable(String name) : this(name, 0, Strength.weakest, 2) + { + } + + public void print() + { + Console.Write(name + "("); + walkStrength.print(); + Console.Write("," + value + ")"); + } + + // Add the given constraint to the set of all constraints that refer to me. + public void addConstraint(Constraint c) + { + constraints.Add(c); + } + + // Remove all traces of c from this variable. + public void removeConstraint(Constraint c) + { + constraints.Remove(c); + if (determinedBy == c) determinedBy = null; + } + + // Attempt to assign the given value to me using the given strength. + public void setValue(int value, Strength strength) + { + EditConstraint e = new EditConstraint(this, strength); + if (e.isSatisfied()) + { + this.value = value; + deltablue.planner.propagateFrom(this); + } + e.destroyConstraint(); + } +} + + + + +//------------------------ constraints ------------------------------------ + +// I am an abstract class representing a system-maintainable +// relationship (or "constraint") between a set of variables. I supply +// a strength instance variable; concrete subclasses provide a means +// of storing the constrained variables and other information required +// to represent a constraint. + +internal abstract class Constraint +{ + public Strength strength; // the strength of this constraint + + public Constraint() { } // this has to be here because of + // Java's constructor idiocy. + + public Constraint(Strength strength) + { + this.strength = strength; + } + + // Answer true if this constraint is satisfied in the current solution. + public abstract Boolean isSatisfied(); + + // Record the fact that I am unsatisfied. + public abstract void markUnsatisfied(); + + // Normal constraints are not input constraints. An input constraint + // is one that depends on external state, such as the mouse, the + // keyboard, a clock, or some arbitrary piece of imperative code. + public virtual Boolean isInput() { return false; } + + // Activate this constraint and attempt to satisfy it. + public void addConstraint() + { + addToGraph(); + deltablue.planner.incrementalAdd(this); + } + + // Deactivate this constraint, remove it from the constraint graph, + // possibly causing other constraints to be satisfied, and destroy + // it. + public void destroyConstraint() + { + if (isSatisfied()) deltablue.planner.incrementalRemove(this); + else + removeFromGraph(); + } + + // Add myself to the constraint graph. + public abstract void addToGraph(); + + // Remove myself from the constraint graph. + public abstract void removeFromGraph(); + + // Decide if I can be satisfied and record that decision. The output + // of the choosen method must not have the given mark and must have + // a walkabout strength less than that of this constraint. + public abstract void chooseMethod(int mark); + + // Set the mark of all input from the given mark. + public abstract void markInputs(int mark); + + // Assume that I am satisfied. Answer true if all my current inputs + // are known. A variable is known if either a) it is 'stay' (i.e. it + // is a constant at plan execution time), b) it has the given mark + // (indicating that it has been computed by a constraint appearing + // earlier in the plan), or c) it is not determined by any + // constraint. + public abstract Boolean inputsKnown(int mark); + + // Answer my current output variable. Raise an error if I am not + // currently satisfied. + public abstract Variable output(); + + // Attempt to find a way to enforce this constraint. If successful, + // record the solution, perhaps modifying the current dataflow + // graph. Answer the constraint that this constraint overrides, if + // there is one, or nil, if there isn't. + // Assume: I am not already satisfied. + // + public Constraint satisfy(int mark) + { + chooseMethod(mark); + if (!isSatisfied()) + { + if (strength == Strength.required) + { + deltablue.error("Could not satisfy a required constraint"); + } + return null; + } + // constraint can be satisfied + // mark inputs to allow cycle detection in addPropagate + markInputs(mark); + Variable outvar = output(); + Constraint overridden = outvar.determinedBy; + if (overridden != null) overridden.markUnsatisfied(); + outvar.determinedBy = this; + if (!deltablue.planner.addPropagate(this, mark)) + { + Console.WriteLine("Cycle encountered"); + return null; + } + outvar.mark = mark; + return overridden; + } + + // Enforce this constraint. Assume that it is satisfied. + public abstract void execute(); + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + public abstract void recalculate(); + + public abstract void printInputs(); + + public void printOutput() { output().print(); } + + public void print() + { + if (!isSatisfied()) + { + Console.Write("Unsatisfied"); + } + else + { + Console.Write("Satisfied("); + printInputs(); + Console.Write(" -> "); + printOutput(); + Console.Write(")"); + } + Console.Write("\n"); + } +} + + + +//-------------unary constraints------------------------------------------- + +// I am an abstract superclass for constraints having a single +// possible output variable. +// +internal abstract class UnaryConstraint : Constraint +{ + public Variable myOutput; // possible output variable + public Boolean satisfied; // true if I am currently satisfied + + public UnaryConstraint(Variable v, Strength strength) : base(strength) + + { + myOutput = v; + satisfied = false; + addConstraint(); + } + + // Answer true if this constraint is satisfied in the current solution. + public override Boolean isSatisfied() { return satisfied; } + + // Record the fact that I am unsatisfied. + public override void markUnsatisfied() { satisfied = false; } + + // Answer my current output variable. + public override Variable output() { return myOutput; } + + // Add myself to the constraint graph. + public override void addToGraph() + { + myOutput.addConstraint(this); + satisfied = false; + } + + // Remove myself from the constraint graph. + public override void removeFromGraph() + { + if (myOutput != null) myOutput.removeConstraint(this); + satisfied = false; + } + + // Decide if I can be satisfied and record that decision. + public override void chooseMethod(int mark) + { + satisfied = myOutput.mark != mark + && Strength.stronger(strength, myOutput.walkStrength); + } + + public override void markInputs(int mark) { } // I have no inputs + + public override Boolean inputsKnown(int mark) { return true; } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied." + public override void recalculate() + { + myOutput.walkStrength = strength; + myOutput.stay = !isInput(); + if (myOutput.stay) execute(); // stay optimization + } + + public override void printInputs() { } // I have no inputs +} + + +// I am a unary input constraint used to mark a variable that the +// client wishes to change. +// +internal class EditConstraint : UnaryConstraint +{ + public EditConstraint(Variable v, Strength str) : base(v, str) { } + + // I indicate that a variable is to be changed by imperative code. + public override Boolean isInput() { return true; } + + public override void execute() { } // Edit constraints do nothing. +} + +// I mark variables that should, with some level of preference, stay +// the same. I have one method with zero inputs and one output, which +// does nothing. Planners may exploit the fact that, if I am +// satisfied, my output will not change during plan execution. This is +// called "stay optimization". +// +internal class StayConstraint : UnaryConstraint +{ + // Install a stay constraint with the given strength on the given variable. + public StayConstraint(Variable v, Strength str) : base(v, str) { } + + public override void execute() { } // Stay constraints do nothing. +} + + + + +//-------------binary constraints------------------------------------------- + + +// I am an abstract superclass for constraints having two possible +// output variables. +// +internal abstract class BinaryConstraint : Constraint +{ + public Variable v1, v2; // possible output variables + public sbyte direction; // one of the following... + public static sbyte backward = -1; // v1 is output + public static sbyte nodirection = 0; // not satisfied + public static sbyte forward = 1; // v2 is output + + public BinaryConstraint() { } // this has to be here because of + // Java's constructor idiocy. + + public BinaryConstraint(Variable var1, Variable var2, Strength strength) + : base(strength) + { + v1 = var1; + v2 = var2; + direction = nodirection; + addConstraint(); + } + + // Answer true if this constraint is satisfied in the current solution. + public override Boolean isSatisfied() { return direction != nodirection; } + + // Add myself to the constraint graph. + public override void addToGraph() + { + v1.addConstraint(this); + v2.addConstraint(this); + direction = nodirection; + } + + // Remove myself from the constraint graph. + public override void removeFromGraph() + { + if (v1 != null) v1.removeConstraint(this); + if (v2 != null) v2.removeConstraint(this); + direction = nodirection; + } + + // Decide if I can be satisfied and which way I should flow based on + // the relative strength of the variables I relate, and record that + // decision. + // + public override void chooseMethod(int mark) + { + if (v1.mark == mark) + direction = + v2.mark != mark && Strength.stronger(strength, v2.walkStrength) + ? forward : nodirection; + + if (v2.mark == mark) + direction = + v1.mark != mark && Strength.stronger(strength, v1.walkStrength) + ? backward : nodirection; + + // If we get here, neither variable is marked, so we have a choice. + if (Strength.weaker(v1.walkStrength, v2.walkStrength)) + direction = + Strength.stronger(strength, v1.walkStrength) ? backward : nodirection; + else + direction = + Strength.stronger(strength, v2.walkStrength) ? forward : nodirection; + } + + // Record the fact that I am unsatisfied. + public override void markUnsatisfied() { direction = nodirection; } + + // Mark the input variable with the given mark. + public override void markInputs(int mark) + { + input().mark = mark; + } + + public override Boolean inputsKnown(int mark) + { + Variable i = input(); + return i.mark == mark || i.stay || i.determinedBy == null; + } + + // Answer my current output variable. + public override Variable output() { return direction == forward ? v2 : v1; } + + // Answer my current input variable + public Variable input() { return direction == forward ? v1 : v2; } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + // + public override void recalculate() + { + Variable invar = input(), outvar = output(); + outvar.walkStrength = Strength.weakestOf(strength, invar.walkStrength); + outvar.stay = invar.stay; + if (outvar.stay) execute(); + } + + public override void printInputs() + { + input().print(); + } +} + + +// I constrain two variables to have the same value: "v1 = v2". +// +internal class EqualityConstraint : BinaryConstraint +{ + // Install a constraint with the given strength equating the given variables. + public EqualityConstraint(Variable var1, Variable var2, Strength strength) + : base(var1, var2, strength) + + { + } + + // Enforce this constraint. Assume that it is satisfied. + public override void execute() + { + output().value = input().value; + } +} + + +// I relate two variables by the linear scaling relationship: "v2 = +// (v1 * scale) + offset". Either v1 or v2 may be changed to maintain +// this relationship but the scale factor and offset are considered +// read-only. +// +internal class ScaleConstraint : BinaryConstraint +{ + public Variable scale; // scale factor input variable + public Variable offset; // offset input variable + + // Install a scale constraint with the given strength on the given variables. + public ScaleConstraint(Variable src, Variable scale, Variable offset, + Variable dest, Strength strength) + { + // Curse this wretched language for insisting that constructor invocation + // must be the first thing in a method... + // ..because of that, we must copy the code from the inherited + // constructors. + this.strength = strength; + v1 = src; + v2 = dest; + direction = nodirection; + this.scale = scale; + this.offset = offset; + addConstraint(); + } + + // Add myself to the constraint graph. + public override void addToGraph() + { + base.addToGraph(); + scale.addConstraint(this); + offset.addConstraint(this); + } + + // Remove myself from the constraint graph. + public override void removeFromGraph() + { + base.removeFromGraph(); + if (scale != null) scale.removeConstraint(this); + if (offset != null) offset.removeConstraint(this); + } + + // Mark the inputs from the given mark. + public override void markInputs(int mark) + { + base.markInputs(mark); + scale.mark = offset.mark = mark; + } + + // Enforce this constraint. Assume that it is satisfied. + public override void execute() + { + if (direction == forward) + v2.value = v1.value * scale.value + offset.value; + else + v1.value = (v2.value - offset.value) / scale.value; + } + + // Calculate the walkabout strength, the stay flag, and, if it is + // 'stay', the value for the current output of this + // constraint. Assume this constraint is satisfied. + public override void recalculate() + { + Variable invar = input(), outvar = output(); + outvar.walkStrength = Strength.weakestOf(strength, invar.walkStrength); + outvar.stay = invar.stay && scale.stay && offset.stay; + if (outvar.stay) execute(); // stay optimization + } +} + + +// ------------------------------------------------------------ + + +// A Plan is an ordered list of constraints to be executed in sequence +// to resatisfy all currently satisfiable constraints in the face of +// one or more changing inputs. + +internal class Plan +{ + private ArrayList _v; + + public Plan() { _v = new ArrayList(); } + + public void addConstraint(Constraint c) { _v.Add(c); } + + public int size() { return _v.Count; } + + public Constraint constraintAt(int index) + { + return (Constraint)_v[index]; + } + + public void execute() + { + for (int i = 0; i < size(); ++i) + { + Constraint c = (Constraint)constraintAt(i); + c.execute(); + } + } +} + + +// ------------------------------------------------------------ + +// The deltablue planner + +internal class Planner +{ + private int _currentMark = 0; + + // Select a previously unused mark value. + private int newMark() { return ++_currentMark; } + + public Planner() + { + _currentMark = 0; + } + + // Attempt to satisfy the given constraint and, if successful, + // incrementally update the dataflow graph. Details: If satifying + // the constraint is successful, it may override a weaker constraint + // on its output. The algorithm attempts to resatisfy that + // constraint using some other method. This process is repeated + // until either a) it reaches a variable that was not previously + // determined by any constraint or b) it reaches a constraint that + // is too weak to be satisfied using any of its methods. The + // variables of constraints that have been processed are marked with + // a unique mark value so that we know where we've been. This allows + // the algorithm to avoid getting into an infinite loop even if the + // constraint graph has an inadvertent cycle. + // + public void incrementalAdd(Constraint c) + { + int mark = newMark(); + Constraint overridden = c.satisfy(mark); + while (overridden != null) + { + overridden = overridden.satisfy(mark); + } + } + + + // Entry point for retracting a constraint. Remove the given + // constraint and incrementally update the dataflow graph. + // Details: Retracting the given constraint may allow some currently + // unsatisfiable downstream constraint to be satisfied. We therefore collect + // a list of unsatisfied downstream constraints and attempt to + // satisfy each one in turn. This list is traversed by constraint + // strength, strongest first, as a heuristic for avoiding + // unnecessarily adding and then overriding weak constraints. + // Assume: c is satisfied. + // + public void incrementalRemove(Constraint c) + { + Variable outvar = c.output(); + c.markUnsatisfied(); + c.removeFromGraph(); + ArrayList unsatisfied = removePropagateFrom(outvar); + Strength strength = Strength.required; + do + { + for (int i = 0; i < unsatisfied.Count; ++i) + { + Constraint u = (Constraint)unsatisfied[i]; + if (u.strength == strength) + incrementalAdd(u); + } + strength = strength.nextWeaker(); + } while (strength != Strength.weakest); + } + + // Recompute the walkabout strengths and stay flags of all variables + // downstream of the given constraint and recompute the actual + // values of all variables whose stay flag is true. If a cycle is + // detected, remove the given constraint and answer + // false. Otherwise, answer true. + // Details: Cycles are detected when a marked variable is + // encountered downstream of the given constraint. The sender is + // assumed to have marked the inputs of the given constraint with + // the given mark. Thus, encountering a marked node downstream of + // the output constraint means that there is a path from the + // constraint's output to one of its inputs. + // + public Boolean addPropagate(Constraint c, int mark) + { + ArrayList todo = new ArrayList(); + todo.Add(c); + while (!(todo.Count == 0)) + { +#if USE_STACK + Constraint d = (Constraint)todo[todo.Count - 1]; + todo.RemoveAt(todo.Count - 1); +#else + Constraint d= (Constraint)todo[0]; + todo.RemoveAt(0); +#endif + if (d.output().mark == mark) + { + incrementalRemove(c); + return false; + } + d.recalculate(); + addConstraintsConsumingTo(d.output(), todo); + } + return true; + } + + + // The given variable has changed. Propagate new values downstream. + public void propagateFrom(Variable v) + { + ArrayList todo = new ArrayList(); + addConstraintsConsumingTo(v, todo); + while (!(todo.Count == 0)) + { +#if USE_STACK + Constraint c = (Constraint)todo[todo.Count - 1]; + todo.RemoveAt(0); +#else + Constraint c= (Constraint)todo[todo.Count-1]; + todo.RemoveAt(0); +#endif + c.execute(); + addConstraintsConsumingTo(c.output(), todo); + } + } + + // Update the walkabout strengths and stay flags of all variables + // downstream of the given constraint. Answer a collection of + // unsatisfied constraints sorted in order of decreasing strength. + // + public ArrayList removePropagateFrom(Variable outvar) + { + outvar.determinedBy = null; + outvar.walkStrength = Strength.weakest; + outvar.stay = true; + ArrayList unsatisfied = new ArrayList(); + ArrayList todo = new ArrayList(); + todo.Add(outvar); + while (!(todo.Count == 0)) + { +#if USE_STACK + Variable v = (Variable)todo[todo.Count - 1]; + todo.RemoveAt(todo.Count - 1); +#else + Variable v= (Variable)todo[0]; + todo.RemoveAt(0); +#endif + for (int i = 0; i < v.constraints.Count; ++i) + { + Constraint c = (Constraint)v.constraints[i]; + if (!c.isSatisfied()) + unsatisfied.Add(c); + } + Constraint determiningC = v.determinedBy; + for (int i = 0; i < v.constraints.Count; ++i) + { + Constraint nextC = (Constraint)v.constraints[i]; + if (nextC != determiningC && nextC.isSatisfied()) + { + nextC.recalculate(); + todo.Add(nextC.output()); + } + } + } + return unsatisfied; + } + + // Extract a plan for resatisfaction starting from the outputs of + // the given constraints, usually a set of input constraints. + // + public Plan extractPlanFromConstraints(ArrayList constraints) + { + ArrayList sources = new ArrayList(); + for (int i = 0; i < constraints.Count; ++i) + { + Constraint c = (Constraint)constraints[i]; + if (c.isInput() && c.isSatisfied()) + sources.Add(c); + } + return makePlan(sources); + } + + // Extract a plan for resatisfaction starting from the given source + // constraints, usually a set of input constraints. This method + // assumes that stay optimization is desired; the plan will contain + // only constraints whose output variables are not stay. Constraints + // that do no computation, such as stay and edit constraints, are + // not included in the plan. + // Details: The outputs of a constraint are marked when it is added + // to the plan under construction. A constraint may be appended to + // the plan when all its input variables are known. A variable is + // known if either a) the variable is marked (indicating that has + // been computed by a constraint appearing earlier in the plan), b) + // the variable is 'stay' (i.e. it is a constant at plan execution + // time), or c) the variable is not determined by any + // constraint. The last provision is for past states of history + // variables, which are not stay but which are also not computed by + // any constraint. + // Assume: sources are all satisfied. + // + public Plan makePlan(ArrayList sources) + { + int mark = newMark(); + Plan plan = new Plan(); + ArrayList todo = sources; + while (!(todo.Count == 0)) + { +#if USE_STACK + Constraint c = (Constraint)todo[todo.Count - 1]; + todo.RemoveAt(todo.Count - 1); +#else + Constraint c= (Constraint)todo[todo.Count-1]; + todo.RemoveAt(0); +#endif + if (c.output().mark != mark && c.inputsKnown(mark)) + { + // not in plan already and eligible for inclusion + plan.addConstraint(c); + c.output().mark = mark; + addConstraintsConsumingTo(c.output(), todo); + } + } + return plan; + } + + public void addConstraintsConsumingTo(Variable v, ArrayList coll) + { + Constraint determiningC = v.determinedBy; + ArrayList cc = v.constraints; + for (int i = 0; i < cc.Count; ++i) + { + Constraint c = (Constraint)cc[i]; + if (c != determiningC && c.isSatisfied()) + coll.Add(c); + } + } +} + +//------------------------------------------------------------ + +public class deltablue +{ + internal static Planner planner; + internal static int chains, projections; + + public static int Main(String[] args) + { + deltablue d = new deltablue(); + d.inst_main(args); + return 100; + } + + [Benchmark] + public static void Bench() + { + deltablue d = new deltablue(); + int iterations = 200; + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + d.inst_inner(iterations, false); + } + } + } + + public void inst_main(String[] args) + { + int iterations = 200; // read iterations from arguments, walter 7/97 + try + { // read iterations from arguments, walter 7/97 + iterations = Int32.Parse(args[0]); + } + catch (Exception) + { + } + inst_inner(iterations, true); + } + + public void inst_inner(int iterations, bool verbose) + { + chains = 0; // NS 11/11 + projections = 0; // NS 11/11 + if (verbose) + { + Console.WriteLine("deltablue parameters: " + iterations + " iterations"); + } + + DateTime start = DateTime.Now; + for (int i = 0; i < iterations; i++) + { + chainTest(1000); + projectionTest(1000); + } + DateTime end = DateTime.Now; + TimeSpan dur = end - start; + if (verbose) + { + Console.WriteLine("chains : " + chains); //NS + Console.WriteLine("projections : " + projections); //NS + Console.WriteLine("Doing {0} iters of Deltablue takes {1} ms; {2} us/iter.", + iterations, dur.TotalMilliseconds, (1000.0 * dur.TotalMilliseconds) / iterations); + } + } + + // This is the standard DeltaBlue benchmark. A long chain of + // equality constraints is constructed with a stay constraint on + // one end. An edit constraint is then added to the opposite end + // and the time is measured for adding and removing this + // constraint, and extracting and executing a constraint + // satisfaction plan. There are two cases. In case 1, the added + // constraint is stronger than the stay constraint and values must + // propagate down the entire length of the chain. In case 2, the + // added constraint is weaker than the stay constraint so it cannot + // be accomodated. The cost in this case is, of course, very + // low. Typical situations lie somewhere between these two + // extremes. + // + private void chainTest(int n) + { + planner = new Planner(); + + Variable prev = null, first = null, last = null; + + // Build chain of n equality constraints + for (int i = 0; i <= n; i++) + { + String name = "v" + i; + Variable v = new Variable(name); + if (prev != null) + new EqualityConstraint(prev, v, Strength.required); + if (i == 0) first = v; + if (i == n) last = v; + prev = v; + } + + new StayConstraint(last, Strength.strongDefault); + Constraint editC = new EditConstraint(first, Strength.preferred); + ArrayList editV = new ArrayList(); + editV.Add(editC); + Plan plan = planner.extractPlanFromConstraints(editV); + for (int i = 0; i < 100; i++) + { + first.value = i; + plan.execute(); + if (last.value != i) + error("Chain test failed!"); + } + editC.destroyConstraint(); + deltablue.chains++; + } + + + // This test constructs a two sets of variables related to each + // other by a simple linear transformation (scale and offset). The + // time is measured to change a variable on either side of the + // mapping and to change the scale and offset factors. + // + private void projectionTest(int n) + { + planner = new Planner(); + + Variable scale = new Variable("scale", 10); + Variable offset = new Variable("offset", 1000); + Variable src = null, dst = null; + + ArrayList dests = new ArrayList(); + + for (int i = 0; i < n; ++i) + { + src = new Variable("src" + i, i); + dst = new Variable("dst" + i, i); + dests.Add(dst); + new StayConstraint(src, Strength.normal); + new ScaleConstraint(src, scale, offset, dst, Strength.required); + } + + change(src, 17); + if (dst.value != 1170) error("Projection test 1 failed!"); + + change(dst, 1050); + if (src.value != 5) error("Projection test 2 failed!"); + + change(scale, 5); + for (int i = 0; i < n - 1; ++i) + { + if (((Variable)dests[i]).value != i * 5 + 1000) + error("Projection test 3 failed!"); + } + + change(offset, 2000); + for (int i = 0; i < n - 1; ++i) + { + if (((Variable)dests[i]).value != i * 5 + 2000) + error("Projection test 4 failed!"); + } + deltablue.projections++; + } + + private void change(Variable var, int newValue) + { + EditConstraint editC = new EditConstraint(var, Strength.preferred); + ArrayList editV = new ArrayList(); + editV.Add(editC); + Plan plan = planner.extractPlanFromConstraints(editV); + for (int i = 0; i < 10; i++) + { + var.value = newValue; + plan.execute(); + } + editC.destroyConstraint(); + } + + public static void error(String s) + { + throw new Exception(s); + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.csproj b/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.csproj new file mode 100644 index 0000000000..810469f0fb --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/DeltaBlue/DeltaBlue.csproj @@ -0,0 +1,45 @@ + + + + + Debug + AnyCPU + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + 7a9bfb7d + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.cs b/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.cs new file mode 100644 index 0000000000..5e993dde5c --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.cs @@ -0,0 +1,756 @@ +// Copyright (c) Microsoft. All rights reserved. +// Licensed under the MIT license. See LICENSE file in the project root for full license information. +// +// This is a C# implementation of the Richards benchmark from: +// +// http://www.cl.cam.ac.uk/~mr10/Bench.html +// +// The benchmark was originally implemented in BCPL by Martin Richards. + +#define INTF_FOR_TASK + +using Microsoft.Xunit.Performance; +using System; +using System.Collections.Generic; + +[assembly: OptimizeForBenchmarks] +[assembly: MeasureInstructionsRetired] + +// using System.Diagnostics; +// using System.Text.RegularExpressions; + +namespace Richards +{ + /// + /// Support is used for a place to generate any 'miscellaneous' methods generated as part + /// of code generation, (which do not have user-visible names) + /// + public class Support + { + public static bool runRichards() + { + Scheduler scheduler = new Scheduler(); + scheduler.addIdleTask(ID_IDLE, 0, null, COUNT); + Packet queue = new Packet(null, ID_WORKER, KIND_WORK); + queue = new Packet(queue, ID_WORKER, KIND_WORK); + scheduler.addWorkerTask(ID_WORKER, 1000, queue); + + queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE); + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE); + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE); + scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue); + + queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE); + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE); + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE); + scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue); + + scheduler.addDeviceTask(ID_DEVICE_A, 4000, null); + scheduler.addDeviceTask(ID_DEVICE_B, 5000, null); + scheduler.schedule(); + + return ((scheduler.queueCount == EXPECTED_QUEUE_COUNT) + && (scheduler.holdCount == EXPECTED_HOLD_COUNT)); + } + + public const int COUNT = 1000; + + /** + * These two constants specify how many times a packet is queued and + * how many times a task is put on hold in a correct run of richards. + * They don't have any meaning a such but are characteristic of a + * correct run so if the actual queue or hold count is different from + * the expected there must be a bug in the implementation. + **/ + public const int EXPECTED_QUEUE_COUNT = 2322; + public const int EXPECTED_HOLD_COUNT = 928; + + public const int ID_IDLE = 0; + public const int ID_WORKER = 1; + public const int ID_HANDLER_A = 2; + public const int ID_HANDLER_B = 3; + public const int ID_DEVICE_A = 4; + public const int ID_DEVICE_B = 5; + public const int NUMBER_OF_IDS = 6; + + public const int KIND_DEVICE = 0; + public const int KIND_WORK = 1; + + /** + * The task is running and is currently scheduled. + */ + public const int STATE_RUNNING = 0; + + /** + * The task has packets left to process. + */ + public const int STATE_RUNNABLE = 1; + + /** + * The task is not currently running. The task is not blocked as such and may + * be started by the scheduler. + */ + public const int STATE_SUSPENDED = 2; + + /** + * The task is blocked and cannot be run until it is explicitly released. + */ + public const int STATE_HELD = 4; + + public const int STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE; + public const int STATE_NOT_HELD = ~STATE_HELD; + + /* --- * + * P a c k e t + * --- */ + + public const int DATA_SIZE = 4; + + public static int Main(String[] args) + { + int n = 1; + if (args.Length > 0) + { + n = Int32.Parse(args[0]); + } + bool result = Measure(n); + return (result ? 100 : -1); + } + + public static bool Measure(int n) + { + DateTime start = DateTime.Now; + bool result = true; + for (int i = 0; i < n; i++) + { + result &= runRichards(); + } + DateTime end = DateTime.Now; + TimeSpan dur = end - start; + Console.WriteLine("Doing {0} iters of Richards takes {1} ms; {2} us/iter.", + n, dur.TotalMilliseconds, (1000.0 * dur.TotalMilliseconds) / n); + return result; + } + + [Benchmark] + public static void Bench() + { + const int Iterations = 5000; + + foreach (var iteration in Benchmark.Iterations) + { + using (iteration.StartMeasurement()) + { + for (int i = 0; i < Iterations; i++) + { + runRichards(); + } + } + } + } + } + + internal class Scheduler + { + public int queueCount; + public int holdCount; + public TaskControlBlock[] blocks; + public TaskControlBlock list; + public TaskControlBlock currentTcb; + public int currentId; + + public Scheduler() + { + this.queueCount = 0; + this.holdCount = 0; + this.blocks = new TaskControlBlock[Support.NUMBER_OF_IDS]; + this.list = null; + this.currentTcb = null; + this.currentId = 0; + } + + /** + * Add an idle task to this scheduler. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + * @param {int} count the number of times to schedule the task + */ + public void addIdleTask(int id, int priority, Packet queue, int count) + { + this.addRunningTask(id, priority, queue, + new IdleTask(this, 1, count)); + } + + /** + * Add a work task to this scheduler. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + */ + public void addWorkerTask(int id, int priority, Packet queue) + { + this.addTask(id, priority, queue, + new WorkerTask(this, Support.ID_HANDLER_A, 0)); + } + + /** + * Add a handler task to this scheduler. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + */ + public void addHandlerTask(int id, int priority, Packet queue) + { + this.addTask(id, priority, queue, new HandlerTask(this)); + } + + /** + * Add a handler task to this scheduler. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + */ + public void addDeviceTask(int id, int priority, Packet queue) + { + this.addTask(id, priority, queue, new DeviceTask(this)); + } + + /** + * Add the specified task and mark it as running. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + * @param {Task} task the task to add + */ + public void addRunningTask(int id, int priority, Packet queue, Task task) + { + this.addTask(id, priority, queue, task); + this.currentTcb.setRunning(); + } + + /** + * Add the specified task to this scheduler. + * @param {int} id the identity of the task + * @param {int} priority the task's priority + * @param {Packet} queue the queue of work to be processed by the task + * @param {Task} task the task to add + */ + public void addTask(int id, int priority, Packet queue, Task task) + { + this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task); + this.list = this.currentTcb; + this.blocks[id] = this.currentTcb; + } + + /** + * Execute the tasks managed by this scheduler. + */ + public void schedule() + { + this.currentTcb = this.list; +#if TRACEIT + int kkk = 0; +#endif + while (this.currentTcb != null) + { +#if TRACEIT + Console.WriteLine("kkk = {0}", kkk); kkk++; +#endif + if (this.currentTcb.isHeldOrSuspended()) + { +#if TRACEIT + Console.WriteLine("held"); +#endif + this.currentTcb = this.currentTcb.link; + } + else + { + this.currentId = this.currentTcb.id; +#if TRACEIT + Console.WriteLine("currentId is now...{0}", this.currentId.ToString()); +#endif + this.currentTcb = this.currentTcb.run(); + } + } + } + + /** + * Release a task that is currently blocked and return the next block to run. + * @param {int} id the id of the task to suspend + */ + public TaskControlBlock release(int id) + { + TaskControlBlock tcb = this.blocks[id]; + if (tcb == null) return tcb; + tcb.markAsNotHeld(); + if (tcb.priority >= this.currentTcb.priority) + { + return tcb; + } + else + { + return this.currentTcb; + } + } + + /** + * Block the currently executing task and return the next task control block + * to run. The blocked task will not be made runnable until it is explicitly + * released, even if new work is added to it. + */ + public TaskControlBlock holdCurrent() + { + this.holdCount++; + this.currentTcb.markAsHeld(); + return this.currentTcb.link; + } + + /** + * Suspend the currently executing task and return the next task control block + * to run. If new work is added to the suspended task it will be made runnable. + */ + public TaskControlBlock suspendCurrent() + { + this.currentTcb.markAsSuspended(); + return this.currentTcb; + } + + /** + * Add the specified packet to the end of the worklist used by the task + * associated with the packet and make the task runnable if it is currently + * suspended. + * @param {Packet} packet the packet to add + */ + public TaskControlBlock queue(Packet packet) + { + TaskControlBlock t = this.blocks[packet.id]; + if (t == null) return t; + this.queueCount++; + packet.link = null; + packet.id = this.currentId; + return t.checkPriorityAdd(this.currentTcb, packet); + } + } + + /** + * A task control block manages a task and the queue of work packages associated + * with it. + * @param {TaskControlBlock} link the preceding block in the linked block list + * @param {int} id the id of this block + * @param {int} priority the priority of this block + * @param {Packet} queue the queue of packages to be processed by the task + * @param {Task} task the task + * @constructor + */ + public class TaskControlBlock + { + public TaskControlBlock link; + public int id; + public int priority; + public Packet queue; + public Task task; + public int state; + + public TaskControlBlock(TaskControlBlock link, int id, int priority, + Packet queue, Task task) + { + this.link = link; + this.id = id; + this.priority = priority; + this.queue = queue; + this.task = task; + if (queue == null) + { + this.state = Support.STATE_SUSPENDED; + } + else + { + this.state = Support.STATE_SUSPENDED_RUNNABLE; + } + } + + public void setRunning() + { + this.state = Support.STATE_RUNNING; + } + + public void markAsNotHeld() + { + this.state = this.state & Support.STATE_NOT_HELD; + } + + public void markAsHeld() + { + this.state = this.state | Support.STATE_HELD; + } + + public bool isHeldOrSuspended() + { + return ((this.state & Support.STATE_HELD) != 0) || (this.state == Support.STATE_SUSPENDED); + } + + public void markAsSuspended() + { + this.state = this.state | Support.STATE_SUSPENDED; + } + + public void markAsRunnable() + { + this.state = this.state | Support.STATE_RUNNABLE; + } + + /** + * Runs this task, if it is ready to be run, and returns the next task to run. + */ + public TaskControlBlock run() + { + Packet packet; +#if TRACEIT + Console.WriteLine(" TCB::run, state = {0}", this.state); +#endif + if (this.state == Support.STATE_SUSPENDED_RUNNABLE) + { + packet = this.queue; + this.queue = packet.link; + if (this.queue == null) + { + this.state = Support.STATE_RUNNING; + } + else + { + this.state = Support.STATE_RUNNABLE; + } +#if TRACEIT + Console.WriteLine(" State is now {0}", this.state); +#endif + } + else + { +#if TRACEIT + Console.WriteLine(" TCB::run, setting packet = Null."); +#endif + packet = null; + } + return this.task.run(packet); + } + + /** + * Adds a packet to the worklist of this block's task, marks this as runnable if + * necessary, and returns the next runnable object to run (the one + * with the highest priority). + */ + public TaskControlBlock checkPriorityAdd(TaskControlBlock task, Packet packet) + { + if (this.queue == null) + { + this.queue = packet; + this.markAsRunnable(); + if (this.priority >= task.priority) return this; + } + else + { + this.queue = packet.addTo(this.queue); + } + return task; + } + + public String toString() + { + return "tcb { " + this.task.toString() + "@" + this.state.ToString() + " }"; + } + } + +#if INTF_FOR_TASK + // I deliberately ignore the "I" prefix convention here so that we can use Task as a type in both + // cases... + public interface Task + { + TaskControlBlock run(Packet packet); + String toString(); + } +#else + public abstract class Task + { + public abstract TaskControlBlock run(Packet packet); + public abstract String toString(); + } +#endif + + /** + * An idle task doesn't do any work itself but cycles control between the two + * device tasks. + * @param {Scheduler} scheduler the scheduler that manages this task + * @param {int} v1 a seed value that controls how the device tasks are scheduled + * @param {int} count the number of times this task should be scheduled + * @constructor + */ + internal class IdleTask : Task + { + public Scheduler scheduler; + public int _v1; + public int _count; + + public IdleTask(Scheduler scheduler, int v1, int count) + { + this.scheduler = scheduler; + this._v1 = v1; + this._count = count; + } + + public +#if !INTF_FOR_TASK + override +#endif + TaskControlBlock run(Packet packet) + { + this._count--; + if (this._count == 0) return this.scheduler.holdCurrent(); + if ((this._v1 & 1) == 0) + { + this._v1 = this._v1 >> 1; + return this.scheduler.release(Support.ID_DEVICE_A); + } + else + { + this._v1 = (this._v1 >> 1) ^ 0xD008; + return this.scheduler.release(Support.ID_DEVICE_B); + } + } + + public +#if !INTF_FOR_TASK + override +#endif + String toString() + { + return "IdleTask"; + } + } + + /** + * A task that suspends itself after each time it has been run to simulate + * waiting for data from an external device. + * @param {Scheduler} scheduler the scheduler that manages this task + * @constructor + */ + internal class DeviceTask : Task + { + public Scheduler scheduler; + private Packet _v1; + + public DeviceTask(Scheduler scheduler) + { + this.scheduler = scheduler; + _v1 = null; + } + + public +#if !INTF_FOR_TASK + override +#endif + TaskControlBlock run(Packet packet) + { + if (packet == null) + { + if (_v1 == null) return this.scheduler.suspendCurrent(); + Packet v = _v1; + _v1 = null; + return this.scheduler.queue(v); + } + else + { + _v1 = packet; + return this.scheduler.holdCurrent(); + } + } + + public +#if !INTF_FOR_TASK + override +#endif + String toString() + { + return "DeviceTask"; + } + } + + /** + * A task that manipulates work packets. + * @param {Scheduler} scheduler the scheduler that manages this task + * @param {int} v1 a seed used to specify how work packets are manipulated + * @param {int} v2 another seed used to specify how work packets are manipulated + * @constructor + */ + internal class WorkerTask : Task + { + public Scheduler scheduler; + public int v1; + public int _v2; + + public WorkerTask(Scheduler scheduler, int v1, int v2) + { + this.scheduler = scheduler; + this.v1 = v1; + this._v2 = v2; + } + + public +#if !INTF_FOR_TASK + override +#endif + TaskControlBlock run(Packet packet) + { + if (packet == null) + { + return this.scheduler.suspendCurrent(); + } + else + { + if (this.v1 == Support.ID_HANDLER_A) + { + this.v1 = Support.ID_HANDLER_B; + } + else + { + this.v1 = Support.ID_HANDLER_A; + } + packet.id = this.v1; + packet.a1 = 0; + for (int i = 0; i < Support.DATA_SIZE; i++) + { + this._v2++; + if (this._v2 > 26) this._v2 = 1; + packet.a2[i] = this._v2; + } + return this.scheduler.queue(packet); + } + } + + public +#if !INTF_FOR_TASK + override +#endif + String toString() + { + return "WorkerTask"; + } + } + + /** + * A task that manipulates work packets and then suspends itself. + * @param {Scheduler} scheduler the scheduler that manages this task + * @constructor + */ + internal class HandlerTask : Task + { + public Scheduler scheduler; + public Packet v1; + public Packet v2; + + public HandlerTask(Scheduler scheduler) + { + this.scheduler = scheduler; + this.v1 = null; + this.v2 = null; + } + + public +#if !INTF_FOR_TASK + override +#endif + TaskControlBlock run(Packet packet) + { + if (packet != null) + { + if (packet.kind == Support.KIND_WORK) + { + this.v1 = packet.addTo(this.v1); + } + else + { + this.v2 = packet.addTo(this.v2); + } + } + if (this.v1 != null) + { + int count = this.v1.a1; + Packet v; + if (count < Support.DATA_SIZE) + { + if (this.v2 != null) + { + v = this.v2; + this.v2 = this.v2.link; + v.a1 = this.v1.a2[count]; + this.v1.a1 = count + 1; + return this.scheduler.queue(v); + } + } + else + { + v = this.v1; + this.v1 = this.v1.link; + return this.scheduler.queue(v); + } + } + return this.scheduler.suspendCurrent(); + } + + public +#if !INTF_FOR_TASK + override +#endif + String toString() + { + return "HandlerTask"; + } + } + + /** + * A simple package of data that is manipulated by the tasks. The exact layout + * of the payload data carried by a packet is not importaint, and neither is the + * nature of the work performed on packets by the tasks. + * + * Besides carrying data, packets form linked lists and are hence used both as + * data and worklists. + * @param {Packet} link the tail of the linked list of packets + * @param {int} id an ID for this packet + * @param {int} kind the type of this packet + * @constructor + */ + public class Packet + { + public Packet link; + public int id; + public int kind; + public int a1; + public int[] a2; + + public Packet(Packet link, int id, int kind) + { + this.link = link; + this.id = id; + this.kind = kind; + this.a1 = 0; + this.a2 = new int[Support.DATA_SIZE]; + } + + public Packet addTo(Packet queue) + { + this.link = null; + if (queue == null) return this; + Packet peek; + Packet next = queue; + while ((peek = next.link) != null) + next = peek; + next.link = this; + return queue; + } + + public String toString() + { + return "Packet"; + } + } +} diff --git a/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.csproj b/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.csproj new file mode 100644 index 0000000000..7a5f521076 --- /dev/null +++ b/tests/src/JIT/Performance/CodeQuality/V8/Richards/Richards.csproj @@ -0,0 +1,45 @@ + + + + + Debug + AnyCPU + 2.0 + {95DFC527-4DC1-495E-97D7-E94EE1F7140D} + Exe + Properties + 512 + {786C830F-07A1-408B-BD7F-6EE04809D6DB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC} + $(ProgramFiles)\Common Files\microsoft shared\VSTT\11.0\UITestExtensionPackages + ..\..\ + 7a9bfb7d + + + + + + pdbonly + true + + + + False + + + + + + + + + + + + + $(JitPackagesConfigFileDirectory)benchmark\project.json + $(JitPackagesConfigFileDirectory)benchmark\project.lock.json + + + + + diff --git a/tests/src/JIT/config/benchmark/project.json b/tests/src/JIT/config/benchmark/project.json index 80dbbb7572..690921a616 100644 --- a/tests/src/JIT/config/benchmark/project.json +++ b/tests/src/JIT/config/benchmark/project.json @@ -3,6 +3,7 @@ "Microsoft.DotNet.xunit.performance": "1.0.0-alpha-build0027", "Microsoft.DotNet.xunit.performance.analysis": "1.0.0-alpha-build0027", "Microsoft.DotNet.xunit.performance.runner.Windows": "1.0.0-alpha-build0027", + "System.Collections.NonGeneric": "4.0.0", "System.Console": "4.0.0-beta-*", "System.Linq": "4.0.0", "System.Runtime": "4.0.20-beta-*", diff --git a/tests/src/JIT/config/benchmark/project.lock.json b/tests/src/JIT/config/benchmark/project.lock.json index 50f6919578..7f134e336d 100644 --- a/tests/src/JIT/config/benchmark/project.lock.json +++ b/tests/src/JIT/config/benchmark/project.lock.json @@ -74,6 +74,23 @@ "lib/dotnet/System.Collections.Concurrent.dll": {} } }, + "System.Collections.NonGeneric/4.0.0": { + "type": "package", + "dependencies": { + "System.Diagnostics.Debug": "4.0.10", + "System.Globalization": "4.0.10", + "System.Resources.ResourceManager": "4.0.0", + "System.Runtime": "4.0.20", + "System.Runtime.Extensions": "4.0.10", + "System.Threading": "4.0.10" + }, + "compile": { + "ref/dotnet/System.Collections.NonGeneric.dll": {} + }, + "runtime": { + "lib/dotnet/System.Collections.NonGeneric.dll": {} + } + }, "System.Console/4.0.0-beta-23516": { "type": "package", "dependencies": { @@ -761,6 +778,23 @@ "lib/dotnet/System.Collections.Concurrent.dll": {} } }, + "System.Collections.NonGeneric/4.0.0": { + "type": "package", + "dependencies": { + "System.Diagnostics.Debug": "4.0.10", + "System.Globalization": "4.0.10", + "System.Resources.ResourceManager": "4.0.0", + "System.Runtime": "4.0.20", + "System.Runtime.Extensions": "4.0.10", + "System.Threading": "4.0.10" + }, + "compile": { + "ref/dotnet/System.Collections.NonGeneric.dll": {} + }, + "runtime": { + "lib/dotnet/System.Collections.NonGeneric.dll": {} + } + }, "System.Console/4.0.0-beta-23516": { "type": "package", "dependencies": { @@ -1451,6 +1485,23 @@ "lib/dotnet/System.Collections.Concurrent.dll": {} } }, + "System.Collections.NonGeneric/4.0.0": { + "type": "package", + "dependencies": { + "System.Diagnostics.Debug": "4.0.10", + "System.Globalization": "4.0.10", + "System.Resources.ResourceManager": "4.0.0", + "System.Runtime": "4.0.20", + "System.Runtime.Extensions": "4.0.10", + "System.Threading": "4.0.10" + }, + "compile": { + "ref/dotnet/System.Collections.NonGeneric.dll": {} + }, + "runtime": { + "lib/dotnet/System.Collections.NonGeneric.dll": {} + } + }, "System.Console/4.0.0-beta-23516": { "type": "package", "dependencies": { @@ -2194,6 +2245,38 @@ "System.Collections.Concurrent.nuspec" ] }, + "System.Collections.NonGeneric/4.0.0": { + "type": "package", + "serviceable": true, + "sha512": "rVgwrFBMkmp8LI6GhAYd6Bx+2uLIXjRfNg6Ie+ASfX8ESuh9e2HNxFy2yh1MPIXZq3OAYa+0mmULVwpnEC6UDA==", + "files": [ + "lib/dotnet/System.Collections.NonGeneric.dll", + "lib/MonoAndroid10/_._", + "lib/MonoTouch10/_._", + "lib/net46/System.Collections.NonGeneric.dll", + "lib/xamarinios10/_._", + "lib/xamarinmac20/_._", + "ref/dotnet/de/System.Collections.NonGeneric.xml", + "ref/dotnet/es/System.Collections.NonGeneric.xml", + "ref/dotnet/fr/System.Collections.NonGeneric.xml", + "ref/dotnet/it/System.Collections.NonGeneric.xml", + "ref/dotnet/ja/System.Collections.NonGeneric.xml", + "ref/dotnet/ko/System.Collections.NonGeneric.xml", + "ref/dotnet/ru/System.Collections.NonGeneric.xml", + "ref/dotnet/System.Collections.NonGeneric.dll", + "ref/dotnet/System.Collections.NonGeneric.xml", + "ref/dotnet/zh-hans/System.Collections.NonGeneric.xml", + "ref/dotnet/zh-hant/System.Collections.NonGeneric.xml", + "ref/MonoAndroid10/_._", + "ref/MonoTouch10/_._", + "ref/net46/System.Collections.NonGeneric.dll", + "ref/xamarinios10/_._", + "ref/xamarinmac20/_._", + "System.Collections.NonGeneric.4.0.0.nupkg", + "System.Collections.NonGeneric.4.0.0.nupkg.sha512", + "System.Collections.NonGeneric.nuspec" + ] + }, "System.Console/4.0.0-beta-23516": { "type": "package", "serviceable": true, @@ -3417,6 +3500,7 @@ "Microsoft.DotNet.xunit.performance >= 1.0.0-alpha-build0027", "Microsoft.DotNet.xunit.performance.analysis >= 1.0.0-alpha-build0027", "Microsoft.DotNet.xunit.performance.runner.Windows >= 1.0.0-alpha-build0027", + "System.Collections.NonGeneric >= 4.0.0", "System.Console >= 4.0.0-beta-*", "System.Linq >= 4.0.0", "System.Runtime >= 4.0.20-beta-*", -- cgit v1.2.3