src/System.Private.CoreLib/shared/System/Number.BigInteger.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 using System.Diagnostics;
   6 using System.Runtime.InteropServices;
   7 using Internal.Runtime.CompilerServices;
   8
   9 namespace System
  10 {
  11     internal static partial class Number
  12     {
  13         [StructLayout(LayoutKind.Sequential, Pack = 1)]
  14         internal unsafe ref struct BigInteger
  15         {
  16             private const int MaxBlockCount = 35;
  17
  18             private static readonly uint[] s_Pow10UInt32Table = new uint[]
  19             {
  20                 1,          // 10^0
  21                 10,         // 10^1
  22                 100,        // 10^2
  23                 1000,       // 10^3
  24                 10000,      // 10^4
  25                 100000,     // 10^5
  26                 1000000,    // 10^6
  27                 10000000,   // 10^7
  28             };
  29
  30             private static readonly int[] s_s_Pow10BigNumTableIndices = new int[]
  31             {
  32                 0,          // 10^8
  33                 2,          // 10^16
  34                 5,          // 10^32
  35                 10,         // 10^64
  36                 18,         // 10^128
  37                 33,         // 10^256
  38             };
  39
  40             private static readonly uint[] s_Pow10BigNumTable = new uint[]
  41             {
  42                 // 10^8
  43                 1,          // _length
  44                 100000000,  // _blocks
  45
  46                 // 10^16
  47                 2,          // _length
  48                 0x6FC10000, // _blocks
  49                 0x002386F2,
  50
  51                 // 10^32
  52                 4,          // _length
  53                 0x00000000, // _blocks
  54                 0x85ACEF81,
  55                 0x2D6D415B,
  56                 0x000004EE,
  57
  58                 // 10^64
  59                 7,          // _length
  60                 0x00000000, // _blocks
  61                 0x00000000,
  62                 0xBF6A1F01,
  63                 0x6E38ED64,
  64                 0xDAA797ED,
  65                 0xE93FF9F4,
  66                 0x00184F03,
  67
  68                 // 10^128
  69                 14,         // _length
  70                 0x00000000, // _blocks
  71                 0x00000000,
  72                 0x00000000,
  73                 0x00000000,
  74                 0x2E953E01,
  75                 0x03DF9909,
  76                 0x0F1538FD,
  77                 0x2374E42F,
  78                 0xD3CFF5EC,
  79                 0xC404DC08,
  80                 0xBCCDB0DA,
  81                 0xA6337F19,
  82                 0xE91F2603,
  83                 0x0000024E,
  84
  85                 // 10^256
  86                 27,         // _length
  87                 0x00000000, // _blocks
  88                 0x00000000,
  89                 0x00000000,
  90                 0x00000000,
  91                 0x00000000,
  92                 0x00000000,
  93                 0x00000000,
  94                 0x00000000,
  95                 0x982E7C01,
  96                 0xBED3875B,
  97                 0xD8D99F72,
  98                 0x12152F87,
  99                 0x6BDE50C6,
 100                 0xCF4A6E70,
 101                 0xD595D80F,
 102                 0x26B2716E,
 103                 0xADC666B0,
 104                 0x1D153624,
 105                 0x3C42D35A,
 106                 0x63FF540E,
 107                 0xCC5573C0,
 108                 0x65F9EF17,
 109                 0x55BC28F2,
 110                 0x80DCC7F7,
 111                 0xF46EEDDC,
 112                 0x5FDCEFCE,
 113                 0x000553F7,
 114
 115                 // Trailing blocks to ensure MaxBlockCount
 116                 0x00000000,
 117                 0x00000000,
 118                 0x00000000,
 119                 0x00000000,
 120                 0x00000000,
 121                 0x00000000,
 122                 0x00000000,
 123                 0x00000000,
 124             };
 125
 126             private static readonly uint[] s_MultiplyDeBruijnBitPosition = new uint[]
 127             {
 128                 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
 129                 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
 130             };
 131
 132             private int _length;
 133             private fixed uint _blocks[MaxBlockCount];
 134
 135             public BigInteger(uint value)
 136             {
 137                 _blocks[0] = value;
 138                 _length = (value == 0) ? 0 : 1;
 139             }
 140
 141             public BigInteger(ulong value)
 142             {
 143                 var lower = (uint)(value);
 144                 var upper = (uint)(value >> 32);
 145
 146                 _blocks[0] = lower;
 147                 _blocks[1] = upper;
 148
 149                 _length = (upper == 0) ? 1 : 2;
 150             }
 151
 152             public static uint BitScanReverse(uint mask)
 153             {
 154                 // This comes from the Stanford Bit Widdling Hacks by Sean Eron Anderson:
 155                 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
 156
 157                 mask |= (mask >> 1); // first round down to one less than a power of 2
 158                 mask |= (mask >> 2);
 159                 mask |= (mask >> 4);
 160                 mask |= (mask >> 8);
 161                 mask |= (mask >> 16);
 162
 163                 uint index = (mask * 0x07C4ACDD) >> 27;
 164                 return s_MultiplyDeBruijnBitPosition[(int)(index)];
 165             }
 166
 167             public static int Compare(ref BigInteger lhs, ref BigInteger rhs)
 168             {
 169                 Debug.Assert(unchecked((uint)(lhs._length)) <= MaxBlockCount);
 170                 Debug.Assert(unchecked((uint)(rhs._length)) <= MaxBlockCount);
 171
 172                 int lhsLength = lhs._length;
 173                 int rhsLength = rhs._length;
 174
 175                 int lengthDelta = (lhsLength - rhsLength);
 176
 177                 if (lengthDelta != 0)
 178                 {
 179                     return lengthDelta;
 180                 }
 181
 182                 if (lhsLength == 0)
 183                 {
 184                     Debug.Assert(rhsLength == 0);
 185                     return 0;
 186                 }
 187
 188                 for (int index = (lhsLength - 1); index >= 0; index--)
 189                 {
 190                     long delta = (long)(lhs._blocks[index]) - rhs._blocks[index];
 191
 192                     if (delta != 0)
 193                     {
 194                         return delta > 0 ? 1 : -1;
 195                     }
 196                 }
 197
 198                 return 0;
 199             }
 200
 201             public static uint HeuristicDivide(ref BigInteger dividend, ref BigInteger divisor)
 202             {
 203                 int divisorLength = divisor._length;
 204
 205                 if (dividend._length < divisorLength)
 206                 {
 207                     return 0;
 208                 }
 209
 210                 // This is an estimated quotient. Its error should be less than 2.
 211                 // Reference inequality:
 212                 // a/b - floor(floor(a)/(floor(b) + 1)) < 2
 213                 int lastIndex = (divisorLength - 1);
 214                 uint quotient = dividend._blocks[lastIndex] / (divisor._blocks[lastIndex] + 1);
 215
 216                 if (quotient != 0)
 217                 {
 218                     // Now we use our estimated quotient to update each block of dividend.
 219                     // dividend = dividend - divisor * quotient
 220                     int index = 0;
 221
 222                     ulong borrow = 0;
 223                     ulong carry = 0;
 224
 225                     do
 226                     {
 227                         ulong product = ((ulong)(divisor._blocks[index]) * quotient) + carry;
 228                         carry = product >> 32;
 229
 230                         ulong difference = (ulong)(dividend._blocks[index]) - (uint)(product) - borrow;
 231                         borrow = (difference >> 32) & 1;
 232
 233                         dividend._blocks[index] = (uint)(difference);
 234
 235                         index++;
 236                     }
 237                     while (index < divisorLength);
 238
 239                     // Remove all leading zero blocks from dividend
 240                     while ((divisorLength > 0) && (dividend._blocks[divisorLength - 1] == 0))
 241                     {
 242                         divisorLength--;
 243                     }
 244
 245                     dividend._length = divisorLength;
 246                 }
 247
 248                 // If the dividend is still larger than the divisor, we overshot our estimate quotient. To correct,
 249                 // we increment the quotient and subtract one more divisor from the dividend (Because we guaranteed the error range).
 250                 if (Compare(ref dividend, ref divisor) >= 0)
 251                 {
 252                     quotient++;
 253
 254                     // dividend = dividend - divisor
 255                     int index = 0;
 256                     ulong borrow = 0;
 257
 258                     do
 259                     {
 260                         ulong difference = (ulong)(dividend._blocks[index]) - divisor._blocks[index] - borrow;
 261                         borrow = (difference >> 32) & 1;
 262
 263                         dividend._blocks[index] = (uint)(difference);
 264
 265                         index++;
 266                     }
 267                     while (index < divisorLength);
 268
 269                     // Remove all leading zero blocks from dividend
 270                     while ((divisorLength > 0) && (dividend._blocks[divisorLength - 1] == 0))
 271                     {
 272                         divisorLength--;
 273                     }
 274
 275                     dividend._length = divisorLength;
 276                 }
 277
 278                 return quotient;
 279             }
 280
 281             public static uint LogBase2(uint value)
 282             {
 283                 Debug.Assert(value != 0);
 284                 return BitScanReverse(value);
 285             }
 286
 287             public static uint LogBase2(ulong value)
 288             {
 289                 Debug.Assert(value != 0);
 290
 291                 uint upper = (uint)(value >> 32);
 292
 293                 if (upper != 0)
 294                 {
 295                     return 32 + LogBase2(upper);
 296                 }
 297
 298                 return LogBase2((uint)(value));
 299             }
 300
 301             public static void Multiply(ref BigInteger lhs, uint value, ref BigInteger result)
 302             {
 303                 if (lhs.IsZero() || (value == 1))
 304                 {
 305                     result.SetValue(ref lhs);
 306                     return;
 307                 }
 308
 309                 if (value == 0)
 310                 {
 311                     result.SetZero();
 312                     return;
 313                 }
 314
 315                 int lhsLength = lhs._length;
 316                 int index = 0;
 317
 318                 ulong carry = 0;
 319
 320                 while (index < lhsLength)
 321                 {
 322                     ulong product = ((ulong)(lhs._blocks[index]) * value) + carry;
 323                     carry = product >> 32;
 324                     result._blocks[index] = (uint)(product);
 325
 326                     index++;
 327                 }
 328
 329                 if (carry != 0)
 330                 {
 331                     Debug.Assert(unchecked((uint)(lhsLength)) + 1 <= MaxBlockCount);
 332                     result._blocks[index] = (uint)(carry);
 333                     result._length += (lhsLength + 1);
 334                 }
 335             }
 336
 337             public static void Multiply(ref BigInteger lhs, ref BigInteger rhs, ref BigInteger result)
 338             {
 339                 if (lhs.IsZero() || rhs.IsOne())
 340                 {
 341                     result.SetValue(ref lhs);
 342                     return;
 343                 }
 344
 345                 if (rhs.IsZero())
 346                 {
 347                     result.SetZero();
 348                     return;
 349                 }
 350
 351                 ref readonly BigInteger large = ref lhs;
 352                 int largeLength = lhs._length;
 353
 354                 ref readonly BigInteger small = ref rhs;
 355                 int smallLength = rhs._length;
 356
 357                 if (largeLength < smallLength)
 358                 {
 359                     large = ref rhs;
 360                     largeLength = rhs._length;
 361
 362                     small = ref lhs;
 363                     smallLength = lhs._length;
 364                 }
 365
 366                 int maxResultLength = smallLength + largeLength;
 367                 Debug.Assert(unchecked((uint)(maxResultLength)) <= MaxBlockCount);
 368
 369                 // Zero out result internal blocks.
 370                 Buffer.ZeroMemory((byte*)(result.GetBlocksPointer()), (maxResultLength * sizeof(uint)));
 371
 372                 int smallIndex = 0;
 373                 int resultStartIndex = 0;
 374
 375                 while (smallIndex < smallLength)
 376                 {
 377                     // Multiply each block of large BigNum.
 378                     if (small._blocks[smallIndex] != 0)
 379                     {
 380                         int largeIndex = 0;
 381                         int resultIndex = resultStartIndex;
 382
 383                         ulong carry = 0;
 384
 385                         do
 386                         {
 387                             ulong product = result._blocks[resultIndex] + ((ulong)(small._blocks[smallIndex]) * large._blocks[largeIndex]) + carry;
 388                             carry = product >> 32;
 389                             result._blocks[resultIndex] = (uint)(product);
 390
 391                             resultIndex++;
 392                             largeIndex++;
 393                         }
 394                         while (largeIndex < largeLength);
 395
 396                         result._blocks[resultIndex] = (uint)(carry);
 397                     }
 398
 399                     smallIndex++;
 400                     resultStartIndex++;
 401                 }
 402
 403                 if ((maxResultLength > 0) && (result._blocks[maxResultLength - 1] == 0))
 404                 {
 405                     result._length = (maxResultLength - 1);
 406                 }
 407                 else
 408                 {
 409                     result._length = maxResultLength;
 410                 }
 411             }
 412
 413             public static void Pow10(uint exponent, ref BigInteger result)
 414             {
 415                 // We leverage two arrays - s_Pow10UInt32Table and s_Pow10BigNumTable to speed up the Pow10 calculation.
 416                 //
 417                 // s_Pow10UInt32Table stores the results of 10^0 to 10^7.
 418                 // s_Pow10BigNumTable stores the results of 10^8, 10^16, 10^32, 10^64, 10^128 and 10^256.
 419                 //
 420                 // For example, let's say exp = 0b111111. We can split the exp to two parts, one is small exp,
 421                 // which 10^smallExp can be represented as uint, another part is 10^bigExp, which must be represented as BigNum.
 422                 // So the result should be 10^smallExp * 10^bigExp.
 423                 //
 424                 // Calculating 10^smallExp is simple, we just lookup the 10^smallExp from s_Pow10UInt32Table.
 425                 // But here's a bad news: although uint can represent 10^9, exp 9's binary representation is 1001.
 426                 // That means 10^(1011), 10^(1101), 10^(1111) all cannot be stored as uint, we cannot easily say something like:
 427                 // "Any bits <= 3 is small exp, any bits > 3 is big exp". So instead of involving 10^8, 10^9 to s_Pow10UInt32Table,
 428                 // consider 10^8 and 10^9 as a bigNum, so they fall into s_Pow10BigNumTable. Now we can have a simple rule:
 429                 // "Any bits <= 3 is small exp, any bits > 3 is big exp".
 430                 //
 431                 // For 0b111111, we first calculate 10^(smallExp), which is 10^(7), now we can shift right 3 bits, prepare to calculate the bigExp part,
 432                 // the exp now becomes 0b000111.
 433                 //
 434                 // Apparently the lowest bit of bigExp should represent 10^8 because we have already shifted 3 bits for smallExp, so s_Pow10BigNumTable[0] = 10^8.
 435                 // Now let's shift exp right 1 bit, the lowest bit should represent 10^(8 * 2) = 10^16, and so on...
 436                 //
 437                 // That's why we just need the values of s_Pow10BigNumTable be power of 2.
 438                 //
 439                 // More details of this implementation can be found at: https://github.com/dotnet/coreclr/pull/12894#discussion_r128890596
 440
 441                 BigInteger temp1 = new BigInteger(s_Pow10UInt32Table[exponent & 0x7]);
 442                 ref BigInteger lhs = ref temp1;
 443
 444                 BigInteger temp2 = new BigInteger(0);
 445                 ref BigInteger product = ref temp2;
 446
 447                 exponent >>= 3;
 448                 uint index = 0;
 449
 450                 while (exponent != 0)
 451                 {
 452                     // If the current bit is set, multiply it with the corresponding power of 10
 453                     if ((exponent & 1) != 0)
 454                     {
 455                         // Multiply into the next temporary
 456                         ref BigInteger rhs = ref *(BigInteger*)(Unsafe.AsPointer(ref s_Pow10BigNumTable[s_s_Pow10BigNumTableIndices[index]]));
 457                         Multiply(ref lhs, ref rhs, ref product);
 458
 459                         // Swap to the next temporary
 460                         ref BigInteger temp = ref product;
 461                         product = ref lhs;
 462                         lhs = ref temp;
 463                     }
 464
 465                     // Advance to the next bit
 466                     ++index;
 467                     exponent >>= 1;
 468                 }
 469
 470                 result.SetValue(ref lhs);
 471             }
 472
 473             public static void PrepareHeuristicDivide(ref BigInteger dividend, ref BigInteger divisor)
 474             {
 475                 uint hiBlock = divisor._blocks[divisor._length - 1];
 476
 477                 if ((hiBlock < 8) || (hiBlock > 429496729))
 478                 {
 479                     // Inspired by http://www.ryanjuckett.com/programming/printing-floating-point-numbers/
 480                     // Perform a bit shift on all values to get the highest block of the divisor into
 481                     // the range [8,429496729]. We are more likely to make accurate quotient estimations
 482                     // in heuristicDivide() with higher divisor values so
 483                     // we shift the divisor to place the highest bit at index 27 of the highest block.
 484                     // This is safe because (2^28 - 1) = 268435455 which is less than 429496729. This means
 485                     // that all values with a highest bit at index 27 are within range.
 486                     uint hiBlockLog2 = LogBase2(hiBlock);
 487                     uint shift = (59 - hiBlockLog2) % 32;
 488
 489                     divisor.ShiftLeft(shift);
 490                     dividend.ShiftLeft(shift);
 491                 }
 492             }
 493
 494             public static void ShiftLeft(ulong input, uint shift, ref BigInteger output)
 495             {
 496                 if (shift == 0)
 497                 {
 498                     return;
 499                 }
 500
 501                 uint blocksToShift = Math.DivRem(shift, 32, out uint remainingBitsToShift);
 502
 503                 if (blocksToShift > 0)
 504                 {
 505                     // If blocks shifted, we should fill the corresponding blocks with zero.
 506                     output.ExtendBlocks(0, blocksToShift);
 507                 }
 508
 509                 if (remainingBitsToShift == 0)
 510                 {
 511                     // We shift 32 * n (n >= 1) bits. No remaining bits.
 512                     output.ExtendBlock((uint)(input));
 513
 514                     uint highBits = (uint)(input >> 32);
 515
 516                     if (highBits != 0)
 517                     {
 518                         output.ExtendBlock(highBits);
 519                     }
 520                 }
 521                 else
 522                 {
 523                     // Extract the high position bits which would be shifted out of range.
 524                     uint highPositionBits = (uint)(input) >> (int)(64 - remainingBitsToShift);
 525
 526                     // Shift the input. The result should be stored to current block.
 527                     ulong shiftedInput = input << (int)(remainingBitsToShift);
 528                     output.ExtendBlock((uint)(shiftedInput));
 529
 530                     uint highBits = (uint)(input >> 32);
 531
 532                     if (highBits != 0)
 533                     {
 534                         output.ExtendBlock(highBits);
 535                     }
 536
 537                     if (highPositionBits != 0)
 538                     {
 539                         // If the high position bits is not 0, we should store them to next block.
 540                         output.ExtendBlock(highPositionBits);
 541                     }
 542                 }
 543             }
 544
 545             public void ExtendBlock(uint blockValue)
 546             {
 547                 _blocks[_length] = blockValue;
 548                 _length++;
 549             }
 550
 551             public void ExtendBlocks(uint blockValue, uint blockCount)
 552             {
 553                 Debug.Assert(blockCount > 0);
 554
 555                 if (blockCount == 1)
 556                 {
 557                     ExtendBlock(blockValue);
 558
 559                     return;
 560                 }
 561
 562                 Buffer.ZeroMemory((byte*)(GetBlocksPointer() + _length), ((blockCount - 1) * sizeof(uint)));
 563                 _length += (int)(blockCount);
 564                 _blocks[_length - 1] = blockValue;
 565             }
 566
 567             public bool IsOne()
 568             {
 569                 return (_length == 1)
 570                     && (_blocks[0] == 1);
 571             }
 572
 573             public bool IsZero()
 574             {
 575                 return _length == 0;
 576             }
 577
 578             public void Multiply(uint value)
 579             {
 580                 Multiply(ref this, value, ref this);
 581             }
 582
 583             public void Multiply(ref BigInteger value)
 584             {
 585                 var result = new BigInteger(0);
 586                 Multiply(ref this, ref value, ref result);
 587
 588                 Buffer.Memcpy((byte*)(GetBlocksPointer()), (byte*)(result.GetBlocksPointer()), (result._length) * sizeof(uint));
 589                 _length = result._length;
 590             }
 591
 592             public void Multiply10()
 593             {
 594                 if (IsZero())
 595                 {
 596                     return;
 597                 }
 598
 599                 int index = 0;
 600                 int length = _length;
 601                 ulong carry = 0;
 602
 603                 while (index < length)
 604                 {
 605                     var block = (ulong)(_blocks[index]);
 606                     ulong product = (block << 3) + (block << 1) + carry;
 607                     carry = product >> 32;
 608                     _blocks[index] = (uint)(product);
 609
 610                     index++;
 611                 }
 612
 613                 if (carry != 0)
 614                 {
 615                     Debug.Assert(unchecked((uint)(_length)) + 1 <= MaxBlockCount);
 616                     _blocks[index] = (uint)(carry);
 617                     _length += 1;
 618                 }
 619             }
 620
 621             public void SetUInt32(uint value)
 622             {
 623                 _blocks[0] = value;
 624                 _length = 1;
 625             }
 626
 627             public void SetUInt64(ulong value)
 628             {
 629                 var lower = (uint)(value);
 630                 var upper = (uint)(value >> 32);
 631
 632                 _blocks[0] = lower;
 633                 _blocks[1] = upper;
 634
 635                 _length = (upper == 0) ? 1 : 2;
 636             }
 637
 638             public void SetValue(ref BigInteger rhs)
 639             {
 640                 int rhsLength = rhs._length;
 641                 Buffer.Memcpy((byte*)(GetBlocksPointer()), (byte*)(rhs.GetBlocksPointer()), (rhsLength * sizeof(uint)));
 642                 _length = rhsLength;
 643             }
 644
 645             public void SetZero()
 646             {
 647                 _length = 0;
 648             }
 649
 650             public void ShiftLeft(uint shift)
 651             {
 652                 // Process blocks high to low so that we can safely process in place
 653                 var length = _length;
 654
 655                 if ((length == 0) || (shift == 0))
 656                 {
 657                     return;
 658                 }
 659
 660                 uint blocksToShift = Math.DivRem(shift, 32, out uint remainingBitsToShift);
 661
 662                 // Copy blocks from high to low
 663                 int readIndex = (length - 1);
 664                 int writeIndex = readIndex + (int)(blocksToShift);
 665
 666                 // Check if the shift is block aligned
 667                 if (remainingBitsToShift == 0)
 668                 {
 669                     Debug.Assert(writeIndex < MaxBlockCount);
 670
 671                     while (readIndex >= 0)
 672                     {
 673                         _blocks[writeIndex] = _blocks[readIndex];
 674                         readIndex--;
 675                         writeIndex--;
 676                     }
 677
 678                     _length += (int)(blocksToShift);
 679
 680                     // Zero the remaining low blocks
 681                     Buffer.ZeroMemory((byte*)(GetBlocksPointer()), (blocksToShift * sizeof(uint)));
 682                 }
 683                 else
 684                 {
 685                     // We need an extra block for the partial shift
 686                     writeIndex++;
 687                     Debug.Assert(writeIndex < MaxBlockCount);
 688
 689                     // Set the length to hold the shifted blocks
 690                     _length = writeIndex + 1;
 691
 692                     // Output the initial blocks
 693                     uint lowBitsShift = (32 - remainingBitsToShift);
 694                     uint highBits = 0;
 695                     uint block = _blocks[readIndex];
 696                     uint lowBits = block >> (int)(lowBitsShift);
 697                     while (readIndex > 0)
 698                     {
 699                         _blocks[writeIndex] = highBits | lowBits;
 700                         highBits = block << (int)(remainingBitsToShift);
 701
 702                         --readIndex;
 703                         --writeIndex;
 704
 705                         block = _blocks[readIndex];
 706                         lowBits = block >> (int)lowBitsShift;
 707                     }
 708
 709                     // Output the final blocks
 710                     _blocks[writeIndex] = highBits | lowBits;
 711                     _blocks[writeIndex - 1] = block << (int)(remainingBitsToShift);
 712
 713                     // Zero the remaining low blocks
 714                     Buffer.ZeroMemory((byte*)(GetBlocksPointer()), (blocksToShift * sizeof(uint)));
 715
 716                     // Check if the terminating block has no set bits
 717                     if (_blocks[_length - 1] == 0)
 718                     {
 719                         _length--;
 720                     }
 721                 }
 722             }
 723
 724             private uint* GetBlocksPointer()
 725             {
 726                 // This is safe to do since we are a ref struct
 727                 return (uint*)(Unsafe.AsPointer(ref _blocks[0]));
 728             }
 729         }
 730     }
 731 }