Novacoin/BignumHelper.cs

   1 \feff/* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   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.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16
  17 namespace Novacoin
  18 {
  19     internal class BignumHelper
  20     {
  21         const ulong Base = 0x100000000;
  22
  23         #region Division function from Mono framework
  24
  25         public static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r)
  26         {
  27             int m = u.Length;
  28             int n = v.Length;
  29
  30             if (n <= 1)
  31             {
  32                 //  Divide by single digit
  33                 //
  34                 ulong rem = 0;
  35                 uint v0 = v[0];
  36                 q = new uint[m];
  37                 r = new uint[1];
  38
  39                 for (int j = m - 1; j >= 0; j--)
  40                 {
  41                     rem *= Base;
  42                     rem += u[j];
  43
  44                     ulong div = rem / v0;
  45                     rem -= div * v0;
  46                     q[j] = (uint)div;
  47                 }
  48                 r[0] = (uint)rem;
  49             }
  50             else if (m >= n)
  51             {
  52                 int shift = GetNormalizeShift(v[n - 1]);
  53
  54                 uint[] un = new uint[m + 1];
  55                 uint[] vn = new uint[n];
  56
  57                 Normalize(u, m, un, shift);
  58                 Normalize(v, n, vn, shift);
  59
  60                 q = new uint[m - n + 1];
  61                 r = null;
  62
  63                 //  Main division loop
  64                 //
  65                 for (int j = m - n; j >= 0; j--)
  66                 {
  67                     ulong rr, qq;
  68                     int i;
  69
  70                     rr = Base * un[j + n] + un[j + n - 1];
  71                     qq = rr / vn[n - 1];
  72                     rr -= qq * vn[n - 1];
  73
  74                     for (;;)
  75                     {
  76                         // Estimate too big ?
  77                         //
  78                         if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2])))
  79                         {
  80                             qq--;
  81                             rr += (ulong)vn[n - 1];
  82                             if (rr < Base)
  83                                 continue;
  84                         }
  85                         break;
  86                     }
  87
  88
  89                     //  Multiply and subtract
  90                     //
  91                     long b = 0;
  92                     long t = 0;
  93                     for (i = 0; i < n; i++)
  94                     {
  95                         ulong p = vn[i] * qq;
  96                         t = (long)un[i + j] - (long)(uint)p - b;
  97                         un[i + j] = (uint)t;
  98                         p >>= 32;
  99                         t >>= 32;
 100                         b = (long)p - t;
 101                     }
 102                     t = (long)un[j + n] - b;
 103                     un[j + n] = (uint)t;
 104
 105                     //  Store the calculated value
 106                     //
 107                     q[j] = (uint)qq;
 108
 109                     //  Add back vn[0..n] to un[j..j+n]
 110                     //
 111                     if (t < 0)
 112                     {
 113                         q[j]--;
 114                         ulong c = 0;
 115                         for (i = 0; i < n; i++)
 116                         {
 117                             c = (ulong)vn[i] + un[j + i] + c;
 118                             un[j + i] = (uint)c;
 119                             c >>= 32;
 120                         }
 121                         c += (ulong)un[j + n];
 122                         un[j + n] = (uint)c;
 123                     }
 124                 }
 125
 126                 Unnormalize(un, out r, shift);
 127             }
 128             else
 129             {
 130                 q = new uint[] { 0 };
 131                 r = u;
 132             }
 133         }
 134
 135         private static int GetNormalizeShift(uint value)
 136         {
 137             int shift = 0;
 138
 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; }
 144
 145             return shift;
 146         }
 147
 148         private static void Unnormalize(uint[] un, out uint[] r, int shift)
 149         {
 150             int length = un.Length;
 151             r = new uint[length];
 152
 153             if (shift > 0)
 154             {
 155                 int lshift = 32 - shift;
 156                 uint carry = 0;
 157                 for (int i = length - 1; i >= 0; i--)
 158                 {
 159                     uint uni = un[i];
 160                     r[i] = (uni >> shift) | carry;
 161                     carry = (uni << lshift);
 162                 }
 163             }
 164             else
 165             {
 166                 for (int i = 0; i < length; i++)
 167                 {
 168                     r[i] = un[i];
 169                 }
 170             }
 171         }
 172
 173         private static void Normalize(uint[] u, int l, uint[] un, int shift)
 174         {
 175             uint carry = 0;
 176             int i;
 177             if (shift > 0)
 178             {
 179                 int rshift = 32 - shift;
 180                 for (i = 0; i < l; i++)
 181                 {
 182                     uint ui = u[i];
 183                     un[i] = (ui << shift) | carry;
 184                     carry = ui >> rshift;
 185                 }
 186             }
 187             else
 188             {
 189                 for (i = 0; i < l; i++)
 190                 {
 191                     un[i] = u[i];
 192                 }
 193             }
 194
 195             while (i < un.Length)
 196             {
 197                 un[i++] = 0;
 198             }
 199
 200             if (carry != 0)
 201             {
 202                 un[l] = carry;
 203             }
 204         }
 205         #endregion
 206
 207     }
 208 }