mcs/class/System.Numerics/System.Numerics/BigInteger.cs

   1 //
   2 // System.Numerics.BigInteger
   3 //
   4 // Rodrigo Kumpera (rkumpera@novell.com)
   5
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28 using System;\r
  29 using System.Collections.Generic;\r
  30 using System.Diagnostics;\r
  31 using System.Diagnostics.CodeAnalysis;\r
  32 using System.Globalization;\r
  33 using System.Text;\r
  34
  35 /*
  36 Optimization
  37         Have proper popcount function for IsPowerOfTwo
  38         Use unsafe ops to avoid bounds check
  39         CoreAdd could avoid some resizes by checking for equal sized array that top overflow
  40 */\r
  41 namespace System.Numerics {\r
  42         public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
  43         {
  44                 //LSB on [0]
  45                 readonly uint[] data;
  46                 readonly short sign;
  47
  48                 static readonly uint[] ZERO = new uint [1];
  49                 static readonly uint[] ONE = new uint [1] { 1 };
  50
  51                 BigInteger (short sign, uint[] data)
  52                 {
  53                         this.sign = sign;
  54                         this.data = data;
  55                 }
  56
  57                 public BigInteger (int value)
  58                 {
  59                         if (value == 0) {
  60                                 sign = 0;
  61                                 data = ZERO;
  62                         } else if (value > 0) {
  63                                 sign = 1;
  64                                 data = new uint[] { (uint) value };
  65                         } else {
  66                                 sign = -1;
  67                                 data = new uint[1] { (uint)-value };
  68                         }
  69                 }
  70
  71                 [CLSCompliantAttribute (false)]
  72                 public BigInteger (uint value)
  73                 {
  74                         if (value == 0) {
  75                                 sign = 0;
  76                                 data = ZERO;
  77                         } else {
  78                                 sign = 1;
  79                                 data = new uint [1] { value };
  80                         }
  81                 }
  82
  83                 public BigInteger (long value)
  84                 {
  85                         if (value == 0) {
  86                                 sign = 0;
  87                                 data = ZERO;
  88                         } else if (value > 0) {
  89                                 sign = 1;
  90                                 uint low = (uint)value;
  91                                 uint high = (uint)(value >> 32);
  92
  93                                 data = new uint [high != 0 ? 2 : 1];
  94                                 data [0] = low;
  95                                 if (high != 0)
  96                                         data [1] = high;
  97                         } else {
  98                                 sign = -1;
  99                                 value = -value;
 100                                 uint low = (uint)value;
 101                                 uint high = (uint)((ulong)value >> 32);
 102
 103                                 data = new uint [high != 0 ? 2 : 1];
 104                                 data [0] = low;
 105                                 if (high != 0)
 106                                         data [1] = high;
 107                         }
 108                 }
 109
 110                 [CLSCompliantAttribute (false)]
 111                 public BigInteger (ulong value)
 112                 {
 113                         if (value == 0) {
 114                                 sign = 0;
 115                                 data = ZERO;
 116                         } else {
 117                                 sign = 1;
 118                                 uint low = (uint)value;
 119                                 uint high = (uint)(value >> 32);
 120
 121                                 data = new uint [high != 0 ? 2 : 1];
 122                                 data [0] = low;
 123                                 if (high != 0)
 124                                         data [1] = high;
 125                         }
 126                 }
 127
 128                 [CLSCompliantAttribute (false)]
 129                 public BigInteger (byte[] value)
 130                 {
 131                         if (value == null)
 132                                 throw new ArgumentNullException ("value");
 133
 134                         int len = value.Length;
 135
 136                         if (len == 0 || (len == 1 && value [0] == 0)) {
 137                                 sign = 0;
 138                                 data = ZERO;
 139                                 return;
 140                         }
 141
 142                         if ((value [len - 1] & 0x80) != 0)
 143                                 sign = -1;
 144                         else
 145                                 sign = 1;
 146
 147                         if (sign == 1) {
 148                                 while (value [len - 1] == 0)
 149                                         --len;
 150
 151                                 int full_words, size;
 152                                 full_words = size = len / 4;
 153                                 if ((len & 0x3) != 0)
 154                                         ++size;
 155
 156                                 data = new uint [size];
 157                                 int j = 0;
 158                                 for (int i = 0; i < full_words; ++i) {
 159                                         data [i] =      (uint)value [j++] |
 160                                                                 (uint)(value [j++] << 8) |
 161                                                                 (uint)(value [j++] << 16) |
 162                                                                 (uint)(value [j++] << 24);
 163                                 }
 164                                 size = len & 0x3;
 165                                 if (size > 0) {
 166                                         int idx = data.Length - 1;
 167                                         for (int i = 0; i < size; ++i)
 168                                                 data [idx] |= (uint)(value [j++] << (i * 8));
 169                                 }
 170                         } else {
 171                                 int full_words, size;
 172                                 full_words = size = len / 4;
 173                                 if ((len & 0x3) != 0)
 174                                         ++size;
 175
 176                                 data = new uint [size];
 177
 178                                 uint word, borrow = 1;
 179                                 ulong sub = 0;
 180                                 int j = 0;
 181
 182                                 for (int i = 0; i < full_words; ++i) {
 183                                         word =  (uint)value [j++] |
 184                                                         (uint)(value [j++] << 8) |
 185                                                         (uint)(value [j++] << 16) |
 186                                                         (uint)(value [j++] << 24);
 187
 188                                         sub = (ulong)word - borrow;
 189                                         word = (uint)sub;
 190                                         borrow = (uint)(sub >> 32) & 0x1u;
 191                                         data [i] = ~word;
 192                                 }
 193                                 size = len & 0x3;
 194
 195                                 if (size > 0) {
 196                                         word = 0;
 197                                         uint store_mask = 0;
 198                                         for (int i = 0; i < size; ++i) {
 199                                                 word |= (uint)(value [j++] << (i * 8));
 200                                                 store_mask = (store_mask << 8) | 0xFF;
 201                                         }
 202
 203                                         sub = word - borrow;
 204                                         word = (uint)sub;
 205                                         borrow = (uint)(sub >> 32) & 0x1u;
 206
 207                                         data [data.Length - 1] = ~word & store_mask;
 208                                 }
 209                                 if (borrow != 0) //FIXME I believe this can't happen, can someone write a test for it?
 210                                         throw new Exception ("non zero final carry");
 211                         }
 212
 213                 }
 214
 215                 public bool IsEven {
 216                         get { return (data [0] & 0x1) == 0; }
 217                 }
 218
 219                 public bool IsOne {
 220                         get { return sign == 1 && data.Length == 1 && data [0] == 1; }
 221                 }
 222
 223
 224                 //Gem from Hacker's Delight
 225                 //Returns the number of bits set in @x
 226                 static int PopulationCount (uint x)
 227                 {
 228                         x = x - ((x >> 1) & 0x55555555);
 229                         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 230                         x = (x + (x >> 4)) & 0x0F0F0F0F;
 231                         x = x + (x >> 8);
 232                         x = x + (x >> 16);
 233                         return (int)(x & 0x0000003F);
 234                 }
 235
 236                 public bool IsPowerOfTwo {
 237                         get {
 238                                 bool foundBit = false;
 239                                 if (sign != 1)
 240                                         return false;
 241                                 //This function is pop count == 1 for positive numbers
 242                                 for (int i = 0; i < data.Length; ++i) {
 243                                         int p = PopulationCount (data [i]);
 244                                         if (p > 0) {
 245                                                 if (p > 1 || foundBit)
 246                                                         return false;
 247                                                 foundBit = true;
 248                                         }
 249                                 }
 250                                 return foundBit;
 251                         }
 252                 }
 253
 254                 public bool IsZero {
 255                         get { return sign == 0; }
 256                 }
 257
 258                 public int Sign {
 259                         get { return sign; }
 260                 }
 261
 262                 public static BigInteger MinusOne {
 263                         get { return new BigInteger (-1, ONE); }
 264                 }
 265
 266                 public static BigInteger One {
 267                         get { return new BigInteger (1, ONE); }
 268                 }
 269
 270                 public static BigInteger Zero {
 271                         get { return new BigInteger (0, ZERO); }
 272                 }
 273
 274                 public static explicit operator int (BigInteger value)
 275                 {
 276                         if (value.data.Length > 1)
 277                                 throw new OverflowException ();
 278                         uint data = value.data [0];
 279
 280                         if (value.sign == 1) {
 281                                 if (data > (uint)int.MaxValue)
 282                                         throw new OverflowException ();
 283                                 return (int)data;
 284                         } else if (value.sign == -1) {
 285                                 if (data > 0x80000000u)
 286                                         throw new OverflowException ();
 287                                 return -(int)data;
 288                         }
 289
 290                         return 0;
 291                 }
 292
 293                 [CLSCompliantAttribute (false)]
 294                 public static explicit operator uint (BigInteger value)
 295                 {
 296                         if (value.data.Length > 1 || value.sign == -1)
 297                                 throw new OverflowException ();
 298                         return value.data [0];
 299                 }
 300
 301                 public static explicit operator long (BigInteger value)
 302                 {
 303                         if (value.sign == 0)
 304                                 return 0;
 305
 306                         if (value.data.Length > 2)
 307                                 throw new OverflowException ();
 308
 309                         uint low = value.data [0];
 310
 311                         if (value.data.Length == 1) {
 312                                 if (value.sign == 1)
 313                                         return (long)low;
 314                                 long res = (long)low;
 315                                 return -res;
 316                         }
 317
 318                         uint high = value.data [1];
 319
 320                         if (value.sign == 1) {
 321                                 if (high >= 0x80000000u)
 322                                         throw new OverflowException ();
 323                                 return (((long)high) << 32) | low;
 324                         }
 325
 326                         if (high > 0x80000000u)
 327                                 throw new OverflowException ();
 328
 329                         return - ((((long)high) << 32) | (long)low);
 330                 }
 331
 332                 [CLSCompliantAttribute (false)]
 333                 public static explicit operator ulong (BigInteger value)
 334                 {
 335                         if (value.data.Length > 2 || value.sign == -1)
 336                                 throw new OverflowException ();
 337
 338                         uint low = value.data [0];
 339                         if (value.data.Length == 1)
 340                                 return low;
 341
 342                         uint high = value.data [1];
 343                         return (((ulong)high) << 32) | low;
 344                 }
 345
 346
 347                 public static implicit operator BigInteger (int value)
 348                 {
 349                         return new BigInteger (value);
 350                 }
 351
 352                 [CLSCompliantAttribute (false)]
 353                 public static implicit operator BigInteger (uint value)
 354                 {
 355                         return new BigInteger (value);
 356                 }
 357
 358                 public static implicit operator BigInteger (long value)
 359                 {
 360                         return new BigInteger (value);
 361                 }
 362
 363                 [CLSCompliantAttribute (false)]
 364                 public static implicit operator BigInteger (ulong value)
 365                 {
 366                         return new BigInteger (value);
 367                 }
 368
 369                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 370                 {
 371                         if (left.sign == 0)
 372                                 return right;
 373                         if (right.sign == 0)
 374                                 return left;
 375
 376                         if (left.sign == right.sign)
 377                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 378
 379                         int r = CoreCompare (left.data, right.data);
 380
 381                         if (r == 0)
 382                                 return new BigInteger (0, ZERO);
 383
 384                         if (r > 0) //left > right
 385                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 386
 387                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 388                 }
 389
 390                 public static bool operator< (BigInteger left, BigInteger right)
 391                 {
 392                         return Compare (left, right) < 0;
 393                 }
 394
 395                 public static bool operator< (BigInteger left, long right)
 396                 {
 397                         return left.CompareTo (right) < 0;
 398                 }
 399
 400
 401                 public static bool operator< (long left, BigInteger right)
 402                 {
 403                         return right.CompareTo (left) > 0;
 404                 }
 405
 406
 407                 [CLSCompliantAttribute (false)]
 408                 public static bool operator< (BigInteger left, ulong right)
 409                 {
 410                         return left.CompareTo (right) < 0;
 411                 }
 412
 413                 [CLSCompliantAttribute (false)]
 414                 public static bool operator< (ulong left, BigInteger right)
 415                 {
 416                         return right.CompareTo (left) > 0;
 417                 }
 418
 419                 public static bool operator<= (BigInteger left, BigInteger right)
 420                 {
 421                         return Compare (left, right) <= 0;
 422                 }
 423
 424                 public static bool operator<= (BigInteger left, long right)
 425                 {
 426                         return left.CompareTo (right) <= 0;
 427                 }
 428
 429                 public static bool operator<= (long left, BigInteger right)
 430                 {
 431                         return right.CompareTo (left) >= 0;
 432                 }
 433
 434                 [CLSCompliantAttribute (false)]
 435                 public static bool operator<= (BigInteger left, ulong right)
 436                 {
 437                         return left.CompareTo (right) <= 0;
 438                 }
 439
 440                 [CLSCompliantAttribute (false)]
 441                 public static bool operator<= (ulong left, BigInteger right)
 442                 {
 443                         return right.CompareTo (left) >= 0;
 444                 }
 445
 446                 public static bool operator> (BigInteger left, BigInteger right)
 447                 {
 448                         return Compare (left, right) > 0;
 449                 }
 450
 451                 public static bool operator> (BigInteger left, long right)
 452                 {
 453                         return left.CompareTo (right) > 0;
 454                 }
 455
 456                 public static bool operator> (long left, BigInteger right)
 457                 {
 458                         return right.CompareTo (left) < 0;
 459                 }
 460
 461                 [CLSCompliantAttribute (false)]
 462                 public static bool operator> (BigInteger left, ulong right)
 463                 {
 464                         return left.CompareTo (right) > 0;
 465                 }
 466
 467                 [CLSCompliantAttribute (false)]
 468                 public static bool operator> (ulong left, BigInteger right)
 469                 {
 470                         return right.CompareTo (left) < 0;
 471                 }
 472
 473                 public static bool operator>= (BigInteger left, BigInteger right)
 474                 {
 475                         return Compare (left, right) >= 0;
 476                 }
 477
 478                 public static bool operator>= (BigInteger left, long right)
 479                 {
 480                         return left.CompareTo (right) >= 0;
 481                 }
 482
 483                 public static bool operator>= (long left, BigInteger right)
 484                 {
 485                         return right.CompareTo (left) <= 0;
 486                 }
 487
 488                 [CLSCompliantAttribute (false)]
 489                 public static bool operator>= (BigInteger left, ulong right)
 490                 {
 491                         return left.CompareTo (right) >= 0;
 492                 }
 493
 494                 [CLSCompliantAttribute (false)]
 495                 public static bool operator>= (ulong left, BigInteger right)
 496                 {
 497                         return right.CompareTo (left) <= 0;
 498                 }
 499
 500                 public static bool operator== (BigInteger left, BigInteger right)
 501                 {
 502                         return Compare (left, right) == 0;
 503                 }
 504
 505                 public static bool operator== (BigInteger left, long right)
 506                 {
 507                         return left.CompareTo (right) == 0;
 508                 }
 509
 510                 public static bool operator== (long left, BigInteger right)
 511                 {
 512                         return right.CompareTo (left) == 0;
 513                 }
 514
 515                 [CLSCompliantAttribute (false)]
 516                 public static bool operator== (BigInteger left, ulong right)
 517                 {
 518                         return left.CompareTo (right) == 0;
 519                 }
 520
 521                 [CLSCompliantAttribute (false)]
 522                 public static bool operator== (ulong left, BigInteger right)
 523                 {
 524                         return right.CompareTo (left) == 0;
 525                 }
 526
 527                 public static bool operator!= (BigInteger left, BigInteger right)
 528                 {
 529                         return Compare (left, right) != 0;
 530                 }
 531
 532                 public static bool operator!= (BigInteger left, long right)
 533                 {
 534                         return left.CompareTo (right) != 0;
 535                 }
 536
 537                 public static bool operator!= (long left, BigInteger right)
 538                 {
 539                         return right.CompareTo (left) != 0;
 540                 }
 541
 542                 [CLSCompliantAttribute (false)]
 543                 public static bool operator!= (BigInteger left, ulong right)
 544                 {
 545                         return left.CompareTo (right) != 0;
 546                 }
 547
 548                 [CLSCompliantAttribute (false)]
 549                 public static bool operator!= (ulong left, BigInteger right)
 550                 {
 551                         return right.CompareTo (left) != 0;
 552                 }
 553
 554                 public override bool Equals (object obj)
 555                 {
 556                         if (!(obj is BigInteger))
 557                                 return false;
 558                         return Equals ((BigInteger)obj);
 559                 }
 560
 561                 public bool Equals (BigInteger other)
 562                 {
 563                         if (sign != other.sign)
 564                                 return false;
 565                         if (data.Length != other.data.Length)
 566                                 return false;
 567                         for (int i = 0; i < data.Length; ++i) {
 568                                 if (data [i] != other.data [i])
 569                                         return false;
 570                         }
 571                         return true;
 572                 }
 573
 574                 public bool Equals (long other)
 575                 {
 576                         return CompareTo (other) == 0;
 577                 }
 578
 579                 [CLSCompliantAttribute (false)]
 580                 public bool Equals (ulong other)
 581                 {
 582                         return CompareTo (other) == 0;
 583                 }
 584
 585                 public override int GetHashCode ()
 586                 {
 587                         uint hash = (uint)(sign * 0x01010101u);
 588
 589                         for (int i = 0; i < data.Length; ++i)
 590                                 hash ^= data [i];
 591                         return (int)hash;
 592                 }
 593
 594                 public static BigInteger Add (BigInteger left, BigInteger right)
 595                 {
 596                         return left + right;
 597                 }
 598
 599                 public int CompareTo (object obj)
 600                 {
 601                         if (obj == null)
 602                                 return 1;
 603
 604                         if (!(obj is BigInteger))
 605                                 return -1;
 606
 607                         return Compare (this, (BigInteger)obj);
 608                 }
 609
 610                 public int CompareTo (BigInteger other)
 611                 {
 612                         return Compare (this, other);
 613                 }
 614
 615                 [CLSCompliantAttribute (false)]
 616                 public int CompareTo (ulong other)
 617                 {
 618                         if (sign < 0)
 619                                 return -1;
 620                         if (sign == 0)
 621                                 return other == 0 ? 0 : -1;
 622
 623                         if (data.Length > 2)
 624                                 return 1;
 625
 626                         uint high = (uint)(other >> 32);
 627                         uint low = (uint)other;
 628
 629                         return LongCompare (low, high);
 630                 }
 631
 632                 int LongCompare (uint low, uint high)
 633                 {
 634                         uint h = 0;
 635                         if (data.Length > 1)
 636                                 h = data [1];
 637
 638                         if (h > high)
 639                                 return 1;
 640                         if (h < high)
 641                                 return -1;
 642
 643                         uint l = data [0];
 644
 645                         if (l > low)
 646                                 return 1;
 647                         if (l < low)
 648                                 return -1;
 649
 650                         return 0;
 651                 }
 652
 653                 public int CompareTo (long other)
 654                 {
 655                         int ls = sign;
 656                         int rs = Math.Sign (other);
 657
 658                         if (ls != rs)
 659                                 return ls > rs ? 1 : -1;
 660
 661                         if (ls == 0)
 662                                 return 0;
 663
 664                         if (data.Length > 2)
 665                                 return -sign;
 666
 667                         if (other < 0)
 668                                 other = -other;
 669                         uint low = (uint)other;
 670                         uint high = (uint)((ulong)other >> 32);
 671
 672                         int r = LongCompare (low, high);
 673                         if (ls == -1)
 674                                 r = -r;
 675
 676                         return r;
 677                 }
 678
 679                 public static int Compare (BigInteger left, BigInteger right)
 680                 {
 681                         int ls = left.sign;
 682                         int rs = right.sign;
 683
 684                         if (ls != rs)
 685                                 return ls > rs ? 1 : -1;
 686
 687                         int r = CoreCompare (left.data, right.data);
 688                         if (ls < 0)
 689                                 r = -r;
 690                         return r;
 691                 }
 692
 693
 694                 static int TopByte (uint x)
 695                 {
 696                         if ((x & 0xFFFF0000u) != 0) {
 697                                 if ((x & 0xFF000000u) != 0)
 698                                         return 4;
 699                                 return 3;
 700                         }
 701                         if ((x & 0xFF00u) != 0)
 702                                 return 2;
 703                         return 1;
 704                 }
 705
 706                 static int FirstNonFFByte (uint word)
 707                 {
 708                         if ((word & 0xFF000000u) != 0xFF000000u)
 709                                 return 4;
 710                         else if ((word & 0xFF0000u) != 0xFF0000u)
 711                                 return 3;
 712                         else if ((word & 0xFF00u) != 0xFF00u)
 713                                 return 2;
 714                         return 1;
 715                 }
 716
 717                 public byte[] ToByteArray ()
 718                 {
 719                         if (sign == 0)
 720                                 return new byte [1];
 721
 722                         //number of bytes not counting upper word
 723                         int bytes = (data.Length - 1) * 4;
 724                         bool needExtraZero = false;
 725
 726                         uint topWord = data [data.Length - 1];
 727                         int extra;
 728
 729                         //if the topmost bit is set we need an extra
 730                         if (sign == 1) {
 731                                 extra = TopByte (topWord);
 732                                 uint mask = 0x80u << ((extra - 1) * 8);
 733                                 if ((topWord & mask) != 0) {
 734                                         needExtraZero = true;
 735                                 }
 736                         } else {
 737                                 extra = TopByte (topWord);
 738                         }
 739
 740                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
 741                         if (sign == 1) {
 742                                 int j = 0;
 743                                 int end = data.Length - 1;
 744                                 for (int i = 0; i < end; ++i) {
 745                                         uint word = data [i];
 746
 747                                         res [j++] = (byte)word;
 748                                         res [j++] = (byte)(word >> 8);
 749                                         res [j++] = (byte)(word >> 16);
 750                                         res [j++] = (byte)(word >> 24);
 751                                 }
 752                                 while (extra-- > 0) {
 753                                         res [j++] = (byte)topWord;
 754                                         topWord >>= 8;
 755                                 }
 756                         } else {
 757                                 int j = 0;
 758                                 int end = data.Length - 1;
 759
 760                                 uint carry = 1, word;
 761                                 ulong add;
 762                                 for (int i = 0; i < end; ++i) {
 763                                         word = data [i];
 764                                         add = (ulong)~word + carry;
 765                                         word = (uint)add;
 766                                         carry = (uint)(add >> 32);
 767
 768                                         res [j++] = (byte)word;
 769                                         res [j++] = (byte)(word >> 8);
 770                                         res [j++] = (byte)(word >> 16);
 771                                         res [j++] = (byte)(word >> 24);
 772                                 }
 773
 774                                 add = (ulong)~topWord + (carry);
 775                                 word = (uint)add;
 776                                 carry = (uint)(add >> 32);
 777                                 if (carry == 0) {
 778                                         int ex = FirstNonFFByte (word);
 779                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
 780                                         int to = ex + (needExtra ? 1 : 0);
 781
 782                                         if (to != extra)
 783                                                 res = Resize (res, bytes + to);
 784
 785                                         while (ex-- > 0) {
 786                                                 res [j++] = (byte)word;
 787                                                 word >>= 8;
 788                                         }
 789                                         if (needExtra)
 790                                                 res [j++] = 0xFF;
 791                                 } else {
 792                                         res = Resize (res, bytes + 5);
 793                                         res [j++] = (byte)word;
 794                                         res [j++] = (byte)(word >> 8);
 795                                         res [j++] = (byte)(word >> 16);
 796                                         res [j++] = (byte)(word >> 24);
 797                                         res [j++] = 0xFF;
 798                                 }
 799                         }
 800
 801                         return res;
 802                 }
 803
 804                 static byte[] Resize (byte[] v, int len)
 805                 {\r
 806                         byte[] res = new byte [len];\r
 807                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 808                         return res;\r
 809                 }
 810
 811                 static uint[] Resize (uint[] v, int len)
 812                 {
 813                         uint[] res = new uint [len];\r
 814                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 815                         return res;\r
 816                 }
 817
 818                 static uint[] CoreAdd (uint[] a, uint[] b)
 819                 {
 820                         if (a.Length < b.Length) {
 821                                 uint[] tmp = a;
 822                                 a = b;
 823                                 b = tmp;
 824                         }
 825
 826                         int bl = a.Length;
 827                         int sl = b.Length;
 828
 829                         uint[] res = new uint [bl];
 830
 831                         ulong sum = 0;
 832
 833                         int i = 0;
 834                         for (; i < sl; i++) {
 835                                 sum = sum + a [i] + b [i];
 836                                 res [i] = (uint)sum;
 837                                 sum >>= 32;
 838                         }
 839
 840                         for (; i < bl; i++) {
 841                                 sum = sum + a [i];
 842                                 res [i] = (uint)sum;
 843                                 sum >>= 32;
 844                         }
 845
 846                         if (sum != 0) {
 847                                 res = Resize (res, bl + 1);
 848                                 res [i] = (uint)sum;
 849                         }
 850
 851                         return res;
 852                 }
 853
 854                 /*invariant a > b*/
 855                 static uint[] CoreSub (uint[] a, uint[] b)
 856                 {
 857                         int bl = a.Length;
 858                         int sl = b.Length;
 859
 860                         Console.WriteLine ("bl {0} sl {1}", bl, sl);
 861
 862                         uint[] res = new uint [bl];
 863
 864                         ulong borrow = 0;
 865                         int i;
 866                         for (i = 0; i < sl; ++i) {
 867                                 borrow = (ulong)a [i] - b [i] - borrow;
 868
 869                                 Console.WriteLine ("a {0} b {1}", a[i], b [i]);
 870
 871                                 res [i] = (uint)borrow;
 872                                 borrow = (borrow >> 32) & 0x1;
 873                         }
 874
 875                         for (; i < bl; i++) {
 876                                 borrow = (ulong)a [i] - borrow;
 877                                 res [i] = (uint)borrow;
 878                                 borrow = (borrow >> 32) & 0x1;
 879                         }
 880
 881                         //remove extra zeroes
 882                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
 883                         if (i < bl - 1)
 884                                 res = Resize (res, i + 1);
 885
 886             return res;
 887                 }
 888
 889                 static int CoreCompare (uint[] a, uint[] b)
 890                 {
 891                         int     al = a.Length;
 892                         int bl = b.Length;
 893
 894                         if (al > bl)
 895                                 return 1;
 896                         if (bl > al)
 897                                 return -1;
 898
 899                         for (int i = al - 1; i >= 0; --i) {
 900                                 uint ai = a [i];
 901                                 uint bi = b [i];
 902                                 if (ai > bi)
 903                                         return 1;
 904                                 if (ai < bi)
 905                                         return -1;
 906                         }
 907                         return 0;
 908                 }
 909
 910         }
 911 }\r