Novacoin/uint160.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 uint160 : base_uint
  26     {
  27         #region Access to internal representation
  28         new protected int nWidth
  29         {
  30             get { return base.nWidth; }
  31             private set { base.nWidth = value; }
  32         }
  33         new protected uint[] pn
  34         {
  35             get { return base.pn; }
  36             private set { base.pn = value; }
  37         }
  38         #endregion
  39
  40         #region Constructors
  41         public uint160()
  42         {
  43             nWidth = 5;
  44             pn = new uint[nWidth];
  45         }
  46
  47         public uint160(uint160 b) : this()
  48         {
  49             for (int i = 0; i < nWidth; i++)
  50             {
  51                 pn[i] = b.pn[i];
  52             }
  53         }
  54
  55
  56         public uint160(ulong n) : this()
  57         {
  58             pn[0] = (uint)n;
  59             pn[1] = (uint)(n >> 32);
  60             for (int i = 2; i < nWidth; i++)
  61             {
  62                 pn[i] = 0;
  63             }
  64         }
  65
  66         public uint160(byte[] bytes) : this()
  67         {
  68             Contract.Requires<ArgumentException>(bytes.Length == 20, "Incorrect array length");
  69             pn = Interop.ToUInt32Array(bytes);
  70         }
  71
  72         public uint160(string hex) : this()
  73         {
  74             Contract.Requires<ArgumentException>(hex.Length == 40, "Incorrect string");
  75             var bytes = Interop.ReverseBytes(Interop.HexToArray(hex));
  76             pn = Interop.ToUInt32Array(bytes);
  77         }
  78         #endregion
  79
  80         #region Cast operators
  81         public static implicit operator uint160(byte[] bytes)
  82         {
  83             return new uint160(bytes);
  84         }
  85
  86         public static implicit operator uint160(ulong n)
  87         {
  88             return new uint160(n);
  89         }
  90         #endregion
  91
  92         #region Bitwise operations
  93         public static uint160 operator ~(uint160 a)
  94         {
  95             var ret = new uint160();
  96             for (int i = 0; i < a.nWidth; i++)
  97             {
  98                 ret.pn[i] = ~a.pn[i];
  99             }
 100             return ret;
 101         }
 102
 103         public static uint160 operator ^(uint160 a, uint160 b)
 104         {
 105             var result = new uint160();
 106             result.pn = new uint[a.nWidth];
 107             for (int i = 0; i < result.nWidth; i++)
 108             {
 109                 result.pn[i] = a.pn[i] ^ b.pn[i];
 110             }
 111             return result;
 112         }
 113
 114         public static uint160 operator &(uint160 a, uint160 b)
 115         {
 116             var result = new uint160();
 117             result.pn = new uint[a.nWidth];
 118             for (int i = 0; i < result.nWidth; i++)
 119             {
 120                 result.pn[i] = a.pn[i] & b.pn[i];
 121             }
 122             return result;
 123         }
 124
 125         public static uint160 operator |(uint160 a, uint160 b)
 126         {
 127             var result = new uint160();
 128             result.pn = new uint[a.nWidth];
 129             for (int i = 0; i < result.nWidth; i++)
 130             {
 131                 result.pn[i] = a.pn[i] | b.pn[i];
 132             }
 133             return result;
 134         }
 135         #endregion
 136
 137         #region Basic arithmetics
 138         public static uint160 operator +(uint160 a, uint160 b)
 139         {
 140             var result = new uint160();
 141             ulong carry = 0;
 142             for (int i = 0; i < result.nWidth; i++)
 143             {
 144                 ulong n = carry + a.pn[i] + b.pn[i];
 145                 result.pn[i] = (uint)(n & 0xffffffff);
 146                 carry = n >> 32;
 147             }
 148             return result;
 149         }
 150
 151         public static uint160 operator +(uint160 a, ulong b)
 152         {
 153             return a + new uint160(b);
 154         }
 155
 156         public static uint160 operator -(uint160 a, uint160 b)
 157         {
 158             return a + (-b);
 159         }
 160
 161         public static uint160 operator -(uint160 a, ulong b)
 162         {
 163             return a - new uint160(b);
 164         }
 165
 166         public static uint160 operator -(uint160 a)
 167         {
 168             var ret = new uint160();
 169             for (int i = 0; i < a.nWidth; i++)
 170             {
 171                 ret.pn[i] = ~a.pn[i];
 172             }
 173             ret++;
 174             return ret;
 175         }
 176
 177
 178         public static uint160 operator ++(uint160 a)
 179         {
 180             int i = 0;
 181             while (++a.pn[i] == 0 && i < a.nWidth - 1)
 182             {
 183                 i++;
 184             }
 185             return a;
 186         }
 187
 188         public static uint160 operator --(uint160 a)
 189         {
 190             int i = 0;
 191             while (--a.pn[i] == uint.MaxValue && i < a.nWidth - 1)
 192             {
 193                 i++;
 194             }
 195             return a;
 196         }
 197
 198         public static uint160 operator /(uint160 a, uint divisor)
 199         {
 200             var result = new uint160();
 201
 202             ulong r = 0;
 203             int i = a.nWidth;
 204
 205             while (i-- > 0)
 206             {
 207                 r <<= 32;
 208                 r |= a.pn[i];
 209                 result.pn[i] = (uint)(r / divisor);
 210                 r %= divisor;
 211             }
 212
 213             return result;
 214         }
 215
 216         public static uint160 operator *(uint160 a, uint multiplier)
 217         {
 218             var result = new uint160();
 219
 220             ulong c = 0;
 221             uint i = 0;
 222
 223             do
 224             {
 225                 c += a.pn[i] * (ulong)multiplier;
 226                 result.pn[i] = (uint)c;
 227                 c >>= 32;
 228             } while (++i < result.nWidth);
 229
 230             return result;
 231         }
 232
 233         public static uint160 operator *(uint160 a, uint160 b)
 234         {
 235             if (!a || !b)
 236             {
 237                 // Multiplication by zero results with zero.
 238                 return 0;
 239             }
 240             else if (b.bits <= 32)
 241             {
 242                 if (b.pn[0] == 1)
 243                 {
 244                     // If right is 1 then return left operand value
 245                     return a;
 246                 }
 247
 248                 return a * b.pn[0];
 249             }
 250             else if (a.bits <= 32)
 251             {
 252                 if (a.pn[0] == 1)
 253                 {
 254                     // If left is 1 then return right operand value
 255                     return b;
 256                 }
 257
 258                 return a * b.pn[0];
 259             }
 260
 261             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 262             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 263
 264             uint160 result = new uint160();
 265
 266             uint[] left = a.pn.Take(m).ToArray();
 267             uint[] right = b.pn.Take(n).ToArray();
 268
 269             for (int i = 0; i < m; ++i)
 270             {
 271                 uint ai = left[i];
 272                 int k = i;
 273
 274                 ulong temp = 0;
 275                 for (int j = 0; j < n; ++j)
 276                 {
 277                     temp = temp + ((ulong)ai) * right[j] + result.pn[k];
 278                     result.pn[k++] = (uint)temp;
 279                     temp >>= 32;
 280                 }
 281
 282                 while (temp != 0)
 283                 {
 284                     temp += result.pn[k];
 285                     result.pn[k++] = (uint)temp;
 286                     temp >>= 32;
 287                 }
 288             }
 289
 290             return result;
 291         }
 292
 293         public static uint operator %(uint160 a, uint divisor)
 294         {
 295             ulong r = 0;
 296             int i = a.nWidth;
 297
 298             while (i-- > 0)
 299             {
 300                 r <<= 32;
 301                 r |= a.pn[i];
 302                 r %= divisor;
 303             }
 304
 305             return (uint)r;
 306         }
 307
 308         public static uint160 operator /(uint160 a, uint160 b)
 309         {
 310             if (b.bits <= 32)
 311             {
 312                 return a / b.Low32;
 313             }
 314
 315             uint160 result = new uint160();
 316
 317             uint[] quotient;
 318             uint[] remainder_value;
 319
 320             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 321             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 322
 323             BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value);
 324
 325             quotient.CopyTo(result.pn, 0);
 326
 327             return result;
 328         }
 329
 330         public static uint160 operator %(uint160 a, uint160 b)
 331         {
 332             if (b.bits <= 32)
 333             {
 334                 return a % b.Low32;
 335             }
 336
 337             uint160 result = new uint160();
 338
 339             uint[] quotient;
 340             uint[] remainder_value;
 341
 342             int m = a.bits / 32 + (a.bits % 32 != 0 ? 1 : 0);
 343             int n = b.bits / 32 + (b.bits % 32 != 0 ? 1 : 0);
 344
 345             BignumHelper.DivModUnsigned(a.pn.Take(m).ToArray(), b.pn.Take(n).ToArray(), out quotient, out remainder_value);
 346
 347             remainder_value.CopyTo(result.pn, 0);
 348
 349             return result;
 350
 351         }
 352
 353         #endregion
 354
 355         #region Shift
 356         public static uint160 operator <<(uint160 a, int shift)
 357         {
 358             var result = new uint160();
 359             int k = shift / 32;
 360             shift = shift % 32;
 361
 362             for (int i = 0; i < a.nWidth; i++)
 363             {
 364                 if (i + k + 1 < a.nWidth && shift != 0)
 365                 {
 366                     result.pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
 367                 }
 368
 369                 if (i + k < a.nWidth)
 370                 {
 371                     result.pn[i + k] |= (a.pn[i] << shift);
 372                 }
 373             }
 374
 375             return result;
 376         }
 377
 378         public static uint160 operator >>(uint160 a, int shift)
 379         {
 380             var result = new uint160();
 381             int k = shift / 32;
 382             shift = shift % 32;
 383
 384             for (int i = 0; i < a.nWidth; i++)
 385             {
 386                 if (i - k - 1 >= 0 && shift != 0)
 387                 {
 388                     result.pn[i - k - 1] |= (a.pn[i] << (32 - shift));
 389                 }
 390
 391                 if (i - k >= 0)
 392                 {
 393                     result.pn[i - k] |= (a.pn[i] >> shift);
 394                 }
 395             }
 396
 397             return result;
 398         }
 399         #endregion
 400     }
 401 }