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