1 \feff/* ****************************************************************************
3 * Copyright (c) Microsoft Corporation.
5 * This source code is subject to terms and conditions of the Microsoft Public License. A
6 * copy of the license can be found in the License.html file at the root of this distribution. If
7 * you cannot locate the Microsoft Public License, please send an email to
8 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
9 * by the terms of the Microsoft Public License.
11 * You must not remove this notice, or any other, from this software.
14 * ***************************************************************************/
19 internal class BignumHelper
21 const ulong Base = 0x100000000;
23 #region Division function from Mono framework
25 public static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r)
32 // Divide by single digit
39 for (int j = m - 1; j >= 0; j--)
52 int shift = GetNormalizeShift(v[n - 1]);
54 uint[] un = new uint[m + 1];
55 uint[] vn = new uint[n];
57 Normalize(u, m, un, shift);
58 Normalize(v, n, vn, shift);
60 q = new uint[m - n + 1];
65 for (int j = m - n; j >= 0; j--)
70 rr = Base * un[j + n] + un[j + n - 1];
78 if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2])))
81 rr += (ulong)vn[n - 1];
89 // Multiply and subtract
93 for (i = 0; i < n; i++)
96 t = (long)un[i + j] - (long)(uint)p - b;
102 t = (long)un[j + n] - b;
105 // Store the calculated value
109 // Add back vn[0..n] to un[j..j+n]
115 for (i = 0; i < n; i++)
117 c = (ulong)vn[i] + un[j + i] + c;
121 c += (ulong)un[j + n];
126 Unnormalize(un, out r, shift);
130 q = new uint[] { 0 };
135 private static int GetNormalizeShift(uint value)
139 if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
140 if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
141 if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
142 if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
143 if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
148 private static void Unnormalize(uint[] un, out uint[] r, int shift)
150 int length = un.Length;
151 r = new uint[length];
155 int lshift = 32 - shift;
157 for (int i = length - 1; i >= 0; i--)
160 r[i] = (uni >> shift) | carry;
161 carry = (uni << lshift);
166 for (int i = 0; i < length; i++)
173 private static void Normalize(uint[] u, int l, uint[] un, int shift)
179 int rshift = 32 - shift;
180 for (i = 0; i < l; i++)
183 un[i] = (ui << shift) | carry;
184 carry = ui >> rshift;
189 for (i = 0; i < l; i++)
195 while (i < un.Length)