Novacoin/uint256.cs

   1 \feff/**
   2  *  Novacoin classes library
   3  *  Copyright (C) 2015 Alex D. (balthazar.ad@gmail.com)
   4
   5  *  This program is free software: you can redistribute it and/or modify
   6  *  it under the terms of the GNU Affero General Public License as
   7  *  published by the Free Software Foundation, either version 3 of the
   8  *  License, or (at your option) any later version.
   9
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU Affero General Public License for more details.
  14
  15  *  You should have received a copy of the GNU Affero General Public License
  16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 using System;
  20 using System.Diagnostics.Contracts;
  21 using System.Linq;
  22
  23 namespace Novacoin
  24 {
  25     public class uint256 : base_uint
  26     {
  27         #region Access to internal representation
  28         new protected int nWidth {
  29             get { return base.nWidth; }
  30             private set { base.nWidth = value; }
  31         }
  32         new protected uint[] pn {
  33             get { return base.pn; }
  34             private set { base.pn = value; }
  35         }
  36         #endregion
  37
  38         #region Constructors
  39         public uint256()
  40         {
  41             nWidth = 8;
  42             pn = new uint[nWidth];
  43         }
  44
  45         public uint256(uint256 b) : this()
  46         {
  47             for (int i = 0; i < nWidth; i++)
  48             {
  49                 pn[i] = b.pn[i];
  50             }
  51         }
  52
  53         public uint256(ulong n) : this()
  54         {
  55             pn[0] = (uint)n;
  56             pn[1] = (uint)(n >> 32);
  57             for (int i = 2; i < nWidth; i++)
  58             {
  59                 pn[i] = 0;
  60             }
  61         }
  62
  63         public uint256(byte[] bytes) : this()
  64         {
  65             Contract.Requires<ArgumentException>(bytes.Length == 32, "Incorrect array length");
  66
  67             pn = Interop.ToUInt32Array(bytes);
  68         }
  69
  70         public uint256(string hex) : this()
  71         {
  72             Contract.Requires<ArgumentException>(hex.Length == 64, "Incorrect string");
  73
  74             var bytes = Interop.ReverseBytes(Interop.HexToArray(hex));
  75             pn = Interop.ToUInt32Array(bytes);
  76         }
  77         #endregion
  78
  79         #region Cast operators
  80         public static implicit operator uint256(byte[] bytes)
  81         {
  82             return new uint256(bytes);
  83         }
  84
  85         public static implicit operator uint256(ulong n)
  86         {
  87             return new uint256(n);
  88         }
  89         #endregion
  90
  91         #region Compact representation
  92         /// <summary>
  93         /// Compact representation of unsigned 256bit numbers.
  94         ///
  95         /// N = (-1^sign) * m * 256^(exp-3)
  96         ///
  97         /// http://bitcoin.stackexchange.com/questions/30467/what-are-the-equations-to-convert-between-bits-and-difficulty
  98         /// </summary>
  99         public uint Compact
 100         {
 101             get
 102             {
 103                 int nSize = (bits + 7) / 8;
 104                 uint nCompact = 0;
 105                 if (nSize <= 3)
 106                     nCompact = ((uint)Low64) << 8 * (3 - nSize);
 107                 else
 108                 {
 109                     uint256 bn = this >> 8 * (nSize - 3);
 110                     nCompact = (uint)bn.Low64;
 111                 }
 112
 113                 if ((nCompact & 0x00800000) != 0)
 114                 {
 115                     nCompact >>= 8;
 116                     nSize++;
 117                 }
 118
 119                 Contract.Assert((nCompact & ~0x007fffff) == 0);
 120                 Contract.Assert(nSize < 256);
 121
 122                 nCompact |= (uint)nSize << 24;
 123                 nCompact |= 0;
 124
 125                 return nCompact;
 126             }
 127             set {
 128                 int nSize = (int)value >> 24;
 129                 uint nWord = value & 0x007fffff;
 130
 131                 uint256 i;
 132
 133                 if (nSize <= 3)
 134                 {
 135                     nWord >>= 8 * (3 - nSize);
 136                     i = new uint256(nWord);
 137                 }
 138                 else
 139                 {
 140                     i = new uint256(nWord);
 141                     i <<= 8 * (nSize - 3);
 142                 }
 143
 144                 pn = i.pn;
 145             }
 146         }
 147         #endregion
 148
 149         #region Bitwise operations
 150         public static uint256 operator ~(uint256 a)
 151         {
 152             var ret = new uint256();
 153             for (int i = 0; i < a.nWidth; i++)
 154             {
 155                 ret.pn[i] = ~a.pn[i];
 156             }
 157             return ret;
 158         }
 159
 160         public static uint256 operator ^(uint256 a, uint256 b)
 161         {
 162             var result = new uint256();
 163             result.pn = new uint[a.nWidth];
 164             for (int i = 0; i < result.nWidth; i++)
 165             {
 166                 result.pn[i] = a.pn[i] ^ b.pn[i];
 167             }
 168             return result;
 169         }
 170
 171         public static uint256 operator &(uint256 a, uint256 b)
 172         {
 173             var result = new uint256();
 174             result.pn = new uint[a.nWidth];
 175             for (int i = 0; i < result.nWidth; i++)
 176             {
 177                 result.pn[i] = a.pn[i] & b.pn[i];
 178             }
 179             return result;
 180         }
 181
 182         public static uint256 operator |(uint256 a, uint256 b)
 183         {
 184             var result = new uint256();
 185             result.pn = new uint[a.nWidth];
 186             for (int i = 0; i < result.nWidth; i++)
 187             {
 188                 result.pn[i] = a.pn[i] | b.pn[i];
 189             }
 190             return result;
 191         }
 192         #endregion
 193
 194         #region Basic arithmetics
 195         public static uint256 operator -(uint256 a)
 196         {
 197             var ret = new uint256();
 198             for (int i = 0; i < a.nWidth; i++)
 199             {
 200                 ret.pn[i] = ~a.pn[i];
 201             }
 202             ret++;
 203             return ret;
 204         }
 205
 206         public static uint256 operator ++(uint256 a)
 207         {
 208             int i = 0;
 209             while (++a.pn[i] == 0 && i < a.nWidth - 1)
 210             {
 211                 i++;
 212             }
 213             return a;
 214         }
 215
 216         public static uint256 operator --(uint256 a)
 217         {
 218             int i = 0;
 219             while (--a.pn[i] == uint.MaxValue && i < a.nWidth - 1)
 220             {
 221                 i++;
 222             }
 223             return a;
 224         }
 225
 226
 227         public static uint256 operator +(uint256 a, uint256 b)
 228         {
 229             var result = new uint256();
 230             ulong carry = 0;
 231             for (int i = 0; i < result.nWidth; i++)
 232             {
 233                 ulong n = carry + a.pn[i] + b.pn[i];
 234                 result.pn[i] = (uint)(n & 0xffffffff);
 235                 carry = n >> 32;
 236             }
 237             return result;
 238         }
 239
 240         public static uint256 operator +(uint256 a, ulong b)
 241         {
 242             return a + new uint256(b);
 243         }
 244
 245         public static uint256 operator -(uint256 a, uint256 b)
 246         {
 247             return a + (-b);
 248         }
 249
 250         public static uint256 operator -(uint256 a, ulong b)
 251         {
 252             return a - new uint256(b);
 253         }
 254
 255         public static uint256 operator /(uint256 a, uint b)
 256         {
 257             var result = new uint256();
 258
 259             ulong r = 0;
 260             int i = a.nWidth;
 261
 262             while (i-- > 0)
 263             {
 264                 r <<= 32;
 265                 r |= a.pn[i];
 266                 result.pn[i] = (uint)(r / b);
 267                 r %= b;
 268             }
 269
 270             return result;
 271         }
 272
 273         public static uint256 operator *(uint256 a, uint b)
 274         {
 275             var result = new uint256();
 276
 277             ulong c = 0;
 278             uint i = 0;
 279
 280             do
 281             {
 282                 c += a.pn[i] * (ulong)b;
 283                 result.pn[i] = (uint)c;
 284                 c >>= 32;
 285             } while (++i < result.nWidth);
 286
 287             return result;
 288         }
 289
 290         public static uint256 operator *(uint256 a, uint256 b)
 291         {
 292             if (!a || !b)
 293             {
 294                 // Multiplication by zero results with zero.
 295                 return 0;
 296             }
 297             else if (b.bits <= 32)
 298             {
 299                 if (b.pn[0] == 1)
 300                 {
 301                     // If right is 1 then return left operand value
 302                     return a;
 303                 }
 304
 305                 return a * b.pn[0];
 306             }
 307             else if (a.bits <= 32)
 308             {
 309                 if (a.pn[0] == 1)
 310                 {
 311                     // If left is 1 then return right operand value
 312                     return b;
 313                 }
 314
 315                 return a * b.pn[0];
 316             }
 317
 318             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 319             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 320
 321             uint256 result = new uint256();
 322
 323             uint[] left = a.pn.Take(m).ToArray();
 324             uint[] right = b.pn.Take(n).ToArray();
 325
 326             for (int i = 0; i < m; ++i)
 327             {
 328                 uint ai = left[i];
 329                 int k = i;
 330
 331                 ulong temp = 0;
 332                 for (int j = 0; j < n; ++j)
 333                 {
 334                     temp = temp + ((ulong)ai) * right[j] + result.pn[k];
 335                     result.pn[k++] = (uint)temp;
 336                     temp >>= 32;
 337                 }
 338
 339                 while (temp != 0)
 340                 {
 341                     temp += result.pn[k];
 342                     result.pn[k++] = (uint)temp;
 343                     temp >>= 32;
 344                 }
 345             }
 346
 347             return result;
 348         }
 349
 350         public static uint operator %(uint256 a, uint b)
 351         {
 352             ulong r = 0;
 353             int i = a.nWidth;
 354
 355             while (i-- > 0)
 356             {
 357                 r <<= 32;
 358                 r |= a.pn[i];
 359                 r %= b;
 360             }
 361
 362             return (uint)r;
 363         }
 364
 365         public static uint256 operator /(uint256 a, uint256 b)
 366         {
 367             if (b.bits <= 32)
 368             {
 369                 return a / b.Low32;
 370             }
 371
 372             uint256 result = new uint256();
 373
 374             uint[] quotient;
 375             uint[] remainder_value;
 376
 377             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 378             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 379
 380             BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value);
 381
 382             quotient.CopyTo(result.pn, 0);
 383
 384             return result;
 385         }
 386
 387         public static uint256 operator %(uint256 a, uint256 b)
 388         {
 389             if (b.bits <= 32)
 390             {
 391                 return a % b.Low32;
 392             }
 393
 394             uint256 result = new uint256();
 395
 396             uint[] quotient;
 397             uint[] remainder_value;
 398
 399             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 400             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 401
 402             BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value);
 403
 404             remainder_value.CopyTo(result.pn, 0);
 405
 406             return result;
 407
 408         }
 409         #endregion
 410
 411         #region Shift
 412         public static uint256 operator <<(uint256 a, int shift)
 413         {
 414             var result = new uint256();
 415             int k = shift / 32;
 416             shift = shift % 32;
 417
 418             for (int i = 0; i < a.nWidth; i++)
 419             {
 420                 if (i + k + 1 < a.nWidth && shift != 0)
 421                 {
 422                     result.pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
 423                 }
 424
 425                 if (i + k < a.nWidth)
 426                 {
 427                     result.pn[i + k] |= (a.pn[i] << shift);
 428                 }
 429             }
 430
 431             return result;
 432         }
 433
 434         public static uint256 operator >>(uint256 a, int shift)
 435         {
 436             var result = new uint256();
 437             int k = shift / 32;
 438             shift = shift % 32;
 439
 440             for (int i = 0; i < a.nWidth; i++)
 441             {
 442                 if (i - k - 1 >= 0 && shift != 0)
 443                 {
 444                     result.pn[i - k - 1] |= (a.pn[i] << (32 - shift));
 445                 }
 446
 447                 if (i - k >= 0)
 448                 {
 449                     result.pn[i - k] |= (a.pn[i] >> shift);
 450                 }
 451             }
 452
 453             return result;
 454         }
 455         #endregion
 456     }
 457 }