From: CryptoManiac Date: Thu, 3 Sep 2015 17:03:14 +0000 (+0300) Subject: uint160 and uint256 division operations. X-Git-Url: https://git.novaco.in/?p=NovacoinLibrary.git;a=commitdiff_plain;h=14dcc623463c612772aa4a5dc20497d8661e3d0b uint160 and uint256 division operations. --- diff --git a/Novacoin/BignumHelper.cs b/Novacoin/BignumHelper.cs new file mode 100644 index 0000000..0741b26 --- /dev/null +++ b/Novacoin/BignumHelper.cs @@ -0,0 +1,208 @@ +/* **************************************************************************** + * + * Copyright (c) Microsoft Corporation. + * + * This source code is subject to terms and conditions of the Microsoft Public License. A + * copy of the license can be found in the License.html file at the root of this distribution. If + * you cannot locate the Microsoft Public License, please send an email to + * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound + * by the terms of the Microsoft Public License. + * + * You must not remove this notice, or any other, from this software. + * + * + * ***************************************************************************/ + + +namespace Novacoin +{ + internal class BignumHelper + { + const ulong Base = 0x100000000; + + #region Division function from Mono framework + + public static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r) + { + int m = u.Length; + int n = v.Length; + + if (n <= 1) + { + // Divide by single digit + // + ulong rem = 0; + uint v0 = v[0]; + q = new uint[m]; + r = new uint[1]; + + for (int j = m - 1; j >= 0; j--) + { + rem *= Base; + rem += u[j]; + + ulong div = rem / v0; + rem -= div * v0; + q[j] = (uint)div; + } + r[0] = (uint)rem; + } + else if (m >= n) + { + int shift = GetNormalizeShift(v[n - 1]); + + uint[] un = new uint[m + 1]; + uint[] vn = new uint[n]; + + Normalize(u, m, un, shift); + Normalize(v, n, vn, shift); + + q = new uint[m - n + 1]; + r = null; + + // Main division loop + // + for (int j = m - n; j >= 0; j--) + { + ulong rr, qq; + int i; + + rr = Base * un[j + n] + un[j + n - 1]; + qq = rr / vn[n - 1]; + rr -= qq * vn[n - 1]; + + for (;;) + { + // Estimate too big ? + // + if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2]))) + { + qq--; + rr += (ulong)vn[n - 1]; + if (rr < Base) + continue; + } + break; + } + + + // Multiply and subtract + // + long b = 0; + long t = 0; + for (i = 0; i < n; i++) + { + ulong p = vn[i] * qq; + t = (long)un[i + j] - (long)(uint)p - b; + un[i + j] = (uint)t; + p >>= 32; + t >>= 32; + b = (long)p - t; + } + t = (long)un[j + n] - b; + un[j + n] = (uint)t; + + // Store the calculated value + // + q[j] = (uint)qq; + + // Add back vn[0..n] to un[j..j+n] + // + if (t < 0) + { + q[j]--; + ulong c = 0; + for (i = 0; i < n; i++) + { + c = (ulong)vn[i] + un[j + i] + c; + un[j + i] = (uint)c; + c >>= 32; + } + c += (ulong)un[j + n]; + un[j + n] = (uint)c; + } + } + + Unnormalize(un, out r, shift); + } + else + { + q = new uint[] { 0 }; + r = u; + } + } + + private static int GetNormalizeShift(uint value) + { + int shift = 0; + + if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; } + if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; } + if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; } + if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; } + if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; } + + return shift; + } + + private static void Unnormalize(uint[] un, out uint[] r, int shift) + { + int length = un.Length; + r = new uint[length]; + + if (shift > 0) + { + int lshift = 32 - shift; + uint carry = 0; + for (int i = length - 1; i >= 0; i--) + { + uint uni = un[i]; + r[i] = (uni >> shift) | carry; + carry = (uni << lshift); + } + } + else + { + for (int i = 0; i < length; i++) + { + r[i] = un[i]; + } + } + } + + private static void Normalize(uint[] u, int l, uint[] un, int shift) + { + uint carry = 0; + int i; + if (shift > 0) + { + int rshift = 32 - shift; + for (i = 0; i < l; i++) + { + uint ui = u[i]; + un[i] = (ui << shift) | carry; + carry = ui >> rshift; + } + } + else + { + for (i = 0; i < l; i++) + { + un[i] = u[i]; + } + } + + while (i < un.Length) + { + un[i++] = 0; + } + + if (carry != 0) + { + un[l] = carry; + } + } + #endregion + + } +} diff --git a/Novacoin/Novacoin.csproj b/Novacoin/Novacoin.csproj index 1990b60..ce2b90b 100644 --- a/Novacoin/Novacoin.csproj +++ b/Novacoin/Novacoin.csproj @@ -108,6 +108,7 @@ + diff --git a/Novacoin/base_uint.cs b/Novacoin/base_uint.cs index 8b36b12..d7b8f4c 100644 --- a/Novacoin/base_uint.cs +++ b/Novacoin/base_uint.cs @@ -81,7 +81,7 @@ namespace Novacoin /// /// Zero or the position of highest non-zero bit plus one. /// - protected int bits + public int bits { get { diff --git a/Novacoin/uint160.cs b/Novacoin/uint160.cs index c051406..eccfe95 100644 --- a/Novacoin/uint160.cs +++ b/Novacoin/uint160.cs @@ -18,6 +18,7 @@ using System; using System.Diagnostics.Contracts; +using System.Linq; namespace Novacoin { @@ -244,6 +245,51 @@ namespace Novacoin return (uint)r; } + public static uint160 operator /(uint160 a, uint160 b) + { + if (b.bits <= 32) + { + return a / b.Low32; + } + + uint160 result = new uint160(); + + uint[] quotient; + uint[] remainder_value; + + int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0); + int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0); + + BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value); + + quotient.CopyTo(result.pn, 0); + + return result; + } + + public static uint160 operator %(uint160 a, uint160 b) + { + if (b.bits <= 32) + { + return a % b.Low32; + } + + uint160 result = new uint160(); + + uint[] quotient; + uint[] remainder_value; + + int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0); + int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0); + + BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value); + + remainder_value.CopyTo(result.pn, 0); + + return result; + + } + #endregion #region Shift diff --git a/Novacoin/uint256.cs b/Novacoin/uint256.cs index dfaebea..606acf0 100644 --- a/Novacoin/uint256.cs +++ b/Novacoin/uint256.cs @@ -18,6 +18,7 @@ using System; using System.Diagnostics.Contracts; +using System.Linq; namespace Novacoin { @@ -251,7 +252,7 @@ namespace Novacoin return a - new uint256(b); } - public static uint256 operator /(uint256 a, uint divisor) + public static uint256 operator /(uint256 a, uint b) { var result = new uint256(); @@ -262,14 +263,14 @@ namespace Novacoin { r <<= 32; r |= a.pn[i]; - result.pn[i] = (uint)(r / divisor); - r %= divisor; + result.pn[i] = (uint)(r / b); + r %= b; } return result; } - public static uint256 operator *(uint256 a, uint multiplier) + public static uint256 operator *(uint256 a, uint b) { var result = new uint256(); @@ -278,7 +279,7 @@ namespace Novacoin do { - c += a.pn[i] * (ulong)multiplier; + c += a.pn[i] * (ulong)b; result.pn[i] = (uint)c; c >>= 32; } while (++i < result.nWidth); @@ -286,7 +287,7 @@ namespace Novacoin return result; } - public static uint operator %(uint256 a, uint divisor) + public static uint operator %(uint256 a, uint b) { ulong r = 0; int i = a.nWidth; @@ -295,43 +296,57 @@ namespace Novacoin { r <<= 32; r |= a.pn[i]; - r %= divisor; + r %= b; } return (uint)r; } - public static uint256 operator /(uint256 a, uint256 divisor) + public static uint256 operator /(uint256 a, uint256 b) { - if (divisor.bits <= 32) + if (b.bits <= 32) { - return a / divisor.Low32; + return a / b.Low32; } - return Divide(a, divisor)[0]; + uint256 result = new uint256(); + + uint[] quotient; + uint[] remainder_value; + + int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0); + int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0); + + BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value); + + quotient.CopyTo(result.pn, 0); + + return result; } - public static uint256 operator %(uint256 a, uint256 divisor) + public static uint256 operator %(uint256 a, uint256 b) { - if (divisor.bits <= 32) + if (b.bits <= 32) { - return a % divisor.Low32; + return a % b.Low32; } - return Divide(a, divisor)[1]; - } - #endregion + uint256 result = new uint256(); - public static uint256[] Divide(uint256 bi1, uint256 bi2) - { - // STUB! + uint[] quotient; + uint[] remainder_value; - uint256[] ret = new uint256[2] { 0, 0 }; + int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0); + int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0); - return ret; - } + BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value); + remainder_value.CopyTo(result.pn, 0); + return result; + + } + #endregion #region Shift public static uint256 operator <<(uint256 a, int shift)