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<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];
  68                                 if (value == int.MinValue)
  69                                         data [0] = 0x80000000u;
  70                                 else
  71                                          data [0] = (uint)-value;
  72                         }
  73                 }
  74
  75                 [CLSCompliantAttribute (false)]
  76                 public BigInteger (uint value)
  77                 {
  78                         if (value == 0) {
  79                                 sign = 0;
  80                                 data = ZERO;
  81                         } else {
  82                                 sign = 1;
  83                                 data = new uint [1] { value };
  84                         }
  85                 }
  86
  87                 public BigInteger (long value)
  88                 {
  89                         if (value == 0) {
  90                                 sign = 0;
  91                                 data = ZERO;
  92                         } else if (value > 0) {
  93                                 sign = 1;
  94                                 uint low = (uint)value;
  95                                 uint high = (uint)(value >> 32);
  96
  97                                 data = new uint [high != 0 ? 2 : 1];
  98                                 data [0] = low;
  99                                 if (high != 0)
 100                                         data [1] = high;
 101                         } else {
 102                                 sign = -1;
 103
 104                                 if (value == long.MinValue) {
 105                                         data = new uint [2] { 0, 0x80000000u };
 106                                 } else {
 107                                         value = -value;
 108                                         uint low = (uint)value;
 109                                         uint high = (uint)((ulong)value >> 32);
 110
 111                                         data = new uint [high != 0 ? 2 : 1];
 112                                         data [0] = low;
 113                                         if (high != 0)
 114                                                 data [1] = high;
 115                                 }
 116                         }
 117                 }
 118
 119                 [CLSCompliantAttribute (false)]
 120                 public BigInteger (ulong value)
 121                 {
 122                         if (value == 0) {
 123                                 sign = 0;
 124                                 data = ZERO;
 125                         } else {
 126                                 sign = 1;
 127                                 uint low = (uint)value;
 128                                 uint high = (uint)(value >> 32);
 129
 130                                 data = new uint [high != 0 ? 2 : 1];
 131                                 data [0] = low;
 132                                 if (high != 0)
 133                                         data [1] = high;
 134                         }
 135                 }
 136
 137                 [CLSCompliantAttribute (false)]
 138                 public BigInteger (byte[] value)
 139                 {
 140                         if (value == null)
 141                                 throw new ArgumentNullException ("value");
 142
 143                         int len = value.Length;
 144
 145                         if (len == 0 || (len == 1 && value [0] == 0)) {
 146                                 sign = 0;
 147                                 data = ZERO;
 148                                 return;
 149                         }
 150
 151                         if ((value [len - 1] & 0x80) != 0)
 152                                 sign = -1;
 153                         else
 154                                 sign = 1;
 155
 156                         if (sign == 1) {
 157                                 while (value [len - 1] == 0)
 158                                         --len;
 159
 160                                 int full_words, size;
 161                                 full_words = size = len / 4;
 162                                 if ((len & 0x3) != 0)
 163                                         ++size;
 164
 165                                 data = new uint [size];
 166                                 int j = 0;
 167                                 for (int i = 0; i < full_words; ++i) {
 168                                         data [i] =      (uint)value [j++] |
 169                                                                 (uint)(value [j++] << 8) |
 170                                                                 (uint)(value [j++] << 16) |
 171                                                                 (uint)(value [j++] << 24);
 172                                 }
 173                                 size = len & 0x3;
 174                                 if (size > 0) {
 175                                         int idx = data.Length - 1;
 176                                         for (int i = 0; i < size; ++i)
 177                                                 data [idx] |= (uint)(value [j++] << (i * 8));
 178                                 }
 179                         } else {
 180                                 int full_words, size;
 181                                 full_words = size = len / 4;
 182                                 if ((len & 0x3) != 0)
 183                                         ++size;
 184
 185                                 data = new uint [size];
 186
 187                                 uint word, borrow = 1;
 188                                 ulong sub = 0;
 189                                 int j = 0;
 190
 191                                 for (int i = 0; i < full_words; ++i) {
 192                                         word =  (uint)value [j++] |
 193                                                         (uint)(value [j++] << 8) |
 194                                                         (uint)(value [j++] << 16) |
 195                                                         (uint)(value [j++] << 24);
 196
 197                                         sub = (ulong)word - borrow;
 198                                         word = (uint)sub;
 199                                         borrow = (uint)(sub >> 32) & 0x1u;
 200                                         data [i] = ~word;
 201                                 }
 202                                 size = len & 0x3;
 203
 204                                 if (size > 0) {
 205                                         word = 0;
 206                                         uint store_mask = 0;
 207                                         for (int i = 0; i < size; ++i) {
 208                                                 word |= (uint)(value [j++] << (i * 8));
 209                                                 store_mask = (store_mask << 8) | 0xFF;
 210                                         }
 211
 212                                         sub = word - borrow;
 213                                         word = (uint)sub;
 214                                         borrow = (uint)(sub >> 32) & 0x1u;
 215
 216                                         data [data.Length - 1] = ~word & store_mask;
 217                                 }
 218                                 if (borrow != 0) //FIXME I believe this can't happen, can someone write a test for it?
 219                                         throw new Exception ("non zero final carry");
 220                         }
 221
 222                 }
 223
 224                 public bool IsEven {
 225                         get { return (data [0] & 0x1) == 0; }
 226                 }
 227
 228                 public bool IsOne {
 229                         get { return sign == 1 && data.Length == 1 && data [0] == 1; }
 230                 }
 231
 232
 233                 //Gem from Hacker's Delight
 234                 //Returns the number of bits set in @x
 235                 static int PopulationCount (uint x)
 236                 {
 237                         x = x - ((x >> 1) & 0x55555555);
 238                         x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 239                         x = (x + (x >> 4)) & 0x0F0F0F0F;
 240                         x = x + (x >> 8);
 241                         x = x + (x >> 16);
 242                         return (int)(x & 0x0000003F);
 243                 }
 244
 245                 public bool IsPowerOfTwo {
 246                         get {
 247                                 bool foundBit = false;
 248                                 if (sign != 1)
 249                                         return false;
 250                                 //This function is pop count == 1 for positive numbers
 251                                 for (int i = 0; i < data.Length; ++i) {
 252                                         int p = PopulationCount (data [i]);
 253                                         if (p > 0) {
 254                                                 if (p > 1 || foundBit)
 255                                                         return false;
 256                                                 foundBit = true;
 257                                         }
 258                                 }
 259                                 return foundBit;
 260                         }
 261                 }
 262
 263                 public bool IsZero {
 264                         get { return sign == 0; }
 265                 }
 266
 267                 public int Sign {
 268                         get { return sign; }
 269                 }
 270
 271                 public static BigInteger MinusOne {
 272                         get { return new BigInteger (-1, ONE); }
 273                 }
 274
 275                 public static BigInteger One {
 276                         get { return new BigInteger (1, ONE); }
 277                 }
 278
 279                 public static BigInteger Zero {
 280                         get { return new BigInteger (0, ZERO); }
 281                 }
 282
 283                 public static explicit operator int (BigInteger value)
 284                 {
 285                         if (value.data.Length > 1)
 286                                 throw new OverflowException ();
 287                         uint data = value.data [0];
 288
 289                         if (value.sign == 1) {
 290                                 if (data > (uint)int.MaxValue)
 291                                         throw new OverflowException ();
 292                                 return (int)data;
 293                         } else if (value.sign == -1) {
 294                                 if (data > 0x80000000u)
 295                                         throw new OverflowException ();
 296                                 if (data == 0x80000000u)
 297                                         return int.MinValue;
 298                                 return -(int)data;
 299                         }
 300
 301                         return 0;
 302                 }
 303
 304                 [CLSCompliantAttribute (false)]
 305                 public static explicit operator uint (BigInteger value)
 306                 {
 307                         if (value.data.Length > 1 || value.sign == -1)
 308                                 throw new OverflowException ();
 309                         return value.data [0];
 310                 }
 311
 312                 public static explicit operator long (BigInteger value)
 313                 {
 314                         if (value.sign == 0)
 315                                 return 0;
 316
 317                         if (value.data.Length > 2)
 318                                 throw new OverflowException ();
 319
 320                         uint low = value.data [0];
 321
 322                         if (value.data.Length == 1) {
 323                                 if (value.sign == 1)
 324                                         return (long)low;
 325                                 long res = (long)low;
 326                                 return -res;
 327                         }
 328
 329                         uint high = value.data [1];
 330
 331                         if (value.sign == 1) {
 332                                 if (high >= 0x80000000u)
 333                                         throw new OverflowException ();
 334                                 return (((long)high) << 32) | low;
 335                         }
 336
 337                         if (high > 0x80000000u)
 338                                 throw new OverflowException ();
 339
 340                         if (high == 0x80000000u) {
 341                                 if (low != 0)
 342                                         throw new OverflowException ();
 343                                 return long.MinValue;
 344                         }
 345
 346                         return - ((((long)high) << 32) | (long)low);
 347                 }
 348
 349                 [CLSCompliantAttribute (false)]
 350                 public static explicit operator ulong (BigInteger value)
 351                 {
 352                         if (value.data.Length > 2 || value.sign == -1)
 353                                 throw new OverflowException ();
 354
 355                         uint low = value.data [0];
 356                         if (value.data.Length == 1)
 357                                 return low;
 358
 359                         uint high = value.data [1];
 360                         return (((ulong)high) << 32) | low;
 361                 }
 362
 363
 364                 public static implicit operator BigInteger (int value)
 365                 {
 366                         return new BigInteger (value);
 367                 }
 368
 369                 [CLSCompliantAttribute (false)]
 370                 public static implicit operator BigInteger (uint value)
 371                 {
 372                         return new BigInteger (value);
 373                 }
 374
 375                 public static implicit operator BigInteger (long value)
 376                 {
 377                         return new BigInteger (value);
 378                 }
 379
 380                 [CLSCompliantAttribute (false)]
 381                 public static implicit operator BigInteger (ulong value)
 382                 {
 383                         return new BigInteger (value);
 384                 }
 385
 386                 public static BigInteger operator+ (BigInteger left, BigInteger right)
 387                 {
 388                         if (left.sign == 0)
 389                                 return right;
 390                         if (right.sign == 0)
 391                                 return left;
 392
 393                         if (left.sign == right.sign)
 394                                 return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 395
 396                         int r = CoreCompare (left.data, right.data);
 397
 398                         if (r == 0)
 399                                 return new BigInteger (0, ZERO);
 400
 401                         if (r > 0) //left > right
 402                                 return new BigInteger (left.sign, CoreSub (left.data, right.data));
 403
 404                         return new BigInteger (right.sign, CoreSub (right.data, left.data));
 405                 }
 406
 407                 public static bool operator< (BigInteger left, BigInteger right)
 408                 {
 409                         return Compare (left, right) < 0;
 410                 }
 411
 412                 [CLSCompliantAttribute (false)]
 413                 public static bool operator< (BigInteger left, ulong right)
 414                 {
 415                         return left.CompareTo (right) < 0;
 416                 }
 417
 418                 public static bool operator<= (BigInteger left, BigInteger right)
 419                 {
 420                         return Compare (left, right) <= 0;
 421                 }
 422
 423                 [CLSCompliantAttribute (false)]
 424                 public static bool operator<= (BigInteger left, ulong right)
 425                 {
 426                         return left.CompareTo (right) <= 0;
 427                 }
 428
 429                 public static bool operator> (BigInteger left, BigInteger right)
 430                 {
 431                         return Compare (left, right) > 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                 public static bool operator>= (BigInteger left, BigInteger right)
 441                 {
 442                         return Compare (left, right) >= 0;
 443                 }
 444
 445                 [CLSCompliantAttribute (false)]
 446                 public static bool operator>= (BigInteger left, ulong right)
 447                 {
 448                         return left.CompareTo (right) >= 0;
 449                 }
 450
 451                 public static bool operator== (BigInteger left, BigInteger right)
 452                 {
 453                         return Compare (left, right) == 0;
 454                 }
 455
 456                 [CLSCompliantAttribute (false)]
 457                 public static bool operator== (BigInteger left, ulong right)
 458                 {
 459                         return left.CompareTo (right) == 0;
 460                 }
 461
 462                 public static bool operator!= (BigInteger left, BigInteger right)
 463                 {
 464                         return Compare (left, right) != 0;
 465                 }
 466
 467                 [CLSCompliantAttribute (false)]
 468                 public static bool operator!= (BigInteger left, ulong right)
 469                 {
 470                         return left.CompareTo (right) != 0;
 471                 }
 472
 473                 public override bool Equals (object obj)
 474                 {
 475                         if (!(obj is BigInteger))
 476                                 return false;
 477                         return Equals ((BigInteger)obj);
 478                 }
 479
 480                 public bool Equals (BigInteger other)
 481                 {
 482                         if (sign != other.sign)
 483                                 return false;
 484                         if (data.Length != other.data.Length)
 485                                 return false;
 486                         for (int i = 0; i < data.Length; ++i) {
 487                                 if (data [i] != other.data [i])
 488                                         return false;
 489                         }
 490                         return true;
 491                 }
 492
 493                 [CLSCompliantAttribute (false)]
 494                 public bool Equals (ulong other)
 495                 {
 496                         return CompareTo (other) == 0;
 497                 }
 498
 499                 public override int GetHashCode ()
 500                 {
 501                         uint hash = (uint)(sign * 0x01010101u);
 502
 503                         for (int i = 0; i < data.Length; ++i)
 504                                 hash ^= data [i];
 505                         return (int)hash;
 506                 }
 507
 508                 public static BigInteger Add (BigInteger left, BigInteger right)
 509                 {
 510                         return left + right;
 511                 }
 512
 513                 public int CompareTo (BigInteger other)
 514                 {
 515                         return Compare (this, other);
 516                 }
 517
 518                 [CLSCompliantAttribute (false)]
 519                 public int CompareTo (ulong other)
 520                 {
 521                         if (sign < 0)
 522                                 return -1;
 523                         if (sign == 0)
 524                                 return other == 0 ? 0 : -1;
 525
 526                         if (data.Length > 2)
 527                                 return 1;
 528
 529                         uint oh = (uint)(other >> 32);
 530                         uint h = 0;
 531                         if (data.Length > 1)
 532                                 h = data [1];
 533
 534                         if (h > oh)
 535                                 return 1;
 536                         if (h < oh)
 537                                 return -1;
 538
 539                         uint ol = (uint)other;
 540                         uint l = data [0];
 541
 542                         if (l > ol)
 543                                 return 1;
 544                         if (l < ol)
 545                                 return -1;
 546
 547                         return 0;
 548                 }
 549
 550                 public static int Compare (BigInteger left, BigInteger right)
 551                 {
 552                         int ls = left.sign;
 553                         int rs = right.sign;
 554
 555                         if (ls != rs)
 556                                 return ls > rs ? 1 : -1;
 557
 558                         int r = CoreCompare (left.data, right.data);
 559                         if (ls < 0)
 560                                 r = -r;
 561                         return r;
 562                 }
 563
 564
 565                 static int TopByte (uint x)
 566                 {
 567                         if ((x & 0xFFFF0000u) != 0) {
 568                                 if ((x & 0xFF000000u) != 0)
 569                                         return 4;
 570                                 return 3;
 571                         }
 572                         if ((x & 0xFF00u) != 0)
 573                                 return 2;
 574                         return 1;
 575                 }
 576
 577                 static int FirstNonFFByte (uint word)
 578                 {
 579                         if ((word & 0xFF000000u) != 0xFF000000u)
 580                                 return 4;
 581                         else if ((word & 0xFF0000u) != 0xFF0000u)
 582                                 return 3;
 583                         else if ((word & 0xFF00u) != 0xFF00u)
 584                                 return 2;
 585                         return 1;
 586                 }
 587
 588                 public byte[] ToByteArray ()
 589                 {
 590                         if (sign == 0)
 591                                 return new byte [1];
 592
 593                         //number of bytes not counting upper word
 594                         int bytes = (data.Length - 1) * 4;
 595                         bool needExtraZero = false;
 596
 597                         uint topWord = data [data.Length - 1];
 598                         int extra;
 599
 600                         //if the topmost bit is set we need an extra
 601                         if (sign == 1) {
 602                                 extra = TopByte (topWord);
 603                                 uint mask = 0x80u << ((extra - 1) * 8);
 604                                 if ((topWord & mask) != 0) {
 605                                         needExtraZero = true;
 606                                 }
 607                         } else {
 608                                 extra = TopByte (topWord);
 609                         }
 610
 611                         byte[] res = new byte [bytes + extra + (needExtraZero ? 1 : 0) ];
 612                         if (sign == 1) {
 613                                 int j = 0;
 614                                 int end = data.Length - 1;
 615                                 for (int i = 0; i < end; ++i) {
 616                                         uint word = data [i];
 617
 618                                         res [j++] = (byte)word;
 619                                         res [j++] = (byte)(word >> 8);
 620                                         res [j++] = (byte)(word >> 16);
 621                                         res [j++] = (byte)(word >> 24);
 622                                 }
 623                                 while (extra-- > 0) {
 624                                         res [j++] = (byte)topWord;
 625                                         topWord >>= 8;
 626                                 }
 627                         } else {
 628                                 int j = 0;
 629                                 int end = data.Length - 1;
 630
 631                                 uint carry = 1, word;
 632                                 ulong add;
 633                                 for (int i = 0; i < end; ++i) {
 634                                         word = data [i];
 635                                         add = (ulong)~word + carry;
 636                                         word = (uint)add;
 637                                         carry = (uint)(add >> 32);
 638
 639                                         res [j++] = (byte)word;
 640                                         res [j++] = (byte)(word >> 8);
 641                                         res [j++] = (byte)(word >> 16);
 642                                         res [j++] = (byte)(word >> 24);
 643                                 }
 644
 645                                 add = (ulong)~topWord + (carry);
 646                                 word = (uint)add;
 647                                 carry = (uint)(add >> 32);
 648                                 if (carry == 0) {
 649                                         int ex = FirstNonFFByte (word);
 650                                         bool needExtra = (word & (1 << (ex * 8 - 1))) == 0;
 651                                         int to = ex + (needExtra ? 1 : 0);
 652
 653                                         if (to != extra)
 654                                                 res = Resize (res, bytes + to);
 655
 656                                         while (ex-- > 0) {
 657                                                 res [j++] = (byte)word;
 658                                                 word >>= 8;
 659                                         }
 660                                         if (needExtra)
 661                                                 res [j++] = 0xFF;
 662                                 } else {
 663                                         res = Resize (res, bytes + 5);
 664                                         res [j++] = (byte)word;
 665                                         res [j++] = (byte)(word >> 8);
 666                                         res [j++] = (byte)(word >> 16);
 667                                         res [j++] = (byte)(word >> 24);
 668                                         res [j++] = 0xFF;
 669                                 }
 670                         }
 671
 672                         return res;
 673                 }
 674
 675                 static byte[] Resize (byte[] v, int len)
 676                 {\r
 677                         byte[] res = new byte [len];\r
 678                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 679                         return res;\r
 680                 }
 681
 682                 static uint[] Resize (uint[] v, int len)
 683                 {
 684                         uint[] res = new uint [len];\r
 685                         Array.Copy (v, res, Math.Min (v.Length, len));\r
 686                         return res;\r
 687                 }
 688
 689                 static uint[] CoreAdd (uint[] a, uint[] b)
 690                 {
 691                         if (a.Length < b.Length) {
 692                                 uint[] tmp = a;
 693                                 a = b;
 694                                 b = tmp;
 695                         }
 696
 697                         int bl = a.Length;
 698                         int sl = b.Length;
 699
 700                         uint[] res = new uint [bl];
 701
 702                         ulong sum = 0;
 703
 704                         int i = 0;
 705                         for (; i < sl; i++) {
 706                                 sum = sum + a [i] + b [i];
 707                                 res [i] = (uint)sum;
 708                                 sum >>= 32;
 709                         }
 710
 711                         for (; i < bl; i++) {
 712                                 sum = sum + a [i];
 713                                 res [i] = (uint)sum;
 714                                 sum >>= 32;
 715                         }
 716
 717                         if (sum != 0) {
 718                                 res = Resize (res, bl + 1);
 719                                 res [i] = (uint)sum;
 720                         }
 721
 722                         return res;
 723                 }
 724
 725                 /*invariant a > b*/
 726                 static uint[] CoreSub (uint[] a, uint[] b)
 727                 {
 728                         int bl = a.Length;
 729                         int sl = b.Length;
 730
 731                         Console.WriteLine ("bl {0} sl {1}", bl, sl);
 732
 733                         uint[] res = new uint [bl];
 734
 735                         ulong borrow = 0;
 736                         int i;
 737                         for (i = 0; i < sl; ++i) {
 738                                 borrow = (ulong)a [i] - b [i] - borrow;
 739
 740                                 Console.WriteLine ("a {0} b {1}", a[i], b [i]);
 741
 742                                 res [i] = (uint)borrow;
 743                                 borrow = (borrow >> 32) & 0x1;
 744                         }
 745
 746                         for (; i < bl; i++) {
 747                                 borrow = (ulong)a [i] - borrow;
 748                                 res [i] = (uint)borrow;
 749                                 borrow = (borrow >> 32) & 0x1;
 750                         }
 751
 752                         //remove extra zeroes
 753                         for (i = bl - 1; i >= 0 && res [i] == 0; --i) ;
 754                         if (i < bl - 1)
 755                                 res = Resize (res, i + 1);
 756
 757             return res;
 758                 }
 759
 760                 static int CoreCompare (uint[] a, uint[] b)
 761                 {
 762                         int     al = a.Length;
 763                         int bl = b.Length;
 764
 765                         if (al > bl)
 766                                 return 1;
 767                         if (bl > al)
 768                                 return -1;
 769
 770                         for (int i = al - 1; i >= 0; --i) {
 771                                 uint ai = a [i];
 772                                 uint bi = b [i];
 773                                 if (ai > bi)
 774                                         return 1;
 775                                 if (ai < bi)
 776                                         return -1;
 777                         }
 778                         return 0;
 779                 }
 780
 781         }
 782 }\r